Vers un moteur de recherche sensible au contexte (1ère partie)

Améliorer la "pertinence" des résultats constitue un objectif technologique majeur pour la plupart des moteurs de recherche. Le problème, c’est que cette "pertinence" est une notion purement subjective, qu’il est donc difficile de manier avec des algorithmes purement mathématiques.

Le moteur de recherche Google, notammment, cherche depuis plusieurs années une solution à ce problème. Les premières pistes en ce sens ont été lancées par Larry Page, dans une publication publiée alors qu’il était encore étudiant à l’université de Stanford.

Stanford conserve depuis l’époque de Page et Brin, les fondateurs de Google, un département de recherche consacré au Pagerank. Depuis deux ans, une nouvelle équipe de chercheurs a ouvert la voie à des solutions permettant de calculer des PageRank personnalisés, et donc d’affiner, avec une économie de moyens remarquable, les pages de résultats des moteurs dans un contexte donné.

Ces travaux sont mal connus, en dehors du cercle des spécialistes et ne sont pas tous encore utilisés par les moteurs. Mais il y’a fort à parier que les premiers moteurs thématiques, construits autour de ce type d’algorithme, ne devraient pas tarder à sortir : certains des chercheurs de Stanford ont constitué en juin 2003 la société Kaltix, rachetée récemment par Google fin septembre 2003...

Les avantages et les limites du Pagerank

L’algorithme du Pagerank : la force brute du calcul au service de la pertinence des résultats

Google a construit son succès autour d’un algorithme de calcul permettant de stocker dans l’index du moteur, avec chaque page, une "valeur" indicative de l’"importance" de ces pages sur le web. On se référera aux excellents articles de Dan Hetzel pour en comprendre les principes [1] Cette valeur part du principe intuitif que l’importance d’une page dépend du nombre de liens entrants pointant vers cette page, mais aussi de l’importance des pages d’où partent ces liens.

Calculer un Pagerank pour une page demande donc un calcul itératif, puisque doter une page d’un pagerank modifie par ricochet le pagerank de toutes les pages vers lesquelles pointe un lien de cette même page, et de toutes les pages reliées à ces pages. Toute modification du pagerank d’une page se "propage" donc au fil des liens de page en page... Mais si l’une des pages ainsi reliée, quel que soit le nombre de liens qui la sépare de la page dont on a calculé le pagerank, contient un lien réciproque vers la page de départ, cela modifie également le pagerank de la page de départ.

L’algorithme itératif de calcul du Pagerank converge au bout d’un certain nombre d’itérations, vers une valeur fixe. Le problème, c’est que cette "convergence" de la suite des résultats n’est pas assurée en théorie (mais elle l’est dans la pratique compte tenu de la structure réelle du web) et la "vitesse de convergence" (le nombre d’itérations pour atteindre une valeur précise proche de la limite) est très variable suivant les zones du web.

Le calcul du Pagerank nécessite du temps et une puissance de calcul phénomale

La puissance de calcul nécessaire pour calculer le Pagerank pour un index de la taille de Google est assez fantastique. Mais heureusement, il s’agit essentiellement de calculs matriciels très simples, qui sont facilement gérables avec une architecture basée sur un grand nombre de machines calculant chacune les valeurs pour une petite zone de la colossale matrice du web.

Selon quelques "fuites" en provenance du Googleplex, le temps de calcul nécessaire pour calculer le PageRank de toutes les pages du Web indexées prenait jusqu’à une bonne semaine... (La méthode utilisée a changé au printemps 2003, on le verra plus loin.)

Par contre, une fois ce calcul effectué, le pagerank est stocké dans l’index avec les pages, et est donc disponible pour affiner le calcul des positions sur les pages de résultats, qui dépend aussi d’autres critères plus classiques, mais propres à chaque page, comme la densité de mots clés par exemple.

L’architecture d’un moteur basé sur le Pagerank

La méthode imaginée par Page et Brin a deux vertus : les calculs les plus complexes et les plus longs se font offline. Le moteur n’a plus que des calculs très simples à effectuer pour construire les pages de résultats à la volée.

On voit sur le graphique ci-dessous, l’architecture d’un moteur utilisant le PageRank : il n’est pas très différent d’un moteur classique.

Architecture d’un moteur de recherche utilisant le pagerank

Ensuite, la prise en compte du seul "nombre de liens" comme critère permet une totale modélisation mathématique du calcul de la "valeur d’une page". Sur le plan théorique, le PageRank est un calcul qui mesure les conséquences du comportement d’un internaute téléporté au hasard de page en page au hasard des liens qui les relient.

Les limites du PageRank

Sur le plan théorique, le postulat de Brin et Page selon lequel la valeur des pages dépend du nombre de liens entrants a été critiqué dès 1999 par les chercheurs du laboratoire Almaden d’IBM. Ces critiques portaient sur deux points :
ce postulat fait fi de la véritable structure du web, qui n’est pas uniformément reliée par des liens hypertextes.
le pagerank n’apporte aucune info sémantique, et est susceptible de donner de l’importance à des pages qui n’en ont pas

On peut vérifier dans la pratique la justesse de ces remarques en consultant les pages de résultats renvoyées par Google.

Suite de l’article (Deuxième partie) :

Les différentes pistes pour calculer un PageRank Personnalisé

Philippe YONNET

Commentez l’article "Vers un moteur de recherche sensible au contexte" sur le forum Webmaster-hub

[1] Sur le pagerank : Le PageRank par l’exemple, par Dan Hetzel
L’algorithme du PageRank expliqué, par Dan Hetzel

> Référencement et publicité