Nouvelles Chroniques d'Amethyste

Penser au Sens, pas au Verbe

Réseau de neurones: les cartes auto-adaptatives

Poster un commentaire

Continuons notre exploration du monde des réseaux de neurones. Les cartes auto-adaptatives (Self-Organizing Map) ou réseau de Kohonen sont des réseaux que j’aime beaucoup car ils se prêtent à une représentation visuelle souvent spectaculaire.

Ce réseau n’a qu’une seule couche, mais l’innovation apportée par Kohonen est de disposer les neurones selon une certaine géométrie. On a ainsi des réseaux linéaires, en matrice, sphériques… Chaque géométrie a ses particularités dont on tire profit lors du fonctionnement du réseau.

Comme toujours on trouvera un projet exemple dans mon espace Github:

https://github.com/DeLeneMirouze/NeuralNetwork

Plusieurs projets sont concernés par cet article.

 

Bien entendu je vous encourage d’écrire vous même votre code. C’est le moyen le plus efficace de comprendre. Faites en particulier attention à un piège expliqué ici:

http://stackoverflow.com/questions/9288904/division-returns-zero

Cela signifie juste que C# est conforme à la norme IEEE 574.

On a vite fait de s’arracher les cheveux!

Description du réseau de Kohonen

Voici un exemple de carte de Kohonen sous la forme d’une matrice 3×3:

2015-09-14_23-12-14

La couche d’entrée est un vecteur de dimension n. Chaque neurone du réseau est relié à toutes les valeurs de la couche d’entrée et disposeront donc de n valeurs de poids.

 

Les caractéristiques de ce réseau sont les suivantes:

  • Une seule couche de neurone que l’on appelle souvent carte
  • Chaque neurone est relié à tous les nœuds de la couche d’entrée
  • Les neurones ne sont pas reliés les uns aux autres
  • Les neurones ont autant de valeur de poids qu’il y a de nœuds dans la couche d’entrée. Il y a aussi un biais comme pour tous neurones

L’ensemble des nœuds de la couche d’entrée s’appelle souvent un vecteur.

Apprentissage

Comme pour tous réseau une phase d’apprentissage à partir d’un jeu d’essai est nécessaire. Les étapes de l’algorithme sont les suivantes:

  1. Initialiser le réseau avec des poids choisis au hasard
  2. Un vecteur du jeu d’essai est présenté au réseau
  3. On parcourt chaque neurone du réseau pour rechercher celui qui ressemble le plus au vecteur d’entrée
    Ce neurone est appelé le neurone gagnant ou BMU (Best Matching Unit)
    Nous verrons plus loin ce que l’on entend par « ressemble le plus »
  4. Les neurones constituant le voisinage du BMU sont recherchés
    Le voisinage est défini par le choix d’une distance entre neurone. Divers choix sont possibles, c’est à cette étape qu’intervient la géométrie du réseau.
    On notera qu’en général le rayon autour du BMU qui détermine le voisinage est décroissant au fil du temps.
  5. Chaque neurone constituant le voisinage est ajusté pour le faire ressembler, le rapprocher, du BMU. Les poids et les biais sont recalculés
  6. On recommence

On remarque une caractéristique importante de cet algorithme est que l’on ne recalcule pas les poids des neurones en fonction d’un vecteur de sortie, il n’y a pas de couche de sortie.

C’est une propriété intéressante pour les situations où il n’est pas aisé de disposer d’exemples de sortie.

Les équations peuvent être retrouvées un peu partout comme ici:

http://www.shy.am/wp-content/uploads/2009/01/kohonen-self-organizing-maps-shyam-guthikonda.pdf

Voici une synthèse:

Recherche du BMU:

2015-09-17_22-44-48

La somme itère sur les n valeurs de la couche d’entrée I et donc les n valeurs de W, le poids. On calcule la distance entre la couche d’entrée et chaque poids du réseau et on garde celui qui a la valeur la plus faible.

Il existe différents choix possibles de distance. La formule est celle de la distance euclidienne. Testez les pour voir celle qui marche le mieux pour votre problème.

