Antoine Bordes

Directeur
Laboratoire

Facebook Artificial Intelligence Research
Paris

**Abstract**

The performance achieved in the exploitation of relational databases through query languages and the ease with which information is accessed to, using keywords on search engines could suggest that we are close to a situation in which the algorithms “will understand” the “natural” language. Understanding in an operational sense, that is, being able to use this understanding to respond in a relevant way to complex questions expressed by a human in his language. But in reality, equipping machines with such a capacity is still a research task. Admittedly, the indexing capacities making it possible to gather in an almost instantaneous way the pieces of information containing virtually the answer to a question have been in place for a long time but the relevant exploitation of these pieces of information once gathered to give the correct answer is still a very difficult task for a machine. Antoine Bordes presents some of the work carried out on these themes, in the general line of neural networks and deep learning. The methods: encoding symbolic elements in continuous spaces, of which Antoine Bordes explains the principles, memory networks. The obtained results: in the field of interrogation of structured knowledge bases as in the field, more widely open, of the interrogation on text bases, like Wikipedia.

<footnote n="1">¹ Ce chapitre est la transcription, effectuée par Jacques Printz et Jean Pierre Treuil, membres de l'AEIS, de la conférence d'Antoine Bordes faite au colloque organisé par l'AEIS, à l'Institut Henri Poincaré, le 16 mars 2018 ; le texte a été relu et corrigé par le conférencier. Il est publié avec son accord.</footnote>
# 1. Introduction

L'histoire de l'informatique et des ordinateurs est jalonnée par les progrès effectués dans la conception des langages – langages de programmation, de requêtes sur les bases de données – permettant de s'adresser à ces machines pour les utiliser ; mais le moyen idéal pour interagir avec elles serait bien de pouvoir leur parler comme nous le faisons entre nous, et donc de faire en sorte qu'elles puissent apprendre et comprendre le langage humain.

Un tel idéal parait atteignable relativement facilement, nombre de technologies déjà disponibles peuvent en effet le laisser penser. Les requêtes sur Google par exemple sont faites à l'aide d'un langage à base de mots clés que tout le monde s'auto-apprend à utiliser, ce langage peut être vu comme une espèce d'intermédiaire proche du langage humain ; autres exemples, les succès obtenus en reconnaissance de la parole, d'usage courant dans les smartphones, la transcription de la parole en texte, l'assistance à la conduite dans les véhicules récents, les agents conversationnels ou *chatbots* <fnref n="2" />. Il est clair que ces technologies vont être de plus en plus performantes, on parlera de plus en plus à son ordinateur ou à son téléphone, les personnes n'auront pas à apprendre à se servir de ces outils, il faudra juste leur parler.

Toutefois les interfaces en jeu dans ces technologies sont certes complexes, puisqu'elles requièrent notamment un certain décodage de la voix humaine ou celui d'un texte écrit, mais on ne peut dire actuellement qu'elles comprennent ce qui est dit de la même façon qu'un être humain le comprend. Affirmer cela, c'est bien sûr être à même de caractériser la spécificité de la compréhension humaine, et d'identifier les difficultés qu'ont actuellement les machines pour atteindre ce même niveau ; difficultés qui sont encore patentes, alors qu'on dispose de machines « surpuissantes », de très grandes capacités de stockage de données, et de concepts mathématiques et algorithmiques qui ont prouvé leur efficacité dans plusieurs domaines de l'intelligence<fnref n="3" />. L'écart éloignant les machines de la capacité à comprendre comme un humain est, pour résumer, la difficulté qu'elles ont à construire par apprentissage, à manipuler, à utiliser des *abstractions* de haut niveau propres aux humains : autrement dit se construire une représentation du monde sous forme de concepts, savoir les composer, les généraliser, et en conséquence pouvoir les utiliser dans plusieurs contextes. Traitements que les humains font beaucoup et relativement facilement, alors que les machines échouent largement à le faire : en simplifiant, on peut dire qu'actuellement les machines peuvent apprendre dans un contexte et appliquer ce qu'elles ont appris dans le même contexte, et cela pose bien sûr de fortes limites.

<footnote n="2">² Chat, pour discussion en ligne, et bot pour robot : un logiciel programmé pour simuler une conversation en langage naturel, dans le but d'apporter une certaine assistance à son utilisateur.</footnote>

