baseline-intermediate.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import csv\n",
    "import random\n",
    "import concurrent.futures\n",
    "\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from typing import *\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "import scipy as sp\n",
    "import scipy.sparse\n",
    "import scipy.sparse.linalg\n",
    "\n",
    "from overloading import overload\n",
    "from tqdm import tqdm\n",
    "\n",
    "from metrics import apk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "DATA_PREFIX = 'data/'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Read data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('{}/{}'.format(os.getcwd(),\n",
    "                        DATA_PREFIX))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def get_likes() -> Iterable[Tuple[str, str]]:\n",
    "    \"\"\"Return an iterator over user->item edges.\"\"\"\n",
    "    train_likes_file = open('train_likes.csv')\n",
    "    reader = csv.DictReader(train_likes_file)\n",
    "    return map(lambda row: (row['user_id'], row['item_id']), reader)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "user_item_pairs = list(get_likes())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "users, items = map(tuple, map(set, zip(*user_item_pairs)))\n",
    "\n",
    "user_to_i = {user: i for i, user in enumerate(users)}\n",
    "item_to_i = {item: i for i, item in enumerate(items)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# We could construct a CSR matrix from the very start, but that's not very convenient for holdoff\n",
    "\n",
    "#ix, iy = zip(* ((user_to_i[u],item_to_i[i]) for (u,i) in user_item_pairs) )\n",
    "#values = np.ones_like(ix,dtype='bool')\n",
    "\n",
    "#A = sp.sparse.csr_matrix((values,(ix,iy) ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Therefore, we construct a LIL matrix and, having populated it, convert to CSR\n",
    "\n",
    "A = sp.sparse.lil_matrix((len(users), len(items)), dtype=np.bool) # a matrix we'll run SVD on, with some connections taken out (held off)\n",
    "A_full = sp.sparse.lil_matrix((len(users), len(items)), dtype=np.bool) # a matrix we'll check against, with all connections in place\n",
    "\n",
    "for user, item in user_item_pairs:\n",
    "    A[user_to_i[user], item_to_i[item]] = (True if random.random() > 0.15 else False) # NB: non-determenistic!\n",
    "    A_full[user_to_i[user], item_to_i[item]] = True\n",
    "    \n",
    "A = A.tocsr()\n",
    "A_full = A_full.tocsr()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SVD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\DeclareMathOperator*{\\argmin}{arg\\,min}$\n",
    "There are two different ways to look at the truncated SVD of a matrix. One is the standard definition:\n",
    "\n",
    "> First you do the SVD: $\\underset{n\\times m}{X} = \\underset{n\\times n}{U} \\overset{n\\times m}{\\Sigma} \\underset{m\\times m}{V^T}$, where $U$ and $V$ are rotation matrices, and $\\Sigma$ has the singular values along the diagonal. Then you pick the top $k$ singular values, zero out the rest, and hack off irrelevant rows and columns to make a $k$-rank approximation to the original: $X \\approx \\tilde{X} = \\underset{n\\times k}{\\tilde{U}} \\overset{k\\times k}{\\tilde{\\Sigma}} \\underset{k\\times m}{\\tilde{V}^T}$\n",
    "\n",
    "This is all fine and dandy, but it doesn't make sense when talking about matrices with missing values. However, there's an interesting property of the $k$-truncated SVD--It's the best $k$-rank approximation to the original! That is:\n",
    "\n",
    "> $ \\tilde{X} = \\argmin_{B : rank(B)=k} \\displaystyle\\sum\\limits_{i,j} (X_{ij} - B_{ij})^2$\n",
    "\n",
    "This property seems easy to generalize to the missing value case. Basically you're looking for a $k$-rank matrix that minimizes the element-wise mean squared error across the known entries of the original matrix. That is, when you're training the system, you ignore all of the missing values.\n",
    "\n",
    "Then, once you've come up with a suitably \"close\" $k$-rank approximation to the original, you use it to fill in the missing values. That is, if $X_{ij}$ was missing, then you fill in $\\tilde{X}_{ij}$. Tada! You are now done.\n",
    "\n",
    "-- http://stats.stackexchange.com/a/35460"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "u, s, vt = sp.sparse.linalg.svds(A.astype(np.float32), k=100) # note the static components count. It could be optimised automatically via gradient descent on mAP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "u.shape, s.shape, vt.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "u"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "vt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Predicting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let the matrix A be such that rows are the users and the columns are the items that the user likes. One way to think of SVD is as follows: SVD finds a hidden feature space where the users and items they like have feature vectors that are closely aligned.\n",
    "\n",
    "So, when we compute $A = U \\times s \\times V^T$, the $U$ matrix represents the feature vectors corresponding to the users in the hidden feature space and the $V^T$ matrix represents the feature vectors corresponding to the items in the hidden feature space.\n",
    "\n",
    "Now, if I give you two vectors from the same feature space and ask you to find if they are similar, what is the simplest thing that you can think of for accomplishing that? Dot product.\n",
    "\n",
    "So, if I want to see user $i$ likes item $j$, all I need to do is take the dot product of the $i$th entry in $U$ and $j$th entry in $V^T$. Of course, dot product is by no means the only thing you can apply, any similarity measure that you can think of is applicable.\n",
    "\n",
    "-- http://stats.stackexchange.com/a/31101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.dot(u[:10,] * s, vt) # get the probabilities for first ten users -> all films"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.dot(u[1,:] * s, vt[:,546]) # get the probabilities for user 1 -> film 546"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recommended interface\n",
    "```python\n",
    "get_like_confidence(user_id: str, item_id: str) -> float\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@overload\n",
    "def get_like_confidence(user_id: int, item_id: int) -> float:\n",
    "    return np.dot(u[user_id,:] * s, vt[:,item_id])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@overload\n",
    "def get_like_confidence(user_id: str, item_id: str) -> float:\n",
    "    return get_like_confidence(user_to_i[user_id],\n",
    "                               item_to_i[item_id])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "get_like_confidence('70a2805f307f49ec42d4309190daa587', '0ccd2d96eb4b393ecb8cf4e55a6544b6')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i, j in list(islice(get_likes(), 10)):\n",
    "    x = get_like_confidence(i, j)\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ranking interface\n",
    "```python\n",
    "def recommend(user_id: str, k: int=10) -> Sequence[str]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@overload\n",
    "def recommend(user_id: int, k: int=10) -> Sequence[int]:\n",
    "    \n",
    "    result = np.dot(u[user_id,:] * s, vt).argsort()[::-1]\n",
    "\n",
    "    if k is None:\n",
    "        # do not truncate\n",
    "        return result\n",
    "    \n",
    "    return result[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@overload\n",
    "def recommend(user_id: str, k: int=10) -> Sequence[str]:\n",
    "    return list(map(lambda x: items[x], recommend(user_to_i[user_id], k)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "recommend(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "recommend('70a2805f307f49ec42d4309190daa587', k=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Check"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we estimate quality of our predictions via mAP@k - a ranking metric (like NDCG) which values the order of elements in addition to their plain accountance in the recommendation.\n",
    "\n",
    "**Note** that the models cannot be compared (a) with different `k` and (b) by results of one run due to the population process being non-determenistic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_actual(user_id: int) -> Sequence[int]:\n",
    "    \"\"\"Returns items user actually liked (ground truth).\"\"\"\n",
    "    return np.where(A_full[user_id, :].toarray()[0] == 1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "get_actual(4214)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# AP for user 0\n",
    "\n",
    "apk(get_actual(0),\n",
    "    recommend(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def apk_i(user_i: int, k: int=10):\n",
    "    \"\"\"Get Average Precision at k for ith user.\"\"\"\n",
    "\n",
    "    if k is None:\n",
    "        k = len(predicted)\n",
    "\n",
    "    return apk(get_actual(user_i),\n",
    "               recommend(user_i),\n",
    "               k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "apk_i(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def apk_n(n: int=len(users), k: int=10):\n",
    "    \"\"\"Get Average Precision at k for n users.\n",
    "    \n",
    "    Note that some time *after* the progress counter reaches 100% is needed for function to return a result; that's an unfortunate side-effect of multi-processing.\n",
    "    \n",
    "    :param n: How many users to account. Use smaller numbers for debugging and leave it at default to get the final score.\n",
    "    \"\"\"\n",
    "    \n",
    "    with concurrent.futures.ProcessPoolExecutor() as e:\n",
    "        return e.map(partial(apk_i, k=k),\n",
    "                     tqdm(range(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "tuple(apk_n(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mapk_n(n: int=len(users), k: int=10):\n",
    "    \"\"\"Get mean Average Precision at k for n users.\n",
    "    \n",
    "    :param n: How many users to account. Use smaller numbers for debugging and leave it at default to get the final score.\n",
    "    \"\"\"\n",
    "    \n",
    "    return np.mean(tuple(apk_n(n, k)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mapk_n(100)"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}