3A.mr - Random Walk with Restart (système de recommandations)#
Links: notebook
, html, python
, slides, GitHub
Si la méthode de factorisation de matrices est la méthode la plus connue pour faire des recommandations, ce n’est pas la seule. L’algorithme Random Walk with Restart s’appuie sur l’exploration locale des noeuds d’un graphe et produit des résultats plus facile à intepréter.
Une des façons d’expliquer le
PageRank est de modéliser
Internet comme une immense chaîne de
Markov. Le score
PageRank correspond alors à la probabilité de rester dans un état ou un
site Internet dans ce cas-là. Ce score est relié à la probabilité
d’atterrir sur un site en suivant une marche aléatoire à travers les
hyperliens. Et pour éviter les problèmes numériques lors du calcul, la
formule fait apparaître un terme qui correspond à la
probabilité qu’un surfer a de continuer son chemin ou d’aller voir
ailleurs sur un site qui n’a rien à voir : il fait un bond avec une
probabilité
. Je ne réécris pas les formules, elles sont
disponibles sur Wikipedia.
Maintenant, si on considère qu’un surfeur se ballade sur Internet de façon aléatoire mais qu’au lieu d’arrêter sa marche et d’aller n’importe ou ailleurs, il revient à son point de départ. Cela revient à étudier toutes les marches aléatoires partant du même noeud. On obtient alors des probabilités de rester dans des états qui dépendent de ce point de départ qu’on utilise pour faire des recommandations Fast Random Walk with Restart and Its Applications).
Je suppose qu’on a un graphe ,
pour les noeuds,
pour les arcs.
représente la matrice de transition
d’un noeud à l’autre. La somme des coefficients sur la même ligne fait 1
:
.
est un vecteur avec que des 0 sauf
pour une coordonnées
où
est le noeud de départ.
est la probabilité de revenir au point de départ. L’objectif
est de trouver le régime transition
qui vérifie l’équation
suivante :
Le vecteur qui en résulte donne un poids à chaque noeud du
graphe et c’est ce poids dont on se sert pour ordonner les
recommandations. Autrement dit, si un surfeur est sur un site
,
on lui recommandera comme autre site ceux dont le poids est le plus fort
dans le vecteur
. Le tout est savoir de le calculer. Exemple,
on choisit pour
:
import numpy as np
from numpy.linalg import det
P = np.matrix ( [[ 0,0.5,0,0.5],[0.5,0,0.5,0],[1./3,1./3,0,1./3],[0.1,0.9,0,0]])
P
matrix([[ 0. , 0.5 , 0. , 0.5 ],
[ 0.5 , 0. , 0.5 , 0. ],
[ 0.33333333, 0.33333333, 0. , 0.33333333],
[ 0.1 , 0.9 , 0. , 0. ]])
c = 0.15
I = np.identity(4)
e = np.matrix( [[ 0., 1., 0., 0. ]]).T
pi = ((I-P.T*(1-c))).I * e * c
pi
matrix([[ 0.24355828],
[ 0.42249412],
[ 0.17956 ],
[ 0.1543876 ]])
Une autre de procéder est de considérer que le vecteur est
un point fixe de la suite :
.
pi = e
for i in range(0,10):
pi = P.T * pi * (1-c) + e * c
pi
matrix([[ 0.24350522],
[ 0.42215404],
[ 0.17924793],
[ 0.15509282]])
On retrouve sensiblement la même chose. Une dernière façon est
d’utiliser des marches aléatoires avec restart ou Random Walk with
Restart. Mais pour ce faire, on doit générer des marches aléatoires
partant de avec la probabilité de revenir au début égale à
.
import random
from numpy.random import multinomial
def marche_alea(P,c,i):
marche = [ i ]
while True:
r = random.random()
if r <= c: return marche
vect = P[i,:].tolist()[0]
i = multinomial(1,vect,size=1).tolist()[0].index(1)
marche.append(i)
def aggregation(marches):
count = {}
for marche in marches:
for i in marche : count[i] = count.get(i,0)+1.0
s = sum( _ for _ in count.values())*1.0
for i in count: count[i] /= s
return [ count.get(i,0) for i in range(0,max(_ for _ in count.keys())+1) ]
marches = [ marche_alea(P,c,1) for k in range(0,1000) ]
count = aggregation(marches)
count
[0.24443757725587145,
0.4207354758961681,
0.1773794808405439,
0.15744746600741658]
On retrouve sensiblement les mêmes résultats. A quoi ça sert ? Selon les
contextes, il est préférable d’utiliser tel ou tel algorithme pour
calculer le vecteur : l’inversion de la matrice, la suite
récursive, ou Monte Carlo voire une combinaison. Voici quelques
questions qu’il faut se poser.
la matrice est grande (plusieurs millions de noeuds) ou petite (quelques milliers) ?
la matrice est sparse ou creuse (ses coefficients sont presque tous nuls) ?
on a besoin des valeurs pour seulement quelques noeuds et seulement les premières valeurs ?
les calculs se font en parallèle sur la même machine (mémoire partagée) ou en map/reduce ?
Sur Internet, les matrices sont souvent très grande, très sparses excepté pour quelques noeuds qui sont comme des hubs et qu’il faut parfois traiter à part.