Comment un moteur de recherche décide-t-il quoi vous montrer

Quand vous appuyez sur entrée, personne ne part chercher sur le web

Niveau Débutant — langage simple, sans maths

La première chose à mettre au clair est qu'un moteur de recherche ne va pas regarder le web quand vous tapez quelque chose. Il ne le pourrait tout simplement pas : la réponse arrive en deux dixièmes de seconde environ, ce qui ne suffit pas à visiter même un seul site lointain, encore moins un milliard. Tout a été fait à l'avance.

Ce qui se passe à l'avance s'appelle l'exploration. Un programme part d'une page quelconque, la lit, note chaque mot qu'elle contient, puis suit chaque lien de cette page pour en trouver d'autres, et recommence, indéfiniment. Le web est tenu ensemble par les liens, donc les suivre depuis quelques points de départ finit par atteindre presque tout.

Ce qui est noté est un index, et il est construit à l'envers de ce qu'on attendrait. Au lieu d'une liste de pages avec les mots qu'elles contiennent, c'est une liste de mots avec les pages qui les contiennent. Cherchez volcan et vous avez immédiatement toutes les pages qui le mentionnent. C'est l'astuce qui rend la réponse instantanée : le travail dur a été fait la semaine dernière.

Vient ensuite la partie intéressante, l'ordre. Compter combien de fois une page dit volcan est un début, mais n'importe qui peut écrire un mot mille fois, et dans le web des débuts les gens faisaient exactement cela. L'idée qui a réglé le problème a été de regarder les liens : traiter un lien comme un vote, et compter les votes des pages importantes comme valant plus que ceux de personne. Bougez le curseur dans la simulation et regardez la page de la boutique, qui mentionne les volcans sans arrêt et vers laquelle personne ne renvoie, glisser au bas de la liste, à sa juste place.

Index inversés, TF-IDF et le surfeur aléatoire

Niveau Élève — les équations essentielles

L'index est la fondation. Pour chaque terme, le moteur stocke une liste d'occurrences : les documents qui le contiennent, généralement avec les positions, pour que les recherches de phrases fonctionnent. Une requête de deux mots devient une intersection de deux listes, ce qui est rapide parce que les listes sont triées et compressées. Tout le reste - classement, extraits, filtres - travaille sur cette structure.

Classer par le seul texte utilise TF-IDF, et les deux moitiés comptent. La fréquence du terme récompense un document pour avoir mentionné le mot, généralement avec une fonction d'amortissement puisque la cinquantième occurrence ajoute moins que la deuxième. La fréquence inverse de document pénalise les mots qui apparaissent partout : une correspondance sur le ne vaut rien, une sur thermocline est très informative, et le poids est \(\log(N/\text{df})\). Le raffinement moderne est BM25, qui ajoute une normalisation par la longueur pour que les documents longs ne gagnent pas simplement parce qu'ils contiennent plus de mots.

PageRank fournit la seconde moitié, et sa définition est récursive d'une façon qui semble circulaire mais ne l'est pas : une page est importante si des pages importantes pointent vers elle. Imaginez un surfeur qui clique des liens au hasard et saute de temps en temps vers une page quelconque - le facteur d'amortissement \(d\), conventionnellement 0,85, est la probabilité de cliquer plutôt que de sauter. Le PageRank est la fraction du temps que le surfeur passe sur chaque page à long terme, c'est-à-dire le vecteur propre principal de la matrice des liens, calculé en itérant jusqu'à ce que cela cesse de bouger.

Le score final les mélange, et c'est dans le mélange que réside le jugement. Trop de poids au texte et le bourrage de mots-clés gagne ; trop aux liens et une page populaire bat une page pertinente. Les systèmes réels ajoutent des centaines d'autres signaux - fraîcheur, comportement de clic, vitesse de la page, et depuis 2019 des modèles de langue neuronaux qui évaluent le passage par rapport au sens de la question plutôt qu'à ses mots - mais la structure en deux parties, pertinence et autorité, reste visible en dessous.

