L’algorithme HITS et le projet CLEVER (deuxième partie)

Dans la première partie de cet article, nous avions présenté les principes de l’algorithme HITS et l’histoire de son « invention » par son créateur : John Kleinberg.

L’algorithme HITS et le projet CLEVER

HITS est resté plus longtemps dans les laboratoires que le Pagerank, mais a eu aussi des applications pratiques. Des applications parfois méconnues, mais pourtant intégrées dans des moteurs de recherche grand public comme Ask Jeeves !

Dans cette deuxième partie, nous allons faire le tour de ses applications les plus remarquables…

« LE WEB EN TANT QUE GRAPHE »

L’une des premières applications pratiques des idées à l’origine de l’algorithme HITS a été l’étude de la structure de la Toile. Les résultats de l’étude réalisée ont été présentées dans un article célèbre baptisé « Le Web en tant que graphe » que nous avons présenté dans un article précédent :
La structure du web est en forme de « noeud papillon »


Cet article a eu un retentissement inattendu, mais essentiellement pour les résultats statistiques qu’il présentait, pas sur les méthodes mathématiques présentées. Pourtant, le titre de l’article fait allusion à l’un des résultats les plus intéressants de l’équipe de Kleinberg, c’est à dire le fait que le Web pouvait être étudié par la méthode mathématique des graphes orientés. Or ce domaine mathématique a été très étudié depuis de nombreuses années, et de nombreux résultats théoriques intéressants ont été obtenus.

Cette idée de représenter les liens hypertextes par des graphes orientés s’est donc révélée particulièrement fructueuse, et a permis depuis lors de nombreuses avancées, tant sur le plan de la théorie que sur le plan pratique, comme par exemple l’accélération des algorithmes de calcul.

LE PROJET CLEVER ET LES PREMIERES APPLICATIONS PRATIQUES

Dès que l’algorithme HITS est « sorti du laboratoire » pour être utilisé à grande échelle sur l’ensemble de la Toile, un certain nombre de « failles » sont apparues… HITS n’était pas pertinent sur toutes les requêtes (ce qui explique pourquoi le PageRank a connu une application grand public beaucoup plus tôt). Et nécessitait un temps de calcul très long pour « noter » les pages et les « classer » en Hubs et Authorities.


Le projet CLEVER (Clientside Eigenvector Enhanced Retrieval : extraction améliorée de vecteur propre côté client) développé au sein du laboratoire Almaden d’IBM a été la première tentative d’utilisation de HITS pour créer un moteur de recherche opérationnel. Kleinkerg a participé au projet en tant que « scientifique invité ».

CLEVER a apporté deux améliorations sensibles à l’algorithme HITS.

D’abord la résolution du problème de la « définition circulaire » : en fait, la théorie ne donne pas une définition « absolue » de ce que sont les « Hub » et les « Authorities ». Certes, les idées sous-jacentes sont assez intuitives : « De bons « Hubs » pointent vers beaucoup d' »Authorities », et de bonnes « Authorities » reçoivent des liens de la part de bons « Hubs ». Mais la définition d’un Hub se fait en parlant d’Authorities, celle d’une Authority en parlant des Hubs…

Cela veut dire en fait qu’on ne sait pas « a priori » ce qu’est un bon Hub ou une bonne « Authority ». Ces entités naissent de l’étude des liens, des résultats de calculs algorithmiques.

Il en résulte une faille majeure : si on se base uniquement sur le nombre de liens, certaines pages se voient attribuer des notes artificiellement hautes, parce qu’elles reçoivent des liens de la part de Hubs qui sont en fait des copies de la même page (un résultat bien connu de nos jours avec le spamming).

Dans le projet CLEVER, des filtres sont ajoutés pour ne pas tenir compte de liens dupliqués, et des corrections sont apportées en fonction du contexte d’apparition du lien dans la page (les termes recherchés sont ils proches ou éloignés du lien).

Par ailleurs, la note « transmise » par certains Hubs peut-être non pertinente : citons un exemple donné dans un article de l’équipe CLEVER.

