Le perceptron à partir de zéro : ce que calcule un neurone

Un perceptron prend les mesures, multiplie chacune par un nombre qu’il contrôle, les additionne, ajoute encore un nombre, puis regarde le signe.

Écrivez les mesures d’une pièce sous forme de vecteur $\mathbf{x} = (x_1, x_2)$ — largeur et poids. Le perceptron possède un vecteur de poids $\mathbf{w} = (w_1, w_2)$ et un biais $b$. Son score est

et sa réponse est le signe de ce score : accepter si $s(\mathbf{x}) \geq 0$, rejeter sinon.

C’est tout le modèle. Tout ce que le perceptron saura jamais de l’usine tient dans trois nombres.

La géométrie mérite qu’on s’y arrête, car c’est l’image qui continue de fonctionner pendant les vingt-neuf chapitres suivants, même lorsque les équations ne tiennent plus sur une ligne. L’ensemble des points où $s(\mathbf{x}) = 0$ — là où le perceptron est exactement indécis — est une droite dans le plan. D’un côté, le score est positif et tout est accepté ; de l’autre, il est négatif et tout est rejeté. Pour un perceptron, apprendre signifie déplacer cette droite.

Deux faits à propos de cette droite découlent directement de l’algèbre, et tous deux compteront plus tard :

• $\mathbf{w}$ lui est perpendiculaire. Le vecteur de poids ne longe pas la frontière, il la traverse, en pointant vers le côté accepté.
• $b$ la fait glisser sans la faire pivoter. Sans biais, la droite serait forcée de passer par l’origine, ce qui, pour une usine qui mesure des millimètres et des grammes, serait une contrainte absurde — cela voudrait dire qu’une pièce de largeur nulle et de poids nul se trouve exactement sur la frontière.

Le perceptron commence en ne sachant rien : $\mathbf{w} = (0, 0)$ et $b = 0$. Chaque score vaut zéro, donc il accepte tout.

Montrez-lui maintenant un exemple à la fois. Étiquetez les pièces acceptées $y = +1$ et les pièces rejetées $y = -1$. Pour chaque exemple, posez une seule question : le signe est-il le bon ? La façon compacte d’écrire cette question consiste à vérifier si $y \cdot s(\mathbf{x})$ est positif — si l’étiquette et le score ont le même signe, leur produit est positif, et s’ils sont en désaccord il est négatif.

Si la réponse est oui, ne changez rien. Si la réponse est non, donnez une impulsion :

C’est tout l’algorithme, et il vaut la peine de comprendre pourquoi c’est la bonne impulsion plutôt que de la mémoriser. Supposons qu’une pièce aurait dû être acceptée ($y = +1$) et que le score soit sorti négatif. Ajouter $\mathbf{x}$ à $\mathbf{w}$ modifie le score sur cette même pièce de

ce qui est un nombre positif. Le score de la pièce qu’il vient de mal classer augmente, ce qui est la direction dont il avait besoin. La règle n’est pas une heuristique devinée par quelqu’un ; c’est le plus petit changement qui améliore de façon prouvable le cas devant lui. Elle peut bien sûr casser un autre cas, ce qui explique pourquoi vous recommencez un tour.

Remarquez ce qui est absent. Il n’y a aucune dérivée nulle part. Ce n’est pas un oubli, et c’est la première idée réellement importante du cours.

Ce que vous voudriez dériver, c’est l’erreur — le nombre de pièces mal classées. Mais ce compte est un escalier : il reste plat à 4 pendant que vous déplacez légèrement la ligne, puis tombe à 3 dès que la ligne franchit un point. Sa dérivée est nulle presque partout et indéfinie sur les marches. Le calcul différentiel n’a aucune prise. La règle du perceptron contourne cela en ne demandant pas du tout de pente : elle demande seulement « correct ou incorrect ? », puis se déplace dans une direction qu’elle peut justifier géométriquement.

C’est une vraie solution, et c’est aussi une impasse. Au Chapitre 2, nous voudrons une loss qui vient de quelque part plutôt que d’être choisie ; au Chapitre 4, un modèle qui indique à quel point il est sûr ; et au Chapitre 5, quelque chose avec plus d’une couche — et aucun de ces objectifs n’est atteignable avec une règle qui ne connaît que « faux ». Récupérer une pente utilisable est ce qui impose les deux chapitres suivants. Mais le perceptron peut faire quelque chose qu’aucun de ses successeurs ne peut faire : apprendre sans aucun calcul différentiel.

Python pur, sans NumPy. Des listes et une boucle. NumPy arrive au chapitre suivant, lorsque l’arithmétique ne tient plus dans une boucle que vous auriez envie de lire ; l’introduire maintenant cacherait l’arithmétique derrière une bibliothèque au moment précis où vous voulez la voir.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Les quatre lignes mises en évidence sont l’algorithme. Tout le reste est de la comptabilité.

