Google Page Rank.
Dans ce sujet de Centrale Supelec, on étudiait le théorème de Perron-Frobenius. Ce théorème a de nombreuses applications, dont l'une est au coeur du moteur de recherche Google.
On note \(M>0\) si \(\forall i,j,\quad m_{ij}>0\) et \(\rho(A)=\max\{\abs{\lambda},\quad \lambda\in \mathrm{Sp}(A)\}\in\mathbb{R}^+\).
Soit \(A>0\in M_n(\mathbb{R})\).
- \(\rho(A)>0\) et \(\rho(A)\) est une valeurs propre de \(A\), d'ordre de multiplicité 1: \(\dim(\ker(A-\rho(A) I))=1\).
- Il existe un vecteur propre \(X>0\) de \(A\) correspondant à la valeur propre \(\rho(A)\) à composantes strictement positives.
- Toute autre valeur propre de \(A\) dans \(\mathbb{C}\) vérifie \(\abs{\lambda}<\rho(A)\).
Lorsque qu'une recherche est effectuée sur Google, l'algorithme doit sélectionner et ordonner les pages web en fonction de leur pertienence. Pour ce faire, il attribue un score à chaque page web:
- Un score évalue directement la pertinence de la page par rapport à la recherche, par example en comparant les mots contenus dans la page avec ceux présents dans la recherche.
- Un autre score est attribué en fonction de l'intérêt intrinsèque de la page, c'est l'algorithme Page Rank dont on va décrire les grandes lignes.
Le principe est d'estimer la qualité d'une page web en analysant tous les liens qui pointent sur cette page: plus la page est citée par des pages de qualité, plus son score sera élevé.
Le score \(s(x_i)\) d'une page sera ainsi la somme des scores des pages qui pointent sur elle, pondérée par l'inverse du nombre total de liens sortant selon la formule suivante: \[s(x_i) = \sum_{x_j\to x_i} \frac{1}{d(x_j)}s(x_j) \tag{1}\] où \(d(x)\) est le total des liens référencés par la page \(x\) (si la page n'a aucun lien sortant, on peut considérer qu'elle se référence elle-même et poser \(d(x)=1\)).
Si on note \(N\) le nombre total de pages web, \(S\in M_{1N}(\mathbb{R})\) le vecteur ligne dont les composantes sont les \(s(x_i)\), et \(M \in M_N(\mathbb{R})\) la matrice définie par: \[ m_{ij} = \left\{ \begin{array}{ll} \frac{1}{d(x_i)} & \mbox{si } x_i \mbox{ pointe sur } x_j. \\ 0 & \mbox{sinon.} \end{array} \right. \] alors le vecteur des scores satisfait l'équation \[ \begin{alignat*}{1} SM&=S \tag{2}\\ \Leftrightarrow M^TS^T &= S^T \end{alignat*} \] On cherche donc un vecteur propre, à composantes strictement positives, de \(M\) associé à la valeur propre \(1\).
On peut reformuler ce problème en terme de probabilités. On peut se représenter le web comme un graphe, dont les sommets \(x_i\) sont les pages web, avec une arête orientée de \(x_i\) vers \(x_j\) pour symboliser un lien vers \(x_j\) présent dans la page \(x_i\).
Imaginons qu'on se déplace sur les sommets de ce graphe: à partir d'une page \(x_i\), on choisit de façon équiprobable un des \(d(x_i)\) liens sortant.
On définit ainsi une chaine de Markov homogène, et même une marche aléatoire (random walk).
La probabilité de la transition de l'état \(x_i\) vers l'état \(x_j\) est \[ \begin{alignat*}{1} p_{ij} &= \left\{ \begin{array}{ll} \frac{1}{d(x_i)} & \mbox{si } x_i \mbox{ pointe sur } x_j. \\ 0 & \mbox{sinon.} \end{array} \right. \\ &= m_{ij} \end{alignat*} \] ce qui montre que la matrice \(M\) est la matrice de transition de la chaine de Markov. Si \(S_n\) est le vecteur donnant les probabilités d'être dans chaque état à l'instant \(n\), on a: \[ S_n M = S_{n+1} \]
Voila un example de graphe avec 5 pages web:
La matrice de transition associée est: \[ M=\begin{bmatrix} 0 &\frac{1}{2} &\frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} & 0 \\ \end{bmatrix} \]
Trouver \(S\in M_{1N}(\mathbb{R})\), à composantes positives, vérifiant \[ SM=S \] revient à trouver une mesure invariante (ou une probabilité si on normalise entre 0 et 1).
La difficulté vient de la structure du web. La matrice \(M\) contient beaucoup de 0 (sparse), et il y a beaucoup de sites qui n'ont aucun lien sortant et qui sont donc "absorbants" dans la chaine de Markov. On peut montrer que l'équation (2) n'a alors pas de solution "intéressante", c'est à dire une solution avec \(\forall i,\quad s(x_i)>0\): tous les états transitoires de la chaine de Markov auront automatiquement \(s(x_i)=0\) (voir encadré), ce qui rend la solution inopérante pour classer les pages.
L'idée est de modifier les déplacements sur le graphe, en se laissant la possibilité de réinitialiser la chaîne avec une petite probabilité \(\beta\), par exemple \(\beta=0.15\). Plus précisément:
- avec la probabilité \(1-\beta\), on suit un lien comme précédemment.
- avec la probabilité \(\beta\), on choisit de manière équiprobable une page quelconque du web.
La probabilité de la transition de l'état \(x_i\) vers l'état \(x_j\) devient \[ \begin{alignat*}{1} \tilde{p}_{ij}&= \left\{ \begin{array}{ll} (1-\beta)\frac{1}{d(x_i)} + \beta\frac{1}{N} & \mbox{si } x_i \mbox{ pointe sur } x_j. \\ \beta\frac{1}{N} & \mbox{sinon.} \end{array} \right. \\ &= (1-\beta)m_{ij} + \beta\frac{1}{N} \end{alignat*} \]
Le graphe de notre exemple devient, avec en gris les transitions de probabilité \(\frac{\beta}{5}\):
La matrice de transition associée est: \[ \tilde{M}=\begin{bmatrix} \frac{\beta}{5} &\frac{1-\beta}{2}+\frac{\beta}{5} &\frac{1-\beta}{2}+\frac{\beta}{5} & \frac{\beta}{5} & \frac{\beta}{5} \\ \frac{1-\beta}{2} +\frac{\beta}{5}& \frac{\beta}{5} & \frac{1-\beta}{2} +\frac{\beta}{5}& \frac{\beta}{5} & \frac{\beta}{5} \\ \frac{\beta}{5} & \frac{\beta}{5} & \frac{\beta}{5} & \frac{\beta}{5} & (1-\beta)+\frac{\beta}{5} \\ \frac{\beta}{5} & \frac{\beta}{5} & \frac{\beta}{5} & (1-\beta)+\frac{\beta}{5} & \frac{\beta}{5} \\ \frac{1-\beta}{3}+\frac{\beta}{5} & \frac{\beta}{5} & \frac{1-\beta}{3}+\frac{\beta}{5} & \frac{1-\beta}{3}+\frac{\beta}{5} & \frac{\beta}{5} \\ \end{bmatrix} \]
La matrice de transition \(\tilde{M}\) définie par \(\tilde{m}_{ij}=\tilde{p}_{ij}\) est irréductible, et on a même \(\tilde{M}^T>0\). Le théorème de Perron s'applique. Comme de plus la matrice \(\tilde{M}\) est stochastique (\(\sum_{j=1}^N m_{ij}=1\)), on peut montrer que \(\rho(\tilde{M}^T)=1\). Le théorème de Perron justifie l'existence d'un vecteur \(X>0\) tel que \(\tilde{M}^TX=X\), et donc en posant \(S=\frac{1}{\sum x_i}X^T\), on a bien \(S>0\) et \(S\tilde{M}=S\). De plus il est clair que la probabilité \(S\) est unique.
Références
S. U. Pillai, T. Suel and Seunghun Cha,
,
IEEE Signal Processing Magazine, vol. 22, issue: 2, pp. 62-75, March 2005.
Sergey Brin, Lawrence Page,
,
Computer Networks, vol. 30, pp. 107-117, 1998.
Quelques notions sur les chaines de Markov
\(E\) est un espace fini ou infini au plus dénombrable. \(X\) est une chaîne de Markov homogène de matrice de transition \(M\).
Pour tout \(x\in E\) tel que \(P(X_0=x)>0\), on note \[ P_x=P(.\mid X_0=x) \] la loi de probabilité conditionnée à l'évènement \(X_0=x\).
Pour \(y\in E\), on définit le temps de première arrivée en \(y\) par \[ T_y=\inf\{n\in \mathbb{N}^*, X_n=y\} \] avec la convention \(\inf \emptyset = +\infty\)
On dit que \(x\) conduit à \(y\) si \(P_x(T_y < +\infty)>0\)
On dit que les états \(x\) et \(y\) communiquent si \(x\) conduit à \(y\) et \(y\) conduit à \(x\). C'est une relation d'équivalence.
Une chaîne est irréductible si tous les états communiquent.
un état \(x\) est récurrent si \(P_x(T_x<+\infty)=1\). Partant de l'état \(x\), il est certain d'y revenir.
un état \(x\) est transitoire si \(P_x(T_x<+\infty)<1\). Partant de l'état \(x\), il est possible de ne jamais y revenir.