Modélisation à l’aide des graph machines

Matrice d’adjacence

Plusieurs représentations sont possibles pour les graphes. Elles ne sont pas équivalentes, et le choix d’une représentation adaptée au problème à résoudre permet d’obtenir une meilleure efficacité des algorithmes utilisés. On distingue ainsi la représentation par matrice d’adjacence, par matrice d’incidence sommets-arcs (ou sommets-arêtes), et par liste d’adjacence. Nous utilisons la matrice d’adjacence, car cette représentation permet de calculer simplement certaines caractéristiques des graphes, telles que la distance entre les sommets. La matrice d’adjacence d’un graphe G = {S, A} est la matrice M(G) dont les coefficients mi, j sont définis par : mi,j = (19) La Figure 3.2 représente un graphe ainsi que la matrice d’adjacence qui lui correspond. Fig.3.2 : Représentation d’un graphe par sa matrice d’adjacence Si n est le nombre de nœuds du graphe, cette matrice est de taille (n, n), et chaque ligne ainsi que chaque colonne correspond à un nœud particulier. Puisque la matrice dépend de la numérotation des nœuds du graphe, la représentation n’est pas unique (il existe n! possibilités). Il est cependant possible de passer d’une représentation à une autre par permutation de lignes et de colonnes. La matrice d’adjacence permet d’énumérer les chemins du graphe, et d’en déduire la connexité, la cyclicité ainsi que les distances entre les nœuds. On utilise pour cela le produit Chapitre 3 Modélisation à l’aide des graph machines 58 matriciel. Par exemple, la matrice M2 a pour coefficients : (M2 )i,j = Chaque composant de la somme est donc non nul ssi il existe une arête de si à sk et de sk à sj , c’est-à-dire s’il existe un chemin de longueur 2 reliant si à sj et passant par sk. Par extension, on peut démontrer que si M est la matrice d’adjacence d’un graphe G dont les sommets sont numérotés de 1 à n, le nombre de chemins de longueur exactement l allant de si à sj est le coefficient (i, j) de la matrice Ml . Un algorithme permet alors de calculer la distance entre deux nœuds si et sj : (20) On en déduit le diamètre du graphe : D = (21) Il est par ailleurs possible de déterminer la connexité d’un graphe, c’est-à-dire le nombre de composantes connexes, et d’en déduire le nombre de cycles indépendants que comporte le graphe : (22) Cette représentation des graphes permet ainsi d’accéder aisément aux principales caractéristiques d’un graphe, ainsi que d’effectuer des opérations telles que la suppression d’une arête ou d’un cycle. 

Apprentissage à partir de graphes 

RAAMs et LRAAMs Nous allons maintenant expliquer comment il est possible d’établir une relation entre un ensemble de données structurées, représentées par des graphes, et un ensemble de nombres réels, réalisant ainsi l’association structures-données réelles évoquée. Les premiers essais de modélisation de données structurées remontent aux mémoires associatives dynamiques. Ces essais ont par la suite conduit aux Mémoires Auto-Associatives Récursives (RAAMs), qui permettent de représenter de façon compacte les arbres, et aux RAAMs étiquetés (LRAAMs). 3.2.1 Les Mémoires Auto-Associatives Récursives Afin de montrer la capacité des réseaux de neurones à manipuler des données structurées, Pollack a proposé un modèle, fondé sur l’idée d’une mémoire associative entre une structure et un vecteur de taille fixe [53]. Les RAAMs (pour Recursive AutoAssociative Memory) et leurs dérivées sont des modèles établis à partir de réseaux de neurones, qui apprennent un codage d’une structure en un vecteur, puis sont à même de décoder la structure d’origine à partir de ce vecteur avec une perte d’information minimale. L’élément de base des RAAMs est un codeur-décodeur constitué par un réseau de neurones possédant autant de variables que de sorties (Ne = Ns), et dont le nombre de neurones cachés est inférieur au nombre de variables (Nc < Ne). Un exemple d’un tel codeur-décodeur est représenté sur la Figure 3.3. À l’issue de l’apprentissage, le système réalise une autoassociation, car les sorties du modèle sont identiques aux variables : la base d’apprentissage est du type ({xk ,xk }, 1 ≤ k ≤ n). Lorsque le problème admet une solution, les neurones cachés réalisent un codage du vecteur de variables x sous forme compacte f(x) (car Nc < Ne), où f(x) désigne le vecteur des sorties des neurones cachés. Ce vecteur f(x) peut ensuite être décodé, afin de retrouver en sorties les données d’entrée. Chapitre 3 Modélisation à l’aide des graph machines 60 Fig.3.3 : Codeur-décodeur constitué de neurones formels Cette unité codeur-décodeur peut être utilisée pour effectuer le codage d’un arbre, de différentes manières. Dans l’article [54], le codage s’effectue de la façon suivante : les feuilles de l’arbre, c’est-à-dire les noeuds sans enfant, sont tout d’abord codées, puis leurs parents et les noeuds suivants, de façon récursive, jusqu’au noeud racine. Le vecteur obtenu en sortie du codeur correspondant au noeud racine est alors une représentation compacte de l’ensemble de l’arbre. Le décodage s’effectue de façon symétrique et de manière récursive, fournissant successivement le décodage du noeud racine jusqu’aux feuilles de l’arbre. Il est alors possible de réaliser un apprentissage de l’ensemble codeur-décodeur obtenu, de façon à retrouver en sortie un vecteur égal au vecteur d’entrées. Considérons par exemple l’arbre binaire ((A,B),(C,D)) de la Figure 3.4 où A, B, C et D sont des vecteurs de taille identique.

Les Mémoires Récursives Auto-Associatives Étiquetées

Les Mémoires Récursives Auto-Associatives Étiquetées (LRAAMs, pour Labeling RAAMs) [54] sont des RAAMs qui permettent de tenir compte des étiquettes d’un graphe. Le principe des LRAAMs consiste à considérer deux types d’entrées pour chaque noeud : une partie des entrées correspond aux pointeurs vers les enfants du noeud dans le graphe, comme précédemment, et une seconde partie correspond aux étiquettes des noeuds. À chaque noeud du graphe est ainsi associée une entrée, qui comporte un vecteur de variables (qui peuvent être codées de façon binaire) associé à ses étiquettes, et un ensemble de pointeurs vers ses enfants dans le graphe, qui sont des nombres réels, et dont le nombre est égal à son degré sortant. Ces données constituent donc les entrées des codeurs associés à chaque noeud. Les SRAAMs sont en ce sens des LRAAMs, pour lesquelles il n’y a qu’un seul pointeur. Ceci soulève une nouvelle fois le problème de la cible mobile, car les pointeurs des nœuds non-terminaux sont calculés lors de l’apprentissage, donc varient. Ce problème peut être évité en utilisant la même idée que celle présentée dans le cadre des RAAMs, c’est-à-dire en associant à l’arbre étiqueté un modèle dont la structure est isomorphe à celle de l’arbre. À chaque noeud sont associés un codeur et un décodeur, et les réseaux de neurones constituant les codeurs-décodeurs des différents noeuds sont à poids partagés : ces réseaux partagent le même jeu de paramètres.