<footnote n="3">³ Que l'on pense par exemple à la reconnaissance d'objets dans les images, la reconnaissance de visages, la capacité de jouer et de gagner au jeu de Go, etc.</footnote>
Dans la confrontation à ces difficultés, l'Intelligence Artificielle oscille depuis le début entre deux « paradigmes », celui des systèmes symboliques et celui des réseaux de neurones<fnref n="4" /> ; sans entrer dans le détail ni refaire l'histoire présentée dans un autre chapitre de cet ouvrage, rappelons brièvement ici les grands traits qui les distinguent, dans la perspective des approches décrites dans ce chapitre. A la base des performances des réseaux de neurones, il y a l'apprentissage statistique. Les réseaux de neurones peuvent intégrer de grands volumes de données diverses ; ils sont ainsi capables d'apprendre, à partir d'une multitude d'exemples de réalisations différentes d'un concept ou d'une tâche, et éventuellement de contre-exemples, à reconnaitre de façon fiable si telle réalisation particulière relève ou non de ce concept ou de pouvoir conduire cette tâche avec succès. Les performances atteintes sont assez robustes aux bruits se superposant à l'information brute portée par un texte, une image, un signal, le déroulement d'un processus, etc. Elles ne nécessitent pas l'intervention d'un expert : elles requièrent simplement les interventions élémentaires certifiant que telles réalisations sont bien des exemples, et telles autres des contre-exemples, au sein de l'ensemble d'apprentissage. Leurs points faibles, c'est d'abord cette nécessité, pour que l'apprentissage aboutisse, d'un très grand nombre d'exemples – les réseaux de neurones sont *very data hungry*<fnref n="5" /> ; c'est ensuite leur *non-transparence*, leur grande difficulté voire impossibilité à rendre compte par eux-mêmes des raisons – au sens où un humain l'entend – qui les conduisent à tel ou tel choix ; par ailleurs ils ne peuvent pas facilement changer de contexte, par exemple utiliser ce qu'ils ont appris sur une tâche pour apprendre plus rapidement à réaliser une nouvelle tâche ; enfin leurs applications à l'apprentissage de la simulation du raisonnement humain restent encore élémentaires, les travaux que nous allons présenter dans ce chapitre visent précisément à élargir les performances dans ce domaine.

Concernant les systèmes symboliques, nous faisons ici référence essentiellement aux *bases de connaissances* avec leurs *ontologies* – les concepts mobilisés et leurs relations – et leurs *systèmes de règles*, basées sur la logique, permettant de conduire des raisonnements relativement complexes, compréhensibles et vérifiables par les humains. Ces *Knowledge Bases (KB)* ont fait depuis les années 1990 l'objet de travaux considérables, avec l'objectif de créer des bases de connaissances gigantesques, comportant des millions de nœuds représentant des concepts allant des plus généraux – des plus abstraits – aux plus spécifiques<fnref n="6" />, avec l'objectif d'englober toute la connaissance sur un domaine donné. Leur construction nécessite – pour l'identification des concepts et des relations, pour la spécification des règles à prendre en compte – l'intervention de nombreux experts. Dans la réalité, de telles bases de connaissances se heurtent à la dynamique même des domaines qu'elles sont censées représenter, de telle sorte qu'il faut sans cesse rajouter des concepts,

<footnote n="4">⁴ Une oscillation entre la logique et la géométrie, pour reprendre une expression de Stéphane Mallat.</footnote>

<footnote n="5">⁵ Pour parler trivialement, pour leur faire comprendre le sens d'un mot, le type d'objet qu'il désigne il faut leur donner 5000 exemples, alors que chez les êtres humains, trois exemples vont peut-être suffire.</footnote>

<footnote n="6">⁶ Pour donner une idée, une KB allant du concept de « chose » à celui de tel modèle de voiture ...</footnote>
des relations et des règles pour ne pas qu'elles deviennent vite obsolètes. Et par ailleurs, la résolution de cas particuliers, la levée d'ambiguïtés, entraine une complexification des règles dont le nombre, pour atteindre les performances humaines, semble potentiellement infini. Aussi bien leur succès a-t-il été limité.

Par rapport à ce bref état des lieux, les travaux dont il va maintenant être question partent de la *conjecture* que les réseaux de neurones – et les algorithmes de la même mouvance – peuvent être adaptés pour dépasser les difficultés rencontrées par les deux paradigmes ; pour opérer (et apprendre) sur des éléments d'information symboliques, et pouvoir ainsi coder des bases de connaissances symboliques et découvrir des structures dans des ensembles de données non structurées.

## 2. Bases de connaissances : d'une approche symbolique à une approche géométrique

<figure><img src="image_1.png" /></figure>

Le premier exemple de travail traite de la capacité des réseaux de neurones d'apprendre à coder des bases de connaissances déjà structurées – plus précisément ici des bases de données relationnelles – de manière à obtenir une structure qui puisse servir aux calculs de réponses correctes à des questions simples, alors même qu'au départ certaines relations peuvent avoir été oubliées, ou même s'avérer fausses. Le schéma ci-contre donne une idée sommaire du type d'inférence espérée : il représente une toute petite base « d'état civil » où les entités sont des personnes et des villes, les relations sont « né à » et « enfant de ». Bien que la relation soit manquante, il est probable (par inférence) que Jane soit née à Miami, puisque son frère John et sa sœur Patti, sont bien nés dans cette ville, et moins probable qu'elle soit née à Austin. C'est ce type d'inférence éventuellement quantifiée par une probabilité que le codage appris par le réseau de neurones devrait pouvoir faciliter. Le principe va consister à projeter la base dans un espace multidimensionnel continu – un espace vectoriel – puisque ces structures sont pour ainsi dire les structures natives sur lesquelles opèrent les réseaux de neurones ; l'inférence va passer d'une représentation logique à une représentation géométrique, en termes d'opérateurs de compositions d'opérateurs et de distance. Entrons un peu dans la technique des mécanismes en jeu.
## 2.1 Apprendre à coder géométriquement une base de données relationnelles

