De l’algorithme de Google aux billards de Sinaï

Un théorème de Viviane Baladi, médaille d’argent du CNRS 2019

Piste bleue Le 16 avril 2019  - Ecrit par  Pierre-Antoine Guihéneuf Voir les commentaires

La médaille d’argent du CNRS, l’un des plus prestigieux prix scientifiques français, vient d’être décernée à la mathématicienne franco-suisse Viviane Baladi. Spécialiste de systèmes dynamiques, travaillant à Sorbonne Université, Viviane a récemment collaboré avec Mark Demers et Carlangelo Liverani à propos du mélange dans les billards de Sinaï.

Le classement des pages web, ou comment devenir milliardaire en faisant des maths

Milieu des années 90. Deux étudiants en thèse d’informatique à l’université Stanford en Californie planchent sur un nouveau moteur de recherche internet. En quelques mois, ils conçoivent un algorithme de classement des pages web, qu’ils baptisent PageRank, adapté d’une idée de Thomas Saaty pour le classement des journaux scientifiques. Ces deux informaticiens sont Sergey Brin et Larry Page ; le moteur de recherche s’appelle Google... la suite de ce succès, vous la connaissez certainement un peu.

Essayons de reconstruire ensemble le processus qui a permis à ces deux jeunes informaticiens de mettre au point leur algorithme. Mettez-vous à leur place. Vous voulez comprendre quelles pages internet sont les plus pertinentes ; autrement dit vous voulez établir un classement des pages web, de la meilleure à la moins bonne. Première idée : vous pouvez vous dire que les meilleures sont celles qui sont le plus souvent visitées. Pas de bol, vous ne disposez pas des statistiques de visite des pages web (en tous cas pas encore !). Vous devez donc faire avec ce que vous avez sous la main : les liens entre les pages.

L’idée qu’ont eue les deux créateurs de Google est qu’on peut imaginer que les utilisateurs d’internet naviguent sur le web au hasard. Plus précisément, que lorsqu’ils sont sur une page, les internautes cliquent au hasard sur un des liens présents sur cette page [1]. Votre but est donc de calculer quelles seront les pages les plus visitées si on applique ce modèle.

Commençons par un exemple concret. Imaginons un internet simplifié, constitué de seulement 5 pages web (numérotées de 1 à 5), et 8 liens entre elles, comme sur la figure suivante, où le web est représenté par un graphe.

Micro web imaginaire : les disques sont les pages web, et les flèches représentent les liens entre les pages : la flèche allant de la page 1 à la page 2 signifie qu’il y a un lien sur la page 1 envoyant sur la page 2.

Prenons un internaute fictif qui part de la page numéro 1. S’il se comporte comme on vient de l’expliquer, après un clic, il aura une chance sur deux de se retrouver sur la page 2, et une chance sur deux sur la page 4.

S’il est arrivé sur la page 4, alors il se retrouvera forcément sur la page 1 au clic suivant. Si, en revanche, il est allé vers la page 2, il aura ensuite une chance sur deux de tomber sur la page 5, et une chance sur deux de tomber sur la page 1. Au final, après deux clics, il aura une chance sur 4 de se trouver sur la page 5, et 3 chances sur 4 sur la page 1.

Ainsi de suite, on peut calculer les probabilités que l’utilisateur se trouve sur une certaine page après un nombre donné d’étapes, et mettre ça dans un tableau : dans chaque case, on met la probabilité que l’utilisateur (qui est parti de la page numéro 1), se retrouve sur la page de numéro donné par la colonne, après le nombre de clics donné par la ligne.

Les nombres ont l’air de se stabiliser : on a l’impression qu’à partir d’un certain moment, l’utilisateur aura presque une chance sur trois de se trouver sur les pages 1 ou 2, mais moins d’une chance sur 10 d’être sur la page 3.

C’est là qu’interviennent les mathématiques : ce n’est pas un hasard si ces nombres semblent se stabiliser. Un théorème datant du début du XXe siècle, dû à Perron et Frobenius, explique que c’est effectivement le cas. Plus précisément, ce théorème affirme que si on laisse beaucoup d’utilisateurs naviguer au hasard sur le web [2], alors la proportion d’internautes situés sur une page donnée aura tendance à se stabiliser.

Dans le cas du mini-web de notre exemple, cette proportion d’utilisateurs sera à peu près égale au nombre correspondant sur la dernière ligne du tableau ci-dessus. Par exemple, on n’aura pas loin d’un tiers d’utilisateurs sur la page numéro 1. Cela correspond à la valeur qu’on veut attribuer aux pages : une page est considérée d’autant plus importante par Google que le nombre correspondant à la page est élevé.

