Comment fonctionne un moteur de recherche ? (4ème partie : l’analyse de la pertinence)

Il est important de bien comprendre ce que nous appelons un terme. A l’origine il s’agissait d’un mot, mais avec les années et la puissance de stockage et de calcul toujours plus importante à disposition, les moteurs se sont mis à utiliser des blocs de plusieurs mots consécutifs, les n-grams, pour récupérer l’information perdue par l’utilisation de l’approche “sac-de-mots” (voir plus loin). Au final, l’espace vectoriel utilisé est donc de taille extrêmement importante.

Pour construire le vecteur associé à un texte, le moteur va effectuer plusieurs opérations différentes qui ont pour but de simplifier les structures de données internes et d’alléger l’espace mémoire utilisé pour l’analyse.

La première opération est de transformer le texte en un sac-de-mots. Il s’agit tout simplement de déconstruire les phrases. Le moteur n’étant en effet pas capable de comprendre la grammaire, il ne lui sert à rien de conserver l’information liée à la place des mots les uns par rapport aux autres. La Figure 1 illustre la notion de sac-de-mots pour un texte de deux phrases et montre le sac-de-mots associé (dans l’ellipse en pointillées).

Fig. 1. La notion de sac de mots.

On peut remarquer que dans les mots qui restent, certains ne sont pas utiles ou significatifs. En effet, pour comprendre le sens d’un texte, on utilise (c’est intuitif) d’abord les mots qui ne sont pas très fréquents dans la langue, car les plus fréquents étant présents partout, ils ne sont pas particulièrements porteurs de sens. C’est ainsi qu’on va pouvoir faire disparaître les articles, les verbes “universels” (être et avoir notamment). Par ailleurs on va aussi pouvoir utiliser une représentation unique pour toutes les formes d’un “même” mot (par exemple en fusionnant pluriel et singulier pour les noms, masculin et féminin pour les adjectifs, etc.). En effet, comme l’approche sac-de-mots fait perdre l’information de proximité entre les mots, la plupart des informations de ce type deviennent inutiles.

La figure 2 illustre ce qu’il reste du texte d’origine une fois qu’on a opéré toutes ces tâches, qu’on regroupe sous le nom de lemmatisation.

Fig. 2. Résultat de la lemmatisation et de l'élimination des mots inutiles.

Une fois qu’on a effectué la lemmatisation, on peut enfin construire le vecteur. Chaque document sera donc caractérisé par un vecteur ayant autant de composantes qu’il existe de dimensions, c’est-à-dire de mots différents dans l’index. La valeur d’une composante pour un terme donné d’un document est appelée le poids du terme dans le document.

Lorsqu’un document ne contient pas un terme, le poids du terme est zéro. Dans tous les autres cas, il y aura une valeur numérique non nulle.

Les types de poids les plus simples sont très naïfs : on peut noter 1 lorsque le terme est présent, (c’est ce que l’on appelle le modèle booléen) ; on peut indiquer la fréquence d’apparition du terme, ou encore le nombre d'occurrences du terme. Mais ces poids ne donnent pas de très bons résultats en matière de compréhension des documents. Notamment car ce sont des notions des poids bien trop faciles à manipuler pour la personne ayant écrit un document, voire même l’ayant mis en ligne sur Internet.

C’est Salton qui a défini la fonction de poids qui a été utilisé ensuite pendant des décennies : la TF-IDF. La TF-IDF est une mesure qui embarque de l’information locale (la TF) et de l’information globale (l’IDF).

La TF est la Term Frequency, c’est-à-dire la fréquence d’apparition du terme dans le document. Cette fréquence est le nombre d’apparition du terme étudié, divisé par le nombre d’apparitions du terme le plus courant du document. On notera que ce n’est pas la définition intuitive de la fréquence (pour cela, il faudrait diviser par le nombre total de mots du document). Cette différence a pour but de rendre la mesure indifférente à la taille du document (sinon les documents plus petits seraient favorisés par le moteur dans le classement).

L’IDF est l’Inverse Document Frequency, c’est-à-dire une quantité qui va donner plus de poids à des mots qui sont rares dans le corpus documentaire (l’index). C’est là la grande idée de Salton : plus un mot est rare, plus il va apporter de la compréhension au sens du document, et donc plus il faut lui donner de poids dans le vecteur correspondant au document.