Le modèle relationnel structure, rappelons-le, une base de données comme une collection d'entités<fnref n="7" /> et de relations entre ces entités ; dans « John est né(e) à Miami » John et Miami sont deux entités identifiées, occurrences respectives des classes d'entités « personnes » et « villes », est né(e) à est une relation, la relation « lieu de naissance ». Dans le modèle le plus simple, ces relations sont binaires, si bien que la base de données peut être vue comme un ensemble de triplets<fnref n="8" /> (h, l, t) où h et t sont les entités (head et tail entities), et l (pour label) la relation qui les lie. On peut donc aussi, de manière plus géométrique, voir une telle base de données comme un graphe orienté, dont les nœuds représentent les entités et les types d'arêtes, les relations.

### 2.1.1 Objectif et Principe

Le développement des bases de données de très grandes dimensions (typiquement des centaines de milliers, voire des millions d'entités, des dizaines de milliers de relations) a amené de nombreuses questions impossibles à résoudre manuellement : comme par exemple le repérage de relations erronées ou, à l'inverse, de relations oubliées ; donc vérifier la cohérence de la base, pouvoir la rectifier et la compléter et répondre à des questions malgré erreurs et incomplétudes. Pour ce faire, il faut des algorithmes capables d'analyser sa structure – et d'en détecter des propriétés « cachées ». De nombreux travaux ont été publiés sur de telles recherches ; une des pistes<fnref n="9" /> consiste à projeter la représentation géométrique « discrète », sous forme de graphe, dans un espace continu de relativement faible dimension $E = \mathbb{R}^d$ ; les entités deviennent des points de cet espace et les types de relations deviennent des opérateurs géométriques, en l'occurrence, dans les travaux présentés, des translations.

Dans cette approche, chaque relation *l* se trouve associée à un vecteur *l* définissant une translation dans l'espace continu *E*. Les symboles *h* et *t* désignant respectivement les images dans *E* des entités *h* et *t*, toute paire d'entités (*h*, *t*) liées par une relation *l* devrait vérifier l'équation *t* = *h* + *l* ; et, inversement, toute paire d'entités (*h*, *t*) non liées par la relation *l* devrait vérifier *t* ≠ *h* + *l*. La réalisation exacte d'une projection satisfaisant ces propriétés idéales n'est en général pas possible<fnref n="10" /> mais, la dimension de l'espace continu *E*

<footnote n="7">⁷ Ces entités peuvent représenter des objets concrets du monde réel, comme dans l'exemple « jouet » donné ci-après, mais aussi des concepts, comme par exemple des classes d'objets, etc.</footnote>

<footnote n="8">⁸ Pour reprendre la notation utilisée dans Bordes et al 2015 qui nous sert ici d'article de référence.</footnote>

<footnote n="9">⁹ Sur laquelle nous nous focalisons donc ici, à partir notamment de l'article de Bordes et al 2015.</footnote>

<footnote n="10">¹⁰ Pour des raisons qui peuvent tenir à la structure de la base de données : par exemple, si toutes les personnes qui sont nées à Miami ne sont pas des salariés, il est clair que ces personnes ne peuvent être toutes projetées sur un même point de l'espace *E*, elles peuvent tout au plus former un « cluster » et ce cluster, regroupant les natifs de Miami, sera lui-même séparé en deux sous-groupes, les personnes salariées et celles qui ne le sont pas ; la cardinalité des relations (relations 1-1, 1-n, n-</footnote>
étant judicieusement choisie, on peut s’en approcher. Pour ce faire, une grandeur $\mathcal{L}$ est définie¹¹, une tension mesurant l’écart séparant les propriétés effectives d’une projection donnée (... $h, t \to h, t, ...$) des propriétés idéales. Partant d’une projection initiale déterminée aléatoirement, un algorithme de « descente du gradient » permet de la modifier progressivement en diminuant peu à peu la grandeur $\mathcal{L}$ jusqu’à atteindre un niveau jugé acceptable.

### 2.1.2. Résultats obtenus

L’approche a été conduite sur une version de la base *Wordnet*, de l’ordre de 40.000 entités, puis sur deux sous-ensembles de Freebase¹² ; dans Wordnet, les entités représentent le sens d’un mot, ou de plusieurs mots synonymes, liés par des relations lexicales. Freebase est une base de connaissances collaborative de faits généraux ; une première expérimentation a été menée sur un sous-ensemble de 15.000 entités environ, liées par quelques 1300 relations ; une seconde expérimentation a cherché à tester l’approche sur des volumes nettement plus importants, de l’ordre du million d’entités.

Les résultats sont évalués sur la capacité de la configuration finale des entités dans l'espace $\mathbf{E}$ à prédire correctement les triplets correspondant à des relations vérifiées et ceux qui n'y correspondent pas¹³. Le principe est de classer, en fonction des écarts $d(\mathbf{t}, \mathbf{h} + \mathbf{l})$, chaque triplet ($h, l, t$) présent dans la base de données dans l'ensemble de tous les triplets possibles ($h, l, t'$) ou ($h', l, t$) partageant la relation $l$ et l'une des entités $h$ ou $t$, mais valant contre-exemples, où la relation n'est pas vérifiée. Une bonne configuration finale sera celle où les triplets présents dans la base seront en moyenne classés correctement, par exemple dans le groupe des dix premiers triplets présentant les écarts $d(\mathbf{t}, \mathbf{h} + \mathbf{l})$ les plus faibles. Deux critères précis sont ainsi utilisés pour comparer avec d'autres approches : le rang moyen de classement des triplets de la base, et la proportion de ceux qui sont classés dans le groupe des dix premiers.

1, n-n) est de fait un critère important dans l'évaluation détaillée des performances de ces approches (cf. Bordes et al déjà cité, table 4).

