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 affine1 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 = (x1,…,xn) 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,x1,..xn). Les ensembles A* et B* sont séparables par l’hyperplan vectoriel H* = (w0,w1,…, wn) si et seulement si A et B sont séparables par l’hyperplan affine intersection des hyperplans H* et (x0 = 1), qui est défini par w0+w1x1+...+wnxn=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 (x0=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 erreur2(W,X) et deux réels emin et emax tels que
pour tout hyperplan W et toute donnée X de {A,B}3
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) > 04
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 un5, 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
( emax2 M(A,B)2 + 2 emin D)/ (emin D)2 é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 W0 unitaire également.
a/
Wi+1.Wi+1 = (Wi – erreur(Wi,X)X).( Wi – erreur(Wi-1,X)X)
= Wi.Wi + erreur(Wi.X)2 X.X -2erreur(Wi.X)Wi.X
d'après la définition le l’erreur erreur(Wi.X)Wi.X ≥ 0
donc Wi+1.Wi+1 ≤ Wi.Wi + erreur(Wi.X)2 X.X ≤ Wi.Wi + emax2 M2
on en déduit Wi.Wi ≤ W0.W0 + i emax2 M2
et, puisque H et W0 unitaires
(Fa) (Wi.H)2 ≤ |Wi| 2 |H| 2 ≤ 1 + i emax2 M2
b/
Wi.H = Wi-1.H – erreur(Wi-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 Wi.H ≥ Wi-1.H + emin D ≥ i emin D + W0.H ≥ i emin D -1
et pour i plus grand que 1/(emin D), en élevant au carré
(Fb) (Wi.H)2 ≥ (i emin D – 1)2
c/
(Fa) et (Fb) fournissent un encadrement de (Wi.H)2
(i emin D – 1)2 ≤ 1 + i emax2 M2 qui se développe puis se simplifie en
(Fc) i ≤ ( emax2 M2 + 2 emin D)/ (emin D)2
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 + M2 + 2 D)/ D2 . 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 Wi avec l’hyperplan H vaut Wi.H/|Wi|, on déduit des inégalités de la preuve une minoration de ce cosinus par (i emin D -1)/ ( 1 + i emax2 M2)1/2 qui dépasserait 1 si l’algorithme ne s’arrêtait pas. Cela signifie Wi tend à devenir parallèle à H, autrement dit le plan (Wi) 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.