Il existe de nombreuses formules différentes pour l’IDF, mais la plupart sont basées sur le logarithme du rapport entre le nombre de documents dans l’index et le nombre de documents de l’index qui contiennent le terme étudié.
Au final, la valeur de la TF-IDF pour un terme dans un document est littéralement la multiplication de la TF et de l’IDF du terme dans le document.

Raisonnons sur un exemple intuitif, avec les deux textes suivants et avec des poids définis uniquement par la fréquence intuitive :
Texte 1 : la loutre est dans la rivière
Texte 2 : la loutre est avec les loutres dans la rivière

On commence par lemmatiser les textes (ici on ne prend pas en compte les verbes) :
Texte 1 : loutre, rivière
Texte 2 : loutre, loutre, rivière

On peut ensuite représenter chacun de ces textes par un vecteur dans l'espace des fréquences des mots rivière, loutre (dans cet ordre).
Texte 1 : (1/2, 1/2 )
Texte 2 : (1/3, 2/3)

Ce qui donne graphiquement ce que l’on observe sur la figure 3.

Fig. 3. Exemple de vecteurs.

 

Le cosinus de Salton pour déterminer la pertinence

On remarquera qu'une requête est aussi un document, un texte, même si la plupart du temps il est plus court qu'un texte classique. Pour voir quelle est la page (= le texte) le plus pertinent pour une requête, on va regarder (graphiquement en quelque sorte) quel est le vecteur (d'un texte) qui est le plus proche du vecteur de la requête. Cette proximité se mesure à l'aide d'une mesure de similarité.

L’une des premières mesures a été proposé dans le cadre du projet SMART, et porte le nom de Salton, c’est le fameux cosinus de Salton.

Pour déterminer quel est le document le plus pertinent pour une requête, on va choisir le texte qui correspond au vecteur qui forme le plus petit angle avec le vecteur de la requête. Autrement dit, plus l'angle est fermé, plus il y aura proximité sémantique.

Dans le cadre de l’exemple précédent, si la requête est « je suis dans la rivière avec les loutres de la rivière » on obtient le vecteur (2/3, 1/3). En traçant le vecteur sur le graphique, on obtient la figure 4.

Fig. 4. Exemple de requête.

On voit alors que le texte le plus pertinent est le texte 1.

Evidemment, la notion d’angle ne se généralise pas graphiquement quand il y a de nombreuses dimensions, et on utilise à la place le cosinus de l’angle, qui peut se définir grâce à la formule du produit scalaire (voir Figure 5).

Fig. 5. Le cosinus de Salton en termes de produit scalaire.

Il faut noter que la notion même de similarité sémantique n’est pas associée uniquement au couple requête-document. On peut ainsi calculer les similarités entre toutes les paires de documents, pour créer un découpage thématique en clusters (groupes de documents qui abordent les mêmes sujets) de tout l’index. L’objectif de tels clusters est d’accélérer les calculs au niveau du moteur (plus la peine de regarder tous les documents pour chaque requête) et aussi d’améliorer la qualité des résultats (nous en reparlerons un peu plus loin).

Est-ce que le cosinus de Salton est vraiment utilisé ? Et pour quoi faire ?

La première chose à souligner concerne la TF-IDF. La TF-IDF est une mesure qui est utilisée par les moteurs, avec sans doute une formule propriétaire pour chaque moteur, mais le concept reste toujours le même. On peut donc partir du principe que l'utilisation du modèle vectoriel avec la TF-IDF est une bonne vision du fonctionnement d’un moteur de recherche.

Ensuite, il faut se poser la question de l’utilisation de la mesure de similarité par le cosinus de Salton. Pour réaliser une clusterisation de l’index, il s'agit d'un très bon outil et l’utiliser pour cela est une chose que les moteurs peuvent faire. En revanche, le cosinus de Salton pour classer les pages par pertinence est un peu faible en qualité de résultat, et la fonction qui va être utilisée par les moteurs est en fait une autre fonction : OKAPI BM25. BM25 (de son nom complet Online Keyword Access to Public Information Best Matching 25) est une fonction de classement mise au point dans les années 80 dans le cadre du projet OKAPI (d’où le nom) par Gillian Venner, Nathalie Mitev et Stephen Walker. C’est encore à l’heure actuelle le concept le plus utilisé par les moteurs de recherche pour déterminer l’adéquation d’un document à une requête.
L’explication de BM25 et de son fonctionnement dépasse largement le cadre de cet article, et nous renvoyons les lecteurs intéressés aux références [3], [4] et [5].

En résumé, un moteur va utiliser le modèle vectoriel et la TF-IDF, puis le cosinus de Salton pour clusteriser l’index, mais va plutôt utiliser BM25 pour le score de pertinence.

Que faire quand les résultats sont mauvais ?

Peu de gens en ont conscience, mais par défaut, toutes les mesures de similarité donnent des résultats assez moyens. Ce qui compte est alors d’être capable de corriger les résultats à partir d’un retour donné par les utilisateurs (c’est-à-dire donnant leur avis sur la pertinence des résultats fournis par le score de pertinence).

De nos jours, il existe de nombreux algorithmes pour corriger les résultats, mais le premier d’entre eux est dû à J.J Rocchio (qui a fait sa thèse à Harvard en 1966, et faisait partie de l’équipe du projet SMART). Cet algorithme est générique, ce qui signifie qu’on peut l’utiliser pour toute fonction de scoring de pertinence, et son but est de reformuler les requêtes. Ce dernier point est très important : c’est sur les requêtes que les moteurs travaillent pour améliorer les résultats, et pas sur les pages. Ceci est dû au fait que la requête est naturellement la source de la plupart des problèmes : il s’agit souvent d’un texte très court, ce qui induit qu’on a très peu d’information à partir d’une requête. il est de plus souvent difficile pour les utilisateurs de traduire efficacement et sans ambiguïtés leur besoin informationnel au sein d’une requête.

En fait de reformulation, la méthode de Rocchio va simplement calculer un nouveau vecteur en modifiant le vecteur de la requête selon une rétropropagation de la pertinence.

Concrètement, on va demander à un certains nombre d’utilisateurs de noter les documents du classement en deux ensembles : les documents pertinents, et ceux non pertinents. On va ensuite modifier le vecteur de la requête de la manière suivante :

V’ = a * V + b * centre(documents pertinents) - c * centre(documents non pertinents)

Que signifie cette formule ? tout d’abord, V est le vecteur de la requête avant reformulation, V’ le vecteur après reformulation, a, b et c sont des paramètres à choisir “pour que ça marche” et centre(X) est le centre de gravité des vecteurs de l’ensemble X.

La méthode de Rocchio va donc créer une requête virtuelle qui contient - en plus des mots de la requête réelle - des mots qui sont dans le champ lexical des pages que les internautes considèrent pertinentes pour la requête (il s’agit souvent de mots co-occurrents, d’où l’utilisation de cette notion pour faire de l’expansion de requête a priori).

Le modèle vectoriel est-il la panacée ?

Le modèle vectoriel comporte de très nombreux avantages : il est extrêmement simple (on apprend les mathématiques nécessaires à ce modèle au collège !) et il est effectif d’un point de vue calculatoire. Il permet par ailleurs de graduer la pertinence avec un score progressif et fin, et il est améliorable grâce à des algorithmes comme celui de Rocchio pour rendre plus performante la pertinence.

En revanche, il n’est pas la panacée puisqu’il ne prend pas en compte l’ordre des mots dans les documents (si bien que les moteurs utilisent des n-grams pour récupérer cette information au moins partiellement) et qu’il ne prend pas en compte le fait que les mots ne sont en réalité pas indépendants les uns des autres.

Par ailleurs, le modèle vectoriel souffre de certains défauts techniques, le principal étant sa dépendance à la taille des documents et son aveuglement aux sous-champs lexicaux (on peut exprimer la même idée avec des mots très différents que le modèle vectoriel n'associe pas entre eux ; Dans le pire des cas on va passer à côté d’un concept sémantique car il sera exprimé par trop de mots différents).

Pour réduire l’impact de tous ces problèmes, les moteurs ont mis en place un grand nombre d’algorithmes qui “patchent” les trous dans la raquette. C’est pour cela qu’ils utilisent des n-grams, qu’ils calculent intensivement les co-occurrences, qu’ils mettent en place différents algorithmes de réécriture des requêtes, etc.

Les nouveaux modèles vectoriels : les vecteurs de contexte

Pour récupérer plus d’information, les moteurs progressent actuellement sur l’utilisation des vecteurs de contexte. Nous reviendrons sur cette notion dans un prochain article, mais il s’agit principalement de créer un vecteur par mot et non plus un vecteur par document.

Le vecteur d’un mot donne une idée de la relation contextuelle à tous les autres mots de la langue, ce qui permet de comprendre le contexte générale d’un texte en composant toutes les relations contextuelles des mots qui composent ce texte.

Le lecteur pressé peut se rapporter à la référence [7] pour en savoir plus avant la publication de notre futur article sur le sujet. Globalement, ce qu’il faut retenir est que les vecteurs de contexte encodent les relations entre les mots, exprimés par des humains, dans les vecteurs. Il faut aussi comprendre que le calcul de ces vecteurs nécessite un volume de données très important car il s’agit d’apprendre “par l’exemple” les relations sémantiques. Les volumes typiquement nécessaires se situent en centaines de millions de mots (de l’ordre de plus de 1 000 livres). Sans oublier qu’un gros volume de données entraîne la nécessité de machines puissantes avec beaucoup de mémoire. Ceci étant, le futur proche de l’analyse de pertinence se trouve sans doute dans ces nouveaux vecteurs.

Conclusion : est-il possible de se servir de ces notions pour améliorer son SEO ?

La réponse est bien sûr oui. Il ne s’agit cependant pas simplement d’optimiser un texte en augmentant la TF-IDF des termes qui sont dans la requête visée (ce qui ne marche pas, et n’a sans doute jamais vraiment complètement fonctionné).
Il faut en fait faire une optimisation des termes importants du champ lexical associé au besoin informationnel des internautes-cibles. Pour cela, il faut les termes de la requête, ceux qui sont co-occurrents dans le besoin informationnel et ceux qui sont co-occurrents dans les pages web bien classées. On peut également plutôt utiliser les mots qui sont en relation avec ceux de la requête dans la composition des vecteurs de contexte associés à la requête.

Et pour faire cela, vous pouvez faire vous-même, ou alors utiliser des outils qui font ça tout seul (je vous laisse deviner lesquels si vous désirez devenir un "guru", la lettre d’Abondance en a déjà parlé 🙂 )...

 

Références

[1] G. Salton, The SMART Retrieval System: Experiments in Automatic Document Processing, 1971, Prentice-Hall.
http://sigir.org/files/museum/Information_Retrieval_Experiment/pdfs/p316-salton.pdf

[2] G. Salton, A. Wong, and C. S. Yang, A Vector Space Model for Automatic Indexing. Communications of the ACM, vol. 18, nr. 11, pages 613–620, 1975
https://pdfs.semanticscholar.org/9e44/b07d10cc18fd7a8800df907212b1fb78196e.pdf

[3] Mitev, N. N., Venner, G. M., & Walker, S. (1985). Designing an Online Public Access
Catalogue: Okapi, a Catalogue on a Local Area Network.
http://sigir.org/files/museum/pub-28/pub-28-frontmatter.pdf

[4] Walker, S. (1987). OKAPI: Evaluating and Enhancing an Experimental Online Catalog.
https://www.ideals.illinois.edu/bitstream/handle/2142/7503/librarytrendsv35i4j_opt.pdf?sequence=1

[5] Walker, S., & Beaulieu, M. H. (1991). Okapi at City: An evaluation facility for interactive IR.
Centre for Information Science City University, British Library Research and Development
Report No. 6056, 1991.
http://sigir.org/files/museum/pub-26/frontmatter.pdf

[6] Rocchio, J. J. (1971). Relevance feedback in information retrieval.

[7] Piotr Migdal. king - man + woman is queen; but why?
http://p.migdal.pl/2017/01/06/king-man-woman-queen-why.html