Vers un moteur de recherche sensible au contexte (2ème partie)

Les chercheurs de Stanford ont cherché des solutions pour dépasser les limitations des moteurs de recherche utilisant le PageRank. Ce sont ces pistes que nous allons détailler dans cette deuxième partie.

Les différentes pistes pour calculer un PageRank Personnalisé

Page et Brin ont posé l’idée de créer un PageRank personnalisé dès la création du premier algorithme du PageRank. Mais leur idée était inapplicable dans la pratique : elle consistait à effectuer des calculs de pagerank à la volée au moment de la requête.

Toutes les pistes explorées depuis partent toujours du principe suivant : réaliser les calculs complexes et qui demandent des temps de calcul important "offline". Stocker les résultats dans l’index, et limiter les calculs à effectuer lors de chaque requête à des opérations simples, qui peuvent être effectuées rapidement sans surutilisation du processeur.

Un préalable nécessaire : accélérer la vitesse de convergence des algorithmes

L’équipe des chercheurs de Stanford s’est vite rendu compte que l’accélération de la vitesse de convergence de l’algorithme du PageRank était indispensable pour progresser dans leurs recherches. En effet, toutes les méthodes explorées consistaient à calculer non pas un, mais des dizaines, voire des centaines de PageRank différents, sensibles au contexte. [1]

Ces recherches ont abouti à trois solutions radicalement différentes
le Pagerank modulaire ("modular Pagerank")
le BlockRank : pagerank calculé par blocs
le Pagerank sensible à la thématique ("Topic sensitive pagerank")

L’équipe qui a constitué Kaltix (Sepandar D. Kamvar Taher H. Haveliwala Christopher D. Manning Gene H. Golub), et qui travaille maintenant pour Google, est à l’origine des deux dernières approches. La première est l’oeuvre de Glen Jeh et Jennifer Widom.

Le pagerank modulaire

Le pagerank modulaire part du principe qu’il est possible de calculer une bonne approximation des pageranks de toutes les pages en découpant le web à partir d’un jeu de pages de départ, baptisé "Hub set".

Un page rank est calculé pour chaque zone reliée à ces pages de départ, l’ensemble des pages dépendant de ces pages de départ recouvrant une zone plus ou moins complète du web.

Les meilleurs résultats sont obtenus lorsque le Hub set est composé de pages à fort pagerank. Dans ce cas, on obtient des résultats corrects pour les page ranks, et, à condition de partir d’un Hub Set comportant un grand nombre de pages, on obtient un recouvrement quasi complet du web.

Une présentation schématique du calcul du pagerank modulaire

Il semble que cette approche reste pour l’instant dans les labos, car le ratio gain en vitesse de calcul/précision des résultats n’est pas bon. Elle permet néanmoins de calculer des pageranks pour des zones particulières du web, avec des résultats meilleurs que l’approche traditionnelle.

Le blockrank

Cet algorithme part d’un constat expérimental : les pages webs ne sont pas réparties uniformément. Notamment, il existe des groupes de pages fortement liées entre elles, comme celles constituant un site web. Chaque "bloc de pages" est ensuite relié aux autres pages par un faible nombre de liens.

L’idée consiste ici à calculer un pagerank "local", sur un bloc de pages (dans la pratique limité à un domaine). L’algorithme converge rapidement dans ce cas particulier. Ensuite, pour le calcul du pagerank définitif, il suffit de faire un calcul sur une matrice de blocs, et non la Toile en entier, pour obtenir une excellente approximation du pagerank réel.

La manière dont les pageranks sont propagés de bloc à bloc dépend toutefois de la fixation de coefficients empiriques. Il est heureusement facile de déterminer ces coefficients de manière précise dès lors que l’on dispose d’un index de référence, avec des pageranks calculés avec un algorithme traditionnel.

Cet algorithme représente une avancée considérable : il diminue le temps de calcul des pageranks de manière considérable (jusqu’à 20 fois moins ?). Il permet aussi de déterminer une bonne approximation du PR effectif pour toute nouvelle page entrant dans l’index.

On soupçonne d’ailleurs fortement Google d’utiliser ce nouvel algorithme depuis mai/juin 2003.

La simplification du calcul apportée par ce nouvel algorithme autorise de plus une création plus aisée de pageranks thématiques, selon le modèle décrit ci-après. Il semble néanmoins que tous les problèmes ne soient pas résolus, car les erreurs de calcul augmentent de manière exponentielle dès que l’on augmente le nombre de PR thématiques calculés.

Le Pagerank sensible à la thématique

Ce "nouvel" algorithme en fait ne consiste en fait qu’en une réutilisation astucieuse du PageRank traditionnel. L’idée part d’un constat simple : le pagerank permet de classer par ordre d’impotance des pages dont le contenu est identique. Mais il ne permet pas de distinguer une page qui parle du "jaguar" l’animal, ou de la "jaguar" la voiture.

La solution proposée dans le "Topic Sensitive Pagerank" est de biaiser le calcul du Pagerank en donnant plus d’importance aux pages bénéficiant de liens en provenance de sites dont on connait la thématique de départ. Dans la pratique, on peut par exemple prendre en compte les sites mentionnés dans l’une des 16 rubriques de niveau 1 de l’ODP.

Le résultat donne forcément 17 vecteurs de Pagerank différents pour chaque page : le PageRank "général", et les 16 pageranks biaisés...

Ces valeurs sont stockées dans l’index avec les pages, comme pour un moteur basé sur le pagerank traditionnel.

Pour utiliser ces valeurs correctement, il suffit ensuite d’être en mesure de déterminer à quelle thématique se rattache une requête donnée. Ceci peut être obtenu grâce à une analyse syntaxique et sémantique sommaire, facile à calculer à la volée. Il suffit en effet de créer un index contenant, pour chaque thématique, le nombre d’occurences de chaque terme apparaissant dans les pages. Ensuite, la thématique associée à une requête sera évaluée selon une méthode probabiliste, d’autant plus précise que l’on connait le contexte de la requête...

Comme on le voit dans le schéma ci-dessous, l’architecture d’un tel moteur est assez peu différente d’une architecture traditionnelle avec pagerank. L’essentiel des calculs longs et complexes est toujours effectué offline.

Architecture d’un moteur de recherche utilisant un pagerank sensible à la thématique

Comme on le voit dans l’exemple ci-dessous, publié dans l’article de Kamvar et Haveliwala, les résultats obtenus sur la requête "bicycle" sont très différents suivant le contexte thématique, et les résultats en général beaucoup plus pertinents.

Un exemple obtenu sur la requête "bicycle" et un moteur sensible à la thématique

Première partie :
Les avantages et les limites du Pagerank
Dernière partie :
Y’a-t’il un avenir pour de tels moteurs de recherche

Philippe YONNET

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

[1] L’une des découvertes a été l’extrapolation quadratique, un système qui permet d’éviter des calculs matriciels systématiques inutiles au cours du calcul du PageRank. Une autre a été le "PageRank adaptatif" ("adaptative pagerank") un algorithme qui tient compte de la possibilité de ne pas calculer certains termes à différentes étapes de l’itération

> Référencement et publicité