DIC9310-7Les réseaux à apprentissage compétitif :

1.Les réseaux de Kohonen

Introduction

L’apprentissage compétitif permet la spécialisation sélective des neurones pour apprendre les vecteurs stimuli.

Dans sa forme extrême, l’apprentissage avide, un seul neurone par essai d’apprentissage voit ses poids synaptiques mis à jour, celui avec la grande activation.

Deux architectures majeures utilisent l’apprentissage compétitif1

o Les réseaux de Kohonen utilisent une approche d’apprentissage qui préserve la topologie de l’espace d’apprentissage dans le réseau final

o Les réseaux ART (« Adaptive Resonnance Theory ») apprennent en identifiant de formes non connues auparavant.

Dans tous les réseaux, c’est la compétition entre neurones qui détermine la ou les unités soumises à l’adaptation des poids.

L’apprentissage conséquent peut être supervisé (CPN et LVQ - voir plus loin) ou non supervisé (SOM et ART). o Dans l’apprentissage non supervisé, ce sont les « régularités »

dans les patrons d’apprentissage qui permettent d’associer ces derniers avec certains neurones.

1 Un troisième type de réseau, le CPN (Counter Propagation Network) utilise aussi l’apprentissage compétitif, mais est vu comme reprenant des caractéristiques des deux architectures principales.

Les réseaux de Kohonen

Développés par Teuvo Kohonen de l’Université d’Helsinki dans les années 70-80 S’inspirent de l’organisation du cortex cérébral où les zones réceptrices sont

organisées suivant une topologie qui respecte celle des récepteurs sensoriels. o Des zones physiquement proches dans le cortex visuel correspondent à des zones qui le

sont aussi dans la rétine; des neurones proches dans le cortex auditif détecteront des fréquences voisines.

o On a observé dans le cortex l'existence au niveau des cortex moteur et sensoriel de cartes somatotopiques qui traduisent la surface sensorielle superficielle du corps.

Le détail de l’organisation n'est pas uniquement d’origine génétique, mais résulte aussi d'un développement faisant suite à des phases d'apprentissages.

L'homoncule : la surface occupée au niveau cortical est fonction de la sensibilité sensorielle ou précision motrice de la partie du corps correspondante. Ainsi, la surface occupée par le pouce est supérieure à celle de la cuisse (arrangement spatial optimal). D'autre part, la topologie est conservée : les doigts sont l'un à coté de l'autre, etc.

Comment une telle représentation peut-elle se bâtir dans le cortex ? Comment peut-être se réaliser sans l’aide d’un « professeur »? Kohonen à proposé plusieurs modèles de RNA pour répondre à ces

questions, en particulier la carte auto-organisatrice qui tente de reproduire l'organisation topologique des stimuli appliqués au réseau pendant l’apprentissage.

Trois types d’architectures de réseau: o « Le chapeau mexicain »

o Les cartes auto-organisatrices (« Self-Organizing Maps » ou SOM)

o La quantification vectorielle par apprentissage (« Learning Vector Quantization » ou LVQ)

Le chapeau mexicain et le SOM utilisent un apprentissage non supervisé, le LVQ un apprentissage supervisé.

Le LVQ est destiné à des applications de classification, alors que les deux premiers servent aussi bien à des fins d’association que de classification. Ils sont particulièrement adaptés aux applications ou les données montrent une cohésion spatiale ou temporelle.

Apprentissage La mise à jours des poids synaptiques se fait de manière à rapprocher le vecteur des

poids du prototype à apprendre, ou l’en éloigner dans LVQ. La distance entre un vecteur d’apprentissage et un vecteur poids décide

des neurones à mettre à jour. À la fin de l’apprentissage cette distance est idéalement réduite à zéro pour le ou les neurones qui reconnaissent le vecteur .On a la règle d’apprentissage suivante pour un neurones j, à une itération donnée :

Donc, l’écart entre et sert à l’adaptation des poids synaptiques. La sélection du neurone j se fait en prenant celui qui a la plus petite distance (euclidienne au autre) entre le vecteur des poids et le vecteur d’apprentissage.

