Débattre

Un moteur de recherche, pour le meilleur et pour le pire

L'ensemble des pages web disponibles constitue une base d'informations que nous apprenons à parcourir, à exploiter et même à truquer...

Nous sommes en train de faire une expérience nouvelle : un ensemble de données d'une taille incroyablement supérieure au volume de tous ceux dont nous avons pu disposer jusqu'à présent est accessible instantanément grâce à Internet. En glissant nos doigts sur le clavier d'un ordinateur relié au réseau des réseaux, nous faisons apparaître sur l'écran de notre machine une page web (composée de textes et d'images) choisie parmi une quantité inouïe de documents électroniques, physiquement localisés sur les ordinateurs du monde entier.

Bien sûr, pour s'y retrouver, des outils sont nécessaires. Vous pouvez noter les adresses des pages qui vous sont utiles, mieux, vous pouvez stocker ces adresses et les organiser en tenant compte de vos critères propres : ce sont les systèmes de signets (bookmarks). Vous pouvez aussi télécharger les pages qui vous intéressent le plus et les ranger dans des dossiers de votre ordinateur, dossiers que vous classerez en les emboîtant ; cela constituera une bibliothèque personnelle électronique que vous compléterez en suivant les liens contenus dans ces pages stockées. En théorie, on se débrouille par de tels moyens artisanaux, et, au début du web, chacun travaillait ainsi.

Qu’est-ce qui a changé ? Les moteurs de recherche ! Ils vous dispensent presque totalement des signets et des téléchargements. Si vous voulez connaître les rapports entre deux personnages que rien ne rassemble, tapez dans le moteur de recherche Einstein + Marilyn Monroe, les réponses vous surprendront.

Premiers résultats obtenus pour la requête Einstein + Marilyn Monroe (le 29 janvier 2007).

Ces moteurs de recherche ont bouleversé l'usage du web et ont contribué à son succès. Leur fonctionnement se fonde sur des milliers d'ordinateurs stockant des copies des pages les plus importantes, et constituant de volumineux index qui permettent de savoir sur quelle page et à quel endroit dans la page se trouve tel mot, ainsi que des informations associées, dont la très importante « note de notoriété » de chaque page.

Grands nombres

Aucun moteur de recherche ne réussit à tout stocker et traiter. C'est d'ailleurs impossible, puisque certaines pages dynamiques changent de contenu toutes les heures, voire toutes les secondes, et que d’autres sont engendrées à la demande. Le moteur de recherche Google annonçait en 2005 qu'il traitait 8 milliards de pages (8 168 684 336, le 4 septembre 2005), ce qui est beaucoup, surtout qu'une page web contient souvent plus d'informations qu'une page de livre ou de journal. Depuis lors, Google ne publie plus de chiffres aussi précis, mais revendique toujours plus de 8 milliards de pages indexées.

Préparation des données de Google.
La collecte des données se fait en permanence et incrémente le contenu des mémoires des milliers d'ordinateurs de la société Google. Ce contenu définit un graphe où chaque page est représentée par un point et est reliée par les liens indiqués sur chaque page. Pour attribuer la note de notoriété de chaque page, on imagine un surfeur aléatoire passant de page en page en procédant selon les règles suivantes. Dans 15 pour cent des cas, et aussi lorsque la page ne contient pas de lien vers une autre page, il choisit au hasard une page parmi toutes les pages possibles et retravaille à partir de celle-là. Dans les autres cas, il choisit au hasard un des liens de cette page, clique dessus et se rend à la page citée. Le PageRank théorique de la page P est la probabilité pour que le surfeur aléatoire se trouve sur cette page P et cette probabilité est une mesure fine de notoriété.
Infographie : Pour la Science

Parmi les idées utilisées pour faire fonctionner les moteurs de recherche, celle à l'origine du PageRank (pour déterminer la notoriété d'une page) est remarquablement simple et efficace. Cet algorithme révolutionnaire a fait le succès du moteur de recherche de la société Google. Tout le monde est concerné par son fonctionnement. On ignore si cet algorithme a été nommé PageRank parce qu'il note les pages web et donc permet de les ranger, ou s'il doit son nom à l'un de ses inventeurs, Larry Page. Avec l'autre inventeur, Sergey Brin, ils fondèrent la société Google en septembre 1998, alors qu'ils préparaient une thèse en informatique à l'Université Stanford en Californie. Leur thèse, jamais terminée, portait sur le PageRank qui est aujourd'hui breveté et constitue un nom déposé.