Vecteurs propres, compression d'index et le classement après la recherche dense

Niveau Expert — profondeur mathématique complète

01PageRank comme chaîne de Markov

Écrivez le web comme une matrice stochastique en colonnes \(M\) où \(M_{ij} = 1/L(j)\) si \(j\) pointe vers \(i\). L'opérateur amorti \(G = dM + \frac{1-d}{N}\mathbf{1}\mathbf{1}^{\!\top}\) est stochastique, irréductible et apériodique, si bien que Perron-Frobenius garantit un unique vecteur stationnaire positif : le PageRank est son vecteur propre principal. La méthode des puissances converge à un rythme gouverné par la seconde valeur propre, bornée par \(d\) pour la chaîne amortie ; à \(d = 0,85\), cela fait environ une décimale toutes les douze itérations, ce qui explique que cinquante itérations aient suffi sur un web de milliards de pages. Les nœuds pendants, qui ne pointent nulle part, doivent être traités explicitement sous peine de fuite de masse de probabilité.

02L'index, et pourquoi la compression est un problème d'ordonnancement

Les listes d'occurrences sont stockées comme des écarts entre identifiants de document plutôt que comme les identifiants eux-mêmes, puis codées par octets variables, Elias-Fano ou schémas adaptés au SIMD. Attribuer les identifiants de sorte que des documents similaires portent des numéros voisins réduit les écarts et donc l'index, ce qui fait de l'ordre des documents une décision de compression aux conséquences directes sur la latence des requêtes. L'évaluation utilise ensuite l'élagage dynamique : WAND et block-max WAND sautent des blocs entiers d'une liste dont la meilleure contribution possible ne peut atteindre le seuil courant des k premiers, et c'est ce qui rend le scorage exhaustif inutile.

03Apprendre à classer

Quand les signaux se comptent par centaines, le réglage manuel s'arrête. Le learning-to-rank traite l'ordonnancement comme un problème supervisé sur des paires requête-document jugées, et les objectifs utiles sont de liste plutôt que de point, parce que la métrique qui compte - le gain cumulé actualisé normalisé - dépend de l'ordre entier et n'est pas différentiable. LambdaMART contourne cela en définissant les gradients directement à partir de la variation de la métrique sous un échange, et il est resté le standard de production pendant des années précisément parce que les arbres boostés gèrent mieux que les réseaux des caractéristiques hétérogènes et mal mises à l'échelle.

04Recherche dense et la fin de la correspondance exacte

Les index inversés retrouvent par recouvrement lexical, si bien qu'un document disant voiture est invisible à une requête sur automobile. La recherche dense encode requête et document en vecteurs avec un transformeur et retrouve par recherche approchée du plus proche voisin sur des graphes HNSW, faisant correspondre le sens plutôt que les chaînes. Elle est généralement associée à l'index lexical dans un hybride, car la recherche dense est faible exactement là où la recherche éparse est forte : noms propres rares, identifiants, et termes que l'encodeur n'a jamais vus à l'entraînement. Le dernier étage est un cross-encodeur qui lit ensemble requête et candidat, bien trop coûteux pour la recherche, abordable pour reclasser les cent premiers.

05Un système adversarial

Unique parmi les problèmes de classement, les documents sont ici écrits par des parties qui connaissent la fonction de classement et profitent à la battre. Cela change l'ingénierie : les signaux doivent être coûteux à falsifier, et c'est pourquoi les liens venant de sources fiables pèsent plus que ceux qu'une page peut se créer elle-même, et pourquoi les signaux de clic sont fortement débruités. Cela explique aussi que les détails du classement ne soient pas publiés. L'arrivée de texte généré à grande échelle aiguise le problème : les signaux bon marché d'effort sur lesquels le classement s'est discrètement appuyé pendant vingt ans ne séparent plus le soigneux de l'automatique.