_doc/notebooks/expose/expose_rwr_recommandation.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# 3A.mr - Random Walk with Restart (syst\u00e8me de recommandations)\n",
        "\n",
        "Si la m\u00e9thode de [factorisation de matrices](https://fr.wikipedia.org/wiki/Factorisation_de_matrices_pour_les_syst%C3%A8mes_de_recommandation) est la m\u00e9thode la plus connue pour faire des recommandations, ce n'est pas la seule. L'algorithme [Random Walk with Restart](http://www2.cs.uh.edu/~ceick/7363/Papers/tong.pdf) s'appuie sur l'exploration locale des noeuds d'un graphe et produit des r\u00e9sultats plus facile \u00e0 intepr\u00e9ter."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Une des fa\u00e7ons d'expliquer le [PageRank](http://fr.wikipedia.org/wiki/PageRank) est de mod\u00e9liser Internet comme une immense [cha\u00eene de Markov](http://fr.wikipedia.org/wiki/Cha%C3%AEne_de_Markov). Le score PageRank correspond alors \u00e0 la probabilit\u00e9 de rester dans un \u00e9tat ou un site Internet dans ce cas-l\u00e0. Ce score est reli\u00e9 \u00e0 la probabilit\u00e9 d'atterrir sur un site en suivant une marche al\u00e9atoire \u00e0 travers les hyperliens. Et pour \u00e9viter les probl\u00e8mes num\u00e9riques lors du calcul, la formule fait appara\u00eetre un terme $d$ qui correspond \u00e0 la probabilit\u00e9 qu'un surfer a de continuer son chemin ou d'aller voir ailleurs sur un site qui n'a rien \u00e0 voir : il fait un bond avec une probabilit\u00e9 $(1-d)$. Je ne r\u00e9\u00e9cris pas les formules, elles sont disponibles sur [Wikipedia](https://fr.wikipedia.org/wiki/)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Maintenant, si on consid\u00e8re qu'un surfeur se ballade sur Internet de fa\u00e7on al\u00e9atoire mais qu'au lieu d'arr\u00eater sa marche et d'aller n'importe ou ailleurs, il revient \u00e0 son point de d\u00e9part. Cela revient \u00e0 \u00e9tudier toutes les marches al\u00e9atoires partant du m\u00eame noeud. On obtient alors des probabilit\u00e9s de rester dans des \u00e9tats qui d\u00e9pendent de ce point de d\u00e9part qu'on utilise pour faire des recommandations [Fast Random Walk with Restart and Its Applications](http://www2.cs.uh.edu/~ceick/7363/Papers/tong.pdf))."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Je suppose qu'on a un graphe $(G,V,E)$, $V$ pour les noeuds, $E$ pour les arcs. $P$ repr\u00e9sente la matrice de transition d'un noeud \u00e0 l'autre. La somme des coefficients sur la m\u00eame ligne fait 1 : $\\sum_j P_{ij}=1$. $e$ est un vecteur avec que des 0 sauf pour une coordonn\u00e9es $i$ o\u00f9 $i$ est le noeud de d\u00e9part. $c$ est la probabilit\u00e9 de revenir au point de d\u00e9part. L'objectif est de trouver le r\u00e9gime transition $\\pi$ qui v\u00e9rifie l'\u00e9quation suivante :"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "$$\\pi=(1-c)P'\\pi+ce  \\Longleftrightarrow \\pi = c(I-(1-c)P')^{-1}e$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Le vecteur $\\pi$ qui en r\u00e9sulte donne un poids \u00e0 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 $i$, on lui recommandera comme autre site ceux dont le poids est le plus fort dans le vecteur $\\pi$. Le tout est savoir de le calculer. Exemple, on choisit pour $P$ :"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "matrix([[ 0.        ,  0.5       ,  0.        ,  0.5       ],\n",
              "        [ 0.5       ,  0.        ,  0.5       ,  0.        ],\n",
              "        [ 0.33333333,  0.33333333,  0.        ,  0.33333333],\n",
              "        [ 0.1       ,  0.9       ,  0.        ,  0.        ]])"
            ]
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import numpy as np\n",
        "from numpy.linalg import det\n",
        "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]])\n",
        "P"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "matrix([[ 0.24355828],\n",
              "        [ 0.42249412],\n",
              "        [ 0.17956   ],\n",
              "        [ 0.1543876 ]])"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "c = 0.15\n",
        "I = np.identity(4)\n",
        "e = np.matrix( [[ 0., 1., 0., 0. ]]).T\n",
        "pi = ((I-P.T*(1-c))).I * e * c\n",
        "pi"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Une autre de proc\u00e9der est de consid\u00e9rer que le vecteur $\\pi$ est un point fixe de la suite : $\\pi^t = (1-c)P \\pi^{t-1} +ce$. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "matrix([[ 0.24350522],\n",
              "        [ 0.42215404],\n",
              "        [ 0.17924793],\n",
              "        [ 0.15509282]])"
            ]
          },
          "execution_count": 4,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "pi = e\n",
        "for i in range(0,10):\n",
        "    pi = P.T * pi * (1-c) + e * c\n",
        "pi"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "On retrouve sensiblement la m\u00eame chose. Une derni\u00e8re fa\u00e7on est d'utiliser des marches al\u00e9atoires avec restart ou <i>Random Walk with Restart</i>. Mais pour ce faire, on doit g\u00e9n\u00e9rer des marches al\u00e9atoires partant de $i$ avec la probabilit\u00e9 de revenir au d\u00e9but \u00e9gale \u00e0 $c$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[0.24443757725587145,\n",
              " 0.4207354758961681,\n",
              " 0.1773794808405439,\n",
              " 0.15744746600741658]"
            ]
          },
          "execution_count": 5,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import random\n",
        "from numpy.random import multinomial\n",
        "\n",
        "def marche_alea(P,c,i):\n",
        "    marche = [ i ]\n",
        "    while True:\n",
        "        r = random.random()\n",
        "        if r <= c: return marche\n",
        "        vect = P[i,:].tolist()[0]\n",
        "        i = multinomial(1,vect,size=1).tolist()[0].index(1)\n",
        "        marche.append(i)\n",
        "\n",
        "def aggregation(marches):\n",
        "    count = {}\n",
        "    for marche in marches:\n",
        "        for i in marche : count[i] = count.get(i,0)+1.0\n",
        "    s = sum( _ for _ in count.values())*1.0\n",
        "    for i in count: count[i] /= s\n",
        "    return [ count.get(i,0) for i in range(0,max(_ for _ in count.keys())+1) ]\n",
        "\n",
        "marches = [ marche_alea(P,c,1) for k in range(0,1000) ]\n",
        "count = aggregation(marches)\n",
        "count "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "On retrouve sensiblement les m\u00eames r\u00e9sultats. A quoi \u00e7a sert ? Selon les contextes, il est pr\u00e9f\u00e9rable d'utiliser tel ou tel algorithme pour calculer le vecteur $\\pi$ : l'inversion de la matrice, la suite r\u00e9cursive, ou Monte Carlo voire une combinaison. Voici quelques questions qu'il faut se poser.\n",
        "\n",
        "- la matrice est grande (plusieurs millions de noeuds) ou petite (quelques milliers) ?\n",
        "- la matrice est [sparse](http://en.wikipedia.org/wiki/Sparse_matrix) ou creuse (ses coefficients sont presque tous nuls) ?\n",
        "- on a besoin des valeurs pour seulement quelques noeuds et seulement les premi\u00e8res valeurs ?\n",
        "- les calculs se font en parall\u00e8le sur la m\u00eame machine (m\u00e9moire partag\u00e9e) ou en map/reduce ?\n",
        "\n",
        "Sur Internet, les matrices sont souvent tr\u00e8s grande, tr\u00e8s sparses except\u00e9 pour quelques noeuds qui sont comme des hubs et qu'il faut parfois traiter \u00e0 part."
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.1"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 1
}