Carte auto adaptative

Carte auto adaptative ou auto organisatrice est une classe de réseau de neurones artificiels fondée sur des méthodes d'apprentissage non-supervisées.
On la désigne souvent par le terme anglais self organizing map (SOM), on encore carte de Teuvo Kohonen (en) du nom du statisticien ayant développé le concept en 1984.

Elles sont utilisées pour cartographier un espace réel, c'est-à-dire pour étudier la répartition de données dans un espace à grande dimension. En pratique, cette cartographie peut servir à réaliser des tâches de discrétisation, quantification vectorielle ou classification (voir un exemple sur le site [1] pour la discrétisation de l'espace de travail d'un robot).

Idée de base

Ces structures intelligentes de représentation de données sont inspirées, comme beaucoup d’autres créations de l’intelligence artificielle, par la biologie ;
Il s'agit de reproduire le principe neuronal du cerveau des vertébrés : des stimuli de même nature excitent une région du cerveau bien particulière. Les neurones sont organisés dans le cortex de façon à interpréter tous les types de stimuli imaginables. De la même manière, la carte auto adaptative se déploie de façon à représenter un ensemble des données, et chaque neurone se spécialise pour représenter un groupe bien particulier des données selon les points communs qui les rassemblent. Elle permet une visualisation en dimension multiple de données croisées.

Techniquement, la carte réalise une quantification vectorielle de l'espace de données. Cela signifie discrétiser l'espace ; c'est-à-dire le diviser en zones, et assigner à chaque zone un point significatif dit vecteur référent

Architecture des cartes auto-organisatrices. L'espace d'entrée V est divisé en plusieurs zones. w_r représente un vecteur référent associé à une petite zone de l'espace $V_{r}^{M}$ et r(2,3) représente son neurone associé dans la grille A. Chaque zone peut être adressée facilement par les index des neurones dans la grille.

Architecture

