Jean Véronis
Aix-en-Provence
(France)


Se connecter à moi sur LinkedIn Me suivre sur Twitter Facebook RSS

jeudi, août 18, 2005

Yahoo: Pages manquantes? (3)



La polémique autour de la taille de l'index Yahoo s'amplifie. Même le New York Times s'y met. L'étude très détaillée [version originale] des chercheurs du NCSA, dont je parlais ici, semble apporter de l'eau au moulin des sceptiques en concluant à la supériorité numérique de l'index de Google. J'ai montré toutefois dans les deux parties précédentes [ici et ici] que cette étude était entachée d'erreurs méthodologiques qui invalident totalement ses conclusions. Dans cette troisième partie, je montrerai que ses hypothèses mêmes sont erronées.



Comme je le mentionnais en fin de mon dernier billet, les auteurs du NCSA supposent que les moteurs ne font aucun filtrage (par exemple pour éliminer des sites de spam) et retournent tous les résultats contenus dans leur index sur chaque requête. Dans le cas contraire, il ne serait pas légitime d'extrapoler les résultats obtenus sur de petites fréquences (moins de 1000) à l'ensemble de l'index, car le filtrage ne serait certainement ni proportionnel au nombre de résultats, ni identique pour chacun des moteurs comparés. Or tout porte à croire que les moteurs opèrent un tel filtrage.

De nombreux internautes ont ainsi observé un comportement apparemment étrange de Yahoo. Par exemple, Béatrice dans un commentaire sur ce billet nous explique que lorsqu'on tape une requête comme "azoïque", Yahoo donne un premier nombre de résultats sur la première page (2380), puis révise ce chiffre à la baisse dans les pages de résultats suivantes, et au final on n'obtient qu'un nombre très inférieur (576, en étendant la recherche aux résultats similaires).

J'ai testé Yahoo sur des mots dans une large gamme de fréquences, et ce comportement est systématique. La perte augmente au fur et à mesure que la fréquence diminue:


On peut bien sûr imaginer que ce comportement soit dû à un bug, ou à une tentative de manipulation des données, mais c'est si visible que j'ai peine à croire que les ingénieurs de Yahoo soient aussi négligents. Un phénomène analogue (mais moins marqué) affecte d'ailleurs Google. L'hypothèse la plus probable est justement celle d'un filtrage des résultats à chaque requête pour éviter des pages indésirables, et notamment du spam.

Le spam gangrène le web, et les moteurs font de gros efforts pour le contrer, car il peut dégrader de façon importante la pertinence des résultats. Il y a deux façons complémentaires pour lutter contre ce fléau:
  • détecter que le document ou le site est du spam lors de l'indexation et l'exclure de l'index;
  • tenir à jour une "blacklist" qui permet d'exclure les URL reconnues comme spammeuses après que l'index ait été calculé.
Cette deuxième technique est particulièrement intéressante, car elle permet une réactivité importante et une mise à jour dynamique sans que l'index ait à être recalculé et propagé sur tous les serveurs du moteurs. C'est à mon sens ce mécanisme de filtrage que nous voyons à l'oeuvre dans les "disparitions" de pages constatées.

Le moteur ne filtre évidemment pas tous les résultats en fonction de la blacklist pour une requête donnée! Si l'utilisateur demande 10 résultats, il suffit d'appliquer la blacklist sur le début des résultats jusqu'à l'obtention de 10 résultats valides. Si l'index contient n résultats, et qu'on a dû en éliminer m, on peut déjà par une simple règle de trois afficher une estimation du nombre total de résultats après filtrage, soit 10 n / (10 + m). La grande majorité des utilisateurs ne demandent jamais le deuxième écran de résultats. Mais s'ils le font, on ré-applique le même mécanisme, et on a alors une estimation améliorée. Sachant qu'on a éliminé au total m' documents, on peut afficher la nouvelle estimation 20 n / (20 + m'). Et ainsi de suite. Simple comme bonjour. Bien sûr, les moteurs utilisent certainement des fonctions plus compliquées que la règle de trois, car la proportion de spam n'a aucune raison d'être constante au fil des écrans de résultats: le classement par pertinence implique même qu'il y ait moins de spam dans le haut du classement.

