Applications des chaînes de Markov...
On peut considérer un texte dans une langue donnée comme une chaîne de Markov où la probabilité d'occurrence d'une lettre dépend :
Par une étude statistique, on obtient les probabilités de transitions.
On simule ainsi les différentes langues, et Shannon (1951) a utilisé ce modèle pour définir la quantité d'information qu'elle véhicule.
On peut, par exemple, prévoir l'évolution d'un système, en reconnaissance vocale par exemple, sans avoir à décrire totalement la structure complète d'une phrase.
Les applications des processus de Markov sont nombreuses, notamment en informatique. Citons, par exemple, leur utilisation :
Derrière le fonctionnement du plus célèbre des moteurs de recherche se cache un gros morceau d'algèbre linéaire. En effet, le fonctionnement de Google repose sur le principe suivant...
Mais cette définition n'est pas explicite. Il faut, pour connaître l'importance relatives de chacune des pages, résoudre un système linéaire.
Définition : On appellera vecteur PageRank un vecteur générateur de l'ensemble des solutions.
Soit $\{p_1, ..., p_n\}$ un ensemble de $n$ pages web, reliées entre elles par des liens du type $i \rightarrow j$. On note $l_i$ le nombre de liens émis de la page $i$. On peut interpréter cette structure comme un graphe du web.
En faisant quelques tests, on peut facilement se rendre compte que définir l'importance des pages n'est pas évident : les définitions les plus simples présentent de nombreux points faibles, et ne permettent pas d'attribuer clairement, à chaque page, une valeur représentative de son contenu.
Une méthode de classement des pages par ordre d'importance qui s'approche assez bien de la réalité, et qui est celle utilisée par Google, fait appel à une définition récursive de la valeur "importance d'une page".
Le principe peut être résumé ainsi :
Une page $i$ est importante si beaucoup de pages importantes pointent vers $i$.
Ce qui amène à définir l'importance $\mu_i$ d'une page par : $\mu_i = \sum_{j \rightarrow i} \frac{\mu_j}{l_j}$
En notant $A$ la matrice de terme général $a_{i,j} = \left\{ \begin{array}{ll} \mu_i & \textrm{ si } j \rightarrow i \\ 0 & \textrm{ sinon } \end{array}\right.$ et $\mu = (\mu_1, ..., \mu_n)^T$, il vient que la détermination des $\mu_i$ est équivalente à la résolution du système $A \mu = \mu$.
On remarque que la matrice $A$ est stochastique.
En faisant l'hypothèse que $\forall i, l_i \geqslant 1$ (quitte à faire pointer vers elles-mêmes les pages qui n'émettent pas de lien), on peut interpréter le coefficient $a_{ij}$ comme la probabilité de passer de la page $j$ à la page $i$, en suivant un des $l_j$ liens au hasard...
À partir d'un vecteur stochastique $X$ (i.e. à coefficients positifs, dont la somme vaut 1) donné, effectuons un pas dans la marche aléatoire : on part de la page $j$ avec une probabilité $x_j$, puis on suit le lien $j \rightarrow i$ avec la probabilité $a_{ij}$.
La probabilité d'arriver sur la page $i$ en suivant ce chemin vaut dont $x_j a_{ij}$. Au total, la probabilité d'arriver sur la page $i$ en suivant n'importe quel chemin est $y_i = \sum_{j=1}^n x_j a_{ij}$.
On peut donc associer à un pas dans la marche aléatoire l'application linéaire $X \rightarrow AX$. Les propriétés de stochasticité de la matrice nous permettent d'affirmer :
Cependant, le modèle proposé a un grave défaut : imaginons que la page $n$ reçoive mais n'émette pas de lien (hormis celui qui pointe vers elle-même, comme convenu plus haut). Alors notre surfeur aléatoire arrivera tôt ou tard sur la page $n$, sans jamais pouvoir en sortir !
La seule mesure invariante est donc le vecteur $(0,...,0,1)^T$, qui ne reflète certainement pas l'importance relative d'une page...
Ainsi, Google utilise un modèle plus élaboré pour déterminer l'importance relative des pages. Avec $\epsilon = \left( \frac{1}{n}, ..., \frac{1}{n} \right)^T$, on définit désormais un pas dans la marche aléatoire par la fonction $T : X \rightarrow c \epsilon + (1-c)AX$ où $c \in $]0,1[.
Le surfeur aléatoire ainsi modélisé ne peut alors plus rester bloqué sur une page. Le vecteur stochastique $\epsilon$ correspondant à l'équiprobabilité, à chaque pas dans la marche aléatoire on a intégré la probabilité $c$ que le surfeur quitte la page et redémarre sur une autre page au hasard.
Signalons de plus que la fonction $T$ est continue et contractante (de rapport $1-c$), le problème du point fixe de Cauchy nous permet donc d'affirmer l'existence et l'unicité d'un point fixe $\mu$ tel que $T(\mu) = \mu$.
Quel que soit le vecteur stochastique $X_0$ que nous choisissons comme point de départ, la suite définie pour $n \geqslant 0$ par $X_{n+1} \geqslant X_n$ converge vers cet unique point fixe.
Pour des raisons que nous ne développerons pas ici, il s'avère que les coordonnées de ce point fixe $\mu = (\mu_1, ..., \mu_n)^T$, que l'on définit comme étant le vecteur PageRank, reflètent bien l'importance relative des pages.
En particulier, il faut prêter attention au choix du paramètre $c$, qui peut par exemple être pris égal à 0,15, compte tenu du fait que $\frac{1}{c}$ représente le nombre moyen de liens parcourus par le surfeur avant de redémarrer sur une nouvelle page au hasard, et que 7 est - paraît-il - environ le nombre de pages parcourues par un internaute avant de redémarrer.
Entrée : $X \in \mathbb{R}^n$
Initialisation :
pour $i$ de 1 à $n$,
$Y_i \leftarrow \frac{c}{n}$
pour $j$ de 1 à $n$,
pour $i \in L_j$,
$Y_i \leftarrow Y_i + \frac{1-c}{l_j} X_j$
retourner $Y$
Réfléchir à la mise en oeuvre d'un mini moteur de recherche sur un mini-web.
On pourra créer $n$ pages sans contenu, si ce n'est des hyperliens, tirés aléatoirement, des unes vers les autres.