Part-1-Matrix-Factorization-Recommendation-Retrieval.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Matrix Factorization Recommendation Retrieval "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A typical recommender system has two phases: preference learning and recommendation retrieval. While the former can be done offline, the latter needs to be fast. However, the cost of linearly scanning through the whole set of billions of items are prohibitive or sometimes even impossible. \n",
    "In this tutorial, what are the key takeaways:\n",
    "1. Recommendation retrieval is a similarity search problem (user is the query)\n",
    "2. Exhaustive search over the whole item set is expensive (when the dimension increases or the number of items increases)\n",
    "\n",
    "In this tutorial, we will investigate the complexity of linear scanning solution for MF-based recommendation retrieval. In particular, we train Probabilistic Matrix Factorization (PMF) model with Movielens 1M dataset.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import time\n",
    "import pickle\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.model_selection import train_test_split\n",
    "from utils.lsh import *\n",
    "from utils.load_data import *\n",
    "from utils.pmf import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recommendation Retrieval is a Similarity Search Problem "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two phases of a matrix factorization recommendation system:\n",
    "1. **Learning phase:** derive a d-dimensional vector $x_u$ for each user $u$ and a d-dimensional vector $y_i$ for each item $i$. The user-item relationship is modelled using the inner product kernel, i.e., the user preference of user $u$ over an item $i$:\n",
    "\n",
    "$$\\mathbf{preference}(u, i) = x_u^Ty_i$$\n",
    "\n",
    "\n",
    "2. **Retrieval phase:** given a user vector $x_u$, construct a recommendation list of $K$ items with highest preference score. This step requires $\\mathcal{O}(n \\times d)$ preference score computations and $\\mathcal{O}(n \\times \\log(n))$. \n",
    "\n",
    "   The total cost of the retrieval step is:\n",
    "\n",
    "$$\\mathcal{O}(n \\times d + n \\times \\log(n)) $$\n",
    "\n",
    "We include below here the illustration of the two phases from the presentation:\n",
    "\n",
    "\n",
    "<img src=\"resources/images/two_phases.png\" width=\"500\">\n",
    "\n",
    "Next, we are going to take a closer look at the linear scanning solution. The matrix factorization model that we use for illustration purpose is Probabilistic Matrix Factorization (PMF).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Probabilistic Matrix Factorization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probabilistic Matrix Factorization is introduced in the following paper: http://papers.nips.cc/paper/3208-probabilistic-matrix-factorization. \n",
    "\n",
    "The objective is to learn for each user $u$ a vector $x_u$ and each item $i$ a vector $y_i$, such that the following error function is minimized:\n",
    "\\begin{equation}\n",
    " E = \\sum_{u = 1}^{m}\\sum_{i = 1}^{n}I_{ui}(r_{ui} - x_u^Ty_i)^2 + \\lambda_x\\sum_{u = 1}^{m}||x_u||^2 + \\lambda_y\\sum_{i = 1}^{n}||y_i||^2, \n",
    "\\end{equation}\n",
    "in which $I_{ui} = 1$ if $u$ rated $i$ in the training data and 0 otherwise. $\\lambda_x$ and $\\lambda_y$ are regularization terms for user vectors and item vectors respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Movielens 1M Dataset\n",
    "\n",
    "This dataset contains 1 million ratings from 6000 users on 4000 movies. The dataset is contained in the 'data/ml-1m' folder.\n",
    "Link to download the dataset: <a>https://grouplens.org/datasets/movielens/1m/</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "# load movielens data \n",
    "file_path = \"data/ml-1m/ratings.dat\"\n",
    "prefer = []\n",
    "for line in open(file_path, 'r'): \n",
    "    (userid, movieid, rating, ts) = re.split(\"\\t|,|::\", line) \n",
    "    uid = int(userid)\n",
    "    mid = int(movieid)\n",
    "    rat = float(rating)\n",
    "    prefer.append([uid, mid, rat])\n",
    "\n",
    "ratings = array(prefer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# split data into train/test pair with 70/30 ratio.\n",
    "train, test = train_test_split(ratings, test_size = 0.3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train PMF algorithm with Movielens 1M dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# learning from the training data\n",
    "pmf = PMF()\n",
    "pmf.set_params({\"num_feat\": 100, \"epsilon\": 1, \"_lambda\": 0.1, \"maxepoch\": 100, \"num_batches\": 100})\n",
    "print(\"#users: {0} -- #items: {1} -- #factors: {2}\".format(len(np.unique(ratings[:, 0])), len(np.unique(ratings[:, 1])), pmf.num_feat))\n",
    "\n",
    "# training PMF with Movielens dataset\n",
    "pmf.fit(train, test)\n",
    "\n",
    "#Check performance by plotting train and test RMSE errors\n",
    "plt.plot(range(pmf.maxepoch), pmf.rmse_train, marker='o', label='Training Data')\n",
    "plt.plot(range(pmf.maxepoch), pmf.rmse_test, marker='v', label='Test Data')\n",
    "plt.title('The MovieLens Dataset Learning Curve')\n",
    "plt.xlabel('Number of Epochs')\n",
    "plt.ylabel('RMSE')\n",
    "plt.legend()\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#save model, training/testing data for future use\n",
    "model_output = \"pmf_mvl1m.model\"\n",
    "pickle.dump(pmf, open(model_output, 'wb'))\n",
    "pickle.dump(train, open('train_data', 'wb'))\n",
    "pickle.dump(test, open('test_data', 'wb'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexity of Linear Scaning \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"resources/images/retrieval_phase.png\" width=\"700\">\n",
    "\n",
    "Given a user query vector $x_u$, the time complexity of linearly scanning through all items is $O(n * d)$, in which:\n",
    "- $n$ is the number of items\n",
    "- $d$ is the number of factors\n",
    "\n",
    "In this experiment, we measure the time to perform inner product computation as the number of items increases and the number features increases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## As the number of items increases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "computation_time = []\n",
    "\n",
    "data = pmf.w_Item\n",
    "queries = pmf.w_User\n",
    "\n",
    "#test queries\n",
    "q = queries.T\n",
    "\n",
    "for incr_size in range(0, data.shape[0], 10):\n",
    "    start_time = time.time()\n",
    "    pred = np.matmul(data[:incr_size, :], q)\n",
    "    end_time   = time.time()\n",
    "    computation_time.append((end_time - start_time)/q.shape[1])\n",
    "\n",
    "#plot the computation time as the number of items increases\n",
    "plt.plot(range(0, data.shape[0], 10), computation_time, marker='o', label='Computation_time')\n",
    "plt.title('Inner product computation time (seconds) as number of items increases')\n",
    "plt.xlabel('Number of Items')\n",
    "plt.ylabel('Computation Time (seconds)')\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## As the number of features increases "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "computation_time = []\n",
    "\n",
    "for d in range(pmf.num_feat):\n",
    "    start_time = time.time()\n",
    "    \n",
    "    # preference computation \n",
    "    pred = np.matmul(data[:incr_size, :d], q[:d, :])\n",
    "    \n",
    "    end_time   = time.time()\n",
    "    \n",
    "    #average the computation time \n",
    "    computation_time.append((end_time - start_time)/q.shape[1])\n",
    "\n",
    "#plot the computation time as the number of dimension increases\n",
    "plt.plot(range(pmf.num_feat), computation_time, marker='v', label='Computation_time')\n",
    "plt.title('Inner product computation time (seconds) as number of dimension increases')\n",
    "plt.xlabel('Number of Dimension')\n",
    "plt.ylabel('Computation Time (seconds)')\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}