• Chapitre 1 : De l’algorithme à la solution : un exemple d’exploitation d’un algorithme d’intelligence artificielle : INTRODUCTION
• Chapitre 2 : De l’algorithme à la solution : un exemple d’exploitation d’un algorithme d’intelligence artificielle : les modèles de langage
• Chapitre 3 : De l’algorithme à la solution : un exemple d’exploitation d’un algorithme d’intelligence artificielle : la proximité sémantique dans le modèle de langage
• Chapitre 4 : De l’algorithme à la solution : un exemple d’exploitation d’un algorithme d’intelligence artificielle : Construire une solution de recherche sémantique avec un modèle de plongement de texte

Mes voisins sont des chics types!

Titre énigmatique s’il en est. Nous allons voir dans ce dernier article de la série comment améliorer la solution que nous avons construite.

Pour rappel, voilà où nous en sommes :

Nous avons bâti une solution permettant d’effectuer dans un corpus de texte des recherches textuelles capables d’aller “au-delà des mots” en prenant en compte une “compréhension” sémantique du texte basée sur une représentation géométrique issue d’un algorithme de “plongement de texte”. Cette solution se base entre autres sur la technologie Elasticsearch qui est en mesure de prendre en compte ces représentations géométriques. Cependant, nous avons rencontré une limitation à notre approche : plus notre corpus est volumineux, plus les recherches sont longues, car nous devons parcourir la totalité du corpus pour chaque requête effectuée.

C’est ce point particulier que nous allons chercher à améliorer. Parmi l’ensemble des documents du corpus, nous allons chercher à ne retenir, par un moyen “performant”, que ceux qui seront susceptibles de nous intéresser.

Pour ce faire, nous allons utiliser le caractère géométrique de la représentation du texte que nous fournit l’algorithme de plongement de texte. Nous avons vu en détail ces propriétés dans la troisième partie de cette série. Pour rappel, chaque texte est encodé par un vecteur de grande dimension, chaque coordonnée de ce vecteur indique le poids relatif d’un “concept abstrait”. Si deux textes similaires ont leurs vecteurs associés qui ont un angle faible entre eux, alors ils sont sémantiquement proches. Ainsi, nous allons rechercher pour une requête donnée les textes dont les vecteurs sont dans le voisinage du vecteur qui représente la requête.

Notre recherche de textes similaires se ramène donc à une recherche de plus proches voisins.

Il existe de nombreux algorithmes permettant la recherche de plus proches voisins :