« Nous rencontrons souvent des situations dans lesquelles une bonne page « Hub », par exemple, apparait avec un différent niveau de généralité que celui de la requête pour laquelle il serait utile. Par exemple, considérons la requête « mangue ». Une page Hub de haute qualité consacrée aux fruits exotiques aurait une section contenant des liens vers des pages parlant de la papaye, une autre des liens parlant de la mangue, et une dernière des liens parlant de la goyave. Néanmoins, si on considère la page comme étant un bon hub sur un plan plus général, les pages sur la papaye et la goyave qui n’ont pas de rapport avec la requête mangue, seront quand même considérées comme de bonnes pages « authorities ». Pour éviter cela, nous identifions des sections intéressantes du web (physiquement contigues) et nous utilisons ces sections pour déterminer quelles sont les pages qui peuvent être considérées comme des bons Hubs et Authorities dans leur intégralité. »

SALSA

SALSA est un acronyme pour « Stochastic Approach for Link-Structure Analysis » [1].

Il s’agit d’un projet de projet de recherche lancé dès 1997 par un étudiant israelien, Ronny Lempel, sous la direction de Shlomo Moran, au Technion d’Haifa. Un laboratoire de recherche qui a travaillé étroitement avec l’équipe d’Aya Soffer, du laboratoire de recherche IBM d’Haifa. Ronny Lempel travaille aujourd’hui au sein de ce laboratoire d’IBM en Israël.

SALSA apporte une solution nouvelle au problème évoqué plus haut de la « définition circulaire [2] » des hubs et authorities et des effets de bords du « renforcement mutuel [*] » qui en résulte, dégradant la pertinence des résultats.

Dans la méthode SALSA, un méta-algorithme est appliqué pour identifier des structures dans les hubs et authorites détectées par HITS. Cette méthode permet de filtrer les hubs et les authorities pour ne garder que les plus pertinents.

Ensuite intervient l’approche stochastique. Qui n’est autre que celle des chaînes de Markov et du « promeneur aléatoire » qui constitue les bases théoriques du pagerank de Google. [3]

LES DESCENDANTS DE L’ALGORITME HITS

Teoma Ask Jeeves


L’algorithme de Teoma est directement dérivé de HITS. Il a été inventé en 1999 par Apostolos Gerasoulis, à l’époque professeur d’informatique à l’Université de Rutgers (New Jersey). Il travaillait sur des projets de défense nationale (notamment le projet DARPA) dont l’objectif était de permettre aux superordinateurs du Pentagone d’aspirer efficacement toutes les données disponibles sur la Toile, ce qui l’a obligé à s’intéresser à la technologie des moteurs de recherche.

En partant des résultats obtenus par Kleinberg, l’équipe de Gerasoulis a réussi a élaborer le prototype d’un moteur d’un genre nouveau, qu’ils ont baptisé Discoweb (DISCOvers the Web : il découvre le web).

Discoweb avait la particularité d’être capable, pour la première fois, de discerner des structures de liens entre les sites, de repérer des sites fortement interconnectés parlant d’un sujet ou d’une thématique unique, et donc, d’être capable de « catégoriser » automatiquement des sites, et de créer ce qui ressemblait fort à un annuaire « automatique ».

Ce prototype s’est transformé rapidement (avril 2000) en un projet de moteur commercial baptisé Teoma (Téoma signifie « expert », en gaëlique : peut-être un clin d’oeil à CLEVER ?).

Les améliorations apportées à HITS accomplis au sein de l’équipe de recherche de Teoma sont visiblement considérables (même si peu de choses a été révélé sur les trouvailles de Gerasoulis), que cela soit au niveau de la vitesse de convergence de l’algo ou de pertinence accrue des résultats.


Teoma a été racheté en septembre 2001 par Ask Jeeves (un site peu connu en France, mais très utilisé dans les pays anglo-saxons). Les résultats du moteur de Teoma apparaissent sous la forme de « suggestions » de sites parlant du même sujet sur les pages de Ask Jeeves [4].

Wisenut


Wisenut est un moteur de recherche peu connu (surtout en Europe), lancé en septembre 2001 [5], par Yeogirl Yun, qui avait auparavant fait partie de l’aventure MySimon, l’un des premiers comparateurs de prix en ligne, absorbé par la suite par C|Net. Wisenut a été racheté par Looksmart quelques mois après son lancement.

Sans le revendiquer officiellement, Wisenut s’appuie sur un algorithme
dérivé de HITS pour catégoriser les sites, ainsi que de méthodes sémantiques pour améliorer la pertinence de ces résultats. Les méthodes utilisées ressemblent beaucoup à celles de Teoma.

Webfountain

Webfountain d’IBM est l’une des plus récentes (et des plus spectaculaires) applications commerciales s’appuyant sur l’algorithme HITS.

Nous avons déjà décrit ses caractéristiques dans cet article :
Webfountain d’IBM

IBM a donc attendu presque sept ans pour « exploiter commercialement » les travaux de recherche menés en son sein (HITS, CLEVER, SALSA… et bien d’autres).

« Big Blue » montre une voie nouvelle : il est possible de créer des moteurs de recherche plus pertinents, combinant sémantique, analyse de la structure des liens, spiders performants et plus intelligents, index dynamiques, et recherche contextuelle pour aboutir à des moteurs beaucoup plus pertinents et performants que ceux d’aujourd’hui…

Philippe YONNET

Quelques liens pour en savoir plus :

Le site du projet Clever chez IBM

Histoire du moteur Teoma

Présentation de la technologie Teoma

Le moteur de recherche Wisenut

Bibliographie :

J. Kleinberg. Authoritative sources in a hyperlinked environment. To appear in the Journal of the ACM, 1999. Also appears as IBM Research Report RJ 10076, May 1997.

S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, and S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Proceedings of the 7th World-Wide Web conference, 1998. Copyright owned by Elsevier Sciences, Amsterdam.

D. Gibson, J. Kleinberg, and P. Raghavan. Inferring Web Communities from Link Topologies. Proceedings of The Ninth ACM Conference on Hypertext and Hypermedia, 1998. Copyright owned by ACM.

S. Chakrabarti, B. Dom, R. Agrawal, P. Raghavan. Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies. VLDB Journal, 1998 (invited).

S. Chakrabarti, B. Dom, D. Gibson, S.R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Spectral filtering for resource discoveryACM SIGIR workshop on Hypertext Information Retrieval on the Web (1998), Melbourne, Australia.

S. Chakrabarti, B. Dom and P. Indyk. Enhanced hypertext categorization using hyperlinks. Proceedings of ACM SIGMOD 1998.

S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Hypersearching the web. Scientific American, June, 1999.

S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Mining the link structure of the World Wide Web IEEE Computer.

S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the Web for emerging cyber-communities Eighth World Wide Web conference, Toronto, Canada, May 1999.

S. Chakrabarti, M. Van den Berg, B. Dom Focused crawling : a new approach to topic specific resource discovery Eighth World Wide Web conference, Toronto, 1999.

J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The web as a graph : Measurements, models and methods. Proceedings of the International Conference on Combinatorics and Computing, 1999 ; invited paper.

S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Extracting large scale knowledge bases from the web. IEEE International conference on Very Large Databases (VLDB), Edinburgh, Scotland.
D. Gibson, J. Kleinberg and P. Raghavan. Clustering categorical data : an approach based on dynamical systems. Proceedings of the VLDB conference, 1998.

The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect
R. Lempel, S. Moran Department of Computer Science
The Technion, Haifa 32000, Israel, 1999


[1] Approche Stochastique pour l’Analyse de la Structure des Liens

[2] *Traduction littérale des expressions utilisées par Kleinberg

[3] cela n’a en fait rien d’étonnant, car il a déjà été mentionné plus haut que PageRank et HITS s’appuient tous les deux sur les mêmes bases théoriques que sont les mathématiques sur les graphes orientés. Mais ici, le « promeneur aléatoire » est utilisé différemment : il ne saute pas de site en site en considérant chaque site comme équivalent, mais il passe par des hubs, et des authorities… ce qui aboutit à des résultats forts différents

[4] Ask Jeeves, qui vient de racheter Excite, est devenu le troisième larron du monde des moteurs de recherche, derrière Google et Yahoo/Overture/Alltheweb/Inktomi, devant MSN. Et ce n’est pas le larron le moins inventif…

[5] La version bêta a été lancée en juin 2001