Si les vecteurs et sont normés et que le carré de la distance euclidienne est utilisé pour mesurer la distance qui les sépare, on peut remplacer la distance par le produit scalaire des vecteurs. En effet, on a :

On peut voir d’après cette équation que si on les vecteurs et sont de longueurs constantes, l’évaluation de la distance entre eux revient à calculer leur produit scalaire. Noter que dans ce cas, le calcul de la distance est une forme de calcul du niveau d’activation d’un neurone, où le terme

joue le rôle d’un biais ajouté.

Le chapeau mexicain ou réseau à inhibition latérale

Imite le mécanisme d’inhibition latérale observé dans le système visuel. o On organise les poids synaptiques de manière à ce que chaque

neurone projette des connections excitatrices vers ses voisins immédiats, des connections inhibitrices plus loin, et des connections nulles plus loin encore.

Typiquement, chaque neurone possède deux rayons de voisinage R1 et R2 avec des connections excitatrices dans R1 et inhibitrices entre R1 et R2. o Afin de simplifier les calculs, les poids des deux types de

connections prennent des valeurs constantes. o On a donc une fonction d’activation de la forme

f est une fonction en rampe qui va de 0 à xmax

Le choix des poids est fait à priori et les mêmes valeurs sont utilisées pour tous les neurones.

Le réseau à carte auto-organisatrice (SOM) Ce réseau classe les vecteurs d’apprentissage par groupes, chacun représenté par un

neurone de sortie. Conceptuellement constitué de deux couches d'interconnexions, d’un certain

nombre d’entrées et d'une couche de neurones de sortie. 1. Couche plastique : mémorise les modifications de poids. Elle relie les neurones

de sortie à ceux d’entrée selon le modèle du combinateur linéaire et produit une mesure de similarité entre les vecteurs poids s associés à chaque neurone et l'entrée présentée

2. Couche d'interconnexions : couche compétitive qui renforce sélectivement l'activité du réseau suivant un réseau à inhibitions latérales similaire à celui observé dans le système visuel.

Réseau SOM linéaire à cinq neurones ( S1, S2, S3, S4, S5) et deux entrées (x1,x2).

Réseau SOM bidimensionnel à p2neurones et n entrées, où chaque neurone est connecté à ses 4 plus proches voisins.

Dans la couche d'interconnexions, chaque neurone est fortement relié à ses voisins immédiats (physiquement). Le poids diminue ensuite en fonction de la distance.

La variation des poids en fonction de la distance devrait suivre une forme de chapeau mexicain2 ; dans les faits, le SOM simplifie cette fonction en un rectangle dans un voisinage donné qui est grand au début de la stimulation, mais dont le rayon rétrécit avec le temps.

2 Ce type d’inhibition existe dans le cortex visuel où l'on observe une excitation latérale entre cellules dans un rayon de 50 à 100 , suivie de connexions inhibitrices dans un rayon de 200 à 500 .

Utilisation du SOM comme classifieur

On ajoute une couche de sortie

Algorithme d’apprentissage du SOM :

1) Initialisation des poids à des valeurs aléatoires, du rayon de voisinage et de son pas et période de mise à jour.

2) Répeter :

a) Pour chaque vecteur d’apprentissage

1) Calculer la distance au carré de chacun des neurones j par rapport à :

2) Sélectionner le neurone J qui présente la plus courte distance entre et  :

3) Adapter les poids du neurone J et de tous ses voisins dans le rayon de

voisinage courant :

b) Modifier le rayon de voisinage à la baisse si sa période de mise à jour est atteinte; modifier au besoin ;

tant que les performances sont insuffisantes

Dans la règle d’apprentissage, le nombre de voisins du neurone vainqueur dépend de la topologie du réseau

o Un rayon de voisinage qui vaut 1 correspond à deux voisins dans un réseau uni-dimensionnel (J1), quatre voisins dans un réseau bidimensionnel carré (J1 dans les deux directions) et six voisins dans un réseau bidimensionnel hexagonal.

o La position relative des neurones les uns par rapport aux autres joue un rôle important.

Le voisinage d'adaptation d'un neurone doit respecter la relation qui définit le voisinage physique, on parlera donc de 1er , 2e ou de n-iéme voisins, suivant la distance à laquelle on va sélectionner les neurones tout en respectant cette relation.