D'un point de vue architectural, les « cartes auto-organisatrices de Kohonen » sont constituées d'une grille (le plus souvent uni- ou bidimensionnelle). Dans chaque nœud de la grille se trouve un « neurone ». Chaque neurone est lié à un vecteur référent, responsable d'une zone dans l'espace des données (appelé encore espace d'entrée).

Dans une carte auto-organisatrice, les vecteurs référents fournissent une représentation discrète de l'espace d'entrée. Ils sont positionnés de telle façon qu'ils conservent la forme topologique de l'espace d'entrée. En gardant les relations de voisinage dans la grille, ils permettent une indexation facile (via les coordonnées dans la grille).
Ceci s'avère utile dans divers domaines, comme la classification de textures, l'interpolation entre des données, la visualisation des données multidimensionnelles.

Soit A la grille neuronale rectangulaire d'une carte auto-organisatrice. Une carte de neurones assigne à chaque vecteur d'entrée $v\in V$ un neurone $r\in A$ désigné par son vecteur de position $\vec{r}$, tel que le vecteur référent w_r est le plus proche de v.

Mathématiquement, on exprime cette association par une fonction:

$\phi _{w}:V\rightarrow A$

$r = \phi _{w}(v)= \arg \min_{r\in A} \left\|v - w_{r} \right\|.$

Cette fonction permet de définir les applications de la carte.

• quantificateur vectoriel: on approxime chaque point dans l'espace d'entrée par le vecteur référent le plus proche par

$w_{r}=\phi _{w}^{-1} (\phi _{w}(v))$

• classificateur en utilisant la fonction r = ϕ_w(v)

on assigne à chaque neurone de la grille une étiquette correspondante à une classe; tous les points de l'espace d'entrée qui se projettent sur un même neurone appartiennent à la même classe. Une même classe peut être associée à plusieurs neurones.

Algorithme d'apprentissage

Principe

Après une initialisation aléatoire des valeurs de chaque neurones on soumet une à une les données à la carte auto adaptative. Selon les valeurs des neurones, il y en a un qui répondra le mieux au stimulus. Celui dont la valeur sera la plus proche de la donnée présentée. Alors ce neurone sera gratifié d'un changement de valeur pour qu'il réponde encore mieux à un autre stimulus de même nature que le précédent. Par là même, on gratifie aussi un peu aussi les neurones voisins du gagnant avec un facteur multiplicatif du gain inférieur à un. Ainsi, c'est toute la région de la carte autour du neurone gagnant qui se spécialise. En fin d'algorithme, lorsque les neurones ne bougent plus, ou très peu, à chaque itération, la carte auto organisatrice recouvre toute la topologie des données.

Représentation de l'algorithme d'auto-organisation pour le modèle de Kohonen. Chaque neurone a un vecteur référent qui le représente dans l'espace d'entrée. Un vecteur d'entrée v est présenté. v sélectionne le neurone vainqueur s, le plus proche dans l'espace d'entrée. Le vecteur référent du vainqueur w_s est rapproché de v. Les vecteurs référents des autres neurones sont aussi déplacés vers v, mais avec une amplitude moins importante.

Formalisation mathématique

La cartographie de l'espace d'entrée est réalisée en adaptant les vecteurs référents w_r. L'adaptation est faite par un algorithme d'apprentissage dont la puissance réside dans la compétition entre neurones et dans l'importance donnée à la notion de voisinage.

Une séquence aléatoire de vecteurs d'entrée est présentée pendant l'apprentissage. Avec chaque vecteur, un nouveau cycle d'adaptation est démarré. Pour chaque vecteur v dans la séquence, on détermine le neurone vainqueur, c'est-à-dire le neurone dont le vecteur référent approche v le mieux possible:

$s = \phi _{w}(v)= \arg \min_{r\in A} \left\|v - w_{r} \right\|$

Le neurone vainqueur s et ses voisins (définis par une fonction d'appartenance au voisinage) déplacent leurs vecteurs référents vers le vecteur d'entrée

$w_{r}^{t+1}=w_{r}^{t}+ \Delta w_{r}^{t}$

avec

$\Delta w_{r}^{t} = \epsilon \cdot h \cdot (v - w_{r}^{t}),$

où $\epsilon=\epsilon (t)$ représente le coefficient d'apprentissage et h = h(r,s,t) la fonction qui définit l'appartenance au voisinage.

Le coefficient d'apprentissage définit l'amplitude du déplacement global de la carte.

Sur la notion de voisinage

Tout comme dans le cortex, les neurones sont reliés les uns aux autres, c'est la topologie de la carte. La forme de la carte définie les voisinages des neurones et donc les liaisons entre neurones.

La fonction de voisinage décrit comment les neurones dans la proximité du vainqueur s sont entraînés dans le mouvement de correction. On utilise en général :

$h(r,s,t)= \exp \left( - \frac{\left\| \vec{r} - \vec{s} \right\|}{2 \sigma^{2}(t)} \right),$

où σ s'appelle coefficient de voisinage. Son rôle est de déterminer un rayon de voisinage autour du neurone vainqueur.

La fonction de voisinage h force les neurones qui se trouvent dans le voisinage de s à rapprocher leurs vecteurs référents du vecteur d'entrée v. Moins un neurone est proche du vainqueur dans la grille, moins son déplacement est important.

La correction de vecteurs référents est pondérée par les distances dans la grille. Cela fait apparaître, dans l'espace d'entrée, les relations d'ordre dans la grille.
Pendant l'apprentissage la carte décrite par les vecteurs référents du réseau évolue d'un état aléatoire vers un état de stabilité dans lequel elle décrit la topologie de l'espace d'entrée tout en respectant les relations d'ordre dans la grille.

Propriétés

• Similitude des densités dans l'espace d'entrée :
  La carte reflète la distribution des points dans l'espace d'entrée. Les zones dans lesquelles les vecteurs d'entraînement v sont tirés avec une grande probabilité d'occurrence sont cartographiées avec une meilleure résolution que les zones dans lesquelles les vecteurs d'entraînement v sont tirés avec une petite probabilité d'occurrence.

• Préservation des relations topologiques :
  Des neurones voisins dans la grille occupent des positions voisines dans l'espace d'entrée (préservation des voisinages de la grille) ; et des points proches dans l'espace d'entrée se projettent sur des neurones voisins dans la grille (préservation de la topologie de l'espace d'entrée). Les neurones ont tendance à discrétiser l'espace de façon ordonnée.

Avantages et inconvénients des cartes auto adaptatives

Les ancêtres des cartes auto-organisatrices, les algorithmes comme "k-moyennes", réalisent la discrétisation de l'espace d'entrée en ne modifiant à chaque cycle d'adaptation qu'un seul vecteur référent. Leur processus d'apprentissage est donc très long.

L'algorithme de Kohonen profite des relations de voisinage dans la grille pour réaliser une discrétisation dans un temps très court. On suppose que l'espace n'est pas constitué de zones isolées, mais de sous-ensembles compacts.
Donc en déplaçant un vecteur référent vers une zone, on peut se dire qu'il y a probablement d'autres zones dans la même direction qui doivent être représentées par des vecteurs référents. Cela justifie le fait de déplacer les neurones proches du vainqueur dans la grille dans cette même direction, avec une amplitude de déplacement moins importante. L'algorithme présente des opérations simples ; il est donc très léger en termes de coût de calculs.

Le voisinage dans les cartes auto adaptatives est malheureusement fixe, et une liaison entre neurones ne peut être cassée même pour mieux représenter des données discontinues. Les Growing Cell Structure, ou Growing Neural Gas sont la solution à ce problème. Des neurones et les liaisons entre neurones peuvent y être supprimées ou ajoutées quand le besoin s'en fait sentir.

Références

• T. Kohonen, Self-Organized Formation of Topologically Correct Feature Maps, Biological Cybernetics, vol. 46, pp. 59–69, 1982.
• T. Kohonen, Self-Organizing Maps, vol. 30, Springer Verlag, 1995.
• H. J. Ritter, T. M. Martinetz, et K. J. Schulten, Neural Computation and Self-Organizing Maps : An Introduction, Addison-Wesley, 1992.

Articles connexes

• Sciences cognitives
• Intelligence artificielle
• Connexionnisme
• Neurone formel
• Réseau neuronal artificiel
• Réseau de neurones de Hopfield

Liens

• Un site canadien sur le sujet (en anglais)
• Growing Neural Gas
• Applet Java de reconnaissance de forme (algorithme de Kohonen et Gaz Neuronal)