Le théorème de convergence du Perceptron

 

Cours de Stéphane Mallat au Collège de France

leçon « Les origines : la cybernétique et le perceptron » (capture d'écran)

Résumé : Cet article démontre une version du théorème qui élucide complètement les capacités d’apprentissage d’un neurone formel muni de la loi de Hebb. Seul article technique de ce blog, il vise à démystifier les IM en mettant à plat par les mathématiques le cas historique du Perceptron qui en son temps fit couler beaucoup d’encre et nourrit beaucoup de fantasmes, comme c’est malheureusement encore le cas actuellement pour ses successeurs.

Tous les étudiants en informatique connaissent sous une forme ou sous une autre ce théorème, qui est un « bien commun » qu’il est difficile d’attribuer à un auteur particulier. La compréhension de la présente version ne requière que des connaissances de bases sur les espaces euclidiens.

Notations

Soit un espace vectoriel euclidien de dimension n. H.X désigne le produit scalaire des deux vecteurs H et X, et |X| la norme de X.

Un hyperplan H (c’est-à-dire un sous-espace de dimension n-1) peut être défini comme l’ensemble des vecteurs orthogonaux à un vecteur H donné, c’est-à-dire comme l’ensemble des vecteurs X tels que H.X = 0. On peut toujours supposer que H est unitaire (i.e. |H| = 1), ce que nous ferons dans la suite. Selon le contexte, H dénote un vecteur ou l’hyperplan orthogonal qu’il définit.

H partage l’espace en deux : d’un côté les vecteurs X tels que H.X > 0 et de l’autre ceux tels que H.X < 0.

Séparabilité

Deux ensembles A et B sont dits linéairement séparables si il existe un hyperplan H tel que H.X > 0 pour tout X d'un de ces ensembles, et H.X < 0 pour tout X de l'autre ensemble. La séparabilité est ici définie au sens strict.

Si H sépare A et B, comme A et B sont finis, la plus petite valeur absolue D des H.X/|H| pour X dans A ou B est strictement positive. On dit alors que A et B sont D-séparables. D représente la distance minimale des éléments de A et B à l’hyperplan H.

Versions affine¹ et vectorielle du problème de séparabilité

 La séparabilité est mathématiquement plus commode à traiter dans le cadre vectoriel, mais on s’en forge une intuition à partir de la représentation de points dans l’espace usuel, celui du collégien considéré au chapitre précédent. Il est donc souhaitable de faire le lien entre les deux formalisations.

Le problème général de séparation linéaire est de séparer par un hyper-plan deux ensembles finis A et B de données à n paramètres réels. Une donnée X = (x₁,…,x_n) peut être considérée comme un vecteur d’un espace vectoriel ou comme un point d’un espace affine. Dans ce dernier cas on se ramène à un problème vectoriel en dimension n+1 comme suit :

A toute donnée X on associe la donnée vectorielle X*= (1,x₁,..x_n). Les ensembles A* et B* sont séparables par l’hyperplan vectoriel H* = (w₀,w₁,…, w_n) si et seulement si A et B sont séparables par l’hyperplan affine intersection des hyperplans H* et (x₀ = 1), qui est défini par w₀+w₁x₁+...+w_nx_n=0.

C’est ce que nous faisons dans l’article précédent : partant des points A1 (2,-1), A2 (-2,3) et B (0,0), nous considérons les vecteurs A1* (1,2,-1), A2* (1,-2,3) et B* (1,0,0) ; nous obtenons le plan vectoriel séparateur (-1,3,4) dont l’intersection avec le plan affine (x₀=1) donne la droite affine D12 ( -1 +3x + 4y= 0).

Fonction d’erreur du Perceptron

Soit deux ensembles finis A et B.

On se donne une fonction erreur²(W,X) et deux réels emin et emax tels que

pour tout hyperplan W et toute donnée X de {A,B}³

0 < emin ≤ |erreur(W,X)| ≤ emax

pour tout hyperplan W et tout point X

si X appartient à A et W.X > 0 ou si X appartient à B et W.X <0

alors erreur (W,X) =0

si X appartient à A et W.X <= 0 alors erreur (W,X) < 0

si X appartient à B et W.X >= 0 alors erreur (W,X) > 0⁴

Bon tirage des échantillons

Lors de l’apprentissage on peut tirer aléatoirement les données d’apprentissage {A, B}, à un détail près. A tout moment il faut être certain que chaque élément sera à nouveau tiré, sinon on ne peut pas tester la correction de l’algorithme sur cet échantillon, nous dirons alors que c’est un bon tirage. Un tirage aléatoire à pile ou face n’est pas un bon tirage car il se peut qu’on ne tire jamais pile, même si la probabilité est nulle.

Un bon tirage pratique, où de plus tous les éléments sont tirées à peu près autant de fois, est de faire un tirage aléatoire sans remise parmi toutes les données, et de recommencer quand on les a toutes tirées.

Algorithme d’apprentissage du Perceptron

Initialement : On se donne un critère d’arrêt On se donne un hyperplan W0 quelconque Itération : On tire par un bon tirage X dans {A,B} ; Si erreur(Wi,X) différente de 0 alors Wi+1 = Wi – erreur(Wi,X)X Arrêt : Quand le critère d’arrêt est satisfait.

Correction et complétude d’un algorithme

On dit qu’un algorithme est correct si, pour toute donnée, si il fournit une réponse elle est correcte. Un algorithme est complet si, pour toute donnée, il fournit un réponse.

Dans le cas de séparation linéaire de deux ensembles finis A et B, nous cherchons un algorithme correct et complet, qui fournit un hyperplan de séparation si il en existe un⁵, et indique qu’il n’y en a pas sinon.

Correction de l’algorithme d’apprentissage du Perceptron

Si on prend pour critère d’arrêt que pour le plan Wi obtenu l’erreur est nulle pour tout élément de {A, B}, alors Wi sépare linéairement A et B

La preuve découle directement de la définition de l’erreur. Toute la difficulté est de montrer la complétude. Nous montrons que si A et B sont D-séparables, l’algorithme trouve une solution en un temps que l’on peut majorer en fonction de A, B et D. Par conséquent, si un plan séparateur n’est pas trouvé à l’issue de ce temps, c’est qu’il n’y en a pas.

Remarque : Nous avons vu que si A et B sont séparables, il existe D (que l’on ne connaît pas) tel qu’ils soient D-séparables. Comme ils sont D-séparables, le résultat précédent fait que l’algorithme trouvera un plan séparateur sans connaître D, mais on ne peut pas borner le temps nécessaire.

Théorème de convergence du Perceptron : complétude

Si A et B sont D séparables,

L’algorithme d’apprentissage du Perceptron fournit un hyperplan séparateur en moins de

( emax² M(A,B)² + 2 emin D)/ (emin D)² étapes

(une étape est un changement d’hyperplan)

Preuve :

On abrège M(A,B) en M.

Par hypothèse il existe un hyperplan H D-séparant A et B. Nous prenons H unitaire et partons de W₀ unitaire également.

a/

W_i+1.W_i+1 = (W_i – erreur(W_i,X)X).( W_i – erreur(W_i-1,X)X)

= W_i.W_i + erreur(W_i.X)² X.X -2erreur(W_i.X)W_i.X

d'après la définition le l’erreur erreur(W_i.X)W_i.X ≥ 0

donc W_i+1.W_i+1 ≤ W_i.W_i + erreur(W_i.X)² X.X ≤ W_i.W_i + emax² M²

on en déduit W_i.W_i ≤ W₀.W₀ + i emax² M²

et, puisque H et W₀ unitaires

(Fa)              (W_i.H)² ≤ |W_i| ² |H| ² ≤ 1 + i emax² M²

b/

W_i.H = W_i-1.H – erreur(W_i-1.X) H.X. On remarque comme dans a/ que par définition, pour l'hyperplan H de l'hypothèse, l' erreur est du signe opposé à H.X,

donc W_i.H ≥ W_i-1.H + emin D ≥ i emin D + W₀.H ≥ i emin D -1

et pour i plus grand que 1/(emin D), en élevant au carré

(Fb)           (W_i.H)² ≥ (i emin D – 1)²

c/

(Fa) et (Fb) fournissent un encadrement de (W_i.H)²

(i emin D – 1)² ≤ 1 + i emax² M² qui se développe puis se simplifie en

(Fc)         i ≤ ( emax² M² + 2 emin D)/ (emin D)²

qui est la majoration annoncée dans l’énoncé du théorème.

Remarques

1/ Dans le cas historique du Perceptron, emin et emax valent 1. Si T est le nombre d’éléments de A et B, on en déduit que le nombre total de données d’apprentissage à tester est majoré par T (1 + M² + 2 D)/ D² . Cette majoration est linéaire par rapport au nombre de données d’apprentissage, ce qui rend l’algorithme tout à fait praticable.

2/ Interprétation géométrique : sachant que le cosinus de l’angle que fait le vecteur W_i avec l’hyperplan H vaut W_i.H/|W_i|, on déduit des inégalités de la preuve une minoration de ce cosinus par (i emin D -1)/ ( 1 + i emax² M²)^1/2 qui dépasserait 1 si l’algorithme ne s’arrêtait pas. Cela signifie W_i tend à devenir parallèle à H, autrement dit le plan (W_i) devient proche de (H), ce qui est intuitif. Minorer par une borne qui tend vers 1 ne veut pas dire que le cosinus se rapproche de 1 à chaque pas, on ici rejoint une remarque à propos de l’observation de l’exemple dans l’article précédent.

3/ La problématique de la séparation (ou classification) linéaire continue de faire l’objet de recherches, du fait de la taille immense des données traitées (des millions voire des milliards de données avec des millions de paramètres). Il s’agit notamment d’accélérer l’algorithme en choisissant bien l’ordre des exemples présentés à l’apprentissage, ou en tenant compte que dans la pratique chaque donnée a souvent une majorité de paramètres nuls. On cherche également à rendre la séparation robuste en cherchant un plan le plus éloigné possible des échantillons. On traite également l’aspect statistique avec des données en nombre potentiellement infini, et on étudie les cas où la séparation n’est pas stricte.

Conclusion

Le Perceptron historique décrit dans un article précédent disposait pour entrée d’une image de 20 lignes de 20 pixels noirs et blancs et de 8 sorties binaires également (lampe allumée ou éteinte). Il était difficile de s’y retrouver dans le fouillis des câbles et des connexions. Rosenblatt avait en tête de mimer une rétine, et c’est ce qui guidait l’introduction d’un câblage intermédiaire. Il a fallu une analyse détaillée des chercheurs pour réaliser que cet intermédiaire n’ajoutait rien à la capacité du Perceptron, et que celui-ci constituait un neurone formel particulier par lampe de sortie, tel que nous les avons décrits.

Il s’agissait donc de 8 neurones formels fonctionnant en parallèle. Ceci permet de coder sur 8 bits les sorties, donc d’obtenir une classification en 256 réponses différentes. Illustrons l’idée avec deux neurones et quatre ensembles de données A, B, C, D à classer. Si {A,B} et {C, D} sont séparables linéairement (avec pour réponses respectives 0 et 1), et de même pour {A,C} et {B, D} (avec pour réponses respectives 0 et 1). Alors pour tout élément de A la réponse sera (0,0), pour B elle sera (0,1), pour C elle sera (1,0) et D elle sera (1,1).

Le Perceptron historique était en réalité loin d’avoir la capacité de 8 neurones formels généraux, car les synapses étaient peu nombreux et parfois partagés entre deux neurones. D’une part des questions matérielles de câblage et de fer à souder limitaient le nombre, et d’autre part Rosenblatt pensait obtenir de meilleurs résultats en s’inspirant de l’anatomie d’une rétine.

Le Perceptron est la première expérience à mettre en débat scientifique la capacité des réseaux de neurones, au coeur de la problématique des réseaux de neurones profonds actuels, notamment à travers l’approche statistique et l’importance de la structuration des connexions. Ce qui manquait par dessus tout à Rosenblatt, et qui a été la grande révélation du deep learning, est que les techniques neuronales ne fonctionnent bien qu’à très large échelle et sur de gigantesques masses de données d’apprentissage.

Le petit neurone et la règle d'écolier

 

Neurone de souris imagé avec un microscope à feuille de lumière © Angela GETZ / Mathieu DUCROS / Daniel CHOQUET / IINS / BIC / CNRS Photothèque

Règle pleine Inox non graduée 500mm – Facom © photo Promeca

Résumé : Nous présentons dans un cas élémentaire ce qu’est un classifieur linéaire et détaillons son analogie avec un neurone. Cette analogie alimente la thèse que l’intelligence est une manifestation de lois universelles de l’information, que ces lois ont conditionné l’évolution des espèces sans que l’intelligence soit pour autant l’apanage du vivant.

Tout ce qui figure dans cet article est bien connu de tout informaticien. Il semble néanmoins nécessaire que tout citoyen puisse s’approprier les notions avec des mathématiques de niveau collège, afin de dissiper des interprétations irrationnelles et ainsi de mieux éclairer le débat public sur la Data et l’IM.

Problématique : la classification linéaire

La classification linéaire consiste à séparer deux ensembles dans un plan par une droite, ou dans l’espace usuel par un plan, ou plus généralement par un hyperplan dans un espace vectoriel de dimension quelconque (ce qui sera traité dans le prochain article). La classification est dite supervisée si un dispositif indique pour chaque exemple d’apprentissage si la réponse donnée par l’apprenant est exacte ou fausse. Il existe d’autres méthodes d’apprentissage qui sont non supervisées, comme le clustering. Dans ce cas, l’algorithme d’apprentissage doit classer lui-même les données par paquets (cluster signifie grappe) en fonction de critères de « ressemblance » (proximité, caractéristiques). Et il existe des classifieurs non linéaires, qui séparent par des courbes. En outre la classification considérée ici ne sépare les échantillons que dans deux classes (les deux demi-espaces séparés par l’hyperplan) ; toutefois en en combinant un grand nombre on parvient à faire des classifications complexes, c’est l’idée de base de l’apprentissage profond.

La notion d’apprentissage supervisé est connue des pédagogues et psychologues depuis longtemps.

Pour apprendre à un enfant à reconnaître les chiffres et les lettres, on lui présente au fil du temps de nombreux exemples d’écritures de chacun d’eux, en les répétant de manière espacée autant de fois qu’il le faut, en l’interrogeant et en lui indiquant chaque fois si sa réponse est bonne ou non. Il s’agit là d’un apprentissage supervisé par le maître ou par les parents. A force de répétitions, l’enfant sait reconnaître les signes. Evidemment, cela ne l’empêchera pas toute sa vie de prendre un 0 mal bouclé pour un 9. Il s’agit de réussir l’apprentissage sur en ensemble d’exemples statistiquement représentatifs de l’écriture de chaque chiffre ou lettre. C’est pourquoi on parle d’apprentissage statistique. Toutefois ici nous ne nous intéressons qu’à la réussite de l’apprentissage sur des ensembles donnés (et finis) d’exemples et n’évoquons pas ces aspects statistiques.

Le protocole est le même pour une machine dotée de capacités d’apprentissage supervisé. Pour l’exemple historique du Perceptron, rappelons qu’une donnée est un ensemble de lampes allumées sur un tableau de 20 lignes de 20 ampoules, c’est-à-dire qu’une donnée possède 400 paramètres qui sont les valeurs des pixels (allumé ou éteint).

Actuellement les données manipulées peuvent avoir des milliards de paramètres et se compter elles mêmes par milliards. La problématique des classifieurs est née en même temps que les machines capables de traiter des masses de données, car auparavant on était très limité dans ce que l’on pouvait faire à la main !

Le neurone

Le web fourmille d’introductions aux neurones biologiques tout comme aux neurones formels. Aussi nos présentations seront-elles minimalistes. Pour la simplicité, nous considérons ici des neurones à deux synapses , alors que les neurones biologiques en ont des centaines et les neurones formels des millions.

Le modèle décrit par Pitts et McCulloch en 1943¹ demeure une approximation valide de l’anatomie et de la physiologie d’un neurone cortical, bien que les phénomènes électrochimiques qui régulent les transmissions d’information au niveau des synapses s’avèrent fort complexes.

Considérons le neurone en noir sur le schéma, relié en entrée à deux neurones (en gris à gauche) par ses deux synapses (points noirs) qui reçoivent les impulsions x₁ et x₂ transmises par les axones des deux neurones de gauche (les axones sont représentés par des fourches). Chaque synapse possède une valeur w, appelée coefficient synaptique, qui peut varier en cours d’apprentissage, tout comme le seuil s. Une synapse est inhibitrice si son coefficient est bas, excitatrice si il est élevé. Dans ce modèle simple, dit binaire, les valeurs de x et y sont 0 (pas d’impulsion) ou 1 (impulsion). Le noyau est représenté par le cercle noir. Si w₁x₁ +w₂x₂ dépasse le seuil s, le neurone envoie une impulsion par son axone aux neurones en gris à droite, ce que l’on note y=1 (wx désigne le produit des deux valeurs w et x). Si le seuil n’est pas dépassé, le neurone n’envoie pas d’impulsion, ce que l’on note y=0.

Ceci s’écrit

si w₁x₁ +w₂x₂ > s alors y =1

si w₁x₁ +w₂x₂ ≤ s alors y = 0

La règle d’écolier

Imaginons nous en maternelle. Traçons quelques points rouges et quelques points bleus sur une feuille. Donnons la feuille, une règle et un crayon à un enfant et demandons lui de tracer une droite séparant les points bleus et les points rouges. L’enfant, en phase d’apprentissage psycho moteur, va tâtonner pour placer sa règle. L’oeil lui indique si la position convient ou non. Il va finir par tracer un trait d’autant plus vite que l’écart est grand entre les bleus et les rouges. Si la séparation n’est pas possible, l’enfant risque de s’énerver ou d’être désorienté.

Passons au collège. Tout le monde se souvient de « y = ax + b », équation d’une droite que l’on s’appliquait à tracer la règle.

La droite partage le plan en deux parties : les points au dessus et les points au dessous, comme la règle qui l’a tracée sépare la feuille en deux. Il s’agit d’un séparateur linéaire, linéaire précisant que la séparation du plan en deux parties se fait par une ligne droite.

Autrement dit

(D) Soit la droite d’équation y = ax + b 

Pour tout point de coordonnées (x,y)

Si y > ax + b alors le point (x,y) est au dessus de la droite

Si y < ax + b alors le point (x,y) est au dessous de la droite

(figure de gauche sur le schéma)

A gauche: La droite y = ax+b tracée à la règle par le collégien sépare le plan en deux.

A droite: Si l’on étend les valeurs de x1 et x2 à des nombres quelconques, le neurone de coefficients synaptiques w1 et w2 et de seuil s sépare en deux le plan : il envoie une impulsion seulement pour les entrées représentées par les points au dessus la droite.

A l’école, on a l’habitude de noter x l’abscisse, représentée horizontalement, et y l’ordonnée, représentée verticalement. La notation ainsi adoptée est plus simple que celle à droite, où sont utilisés des indices, mais elle ne se généralise pas aux grandes dimensions. La notation à droite est préférée des mathématiciens car dans la pratique, on considère des espaces de représentation de dimensions se chiffrant en millions. En outre, la représentation scolaire a le défaut de ne pas convenir pour le cas particulier d’une droite verticale, qu’il faut écrire x= c. En contrepartie, dans la notation mathématique, l’écriture est définie à une constante multiplicative près, mais on s’en accommode très bien (par exemple 2x₁ +3x₂ = 1 et 4x₁ +6x₂ =2 représentent la même droite).

La loi d’apprentissage de Hebb ²

La loi de Hebb porte sur l’apprentissage d’un neurone par variation de ses coefficients synaptiques. Elle stipule que si deux neurones partageant une synapse (en sortie de l’un et en entrée de l’autre) produisent conjointement une décharge, le coefficient synaptique est renforcé (excitation). Très vite les chercheurs on ajouté une règle complémentaire, non explicite chez Hebb : si le premier neurone produit une décharge vers le second sans que celui-ci en produise une, le coefficient synaptique qui les lie est affaibli (inhibition). Il est très difficile de vérifier cette loi expérimentalement du fait que dans un système nerveux un neurone est connecté à une foultitude d’autres et noyé dans des réseaux complexes. Cette loi a néanmoins été confirmée sur des espèces possédant un système nerveux rudimentaire³. L’application de la loi de Hebb revient à ajuster les coefficients synaptiques au fil des données d’apprentissage, afin d’obtenir à la longue des réponses correctes (autrement dit, on vise à ce que la loi soit vérifiée pour toute situation d’apprentissage réussi, qui est alors une situation stable⁴ (les coefficients ne changent plus).

Si le but de l’apprentissage est que y=1 pour tout exemple d’un ensemble A et que y=0 pour tout exemple d’un ensemble B, ceci revient à poser, pour tout synapse i du neurone, en notant w_i son coefficient synaptique

Si, pour un exemple de A, x_i = 1 et y =0 alors augmenter w_i

Si, pour pour un exemple de B, x_i = 1 et y =1 alors diminuer w_i

Sinon, pour l’exemple considéré, ne pas changer w_i

Pour le cas historique du Perceptron où les x_i valent 0 ou 1, et où les coefficients synaptiques évolue de ± 1, ceci est réalisé par

algorithme du Perceptron Si, pour un exemple de A, y =0 alors augmenter wi de xi Si, pour pour un exemple de B, y =1 alors diminuer wi de xi

Les exemples sont présentés dans un ordre quelconque et représentés ultérieurement tant que A et B ne sont pas séparés.

Le théorème de convergence permet de calculer le nombre de présentations d’exemples à partir duquel si A et B ne sont pas séparés, c’est qu’ils ne sont pas séparables (voir l’article suivant).

Il est mathématiquement commode de considérer le seuil comme un coefficient synaptique particulier qui évolue selon la même loi que les autres, en lui attribuant une excitation constante valant 1⁵, ce qui revient à ajouter une coordonnée de valeur fixe 1 à chaque donnée (en général on la place en premier). Ainsi, dans le cas de 2 synapses, w₁x₁ +w₂x₂ > s est transformé en w₀x₀ + w₁x₁ +w₂x₂ >0 avec x₀=1 et w₀ = -s.

L’exemple suivant illustre avec ces notations l’algorithme du Perceptron pour x₁ et x₂ prenant des valeurs réelles. Il consiste à faire apprendre à un neurone à deux entrées à séparer par une droite deux ensembles de points du plan qui sont les exemples d’apprentissage.

On cherche à séparer l’ensemble A constitué de deux points A1 (2,-1) et A2 (2,3) de l’ensemble B contenant le seul point B (0,0), avec A au dessus de la droite (réponse y = 1) et B au dessous (réponse y = 0). Avec les conventions ci-dessus pour le seuil, les coordonnées des trois points deviennent A1* (1,2,-1), A2* (1,-2,3) et B* (1,0,0).

Figure : On choisit de partir de la droite D0 (1,1,1), c’est-à-dire d’équation 1 + x + y = 0 (en pointillés bleus) et on aboutit à la droite D12 (-1,3,4) c’est-à-dire d’équation -1 + 3x + 4y = 0 (en rouge). Figure réalisée avec GeoGebra.

Pour A1 on obtient w₀x₀ + w₁x₁ +w₂x₂ = 2 >0, la réponse est correcte et les coefficients ne sont pas modifiés.

Pour B l’expression vaut 1 donc la réponse y vaut 1 et est incorrecte, la loi de Hebb donne pour nouveau coefficients (0,1,1).

En écrivant la liste des exemples présentés à l’apprentissage et en précisant la nouvelle valeur des coefficients après chaque réponse incorrecte, en partant de (1,1,1) représenté par D0 sur la figure, on obtient

A1* ; B* (0,1,1) ; A2*  ; B* (-1,1,1) ; A2* (0,-1,4) ; B* (-1,-1,4) ; A1* (0,1,3) ; B* (-1,1,3) ; A2* ; B*; A1* (0,3,2) ; B* (-1,3,2) ; A2* (0,1,5) : B* (-1,1,5) ; A1* (0,3,4) ; B* (-1,3,4) ; A2* ; B* ; A1*

qui se lit « réponse correcte à A1*, pas de changement ; réponse erronée à B*, on obtient la droite D1 (0,1,1) c’est-à-dire x+y = 0 » et ainsi de suite. Les 11 valeurs intermédiaires sont représentées par les droites D1 à D11 en pointillés gris.

L’apprentissage est réussi et s’arrête puisque la réponse est correcte pour chaque exemple. Le résultat obtenu (-1,3,4)  représente la droite D12 -1 +3x + 4y= 0 soit encore y= - 0.75 x + 0.25 (en rouge sur la figure).

Un exemple simple de non séparabilité linéaire

Considérons les quatre sommets S, T, U et V d’un carré, où S et U d’une part et T et V d’autre part sont opposés. Rien de plus évident que de constater que les deux ensembles A = {S, U} et B = {T, V} ne sont pas séparables par une droite. Ce simple constat contribua à l’hiver de l’IM⁶ connexionniste, celle des réseaux de neurones formels. Cela semble difficile à croire à la lecture de cet article, mais il a fallu une vingtaine d’années pour sortir par les mathématiques des passions, des confusions et des polémiques suscitées par le Perceptron. A cet époque les capacités du Perceptron n ‘étaient pas formalisées et étaient loin d’être claires. Voir l’article d’août 2022 de ce blog, « L’affaire du Perceptron ».

L’exemple que nous avons donné sous forme de sommets d’un carré est historiquement connu sous le nom de non séparabilité du XOR. Le XOR, abréviation anglaise du OU EXCLUSIF, est la fonction logique de deux arguments qui vaut VRAI si un seul de ses arguments vaut VRAI, et qui vaut FAUX si l’un des arguments vaut VRAI et l’autre FAUX. Il est facile de passer de l’une à l’autre formulation.

Généralisation : le théorème de convergence du Perceptron

Dans l’exemple de cet article, les ensembles A et B étaient séparables par une droite et l’algorithme d’apprentissage a permis d’en trouver une, sans que nous ayons ici démontré pourquoi.

L’observation sur la figure des positions successives des droites D0 à D12 est déroutante, malgré la grande simplicité de l’exemple. Leur évolution évoque plus les mouvements erratiques d’une mouche autour d’un pot de confiture que le fait de se rapprocher d’une solution, puisque les droites changent de directions, tantôt se rapprochent tantôt s’éloignent de la position finale. En un mot, le comportement semble incompréhensible. Et pourtant, les mathématiques centenaires de l’algèbre linéaire élucident complètement le sujet par le théorème du Perceptron.

Si A et B ne sont pas séparables, l’algorithme risque de tourner indéfiniment à la recherche d’une droite séparatrice alors qu’il n’en existe pas. Il se pose alors la question de savoir quand arrêter, et avec quelle conclusion. Le théorème de convergence du Perceptron résout là aussi complètement cette question en permettant de calculer, à partir des ensembles A et B d’exemples, un maximum de pas⁷ à effectuer, à l’issue desquels si l’algorithme n’a pas trouvé de séparateur c’est qu’il n’y en a pas.

Qui plus est le théorème est établi pour des conditions tout à fait générales : les données peuvent être prises dans un espace de dimension quelconque (ici c’était 2), avec des coordonnées de valeur réelle quelconques (ici c’était -1 ou +1) et avec des amplitude de renforcement ou d’affaiblissement des coefficients synaptiques de valeur quelconque (ici c’était 1). Cette dernière généralisation renforce la pertinence de la loi de Hebb, qui est qualitative et ne dit rien de cette amplitude des termes correctifs des coefficients synaptiques.

Ce théorème sera l’objet du prochain article, son élaboration collective prit plusieurs années et mit fin aux controverses liées au Perceptron.

_______________________

1McCulloch, W. S., Pitts, W., A Logical Calculus of the Ideas Immanent in Nervous Activity, Bulletin of Mathematical Biophysics, vol. 5, pp. 115-133, 1943

2The organization of behavior; a neuropsychological theory, Hebb, D. O. (Donald Olding), New York, Wiley, 1949. Si le nom de Hebb est resté attaché à l’énoncé de cette loi, comme souvent en sciences il ne fut pas le seul parmi les psychologues à en émettre l’idée, et certains contestent cette paternité.

3Eric Kandel, prix Nobel de médecine 2000 et ses collaborateurs ont mis en évidence l’implication du mécanisme de renforcement de Hebb dans les synapses du gastropode marin Aplysia californica, plus connu sous le nom de lièvre des mers.

4La notion de stabilité est fondamentale dans tous les modèles physiques et biologiques.

5Cela évite également le cas particulier où toutes les coordonnées d’une donnée sont nulles.

6Au chapitre précédent, nous avons convenu d’utiliser le terme d’intelligence machine pour désigner l’IA.

7Un pas est l’application de l’algorithme sur un exemple de A ou de B.