Et voici le tapis, avec huit pièces mesurées dessus — quatre expédiées et quatre revenues :

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Ces huit pièces sont séparables par une droite — chaque pièce acceptée mesure moins de 22 mm et chaque pièce rejetée mesure 23 mm ou plus. Une barrière verticale à 22 millimètres fait l’affaire. Le perceptron devrait donc la trouver.

Exécutez-le :

None [-142.1, -13.0] 54.0

Deux cents époques, 454 corrections, et il n’a pas convergé. Les poids sont grands et du mauvais signe. Quelque chose cloche — sauf que rien ne cloche, et la raison est l’élément le plus utile de ce chapitre.

Le perceptron dispose d’une garantie, prouvée par Novikoff en 1962.¹ Si les données peuvent être séparées par une droite, l’algorithme effectue au plus

corrections avant de cesser d’en faire — où $R$ est le rayon des données, la longueur du plus long vecteur d’exemple, et $\gamma$ est la marge : la distance entre l’hyperplan séparateur et le point le plus proche dans l’espace augmenté où le biais est une troisième coordonnée. C’est pourquoi centrer les données la modifie alors que la distance en millimètres ne change pas.

La garantie est inconditionnelle et elle ne mentionne ni époques, ni taux d’apprentissage, ni chance. Elle ne mentionne pas non plus le temps, et c’est précisément le sujet.

Insérons nos nombres. Mesurés directement à partir des huit pièces, avec le biais replié comme variable constante :

Le théorème n’a jamais été violé. Exécutez la version brute assez longtemps et elle converge effectivement — à l’époque 11 976, après 29 870 corrections — largement à l’intérieur de sa borne de 2 633 550, et cet écart est lui-même le sujet : le théorème borne le pire cas, pas le cas typique. Il lui fallait simplement soixante fois plus d’époques que ce que n’importe qui accepterait d’attendre.

La deuxième ligne correspond aux mêmes huit pièces, aux mêmes vingt lignes de code, avec trois lignes ajoutées pour soustraire la largeur moyenne et le poids moyen de chaque mesure. C’est tout. C’est tout le changement. Cela déplace le nuage de points pour qu’il chevauche l’origine au lieu de flotter vers (22, 57), et l’effet sur la borne est un facteur quinze mille, parce que les deux termes s’améliorent en même temps : $R$ tombe de 74 à 13 parce que les points ne sont plus mesurés depuis une origine lointaine, et $\gamma$ passe de 0,045 à 0,989 parce que la marge est mesurée par rapport à un vecteur de poids qui n’a plus besoin de porter un énorme biais pour atteindre les données.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Convergé en deux époques, après s’être corrigé exactement une fois.

Il y a ici une vraie leçon, et ce n’est pas « pensez à normaliser vos entrées », même si vous devriez le faire. C’est que la garantie qu’un algorithme termine ne vous dit rien sur le fait que vous serez encore là quand il le fera, et que l’écart entre les deux est généralement géométrique. C’est la première apparition d’un motif que vous retrouverez au Chapitre 6 avec l’initialisation, au Chapitre 10 avec les calendriers de taux d’apprentissage, et au Chapitre 13 avec la quantification : les mathématiques disent que la chose est possible, et l’ingénierie décide si elle est pratique. Un cours qui ne vous enseigne que le théorème vous remet un modèle qui s’entraîne pendant trois jours et vous en rend responsable.

Voici maintenant l’échec qui a clos la première ère des réseaux neuronaux, et il tient en quatre lignes.

Oubliez l’usine. Prenez deux entrées qui valent chacune 0 ou 1, et demandez que la réponse soit $+1$ lorsque exactement l’une d’elles vaut 1 :

C’est XOR — le ou exclusif. Avant de continuer, dessinez les quatre points sur papier : trois coins d’un carré unité et le quatrième. Marquez les deux coins diagonaux $(0,1)$ et $(1,0)$ comme acceptés, et $(0,0)$ et $(1,1)$ comme rejetés. Maintenant, tracez une droite avec les deux points acceptés d’un côté et les deux points rejetés de l’autre.

Vous ne pouvez pas. Ce n’est pas que ce soit difficile, ni qu’il faille un algorithme plus malin ; c’est que la droite n’existe pas. Trois lignes d’algèbre montrent pourquoi. Si un perceptron classait correctement les quatre cas, alors la lecture des quatre lignes dans l’ordre donnerait

Additionnez les deux inégalités du milieu : $w_1 + w_2 + 2b \geq 0$, donc $w_1 + w_2 \geq -2b$. La dernière dit $w_1 + w_2 < -b$. Ensemble : $-2b \leq w_1 + w_2 < -b$, ce qui exige $-2b < -b$, ce qui exige $b > 0$. Et la première inégalité dit $b < 0$. Il n’existe pas un tel $b$, donc il n’existe pas de tels poids. Aucun perceptron, avec quelque nombre que ce soit, ne classe XOR.

