notebooks/02_model/sar_deep_dive.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<i>Copyright (c) Microsoft Corporation. All rights reserved.</i>\n",
    "\n",
    "<i>Licensed under the MIT License.</i>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SAR Single Node on MovieLens (Python, CPU)\n",
    "\n",
    "In this example, we will walk through each step of the Smart Adaptive Recommendations (SAR) algorithm using a Python single-node implementation.\n",
    "\n",
    "SAR is a fast, scalable, adaptive algorithm for personalized recommendations based on user transaction history. It is powered by understanding the similarity between items, and recommending similar items to those a user has an existing affinity for."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 SAR algorithm\n",
    "\n",
    "The following figure presents a high-level architecture of SAR. \n",
    "\n",
    "At a very high level, two intermediate matrices are created and used to generate a set of recommendation scores:\n",
    "\n",
    "- An item similarity matrix $S$ estimates item-item relationships.\n",
    "- An affinity matrix $A$ estimates user-item relationships.\n",
    "\n",
    "Recommendation scores are then created by computing the matrix multiplication $A\\times S$.\n",
    "\n",
    "Optional steps (e.g. \"time decay\" and \"remove seen items\") are described in the details below.\n",
    "\n",
    "<img src=\"https://recodatasets.blob.core.windows.net/images/sar_schema.svg?sanitize=true\">\n",
    "\n",
    "### 1.1 Compute item co-occurrence and item similarity\n",
    "\n",
    "SAR defines similarity based on item-to-item co-occurrence data. Co-occurrence is defined as the number of times two items appear together for a given user. We can represent the co-occurrence of all items as a $m\\times m$ matrix $C$, where $c_{i,j}$ is the number of times item $i$ occurred with item $j$, and $m$ is the total number of items.\n",
    "\n",
    "The co-occurence matric $C$ has the following properties:\n",
    "\n",
    "- It is symmetric, so $c_{i,j} = c_{j,i}$\n",
    "- It is nonnegative: $c_{i,j} \\geq 0$\n",
    "- The occurrences are at least as large as the co-occurrences. I.e., the largest element for each row (and column) is on the main diagonal: $\\forall(i,j) C_{i,i},C_{j,j} \\geq C_{i,j}$.\n",
    "\n",
    "Once we have a co-occurrence matrix, an item similarity matrix $S$ can be obtained by rescaling the co-occurrences according to a given metric. Options for the metric include `Jaccard`, `lift`, and `counts` (meaning no rescaling).\n",
    "\n",
    "\n",
    "If $c_{ii}$ and $c_{jj}$ are the $i$th and $j$th diagonal elements of $C$, the rescaling options are:\n",
    "\n",
    "- `Jaccard`: $s_{ij}=\\frac{c_{ij}}{(c_{ii}+c_{jj}-c_{ij})}$\n",
    "- `lift`: $s_{ij}=\\frac{c_{ij}}{(c_{ii} \\times c_{jj})}$\n",
    "- `counts`: $s_{ij}=c_{ij}$\n",
    "\n",
    "In general, using `counts` as a similarity metric favours predictability, meaning that the most popular items will be recommended most of the time. `lift` by contrast favours discoverability/serendipity: an item that is less popular overall but highly favoured by a small subset of users is more likely to be recommended. `Jaccard` is a compromise between the two.\n",
    "\n",
    "\n",
    "### 1.2 Compute user affinity scores\n",
    "\n",
    "The affinity matrix in SAR captures the strength of the relationship between each individual user and the items that user has already interacted with. SAR incorporates two factors that can impact users' affinities: \n",
    "\n",
    "- It can consider information about the **type** of user-item interaction through differential weighting of different events (e.g. it may weigh events in which a user rated a particular item more heavily than events in which a user viewed the item).\n",
    "- It can consider information about **when** a user-item event occurred (e.g. it may discount the value of events that take place in the distant past.\n",
    "\n",
    "Formalizing these factors produces us an expression for user-item affinity:\n",
    "\n",
    "$$a_{ij}=\\sum_k w_k e^{[-\\text{log}(2)\\frac{t_0-t_k}{T}]} $$\n",
    "\n",
    "where the affinity $a_{ij}$ for user $i$ and item $j$ is the weighted sum of all $k$ events involving user $i$ and item $j$. $w_k$ represents the weight of a particular event, and the exponential term reflects the temporally-discounted event. The $\\text{log}(2)$ scaling factor causes the parameter $T$ to serve as a half-life: events $T$ units before $t_0$ will be given half the weight as those taking place at $t_0$.\n",
    "\n",
    "Repeating this computation for all $n$ users and $m$ items results in an $n\\times m$ matrix $A$. Simplifications of the above expression can be obtained by setting all the weights equal to 1 (effectively ignoring event types), or by setting the half-life parameter $T$ to infinity (ignoring transaction times).\n",
    "\n",
    "### 1.3 Remove seen item\n",
    "\n",
    "Optionally we remove items which have already been seen in the training set, i.e. don't recommend items which have been previously bought by the user again.\n",
    "\n",
    "### 1.4 Top-k item calculation\n",
    "\n",
    "The personalized recommendations for a set of users can then be obtained by multiplying the affinity matrix ($A$) by the similarity matrix ($S$). The result is a recommendation score matrix, where each row corresponds to a user, each column corresponds to an item, and each entry corresponds to a user / item pair. Higher scores correspond to more strongly recommended items.\n",
    "\n",
    "It is worth noting that the complexity of recommending operation depends on the data size. SAR algorithm itself has $O(n^3)$ complexity. Therefore the single-node implementation is not supposed to handle large dataset in a scalable manner. Whenever one uses the algorithm, it is recommended to run with sufficiently large memory. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 SAR single-node implementation\n",
    "\n",
    "The SAR implementation illustrated in this notebook was developed in Python, primarily with Python packages like `numpy`, `pandas`, and `scipy` which are commonly used in most of the data analytics / machine learning tasks. Details of the implementation can be found in [Recommenders/reco_utils/recommender/sar/sar_singlenode.py](../../reco_utils/recommender/sar/sar_singlenode.py)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 SAR single-node based movie recommender"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "System version: 3.6.7 | packaged by conda-forge | (default, Nov 21 2018, 03:09:43) \n",
      "[GCC 7.3.0]\n",
      "Pandas version: 0.24.1\n"
     ]
    }
   ],
   "source": [
    "# set the environment path to find Recommenders\n",
    "import sys\n",
    "sys.path.append(\"../../\")\n",
    "\n",
    "import itertools\n",
    "import logging\n",
    "import os\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import papermill as pm\n",
    "\n",
    "from reco_utils.dataset import movielens\n",
    "from reco_utils.dataset.python_splitters import python_random_split\n",
    "from reco_utils.evaluation.python_evaluation import map_at_k, ndcg_at_k, precision_at_k, recall_at_k\n",
    "from reco_utils.recommender.sar.sar_singlenode import SARSingleNode\n",
    "\n",
    "print(\"System version: {}\".format(sys.version))\n",
    "print(\"Pandas version: {}\".format(pd.__version__))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": [
     "parameters"
    ]
   },
   "outputs": [],
   "source": [
    "# top k items to recommend\n",
    "TOP_K = 10\n",
    "\n",
    "# Select Movielens data size: 100k, 1m, 10m, or 20m\n",
    "MOVIELENS_DATA_SIZE = '100k'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Load Data\n",
    "\n",
    "SAR is intended to be used on interactions with the following schema:\n",
    "`<User ID>, <Item ID>, <Time>`. \n",
    "\n",
    "Each row represents a single interaction between a user and an item. These interactions might be different types of events on an e-commerce website, such as a user clicking to view an item, adding it to a shopping basket, following a recommendation link, and so on. \n",
    "\n",
    "The MovieLens dataset is well formatted interactions of Users providing Ratings to Movies (movie ratings are used as the event weight) - we will use it for the rest of the example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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>196</td>\n",
       "      <td>242</td>\n",
       "      <td>3.0</td>\n",
       "      <td>881250949</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>186</td>\n",
       "      <td>302</td>\n",
       "      <td>3.0</td>\n",
       "      <td>891717742</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>22</td>\n",
       "      <td>377</td>\n",
       "      <td>1.0</td>\n",
       "      <td>878887116</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>244</td>\n",
       "      <td>51</td>\n",
       "      <td>2.0</td>\n",
       "      <td>880606923</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>166</td>\n",
       "      <td>346</td>\n",
       "      <td>1.0</td>\n",
       "      <td>886397596</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   UserId  MovieId  Rating  Timestamp\n",
       "0     196      242     3.0  881250949\n",
       "1     186      302     3.0  891717742\n",
       "2      22      377     1.0  878887116\n",
       "3     244       51     2.0  880606923\n",
       "4     166      346     1.0  886397596"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = movielens.load_pandas_df(\n",
    "    size=MOVIELENS_DATA_SIZE,\n",
    "    header=['UserId','MovieId','Rating','Timestamp']\n",
    ")\n",
    "\n",
    "# Convert the float precision to 32-bit in order to reduce memory consumption \n",
    "data.loc[:, 'Rating'] = data['Rating'].astype(np.float32)\n",
    "\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Split the data using the python random splitter provided in utilities:\n",
    "\n",
    "We utilize the provided `python_random_split` function to split into `train` and `test` datasets randomly at a 75/25 ratio."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "train, test = python_random_split(data, 0.75)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "header = {\n",
    "        \"col_user\": \"UserId\",\n",
    "        \"col_item\": \"MovieId\",\n",
    "        \"col_rating\": \"Rating\",\n",
    "        \"col_timestamp\": \"Timestamp\",\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, for the illustration purpose, the following parameter values are used:\n",
    "\n",
    "|Parameter|Value|Description|\n",
    "|---------|---------|-------------|\n",
    "|`similarity_type`|`jaccard`|Method used to calculate item similarity.|\n",
    "|`time_decay_coefficient`|30|Period in days (term of $T$ shown in the formula of Section 2.2.2)|\n",
    "|`time_now`|`None`|Time decay reference.|\n",
    "|`timedecay_formula`|`True`|Whether time decay formula is used.|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set log level to INFO\n",
    "logging.basicConfig(level=logging.DEBUG, \n",
    "                    format='%(asctime)s %(levelname)-8s %(message)s')\n",
    "\n",
    "model = SARSingleNode(\n",
    "    remove_seen=True, \n",
    "    similarity_type=\"jaccard\", \n",
    "    time_decay_coefficient=30, \n",
    "    time_now=None, \n",
    "    timedecay_formula=True, \n",
    "    **header\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2019-02-07 21:12:50,049 INFO     Collecting user affinity matrix\n",
      "2019-02-07 21:12:50,055 INFO     Calculating time-decayed affinities\n",
      "2019-02-07 21:12:50,135 INFO     Creating index columns\n",
      "2019-02-07 21:12:50,164 INFO     Building user affinity sparse matrix\n",
      "2019-02-07 21:12:50,174 INFO     Calculating item co-occurrence\n",
      "2019-02-07 21:12:50,419 INFO     Calculating item similarity\n",
      "2019-02-07 21:12:50,420 INFO     Calculating jaccard\n",
      "2019-02-07 21:12:50,631 INFO     Calculating recommendation scores\n",
      "2019-02-07 21:12:50,738 INFO     Removing seen items\n",
      "2019-02-07 21:12:50,740 INFO     Done training\n"
     ]
    }
   ],
   "source": [
    "model.fit(train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2019-02-07 21:12:50,762 INFO     Getting top K\n"
     ]
    }
   ],
   "source": [
    "top_k = model.recommend_k_items(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO: remove this call when the model returns same type as input\n",
    "top_k['UserId'] = pd.to_numeric(top_k['UserId'])\n",
    "top_k['MovieId'] = pd.to_numeric(top_k['MovieId'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final output from the `recommend_k_items` method generates recommendation scores for each user-item pair, which are shown as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "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>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>600</td>\n",
       "      <td>69</td>\n",
       "      <td>12.984131</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>600</td>\n",
       "      <td>183</td>\n",
       "      <td>13.106912</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>600</td>\n",
       "      <td>89</td>\n",
       "      <td>13.163791</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>600</td>\n",
       "      <td>423</td>\n",
       "      <td>12.991756</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>600</td>\n",
       "      <td>144</td>\n",
       "      <td>13.489795</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   UserId  MovieId  prediction\n",
       "0     600       69   12.984131\n",
       "1     600      183   13.106912\n",
       "2     600       89   13.163791\n",
       "3     600      423   12.991756\n",
       "4     600      144   13.489795"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(top_k.head())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Evaluate the results\n",
    "\n",
    "It should be known that the recommendation scores generated by multiplying the item similarity matrix $S$ and the user affinity matrix $A$ **DOES NOT** have the same scale with the original explicit ratings in the movielens dataset. That is to say, SAR algorithm is meant for the task of *recommending relevent items to users* rather than *predicting explicit ratings for user-item pairs*. \n",
    "\n",
    "To this end, ranking metrics like precision@k, recall@k, etc., are more applicable to evaluate SAR algorithm. The following illustrates how to evaluate SAR model by using the evaluation functions provided in the `reco_utils`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# all ranking metrics have the same arguments\n",
    "args = [test, top_k]\n",
    "kwargs = dict(col_user='UserId', \n",
    "              col_item='MovieId', \n",
    "              col_rating='Rating', \n",
    "              col_prediction='prediction', \n",
    "              relevancy_method='top_k', \n",
    "              k=TOP_K)\n",
    "\n",
    "eval_map = map_at_k(*args, **kwargs)\n",
    "eval_ndcg = ndcg_at_k(*args, **kwargs)\n",
    "eval_precision = precision_at_k(*args, **kwargs)\n",
    "eval_recall = recall_at_k(*args, **kwargs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Model:\t\t sar_ref\n",
      "Top K:\t\t 10\n",
      "MAP:\t\t 0.105815\n",
      "NDCG:\t\t 0.373197\n",
      "Precision@K:\t 0.326617\n",
      "Recall@K:\t 0.175957\n"
     ]
    }
   ],
   "source": [
    "print(f\"Model:\\t\\t {model.model_str}\",\n",
    "      f\"Top K:\\t\\t {TOP_K}\",\n",
    "      f\"MAP:\\t\\t {eval_map:f}\",\n",
    "      f\"NDCG:\\t\\t {eval_ndcg:f}\",\n",
    "      f\"Precision@K:\\t {eval_precision:f}\",\n",
    "      f\"Recall@K:\\t {eval_recall:f}\", sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "Note SAR is a combinational algorithm that implements different industry heuristics. The followings are references that may be helpful in understanding the SAR logic and implementation. \n",
    "\n",
    "1. Badrul Sarwar, *et al*, \"Item-based collaborative filtering recommendation algorithms\", WWW, 2001.\n",
    "2. Scipy (sparse matrix), url: https://docs.scipy.org/doc/scipy/reference/sparse.html\n",
    "3. Asela Gunawardana and Guy Shani, \"A survey of accuracy evaluation metrics of recommendation tasks\", The Journal of Machine Learning Research, vol. 10, pp 2935-2962, 2009.\t"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (reco)",
   "language": "python",
   "name": "reco"
  },
  "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}