Comment les chaînes de Markov sont-elle utilisées par Google?

Oral Maths

Comment les chaînes de Markov sont utilisées par Google?

Les mathématiques sont partout, en physique, en sociologie et même dans une fleur de tournesol. Il n’est donc pas étonnant de voir des concepts mathématiques utilisés en informatique, pour traiter les quantités énormes d’information que les navigateurs doivent gérer, et notamment pour classer les sites internets. Or ces outils peuvent être complexes à utiliser et appréhender, et il est donc possible de se demander comment les chaînes de Markov sont-elles utilisées par Google ? Nous nous intéresserons à :

• La vie de Andreï Markov

• Les chaînes de Markov
• Les matrices de transition
• les distributions invariantes

• Le système PageRank

• La vie d’ Andreï Markov

Andrei Markov (1856-1922) est un mathématicien russe de renommée internationale, notamment connu pour ses travaux en probabilité. Durant ses études à l’université Impériale de Saint-Pétersbourg, il côtoya de grands mathématiciens de son époque, tel que Pafnuty Lvovitch Tchebychev, connu lui aussi pour ces travaux en probabilité. Il obtint ses 1ères lettres de noblesse à seulement 22 ans, grâce à ses recherches sur les équations différentielles, ce qui lui valut une médaille d’or. Après avoir obtenu son doctorat en 1884, il devient professeur de mathématiques à Saint- Pétersbourg à 30 ans. Mais Markov, surnommé le “furieux” en raison de son tempérament houleux, était connu pour ses parti-pris politiques anti-impérialistes, à l’image de son refus de signaler ses élèves anti-tsaristes aux autorités. Il eut aussi de nombreux déboires avec l’église Orthodoxe, surtout lorsqu’il manifesta sa volonté de se faire excommunier en preuve de son soutien à Léon Tolstoï, qui avait subi ce sort en 1901. Il est amusant de voir que sa plus grande réalisation, les chaînes de Markov, trouvent leurs sources dans un débat houleux face à Nikolaï Nekrasov, un mathématicien moscovite conservateur et réactionnaire. Nekrasov tentait d’infirmer les théories sociales et les thèses déterministes, en désaccord avec le dogme Orthodoxe, en utilisant des outils mathématiques. Markov, outré par cet affront fait aux maths, jeta les bases des chaînes de Markov afin de prouver les erreurs de son rival.

• Les chaînes de Markov

. Les chaînes de Markov sont des objets discrets, permettant de calculer l’évolution d’une probabilité, (Un objet discret est un objet qui évolue d’entier en entier, à l’ image d’une suite numérique. Au contraire, une structure continue, à l’image des nombres réels, ne connaît pas de “trou” dans son évolution.) Les chaînes sont constituées de valeurs aléatoires faiblement dépendantes (Les valeurs faiblement dépendantes permettent de s’approcher des modèles probabilistes constitués de VA indépendantes, qui sont les plus précis mais rares dans les cas concrets, au contraire d’une chaîne de markov qui reste “réaliste”.) où, pour tout xo,..., xn+1 € E tel que P (Xo = xo,..., Xn = xn) > 0, on a P(Xo = x0,..., Xn = xn) (Xn+1 = xn+1) = P(X = xn) (Xn+1 = xn+1) . Il est primordial de noter que dans une chaîne de Markov, le futur ne dépend du passé que par le présent.