Exécutez-le quand même, parce que voir un algorithme échouer vaut mieux que de se faire dire qu’il échouera :

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Il ne diverge pas, et il ne s’agite pas près d’une réponse correcte. Il cycle : il parcourt une courte boucle dans l’espace des poids et revient exactement à son point de départ, indéfiniment, en classant correctement deux cas sur quatre — ce que vous obtiendriez en devinant. Cent mille époques et cent époques sont indiscernables, parce que l’algorithme ne fait pas de progrès qu’une exécution plus longue pourrait achever. Comparez cela au tapis, qui semblait bloqué à 200 époques et avançait en réalité péniblement vers une vraie réponse. De l’extérieur, les deux se ressemblent pendant les premières secondes. Les distinguer, sans le théorème, est impossible — ce qui est un argument de plus pour connaître le théorème.

En 1969, Marvin Minsky et Seymour Papert ont publié Perceptrons, une étude mathématique de la taille d’un livre sur ce que ce modèle peut et ne peut pas représenter.² XOR en est le résultat le plus cité, et la citation sert généralement d’accusation : le livre aurait tué la recherche sur les réseaux neuronaux pendant quinze ans par rivalité ou par rancune.

Les mathématiques du livre sont correctes, et elles sont plus intéressantes que l’exemple XOR. Minsky et Papert ne s’intéressaient pas principalement à la question de savoir si un perceptron seul pouvait faire XOR ; ils s’intéressaient à ce qui se passe lorsque des perceptrons reçoivent des champs récepteurs limités — chaque unité ne voyant qu’une partie de l’entrée — et ils ont prouvé que certaines propriétés globales d’une image, comme le fait qu’une figure soit connexe, ne peuvent pas être calculées de cette façon, quel que soit le nombre d’unités utilisées. C’est un résultat réellement profond sur la localité, et il n’a rien à voir avec l’histoire populaire.

L’histoire populaire se trompe aussi sur l’histoire. Minsky et Papert discutent explicitement des perceptrons multicouches et disent que la question de leur puissance est ouverte — ils soupçonnaient qu’étendre la théorie serait « stérile », ce qui est une prédiction, pas une preuve, et elle était fausse. Ce qui manquait en 1969 n’était pas l’idée d’empiler des couches ; c’était un moyen d’entraîner une pile. La règle du perceptron ne peut pas le faire : elle doit savoir à quel point chaque unité se trompe, et pour une unité enfouie au milieu il n’y a pas d’étiquette à laquelle se comparer. Cette faille est restée ouverte jusqu’à ce que backpropagation soit popularisée en 1986,³ et la combler est ce que fait le Chapitre 5.

Le résumé honnête est donc celui-ci. Le livre a prouvé une vraie limite d’un vrai modèle. L’effondrement du financement du domaine dans les années soixante-dix a eu de nombreuses causes, dont l’une était que les promesses faites pour les perceptrons au début des années soixante avaient été extravagantes. Et l’obstacle technique était soluble, mais personne ne disposait encore de l’outil.

Le perceptron a soixante-huit ans et vous venez d’en écrire un. Il vaut la peine d’être précis sur les parties qui se trouvent encore dans la machine que vous aurez terminée à la fin de ce cours, parce que la réponse est : plus que vous ne l’imaginez.

Le perceptron s’est bloqué sur deux choses à la fois, et elles se révèlent être la même chose.

Il ne peut pas représenter XOR, parce qu’une seule droite ne suffit pas. Corriger cela signifie empiler des couches — une première couche qui courbe l’espace, une seconde qui trace la droite dans l’espace courbé. C’est le Chapitre 5.

Mais vous ne pouvez pas entraîner une pile avec la règle du perceptron, parce qu’elle ne connaît que « faux », et une unité au milieu d’un réseau n’a pas d’étiquette propre sur laquelle se tromper. Pour entraîner une pile, vous devez savoir à quel point c’est faux, et dans quelle direction, pour chaque poids — vous avez besoin d’une pente. Et la fonction d’erreur du perceptron, l’escalier, n’en a pas.

Donc avant la pile, il faut une fonction de loss avec une dérivée utilisable. Pas une fonction choisie parce qu’elle est pratique à dériver, non plus : une fonction qui vient de quelque part, qui dit quelque chose de vrai sur les données, et dont le gradient découle de ce sens au lieu d’être rétroconçu pour avoir l’air propre.

C’est le Chapitre 2, et il commence par poser une question à laquelle le perceptron n’a jamais eu à répondre : non pas « cette pièce est-elle bonne ? », mais « quelle est la probabilité de ces mesures, si ceci est la vérité ? »

À lire aussi en parallèle de ce chapitre : l’article original de Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), plus lisible que sa réputation ne le laisse penser ; McCulloch et Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), l’article qui a modélisé pour la première fois un neurone comme un seuil appliqué à une somme pondérée ; la section sur le perceptron du A Course in Machine Learning de Hal Daumé III, qui dérive la même mise à jour avec un accent différent ; et les chapitres 2 et 3 de Mathematics for Machine Learning de Deisenroth, Faisal et Ong pour l’algèbre linéaire, si l’encadré ci-dessus vous a donné envie d’en savoir plus.