Part-2-Scalable-Recommendation-Retrieval-with-Locality-Sensitive-Hashing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Scalable Recommendation Retrieval with Locality Sensitive Hashing\n",
    "\n",
    "From the previous example, we can see that the cost of exhaustive search is linear to the number of items, i.e., $n$ and number of features, i.e., $d$. \n",
    "\n",
    "In this part, we will practice to use Locality Sensitive Hashing to speed up the recommendation retrieval task. "
   ]
  },
  {
   "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 *\n",
    "from utils.evaluation import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#load train/test data and trained pmf model\n",
    "path_to_model = 'pmf_mvl1m.model'\n",
    "path_to_train_data = 'train_data'\n",
    "path_to_test_data  = 'test_data'\n",
    "\n",
    "pmf_mvl = pickle.load(open(path_to_model, 'rb'))\n",
    "train   = pickle.load(open(path_to_train_data, 'rb'))\n",
    "test    = pickle.load(open(path_to_test_data, 'rb'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Performance of Linear Scanning Solution\n",
    "\n",
    "We first measure the precision@10 and recall@10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# measuring performance of the first 1000 users\n",
    "topK = 10\n",
    "data = pmf_mvl.w_Item\n",
    "queries = pmf_mvl.w_User[:1000,:]\n",
    "\n",
    "linear_prec, linear_recall = evaluate_topK(test, data, queries, topK)\n",
    "print('linear_prec@{0} \\t linear_recall@{0}'.format(topK))\n",
    "print('{0}\\t{1}'.format(linear_prec, linear_recall))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Locality Sensitive Hashing\n",
    "\n",
    "One of the most popular search protocal using Locality Sensitive Hashing structure is Hashtable look-up (illustrated below).  \n",
    "\n",
    "<img src=\"resources/images/lsh_retrieval.png\" width=\"600\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this experiment, we build LSH index on the output of PMF algorithm. You should expect to see the precision and recall degeneration as compared to those of linear scanning solution. Here, we report three values:\n",
    "\n",
    "\n",
    "1. relative_prec@10 = $\\frac{\\text{precision@10 of LSH Indexing}}{\\text{precision@10 of linear scanning}}$ \n",
    "&nbsp;\n",
    "&nbsp;\n",
    "&nbsp;  \n",
    "&nbsp;\n",
    "2. relative_rec@10    = $\\frac{\\text{recall@10 of LSH Indexing}}{\\text{recall@10 of linear scanning}}$\n",
    "&nbsp;\n",
    "&nbsp;\n",
    "&nbsp;  \n",
    "&nbsp;\n",
    "3. touched = $\\frac{\\text{Average number of investigated items by LSH}}{\\text{Total number of items}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Without Transformation\n",
    "Since Xbox transformation augments user and item vectors to $(d+1)-$dimensional space. For comparison purpose, we append 0s to each user and item vector. \n",
    "\\begin{equation}\n",
    "P(y_i) = [y_i, 0] \n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "Q(x_u) = [x_u, 0]\n",
    "\\end{equation}\n",
    "\n",
    "With this transformation, we have:\n",
    "\n",
    "\\begin{equation}\n",
    "Q(x_u)^T.P(y_i) = x_u^T.y_i\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "same_queries = np.concatenate((queries, np.zeros((queries.shape[0], 1))), axis = 1)\n",
    "same_data = np.concatenate((data, np.zeros((data.shape[0], 1))), axis = 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### With Xbox Transformation\n",
    "\n",
    "Now, before building LSH index, we first apply the Xbox transformation for both user and item vectors. This original maximum inner product search on the original representation becomes the maximum cosine similarity search on the new representation.\n",
    "\n",
    "\\begin{equation}\n",
    "P(y_i) = [y_i, \\sqrt{M^2 - ||y_i||^2}] (M = \\max\\{||y_i||\\})\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "Q(x_u) = [x_u, 0]\n",
    "\\end{equation}\n",
    "\n",
    "We have the following observation:\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{Q(x_u)^T.P(y_i)}{||Q(x_u)||.||P(y_i)||} = \\frac{x_u^T.y_i}{M.||x_u||}\n",
    "\\end{equation}\n",
    "\n",
    "i.e., \n",
    "\n",
    "\\begin{equation}\n",
    "\\arg\\max_{1\\leq i\\leq n}{x_u^Ty_i} = \\arg\\max_{1\\leq i\\leq n}\\frac{Q(x_u)^T.P(y_i)}{||Q(x_u)||.||P(y_i)||}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "We Xbox transformation, we effectively convert Maximum Inner Product Search (MIPS) problem to Maximum Cosine Similarity Search (MCCS)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#apply Xbox transformation\n",
    "M = np.linalg.norm(data, axis=1) # compute item vector norms\n",
    "max_norm = max(M) # max item norm\n",
    "\n",
    "xbox_data = np.concatenate((data, np.sqrt(max_norm**2 - pow(M, 2)).reshape(data.shape[0], -1)), axis = 1)\n",
    "xbox_queries = np.concatenate((queries, np.zeros((queries.shape[0], 1))), axis = 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparing LSH performances with vs. without Xbox transformation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "topK = 10 # top-K value\n",
    "b_vals = [4, 6, 8] # number of hash function\n",
    "L_vals = [5, 10] #number of hashtables\n",
    "\n",
    "print('#table\\t #bit\\t ?Xbox \\t relative_prec@{0} \\t relative_recall@{0} \\t touched'.format(topK))\n",
    "for nt in L_vals:\n",
    "    for b in b_vals: \n",
    "        #init lsh index:\n",
    "        #------ hash-family: the LSH scheme/family \n",
    "        #------ k          : number of hash functions\n",
    "        #------ L          : number of hash tables\n",
    "        lsh_index = LSHIndex(hash_family = CosineHashFamily(same_data.shape[1]), k = b, L=nt)\n",
    "        \n",
    "        #performance without employing Xbox transformation\n",
    "        print('---------------------------------------------------------------------------------')\n",
    "        prec_1, recall_1, touched_1 = evaluate_LSHTopK(test, same_data, -same_queries, lsh_index, dot, topK)\n",
    "        print(\"{0}\\t{1}\\t{2}\\t{3}\\t{4}\\t{5}\".format(nt, b, 'No',prec_1/linear_prec, recall_1/linear_recall, touched_1)) \n",
    "        \n",
    "        #performance with Xbox transformation\n",
    "        prec_2, recall_2, touched_2 = evaluate_LSHTopK(test, xbox_data, -xbox_queries, lsh_index, dot, topK)\n",
    "        print(\"{0}\\t{1}\\t{2}\\t{3}\\t{4}\\t{5}\".format(nt, b, 'Yes', prec_2/linear_prec, recall_2/linear_recall, touched_2)) "
   ]
  },
  {
   "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": 1
}