Une chaîne de Markov peut être représentée sous forme de matrice (En mathématiques, les matrices sont des tableaux d'éléments (nombres, caractères) qui servent à interpréter en termes calculatoires, et donc opérationnels, les résultats théoriques de l'algèbre linéaire et même de l'algèbre bilinéaire. Elles ont l’avantage d’être compréhensible par un ordinateur.).

, appelée distribution et notée π, ce qui facilite les opérations à effectuer. Grâce à cette particularité, il est possible d’utiliser une matrice de transition, afin d’établir l’évolution de la chaîne. Une matrice de transition est une matrice carré (elle comporte autant de lignes que de colonnes) et stochastique ( les éléments de la matrice sont =>0 et toutes les sommes de chaque ligne sont égales à 1).. En affectant à chaque ligne et colonne son événement correspondant, et en inscrivant sa probabilité dans les bonnes cases on obtient une matrice représentant les évolutions de la chaîne. Il est alors possible, en utilisant la distribution π, de connaître l’état de la chaîne à n’importe quel instant (avec la formule π0*Q^n= πn avec n c ℕ).

De plus, il est intéressant de noter que lorsque que la matrice de transition portée à une puissance n quelconque devient ergodique, (Aucun de ses coefficients n’est nul) ou dans quelques cas précis (donner l’exemple du jeu du Kems si question), il est possible de trouver une unique distribution invariante de π (πQ=π) correspondant à la limite de π en + l’infini. Cet état est intéressant car il correspond à l’état stabilisé de la chaîne de Markov, donc la probabilité finale d’un événement. De plus, il est possible de calculer cette distribution invariante et donc de prédire la limite d’une distribution.

• Le système PageRank

L’origine de PageRank vient de la volonté de Sergueï Brin et Larry Page de connaître la popularité et la qualité de chaque site internet afin de proposer les réponses les plus adéquates possibles. Avant PageRank, certains algorithmes tentaient de classer les sites par pertinence en fonction de mots clé contenu dans une page, mais ces algorithmes étaient facilement détournable, en accumulant beaucoup de mot clé sur une page web pour augmenter la chance du site d’apparaître lors d’une recherche. L’avancé de PageRank est de considérer internet comme un hypertexte géant, renvoyant lui-même vers d’autres hypertextes, etc-caetera. Pour fonctionner, PR va simuler la navigation d’un internaute, en cliquant aléatoirement sur les liens d’un site, afin de calculer la popularité d’une page, puis la combine avec la note de qualitée constituée de la durée moyenne de consultation d’un site, afin de créer le classement PageRank. Ce système à l’avantage de se baser sur la quantité de liens qui amène à ce site, en considérant que plus le nombre de liens dirigeant vers un même site est important, plus ce site est populaire et digne de confiance. Cela permet de se séparer de la recherche de l’internaute, et donc des mots clés facilement intégrables dans une page web. Pour calculer cette popularité, les chaînes de Markov entrent en jeu, car la navigation aléatoire peut être assimilée à une  chaîne de Markov, et il donc possible de calculer la distribution invariante de la chaîne en utilisant une matrice de transition où les coefficients de chaque ligne correspondent à l’inverse de la somme des arêtes partant du sommet en question. Malheureusement, il est rare que la matrice de transition soit ergodique, car certaines pages n’ont pas de liens. Il est donc ardu de déterminer l’existence d’une unique distribution invariante. Pour contrer ce phénomène, PR va remplacer les coefficient de la colonne d’un site absorbant (Un site absorbant est un site qui ne contient aucun lien, rendant ce site impossible à quitter avec un autre lien.), en une colonne ou tous les coefficients sont l’inverse de la somme des sites de la chaîne. Nous appellerons ce chiffre 1/n. Cela revient à dire que l’internaute effectue une recherche au hasard et se retrouve sur un autre site. Mais  ce n’est pas toujours suffisant pour rendre la matrice de transition ergodique. En effet, certains sites ne sont pas reliés entre eux. PR dispose alors d’une seconde hypothèse qui consiste à dire qu’un internaute à une probabilité p de choisir un des liens dans cette page et une probabilité 1 - p d’aller chercher un site aléatoire, avec p généralement autour de 0,85. PR multiplie donc la matrice de transition avec p et lui additionne une matrice carré de la taille du nombre de sites de la chaîne avec  tous les coefficient de valeur 1/n multiplié par 1 - p. ( G = pT + (1 - p)K). Le résultat, appelé matrice de Google, est alors une matrice ergodique qui permet alors de calculer la distribution invariante de la chaîne. Pour terminer, PR utilise la valeur de  la distribution invariante de chaque site pour déterminer sa note et en fonction des mots de la requête de l’internaute, va proposer les sites contenant aussi ces mots avec le PR le plus élevé.