|
|
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 19431 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 x1 et x2 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 w1x1 +w2x2 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 w1x1 +w2x2 > s alors y =1
si w1x1 +w2x2 ≤ 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 2x1 +3x2 = 1 et 4x1 +6x2 =2 représentent la même droite).
La loi d’apprentissage de Hebb 2
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 rudimentaire3. 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 stable4 (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 wi son coefficient synaptique
Si, pour un exemple de A, xi = 1 et y =0 alors augmenter wi
Si, pour pour un exemple de B, xi = 1 et y =1 alors diminuer wi
Sinon, pour l’exemple considéré, ne pas changer wi
Pour le cas historique du Perceptron où les xi 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 15, 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, w1x1 +w2x2 > s est transformé en w0x0 + w1x1 +w2x2 >0 avec x0=1 et w0 = -s.
L’exemple suivant illustre avec ces notations l’algorithme du Perceptron pour x1 et x2 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).
.png)
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 w0x0 + w1x1 +w2x2 = 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’IM6 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 pas7 à 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.