Recherche du voisinage:

2015-09-17_22-52-09

r(t) est le rayon du voisinage pour l’itération t>=0. Il diminue donc pour chaque itération. Dans certaines implémentation on l’ajuste pour qu’il y ai au moins un neurone en plus du BMU (neurone gagnant). Tous les neurones dont la distance au BMU est inférieure ou égale à r feront partie de son voisinage.

r(0) est le rayon de la carte. Si la carte est un cercle il s’agit du rayon du cercle, si la carte est carrée, de la demi arête…

T est une constante de temps calculée ainsi:

2015-09-17_23-08-36

Cette formule est assez arbitraire à vrai dire! On pourrait choisir une autre constante.

Recalcul des poids:

W(t+1) = W(t) + D(t).L(t).(I(t) – W(t))

W(t+1) est la nouvelle valeur du poids connaissant la valeur antérieure W(t). Le calcul est fait pour chacune des n valeurs de poids W et entrée I.

L(t) est le taux d’apprentissage:

2015-09-17_23-14-33

T est la constante de temps de tout à l’heure et L0 la valeur initiale du taux d’apprentissage.

D(t) est calculé ainsi:

2015-09-17_23-17-46

Avec r(t) le rayon précédemment calculé et d la distance du neurone au BMU, c’est à dire le nombre de nœuds entre le BMU et le nœud courant. On calcule d comme la distance euclidienne entre le nœud BMU et le nœud courant.

Cette formule rend un neurone donné de plus en plus proche du BMU. Un neurone proche du BMU « apprendra » plus qu’une neurone proche, tandis qu’un neurone éloigné tendra à être ignoré.

 

Ne pas rester figé sur ces équations, on rencontre de nombreuses variantes, à commencer par les exemples que je fournis!

 

Premier exemple

Le premier projet s’appelle KohonenNetwork. Il s’agit d’un projet Winform.

Le réseau est modélisé par la classe KohonenMap2D. Nous allons créer une entrée constituée d’une image composé par 8 couleurs choisies au hasard. Le réseau va ensuite les classer par similitude en les renormalisant dans la liste des 8 couleurs initiales.

On pourrait parfaitement partir ou arriver à un nombre quelconque de couleurs. Tout dépend de l’objectif assigné à notre réseau. Ici il est purement pédagogique et il m’a semblé que c’est plus facile de visualiser les choses ainsi.

La technique présentée est une approche possible des algorithmes de quantification sur lesquels Kohonen a justement beaucoup travaillé.

 

La phase d’entraînement s’effectue ainsi dans la méthode Entrainer():

// recherche du meilleur neurone
KohonenNeurone gagnant = RechercherGagnant(entrees);
 
// récupère le voisinage du gagnant
List<KohonenNeurone> voisinage = Voisinage(gagnant, iterations, iterationCourante);
if (voisinage.Count == 0)
{
   return;
}
 
// ajuste les poids
AjusterPoids(voisinage, entrees, iterations, iterationCourante);
 
Pas = PasInitial * Math.Exp(-(iterationCourante / iterations));

La méthode est appelée pour chaque itération.

Le jeu d’essai de l’apprentissage du réseau est constitué des pixels d’une image générée automatiquement. Dans l’implémentation chaque couleur de pixel est choisie au hasard parmi 8 couleurs.

Les pixels sont caractérisés par 3 valeurs RGB qui constituent le vecteur d’entrée. On itère sur chaque pixel. Les neurones du réseau auront donc 3 poids, chacun correspondant à une valeurs R, G ou B. La figure qui suit résume les choses avec l’exemple d’une réseau à 2 neurones.

2015-09-17_09-36-32

 

On reconnaît facilement dans la code qui précède, les étapes définies dans l’algorithme. Remarquez que cette fois le pas d’apprentissage n’est pas fixe, il diminue dans le temps, c’est à dire avec le nombre d’itération. IterationCourante est l’itération en cours et est inférieur ou égal à itérations. Là aussi il existe des recherches sur différentes formules.

La recherche du gagnant exploite pour l’essentiel la méthode Helper.Distance:

public static double Distance(double[] v1, double[] v2)
{
   double somme = 0.0;
   for (int i = 0; i < v1.Length; i++)
   {
      double ecart = v1[i] - v2[i];
      somme += ecart * ecart;
   }
 
   double distance = Math.Sqrt(somme);
 
   return distance;
}

De nombreuses distances sont possibles. Ici il s’agit d’une distance euclidienne.

La partie spécifique à ce réseau est la sélection du voisinage:

// on commence par calculer le rayon
double rayon = FonctionsAttenuation.Sigma(RayonCarte, totalIteration, iterationCourante);
 
// on recherche les neurones présents dans le rayon
// leurs poids seront ajustés
List<KohonenNeurone> voisinage = new List<KohonenNeurone>();
for (int x = 0; x < Grille.GetLength(0); x++)
{
   for (int y = 0; y < Grille.GetLength(1); y++)
   {
      KohonenNeurone neurone = Grille[x, y];
      neurone.Distance = Distance(neurone, gagnant);
 
      if (neurone.Distance <= rayon)
      {
         voisinage.Add(neurone);
      }
   }
}
 
Debug.WriteLine("Voisinage: " + voisinage.Count.ToString());
return voisinage;

Grille désigne le réseau sous la forme d’une matrice 2D.

L’algorithme consiste à calculer un rayon à l’aide d’une fonction sigma (mais d’autres choix sont possibles).

On remarque que ce rayon diminue dans le temps. C’est à dire qu’au fur et à mesure de l’apprentissage, le voisinage d’un neurone désigné comme le neurone gagnant sera de plus en plus réduit.

2015-09-14_23-27-52

Le rayon définit alors un disque autour du neurone gagnant et tous les neurones situés dans ce disque appartiennent au voisinage. C’est le point original des réseaux de Kohonen, la géométrie du réseau intervient dans l’algorithme d’apprentissage. Ici il s’agit d’une matrice 2×2, d’où le disque. Lors de leur initialisation, chaque neurone se voit attribuer un couple de valeurs (X,Y) qui définit sa position dans la matrice et permet le calcul de sa distance au neurone gagnant (une distance euclidienne dans mon exemple).

Certaines implémentations imposent que le rayon ne descende pas en dessous d’une certaine valeur de sorte que le voisinage ne soit ni vide, ni réduit au neurone gagnant.

Vient ensuite l’étape cruciale de tous processus d’entrainement de réseaux de neurones: l’ajustement des poids. Cette étape a de nombreuses variantes en fonction des propriétés que l’on souhaite donner au réseau:

foreach (KohonenNeurone neurone in voisinage)
{
   // le facteur d'atténuation (diminue avec la distance au neurone gagnant)
   double facteur = FonctionsAttenuation.Gaus(neurone.Distance, RayonCarte, iterations, iterationCourante);
 
   for (int p = 0; p < neurone.Poids.Length; p++)
   {
      double ecart = facteur * Pas * (entrees[p] - neurone.Poids[p]);
      neurone.Poids[p] += ecart;
   }
 
   neurone.Couleur = Color.Transparent;
}

Souvenons nous que l’on a pas de vecteur de sortie. Le calcul de l’écart se fait donc de façon très différente de ce que l’on a vu pour le Perceptron. Dans notre cas c’est l’état de chaque neurone qui constitue la cible, c’est pour cela que l’on dit souvent que le réseau de Kohonen n’est pas supervisé.

On calcule donc un écart entre l’entrée et la valeur particulière du poids. Pour rappel chaque neurone a 3 valeurs de poids et le calcul est effectué uniquement dans le voisinage du neurone gagnant.

On va donc ajuster le neurone gagnant pour qu’il ressemble au pixel d’entrée et ajuster le voisinage de ce neurone pour qu’ils en soient proches eux aussi.

 

C’est cette étape qui va, itération après itération, rassembler les neurones par similitude et créer la carte de Kohonen. Il est intéressant de noter qu’à part quelques cas particuliers, on ne sait pas démontrer que cette convergence se produit pour tous les réseaux de Kohonen. On a constaté un bon comportement sur des milliers d’exemples, ce qui est une preuve suffisante pour un ingénieur!

 