C'est exactement le mécanisme que nous voyons à l'oeuvre chez Yahoo et Google. Le fait que la proportion de pages filtrées diminue avec la fréquence du mot-clé est tout à fait logique. Deux facteurs y contribuent. D'une part les sites de spam utilisent massivement des dictionnaires et des listes de mots aléatoires pour fabriquer des textes artificiels qui essaient de flouer les moteurs. Ce faisant, ces textes artificiels utilisent une proportion de mots peu fréquents bien supérieure à la normale. Par ailleurs, le principe de classement des résultats par pertinence implique sur les requêtes à haute fréquence que le sommet de la liste n'est probablement pas du spam, comme je le mentionnais à l'instant.

Le plus étonnant est que les résultats publiés par les chercheurs du NCSA eux-mêmes montrent très clairement ce filtrage! Dans leur table 3, ils montrent que le pourcentage de résultats réels retournés par Yahoo sur leur ensemble de requêtes n'est que de 27% (soit 73% de filtrage), contre 92% pour Google (8% de filtrage). Je cite [voir l'étude ici] :

Table Three (n=10,012)


Estimated Search Results (Excluding Duplicate Results)
Total Search Results (Excluding Duplicate Results)
Percent of Actual Results Based on Estimate
Estimated Search Results (Including Duplicate Results)
Total Search Results (Including Duplicate Results)
Percent of Actual Results Based on Estimate
Yahoo!
690,360
146,330
21.1%
821,043
223,522
27.2%
Google
713,729
390,595
54.7%
708,029
651,398
92.0%

Le filtrage appliqué par Yahoo est bien plus important que celui de Google. Sans doute leur blacklist est-elle plus étoffée. De fait, sur ces fameuses requêtes-test, Yahoo retourne beaucoup moins de déchets que son concurrent. C'est plutôt à mettre au crédit du moteur, mais en tous cas, ce mécanisme empêche totalement la moindre extrapolation des résultats observés à la taille globale de l'index. Voilà donc une troisième raison pour laquelle je peux affirmer que les chercheurs du NCSA n'ont rien démontré du tout, si ce n'est que Google indexe très bien le spam, et ispell!

Ces collègues ont dû être bien embêtés de lire mes critiques relayées par le NY Times, et celles d'autres bloggeurs (ici). Pendant que je rédigeais ce billet, Serge Courrier [qui m'interviewait pour 01net] m'a fait remarquer qu'ils ont modifié leur page, et ont enlevé cette réserve méthodologique sur le filtrage. Donc ils se sont rendus compte de leur bourde, mais au lieu d'annuler leur étude (tout le monde peut se tromper, ne leur jetons pas la pierre), ils ont préféré supprimer des précautions méthodologiques qui les honoraient. C'est une façon de faire. Pas celle que j'aurais choisie...


Nouveaux développements

22 aoû -- Les gens du NCSA admettent les erreurs et publient un démenti
23 aoû -- Une nouvelle version de l'étude est mise en ligne

Lire les détails: Yahoo: Pages manquantes? (4)

Libellés :


10 Commentaires:

Blogger J2J2 a écrit...

Les chercheurs du NCSA ont tout de même un mérite: ils ont réellement compté les résultats retournés par Google et Yahoo! plutôt que de se contenter de lire l'estimation fournie par les moteurs sur la première page de recherche comme le font beaucoup "d'études" un peu attives.

