Physique statistique des réseaux de neurones et de l’optimisation combinatoire
RESEAUX DE NEURONES
Le système modèle (fig. 1) d’une mémoire associative que nous étudions est constitué d’un nombre N de processeurs que, suivant l’usage, nous appellerons ’neurones’. Chaque neurone i peut prendre deux valeurs 03C3 i=+1 (neurone ’actif) ou 03C3 i=-1 (neurone ’inactif). Le neurone i peut communiquer son état à chacun des autres neurones j par un couplage ’synaptique’ de poids Jji. fig. 1 Système modèle d’un réseau de neurones, constitué de neurones i=1,…,N (ici N=6). Le neurone i peut communiquer son état 03C3 i=±1 au neurone j par un couplage ’synaptique’ Jji (Jij~ji). 10 Les deux régimes du système, l’apprentissage et le rappel, sont séparés l’un de l’autre (c’est-à-dire que les échelles de temps de leurs dynamiques sont supposées différentes). Dans le régime de rappel, la matrice des couplages est figée. L’état du réseau pendant la phase de rappel est donc décrit par le vecteur à N dimensions 03C3 donnant les états de tous les neurones La configuration 03C3= 03C3(t) du réseau évolue aux intervalles de temps discrets t=0,1,…, selon la dynamique suivante: Ceci est une dynamique (parallèle) de Monte Carlo à température zéro, qui se généralise facilement à des températures non-nulles [2]. Pendant l’apprentissage, un nombre p de ’patterns’ 03BE03BC,03BC=1,…,p sont présentés au réseau. Les patterns sont des configurations possibles du système (correspondant à un état donné (actif ou inactif) de chaque neurone): Ce sont ces patterns 03BE03BC que le réseau doit être capable de reconnaître 11 dans la phase de rappel. Par définition le pattern 03BE03BC est mémorisé par le réseau quand il est un point fixe de la dynamique éq. (1.2): mémoire: On dit que la mémoire est en plus associative, si un état initial 03C3 proche de 03BE03BC (dans un sens qui sera précisé par la suite), est ramené vers le pattern 03BE03BC associativité: c’est-à-dire si le pattern 03BE03BC peut être récupéré à partir de données ( 03C3(t=0)) incomplètes. Les paradigmes (1.4) et (1.5) sont essentiellement dus a Hopfield [2]. Evidemment, les définitions de la mémoire peuvent facilement être généralisées pour tenir compte d’un taux d’erreur dans le rappel. Afin de quantifier les possibilités de ces réseaux et de comparer diverses règles d’apprentissage, un cas d’étude extrêmement important est celui des patterns aléatoires. Les patterns 03BE03BC sont dits aléatoires, si leurs composantes sont tirées au hasard le paramètre m est le biais des patterns. L’introduction d’une distribution de probabilité pour les patterns rend possible l’étude des réseaux de 12 neurones dans la limite N~~, la limite thermodynamique. La règle d’apprentissage est choisie afin de mémoriser (c’est-à-dire stabiliser) les patterns 03BE03BC, et afin de les entourer de bassins d’attraction aussi grands que possibles (c’est-à-dire de ramener le plus de configurations vers les patterns 03BE03BC). L’analyse que nous présentons dans ce chapitre s’appuie en grande partie sur la notion de la stabilité. Cette notion, qui sera introduite dans la section suivante (I.2), permet une discussion unifiée de la mémorisation et de l’associativité dans le réseau de Hopfield. Plus encore, la stabilité donne un critère à la fois clair et simple pour construire des algorithmes d’apprentissage avec de très bonnes propriétés associatives. Toujours dans la section I.2, un algorithme de stabilité optimale – le ’minover’ – sera présenté. Nous discuterons les liens de ce nouvel algorithme avec l’algorithme du perceptron (de vingt ans son aîné). La stabilité donne un critère, une fonction de coût, qui peut être attribuée à toute règle d’apprentissage possible. Ceci est l’origine d’une approche due à E. Gardner, qui a introduit des calculs analytiques sur l’espace des règles d’apprentissage. La section I.3 est une introduction à cette approche propre à la physique statistique. Les calculs à la Gardner permettent en particulier de déterminer analytiquement les performances de l’algorithme ’minover’. La section I.4 sera consacrée à l’étude (numérique et analytique) du régime de rappel. Nous tâcherons surtout d’étayer l’hypothèse initiale selon laquelle la stabilité doit être optimisée afin d’optimiser les propriétés associatives du réseau. Dans la section I.5, enfin, nous reviendrons sur le problème de 13 l’apprentissage, mais cette fois-ci dans le cas où les efficacités synaptiques sont contraintes à prendre deux valeurs Jij=±1. Pour ce système, le rôle de la stabilité reste inchangé par rapport aux systèmes à couplages Jij continus. Les analyses sur la phase de rappel dans la section I.4 restent donc valables. En revanche, le calcul de la stabilité optimale est profondément changé. D’une part, le problème de l’algorithme qui cherche un réseau de stabilité optimale (résolu par le ’minover’ dans le cas continu) est à ce jour sans solution véritable : nous utilisons un algorithme d’énumération pour estimer les valeurs de la stabilité optimale dans la limite thermodynamique. D’autre part, le calcul à la Gardner sur l’espace des règles d’apprentissage discrètes se complique nettement par l’existence d’une phase verre de spin. Celle-ci nécessite l’inclusion d’effets dits de brisure de la symétrie des répliques. Néanmoins la double approche numérique et analytique fournit des résultats précis et cohérents.
Règles d’apprentissage
Pour les patterns aléatoires non-biaisés (m=0), Hopfield [2] a proposé un algorithme d’apprentissage selon la règle de Hebb [5]: Il se trouve qu’avec cette règle, pour le cas de patterns aléatoires, on arrive à mémoriser un nombre considérable de patterns p=0.14 N avec un très faible nombre d’erreurs. Depuis la proposition de Hopfield, ce modèle, utilisant des patterns aléatoires, a été étudié en grand détail [6]. Cette étude est facilitée par le fait qu’avec le choix de la règle de Hebb éq. (1.7), la matrice (Jij) des connections synaptiques est symétrique. En conséquence, la dynamique de Monte-Carlo éq. (1.2) peut s’écrire comme une dynamique de relaxation à la température T pour un système décrit par un Hamiltonien; le réseau de neurones devient alors un ’vrai’ système physique. Toujours à propos de ce problème d’apprentissage, un grand nombre d’algorithmes différents ont été proposés [7,8,9,10] afin d’améliorer à la fois le nombre de patterns que le modèle est capable de mémoriser et les propriétés associatives du réseau. Finalement, la connexion profonde du problème d’apprentissage sur le réseau de Hopfield avec l’apprentissage bien connu du perceptron [11] a 15 été révélée. En fait, la condition de stabilité des patterns (voir éqs. (1.2) et (1.4)) s’écrit comme (la notation 03A3 j(~i) indique une sommation uniquement sur l’indice j, excluant le terme j=i). L’équation (1.8) équivaut à Dans la formule (1.9) les patterns 03BE iC sont des paramètres, tandis que les poids synaptiques Jij sont les variables dynamiques de l’apprentissage. Pour chaque neurone i, la condition de stabilité de tous les patterns ne fait intervenir que les connexions Jij, j=1,…,N, c’est-à-dire le vecteur de la ième ligne de la matrice (Jij). Les conditions de stabilité éq.(1.9) sur la matrice (Jij) se découplent donc en N systèmes autonomes (à l’intérieur des parenthèses {}) si les différentes lignes de la matrice (Jij) sont indépendantes (voir l’article [I]). Ainsi, le problème complet éq. (1.9) de l’apprentissage se décompose en N systèmes avec N-1 unités d’entrée et une seule unité de sortie, c’est-à-dire N systèmes du type perceptron : L’éq. (1.10) peut s’écrire comme équation vectorielle entre le vecteur de ligne J = (Ji1,2…,J iN) et les patterns ’auxiliaires’ ~03BC = 03BE iC 03BE 16 Il est important de réaliser que l’éq. (1.11) offre une formulation géométrique de la mémoire équivalente à la définition dynamique initiale (éq .(1.4)) : un vecteur J mémorise (au neurone i) tous les patterns 03BE03BC si et seulement s’il a un recouvrement positif avec les patterns ’auxiliaires’ ~03BC (voir fig. 2). fig.2 L’image géométrique de l’apprentissage (voir éq. (1.11)). Un pattern 03BE03BC est appris par le vecteur J si le recouvrement de J avec le pattern ’auxiliaire’ ~03BC est positif. En termes géométriques l’apprentissage consiste à trouver un vecteur J ayant un recouvrement positif avec tous les vecteurs ~03BC. J1 est un tel vecteur, J2 ne l’est pas. Si elle existe, une telle solution J peut être trouvée par le célèbre algorithme du perceptron [11] : commençant par un vecteur J = J(t=O) = (0,0,…,0) on cherche, à chaque instant du temps d’apprentissage t=0,1,…, un pattern ~03BC qui n’est pas encore appris J(t) · ~03BC < 0 et on l’ajoute à la solution du pas de temps précédent: J(t+1)=J(t)+~03BC. L’apprentissage est terminé (t=M) s’il n’existe plus de patterns avec recouvrement négatif, le 17 problème (1.11) étant alors résolu. Le théorème de convergence du perceptron [11] assure que le temps d’apprentissage avec l’algorithme du perceptron est fini si et seulement si le problème (1.11) a une solution J. (Il existe des méthodes basées sur la programmation linéaire ([12], I) qui permettent de décider en un temps fini (qui croît comme une fonction polynomiale de la taille N du système) si le problème de l’apprentissage n’a aucune solution). En conséquence, l’algorithme du perceptron serait une bonne extension de la règle de Hebb dans le modèle de Hopfield [8], [13] : pour un problème donné, il est possible de déterminer une matrice (Jij) (par N applications de l’algorithme du perceptron) qui, stabilise tous les patterns, à condition qu’il existe au moins une telle solution. Cet algorithme (comme ses variantes) converge en général vers des matrices non-symétriques (Jij~ji). Un signe de sa robustesse est qu’il peut être modifié pour préserver la symétrie de la matrice (Jij) [8] (à condition qu’il existe une matrice symétrique stabilisant tous les patterns). Si les méthodes classiques permettent déjà de donner une réponse algorithmique au problème de la mémorisation, la transcription d’un autre résultat connu depuis les années 60 [14] permet d’établir un résultat d’une grande importance théorique : le nombre maximal de patterns aléatoires et sans biais qui peuvent être mémorisés sans erreurs dans le modèle de Hopfield se comporte dans la limite N~~ comme p~2N. Ce résultat est important en ce qu’il fournit une valeur de la capacité de mémorisation de patterns aléatoires dans le modèle de Hopfield, indépendamment de toute règle d’apprentissage explicite. Si certaines 18 règles ont des performances restant très en deçà de cette limite, les règles élaborées à partir de l’algorithme du perceptron permettent d’atteindre la limite théorique de Cover (car elles convergent à condition qu’il existe une solution). Notons enfin, que la limite de mémorisation de Cover s’applique à la mémorisation des patterns stricto sensu, la limite de mémorisation avec un faible taux d’erreurs n’étant pas connue. Jusqu’ici nous nous sommes préoccupés du problème de la mémorisation (éq. (1.4)) des patterns 03BE03BC, laissant de côté la condition de l’associativité (éq. (1.5)), qui est d’une égale importance. A première vue, ceci semble être un problème beaucoup plus compliqué. La mémorisation (éq. (1.4)) des p patterns 03BE03BC implique (sur chaque neurone) p conditions sur la dynamique à un pas de temps à partir de ces patterns (ceci est le contenu de l’équation (1.8)). L’associativité éq. (1.5), au contraire, correspond à un grand nombre de conditions sur la dynamique à plusieurs pas de temps à partir de toute configuration 03C3 proche d’un des patterns. Nous avons proposé dans ce contexte [15], [I] de considérer des vecteurs J dé norme fixée (comme |Jij ~ 1, j=1,…,N; ou 03A3 jJij2 ~ N) vérifiant les conditions : avec une stabilité 03BA aussi grande que possible (pour des vecteurs J de norme bornée): pour la norme du maximum (|Jij ~ 1, j=1,…,N) on voit facilement [I] que chaque configuration initiale 03C3 qui diffère du pattern 03BE03BC en moins de 03BA~N/2 positions est ramenée vers ce pattern en un pas de 19 temps. Regardons sans restriction de généralité le cas où seuls les s premiers éléments de 03C3 diffèrent de 03BE03BC (03C3 i= – 03BE iC , i=1,…,m ; 03C3 i= 03BE iC , i=m+1,…,N). La condition de convergence en un pas de temps est (voir éqs. (1.8), (1.9)) (à cause de la condition |Jij ~1). Pour assurer la convergence on a donc la condition m < 03BA~N/2. A partir d’un tel argument on est conduit à rechercher des algorithmes d’apprentissage optimisant la stabilité, pour l’une ou l’autre définition de la norme du vecteur J. L’algorithme ’minover’ que nous proposons dans [I] est capable de déterminer la solution Jopt avec stabilité optimale 03BA opt parmi tous les vecteur J de norme euclidienne fixée 03A3 jJij2= N , c’est-à-dire de trouver un vecteur maximisant une stabilité renormalisée où |J | est la norme euclidienne de J. Cet algorithme est d’une certaine importance, car il se trouve que la stabilité 039403BC’ = J·~03BC / |J| correspondant à la norme euclidienne est le paramètre pertinent pour la dynamique du réseau proche d’un pattern 03BE03BC (voir la section 1.4) L’algorithme ’minover’ converge vers la solution optimale (c’est-à-dire un vecteur de stabilité minimale optimale) pour tout ensemble de 20 fig. 3 L’algorithme ’minover’ en action. A chaque itération t, on ajoute au vecteur J(t) le pattern auxiliaire ~03BC ayant un recouvrement minimal avec J(t). 21 patterns pour lequel une solution avec stabilité positive existe. Il est relié à l’algorithme du perceptron en ce qu’il est de nature itératif (voir fig. 3). A chaque instant du temps d’apprentissage le vecteur J(t) est mis à jour suivant J(t+1)=J(t)+c·~03BC(t), où ~03BC(t) est le pattern ayant un recouvrement minimal avec la solution J(t) (dans le perceptron ~03BC(t) était un pattern quelconque ayant un recouvrement inférieur à zéro). Le critère d’arrêt est aussi différent de celui du perceptron (voir I). Comme nous le verrons plus loin, l’algorithme ’minover’ donne une réponse satisfaisante au problème d’une règle d’apprentissage créant des bassins d’attraction les plus grands possibles.
Remerciements |
