S'abonner à la newsletter d'AI For Tomorrow
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Si vous deviez représenter votre entourage familial et amical sur une feuille de papier, comment le dessineriez-vous ?
J’imagine que vous commenceriez par vous représenter vous-même, au centre de la feuille. Puis vous ajouteriez les membres de votre famille autour de vous, vos amis proches, les moins proches… Peut-être ajouteriez-vous les liens qui unissent vos amis entre eux, si certains se connaissent, sont en couple.
Certainement un peu de cette manière non ?
C’est un graphe !
On peut y voir les deux principales propriétés des graphes :
Comme nous le constatons, les graphes sont utilisés pour représenter des choses et les liens entre ces choses.
Ils sont très génériques, et permettent donc de représenter de nombreux concepts.
On peut par exemple trouver les connexions entre les utilisateurs d’un réseau social (un peu à la manière de celui que nous avons dessiné plus haut), les liaisons entre les atomes au sein d’une molécule [1], des transactions financières [2], les pages web et pourquoi pas des mots dans un texte. En fait, quasiment n’importe quoi peut être représenté sous forme de graphe.
C’est cette généricité qui donne à l’analyse des graphes son intérêt.
L’analyse des graphes ne date pas de l’apparition des réseaux sociaux ni d’internet, elle est beaucoup plus ancienne.
Elle s’est développée petit à petit à travers une branche des mathématiques que l’on appelle la théorie des graphes.
Le premier problème connu de théorie des graphes est le problème nommé des 7 ponts de Königsberg. C’est un problème qu’a étudié Euler en 1735.
La question qu’il s’est posée consistait à savoir s’il était possible de se promener dans la ville de Königsberg en passant par chaque pont une fois et une fois seulement, tout en revenant au point de départ à la fin de la promenade (évidemment).
Voici un aperçu de la ville de Königsberg :
https://fr.wikipedia.org/wiki/Problème_des_sept_ponts_de_Königsberg
Pour aborder le problème rigoureusement, on représente la ville à l’aide d’un graphe, comme ceci :
https://fr.wikipedia.org/wiki/Problème_des_sept_ponts_de_Königsberg
Les 4 nœuds représentent les endroits de la ville où l’on peut aller :
Les liens entre les nœuds sont les ponts, qui mènent d’un endroit à l’autre.
D’après vous, quelle est la promenade qui remplit les conditions d’Euler ?
Il n’en existe pas ! Euler a démontré qu’il est impossible d’imaginer un parcours qui passe une fois et une seule fois par chaque pont dans cette situation.
La raison est en fait assez intuitive. Prenons n’importe quel endroit d’où notre promenade pourrait commencer, n’importe quel nœud, par exemple le nœud de droite. L’on passera par l’un des trois ponts pour aller vers un autre nœud. Peu importe ensuite quel chemin nous effectuerons, il nous faut revenir au même nœud. Pour revenir au même nœud, nous allons donc emprunter un autre pont que celui que nous avons déjà emprunté. Mais alors, puisque le nœud de droite à trois liens, comment passer par le troisième lien et quand même revenir au point de départ sans utiliser un des deux autres ponts ? C’est impossible !
Puisqu’au moins un nœud du graphe possède 3 liens, alors il est impossible de trouver une promenade qui passera par chaque pont une seule fois en revenant au point de départ.
Cette démonstration constitue la première victoire de la théorie des graphes.
Et elle est loin d’être la dernière. On peut citer le théorème des quatre couleurs, qui montre qu’il suffit de quatre couleurs différentes pour colorier n’importe quelle carte, sans que deux pays limitrophes ne soient coloriés de la même couleur [3].
Maintenant que nous en savons plus sur ce que sont les graphes, revenons au sujet qui nous intéresse : les réseaux de neurones de graphes.
Comme leurs noms l’indiquent, les réseaux de neurones de graphes sont des réseaux de neurones qui opèrent sur les graphes. De la même manière qu’il existe des réseaux de neurones pour le texte, les images, les vidéos (entre autres), il en existe aussi pour travailler avec les graphes.
Qu’est-ce qui constitue la spécificité des réseaux de neurones de graphes ?
Leur spécificité, c'est leur absence de structure. A l'inverse, par exemple, dans une image, on suppose que deux pixels proches sont liés sémantiquement, c’est-à-dire qu’il fait sens de les considérer ensemble.
Prenons cette photo de groupe, et plus spécifiquement la jeune femme au milieu, habillée en blanc. Son visage, comme le visage de n’importe qui, est fait de deux yeux, un nez et une bouche. Je n’ai pas eu à préciser que les yeux, la bouche et le nez ne peuvent pas être positionnés n’importe où.
En fait, c’est même fondamental que les yeux ne soient pas n’importe où. Je ne peux pas considérer que l’œil gauche de la jeune femme en rouge, l’œil droit du jeune homme à droite et le nez et la bouche de la femme au milieu forment un seul et même visage. La proximité et l’agencement sont fondamentaux. Je peux définir un agencement nécessaire des yeux et de la bouche parce qu’une image dispose d’une structure géométrique dans laquelle la distance et les angles ont du sens.
Mais ce n’est plus vrai dans un graphe, parce que je ne peux pas définir d’angle par exemple.
Quel est l’angle entre le lien qui unit Antoine et Clémence, et Clémence et Éloïse dans mon exemple introductif ? Cette question n’a aucun sens puisque je peux représenter les nœuds n’importe où sur la feuille, seuls les liens entre eux comptent.
Les réseaux de neurones doivent prendre en compte cette propriété. Il nous faut redéfinir certaines notions, comme par exemple la convolution (un opérateur mathématique qui calcule une somme des voisins proches, un peu comme une intégrale), très utilisée en traitement d’image.
Ces différences importantes font que les mathématiques utilisées pour travailler avec les réseaux de neurones de graphes sont différentes de celles impliquées dans le traitement d’image.
Pour un aperçu de ces dernières, voici un papier écrit notamment par Yann LeCun à propos de l’apprentissage profond dans des espaces non euclidiens, que l’on appelle l’apprentissage profond géométrique (geometric deep learning) : https://arxiv.org/abs/1611.08097.
Il recense les fondamentaux nécessaires à la compréhension des réseaux de neurones de graphes, et redéfinit quelques opérations dans un espace non-euclidien.
Pour terminer, voici quelques applications des réseaux de neurones de graphes.
L’analyse de réseaux peut aussi bien englober les réseaux sociaux que les citations dans les papiers de recherche (un papier est un nœud et une citation est un lien entre le papier qui cite et le papier cité). On peut avoir besoin, à l’intérieur d’un réseau, de chercher les « communautés », un ensemble de nœuds qui interagissent plus souvent ensemble qu’avec les autres, pour par exemple trouver les cercles d’amis, les groupes d’intérêt…
Recommander des films sur Netflix ou des pages Facebook aux utilisateurs fait usage de ce que l’on appelle les systèmes de recommandation. Ces problèmes consistent en un remplissage de matrices dont les lignes sont les utilisateurs, les colonnes les produits et les valeurs à l’intérieur représentent un score qui indique à quel point un utilisateur a aimé un film par exemple. La difficulté réside dans le fait que chaque utilisateur a vu une très faible minorité de films parmi le catalogue entier. Les matrices sont donc extrêmement peu remplies. En 2009, Netflix avait offert 1 million de dollars à qui pourrait améliorer son système de recommandation, dont les matrices étaient remplies à seulement 0.011% [4] !
De plus en plus, les algorithmes traitent des données en 3 dimensions, pour lesquelles on ne peut plus appliquer les méthodes traditionnelles.
Les médicaments sont relativement faciles à inventer, mais leurs propriétés peuvent être difficiles à anticiper. C’est la raison pour laquelle les essais cliniques sont aussi longs. Mettre au point des algorithmes capables, à partir des molécules, de connaitre la toxicité d’un médicament serait un gain de temps, et donc d’argent, considérable pour la recherche médicale.
La combinaison de la théorie des graphes, de la géométrie non euclidienne et de l’apprentissage profond a fait naître un nouveau domaine complexe et passionnant : l’apprentissage profond géométrique.
Il y a fort à parier que c’est un secteur qui se développera rapidement dans les mois et les années à venir.
Aidez-nous à déterminer le niveau de lecture:
