MSN Search utilise-t’il l’analyse au niveau des blocs ?

Quelques jours après le lancement officiel du moteur MSN Search, et à la veille de la campagne de publicité sur le dernier produit de Microsoft, tous les regards des référenceurs et des webmasters se tournent vers les pages de résultats pour en déterminer les secrets.

Deux articles publiés par les chercheurs du centre de recherche de Microsoft peuvent nous donner un éclairage sur les axes de recherche suivis pour améliorer la pertinence des résultats dans le moteur de MSN.

L’analyse au niveau des blocs, c’est quoi ?

Tous les moteurs grand public utilisent des algorithmes basés sur l’analyse des liens

Les moteurs de recherche « grand public » utilisent, dans leur algorithme de classement, un sous algorithme basé sur la popularité des liens (link popularity). Ces algorithmes partent du principe qu’il faut classer en tête des résultats de préférence des pages « populaires », c’est à dire des pages vers lesquelles pointent de nombreux liens hypertextes. En plus, plus les pages d’où émanent ces liens sont elles mêmes populaires, plus la note de la page liée sera importante.

Ces algorithmes sont donc basés sur un calcul itératif.

Il existe deux grandes familles d’algorithmes basés sur la popularité des liens : le pagerank (de Google) et l’algorithme HITS (utilisé par Teoma, ou par IBM).

Ces algorithmes analysent les liens au niveau des pages : c’est la note de la page entière d’où provient le lien qui transmet une partie de sa valeur à la page liée…

Quelques articles du Hub pour en savoir plus sur ces algorithmes :

Sur le pagerank
L’algorithme du PageRank expliqué par Dan HETZEL
L’algorithme du PageRank expliqué – 2ème partie par Dan HETZEL
Le PageRank par l’exemple par Dan HETZEL

Sur HITS
L’algorithme HITS et le projet CLEVER par Philippe YONNET
L’algorithme HITS et le projet CLEVER (deuxième partie) par Philippe YONNET

Les failles théoriques des algorithmes basées sur l’analyse des liens

Les algorithmes d’analyse des liens sont tous basés sur deux hypothèses :
-les liens sont une indication qu’un humain accorde de la valeur à une page… Si une page A contient un lien vers une page B, et que ces deux pages ont été créées par deux personnes différentes, c’est le signe que l’auteur de A juge la page B intéressante. Et si l’avis de A est celui d’une personne « autorisée », alors la page B doit se voir accorder une importance plus grande encore.
-si deux pages sont « co-citées » par une même page, alors ces deux pages parlent probablement du même sujet… (hypothèse sous jacente dans l’algorithme HITS)

Or il s’avère que ces deux hypothèses sont fausses dans bien des cas…

La première hypothèse résulte d’une analogie avec les systèmes de calcul utilisés en bibliométrie pour évaluer la popularité des articles scientifiques (analyse des citations). Le problème c’est que les pages web contiennent de plus en plus de liens automatiques, et que nombre de liens sont liés à des objectifs publicitaires ou commerciaux, et ne présagent pas de la « pertinence » réelle accordée par l’auteur de la page aux pages liées. Sur une même page, on aura donc des liens « artificiels », qui n’ont pas d’autres auteurs qu’une machine, un logiciel, et des liens réellement construits à la main par un auteur… Par chance, le plus souvent, ces liens ne sont pas mélangés mais apparaissent dans des « zones » de la page différentes et identifiables.

L’existence de ces zones conduit également à des erreurs flagrante, si l’analyse des co-citations se fait au niveau des pages , en associant à la même thématique des pages au contenu totalement différent !

Les chercheurs de Microsoft ont donc décidé de voir s’il était possible de faire une analyse des liens, non plus au niveau de la page, mais à un niveau inférieur, pertinent sémantiquement : le « bloc sémantique ».


La définition d’un bloc sémantique

La première tâche importante consiste à identifier les « blocs sémantiques » différents sur une page. Pour cela, les chercheurs de Microsoft utilisent l’algorithme VIPS (VIsion-based Page Segmentation) : Segmentation de la page sur critères visuels. Il s’agit d’extraire la structure d’une page en se basant sur des informations donnée par sa présentation visuelle (en fait le code HTML de la page). Le résultat est une structure arborescente, dans laquelle chaque noeud constitue un bloc. Les blocs se voient attribuer un « degré de cohérence », qui permet de déterminer à quel point le bloc en question est clairement séparé des autres blocs.

A ce stade, il est possible d’éliminer le « bruit de fond » sémantique, en identifiant les blocs de navigation, les publicités, et les éléments de décoration, qui sont en général facilement reconnaissables.

Analyse des liens au niveau des blocs

Une fois les blocs identifiés, il reste à analyser les liens qu’ils contiennent, et la manière dont les blocs relient les pages entre elles…

Cela signifie que l’on ne va plus utiliser un graphe de relations « page à page », mais « bloc à page » et « page à bloc ».

La relation « bloc à page » identifie le fait qu’un bloc sémantique contient un lien vers une page donnée (c’est une page entière, en l’absence d’ancre, un lien émanant d’un bloc pointe vers une page entière, et ne donne pas d’indication sur la partie de la page qui est « visée » par le lien).

La relation « page à bloc » identifie l’appartenance des blocs à une page donnée.

A partir de ces graphes de relations, les algorithmes HITS et Pagerank restent utilisables sans modification majeures : on obtient deux algorithmes dérivés, le BLPR (Block Level Page Rank) d’une part, et le BLHITS (Block Level HITS d’autre part).

Est-ce une idée originale ?

Non, pas vraiment. Le problème de la co-citation a été identifié dès les premiers balbutiements de HITS, et des approches très similaires ont été développées par d’autres chercheurs pour cet algorithme (notamment par l’équipe de Chakrabarti).

D’autres ont eu le même genre d’idées pour le Pagerank, mais ce sont plutôt les approches inverses, comme le blockrank, qui ont été privilégiées. Le blockrank est une technique d’analyse des liens qui identifie des groupes de pages. Pour accélérer le calcul des pageranks, on calcule un pagerank sur la matrice des liens internes à ce groupe de pages, puis sur la matrice des liens externes entre ces groupes de pages. Ce qui permet de travailler sur des matrices de taille réduites. [1]

Or, avec le BLPR, la matrice enfle d’un seul coup dans des proportions gigantesques. Ce qui signifie que la puissance de calcul nécessaire augmente aussi dans des proportions impressionnantes…

Cet algorithme est-il réellement utilisé dans MSN Search ?

Difficile à dire. Les sous-algorithmes basés sur la popularité des liens ne sont que l’un des nombreux critères utilisés pour classer les pages. Il est donc difficile d’isoler les effets de tel ou tel algorithme. L’un des avantages de l’analyse au niveau des blocs sémantiques, c’est d’identifier facilement une certaine proximité thématique entre les pages… Mais d’autres outils de linguistique statistique, utilisés depuis belle lurette dans les moteurs permettent d’aboutir à des résultats similaires. Donc, tant que quelqu’un de chez MSN n’aura pas lâché l’info, on ne pourra pas vraiment l’affirmer.

Cet algorithme donne-t’il un avantage concurrentiel à MSN ?

La réponse est clairement : non ! L’amélioration obtenue en termes de pertinence est réelle, mais marginale car comme d’habitude noyée dans les autres critères. Et il existe de nombreuses autres approches qui permettent d’améliorer la pertinence sans utiliser l’analyse des liens.

Bref, cette nouvelle approche dans l’analyse des liens est intéressante à connaître, mais il ne faut pas forcément en conclure qu’elle est réellement déjà implémentée dans l’algorithme de MSN Search. Et si l’algorithme « block level analysis » est utilisé, c’est peut-être sous une forme différente ou dérivée.

En tout cas, à ce stade de nos connaissances, il serait imprudent de considérer qu’il faille absolument prendre en compte les blocs pour optimiser ses pages pour le moteur MSN Search …

Philippe YONNET

Liens utiles :

MSN Search

La discussion sur Searchenginewatch.com

Bibliographie

Block-level Link Analysis par Deng Cai1* Xiaofei He2* Ji-Rong Wen* Wei-Ying Ma* – Microsoft Research/Juin 2004

Block based web search – Deng Cai ; Shipeng Yu ; Ji-Rong Wen ; Wei-Ying Ma – Microsoft Research/ Juin 2004

(ces deux articles ne sont plus accessibles : ne me les demandez pas, Microsoft les a retirés de son site pour certainement de bonnes raisons, que je respecte).


[1] Le blockrank est évoqué dans cet article :
Vers un moteur de recherche sensible au contexte (1ère partie)