¹¹$\mathcal{L}$ est un bilan des écarts entre **t** et **h** + **l**. Ces écarts $d(\mathbf{t}, \mathbf{h} + \mathbf{l})$– possiblement des distances euclidiennes – sont calculés sur les images dans $\mathbf{E}$ de triplets ($h, l, t$) constituant l'ensemble d'apprentissage. Ces triplets sont des exemples ($h$ et $t$ sont liés par la relation $l$, présents dans la base) ou des contre-exemples ($h$ et $t$ ne sont pas liés par $l$). La valeur de $\mathcal{L}$ sera grande lorsque les écarts mesurés sur les triplets du premier type l'emportent sur ceux du second (cf. Bordes, réf. citée, équation 1).

¹² Fermée par Google en 2015, le contenu étant transféré dans Wikidata.

¹³ Il faut préciser que si l'ajustement de la position des entités dans l'espace $\mathbf{E}$ est effectué sur l'ensemble d'apprentissage, l'évaluation est effectuée sur un ensemble de test, constitué de triplets jamais vus par l'algorithme durant la phase d'apprentissage. On évalue ainsi sa capacité de généralisation, de découverte de liens oubliés, ou inconnus mais qui s'avèrent vérifiés (capacité de link prediction).
Les expérimentations menées par Bordes et al 2015 [1] sur Wordnet et Freebase, ont abouti
à des performances tout à fait encourageantes, notamment par rapport à d'autres méthodes :
par exemple, sur la version de Wordnet comportant quelques 40.000 entités et 5000 triplets
de test, l'expérimentation atteint 89% de triplets bien classés (c.-à-d. classés dans le groupe
de tête des dix premiers), la dimension *k* de l'espace continu *E* étant de 20 ; cette proportion
est encore de 47% sur le sous-ensemble de Freebase comportant de l'ordre de 15.000 entités
mais quelques 60.000 triplets de test, la dimension *k* de l'espace étant cette fois-ci de 50.

## 2.2 Cas particulier de bases de données structurées par une hiérarchie

L'espace continu utilisé dans les projections $(h, l, t) \rightarrow (h, l, t)$ est sous-tendu par une métrique euclidienne, et les images $l$ des relations sont des translations ; on peut légitimement se demander si d'autres options n'aboutiraient pas à de meilleurs résultats, l'option optimale dépendant de la nature des relations et de la structure sous-jacente de la base de données. Des recherches ont donc été menées dans ce sens, notamment pour des bases de données structurées, de façon latente ou explicite, par une hiérarchie ; autrement dit celles dont le graphe associé est un arbre, ou est proche de l'être.

### 2.2.1 Arbres et espaces hyperboliques

On sait qu'un arbre régulier, dont chaque nœud possède le même nombre *b* de descendants immédiats, peut être projeté sur un espace de dimension 2. Dans une telle projection, les *N*(*l*) nœuds de même rang *l* = 1,2,3, ... vont être placés concentriquement autour du sommet de l'arbre <fnref n="14" /> sur un cercle *C*<sub>*l*</sub> ; pour que la densité de la distribution des nœuds demeure constante d'un rang à l'autre, il faut que la circonférence du cercle croisse proportionnellement au nombre de nœuds qu'elle doit contenir et donc, croître, en tendance, de façon exponentielle avec *l* <sup>15</sup>. Or il existe des espaces bidimensionnels qui remplissent cette condition de façon « naturelle » ; ce sont les espaces de courbure constante négative, les espaces hyperboliques. Dans un référentiel où les points d'un tel espace sont repérés par des coordonnées « polaires » *ρ*, *θ* autour d'un point origine choisi arbitrairement, l'ensemble des points de coordonnées *ρ* = *l*, *θ* &lt; 2π forme un cercle *C*<sub>*l*</sub> dont la circonférence est 2π sinh(*l*). Cette circonférence croit donc de façon exponentielle avec *l*, ce qui est bien la propriété recherchée : *les espaces hyperboliques peuvent donc être pensés comme des versions continues d'arbres et vice versa, les arbres peuvent être vus comme des espaces hyperboliques discrets*<sup>16</sup>.

Cette constatation sous-tend les travaux de Maximilian Nickel et Douwe Kiela, du centre de recherche de Facebook, autour, notamment, d'une base de données taxonomiques extraite de Wordnet ; les éléments de cette base de noms projetés sur une représentation

<footnote n="14">14 Le nœud de rang $l = 0$.</footnote>

<footnote n="15">15 Ces propriétés n'exigent pas l'absolue régularité de l'arbre ; en général, le nombre de nœuds reste en relation exponentielle avec la profondeur.</footnote>

