L'apprentissage automatique peut-il apprendre une fonction comme trouver le maximum dans une liste?

J'ai une entrée qui est une liste et la sortie est le maximum des éléments de la liste d'entrée.

L'apprentissage automatique peut-il apprendre une telle fonction qui sélectionne toujours le maximum des éléments d'entrée présents dans l'entrée?

Cela peut sembler une question assez basique mais cela pourrait me donner une compréhension de ce que l'apprentissage automatique peut faire en général. Merci!

Peut - être , mais notez que c'est l'un de ces cas où l'apprentissage automatique n'est pas la réponse . Il y a une tendance à essayer l'apprentissage automatique du chausse-pied dans les cas où, en réalité, les solutions basées sur des règles standard sont plus rapides, plus simples et tout simplement le bon choix: P

Ce n'est pas parce que vous le pouvez que vous devriez

Edit : à l'origine, j'ai écrit ceci comme "Oui, mais notez que ..." mais j'ai ensuite commencé à douter de moi-même, ne l'ayant jamais vu faire. Je l'ai essayé cet après-midi et c'est certainement faisable:

import numpy as np
from keras.models import Model
from keras.layers import Input, Dense, Dropout
from keras.utils import to_categorical
from sklearn.model_selection import train_test_split
from keras.callbacks import EarlyStopping

# Create an input array of 50,000 samples of 20 random numbers each
x = np.random.randint(0, 100, size=(50000, 20))

# And a one-hot encoded target denoting the index of the maximum of the inputs
y = to_categorical(np.argmax(x, axis=1), num_classes=20)

# Split into training and testing datasets
x_train, x_test, y_train, y_test = train_test_split(x, y)

# Build a network, probaly needlessly complicated since it needs a lot of dropout to
# perform even reasonably well.

i = Input(shape=(20, ))
a = Dense(1024, activation='relu')(i)
b = Dense(512, activation='relu')(a)
ba = Dropout(0.3)(b)
c = Dense(256, activation='relu')(ba)
d = Dense(128, activation='relu')(c)
o = Dense(20, activation='softmax')(d)

model = Model(inputs=i, outputs=o)

es = EarlyStopping(monitor='val_loss', patience=3)

model.compile(optimizer='adam', loss='categorical_crossentropy')

model.fit(x_train, y_train, epochs=15, batch_size=8, validation_data=[x_test, y_test], callbacks=[es])

print(np.where(np.argmax(model.predict(x_test), axis=1) == np.argmax(y_test, axis=1), 1, 0).mean())

La sortie est de 0,74576, il trouve donc correctement le maximum 74,5% du temps. Je ne doute pas que cela pourrait être amélioré, mais comme je le dis, ce n'est pas un cas d'utilisation que je recommanderais pour ML.

EDIT 2 : En fait, j'ai relancé ce matin en utilisant RandomForestClassifier de sklearn et il a nettement mieux fonctionné:

# instantiation of the arrays is identical

rfc = RandomForestClassifier(n_estimators=1000, verbose=1)
rfc.fit(x_train, y_train)

yhat_proba = rfc.predict_proba(x_test)


# We have some annoying transformations to do because this .predict_proba() call returns the data in a weird format of shape (20, 12500, 2).

for i in range(len(yhat_proba)):
    yhat_proba[i] = yhat_proba[i][:, 1]

pyhat = np.reshape(np.ravel(yhat_proba), (12500,20), order='F')

print(np.where(np.argmax(pyhat, axis=1) == np.argmax(y_test, axis=1), 1, 0).mean())

Et le score ici est de 94,4% des échantillons avec le max correctement identifié, ce qui est assez bon en effet.

Oui. Très important, VOUS décidez de l'architecture d'une solution d'apprentissage automatique. Les architectures et les procédures de formation ne s'écrivent pas elles-mêmes; ils doivent être conçus ou modélisés et la formation s'ensuit comme un moyen de découvrir une paramétrisation de l'architecture adaptée à un ensemble de points de données.

Vous pouvez construire une architecture très simple qui inclut en fait une fonction maximale:

net(x) = a * max(x) + b * min(x)

où a et b sont des paramètres appris.

Avec suffisamment d'échantillons de formation et une routine de formation raisonnable, cette architecture très simple apprendra très rapidement à mettre a 1 et b à zéro pour votre tâche.

L'apprentissage automatique prend souvent la forme d'hypothèses multiples sur la personnalisation et la transformation des points de données d'entrée, et d'apprendre à ne conserver que les hypothèses qui sont corrélées avec la variable cible. Les hypothèses sont encodées explicitement dans l'architecture et les sous-fonctions disponibles dans un algorithme paramétré, ou comme les hypothèses encodées dans un algorithme "sans paramètre".

Par exemple, le choix d'utiliser des produits scalaires et des non-linéarités comme cela est courant dans le réseau neuronal vanille ML est quelque peu arbitraire; il exprime l'hypothèse englobante selon laquelle une fonction peut être construite en utilisant une structure de réseau compositionnelle prédéterminée de transformations linéaires et de fonctions de seuil. Différentes paramétrisations de ce réseau incarnent différentes hypothèses sur les transformations linéaires à utiliser. N'importe quelle boîte à outils de fonctions peut être utilisée et le travail d'un apprenant machine consiste à découvrir par différenciation ou essai et erreur ou tout autre signal reproductible quelles fonctions ou fonctionnalités de sa matrice minimisent le mieux une mesure d'erreur. Dans l'exemple donné ci-dessus, le réseau appris se réduit simplement à la fonction maximale elle-même, tandis qu'un réseau indifférencié pourrait alternativement "apprendre" une fonction minimale. Ces fonctions peuvent être exprimées ou approchées par d'autres moyens, comme dans la fonction de régression nette linéaire ou neuronale dans une autre réponse. En somme, cela dépend vraiment des fonctions ou des pièces LEGO que vous avez dans votre boîte à outils d'architecture ML.

Oui - L'apprentissage automatique peut apprendre à trouver le maximum dans une liste de nombres.

Voici un exemple simple d'apprentissage pour trouver l'indice du maximum:

import numpy as np
from sklearn.tree import DecisionTreeClassifier

# Create training pairs where the input is a list of numbers and the output is the argmax
training_data = np.random.rand(10_000, 5) # Each list is 5 elements; 10K examples
training_targets = np.argmax(input_data, axis=1)

# Train a descision tree with scikit-learn
clf = DecisionTreeClassifier()
clf.fit(input_data, targets)

# Let's see if the trained model can correctly predict the argmax for new data
test_data = np.random.rand(1, 5)
prediction = clf.predict(test_data)
assert prediction == np.argmax(test_data) # The test passes - The model has learned argmax

Algorithmes d'apprentissage

Au lieu d'apprendre une fonction comme un calcul effectué par un réseau de neurones à action directe, il y a tout un domaine de recherche concernant les algorithmes d' apprentissage à partir d'échantillons de données. Par exemple, on pourrait utiliser quelque chose comme une Neural Turing Machine ou une autre méthode où l'exécution d'un algorithme est contrôlée par l'apprentissage automatique à ses points de décision. Les algorithmes de jouets comme la recherche d'un maximum ou le tri d'une liste, ou l'inversion d'une liste ou le filtrage d'une liste sont couramment utilisés comme exemples dans la recherche d'apprentissage d'algorithmes.

J'exclurai les conceptions instruites de ma réponse. Non, il n'est pas possible d'utiliser une approche d'apprentissage machine (ML) prête à l'emploi pour représenter pleinement la fonction maximale pour des listes arbitraires avec une précision arbitraire. ML est une méthode basée sur les données et il est clair que vous ne pourrez pas approximer une fonction dans les régions où vous n'avez pas de points de données. Par conséquent, l'espace des observations possibles (qui est infini) ne peut pas être couvert par des observations finies.

Mes déclarations ont une base théorique avec le théorème d'approximation universelle de Cybeko pour les réseaux de neurones. Je vais citer le théorème de Wikipedia:

$\mathbb{R}^n$

