Self-organizing map

Self-organizing map

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é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 é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 [1] pour la discrétisation de l'espace de travail d'un robot).

Sommaire

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 diviser l'espace en plusieurs zones, et assigner à chaque zone un point significatif dit vecteur référent

Architecture SOM.JPG

Architecture des cartes auto-organisatrices. L'espace d'entrée V est divisé en plusieurs zones. wr 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 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 v\in V un neurone r\in A désigné par son vecteur de position \vec{r}, tel que le vecteur référent wr 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.

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 ws 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 wr. 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ù ε = ε(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. 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é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. 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

Ce document provient de « Carte auto adaptative ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Self-organizing map de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Self-organizing map — A self organizing map (SOM) is a type of artificial neural network that is trained using unsupervised learning to produce a low dimensional (typically two dimensional), discretized representation of the input space of the training samples, called …   Wikipedia

  • Growing self-organizing map — A growing self organizing map (GSOM) is a growing variant of the popular self organizing map (SOM). The GSOM was developed to address the issue of identifying a suitable map size in the SOM. It starts with a minimal number of nodes (usually 4)… …   Wikipedia

  • Self-Organizing Maps — Als Selbstorganisierende Karten, Kohonenkarten oder Kohonennetze (nach Teuvo Kohonen) bezeichnet man eine Art von künstlichen neuronalen Netzen. Sie sind als unüberwachtes Lernverfahren ein leistungsfähiges Werkzeug des Data Mining. Ihr… …   Deutsch Wikipedia

  • Generative topographic map — (GTM) is a machine learning method that is a probabilistic counterpart of the self organizing map (SOM), is provably convergent and does not require a shrinking neighborhood or a decreasing step size. It is a generative model: the data is assumed …   Wikipedia

  • Mind map — A hand drawn mind map A mind map is a diagram used to represent words, ideas, tasks, or other items linked to and arranged around a central key word or idea. Especially in British English, the terms spidergram and spidergraph are more common,[1]… …   Wikipedia

  • Data mining in meteorology — Meteorology is the interdisciplinary scientific study of the atmosphere. It observes the changes in temperature, air pressure, moisture and wind direction. Usually, temperature, pressure, wind measurements and humidity are the variables that are… …   Wikipedia

  • Selbstorganisierende Karte — Als Selbstorganisierende Karten, Kohonenkarten oder Kohonennetze (nach Teuvo Kohonen; engl. self organizing map, SOM) bezeichnet man eine Art von künstlichen neuronalen Netzen. Sie sind als unüberwachtes Lernverfahren ein leistungsfähiges… …   Deutsch Wikipedia

  • Nonlinear dimensionality reduction — High dimensional data, meaning data that requires more than two or three dimensions to represent, can be difficult to interpret. One approach to simplification is to assume that the data of interest lies on an embedded non linear manifold within… …   Wikipedia

  • Kohonen-karten — Als Selbstorganisierende Karten, Kohonenkarten oder Kohonennetze (nach Teuvo Kohonen) bezeichnet man eine Art von künstlichen neuronalen Netzen. Sie sind als unüberwachtes Lernverfahren ein leistungsfähiges Werkzeug des Data Mining. Ihr… …   Deutsch Wikipedia

  • Kohonenkarte — Als Selbstorganisierende Karten, Kohonenkarten oder Kohonennetze (nach Teuvo Kohonen) bezeichnet man eine Art von künstlichen neuronalen Netzen. Sie sind als unüberwachtes Lernverfahren ein leistungsfähiges Werkzeug des Data Mining. Ihr… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”