<footnote n="16">16 Comme il est dit dans la publication Nickel et Kiela citée en référence.</footnote>
finie<fnref n="17" /> d'un espace hyperbolique, appelée dans la littérature disque de Poincaré en dimension 2, et plus généralement boule ouverte de Poincaré. L'objectif est de reconstruire l'arbre taxonomique complet à partir d'informations partielles du type « le *mustang est un mammifère* » ; ce, par un processus d'apprentissage ; ce processus projette aléatoirement les taxons de la base sur une boule de Poincaré B de faible dimension, puis déplace progressivement leurs images de façon à ce que celles des taxons liés par la relation *est un* soient globalement proches selon la métrique de cet espace de projection.

La méthode est similaire à celle utilisée précédemment ; une fonction $\mathcal{L}(u_1, u_2, ..., u_N)$ évalue la configuration des images dans B des différents taxons $(u_1, u_2, ..., u_N)$ en exprimant une tension entre cette configuration et les relations, de type *est un*, inscrites dans l'ensemble d'apprentissage<fnref n="18" />. Un algorithme de descente du gradient est ensuite appliqué, avec cette fois-ci la particularité mathématique que ce gradient doit être calculé sur un espace non euclidien.

### 2.2.2 Résultats obtenus

La base extraite de WordNet sur laquelle les expérimentations ont été menées comportait quelques 82.000 noms et 740.000 relations (asymétriques) d'hyperonymie ; l'objectif a été de reconstruire la structure hiérarchique<fnref n="19" /> du graphe sous-jacent, à partir de la donnée de tout (Reconstruction) ou partie (Link Prediction) de ces relations ; et par là même, de montrer l'efficacité de la démarche, à l'aide de procédés d'évaluation du même type que ceux mentionnés précédemment. La figure 1 illustre, pour simplifier en dimension 2 (disque de Poincaré), la progression du processus mis en œuvre sur le sous-arbre de la base constitué des seuls mammifères : dans une étape intermédiaire, les images des taxons sur

<footnote n="17">¹⁷ C.-à-d. que les noms de la base taxonomique, les taxons, sont projetés sur des points dont la distance euclidienne à l'origine est strictement inférieure à 1 : donc effectivement restant à l'intérieur d'une « boule ouverte » dont la surface reste hors du domaine de projection. En dimension 2, la transformation passant des coordonnées $\rho, \theta$ de l'espace hyperbolique ($0 \ll \rho < \infty$) aux coordonnées $r, \theta$ sur le disque de Poincaré ($0 \ll r < 1$) est donnée par $r = \frac{\sinh(\rho)}{1+\cosh(\rho)}$, et donc inversement $\rho = \operatorname{Arcosh} \frac{1+r^2}{1-r^2}$. L'expression de l'élément de distance, soit $ds^2 = d\rho^2 + (\sinh \rho)^2 d\theta^2$ dans l'espace hyperbolique, devient ainsi $ds^2 = \left(\frac{2}{1-r^2}\right)^2 [dr^2 + r^2 d\theta^2]$ dans sa représentation par le disque de Poincaré. La distance, dans cette métrique, entre le centre du disque et un point se rapprochant du bord du disque augmente indéfiniment : le disque de Poincaré peut potentiellement recevoir, sa racine étant placée au centre, la projection de tous les nœuds d'un arbre de profondeur infinie.</footnote>

