<page>
    <title>Carte auto adaptative</title>
    <id>819073</id>
    <revision>
      <id>31233301</id>
      <timestamp>2008-07-02T17:37:28Z</timestamp>
      <contributor>
        <username>Xofc</username>
        <id>66118</id>
      </contributor>
      <comment>[[User:EDUCA33E/LiveRC/Documentation|LiveRC]] : Révocation des modifications de [[Special:Contributions/89.232.5.97|89.232.5.97]]; retour à la version de [[User:VanBot|VanBot]]</comment>
      <text xml:space="preserve">==Définitions==
''' 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ée.  On la désigne souvent par le terme anglais ''self organizing map'' ('''SOM'''), on encore '''carte de [[Kohonen]]''' 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 pour étudier la répartitions 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 [http://video.google.fr/videoplay?docid=-2649568088984419360] pour la discrétisation de l'éspace 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 ''[[stimulus|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 diviser l'espace en plusieurs zones, et assigner
à chaque zone un point signifcatif dit ''vecteur référent''

[[Image:Architecture_SOM.JPG ]]


'''Architecture des cartes auto-organisatrices. L'espace d'entrée ''V'' est divisé en plusieurs zones. &lt;math&gt;w_{r}&lt;/math&gt; représente un vecteur référent associé à une petite zone de l'espace &lt;math&gt;V_{r}^{M}&lt;/math&gt; 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 noeud 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. De plus, ils
gardent les relations de voisinage dans la grille, donc ils permettent
une indexation facile, en utilisant les coordonnées dans la grille.
Toutes ces caractéristiques s'avèrent très utiles dans divers domaines, comme
la classifcation 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 &lt;math&gt; v\in V&lt;/math&gt;  un neurone &lt;math&gt; r\in A &lt;/math&gt;  désigné par son vecteur de position &lt;math&gt;\vec{r}&lt;/math&gt;, tel que le vecteur référent &lt;math&gt;w_{r}&lt;/math&gt; est le plus proche de ''v''.


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

&lt;math&gt;
\phi _{w}:V\rightarrow A 
&lt;/math&gt;


&lt;math&gt;
            r = \phi _{w}(v)= \arg \min_{r\in A} \left\|v - w_{r} \right\|.  
&lt;/math&gt;


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 

&lt;math&gt;w_{r}=\phi _{w}^{-1} (\phi _{w}(v))&lt;/math&gt; 


* ''classificateur'' en utilisant la fonction  &lt;math&gt;r= \phi _{w}(v)&lt;/math&gt;  

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.

[[Image:Algorithme som.JPG]]

'''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électione le neurone vainqueur ''s'', le plus proche dans l'espace d'entrée. Le vecteur référent du vainqueur &lt;math&gt;w_{s}&lt;/math&gt; 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é en adaptant les vecteurs référents &lt;math&gt; w_r &lt;/math&gt;. 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:

&lt;math&gt;
s = \phi _{w}(v)= \arg \min_{r\in A} \left\|v - w_{r} \right\|
&lt;/math&gt;

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

&lt;math&gt;
 w_{r}^{t+1}=w_{r}^{t}+ \Delta w_{r}^{t}
&lt;/math&gt;

avec 

&lt;math&gt;
 \Delta w_{r}^{t} =  \epsilon \cdot h \cdot (v - w_{r}^{t}), 
&lt;/math&gt;

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


Le coefcient 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 :

&lt;math&gt;
h(r,s,t)= \exp \left( - \frac{\left\| \vec{r} - \vec{s} \right\|}{2 \sigma^{2}(t)} \right),
&lt;/math&gt;

où &lt;math&gt;\sigma&lt;/math&gt; 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énient des cartes auto adaptatives==

Les ancêtres des cartes auto-organisatrices, les algorithmes comme &quot;k-moyennes&quot;, réalisent la discrétisation de l'espace d'entrée en 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érisation 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 problablement 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. Il est essentiel d'observer
que l'algorithme présente des opérations très simples donc qu'il est
très léger du point de vue du 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éferences ==

T. Kohonen, &quot;Self-Organized Formation of Topologically Correct Feature Maps&quot;, Biological Cybernetics, vol. 46, pp. 59-69, 1982.

T. Kohonen, Self-Organizing Maps, vol. 30. Berlin : Springer-Verlag, 1995.

H. J. Ritter, T. M. Martinetz, et K. J. Schulten, Neural Computation and Self-
Organizing Maps : An Introduction. Reading, MA : Addison-Wesley, 1992.

== Liens ==

* [http://www.ryerson.ca/~dgrimsha/courses/cps721/kohonen.html Un site Canadien sur le sujet.( en Anglais.)]

* [http://www.ryerson.ca/~dgrimsha/courses/cps721/competitive.html Carte adaptative et apprentissage compétitif.(en Anglais.)]

* [http://www.shef.ac.uk/psychology/gurney/notes/l7/subsection3_3_3.html#SECTION0003300000000000000 Un exemple graphique.(en Anglais.)]

* [http://www.neuroinformatik.ruhr-uni-bochum.de/VDM/research/gsn/JavaPaper/node19.html Growing Neural Gas]

[[Catégorie:cybernétique]]

[[ar:شبكات كوهونين ذاتية التنظيم]]
[[de:Selbstorganisierende Karte]]
[[en:Self-organizing map]]
[[es:Kohonen (RNA)]]
[[fi:Itseorganisoituva kartta]]
[[it:Self-Organizing Map]]
[[ja:自己組織化写像]]
[[ko:자기조직화지도]]
[[nl:Kohonen-netwerk]]
[[ru:Самоорганизующаяся карта Кохонена]]
[[sl:SOM]]
[[uk:Самоорганізаційна Карта Кохонена]]</text>
    </revision>
  </page>