Un moteur de recherche comme Google ou Bing est loin d'être un système simple pouvant être expliqué en quelques lignes. Il est au contraire l'addition de plusieurs technologies souvent assez complexes, lui permettant de renvoyer à l'internaute qui l'utilise les résultats les plus pertinents. Cette série d'articles vous explique donc quelles sont les différentes briques d'un moteur et vous dévoile les arcanes qui constituent leurs entrailles. Après nos précédents articles sur les technologies de crawl, l'index inversé, le duplicate content et le PageRank thématique, nous abordons ce mois-ci la notion de calcul de la pertinence d'une page web par rapport à la demande de l'internaute; Après avoir lu ces quelques lignes, les notions de modèle vectoriel, TF-IDF, cosinus de Salton et Okapi BM 25 n'auront - presque - plus de secrets pour vous...
Par Guillaume Peyronnet, Sylvain Peyronnet et Thomas LargillierNous poursuivons notre cycle sur le fonctionnement des moteurs de recherche par cet article qui aborde ce mois-ci les bases de ce que nous appelons “l’analyse de la pertinence”. Bien sûr, il s’agit d’une vision extrêmement simplifiée, mais qui permet de bien comprendre les différents types de traitements que va opérer un moteur de recherche pour “comprendre” le contenu des documents disponibles sur le Web, et sur la façon de renvoyer les bons documents pour une requête tapée par un utilisateur.
Des signaux, des requêtes et des pages
Avant de rentrer dans une explication plus complète, voyons ce qu’est la démarche réelle, sans jamais rentrer dans les détails pour le moment.
En pratique, on peut distinguer différents types de signaux pour un moteur de recherche. Il existe des signaux qui sont attachés aux documents, comme par exemple le PageRank, le nombre de liens sortants et entrants, le nombre de versions existantes (en cas de duplication de documents), le fait que le document soit considéré comme du spam, etc. Il existe ensuite des signaux qui sont associés à un couple requête-texte (le texte en question pouvant être un document complet ou juste une partie d’un document (comme par exemple la balise Title ou la description, etc.). Enfin, il existe des signaux qui viennent de l’analyse du comportement des utilisateurs du moteur.
Quand un utilisateur tape une requête, par exemple “machine à café pas chère”, le moteur de recherche va récupérer et regarder tous les vecteurs de signaux pour les couples composés de cette requête et des documents de l’index. Ces vecteurs vont être ordonnés par une formule de pondération qui détermine quels sont les signaux qu’il faut utiliser et dans quelles proportions. Cette formule est simple, mais ces paramètres ne sont pas faciles à connaître car ils sont déterminés par un algorithme de machine learning (apprentissage automatique).
Parmi tous les signaux, un grand nombre caractérisent la pertinence par rapport à la requête. Certains signaux sont simplistes (un exemple typique serait “est-ce que les mots de la requête sont dans la balise title ?”) tandis que d’autres sont plus complexes. Dans ces dernier,s on trouve des signaux dépendant du modèle vectoriel, et c’est de cela dont nous allons parler aujourd’hui.
Le modèle vectoriel
Le modèle vectoriel pour représenter des documents textuels a été mis en place dans le cadre du système SMART (System for the Mechanical Analysis and Retrieval of Text) [1][2]. SMART était un projet de l’Université de Cornell dirigé par Gérard Salton à partir des années 60. Les premières versions opérationnelles du système datent de 1968, mais le travail a été poursuivi assez longtemps puisque, par exemple, une réécriture totale en a été effectuée dans les années 80.
Comme son nom l’indique, le modèle vectoriel va utiliser des vecteurs pour représenter les documents et les requêtes. Chaque dimension de l’espace vectoriel va correspondre à un terme différent existant dans des documents de l’index du moteur. Il va donc y avoir autant de dimensions qu’il y a de termes disponibles dans l’index.
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
Thomas Largillier, Guillaume Peyronnet et Sylvain Peyronnet sont les fondateurs de la régie publicitaire sans tracking The Machine In The Middle (http://themachineinthemiddle.fr/).