Le théorème de Perron et Frobenius est même un peu plus précis, il nous dit que la convergence est exponentielle : on sait combien de lignes du tableau il faut calculer avant d’avoir une bonne approximation de la valeur d’une page, et on sait que ce nombre est assez petit [3]. C’est une indication précieuse en pratique : lorsqu’on veut calculer la valeur de chaque page du web, la quantité de pages et de liens qu’il faut prendre en compte est titanesque ; c’est une bonne nouvelle qu’il ne faille pas en plus de cela obliger l’algorithme à faire beaucoup d’étapes de calcul des probabilités.

Quelques précisions sur les maths derrière le théorème de Perron-Frobenius (piste noire !)

À partir du graphe des transitions entre les $n$ pages web, on peut fabriquer une matrice à $n$ lignes et $n$ colonnes. Le coefficient situé à l’intersection de la $i$-ème ligne avec la $j$-ème colonne est la probabilité de passer en un clic de la page $i$ à la page $j$ (qui vaut $0$ s’il n’y a pas de lien allant de la page $i$ à la page $j$). Un peu de réflexion permet de se convaincre que la probabilité de passer de la page $i$ à la page $j$ en $k$ clics est égale au coefficient $i,j$ de la matrice $A^k$.

Sous une hypothèse supplémentaire d’irréductibilité, le théorème de Perron Frobenius assure que la matrice $A^t$ n’a qu’une valeur propre de module $1$, que cette valeur propre est $1$, et qu’elle est simple. Il assure aussi que pour tout vecteur non nul $v\in\mathbb R^n$ ayant toutes ses coordonnées positives, les vecteurs $(A^t)^k v$ convergent exponentiellement vite vers un vecteur propre associé à la valeur propre 1.

Le mélange dans les billards de Sinaï

Autre lieu, autre époque, autres acteurs. Dans les années 70, en s’inspirant d’idées venues de la physique, le mathématicien franco-belge David Ruelle a associé à certains systèmes dynamiques dits « hyperboliques » un objet appelé opérateur de transfert. Un pan entier de l’étude du comportement statistique de systèmes repose désormais sur cette très belle idée.

Une bonne partie des travaux de Viviane Baladi a consisté à exploiter cette idée à fond, pour obtenir une compréhension de plus en plus fine de systèmes de plus en plus complexes.

Une de ses grandes réussites a été de démontrer — en collaboration avec Mark Demers (de l’université de Fairfield, près de la ville de New York) et Carlangelo Liverani (de l’université Tor Vergata à Rome) — le mélange exponentiel pour le flot des billards de Sinaï. Pas de panique, on va vous expliquer tous les mots.

Un billard de Sinaï est un type de billard mathématique introduit par le mathématicien russe Iakov Sinaï. Sa table est constituée d’un bord carré [4], plus un nombre fini d’obstacles, tous convexes (c’est-à-dire qu’un segment dont les deux extrémités sont situées sur le bord d’un obstacle est tout entier inclus à l’intérieur de l’obstacle) [5]. Sur cette table, on fait rouler des boules de billard : tant qu’elles ne rencontrent pas de bord, elles avancent tout droit, et au moment où elles rencontrent un bord elles rebondissent selon la loi de réflexion de Snell-Descartes. On suppose également que les boules sont des points : elles sont minuscules. Enfin, on néglige les frottements : les boules roulent à vitesse constante sur la table, sans jamais s’arrêter. Voilà ce que ça donne sur un dessin (voir aussi cette vidéo pour un exemple animé, ainsi que cet article de Jean-Christophe Yoccoz, en piste noire) :

Ce modèle, dit du gaz de Lorentz, est censé modéliser la diffusion d’électrons dans un métal : on place périodiquement dans le plan des obstacles qui représentent les atomes du métal, et on observe les trajectoires des boules de billard qui représentent les électrons du métal. Pour comprendre le comportement de ces trajectoires, une première étape consiste à étudier le modèle du billard de Sinaï qu’on a décrit plus haut.

D’autre part, s’il y a un unique obstacle qui est un disque situé exactement au milieu de la table, alors le billard qu’on vient de définir modélise aussi ce qui se passe lorsqu’il y a deux particules dans une table de billard carré, qui rebondissent non seulement sur le bord de la table mais aussi lorsqu’elles se percutent l’une l’autre. Comprendre le comportement du gaz de Lorentz, c’est comprendre d’un même coup ces deux phénomènes physiques.