Le voisinage peut varier au cours du temps, et permettra de contrôler le nombre de vecteurs modifiés autour du neurone gagnant pour une entrée .

Fonctionnement au cours du temps du réseau. On voit se dégager progressivement, pour une même information, un foyer d'excitation alors que les autres neurones sont inhibés.

Pour une entrée donnée, on rapproche donc « un peu » les coefficients synaptiques du neurone sélectionné et ceux qui font partie de son voisinage, et on laisse les autres inchangés.

L'amplitude de la modification dépend du coefficient et du rayon de voisinage qui décroissent généralement avec le temps.

Comme le nombre de neurones inclus dans un rayon de voisinage donné dépend de la topologie du réseau, cette dernière se trouve aussi avoir un effet sur les capacités d’apprentissage du réseau.

Exemple d’apprendre 7 lettres de l’alphabet représentées avec 3 polices différentes en utilisant trois topologies de réseau, chacune comprenant 25 neurones :

Réseau sans topologie (R=0) Réseau linéaire avec R=1

Réseau bidimensionnel avec R=1

Réseau sans topologie (R=0): les 21 formes présentées sont apprises par 5 des 25 unités

Unité Lettre apprise

3 C1,C2,C3

13 B1, B3, D1, D3, E1, K1, K3, E3

16 A1, A2, A3

18 J1, J2, J3

24 B2, D2, E2, K2

Réseau à topologie linéaire avec R=1 : les 21 formes sont apprises par 9 unités sur les 25, offrant ainsi une meilleure sélectivité.

Unité Lettre apprise Unité Lettre apprise

6 K2 20 C1, C2, C3

10 J1, J2, J3 22 D2

14 E1, E3 23 B2, E2

16 K1, K3 25 A1, A1, A3

18 B1, B3, D1, D3

Réseau à topologie bidimensionnelle avec R=1 : les 21 formes sont apprises par 11 unités sur les 25. La table qui suit identifie les lettres apprises par chaque unité située aux coordonnées (x,y) dans le réseau.

x/y 1 2 3 4 5

1 J1, J2, J3 D2

2 C1, C2, C3 D1, D2 B2, E2

3 B1 K2

4 E1, E2, B3 A3

5 K1, K3 A1, A2

Suivi graphique de la dynamique d’auto organisation

Moyen simple pour suivre l'effet de l'algorithme d’apprentissage On suit l’évolution du SOM dans l'espace des coefficients.

o Les vecteurs d'entrée sont de même dimension que le vecteur des coefficients chaque neurone ; ils peuvent donc être représentés sur un même diagramme, sans chercher à donner une signification aux axes

o Grâce à cette représentation, on est en mesure de visualiser l'organisation qui apparaît au cours de l'apprentissage

En deux dimensions par exemple, chaque neurone est placé aux coordonnées de son vecteur de coefficients (wj1, wj2) ; modifier ce vecteur se traduit par un déplacement du neurone dans la carte.

Réseau unidimensionnel à deux entrées montrant la représentation conventionnelle de la topologie du réseau et la représentation correspondante dans l’espace des coefficients. Dans la première représentation, chaque neurone porte un numéro et est relié aux entrées par ses poids synaptiques; dans la seconde, l'emplacement d’un neurone dépend de la valeur de ses coefficients, et la relation physique entre voisins est rappelée par les lignes qui relient les neurones..

Exemple d’un réseau bidimensionnel de 10x10 neurones à voisinage carré de rayon 1, avec des entrées de dimension 2.

L’initialisation des coefficients synaptiques avec des valeurs aléatoires centrées au milieu du carré donne le diagramme suivant dans l’espace des coefficients.

Si on fournit au réseau ensuite des vecteurs d’entrée uniformément repartis dans le carré, la position des neurones dans l'espace des coefficients aboutira généralement à la même répartition.

Exemple d'évolution des positions aux instants t = 10, 200 et 1000 itérations. L’apprentissage se traduit par l'apparition d'une « organisation » autonome du réseau, qui était initialement désordonné.

Le réseau s’adapte aussi à des distributions non carrées et/ou non uniformes.

