notes/rs/rs_Matrix-Factorization.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>userId</th>\n",
       "      <th>movieId</th>\n",
       "      <th>rating</th>\n",
       "      <th>timestamp</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3.5</td>\n",
       "      <td>2005-04-02 23:53:47</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>29</td>\n",
       "      <td>3.5</td>\n",
       "      <td>2005-04-02 23:31:16</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>32</td>\n",
       "      <td>3.5</td>\n",
       "      <td>2005-04-02 23:33:39</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>47</td>\n",
       "      <td>3.5</td>\n",
       "      <td>2005-04-02 23:32:07</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>50</td>\n",
       "      <td>3.5</td>\n",
       "      <td>2005-04-02 23:29:40</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   userId  movieId  rating            timestamp\n",
       "0       1        2     3.5  2005-04-02 23:53:47\n",
       "1       1       29     3.5  2005-04-02 23:31:16\n",
       "2       1       32     3.5  2005-04-02 23:33:39\n",
       "3       1       47     3.5  2005-04-02 23:32:07\n",
       "4       1       50     3.5  2005-04-02 23:29:40"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "from tqdm import tqdm\n",
    "from datetime import datetime\n",
    "from heapq import heappush,heappop\n",
    "from collections import Counter,defaultdict\n",
    "import multiprocessing as mp\n",
    "\n",
    "PATH=\"/home/yui/Documents/data/recommender/movieLens20M/rating.csv\"\n",
    "df = pd.read_csv(PATH)\n",
    "df.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Matrix Fatorization\n",
    "Imagine there is a optimized ratings for all users $N$ and all items $M$, it is a matrix $\\hat{R}$ decomposable into user matrix $W$ and item matrix $U$,\n",
    "$$\\begin{align*}\n",
    "\\hat{R} &= WU^\\top \\\\\n",
    "[N\\times M] &= [N\\times k][k\\times M]\n",
    "\\end{align*}$$\n",
    "\n",
    "But it is not worthy to compute all ratings since it could require too much computation, it can be rewritten as element form, \n",
    "$$\\hat{r}_{ij} = w_i^\\top u_j$$\n",
    "where $w_i$ is the row of user matrix $W$, $u$ is the row of item matrx $U$.\n",
    "\n",
    "To optimize each rating, we can consider the Mean Squared Error (MSE). \n",
    "\n",
    "$$J = \\sum_{i,j\\in\\Omega} (r_{ij}-\\hat{r}_{ij})^2=\\sum_{i,j\\in\\Omega}(r_{ij}-w_i^\\top u_j)^2$$\n",
    "where $\\Omega$ set of pairs $(i,j)$ where user $i$ rated movie $j$.\n",
    "\n",
    "We solve both $w_i$ and $u_j$ dependence by setting their gradients to zero to reach the local minima, \n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial J}{\\partial w_i} = 0 &\\quad \\frac{\\partial J}{\\partial u_j} = 0 \\\\\n",
    "w_i=\\bigg(\\sum_{j\\in \\Psi_i}u_ju_j^\\top\\bigg)^{-1}\\sum_{j\\in\\Psi_i}r_{ij}u_j &\\quad u_j= \\bigg(\\sum_{i\\in\\Omega_j }w_iw_i^\\top\\bigg)^{-1}\\sum_{i\\in\\Omega_j}r_{ij}w_i \\\\\n",
    "\\end{align*}$$\n",
    "where $\\Psi_i$ set of movies where users has rated, $\\Omega_j$ set of users where movies have been rated.\n",
    "\n",
    "Though they depend on each other, we can still optimize as alternating least squares.\n",
    "\n",
    "**Advantages**\n",
    "\n",
    "1. It is a type of dimensionality reduction. If consider both $N$ and $M$ are around $10^6$, the rating matrix can have $10^{12}$ elements. But if it is decomposed with $k=100$, the number of elements is only $2\\times(10^6\\times 10^2)\\approx 10^8$. It is more space efficient.\n",
    "2. The dimension of $K$ can be the latent features which have some meanings to the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findNMatches(df,targetUser,leastCommon=25,minMoviesWatched=50,noRef=25):\n",
    "    tardf = df[df[\"userId\"]==targetUser]\n",
    "    u2m = defaultdict(dict)\n",
    "    valCountsUserId = df[\"userId\"].value_counts()\n",
    "\n",
    "    for j in range(tardf.shape[0]):\n",
    "        movieId = tardf.iloc[j][\"movieId\"]\n",
    "        u2m[targetUser][movieId] = tardf.iloc[j][\"rating\"]\n",
    "    avg = np.array(list(u2m[targetUser].values())).mean()\n",
    "    u2m[targetUser] = (u2m[targetUser],avg)\n",
    "    tarSet = set(u2m[targetUser][0])\n",
    "    # print(tarSet)\n",
    "    prevId,storeSet,storeDict = 0,set(),dict()\n",
    "    for i in tqdm(range(df.shape[0])):\n",
    "        row = df.iloc[i]\n",
    "        userId = row[\"userId\"]\n",
    "        if valCountsUserId[userId]<minMoviesWatched:\n",
    "            continue\n",
    "        if userId==targetUser:\n",
    "            continue\n",
    "        if userId!=prevId:\n",
    "            if len(tarSet&storeSet)>=leastCommon:\n",
    "                avg = np.array(list(storeDict.values())).mean()\n",
    "                u2m[prevId]=(storeDict,avg)\n",
    "            storeSet,storeDict=set(),dict()\n",
    "        prevId = userId\n",
    "        storeSet.add(row[\"movieId\"])\n",
    "        storeDict[row[\"movieId\"]]=row[\"rating\"]\n",
    "        if len(u2m)>noRef:\n",
    "            break\n",
    "    return u2m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "  0%|          | 14900/20000263 [00:01<35:24, 9408.79it/s] \n"
     ]
    }
   ],
   "source": [
    "u2m = findNMatches(df,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Further extend the model, we introduce user bias $b_i$, movie bias $c_j$ and global mean $\\mu$, \n",
    "\n",
    "$$\\hat{r}_{ij}=w_i^\\top u_j + b_i+c_j+\\mu$$\n",
    "\n",
    "So the alternating least squares now become,\n",
    "\n",
    "$$\\begin{align*}\n",
    "w_i&=\\bigg(\\sum_{j\\in \\Psi_i}u_ju_j^\\top\\bigg)^{-1}\\sum_{j\\in\\Psi_i}(r_{ij}-b_i-c_j-\\mu)u_j \\\\\n",
    "u_j&= \\bigg(\\sum_{i\\in\\Omega_j }w_iw_i^\\top\\bigg)^{-1}\\sum_{i\\in\\Omega_j}(r_{ij}-b_i-c_j-\\mu)w_i \\\\\n",
    "b_i &= \\frac{1}{|\\Psi_i|}\\sum_{j\\in\\Psi_i}(r_{ij}-w_i^\\top u_j-c_j-\\mu)\\\\\n",
    "c_j &= \\frac{1}{|\\Omega_j|}\\sum_{i\\in\\Omega_j}(r_{ij}-w_i^\\top u_j-b_i-\\mu)\n",
    "\\end{align*}$$\n",
    "\n",
    "Adding regularization terms into loss function, \n",
    "\n",
    "$$J = \\sum_{i,j\\in\\Omega}(r_{ij}-\\hat{r}_{ij})^2+\\lambda \\bigg(\\|W\\|^2_F+\\|U\\|_F^2+\\|b\\|_2^2+\\|c\\|_2^2\\bigg)$$\n",
    "\n",
    "Finally,\n",
    "\n",
    "$$\\begin{align*}\n",
    "w_i&=\\bigg(\\sum_{j\\in \\Psi_i}u_ju_j^\\top + \\lambda I\\bigg)^{-1}\\sum_{j\\in\\Psi_i}(r_{ij}-b_i-c_j-\\mu)u_j \\\\\n",
    "u_j&= \\bigg(\\sum_{i\\in\\Omega_j }w_iw_i^\\top+ \\lambda I\\bigg)^{-1}\\sum_{i\\in\\Omega_j}(r_{ij}-b_i-c_j-\\mu)w_i \\\\\n",
    "b_i &= \\frac{1}{|\\Psi_i|+\\lambda}\\sum_{j\\in\\Psi_i}(r_{ij}-w_i^\\top u_j-c_j-\\mu)\\\\\n",
    "c_j &= \\frac{1}{|\\Omega_j|+\\lambda}\\sum_{i\\in\\Omega_j}(r_{ij}-w_i^\\top u_j-b_i-\\mu)\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MF:\n",
    "    def __init__(self,u2m,K=100,penalty=0.1):\n",
    "        self.u2m = u2m\n",
    "        self.penalty = penalty\n",
    "        self.K = K\n",
    "        self.allmovies = dict()\n",
    "        self.mean,i=0,0\n",
    "        for candidate in u2m:\n",
    "            for movie in u2m[candidate][0]:\n",
    "                t,c = self.allmovies.get(movie,(0,0))\n",
    "                c+=1\n",
    "                t+=u2m[candidate][0][movie]\n",
    "                self.allmovies[movie]=(t,c)\n",
    "                i+=1\n",
    "                self.mean+=u2m[candidate][0][movie]\n",
    "        self.mean/=i\n",
    "        for movie in self.allmovies:\n",
    "            t,c = self.allmovies[movie]\n",
    "            self.allmovies[movie] = (t/c,c)\n",
    "        self.m2id = {key:i for i,key in enumerate(self.allmovies)}\n",
    "        self.id2m = {i:key for i,key in enumerate(self.allmovies)}\n",
    "        self.u2id = {key:i for i,key in enumerate(u2m)}\n",
    "        self.id2u = {i:key for i,key in enumerate(u2m)}\n",
    "        self.N = len(u2m)\n",
    "        self.M = len(self.allmovies)\n",
    "        self.W = np.random.randn(self.N,self.K)\n",
    "        self.U = np.random.randn(self.M,self.K)\n",
    "        self.B = np.random.randn(self.N)\n",
    "        self.C = np.random.randn(self.M)\n",
    "    def alternatingLS(self,epochs=1000):\n",
    "        Js = [self.loss()]\n",
    "        for e in tqdm(range(epochs)):\n",
    "            for candidate in self.u2m:\n",
    "                self.updateW(candidate)\n",
    "                self.updateB(candidate)\n",
    "            for movie in self.allmovies:\n",
    "                self.updateU(movie)\n",
    "                self.updateC(movie)\n",
    "            Js.append(self.loss())\n",
    "        return Js\n",
    "    def updateW(self,targetUser):\n",
    "        up,down = 0,0\n",
    "        bi = self.B[self.u2id[targetUser]]\n",
    "        for j in self.u2m[targetUser][0]:\n",
    "            uj = self.U[self.m2id[j]]\n",
    "            rij = self.u2m[targetUser][0][j]\n",
    "            cj = self.C[self.m2id[j]]\n",
    "            up += (rij-bi-cj-self.mean)*uj\n",
    "            down += np.outer(uj,uj)\n",
    "        n=len(down)\n",
    "        self.W[self.u2id[targetUser]]=\\\n",
    "            np.linalg.inv(down+self.penalty*np.identity(n)).dot(up)\n",
    "    def updateU(self,targetItem):\n",
    "        up,down=0,0\n",
    "        cj = self.C[self.m2id[targetItem]]\n",
    "        for candidate in self.u2m:\n",
    "            if targetItem not in self.u2m[candidate][0]:\n",
    "                continue\n",
    "            wi = self.W[self.u2id[candidate]]\n",
    "            rij = self.u2m[candidate][0][targetItem]\n",
    "            bi = self.B[self.u2id[candidate]]\n",
    "            up += (rij-bi-cj-self.mean)*wi\n",
    "            down += np.outer(wi,wi)\n",
    "        n=len(down)\n",
    "        self.U[self.m2id[targetItem]]=\\\n",
    "            np.linalg.inv(down+self.penalty*np.identity(n)).dot(up)\n",
    "    def updateB(self,targetUser):\n",
    "        s=0\n",
    "        wi = self.W[self.u2id[targetUser]]\n",
    "        c = len(self.u2m[targetUser][0])\n",
    "        for j in self.u2m[targetUser][0]:\n",
    "            rij = self.u2m[targetUser][0][j]\n",
    "            cj = self.C[self.m2id[j]]\n",
    "            uj = self.U[self.m2id[j]]\n",
    "            s+=(rij-wi.T.dot(uj)-cj-self.mean)\n",
    "        self.B[self.u2id[targetUser]]=s/(c+self.penalty)\n",
    "    def updateC(self,targetItem):\n",
    "        s=0\n",
    "        uj = self.U[self.m2id[targetItem]]\n",
    "        c = self.allmovies[targetItem][1]\n",
    "        for candidate in self.u2m:\n",
    "            if targetItem not in self.u2m[candidate][0]:\n",
    "                continue\n",
    "            wi = self.W[self.u2id[candidate]]\n",
    "            bi = self.B[self.u2id[candidate]]\n",
    "            rij = self.u2m[candidate][0][targetItem]\n",
    "            s+=(rij-wi.T.dot(uj)-bi-self.mean)\n",
    "        self.C[self.m2id[targetItem]]=s/(c+self.penalty)\n",
    "    def loss(self):\n",
    "        J = 0\n",
    "        for candidate in self.u2m:\n",
    "            for movie in self.u2m[candidate][0]:\n",
    "                rij = self.u2m[candidate][0][movie]\n",
    "                wi = self.W[self.u2id[candidate]]\n",
    "                uj = self.U[self.m2id[movie]]\n",
    "                bi = self.B[self.u2id[candidate]]\n",
    "                cj = self.C[self.m2id[movie]]\n",
    "                J+=(rij-wi.T.dot(uj)-bi-cj-self.mean)**2\n",
    "        return J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "mf = MF(u2m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 100/100 [01:16<00:00,  1.31it/s]\n"
     ]
    }
   ],
   "source": [
    "epochs = 100\n",
    "Js = mf.alternatingLS(epochs=epochs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f948ae40710>]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYkAAAD4CAYAAAAZ1BptAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAUWklEQVR4nO3dcYxdZZnH8e9zz7UKGhaEarQFi6FRK4kLdrHKxjVgtKCx/CFZjC4NYdPE4IriRov/kNWQaNaIklUSQlHIGoEgWbqmSghidjcRpIArQiVMykpHEAYLSDSKbZ/947x37rnn3jszwFynTL+fZDL3vPc995wzB+bX57zvOROZiSRJo3SWegckSQcvQ0KSNJYhIUkay5CQJI1lSEiSxuou9Q4stmOOOSbXrFmz1LshSS8pd99995OZubLdvuxCYs2aNezcuXOpd0OSXlIi4lej2r3cJEkay5CQJI1lSEiSxjIkJEljGRKSpLEMCUnSWIaEJGksQ6K46Z5p/v2OkdOEJemQZUgU//m/j3L9XXuWejck6aBiSBRVp8P+A/4BJklqMiSKbicMCUlqMSSKqgr2HTiw1LshSQcVQ6KwkpCkYYZEUXWCfYaEJA0wJAorCUkaZkgUVadjJSFJLYZEYSUhScMMiaLqBPv2O7tJkpoMicJKQpKGGRJFfZ+EISFJTYZEYSUhScMMiaI3uynToJCkHkOi6HYCAIsJSeozJIqqhITPb5KkPkOi6IWE4xKS1GdIFN3ZSsKQkKQeQ6LoVRIHDAlJmmVIFFYSkjTMkCiqTv2jcExCkvoMicJKQpKGGRLF7Oym/YaEJPUsKCQi4tMRcX9E/CIivhsRr4iI4yPizoh4KCKuj4gVpe/Ly/JUeX9N43MuLu0PRsT7G+0bS9tURGxttI/cxiR0K++TkKS2eUMiIlYBnwTWZ+aJQAWcA3wZuCwz1wJPAeeXVc4HnsrME4DLSj8iYl1Z763ARuCbEVFFRAV8AzgDWAd8pPRljm0sOu+TkKRhC73c1AUOi4gucDjwGHAacGN5/xrgrPJ6U1mmvH96RERpvy4z/5SZDwNTwCnlayozd2fmc8B1wKayzrhtLDrHJCRp2LwhkZm/Br4CPEIdDs8AdwNPZ+a+0m0aWFVerwL2lHX3lf5HN9tb64xrP3qObQyIiC0RsTMids7MzMx3SCM5u0mShi3kctNR1FXA8cDrgVdSXxpq6/12jTHvLVb7cGPmlZm5PjPXr1y5clSXeVlJSNKwhVxuei/wcGbOZOafgZuAdwFHlstPAKuBR8vraeBYgPL+XwF7m+2tdca1PznHNhZdf0zCgWtJ6llISDwCbIiIw8s4wenAA8DtwIdLn83AzeX19rJMef9HWf+Rhu3AOWX20/HAWuCnwF3A2jKTaQX14Pb2ss64bSy62UrCKbCSNGshYxJ3Ug8e3wPcV9a5EvgccFFETFGPH2wrq2wDji7tFwFby+fcD9xAHTA/BC7IzP1lzOETwC3ALuCG0pc5trHonN0kScO683eBzLwEuKTVvJt6ZlK77x+Bs8d8zqXApSPadwA7RrSP3MYk9O+TMCQkqcc7rgtnN0nSMEOiqMJKQpLaDInC2U2SNMyQKHpjEvvNCEmaZUgUVccH/ElSmyFRdJ0CK0lDDImi8rEckjTEkCi6ToGVpCGGRGElIUnDDIlidkzC6U2SNMuQKCofyyFJQwyJwtlNkjTMkCgck5CkYYZE4ewmSRpmSBSlkLCSkKQGQ6KICLqd8AF/ktRgSDRUnbCSkKQGQ6Kh2wn2+zeuJWmWIdHQsZKQpAGGREM9JmFISFKPIdFQdTrsT0NCknoMiQbHJCRpkCHR4OwmSRpkSDR0K++TkKQmQ6LBSkKSBhkSDc5ukqRBhkRD1elYSUhSgyHRYCUhSYMMiQbHJCRpkCHR4FNgJWmQIdFQdYJ93kwnSbMMiYb6PglDQpJ6DIkGZzdJ0iBDosHZTZI0aEEhERFHRsSNEfHLiNgVEe+MiFdHxK0R8VD5flTpGxFxeURMRcTPI+LkxudsLv0fiojNjfa3R8R9ZZ3LIyJK+8htTIqzmyRp0EIria8DP8zMNwNvA3YBW4HbMnMtcFtZBjgDWFu+tgBXQP0LH7gEeAdwCnBJ45f+FaVvb72NpX3cNiaiCmc3SVLTvCEREUcA7wa2AWTmc5n5NLAJuKZ0uwY4q7zeBFybtTuAIyPidcD7gVszc29mPgXcCmws7x2RmT/JzASubX3WqG1MRFVZSUhS00IqiTcCM8C3IuLeiLgqIl4JvDYzHwMo319T+q8C9jTWny5tc7VPj2hnjm0MiIgtEbEzInbOzMws4JBG63aCA4aEJM1aSEh0gZOBKzLzJOD3zH3ZJ0a05QtoX7DMvDIz12fm+pUrVz6fVQc4JiFJgxYSEtPAdGbeWZZvpA6Nx8ulIsr3Jxr9j22svxp4dJ721SPamWMbE+HsJkkaNG9IZOZvgD0R8abSdDrwALAd6M1Q2gzcXF5vB84ts5w2AM+US0W3AO+LiKPKgPX7gFvKe89GxIYyq+nc1meN2sZEeJ+EJA3qLrDfPwHfiYgVwG7gPOqAuSEizgceAc4ufXcAZwJTwB9KXzJzb0R8Ebir9PtCZu4trz8OfBs4DPhB+QL40phtTISVhCQNWlBIZObPgPUj3jp9RN8ELhjzOVcDV49o3wmcOKL9t6O2MSn1s5ucAitJPd5x3WAlIUmDDIkG75OQpEGGRIOVhCQNMiQaerOb6mEVSZIh0dDt1Pf1WUxIUs2QaKhKSOzzIX+SBBgSA3qVhOMSklQzJBr6lYQhIUlgSAyYrST2GxKSBIbEgKqqfxxWEpJUMyQaqnBMQpKaDImG2ctN3ichSYAhMaByTEKSBhgSDd3K+yQkqcmQaKi8T0KSBhgSDV3vk5CkAYZEQ9WpfxxWEpJUMyQarCQkaZAh0dAfk3DgWpLAkBgwW0k4BVaSAENigLObJGmQIdHQv0/CkJAkMCQGOLtJkgYZEg3ObpKkQYZEg7ObJGmQIdFgJSFJgwyJBmc3SdIgQ6Kh8j4JSRpgSDRU/tEhSRpgSDR0nQIrSQMMiYbKgWtJGmBINMz+jev9ToGVJDAkBlQ+lkOSBhgSDV2nwErSgAWHRERUEXFvRHy/LB8fEXdGxEMRcX1ErCjtLy/LU+X9NY3PuLi0PxgR72+0byxtUxGxtdE+chuT4piEJA16PpXEhcCuxvKXgcsycy3wFHB+aT8feCozTwAuK/2IiHXAOcBbgY3AN0vwVMA3gDOAdcBHSt+5tjERzm6SpEELComIWA18ALiqLAdwGnBj6XINcFZ5vaksU94/vfTfBFyXmX/KzIeBKeCU8jWVmbsz8zngOmDTPNuYiFJIWElIUrHQSuJrwGeB3rSfo4GnM3NfWZ4GVpXXq4A9AOX9Z0r/2fbWOuPa59rGgIjYEhE7I2LnzMzMAg9p5OfQ7YQP+JOkYt6QiIgPAk9k5t3N5hFdc573Fqt9uDHzysxcn5nrV65cOarLglWdsJKQpKK7gD6nAh+KiDOBVwBHUFcWR0ZEt/xLfzXwaOk/DRwLTEdEF/grYG+jvae5zqj2J+fYxsR0O8F+n90kScACKonMvDgzV2fmGuqB5x9l5keB24EPl26bgZvL6+1lmfL+jzIzS/s5ZfbT8cBa4KfAXcDaMpNpRdnG9rLOuG1MjJWEJPW9mPskPgdcFBFT1OMH20r7NuDo0n4RsBUgM+8HbgAeAH4IXJCZ+0uV8AngFurZUzeUvnNtY2K6VcfZTZJULORy06zM/DHw4/J6N/XMpHafPwJnj1n/UuDSEe07gB0j2kduY5KsJCSpzzuuW5zdJEl9hkRLJ6wkJKnHkGjpVsEBQ0KSAENiiGMSktRnSLTUYxKGhCSBITGk6nSsJCSpMCRarCQkqc+QaHFMQpL6DIkW75OQpD5DoqXqBPt8wJ8kAYbEkG7lmIQk9RgSLc5ukqQ+Q6LF2U2S1GdItDi7SZL6DIkWZzdJUp8h0WIlIUl9hkSLYxKS1GdItFSdjvdJSFJhSLRUHawkJKkwJFqqTof9aUhIEhgSQxyTkKQ+Q6KlfnaTU2AlCQyJIVYSktRnSLRUlfdJSFKPIdFiJSFJfYZES+8psOkMJ0kyJNq6nQDAYkKSDIkhVQmJfT7kT5IMibZeJeG4hCQZEkP6lYQhIUmGRMtsJeFD/iTJkGirqvpHYiUhSYbEEMckJKnPkGhxdpMk9c0bEhFxbETcHhG7IuL+iLiwtL86Im6NiIfK96NKe0TE5RExFRE/j4iTG5+1ufR/KCI2N9rfHhH3lXUuj4iYaxuTZCUhSX0LqST2AZ/JzLcAG4ALImIdsBW4LTPXAreVZYAzgLXlawtwBdS/8IFLgHcApwCXNH7pX1H69tbbWNrHbWNinN0kSX3zhkRmPpaZ95TXzwK7gFXAJuCa0u0a4KzyehNwbdbuAI6MiNcB7wduzcy9mfkUcCuwsbx3RGb+JOtnYVzb+qxR25iYXkgcMCQk6fmNSUTEGuAk4E7gtZn5GNRBArymdFsF7GmsNl3a5mqfHtHOHNto79eWiNgZETtnZmaezyEN6VpJSNKsBYdERLwK+B7wqcz83VxdR7TlC2hfsMy8MjPXZ+b6lStXPp9Vh1Sd+kfimIQkLTAkIuJl1AHxncy8qTQ/Xi4VUb4/UdqngWMbq68GHp2nffWI9rm2MTFWEpLUt5DZTQFsA3Zl5lcbb20HejOUNgM3N9rPLbOcNgDPlEtFtwDvi4ijyoD1+4BbynvPRsSGsq1zW581ahsTU83ObnIKrCR1F9DnVOAfgPsi4mel7fPAl4AbIuJ84BHg7PLeDuBMYAr4A3AeQGbujYgvAneVfl/IzL3l9ceBbwOHAT8oX8yxjYmZrSR8LIckzR8Smfk/jB43ADh9RP8ELhjzWVcDV49o3wmcOKL9t6O2MUmV90lI0izvuG7pVo5JSFKPIdHi7CZJ6jMkWpzdJEl9hkSLs5skqc+QaLGSkKQ+Q6LF2U2S1GdItHTLwLX3SUiSITGkqqwkJKnHkGhxTEKS+gyJFmc3SVKfIdFShZebJKnHkGipfCyHJM0yJFq6ToGVpFmGREvlwLUkzTIkWro+4E+SZhkSLaWQsJKQJAyJIRFBtxNOgZUkDImRqk5YSUgShsRI3U6w32c3SZIhMYqVhCTVDIkRulXH2U2ShCExkpWEJNUMiRGc3SRJNUNiBCsJSaoZEiPUlYQhIUmGxAhWEpJUMyRG6HY63ichSRgSI3U6wf40JCTJkBjBMQlJqhkSIzgmIUk1Q2IE75OQpJohMULVCfY5cC1JhsQo3coxCUkCQ2KkqtNxTEKSeAmERERsjIgHI2IqIrb+Jbbp7CZJqh3UIRERFfAN4AxgHfCRiFg36e06u0mSat2l3oF5nAJMZeZugIi4DtgEPDDJjXY7wdQTz/J3/3o7UW+XaHaIkS/HilhIr0ObPyHpxdu2+W847ujDF/UzD/aQWAXsaSxPA+9od4qILcAWgOOOO+5Fb/RjG97AYS+rSOBAJs2iIht3Yi+o1rAgmVf6Q5IWxYru4l8cOthDYtQ/MId+o2TmlcCVAOvXr3/Rv3FOPeEYTj3hmBf7MZL0kndQj0lQVw7HNpZXA48u0b5I0iHnYA+Ju4C1EXF8RKwAzgG2L/E+SdIh46C+3JSZ+yLiE8AtQAVcnZn3L/FuSdIh46AOCYDM3AHsWOr9kKRD0cF+uUmStIQMCUnSWIaEJGksQ0KSNFbkMvtbzhExA/zqBa5+DPDkIu7OS4HHfGjwmJe/F3u8b8jMle3GZRcSL0ZE7MzM9Uu9H39JHvOhwWNe/iZ1vF5ukiSNZUhIksYyJAZdudQ7sAQ85kODx7z8TeR4HZOQJI1lJSFJGsuQkCSNZUgUEbExIh6MiKmI2LrU+7PYIuLYiLg9InZFxP0RcWFpf3VE3BoRD5XvRy31vi62iKgi4t6I+H5ZPj4i7izHfH15DP2yERFHRsSNEfHLcr7fudzPc0R8uvx3/YuI+G5EvGK5neeIuDoinoiIXzTaRp7XqF1efp/9PCJOfqHbNSSof4kA3wDOANYBH4mIdUu7V4tuH/CZzHwLsAG4oBzjVuC2zFwL3FaWl5sLgV2N5S8Dl5Vjfgo4f0n2anK+DvwwM98MvI362JfteY6IVcAngfWZeSL1nxU4h+V3nr8NbGy1jTuvZwBry9cW4IoXulFDonYKMJWZuzPzOeA6YNMS79OiyszHMvOe8vpZ6l8cq6iP85rS7RrgrKXZw8mIiNXAB4CrynIApwE3li7L6pgj4gjg3cA2gMx8LjOfZpmfZ+o/e3BYRHSBw4HHWGbnOTP/C9jbah53XjcB12btDuDIiHjdC9muIVFbBexpLE+XtmUpItYAJwF3Aq/NzMegDhLgNUu3ZxPxNeCzwIGyfDTwdGbuK8vL7Vy/EZgBvlUusV0VEa9kGZ/nzPw18BXgEepweAa4m+V9nnvGnddF+51mSNRiRNuynBscEa8Cvgd8KjN/t9T7M0kR8UHgicy8u9k8outyOtdd4GTgisw8Cfg9y+jS0ijlOvwm4Hjg9cArqS+3tC2n8zyfRfvv3JCoTQPHNpZXA48u0b5MTES8jDogvpOZN5Xmx3tlaPn+xFLt3wScCnwoIv6P+hLiadSVxZHlsgQsv3M9DUxn5p1l+Ubq0FjO5/m9wMOZOZOZfwZuAt7F8j7PPePO66L9TjMkancBa8tsiBXUg17bl3ifFlW5Fr8N2JWZX228tR3YXF5vBm7+S+/bpGTmxZm5OjPXUJ/TH2XmR4HbgQ+XbsvtmH8D7ImIN5Wm04EHWMbnmfoy04aIOLz8d9475mV7nhvGndftwLllltMG4JneZannyzuui4g4k/pfmRVwdWZeusS7tKgi4m+B/wbuo399/vPU4xI3AMdR/892dma2B8de8iLiPcA/Z+YHI+KN1JXFq4F7gY9l5p+Wcv8WU0T8NfVA/QpgN3Ae9T8Il+15joh/Af6eehbfvcA/Ul+DXzbnOSK+C7yH+pHgjwOXAP/BiPNawvLfqGdD/QE4LzN3vqDtGhKSpHG83CRJGsuQkCSNZUhIksYyJCRJYxkSkqSxDAlJ0liGhCRprP8Hz9eKoTr/wcMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(range(epochs+1),Js)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Compare Ground Truth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Movie 2: 3.5 (truth) 3.8641300336631623 (predict)\n",
      "Movie 29: 3.5 (truth) 3.8648064809412044 (predict)\n",
      "Movie 32: 3.5 (truth) 3.8717774364095674 (predict)\n",
      "Movie 47: 3.5 (truth) 3.8767950477986477 (predict)\n",
      "Movie 50: 3.5 (truth) 3.872220679830462 (predict)\n",
      "Movie 112: 3.5 (truth) 3.865349967672109 (predict)\n",
      "Movie 151: 4.0 (truth) 4.3583792140853275 (predict)\n",
      "Movie 223: 4.0 (truth) 4.357461098814121 (predict)\n",
      "Movie 253: 4.0 (truth) 4.362300383977879 (predict)\n",
      "Movie 260: 4.0 (truth) 4.361746296378296 (predict)\n",
      "Movie 293: 4.0 (truth) 4.3604240749456125 (predict)\n"
     ]
    }
   ],
   "source": [
    "targetUser,limit = 1,10\n",
    "for i,movie in enumerate(mf.u2m[targetUser][0]):\n",
    "    pred = mf.W[mf.u2id[targetUser]].T.dot(mf.U[mf.m2id[movie]])\n",
    "    pred += mf.mean\n",
    "    pred += mf.B[targetUser]\n",
    "    pred += mf.C[mf.m2id[movie]]\n",
    "    print(\"Movie {}: {} (truth) {} (predict)\".format(\\\n",
    "        movie,mf.u2m[1][0][movie],pred))\n",
    "    if i==10:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### New suggestions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "res = []\n",
    "for i,movie in enumerate(mf.allmovies):\n",
    "    if movie in mf.u2m[targetUser][0]:\n",
    "        continue\n",
    "    pred = mf.W[mf.u2id[targetUser]].T.dot(mf.U[mf.m2id[movie]])\n",
    "    pred += mf.mean\n",
    "    pred += mf.B[targetUser]\n",
    "    pred += mf.C[mf.m2id[movie]]\n",
    "    heappush(res,(-pred,movie))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(-4.625469862065435, 1210),\n",
       " (-4.613845294378064, 356),\n",
       " (-4.572742889837487, 2858),\n",
       " (-4.404287744570658, 457),\n",
       " (-4.487730889703764, 7361),\n",
       " (-4.2959470221008305, 33794),\n",
       " (-4.404815374578511, 1356),\n",
       " (-4.328141147572148, 475),\n",
       " (-4.339826666156794, 1206),\n",
       " (-4.389067685816456, 904)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}