Grâce à des avancées successives de plusieurs mathématiciens et mathématiciennes, le comportement à long terme de ce modèle est de mieux en mieux compris. En gros, on veut comprendre à quel point les trajectoires des boules sont imprévisibles sur le long terme, et ont tendance à se comporter comme des trajectoires aléatoires (on en reparle dans quelques paragraphes !). Une des avancées principales a été un résultat de la mathématicienne Hongkongaise Lai-Sang Young : elle a démontré en 1998 le mélange exponentiel pour un modèle un tout petit peu différent où le temps est discret. Malgré tout, personne n’avait encore réussi à montrer le mélange exponentiel pour le modèle précis du gaz de Lorentz à temps continu. C’est désormais chose faite, grâce au théorème suivant, qu’ont démontré Viviane, Mark et Carlangelo dans un article intitulé Exponential Decay of Correlations for Finite Horizon Sinai Billiard Flows, et publié dans la prestigieuse revue Inventiones mathematicae :

Carlangelo Liverani, à gauche, travaillant au Brésil, et Mark Demers, à droite, cultivant son jardin

Théorème (Baladi-Demers-Liverani) : Dans un billard de Sinaï à horizon fini [6], on a un mélange exponentiel.

Vous ne savez sans doute toujours pas ce que veulent dire les mots « mélange exponentiel »... Cette propriété caractérise les systèmes qui sont très fortement chaotiques : il y a une dépendance très forte aux conditions initiales. Plus précisément, si je veux viser un endroit du billard en faisant deux rebonds, il va falloir que je sois très précis dans mon lancer, et encore plus si je veux viser en faisant 3 rebonds. Le billard est chaotique si, pour viser juste en faisant plus de quelques rebonds, il ne me suffit pas d’être précis, il me faut être (presque) parfait : si je dévie mon lancer d’un chouïa, ma boule va aboutir très loin de son objectif.

En revanche, ce caractère chaotique a un bon côté : il permet de voir le billard comme un système aléatoire. Plus formellement, les mots « mélange exponentiel » signifient que si on lance simultanément beaucoup de boules d’une petite région de la table de billard (en supposant que ces boules n’entrent jamais en collision), alors on sait qu’à partir d’un certain moment les boules seront bien réparties dans la table. De plus, on sait que le temps à partir duquel cela arrive est assez petit [7]. Autrement dit, si je lance une boule de billard avec ma précision d’être humain, il ne faudra pas attendre beaucoup de rebonds avant que la position de boule soit complètement aléatoire, de la même manière que si je lance un dé avec ma précision d’être humain, je peux considérer que le résultat du lancer sera bien un chiffre aléatoire entre 1 et 6 (et ce, même si le comportement du billard, ou du dé, sont complètement déterministes). Pour un autre point de vue sur le chaos dans les billards de Sinaï, on pourra consulter cet article de Françoise Pène, et regarder cette belle animation de Benoît Saussol.

Cela vous rappelle quelque chose ? On avait le même type de résultat pour les pages web et la stabilisation rapide des probabilités de visite. Et ce n’est pas un hasard !

Pour voir ça, on peut découper notre table de billard par une grille formée de petits carrés, comme ci-dessous.

On se fixe une direction, et un carré de la grille (qui n’est pas situé entièrement à l’intérieur d’un obstacle). On choisit alors au hasard un point de ce petit carré, et on lance une boule de ce point et dans la direction qu’on avait fixée. On se demande alors où aura atterri la boule une seconde plus tard. Ou plutôt, on veut une probabilité : quelle est la probabilité qu’au bout d’une seconde, la boule soit dans un carré donné, sachant qu’on l’avait lancée du carré fixé au départ. Cela donne une probabilité de transition d’un carré vers l’autre [8].

À l’instant initial on lance les boules rouges suivant la direction donnée par les flèches (et on suppose qu’il n’y a pas de collision entre les boules). On regarde alors où se retrouvent ces boules une seconde plus tard (par exemple sur les emplacements verts), et on note les carrés dans lesquels elles tombent.

À peu de choses près, si les carrés sont assez petits, cela donne un graphe de transitions, avec des probabilités, comme dans le cas de l’algorithme de Google [9]. On peut ensuite appliquer le théorème de Perron-Frobenius, qui dit que si je lance une boule au hasard dans un petit carré, alors après un temps assez court, j’aurai autant de chances d’être dans un carré que dans n’importe quel autre.

Tous les argument donnés jusque-là sont plutôt vagues, et il faut beaucoup, énormément de travail pour les rendre rigoureux et justifier soigneusement chaque étape. En particulier, il faut remplacer le graphe fini par un graphe ayant une infinité de sommets, et démontrer un théorème de Perron-Frobenius pour ces règles de transition plus complexes [10].