$\mathbb{R}^n$$x\in \mathbb{R}$

Si votre espace d'observations est compact, vous pourrez peut-être approximer la fonction maximale avec un ensemble de données finies. Comme la réponse la plus votée l'a clairement montré, vous ne devez pas réinventer la roue!

Voici une extension de mon commentaire. Pour commencer, absolument @DanScally a raison de dire qu'il n'y a aucune raison d'utiliser ML pour trouver le maximum d'une liste. Mais je pense que votre "cela pourrait me donner une compréhension de ce que l'apprentissage automatique peut faire en général" est une raison suffisante pour approfondir cela.

$\max$$\max$

$\max$$\max$$\max$

$n$ $n$

$\operatorname{argmax}$$n$$\binom{n}{2}$$\delta_{ij} = \mathbf{1}(x_i < x_j)$$i<j$$x_j-x_i$$n$$x_i$$\sum_{j<i} \delta_{ji} + \sum_{j>i} (1-\delta_{ij})$$j$$x_i>x_j$$x_i$dans la liste triée. Pour terminer l'argmax, il suffit de seuiller cette couche.
À ce stade, si nous pouvions multiplier, nous obtiendrions la valeur maximale réelle assez facilement. La solution dans l'article est d'utiliser la représentation binaire des nombres, à quel point la multiplication binaire est la même que l'addition seuil. Pour obtenir juste l'argmax, il suffit d'avoir une simple fonction linéaire multipliant le ème indicateur par et sommant.$i$$i$

Enfin, pour la question suivante: pouvons-nous former un NN dans cet état? @DanScally nous a permis de démarrer; Peut-être que connaître l'architecture théorique peut nous aider à tromper la solution? (Notez que si nous pouvons apprendre / approximer l'ensemble particulier de poids ci-dessus, le filet fonctionnera réellement bien en dehors de la plage des échantillons d'entraînement.)

Carnet dans github / Colab

En changeant un peu les choses, j'obtiens un meilleur score de test (0,838), et même des tests sur un échantillon en dehors de la plage d'entraînement d'origine obtiennent un score décent (0,698). Utilisation d'entrées mises à l'échelle à$[-1,1]$obtient le score du test jusqu'à 0,961, avec un score hors plage de 0,758. Mais, je marque avec la même méthode que @DanScally, ce qui semble un peu malhonnête: la fonction d'identité marquera parfaitement sur cette métrique. J'ai également imprimé quelques coefficients pour voir si quelque chose de proche de l'ajustement exact décrit ci-dessus apparaît (pas vraiment); et quelques sorties brutes, qui suggèrent que le modèle est trop timide pour prédire un maximum, préférant ne pas prédire qu'aucune des entrées n'est le maximum. Peut-être que modifier l'objectif pourrait aider, mais à ce stade, j'ai déjà mis trop de temps; si quelqu'un veut améliorer l'approche, n'hésitez pas à jouer (dans Colab si vous voulez) et faites le moi savoir.

Oui, même un apprentissage automatique aussi simple que les moindres carrés linéaires ordinaires peut le faire si vous utilisez une certaine intelligence appliquée.

(Mais la plupart considéreraient cette surestimation assez horrible).

(Je suppose que nous voulons trouver le maximum d'abs du vecteur d'entrée):

1. Sélectionnez une fonction monotone décroissante de valeur absolue, par exemple $$f(x) = \frac{1}{x^2}$$
2. Construisez une matrice diagonale de . Appelons-le$f({\bf r})$$\bf C_r$
3. Vecteur de construction complète de ceux .$\bf S$
4. Construire et résoudre un système d'équations$(\epsilon {\bf I}+10^3{\bf S}^t{\bf S}+{\bf C_r})^{-1}(10^3 {\bf S}^t)$
5. Appelons le vecteur de résultat , ce sera une mesure de probabilité (somme à 1), nous pouvons le peser de façon non linéaire, par exemple$\bf p$ $$p_i = \frac{p_i^k}{\sum|p_i|^k}$$
6. Calculez simplement le produit scalaire avec le vecteur d'index et arrondissez.