a) b)Adéquation entre la dimension et la forme du réseau avec l'espace des entrées ; cas d'une carte triangulaire équilatérale (chaque côté du triangle comporte le même nombre de neurones) ; hormis sur la périphérie, chaque neurone possède six voisins. a) Carte carrée dans un triangle, b) Carte triangulaire dans le même triangle.

 

Occupation non uniforme d'un carré par un réseau carré ; les neurones se concentrent dans la zone de distribution plus élevée, correspondant à une plus grande représentation au niveau de

l’espace d’apprentissage.

Application à la reconnaissance des lettres

Que traduit l’auto-organisation ?

Se rappeler que la dimension des entrées et la dimension des poids synaptiques sont les mêmes. D'autre part, la règle d’apprentissage fait que le domaine de variation des coefficients est confondu avec celui des entrées (puisque

)

=> la distribution des entrées et celle des poids appartiennent au même espace et la correspondance entre les deux apparaît naturellement et respecte la topologie de l'espace, c'est-à-dire que deux points voisins, suffisamment proches dans l'espace d'entrée, sont représentés par le même vecteur ou par deux vecteurs de coefficients voisins.

La quantification vectorielle par apprentissage

Groupe un ensemble de vecteurs en classes définies par un « codebook » qui contient les coordonnées des différents centroïdes.o La solution classique donne des résultats qui dépendent des

conditions initiales du codebook. o La capacité du SOM à s’auto organiser résout le problème;

chaque neurone du réseau prend en charge une région de l’espace stimuli dont il est le centre.

Exemple d’un espace carré uniforme représenté par un réseau bi-dimensionnel. Dans la figure, chaque neurone est représenté par une croix, et la relation entre neurones est montrée par les liens entre les croix. La zone polygonale autour de chacun d'eux délimite la région de l'espace d'entrée qu’il prend en charge. La forme précise de cette région est liée au choix de la mesure de distance entre neurones et de la procédure de sélection du neurone vainqueur durant la phase d’apprentissage. Un diagramme de Voronoi est couramment utilisé pour couvrir l’espace d’entrée..

La topologie du réseau n’a pas de pertinence, le but de l’apprentissage est de grouper un ensemble de n vecteurs en m amas représentés par les m neurones du réseau. Il en va de même pour le concept de voisinage, puisque chaque neurone veut être le centre d’un amas3.

L’apprentissage est supervisé ; on sait a priori à quelle classe appartient un vecteur d’apprentissage.

Algorithme d’apprentissage LVQ :

3 À moins d’introduire un apprentissage flou, mais cela est une autre histoire…

1) Initialiser les poids à des valeurs aléatoires, et le gain et période de mise à jour ;

2) Répéter :

a) Pour chaque vecteur d’apprentissage :

1) Calculer la distance de chacun des neurones j par rapport à :

2) Sélectionner le neurone J qui présente la plus courte distance :

3) Adapter les poids du neurone J  :

Si J correspond à la classe de

sinon

b) Modifier à la baisse si sa période de mise à jour est atteinte

tant que les performances sont insuffisantes

Plusieurs variantes de l’algorithme existento L’initialisation des poids peut se faire en prenant m vecteurs

dans l’apprentissage, en prenant des valeurs au hasard, ou encore en passant les vecteurs d’apprentissage dans un SOM et en prenant les coordonnées des neurones à l’équilibre.

Applications des réseaux de Kohonen

Le SOM et l’algorithme LVQ ont été utilisés dans un nombre impressionnant d’applications.

o Reconnaissance de la voix

o Reconnaissance de l’écriture,

o robotique,

o compression d’images,

o optimisation,

o etc. tout y est passé.

Un réseau de Kohonen a aussi été proposé pour résoudre le problème du commis voyageur.

Problème du commis voyageur

Réseau linéaire dont les neurones sont au nombre des villes à visiter et dont les entrées sont les coordonnées des villes.

Contrairement à la solution de Hopfield, on ne part pas d’une topologie fixe et d’une fonction d’énergie à minimiser4.

4 Cette dernière existe mais est rarement utilisée à des fins pratiques ; pour le SOM, on a

Dactylo phonographique

Commande de bras de robot