Quoi qu'il en soit, Jean, vous illustrez une fois de plus avec brio, qu'il est malheureusement nécessaire de faire du reverse engineering (à la manière d'un hacker) pour tenter de comprendre les résultats fournis pour nos chers moteurs commerciaux!!!

18 août, 2005 13:55  
Blogger Marianne a écrit...

Je suis convaincue. Merci !!

18 août, 2005 14:22  
Blogger Chris a écrit...

C'est un véritable roman policier ici. Encore merci.

Vous expliquez aussi pourquoi j'ai été incapable de reproduire la diminution du nombre des résultats affichés : je règle toujours les options de sorte que le premier écran affiche 100 résultats. La première estimation appliquée est alors déjà plus proche du résultat après-filtrage total.

18 août, 2005 17:59  
Blogger Eric Baillargeon a écrit...

> L'hypothèse la plus probable est justement celle d'un filtrage des résultats à chaque requête...

Ce n'est pas une hypothèse chez Yahoo. Jeremy Zawodny de Yahoo le mentionne clairement dans son billet sur toute cette polémique :
You know, we index those too. But we filter 'em out because they're pretty useless.I'm not sure why Google thinks those are good pages to include, but hey--it boosts the numbers! Our algorithms manage to suppress such pages and I doubt anyone misses them.

Par contre quelques autres observateurs ont tout de même retrouvés ce type de page dans l'index de Yahoo !

18 août, 2005 19:51  
Anonymous Anonyme a écrit...

"si ce n'est que Google indexe très bien le spam, et ispell!" Ou encore que Google ne donne pas les pages filtrées dans le total de résultat, contrairement à Yahoo qui les retire à postériori.

19 août, 2005 12:07  
Blogger Jean Véronis a écrit...

Olivier G.> Google ne donne pas les pages filtrées dans le total de résultat, contrairement à Yahoo qui les retire à postériori Les deux moteurs filtrent a priori et a posteriori. Mais google laisse passer beaucoup plus de spam (et de copies d'ispell) que Yahoo.

19 août, 2005 12:16  
Anonymous Anonyme a écrit...

Il reste quand même une réserve dans l'histoire...
Je reprends le test sur "azoïque".
Sur une requête normale j'obtiens 2480 résultats. Mais lorsque je lui dit d'afficher 100 résultats par page, il n'en reste plus que 2390. Et comble d'illogisme, quand sur cette même requête à 100 résultats par page je lui demande d'afficher les résultats omis, il ne reste plus que 2320 résultats!!!
Donc il y a quand même un gros problème de calcul chez yahoo, car le fait d'ajouter des résultats omis ne peut en aucun cas donner un nombre inférieur de résultats...

La copie est donc à revoir pour tout le monde : yahoo pour ses calculs, et les observateur pour leurs commentaires. Il ne s'agit pas seulement d'une question de filtrage, il ne s'agit pas non plus d'un bluf sur la taille de l'index. Il s'agit aussi d'une incohérence totale du choix des résultats affichés.

19 août, 2005 13:44  
Blogger Jean Véronis a écrit...

Jérome k> Oui, mais attention, dans les deux cas, ce qui apparaît sur la première page est une estimation, pas un nombre exact. Or 1) l'échantillon sur laquelle l'estimation est basée n'est pas le même dans les deux cas (ce que j'appelle m dans mon billet est différent ; 2) la formule d'estimation n'est peut-être pas la même avec et sans duplications (il serait logique qu'elle ne le soit pas).

19 août, 2005 14:02  
Anonymous Anonyme a écrit...

Je travaille comme documentaliste juridique. Je fais des recherches de documents et informations juridiques tous les jours sur le Web et franchement, je continue à trouver les 30 premiers résultats de Google plus pertinents que ceux de Yahoo, dans 9 cas sur 10. Et ça se vérifie dans d'autres domaines que le droit.

Je comprend la conclusion de Jean Véronis, mais attention à ne pas en déduire que la pertinence des résultats de Google est inférieure à celle de Yahoo. Ce n'est pas parce que Google "gonfle" son index avec des pages de spam que pour autant ses 30 premiers résultats ne sont pas pertinents.

20 octobre, 2005 22:26  
Blogger Jean Véronis a écrit...

Emmanuel> Vous avez raison de souligner ce point. La discussion ici ne porte que sur la taille d'index et sur les mots-clés de petites fréquences (sur lesquelles la taille d'index a une incidence manifeste: pas indexé, pas retourné!). Je n'ai à aucun moment pris position sur la pertinence des résultats retournés par Google ou Yahoo sur des mots-clés plus fréquents.

Merci!

21 octobre, 2005 08:58  

Enregistrer un commentaire