• L’approche par force brute (parcours de tous les éléments) est exclue dans notre contexte : elle correspondant à la solution que nous cherchons justement à améliorer.
• Une autre approche (kd-trees : https://fr.wikipedia.org/wiki/Arbre_kd ) se base sur des partitionnements successifs de l’espace, mais elle n’est performante que pour des espaces de dimension faible (< 15), ce qui la rend non pertinente dans notre cas (notre espace est de dimension 512). 

L’approche que nous allons utiliser se base sur l’algorithme LSH (Local Sensitivity Hashing) car elle est adaptée aux espaces de grandes dimensions.

Local Sensitivity Hashing : comment ça marche ?

Disclaimer : faire des représentations compréhensibles pour un espace à 512 dimensions est un défi que nous ne relèverons pas 😉 Dans ce qui suit, nous allons nous contenter d’expliquer l’algorithme dans un espace à 2 dimensions.

L’approche est de type “diviser pour mieux régner”. L’idée maîtresse est la suivante : l’espace est subdivisé en plusieurs régions et chaque région est identifiée par un nombre (le hash). Autrement dit, tous les éléments d’une même région de l’espace auront le même hash. Vous pouvez également vous représenter cette structure de données comme une table de hachage géométrique, si tant est que ce concept vous est familier.

Si on se rattache à la métaphore des voisins, on va s’intéresser à la population du quartier dans lequel on est tombé. Le nombre (hash) dont on parle est l’”adresse” du quartier.

Maintenant rentrons dans le vif du sujet pour découvrir comment ce hash est calculé :

Un ensemble de droites données partitionne l’espace. Chaque droite possède son propre index. Considérons un vecteur, situé entre les droites d’indice 2 et 5. Pour caractériser ce vecteur par rapport aux droites, on peut qualifier sa position (droite ou gauche) par rapport à chaque droite. Dans le cas présent, on obtient :

On a deux valeurs possibles : droite ou gauche. Si on choisit de les traduire par un nombre binaire 0 ou 1, alors on obtient ceci :

Vous voyez venir la suite non ? Cette succession de 0 et de 1 nous permet de construire un nombre, ici 17 (1×2⁴ + 0x2³ + 0x2² + 0x2¹ +1×2⁰  = 16+0+0+0+1), qui caractérise le vecteur, ainsi que tous les vecteurs qui “tombent” dans la même partition. Ce nombre est le hash “local” associé à cette partition.

L’illustration suivante nous donne le calcul des hash de chaque partition de l’espace.

A titre d’exemple, on peut vérifier pour la partition dont le hash est 27, entre les droites d’indice 3 et 4.

On trouve le nombre binaire 11011 qui correspond au nombre entier 27 = 16 +8 +0 +2 +1

Ainsi tout vecteur dont le hash est 27 “regarde” dans une direction comprise entre les droites d’indice 3 et 4.

D’un point de vue personnel, je trouve cet algorithme tout simplement génial : 

• il est simple à comprendre
• il est élégant
• il est efficace 

Ah oui, aussi : il résout notre problème :-p 

Vraiment ? Pas si vite…

On voit rapidement une limite à notre approche dans son état actuel : on peut facilement ignorer des voisins. Dans la figure suivante, on se rend compte que, si le vecteur correspondant à notre recherche est proche d’une frontière (ici la frontière 2), on va trouver ses voisins dans la partition 1. Par contre on va tout bonnement ignorer les voisins présents dans la partition 2.

Si la solution que vous mettez en œuvre peut se contenter de ce genre d’approximation, alors on peut en rester là.

Cependant, il y a fort à parier que vos utilisateurs seront plus exigeants. Il y a plusieurs stratégies possibles pour résoudre ce problème:

• trouver les partitions voisines : une ouverture des frontières en quelque sorte, autrement dit aller chercher les voisins du / des quartiers d’à côté.
• se baser sur plusieurs partitionnements distincts.

Pas de quartier !

En fait non ! Plus de quartier ! Heu… c’est peut-être un peu obscur là, alors on va s’expliquer. 

Ce qui nous intéresse ici, c’est de trouver pour un quartier donné, les quartiers adjacents.

Or, en regardant la figure précédente, si le quartier 1 est à gauche de la frontière 2, le quartier adjacent est à sa droite. Autrement dit, le bit associé à cette frontière passe de 1 à 0 (ou l’inverse) lorsqu’on la franchit.

Pour s’en convaincre, vérifions : 

• le quartier 1 a pour hash 25 soit 11001
• le quartier 2 a pour hash 17 soit 10001

le bit associé à la 2ème frontière est inversé.

Et voilà ! on a le moyen d’aller visiter les quartiers d’à côté ! Pour cette technique, appelée bit flipping, il suffit d’inverser un à un les bits du hash qu’on a trouvé. Diaboliquement simple non ?

D’autres quartiers ?

Jusqu’à présent nous avons utilisé un partitionnement particulier pour classer nos vecteurs. Pourquoi ne pas en utiliser un autre, voire des autres ? Comme le montre la figure suivante, on se rend compte que la superposition de plusieurs partitions va nous permettre de trouver plus de voisins à un vecteur de requêtes donné.

En effet, les différentes partitions ont des quartiers qui “voient” des populations différentes et permettent ainsi d’obtenir pour un vecteur de requête donné plus de voisins. Cette approche permet de contrecarrer le problème des voisins que l’on ne voit pas parce qu’ils sont de l’autre côté d’une frontière.

La recherche du voisinage d’un vecteur de requête revient ainsi à rechercher les vecteurs qui sont dans l’un ou l’autre des quartiers associés à chaque partitionnement. En utilisant LSH, cette recherche revient à retourner les vecteurs qui ont le même nombre LSH du vecteur requête selon le partitionnement 1 OU qui ont le même nombre LSH selon le partitionnement 2.

Ici aussi, on aboutit à une implémentation simple : un “ou logique” nous permet d’élargir la recherche de voisinage afin d’obtenir un résultat plus pertinent.

Derniers obstacles

Il y a encore quelques points à éclaircir :

• Gauche/droite, ça veut dire quoi dans notre espace à 512 dimensions ?
• Comment déterminer le partitionnement de l’espace ?
• Combien faut-il de frontières dans un partitionnement
• Choisir entre la technique de bit flipping et le multi-partitionnement
• Pour le multi-partitionnement, combien de partitions faut-il utiliser ?

Droite ou gauche dans un espace de grande dimension. 

Là encore, la représentation en 2 dimensions va nous aider. Concrètement, en 2D comment affirmer qu’un vecteur est à gauche ou à droite d’une frontière ?

Pour ceux qui ont des souvenirs de maths de lycée, voici comment on répond à cette question : on considère le vecteur normal (perpendiculaire) à la frontière et on effectue le “produit scalaire¹” avec le vecteur à caractériser. Si le résultat est positif, le vecteur est à gauche, sinon il est à droite.

Cette approche se généralise à un espace de dimension quelconque où l’équivalent des droites en 2D s’appelle des hyperplans. Pour conserver une analogie, on a transformé “à gauche/droite” d’une droite en “dessus/dessous” d’un hyperplan.

Partitionner un espace de grande dimension. 

Jusqu’à présent, pour faciliter la compréhension, on s’est appuyé sur une représentation en deux dimensions de l’espace. Dans ce contexte, partitionner l’espace est aisé : si, par exemple, on désire partitionner l’espace avec “K” frontières, on peut choisir “K” droites espacées chacune de 360/K degrés. (par exemple 0°, 90°,180°,270° si on désire 4 frontières).

Or l’espace qu’on va manipuler est de dimension 512 : la notion d’angle n’y est plus du tout évidente ! La solution pourra paraître brutale à certains : on va partitionner de manière aléatoire. Ainsi, si on désire obtenir “K” frontières, il nous suffira de choisir “K” vecteurs aléatoires à l’aide d’une distribution uniforme².

Combien de frontières?

Il nous faut choisir le nombre “K” de frontières qui vont définir un partitionnement. Chaque frontière coupant l’espace en 2, on aura au maximum 2^K quartiers possibles. Ainsi 10 frontières nous permettent de définir 2¹⁰=1024 quartiers. En première approximation, on peut faire l’hypothèse que les vecteurs représentant les textes du corpus se répartissent uniformément dans ces quartiers. Ainsi, avec un corpus de 1 million de points et 10 frontières, on peut estimer qu’en gros, chaque quartier contient à peu près 1 millier de vecteurs (≈ 1 million/1024), ce qui donne l’ordre de grandeur du nombre de vecteurs qui seront examinés pour scorer les textes éligibles du corpus vis-à-vis du texte de la requête. Certes c’est une amélioration significative par rapport à l’examen de tous les vecteurs, mais cela se fait au prix d’une perte de précision (on risque de “louper” des textes).

On retient donc qu’augmenter le nombre de frontières:

• améliore les performances
• diminue la précision

Améliorer la précision

On a vu deux stratégies possibles pour améliorer la précision : 

• inversion de bits 
• utilisation de plusieurs partitions

D’un point de vue théorique, il est démontré que l’approche avec plusieurs partitions est plus efficace³. Cependant, cette approche requiert plus de ressources tant d’un point de vue calcul que d’un point de vue stockage.

On ne peut pas donner une recommandation claire à part celle-ci : pour trouver la bonne stratégie, il vous faudra expérimenter pour trouver le compromis adapté à votre cas d’utilisation et vos données.

Récapitulons !

Pour terminer et résumer cette série d’articles, on va récapituler ce que nous avons vu. Le schéma qui suit donne une vue synoptique du processus mis en œuvre.

Revenons à l’objectif : créer un moteur de recherche qui soit capable d’aller “plus loin que les mots”, c’est-à-dire pouvant se baser sur les concepts contenus dans la requête de l’utilisateur. Point bonus, si notre moteur de recherche peut prendre en compte plusieurs langues c’est encore mieux. 

Les techniques récentes de traitement du langage naturel permettent de modéliser les concepts contenus dans du texte. Un texte est ainsi vu comme une combinaison de concepts. Dans cette représentation, pour un texte donné, chaque concept a un “poids” spécifique. Nous avons à notre disposition un algorithme, l’Universal Sentence Encoder Multilingual qui nous donne une telle représentation. À un texte, il associe un vecteur de dimension 512 ou chaque coordonnée représente le poids d’un concept abstrait.

Cette représentation vectorielle nous permet de caractériser la proximité sémantique de deux textes en utilisant la notion géométrique de similarité entre vecteurs.

Le moteur de recherche Elasticsearch nous offre la possibilité de manipuler dans une même structure de donnée (un index) du texte et des vecteurs et propose des fonctionnalités de calcul de similarité entre vecteurs. Ainsi, nous pouvons, pour une requête textuelle donnée, trouver, parmi tous les textes présents dans le moteur de recherche, les textes qui ont la similarité la plus grande vis-à-vis de la requête.

Une première implémentation nous a permis de concevoir une solution fonctionnelle. Cependant, cette solution n’est pas performante car elle impose de parcourir l’entièreté du corpus de documents présents dans le moteur de recherche.

Nous avons donc cherché à améliorer la performance en ne retenant pour le calcul de similarité que les plus proches voisins par rapport à la représentation vectorielle du texte de la requête. Pour ce faire, nous avons introduit l’approche LSH qui permet d’identifier, via un nombre entier, la région de l’espace à laquelle appartient un vecteur.

Nous avons vu que cette méthode permet de diminuer très significativement la charge de calcul nécessaire, mais au prix d’une perte de précision (on risque de ne pas trouver tous les plus proches voisins).

Il y a plusieurs paramètres sur lesquels on peut jouer pour faire les compromis acceptables en regard des contraintes liées à votre cas d’utilisation: la mise au point de ces paramètres vous demandera un effort d’expérimentation. “À vous de jouer”!

Et le code dans tout ça ?

Dans le cadre de cet article, rentrer dans les détails d’implémentation serait rapidement soporifique et indigeste. Une proposition d’implémentation est disponible ici sur Github: https://github.com/Zenika/elasticsearch-semantic-search. Le fichier README vous fournira les indications nécessaires pour rentrer dans le code.

Remerciements

Je remercie très chaleureusement mes collègues Jeanne Marcadé, Cynthia Staebler, Laurent Tardif, Benoit Lutringer et Guillaume Faccini pour leur aide lors de la rédaction de cette série d’articles.

(1) Pour aller plus loin, le produit scalaire est la somme des produits 2 à deux des coordonnées des 2 vecteurs.
(2) Une distribution uniforme signifie que la probabilité qu’un nombre d’un intervalle donné soit choisi est la même pour tous les nombres de cet intervalle.
(3) Une démonstration, assez technique, est proposée dans cette vidéo: https://www.coursera.org/lecture/ml-clustering-and-retrieval/optional-improving-efficiency-through-multiple-tables-aZCHX.