Le nom Google quant à lui provient du mot googol introduit par Edward Kasner pour désigner le nombre 10100 (un 1 suivi de 100 zéros). L'immeuble du siège Californien de la société porte le nom de Googleplex, un googleplex étant le nombre 10googol, c'est-à-dire un 1 suivi de un googol de zéros. Le succès du moteur de recherche Google est tel qu'un nouveau verbe a été créé en anglais pour désigner son utilisation : to google.

Sélectionner, puis ranger

Lorsque vous interrogez le moteur de recherche de Google, par exemple avec les mots Enigma Turing, il détermine toutes les pages (parmi celles que ses robots d'exploration ont visitées et qui sont stockées par la société Google) qui comportent les deux mots Enigma et Turing. (Notons que les majuscules n'ont pas d'importance pour Google.) Il trouvait ainsi 77 000 références le 4 septembre 2005, et le 29 janvier 2007 à Paris, environ 491 000.

L'ordre dans lequel Google affiche ces pages pertinentes pour répondre à votre interrogation dépend de nombreux facteurs, mais les deux principaux sont, d'une part, la proximité des mots recherchés dans le texte et, d'autre part, la note qui a été attribuée à chaque page par l'algorithme PageRank. Plus les mots sont proches dans une page, plus elle a de chances de se retrouver bien placée parmi les réponses retenues, mais parmi toutes les pages comportant Enigma et Turing rapprochées (elles sont très nombreuses), PageRank fixe l'ordre des réponses. On comprend l’importance du classement : pour qu'une page soit proposée dans le premier écran de résultats, il faut qu'elle soit bien notée par PageRank.

Recherche des sites pertinents
Lorsque l'on interroge le moteur de recherche Google pour trouver les pages contenant une série de mots, un calcul est opéré comportant deux phases.
1. La recherche des pages répondant à la requête, c'est-à-dire contenant effectivement les mots recherchés. Ce travail est effectué grâce à d'énormes index informatiques (analogues aux index des livres) qui ont été calculés à l'avance après l'opération mensuelle de parcours du Web par les robots logiciels de Google en charge de télécharger tout ce qu'on peut trouver.
2. La classification des pages retenues qui fait apparaître en tête les pages les plus intéressantes. Pour cette classification, les deux principaux facteurs pris en compte sont la proximité des mots recherchés dans les pages retenues, et la notoriété des pages. Celle-ci a été calculée à l'avance par l'algorithme PageRank mis au point par les créateurs de Google en 1998.
Infographie : Pour la Science

L'évaluation de la note est fondée sur un principe de vote démocratique et sur ce que l’on désigne par le modèle du surfeur aléatoire. Ces deux idées garantissent à la fois la pertinence des résultats et une certaine robustesse aux tentatives de manipulations. L'évaluation de notoriété produite par PageRank est calculée grâce à une astuce que nous allons voir, classant les quelque 8 milliards de pages prises en compte.

Objectivité ?

Avant de détailler le principe et le calcul pratique de PageRank, précisons que lorsque l'on interroge Google sur un mot ou une liste de mots, il répond de manière « objective » par une liste de liens placés à gauche sur la page de résultats et qu'il n'est pas possible d'acheter une bonne place sur cette liste en payant Google. Selon les propres mots de la firme : « Google ne pratique pas la vente des positions dans les résultats : il est impossible d'acheter une valeur PageRank supérieure à la réalité du Web. Avec la recherche Google, vous disposez d'une solution simple, rapide, honnête et objective pour trouver des sites Web dont les informations répondent à vos besoins ».

En revanche, les liens affichés à droite, de même que certains placés en haut sur fond grisé, sont des liens commerciaux, pour lesquels il faut payer, et ce sont eux qui permettent à Google de gagner de l'argent. (Ces liens sont peu nombreux en général : il n'y en a pas si vous interrogez Google sur Turing seul ; il y en a un si vous l'interrogez sur Enigma.) Cette « objectivité » des réponses principales de Google est sans doute un élément important de son succès, mais aujourd'hui rien ne la garantit : Google affirme qu'aucun critère commercial n'entre en ligne de compte dans l'affichage des réponses principales qu'il affiche, mais personne, sauf lui, ne peut le vérifier. Nous reviendrons sur ces aspects éthiques, traités de manière insatisfaisante à l'heure actuelle.

Le PageRank d'une page est un nombre qui mesure sa notoriété. En principe, il s'agit d'une probabilité, donc d'un nombre entre 0 et 1 ; cependant, ce nombre peut être, par commodité, multiplié par un facteur constant positif, on peut aussi en prendre le logarithme ou effectuer d'autres transformations, pourvu qu'elles ne changent pas l'ordre des classements.

Le surfeur aléatoire est un utilisateur imaginaire du web, qui va de page en page, toujours en avant (c'est-à-dire sans jamais utiliser le bouton de « retour à la page précédente ») et qui, lorsqu'il affiche une page, choisit pour aller à la suivante un lien au hasard sur la page affichée : il choisit en tirant au sort l'un des liens présents sur la page courante, sans en favoriser aucun. Lorsque la page affichée est une page sans lien, une page « cul-de-sac », le surfeur choisit au hasard une page parmi les milliards de pages disponibles et reprend sa promenade aléatoire.

De plus, pour éviter que le surfeur aléatoire reste dans une même zone de l'espace web, à chaque nouvelle page, le surfeur, avec une probabilité fixée à l'avance, appelée le coefficient d'échappement (en général 0,15), choisit une nouvelle page parmi toutes les pages possibles. Un tel surfeur imaginaire qui parcourt indéfiniment le web passera plus de temps sur les pages citées par un grand nombre de pages, et moins sur les autres. Cette proportion de temps passée sur une page donnée est le PageRank théorique de la page (nous le nommons PageRank théorique, car celui calculé diffère en plusieurs points de celui de la théorie).

À ce modèle correspond une formule reliant le PageRank d'une page à celui des pages qui ont un lien vers elle, mais avant d'expliquer cette formule tirons un certain nombre de conséquences de la définition.

Démocratie dans le cyberespace

Le principe d'attribution de cette valeur de notoriété est fondé, non pas sur une notation humaine ou sur l'observation du nombre de fois qu'une page a été réellement consultée (ces deux éventualités sont impossibles à mettre en œuvre), et il concerne chaque page et non chaque site web : les pages d'un même site peuvent avoir des PageRank très différents. Même si une page n'est jamais visitée par les internautes, elle peut avoir un bon PageRank ; pour augmenter le PageRank de votre page personnelle, ne perdez pas votre temps à l'ouvrir dix fois par jour !

Une autre conséquence importante de la définition de PageRank est que le contenu des pages, à l'exception des liens qui y apparaissent, n'a aucune importance pour sa notation et que cette notation est globale : toute la structure des référencements des huit milliards de pages intervient dans le PageRank théorique et non pas seulement les pages proches (à quelques clics de celle à laquelle vous vous intéressez).

L’indifférence de PageRank relativement au contenu de la page a parfois été mal comprise. Elle ne signifie pas que les pages affichées en réponse à une question posée à Google sont sans rapport avec le contenu général de la page, car, bien sûr, pour qu'une page soit affichée en réponse à une requête, il faut avant tout qu'elle contienne les mots voulus (PageRank n'intervient qu'après la présélection des pages pertinentes). De plus, c'est en fonction du contenu de votre page que ceux qui réalisent de nouvelles pages la mentionneront ou non : il importe donc que les mots importants liés au sujet de votre page y apparaissent... et que votre page soit intéressante !

En consultant le site Google PageRank Calculator, vous aurez une idée du PageRank des pages qui vous intéressent, mais un tel outil est fondé sur ce que Google accepte de dévoiler ; le PageRank que Google rend public est un nombre entier entre 0 et 10 qui, d'après les spécialistes, est une approximation du logarithme du PageRank théorique et non le PageRank lui-même.

Début de la liste des sites ayant un PageRank de 10 affichée sur le site Search Engine Genie (janvier 2007).

Les pages qui ont la note de 10 sont indiquées sur le site Search Engine Genie. Parmi ces pages, on note celles de la NASA, du MIT, de Harvard, de Apple, de Microsoft, de Adobe, du New York Times et de… Google !

Principe mathématique du surfeur aléatoire

L'étude du surfeur aléatoire se ramène à un problème mathématique assez classique rattaché à la théorie des processus de Markov. Elle conduit à la formule suivante que nous allons examiner.

Si p est une page dont l'adresse apparaît dans les pages p1, p2,…, pi alors le PageRank Pr(p) de p est lié aux PageRank Pr(p1), Pr(p2),…, Pr(pi) de p1, p2,…, pi par cette formule, qui fait aussi intervenir K le nombre total de pages pris en compte, e le coefficient d'échappement (0,15 généralement), et NL(pm) le nombre de liens total vers d'autres pages que contient la page pm (qui, par hypothèse, contient un lien vers p) :
Pr(p) = e/K + (1 – e) [Pr(p1)/NL(p1) +  Pr(p2)/NL(p2) + … + Pr(pi)/NL(pi)].

Cette formule est riche d’informations. D'abord, PageRank est un « bien » que chaque page distribue aux pages qu'elle cite : si une page en cite beaucoup, elle ne transmet à chacune qu'une faible partie de sa richesse ; si elle en cite peu, elle les enrichit plus. Ainsi, 15 % de votre PageRank sera équitablement transmis aux milliards d’autres pages qui, puisqu'elles sont très nombreuses, recevront individuellement très peu de ces 0,15 (c'est l'idée que le surfeur aléatoire avec une probabilité de 0,15 choisit de s'échapper sur une page prise au hasard). Pour les 85 % restant, si vous ne citez qu'une page, ils iront vers elle ; si vous en citez deux, ils seront partagés et iront pour moitié à chacune. Plus généralement : si votre page possède NL liens, chacune des pages citées recevra 0,85/NL du PageRank de votre page.

En clair, chaque page vote pour les pages dont elle mentionne l’adresse et reçoit des votes de toutes les pages qui la mentionnent. Son vote pour une autre page a une force proportionnelle à son PageRank et inversement proportionnelle au nombre de pages qu'elle mentionne.

Une page p donnée peut avoir un très gros PageRank théorique même si elle n'est citée que par une seule page q, à condition que q soit très populaire et que cette page q ne cite que très peu de pages. À l'autre extrême, une page peut être très populaire parce qu'elle est citée par un très grand nombre d'autres pages, même si aucune des pages qui la citent n'a un fort PageRank. La détermination du PageRank théorique s'apparente à un super-jeu de démocratie se mordant la queue : chaque page vote, et l'ensemble de tous ces votes, y compris ceux du type « A vote pour B qui vote pour A », fixe la notoriété de chacune.

Huit milliards d'électeurs

Pour calculer le PageRank théorique, l'idée la plus naturelle est de résoudre simultanément toutes les équations qu'on tire de la formule indiquée. Si vous voulez traiter 8 milliards de pages, cela fait 8 milliards d'équations avec 8 milliards d'inconnues. Cela semble beaucoup, mais une méthode, fondée sur une idée simple, y parvient : elle donne au départ à chaque page la même richesse – le même PageRank –, et fait circuler cette richesse plusieurs fois de suite en suivant les liens entre les pages. Petit à petit, les richesses de chaque page convergent vers les valeurs correspondant à la solution du système des huit milliards d'équations.

On commence par distribuer équitablement à chaque page un PageRank de 1/K ; K est le nombre total de pages ; le total distribué est donc 1. En utilisant (huit milliards de fois) la formule écrite au-dessus, on recalcule un nouveau PageRank pour chacune des pages (la formule est utilisée de la droite vers la gauche) : chaque page fait passer 0,15/K de son PageRank aux autres pages et 0,85/NL de son PageRank à chacune des NL pages qu'elle cite – c'est son vote. En même temps, elle reçoit un nouveau PageRank en totalisant ce que les pages qui votent pour elle lui transmettent.

Le total distribué au départ faisait 1, après une étape, il fait encore 1, car chaque page a distribué exactement ce qu'elle avait, ni plus ni moins (conservation du PageRank total lors d'une étape de calcul). On recommence une seconde étape, une troisième, etc. Assez rapidement, les valeurs obtenues pour chaque page ne varient presque plus d'une étape à la suivante, et l'ensemble de ces valeurs vérifie les équations données. À chaque étape, la somme de tous les PageRank est 1, et quand tout est stabilisé, la somme de tous les PageRank est encore 1, résultat interprétable comme une probabilité (les valeurs calculées sont les probabilités de localisation de l'infatigable surfeur aléatoire).

Quelle est la méthode vraiment utilisée ?

Malheureusement quand, chaque mois, Google renouvelle toutes les pages prises en compte et en met à jour le PageRank, il n’utilise sans doute pas exactement la méthode décrite, et cela pour plusieurs raisons.

D'abord, vouloir que la somme de tous les PageRank fasse 1 est un souci de mathématicien, et une formule plus simple à utiliser que la formule théorique est mentionnée dans les documents publiés par L. Page et S. Brin en 1998. Cette formule publiée ne conduit pas à une répartition de probabilité, et elle est considérée comme fausse par certains analystes : on se demande même si elle n'était pas volontairement erronée pour tromper ceux qui auraient voulu prendre de vitesse les fondateurs de Google en 1998. Une formule légèrement différente de celle indiquée plus haut est souvent associée au PageRank de Google sur les sites web consacrés au sujet. C'est sans grande importance pratique, car la formule fausse donne un résultat assez proche de ce que donnerait la formule correcte du surfeur aléatoire. Il est néanmoins dommage qu'une confusion entache la définition du cœur même de l'algorithme du PageRank !

La deuxième raison de l'écart entre PageRank théorique et PageRank réel est que des ajustements ad hoc sont utilisés par Google pour corriger certains problèmes rencontrés et pour masquer sa véritable valeur.

  • Certaines pages sont délibérément notées 0 par Google (ou notées très bas) parce qu'il considère qu'elles tentent de tricher. Toutes sortes d'ajustements sont opérés par Google pour contourner ceux qui veulent augmenter artificiellement le PageRank de leurs pages.
  • Le calcul, chaque mois, des nouveaux PageRank ne démarre sans doute pas avec toutes les valeurs de PageRank égales à 1/K, mais réutilise les résultats précédents de façon à obtenir une convergence plus rapide. On évoque aussi l'idée que dans la formule, e/K pourrait être remplacé par un paramètre dépendant de la page p, ce qui permettrait d'ajuster le calcul en prenant en compte la nature de la page ou certaines de ces caractéristiques.
  • Le PageRank rendu public par Google n'est pas le vrai PageRank, mais quelque chose ressemblant au logarithme d'un multiple de PageRank, le tout arrondi pour produire un nombre entier entre 0 et 10. Google ne donne pas de précision sur ces changements.

La situation est donc curieuse et incontrôlable. Elle est scientifiquement malsaine et fait apparaître que la vérité et son approfondissement sont incompatibles avec les soucis commerciaux des grosses sociétés du web. L'idée du PageRank est un principe de démocratie parfaite (c'est pour cela que l'ordre des réponses est souvent si pertinent), mais le secret qui entoure sa mise en œuvre par Google contredit ce principe. Google devrait donner exactement le détail de ce qu'il calcule, ce qui ne serait pas trop dangereux, car décrire ce que l'on calcule ne force pas à dire comment on le calcule.

Le goût injustifié du secret

Pour justifier le secret qui entoure la définition exacte de ce que calcule Google, on argumente qu'il empêche ou limite les tricheries menées pour obtenir artificiellement un bon PageRank. Cet argument ne tient pas, car comme l'a montré Andrew Clausen et comme on le constate en pratique, PageRank est robuste aux tentatives de tricherie : on peut parfois fausser les résultats du PageRank par la création de pages ou de liens artificiels (le Google Bombing), mais il en faut beaucoup, et cela est donc coûteux. Même si Google souhaite adopter des contre-mesures pour empêcher ou décourager certaines pratiques, rien n'interdit de rendre publiques ces contre-mesures qui pourront évoluer ! Le Droit s'adapte pour prendre en compte l'évolution de la délinquance et personne n'en déduit que la loi doit être secrète.

La vérité est sans doute que Google, en ne donnant pas la définition de ce qu'il calcule, se protège à bon compte des objections qu'on pourrait formuler à propos de PageRank. L'approximation qu'il met en œuvre est sujette à des imperfections qui pénalisent certaines pages, dont les propriétaires risqueraient de se plaindre s'ils étaient informés. Google traite certains problèmes par des complications dont l'efficacité est sans doute discutable, alors que si sa spécification était publique, il devrait traiter les difficultés par un approfondissement et des versions plus propres du PageRank, dont la théorie devrait être perfectionnée. C'est confortable de n'avoir aucune justification à donner !

Notons aussi qu'on a certaines raisons de douter de l'honnêteté de Google. L'exemple le plus flagrant d'une manipulation que Google effectue sur ses résultats est le nombre de liens qu'il affiche avoir trouvé en réponse à une requête. D'une part, ce nombre est invérifiable, puisque Google refuse d'afficher les pages au-delà de la millième. D'autre part, ce nombre est clairement exagéré à la hausse : essayez par exemple « the », « us » ou « Washington ».

Ce nombre est aussi manifestement délibérément biaisé dans le cas des requêtes du type "Jacques Dupont" (un prénom suivi d'un nom, le tout placé entre " "), car pour ce type de requêtes, on obtient toujours un résultat inférieur à 1 100 ou supérieur à 9 000, comme si, au-delà d'un certain seuil, Google multipliait par 9 ou 10 le résultat affiché, dans le but de faire croire qu'il indexe plus de pages qu'il n'en indexe en réalité... et pour faire plaisir à Jacques Dupont.

Une analyse des incohérences inquiétantes de Google est donnée par Jean Véronis : Le mystère des pages manquantes de Google résolu, mais vous pouvez aussi trouver d'autres informations en demandant à Google « Google cheating », requête pour laquelle Google prétendait le 31 janvier 2007 disposer de 1 410 000 pages pertinentes ! Il est ainsi à peu près certain que même lorsqu'il annonçait 8 milliards de pages, Google n'en stockait la copie que d'une partie.

La firme Google détient un pouvoir considérable en choisissant elle-même les spécificités de ses algorithmes, et il serait normal que chacun soit informé sur ses méthodes, qui sont imposées dans la plus grande opacité et le plus total arbitraire aujourd'hui. Google juge chaque page, cela a parfois des conséquences graves pour les individus et les sociétés commerciales dont le succès dépend directement du PageRank que Google leur attribue : il est donc nécessaire que soit rendue publique la méthode de classement. Chacun a le droit de savoir selon quelles lois on le juge. Même s'il est vrai que la façon la plus efficace pour avoir un bon PageRank est simplement d'être un bon site que tout le monde souhaite référencer, la notation secrète produite par Google est en contradiction avec le génial principe d'équité totale du surfeur aléatoire.

Améliorer le fonctionnement du calcul de notoriété ?

Deux solutions sont possibles pour rétablir un fonctionnement satisfaisant du calcul de notoriété qu'opèrent les moteurs de recherche.

  • La première solution s'appuie sur le marché, qui devrait à la longue forcer la transparence : les internautes préféreront utiliser les moteurs de recherche qui rendent publiques leurs spécifications plutôt que les boîtes noires qu'on peut truquer et manipuler à l'insu de tous. Déjà de nombreux internautes se plaignent du comportement lunatique du PageRank de Google. La naissance de nouveaux concurrents plus clairs, la remontée d'anciens concurrents devenus soucieux de transparence, ou même un changement de comportement de la part de Google ne sont donc pas exclus… si le marché fonctionne bien.
  • Si les marchés ne déclenchent pas le miracle attendu, la seconde solution sera la réglementation. Quand les enjeux auront été évalués trop importants pour laisser l'arbitraire d'une société commerciale décider ce qui a de la valeur et ce qui n'en a pas, on peut imaginer l'adoption de lois obligeant la publication des spécifications des moteurs de recherche du web et organisant le contrôle du respect de ces spécifications. Une telle solution est certes difficile à mettre en œuvre et ne le sera vraisemblablement pas dans l'immédiat, mais est-ce si absurde, puisque dans bien d'autres secteurs de la vie sociale et de l'économie, la transparence est exigée par la loi (revenu des particuliers, données économiques des sociétés, etc.) ?

Une première version de ce document est parue sous le titre « Démocratie et notoriété sur Internet » dans la revue Pour la Science n°337 en novembre 2005.

Tags

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).