Si vous avez fait des stats, vous remarquerez une ressemblance du comportement du réseau de Kohonen avec l’analyse factorielle. C’est en effet un des débouché possibles de ce réseau. D’ailleurs les calculs, avec leurs boucles for imbriquées, évoquent facilement les calculs matriciels.

Faisons tourner notre réseau!

Démonstration

Je n’entre pas dans les détails de fonctionnement du formulaire qui ne présente pas de difficultés, pour me concentrer sur l’affichage.

Tout d’abord le vecteur d’entrée:

2015-09-13_12-19-44

Il s’agit d’une matrice 50×50 de couleurs choisies au hasard parmi 8. Mais rien ne vous empêche de modifier le code pour charger une image quelconque.

Une fois entraîné, nous affichons les états du réseau de façon visuelle et en couleur. Cela donne typiquement:

2015-09-13_12-21-39

On voit très clairement comment les couleurs similaires se sont agrégées dans des zones. On peut d’ailleurs afficher la liste des 8 neurones qui ont été le plus souvent des neurones gagnants:

2015-09-13_12-22-24

Remarquez la cohérence entre les positionnements et la carte de Kohonen.

Je vous laisse à titre d’exercice modifier le code pour utiliser un nombre de couleur quelconque. Voici un exemple:

https://www.youtube.com/watch?v=pP8SdSAKRTA

Un autre exemple

Le projet KohonenPath présente un autre exemple dans lequel le réseau est disposé le long d’une ligne.

Visuellement les choses ressemblent à ceci:

2015-09-13_12-39-33

On choisit des points au hasard reliés entre eux sur une ligne. Dans notre exemple il y a 50 points. On peut imaginer une ficelle jetée en tas sur une surface.

Nous allons utiliser le réseau pour démonter la pelote de fils afin que celui-ci soit entièrement dans la zone en forme de L que l’on aperçoit sur la figure.

Le réseau ne connaît rien de la géométrie de cette zone, la fonction d’apprentissage sera juste gratifiée en cas de bonne réponse et pénalisée en cas de mauvaise réponse.

Si on fait tourner un peu le réseau on aboutit à des choses de ce genre:

2015-09-13_12-45-01

Un exercice intéressant serait d’ajouter des contraintes supplémentaires pour que la ficelle soit étalées le plus possible dans le L.

On trouve des tas d’exemples de ce genre notamment en 2D:

https://www.youtube.com/watch?v=aQkIg69ZAXs&list=PLDjaeDn1mUp56-Pf87CqtMUZ98uS7k7s_&index=11

 

Côté code, la classe qui modélise le réseau est KohonenMap. On retrouvera facilement les éléments du code de l’exemple précédent. La principale différence est que le voisinage est calculé de sorte qu’il y ai toujours au moins 4 neurones, ce qui assure que le réseau apprend à chaque itération.

 

Dans notre modélisation les neurones ont deux valeurs de poids correspondant aux deux valeurs X et Y dans cet ordre. On ajuste la fonction d’apprentissage pour que ces poids ne sortent jamais de la grille.

Pour générer une sortie, on sélectionne au hasard des points situés dans la zone du L. Le réseau va donc essayer d’ajuster ses états de façon à ressembler le plus possible à ces points et pénaliser ainsi les états en dehors du L.

Je pense qu’en jouant sur l’algorithme de génération des points on devrait pouvoir assurer que la ficelle recouvre un peu mieux le L. Par exemple on pénalise la branche qui contient le plus de points en diminuant sa probabilité de générer une entrée.

Je vous laisserai jouer avec ça.

 

Pour finir un réseau de Kohonen qui joue au foot (mettez le son, ça vaut la peine!):

https://www.youtube.com/watch?v=cP035M_w82s

https://mobile.aau.at/~welmenre/papers/fehervari-2010-Evolving_Neural_Network_Controllers_for_a_Team_of_Self-organizing_Robots.pdf

2015-09-13_13-18-11

Bibliographie

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s