Pour cela, les auteurs ont utilisé des outils sophistiqués répondant aux doux noms d’opérateurs de transfert et autres espaces de Banach anisotropes. Ces mêmes outils ouvrent la voie à l’étude de fonctions $\zeta$ dynamiques, où on rencontre des problèmes très similaires à celui de l’hypothèse de Riemann [11]. Avis aux amateurs...

Le début des 93 pages de l’article de Viviane, Mark et Carlangelo. De l’aveu même des auteurs, la rédaction a été longue et difficile !

Quelques mots sur Viviane Baladi

Viviane est directrice de recherche au CNRS et travaille sur le campus de Jussieu (Paris) au LPSM, un laboratoire CNRS de probabilités et statistiques, qui est à cheval entre Sorbonne Université et l’université Paris Diderot. Elle a étudié à Genève, où elle a soutenu une thèse sous la direction de Jean-Pierre Eckmann, grand spécialiste de théorie du chaos. La carrière de Viviane s’est construite aux quatre coins du monde : elle est passée par les États-Unis, Lyon, Zürich, Paris, Rio et Copenhague. Le théorème dont il est question dans cet article a lui-même été écrit lorsque Viviane était au DMA, puis à l’IMJ-PRG. Cette bougeotte géographique, et son hyperactivité tant mathématique qu’institutionnelle, lui viennent peut-être de ses origines cosmopolites : suisse et libanaise, elle a depuis été naturalisée française.

Post-scriptum :

L’auteur tient à remercier, pour leurs remarques pertinentes sur le texte, Viviane Baladi, Frédéric Le Roux, ainsi que les très efficaces relecteurs Mathilde Herblot, Michele Triestino, Karim Drifi, Simon Billouet, Jacques Lafontaine et Clément Caubel. Merci aussi aux secrétaires de rédaction qui font un travail formidable !

Article édité par Frédéric Le Roux

Notes

[1En fait, le modèle de Google est un peu plus subtil, on suppose en fait que soit le surfeur clique au hasard (uniformément) sur l’un des liens présents sur la page où il est, soit entre à la main l’adresse d’une page prise au hasard (uniformément) sur tout le web, voir cet article.

[2Il faut en fait se placer dans le modèle expliqué dans la note 1, où les utilisateurs ont aussi une petite probabilité de sauter au hasard sur n’importe quelle page du web.

[3Si on veut obtenir des approximations « à $\varepsilon$ près », alors ce nombre est exponentiellement petit en $\varepsilon$.

[4En fait, la table est torique, mais on peut la supposer carrée ici : avec quelques petites hypothèses supplémentaires les théorèmes s’appliqueront encore.

[5Plus précisément, on demande que les obstacles soient strictement convexes : un segment dont les deux extrémités sont situées sur le bord d’un obstacle a tout son intérieur inclus à l’intérieur de l’obstacle. Par exemple, pas d’obstacles carrés possibles !

[6Cela signifie que toute trajectoire rencontre au moins une fois un des obstacles, autrement dit il n’y a aucune trajectoire de boule qui ne rebondit que sur les bords du carré.

[7Si elles sont « bien réparties à $\varepsilon$ près », alors ce temps est exponentiellement petit en $\varepsilon$.

[8En fait je triche ici : il faut aussi prendre en compte les directions. Il faudrait plutôt dire : si je découpe l’ensemble des directions, qui est l’ensemble des angles entre 0 et 360°, quelle est la probabilité de transition que, partant d’un premier carré avec une direction dans un premier secteur, j’arrive dans un second carré avec une direction dans un second secteur ?

[9La probabilité de passer d’un carré $C_1$ à un carré $C_2$ puis un carré $C_3$ n’est pas égal au produit de la probabilité de passer du carré $C_1$ au carré $C_2$ avec celle de passer du carré $C_2$ au carré $C_3$. Cette propriété n’est vraie qu’approximativement, mais est « de moins en moins fausse » lorsque la taille des carrés tend vers 0.

[10Le graphe sera ici une densité de probabilité, sur à la fois la table de billard et les directions de lancers.

[11Le lecteur n’ayant pas peur du hors-piste pourra consulter le joli cours de Mark Pollicott.

Partager cet article

Pour citer cet article :

Pierre-Antoine Guihéneuf — «De l’algorithme de Google aux billards de Sinaï» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - Lucien Birgé
img_20263 - Pages personnelles des auteurs
img_20264 - ArXiv

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?