<footnote n="18">¹⁸ D étant cet ensemble, la fonction $\mathcal{L}$ met en rapport la distance $d(u, v)$ de chaque couple de termes $(u, v) \in D$ (qui satisfont donc la relation *est un*, exemples positifs) avec les distances $d(u, v')$ de couples de termes $(u, v') \notin D$, constituant donc des contre-exemples ou exemples négatifs (Voir la formule 6 de l'article cité). La valeur de $\mathcal{L}$ est élevée lorsque les distances associées aux exemples positifs sont grandes et celles associées aux exemples négatifs petites.</footnote>

<footnote n="19">¹⁹ En termes mathématiques, assurer la clôture transitive de cet ensemble de relations.</footnote>
le disque de Poincaré forment encore une configuration assez confuse, avec plusieurs noms d'espèces – tel que « écureuil » – encore placés au centre du disque.

La configuration finale obtenue à l'issue de processus fait au contraire clairement apparaitre la structure hiérarchique, avec le taxon de rang le plus élevé. « mammifères » près du centre, et les noms des différentes espèces – les feuilles de l'arbre – réparties quasi uniformément à proximité de la circonférence du disque.

D'autres expérimentations ont été menées dans des contextes différents, expérimentations qui ont montré également l'avantage d'une projection sur une boule de Poincaré par rapport à une projection sur un espace euclidien ; ainsi en a-t-il été dans la prédiction de liens dans certains réseaux sociaux (par exemple de collaboration entre scientifiques) dont on pense qu'ils sont en partie structurés par une hiérarchie latente. De même dans le traitement de réseaux sémantiques, dont les liens représentent des *assertions graduées*, c'est-à-dire affectées d'une valeur de vraisemblance, d'un degré de certitude.

### 3. Réseaux de mémoire

* John dropped the Milk
* John took the Milk there
* Sandra went to the bathroom
* John moved to the hallway
* Mary went to the bedroom
* Where is the Milk ?

Comme suggéré dans l'introduction de ce chapitre, il est difficile de doter une machine de la capacité à *comprendre* un texte, dans l'acceptation suivante : être à même *d'inférer* la réponse correcte à une question à partir des faits énoncés dans ce même texte. Cette difficulté se manifeste même lorsque ce texte raconte une histoire très simple, comme par exemple l'histoire donnée dans l'encadré ci-contre<fnref n="20" />, et que la question porte sur un fait

pourtant très vite inféré par un être humain. Pour réaliser de telles tâches<fnref n="21" />, on a pu penser qu'une approche d'apprentissage profond classique pourrait être une voie suffisante, en s'appuyant sur la fourniture d'un ensemble d'apprentissage composé d'un grand nombre de ces petites histoires très courtes, des questions et réponses associées. Or il n'en a rien été ou plus exactement le taux de réussite, environ d'un cinquième dans de premières tentatives, s'avérait insatisfaisant.

<footnote n="20">²⁰ Extrait de Sainbayar Sukhbaatar et al. 2015 [3].</footnote>

<footnote n="21">²¹ En fait, une vingtaine de catégories de tâches ont été identifiées pour comparer différents algorithmes proposés par la communauté (cf. J. Weston, A. Bordes et al 2015, *Towards AI-Complete Question Answering: A set of Prerequisite Toy Tasks* [5]). Ces catégories se différencient par exemple par le nombre de faits (*supporting facts*) ou par le nombre d'arguments dont le raisonnement doit tenir compte, ou encore par la prise en compte de notions temporelles, spatiales, etc.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1a : étape intermédiaire</figcaption></figure>

**Figure 1** Progression de l'apprentissage projetant la taxonomie des mammifères sur le disque de Poincaré, pour en refléter la structure hiérarchique. Image extraite de Maximilan Nickel et Douwe Kiela 2017 [8]
<figure><img src="image_3.png" /><figcaption>Figure 1b : étape finale</figcaption></figure>
## 3.1 Principes

Ces premières tentatives ont conduit à la conclusion qu'il manquait une mémoire à court terme, capable de stocker les éléments pertinents pour la réalisation de la tâche. On s'est alors orienté vers des algorithmes capables d'apprendre simultanément, pour ainsi dire au sein d'un même processus, la manière d'encoder dans cette mémoire à court terme ce que racontent les textes et les questions posées, d'élaborer et d'encoder des éléments intermédiaires de raisonnement et enfin d'inférer les réponses. Telle est l'idée à la base des réseaux de mémoire<fnref n="22" /> ; de nombreuses publications leur ont été consacrées, nous allons dans un premier temps, pour donner au lecteur un exemple de tels processus, reprendre l'une d'entre elles, celle de S. Sukhbaatar & al. 2015, *End-To-End Memory Networks* [3], avec application à la compréhension d'histoires simples. Dans un second temps, nous décrirons brièvement l'application des mêmes principes algorithmiques à des applications visant à répondre à des questions posées à de grandes bases de données et de grandes bases de textes.

## 3.2 Répondre à des questions sur des histoires simples

La recherche d'une réponse à une question du type *Where is the Milk ?* dans l'exemple de l'encadré passe intuitivement par la recherche en mémoire des énoncés qui paraissent le plus en rapport, à travers les termes mis en œuvre, avec la question posée. Une recherche itérative : on commence par retenir un premier énoncé, qui pourra être *John took the milk there*, puis la combinaison de son contenu et de celui de la question initiale sert de base à une seconde recherche, qui sélectionnera par exemple *John moved to the hallway*. C'est bien ce type de démarche itérative qui est mise en œuvre dans les algorithmes ; l'originalité réside dans la manière dont sont codés les énoncés, la question posée, les contenus intermédiaires et la réponse à fournir ; elle réside aussi dans la manière dont s'effectue les rapprochements de contenu dont il vient d'être question. Tous les calculs s'effectuent en effet dans un espace de représentations internes particulières dont on pourrait dire, dans la mesure où elles permettent à l'algorithme de fournir des réponses correctes, que d'une certaine manière elles capturent le sens des énoncés.

Dans la publication citée en référence, l'idée est d'inscrire ces représentations internes dans un espace vectoriel d'une certaine dimension *d* ; puis d'effectuer les rapprochements par la mesure de relations entre différents vecteurs ; on retrouve ainsi le parti pris géométrique utilisé pour raisonner sur les bases de données. La transformation d'un énoncé en sa représentation interne s'effectue en deux étapes : une première étape code d'une manière simple et déterminée par le concepteur, l'énoncé dans un premier espace vectoriel de

<footnote n="22">²² Le lecteur pourra trouver dans J.Weston, S.Chopra & A. Bordes 2015, *Memory Networks* [4], une description algorithmique générale du fonctionnement de ces réseaux de mémoire.</footnote>
grande dimension $V^{23}$ ; une seconde étape applique une matrice $A$ de $d$ lignes et $V$ colonnes, (avec $d \ll V$) pour projeter cette première représentation dans la représentation interne finale désirée ; mais, cette fois-ci, les coefficients de $A$ et ceux d'autres matrices $B$, $C$ du même type, ainsi que ceux de la matrice de « sortie » $W$ de dimension $V \times d^{24}$ ne sont pas fixés par le concepteur : ils vont être déterminés par apprentissage.

Très schématiquement, l'algorithme d'élaboration de la réponse comporte une succession d'étapes (hops ou layers) indicées par $k = 1, 2, 3...$ où interviennent les opérations suivantes :

* Mise en mémoire d'une première série (inputs) de représentations internes $m_i$, des différents énoncés $x_1, ..., x_i, ..., x_n$ de l'histoire :

$$m_i = A^k x_i$$

* Mise en mémoire d'une seconde série (outputs) de représentations internes $c_i$, issues des différents énoncés $x_1, ..., x_i, ..., x_n$ de l'histoire, qui vont servir directement, à cette étape, à l'élaboration de la réponse :

$$c_i = C^k x_i$$

* Appariement de ce qu'on peut appeler l'état de la réponse à cette étape de l'itération, savoir un vecteur $u^k$, avec les différents représentations internes $m_i$, pour apprécier leur pertinence, à cette étape, dans l'élaboration de la réponse finale ; cette pertinence est codée, pour chaque $m_i$, par une probabilité $p_i^{25}$.

* Élaboration, à partir de l'état de la réponse $u^k$, des vecteurs $c_i$ et de leur poids de pertinence $p_i$, d'un nouvel état de la réponse $u^{k+1}$, utilisable à l'étape suivante.

Dans la première étape, le vecteur $u^1 = Bq$ est simplement la représentation interne de la question ; lorsque la dernière étape est atteinte$^{26}$, $u^{k+1}$ est la représentation interne de la réponse $r = Wu^{k+1}$.

L'apprentissage s'effectue à partir de la donnée d'un grand nombre$^{27}$ de triplets histoires, questions, réponses fournies ; il s'agit donc d'un apprentissage faiblement supervisé : les énoncés marquants, déterminants pour la réponse à la question – les supporting facts – ne

<footnote>$^{23}$ Le codage le plus simple – qui ne tient pas compte de l'ordre des mots – transcrit l'énoncé dans un espace dont la dimension est la taille du vocabulaire, chaque mot de ce vocabulaire étant associé à une composante de ce vecteur ; une valeur 1 d'une composante de ce vecteur signalant que le terme associé est présent dans l'énoncé (méthode identifiée sous l'expression *bag-of-words*).</footnote>

<footnote>$^{24}$ Transformant la représentation interne de la réponse à son énoncé en mots du vocabulaire.</footnote>

<footnote>$^{25}$ Une manière de faire cet appariement est d'effectuer le produit scalaire $m_i \cdot u^k$ (dans l'espace vectoriel des représentations internes, de dimension $d$).</footnote>

<footnote>$^{26}$ Avec, par exemple, $k = 3$, modèle à trois étapes ou couches.</footnote>

<footnote>$^{27}$ Typiquement 1000 ou 10.000 exemples.</footnote>
sont nullement indiqués comme tels durant la phase d'apprentissage<fnref n="28" />. Cet apprentissage opère par descente du gradient dans l'espace des paramètres, en ajustant progressivement les coefficients des matrices $A^k, C^k, ..., k = 1, 2, 3, ...,$ applicables aux différentes étapes ainsi qu'aux matrices $B$ et $W$. Pour réduire la dimension de cet espace, certaines contraintes sont posées sur ces matrices ; par exemple $A^{k+1} = C^k$ : les outputs $c_i$ d'une étape (éléments retenus pour le calcul du nouvel état de la réponse à cette étape) seront les inputs $m_i$ de l'étape suivante ; ou encore, plus drastiquement, les matrices $A$ et $C$ ne varient pas d'une étape à l'autre.

Les publications faites sur ces travaux analysent systématiquement leurs performances en fonction de différentes options possibles sur l'algorithme présenté, en fonction également des performances atteintes par d'autres approches. La publication de S. Sukhbaatar 2015 commentée ici donne ainsi une idée des résultats atteints<fnref n="29" /> : retenons ici qu'avec la meilleure option, dans un apprentissage sur 10.000 exemples effectué indépendamment pour chacune des 20 catégories de tâches, le taux d'erreur dans les réponses apportées est en moyenne sur l'ensemble des catégories de 6,6%, ce taux excédant 5% seulement dans 4 catégories. Ces résultats s'avéraient à l'époque nettement supérieurs à ceux d'autres travaux, excepté l'un d'eux utilisant un apprentissage fortement supervisé. Récemment (2017) des approches similaires (EntNets, Query-reduction Networks) ont réussi à résoudre correctement l'ensemble des 20 catégories.

## 3.3 Répondre à des questions sur de grandes bases de données ou de textes

La recherche d'une réponse à une question portant sur des histoires simples composées d'une dizaine ou d'une centaine de phrases est le prélude à la réalisation d'ambitions plus vastes : pouvoir interroger en « langage naturel » de grandes bases de connaissances, comportant des millions d'éléments, et obtenir des réponses pertinentes.

Que ces bases de connaissances soient structurées en bases de données (ensembles de triplets entités-relation **h, l, t**) ou simplement constituées par un ensemble de textes, le schéma d'élaboration de la réponse est le même et se déploie en deux étapes : une première étape de filtrage rassemble, à partir des mots de la question – un relativement petit nombre d'éléments d'information – de triplets entités-relation ou de phrases de textes et les insère dans la mémoire du réseau. Une seconde étape utilise des méthodes inspirées de celles que nous avons vues précédemment pour construire la réponse.

S'agissant des bases de données relationnelles, on pourrait penser que le problème est simple : un utilisateur connaissant la structure de la base et le langage d'interrogation SQL<fnref n="30" />

<footnote n="28">²⁸ Contrairement à l'apprentissage fortement supervisé, appliqué par certains algorithmes, où l'on indique à chaque étape l'énoncé – le *supporting fact* – qui doit être utilisé.</footnote>

<footnote n="29">²⁹ Table 1 de la publication.</footnote>

<footnote n="30">³⁰ Structured Query Language.</footnote>
Des tests de performances ont été réalisés, en expérimentant différents types de partage des éléments d'information entre *Key* et *Value*, et ce sur trois contextes : sur une base de données créée à partir d'une documentation de base par des opérateurs humains, sur une base de données générée automatiquement à partir de la même documentation<fnref n="35" /> et enfin directement sur cette documentation de base, constituée d'un ensemble d'articles de Wikipédia dans le domaine cinématographique. Treize catégories de questions ont été mobilisées pour ces tests. L'ensemble d'apprentissage a comporté de l'ordre de 100.000 couples questions-réponses. Les meilleures performances ont été atteintes sur le premier contexte – base de données construite par des opérateurs humains, avec un taux de bonne réponse de 93,9%. Viennent ensuite celles obtenues sur le troisième contexte opérant directement sur les articles Wikipédia, avec 76,2% de réussite, et descendent à 68,3% dans le cas d'une base de données construite automatiquement. Ces performances que Miller et al analysent en détail par type de question sont tout à fait intéressantes lorsqu'on les compare à d'autres méthodes appliquées sur les mêmes contextes.

## 4. Conclusion

La compréhension du langage par les machines fait des progrès rapides dus à la combinaison de méthodes capables d'apprendre sur de grandes quantités de données avec des modèles et des concepts venant de l'Intelligence Artificielle symbolique. Néanmoins, il reste encore de multiples étapes à franchir, de multiples verrous scientifiques à lever, avant de pouvoir converser avec une machine comme on le fait avec un humain. En effet, nos conversations s'appuient toutes sur le socle de notre connaissance commune, que l'on appelle le sens commun, qui informe nos paroles et les ancrent dans le monde physique, philosophique et sociologique. Pour l'instant, ce sens commun est inatteignable par les machines. Comment le sens commun peut-il être encodé dans un programme ? Doit-il être précodé ou appris à partir d'expériences ? Les recherches sur de telles questions sont encore aujourd'hui très préliminaires et recèlent encore de nombreuses inconnues.

<footnote n="35">³⁵ Le principe de cette génération automatique étant d'exploiter les regroupements sujet-verbe-objet.</footnote>
Key-Value Memory Networks on KB

<figure><img src="image_4.png" /><figcaption>**Figure 2** illustrant les deux étapes de la recherche de la réponse à une simple question sur une base de données cinématographique ; image construite par A. Bordes à partir de Bordes et al 2015 [2] et Miller et al. 2016 [6].</figcaption></figure>
Key-Value Memory Networks on Text

<figure><img src="image_5.png" /><figcaption>**Figure 3** illustrant les deux étapes de la recherche de la réponse à une simple question sur une base de texte (Wikipédia) ; image construite par A. Bordes à partir de Bordes et al 2015 [2] et Miller et al. 2016 [6].</figcaption></figure>
Références

[1] Antoine Bordes, Nicolas Usumier, Alberto Garcia-Duran, Jason Weston. Translating Embeddings for Modeling Multi-relational Data, *Advances in Neural Information Processing Systems* 26 (NIPS 2013).

[2] Antoines Bordes, Nicolas Usumier, Sumit Chopra, Jason Weston. Large-scale Simple Question Answering with Memory Networks, arXiv 5 Jun 2015.

[3] Sainbayar Sukhbaatar, Arthur Szlam, James Weston, Rob Fergas. End-to-End Memory Networks, arXiv 24 nov 2015, *Advances in Neural Information Processing Systems* 28 (NIPS 2015).

[4] Jason Weston, Sumit Chopra, Antoine Bordes. Memory Networks, arXiv 29 Nov 2015, *conference paper at ICLR 2015*.

[5] Jason Weston, Antoine Bordes, Sumit Chopra, Alexander Rush, Bart van Merriënboer, Armand Joulin, Tomas Mikolof. Toward AI-Compete Question Answering ; a Set of Prerequisite Toy Tasks. arXiv 31 Dec 2015.

[6] Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, Jason Weston. Key-Value Memory Networks for Directly Reading Documents, arXiv 10 Oct 2016.

[7] Danqi Chen, Adam Fisch, Jason Weston, Antoine Bordes. Reading Wikipedia to Answer Open-Domain Questions. arXiv 28 Apr 2017.

[8] Maximilian Nickel, Douwe Kiela. Poincaré Embeddings for Learning Hierarchical Representations. arXiv 20 May 2017.
<figure><img src="image_6.png" /></figure>