Chapter 9 - Recommendation Systems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "- <a href='#9-2-1'>Exercise 9.2.1</a>\n",
    "- <a href='#9-2-2'>Exercise 9.2.2</a>\n",
    "- <a href='#9-2-3'>Exercise 9.2.3</a>\n",
    "- <a href='#9-3-1'>Exercise 9.3.1</a>\n",
    "- <a href='#9-4-2'>Exercise 9.4.1 and 9.4.2</a>\n",
    "- <a href='#9-4-3'>Exercise 9.4.3</a>\n",
    "- <a href='#9-4-5'>Exercise 9.4.5 (Normalizing the Utility Matrix)</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from __future__ import division"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-2-1'></a>\n",
    "# 9.2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Computer(object):\n",
    "    def __init__(self, proc, disk, mem):\n",
    "        self.processor_speed = proc\n",
    "        self.disk = disk\n",
    "        self.main_memory = mem\n",
    "        self.summary = [proc, disk, mem]\n",
    "    \n",
    "    def dot_prod(self,X):\n",
    "        if isinstance(X, Computer):\n",
    "            bar = [X.processor_speed, X.disk, X.main_memory]\n",
    "            return sum([x*y for x,y in zip(self.summary,bar)])\n",
    "        else:\n",
    "            assert len(X) == 3\n",
    "            return sum([x*y for x,y in zip(self.summary,X)])\n",
    "            \n",
    "    def cosine(self,X,alpha=1,beta=1):\n",
    "        if isinstance(X, Computer):\n",
    "            foo = [self.processor_speed, alpha*self.disk, beta*self.main_memory]\n",
    "            bar = [X.processor_speed, alpha*X.disk, alpha*X.main_memory]\n",
    "            ati = np.dot(foo,bar)\n",
    "            tun = np.sqrt(np.dot(foo,foo))*np.sqrt(np.dot(bar,bar))\n",
    "            return ati/tun\n",
    "    \n",
    "    def normalize(self, mu):\n",
    "        assert len(mu) == 3\n",
    "        return [self.processor_speed - mu[0], self.disk - mu[1], \n",
    "                       self.main_memory - mu[2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = Computer(3.06,500,6)\n",
    "B = Computer(2.68,320,4)\n",
    "C = Computer(2.92,640,6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "computers = {'A':A, 'B':B, 'C':C}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) cosine similarities when alpha=beta=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pairs = [['A','B'],['A','C'],['B','C']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'B'] 0.999997333284\n",
      "['A', 'C'] 0.999995343121\n",
      "['B', 'C'] 0.999987853375\n"
     ]
    }
   ],
   "source": [
    "# cosine similarities\n",
    "for pair in pairs:\n",
    "    print pair, computers[pair[0]].cosine(computers[pair[1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) cosine similarities when alpha=0.01 and beta=0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'B'] 0.884792148899\n",
      "['A', 'C'] 0.887525858762\n",
      "['B', 'C'] 0.873005241921\n"
     ]
    }
   ],
   "source": [
    "for pair in pairs:\n",
    "    print pair, computers[pair[0]].cosine(computers[pair[1]],0.01,0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) setting alpha = 1/avg(disk size) and beta = 1/avg(main_memory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "alpha = 1/np.mean([A.disk,B.disk,C.disk])\n",
    "beta = 1/np.mean([A.main_memory,B.main_memory,C.main_memory])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00205479452055 0.1875\n"
     ]
    }
   ],
   "source": [
    "print alpha,beta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'B'] 0.941990802633\n",
      "['A', 'C'] 0.940905717338\n",
      "['B', 'C'] 0.949959248828\n"
     ]
    }
   ],
   "source": [
    "for pair in pairs:\n",
    "    print pair, computers[pair[0]].cosine(computers[pair[1]],alpha,beta)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-2-2'></a>\n",
    "# 9.2.2 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Normalizing the vectors of the three computers of 9.2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mean_proc = np.mean([comp.processor_speed for comp in computers.values()])\n",
    "mean_disk = np.mean([comp.disk for comp in computers.values()])\n",
    "mean_memory = np.mean([comp.main_memory for comp in computers.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "means = [mean_proc, mean_disk, mean_memory]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A: [0.17333333333333334, 13.333333333333314, 0.66666666666666696]\n",
      "B: [-0.20666666666666655, -166.66666666666669, -1.333333333333333]\n",
      "C: [0.033333333333333215, 153.33333333333331, 0.66666666666666696]\n"
     ]
    }
   ],
   "source": [
    "print 'A:', A.normalize(means)\n",
    "print 'B:',B.normalize(means)\n",
    "print 'C:',C.normalize(means)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) A few options I can think of: median (of differences), length (or norm), max etc. In all cases, the interpretation of a small angle (note that cosine lies between -1 and 1) means that the two vectors are similarly directed. To be similarly directed in this context of normalized components implies that the items are similarly dispersed about the average."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-2-3'></a>\n",
    "# 9.2.3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# ordered [A,B,C]\n",
    "user_ratings = [4,2,5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) normalizing the ratings for this user"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "avg_rating = np.mean(user_ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.33333333333333348, -1.6666666666666665, 1.3333333333333335]"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# normalize the ratings for this user\n",
    "[rate - avg_rating for rate in user_ratings]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) constructing a user profile from the items profiles\n",
    "\n",
    "*I use the weights rating/5 *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "weights = [rate/5 for rate in user_ratings]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.8, 0.4, 1.0]"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "user_profile = {}\n",
    "user_profile['proc_speed'] = sum([wt*proc for wt,proc in zip(weights,[A.processor_speed,\n",
    "                                                                B.processor_speed,C.processor_speed])])\n",
    "user_profile['disk'] = sum([wt*disk for wt,disk in zip(weights,[A.disk,B.disk,C.disk])])\n",
    "user_profile['main_memory'] = sum([wt*mm for wt,mm in zip(weights,[A.main_memory,B.main_memory,\n",
    "                                                                  C.main_memory])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'disk': 1168.0, 'main_memory': 12.4, 'proc_speed': 6.44}"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "user_profile"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, can use the following weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.36363636363636365, 0.18181818181818182, 0.45454545454545453]"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights = [rate/sum(user_ratings) for rate in user_ratings]\n",
    "weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "user_profile = {}\n",
    "user_profile['proc_speed'] = sum([wt*proc for wt,proc in zip(weights,[A.processor_speed,\n",
    "                                                                B.processor_speed,C.processor_speed])])\n",
    "user_profile['disk'] = sum([wt*disk for wt,disk in zip(weights,[A.disk,B.disk,C.disk])])\n",
    "user_profile['main_memory'] = sum([wt*mm for wt,mm in zip(weights,[A.main_memory,B.main_memory,\n",
    "                                                                  C.main_memory])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'disk': 530.9090909090909,\n",
       " 'main_memory': 5.636363636363637,\n",
       " 'proc_speed': 2.9272727272727272}"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "user_profile"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This user_profile supplies aggregates that are within the support of each component."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-3-1'></a>\n",
    "# 9.3.1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Jaccard similarities: SIM(A,B) = 4/8; SIM(A,C) = 3/8; SIM(B,C) = 4/8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Cosine distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "U = np.array([4,5,0,5,1,0,3,2,0,3,4,3,1,2,1,0,2,0,1,3,0,4,5,3]).reshape(3,8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# user ratings are rows of Utility matrix\n",
    "A = U[0]\n",
    "B = U[1]\n",
    "C = U[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cosine(X,Y):\n",
    "    return np.dot(X,Y)/(np.sqrt(np.dot(X,X)*np.dot(Y,Y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A,B: 0.601040764009\n",
      "A,C: 0.614918693812\n",
      "B,C: 0.513870119777\n"
     ]
    }
   ],
   "source": [
    "print 'A,B:', cosine(A,B)\n",
    "print 'A,C:', cosine(A,C)\n",
    "print 'B,C:', cosine(B,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4, 5, 0, 5, 1, 0, 3, 2],\n",
       "       [0, 3, 4, 3, 1, 2, 1, 0],\n",
       "       [2, 0, 1, 3, 0, 4, 5, 3]])"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) Rounding data in the utility matrix and computing Jaccard distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ratings = [4,5,0,5,1,0,3,2,0,3,4,3,1,2,1,0,2,0,1,3,0,4,5,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# mapping 3,4,5 to 1 and 1,2 to 0\n",
    "U_rounded = np.array(map(lambda x: 1 if x>=3 else 0, ratings)).reshape(3,8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 1, 0, 1, 0, 0, 1, 0],\n",
       "       [0, 1, 1, 1, 0, 0, 0, 0],\n",
       "       [0, 0, 0, 1, 0, 1, 1, 1]])"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U_rounded"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jaccard distances: sim(A,B) = 2/5; sim(A,C) = 2/6; sim(B,C) = 1/6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) computing cosine similarities for rounded data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A,B: 0.57735026919\n",
      "A,C: 0.5\n",
      "B,C: 0.288675134595\n"
     ]
    }
   ],
   "source": [
    "A_rd = U_rounded[0]\n",
    "B_rd = U_rounded[1]\n",
    "C_rd = U_rounded[2]\n",
    "\n",
    "print 'A,B:', cosine(A_rd,B_rd)\n",
    "print 'A,C:', cosine(A_rd,C_rd)\n",
    "print 'B,C:', cosine(B_rd,C_rd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) Normalizing the matrix by user ratings: *subtract from each nonblank entry the average value for its user*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A_norm = map(lambda x: x-np.mean(A) if x>0 else 0, A)\n",
    "B_norm = map(lambda x: x-np.mean(B) if x>0 else 0, B)\n",
    "C_norm = map(lambda x: x-np.mean(C) if x>0 else 0, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "U_norm = np.array([A_norm,B_norm,C_norm])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.5 ,  2.5 ,  0.  ,  2.5 , -1.5 ,  0.  ,  0.5 , -0.5 ],\n",
       "       [ 0.  ,  1.25,  2.25,  1.25, -0.75,  0.25, -0.75,  0.  ],\n",
       "       [-0.25,  0.  , -1.25,  0.75,  0.  ,  1.75,  2.75,  0.75]])"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U_norm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) Computing the cosine distance between each pair of users"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A,B: 0.546504040851\n",
      "A,C: 0.163408291384\n",
      "B,C: -0.312561520424\n"
     ]
    }
   ],
   "source": [
    "print 'A,B:', cosine(A_norm,B_norm)\n",
    "print 'A,C:', cosine(A_norm,C_norm)\n",
    "print 'B,C:', cosine(B_norm,C_norm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-4-2'></a>\n",
    "# 9.4.1 and 9.4.2 (UV Decomposition) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "U = np.array([1]*10).reshape(5,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "V = np.array([1]*10).reshape(2,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 282,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "M = np.array([5,2,4,4,3,3,1,2,4,1,2,99,3,1,4,2,5,4,3,5,4,4,5,4,99]).reshape(5,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 283,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5,  2,  4,  4,  3],\n",
       "       [ 3,  1,  2,  4,  1],\n",
       "       [ 2, 99,  3,  1,  4],\n",
       "       [ 2,  5,  4,  3,  5],\n",
       "       [ 4,  4,  5,  4, 99]])"
      ]
     },
     "execution_count": 283,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Gradient descent**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 311,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def opt_x(r,s):\n",
    "    num = 0\n",
    "    den = 0\n",
    "    for j in range(1,6):\n",
    "        if M[r-1,j-1] != 99:\n",
    "            num += V[s-1,j-1]*(M[r-1,j-1]-np.dot(U[r-1,:],V[:,j-1])\n",
    "                              +U[r-1,s-1]*V[s-1,j-1]) # add back k=r\n",
    "            den += V[s-1,j-1]**2\n",
    "    return num/den"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 324,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def opt_y(r,s):\n",
    "    num = 0\n",
    "    den = 0\n",
    "    for i in range(1,6):\n",
    "        if M[i-1,s-1] != 99:\n",
    "            num += U[i-1,r-1]*(M[i-1,s-1]-np.dot(U[i-1,:],V[:,s-1])\n",
    "                              +U[i-1,r-1]*V[r-1,s-1]) # add back when k=s\n",
    "            den += U[i-1,r-1]**2\n",
    "    return num/den"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9.4.1 (a) and (b) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 325,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 325,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt_x(3,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 326,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.2000000000000002"
      ]
     },
     "execution_count": 326,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt_y(1,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rest of solution to 9.4.2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 384,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def RMSE(r,s,axis):\n",
    "    \"\"\"\n",
    "    if axis=0 then we are starting the decomposition with u_{r,s},\n",
    "    if axis=1, then start decomposition with v_{r,s}\n",
    "    \"\"\"\n",
    "    assert axis == 0 or axis == 1\n",
    "    if axis == 0:\n",
    "        x = opt_x(r,s)\n",
    "        # contribution of mse due to the r-th row of UV\n",
    "        mse = sum(map(lambda u: (u-(x+1))**2 if u!=99 else 0, M[r-1,:]))\n",
    "        # contribution of mse due to the other rows of UV\n",
    "        mse += sum(sum(map(lambda u: (u-2)**2 if u!=99 else 0, M[i,:])) for i in range(0,5) if i != r-1)\n",
    "        return np.sqrt(mse)\n",
    "    else:\n",
    "        y = opt_y(r,s)\n",
    "        # contribution of mse due to the s-th row of UV\n",
    "        mse = sum(map(lambda u: (u-(y+1))**2 if u!=99 else 0, M[:,s-1]))\n",
    "        mse += sum(sum(map(lambda u: (u-2)**2 if u!=99 else 0, M[:,j])) for j in range(0,5) if j != s-1)\n",
    "        return np.sqrt(mse)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 385,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.8866976612521418"
      ]
     },
     "execution_count": 385,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RMSE(1,1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 386,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.8866976612521418"
      ]
     },
     "execution_count": 386,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# manual check for starting UV decomposition with u_{1,1}\n",
    "np.sqrt(sum((M[0,:]-3.6)**2+(M[1,:]-2)**2+(M[3,:]-2)**2)\n",
    "+sum([(m-2)**2 for m in M[2,:] if m!=99])+sum([(m-2)**2 for m in M[4,:] if m!=99]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 392,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimum RMSE from U: 7.3993 occurring from: [5, 1]\n"
     ]
    }
   ],
   "source": [
    "# finding the pair (r,s) that achieves the min RMSE after starting decomposition with u_{r,s}\n",
    "min_RMSE = 2**32\n",
    "min_pair = []\n",
    "for r in range(1,6):\n",
    "    for s in range(1,3):\n",
    "        step_RMSE = RMSE(r,s,0)\n",
    "        if step_RMSE < min_RMSE:\n",
    "            min_RMSE, min_pair = step_RMSE, [r,s]\n",
    "\n",
    "print 'minimum RMSE from U: %.4f occurring from: %s' %(min_RMSE, str(min_pair))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 393,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimum RMSE from V: 7.8867 occurring from: [1, 3]\n"
     ]
    }
   ],
   "source": [
    "# finding the pair (r,s) that achieves the min RMSE after starting decomposition with v_{r,s}\n",
    "min_RMSE = 2**32\n",
    "min_pair = []\n",
    "for r in range(1,3):\n",
    "    for s in range(1,6):\n",
    "        step_RMSE = RMSE(r,s,1)\n",
    "        if step_RMSE < min_RMSE:\n",
    "            min_RMSE, min_pair = step_RMSE, [r,s]\n",
    "\n",
    "print 'minimum RMSE from V: %.4f occurring from: %s' %(min_RMSE, str(min_pair))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above shows that the minimum RMSE from all possible starting points is 7.3993 which we obtain by starting the decomposition at u_{5,1}. *Note that the above code only finds one such pair that results in the minimum*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 406,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.399324293474371"
      ]
     },
     "execution_count": 406,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RMSE(5,2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 408,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.6681158050723255"
      ]
     },
     "execution_count": 408,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RMSE(4,2,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, u_{5,2} also achieves the minimum RMSE, whereas starting from u_{4,2} does not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-4-3'></a>\n",
    "# 9.4.3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 430,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2.6  ,  1.   ],\n",
       "       [ 1.   ,  1.   ],\n",
       "       [ 1.178,  1.   ],\n",
       "       [ 1.   ,  1.   ],\n",
       "       [ 1.   ,  1.   ]])"
      ]
     },
     "execution_count": 430,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U = np.array([2.6,1,1,1,1.178,1,1,1,1,1]).reshape(5,2)\n",
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 431,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.617,  1.   ,  1.   ,  1.   ,  1.   ],\n",
       "       [ 1.   ,  1.   ,  1.   ,  1.   ,  1.   ]])"
      ]
     },
     "execution_count": 431,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V = np.array([1.617,1,1,1,1,1,1,1,1,1]).reshape(2,5)\n",
    "V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can do matrix multiplication using numpy's dot() method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 432,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5.2042  ,  3.6     ,  3.6     ,  3.6     ,  3.6     ],\n",
       "       [ 2.617   ,  2.      ,  2.      ,  2.      ,  2.      ],\n",
       "       [ 2.904826,  2.178   ,  2.178   ,  2.178   ,  2.178   ],\n",
       "       [ 2.617   ,  2.      ,  2.      ,  2.      ,  2.      ],\n",
       "       [ 2.617   ,  2.      ,  2.      ,  2.      ,  2.      ]])"
      ]
     },
     "execution_count": 432,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UV = np.dot(U,V)\n",
    "UV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use functions similar to `opt_x` and `opt_y` from the previous question. In this function, opt_x and opt_y will alter the U and V matrices in addition to returing the optimal values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 433,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def opt_x(r,s):\n",
    "    num = 0\n",
    "    den = 0\n",
    "    for j in range(1,6):\n",
    "        if M[r-1,j-1] != 99:\n",
    "            num += V[s-1,j-1]*(M[r-1,j-1]-np.dot(U[r-1,:],V[:,j-1])\n",
    "                              +U[r-1,s-1]*V[s-1,j-1]) # add back k=r\n",
    "            den += V[s-1,j-1]**2\n",
    "    U[r-1,s-1] = num/den\n",
    "    return num/den\n",
    "\n",
    "def opt_y(r,s):\n",
    "    num = 0\n",
    "    den = 0\n",
    "    for i in range(1,6):\n",
    "        if M[i-1,s-1] != 99:\n",
    "            num += U[i-1,r-1]*(M[i-1,s-1]-np.dot(U[i-1,:],V[:,s-1])\n",
    "                              +U[i-1,r-1]*V[r-1,s-1]) # add back when k=s\n",
    "            den += U[i-1,r-1]**2\n",
    "    V[r-1,s-1] = num/den\n",
    "    return num/den"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 434,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def RMSE_general():\n",
    "    UV = np.dot(U,V)\n",
    "    mse = 0\n",
    "    for i in range(5):\n",
    "        for j in range(5):\n",
    "            if M[i,j] != 99:\n",
    "                mse += (M[i,j]-UV[i,j])**2\n",
    "    return np.sqrt(mse)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 435,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.6107507336842932"
      ]
     },
     "execution_count": 435,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Current RMSE\n",
    "RMSE_general()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Considering u_{1,1} as the element to update "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 436,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.3384319353487366"
      ]
     },
     "execution_count": 436,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# update U with optimal x and print out optimal x\n",
    "opt_x(1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 437,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2.33843194,  1.        ],\n",
       "       [ 1.        ,  1.        ],\n",
       "       [ 1.178     ,  1.        ],\n",
       "       [ 1.        ,  1.        ],\n",
       "       [ 1.        ,  1.        ]])"
      ]
     },
     "execution_count": 437,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 439,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.5809606194928714"
      ]
     },
     "execution_count": 439,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check new RMSE has decreased\n",
    "RMSE_general()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Then choose the best value for u_{5,2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 440,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2.33843194,  1.        ],\n",
       "       [ 1.        ,  1.        ],\n",
       "       [ 1.178     ,  1.        ],\n",
       "       [ 1.        ,  1.        ],\n",
       "       [ 1.        ,  3.09575   ]])"
      ]
     },
     "execution_count": 440,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt_x(5,2)\n",
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 444,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.3168260751980299"
      ]
     },
     "execution_count": 444,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# checking if RMSE was decreased\n",
    "RMSE_general()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) Next, choosing the best value for v_{2,2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 445,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.617,  1.   ,  1.   ,  1.   ,  1.   ],\n",
       "       [ 1.   ,  1.   ,  1.   ,  1.   ,  1.   ]])"
      ]
     },
     "execution_count": 445,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 446,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.617     ,  1.        ,  1.        ,  1.        ,  1.        ],\n",
       "       [ 1.        ,  1.02901777,  1.        ,  1.        ,  1.        ]])"
      ]
     },
     "execution_count": 446,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# updating V at v_{2,2}\n",
    "opt_y(2,2)\n",
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 447,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.3159873198925407"
      ]
     },
     "execution_count": 447,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# checking that RMSE indeed decreased\n",
    "RMSE_general()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**BONUS STEP: choosing best value for v_{1,5}**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 449,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.617     ,  1.        ,  1.        ,  1.        ,  1.37883194],\n",
       "       [ 1.        ,  1.02901777,  1.        ,  1.        ,  1.        ]])"
      ]
     },
     "execution_count": 449,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt_y(1,5)\n",
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 450,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.2145592358668278"
      ]
     },
     "execution_count": 450,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RMSE_general()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='9-4-5'></a>\n",
    "# 9.4.5 (Normalizing the Utility Matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 519,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5,  2,  4,  4,  3],\n",
       "       [ 3,  1,  2,  4,  1],\n",
       "       [ 2, 99,  3,  1,  4],\n",
       "       [ 2,  5,  4,  3,  5],\n",
       "       [ 4,  4,  5,  4, 99]])"
      ]
     },
     "execution_count": 519,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (a) First subtract from each element the average of its row, and then subtract from each element the average of its (modified) column"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 520,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[5, 2, 4, 4, 3],\n",
       "       [3, 1, 2, 4, 1],\n",
       "       [2, 0, 3, 1, 4],\n",
       "       [2, 5, 4, 3, 5],\n",
       "       [4, 4, 5, 4, 0]])"
      ]
     },
     "execution_count": 520,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# changing 99 values to 0 so that they don't affect the row sums\n",
    "(M!=99)*M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 521,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([18, 11, 10, 19, 17])"
      ]
     },
     "execution_count": 521,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# row sums of the above matrix\n",
    "foo = np.sum((M!=99)*M,1)\n",
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 522,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5, 5, 4, 5, 4])"
      ]
     },
     "execution_count": 522,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of ratings per user (i.e. per row)\n",
    "bar = np.sum((M!=99),1)\n",
    "bar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 523,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3.6 ,  2.2 ,  2.5 ,  3.8 ,  4.25])"
      ]
     },
     "execution_count": 523,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# row averages\n",
    "row_averages = foo/bar # elementwise division\n",
    "row_averages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 524,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  1.4 ,  -1.6 ,   0.4 ,   0.4 ,  -0.6 ],\n",
       "       [  0.8 ,  -1.2 ,  -0.2 ,   1.8 ,  -1.2 ],\n",
       "       [ -0.5 ,  99.  ,   0.5 ,  -1.5 ,   1.5 ],\n",
       "       [ -1.8 ,   1.2 ,   0.2 ,  -0.8 ,   1.2 ],\n",
       "       [ -0.25,  -0.25,   0.75,  -0.25,  99.  ]])"
      ]
     },
     "execution_count": 524,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_step1 = []\n",
    "for i,row in enumerate(M):\n",
    "    M_step1 += map(lambda x: x-row_averages[i] if x!=99 else 99, row)\n",
    "\n",
    "M_step1 = np.array(M_step1).reshape(5,5)\n",
    "M_step1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 525,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-0.35, -1.85,  1.65, -0.35,  0.9 ])"
      ]
     },
     "execution_count": 525,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# column sums of the above matrix\n",
    "foo = np.sum((M_step1!=99)*M_step1,0)\n",
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 526,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5, 4, 5, 5, 4])"
      ]
     },
     "execution_count": 526,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of ratings per item (i.e. per column)\n",
    "bar = np.sum((M_step1!=99),0)\n",
    "bar# number of ratings per item (i.e. per column)\n",
    "bar = np.sum((M_step1!=99),0)\n",
    "bar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 527,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-0.07  , -0.4625,  0.33  , -0.07  ,  0.225 ])"
      ]
     },
     "execution_count": 527,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# column averages\n",
    "col_averages = foo/bar # elementwise division\n",
    "col_averages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 548,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  1.47000000e+00,  -1.13750000e+00,   7.00000000e-02,\n",
       "          4.70000000e-01,  -8.25000000e-01],\n",
       "       [  8.70000000e-01,  -7.37500000e-01,  -5.30000000e-01,\n",
       "          1.87000000e+00,  -1.42500000e+00],\n",
       "       [ -4.30000000e-01,   9.90000000e+01,   1.70000000e-01,\n",
       "         -1.43000000e+00,   1.27500000e+00],\n",
       "       [ -1.73000000e+00,   1.66250000e+00,  -1.30000000e-01,\n",
       "         -7.30000000e-01,   9.75000000e-01],\n",
       "       [ -1.80000000e-01,   2.12500000e-01,   4.20000000e-01,\n",
       "         -1.80000000e-01,   9.90000000e+01]])"
      ]
     },
     "execution_count": 548,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_step2 = []\n",
    "for i,row in enumerate(M_step1.T): # take transpose of the M_step1 and consider the rows\n",
    "    M_step2 += map(lambda x: x-col_averages[i] if x!=99 else 99, row)\n",
    "\n",
    "M_step2 = (np.array(M_step2).reshape(5,5)).T # need to take the transpose again\n",
    "M_step2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (b) First subtract from each element the average of its column, and then subtract from each element the average of its modified row."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 550,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5,  2,  4,  4,  3],\n",
       "       [ 3,  1,  2,  4,  1],\n",
       "       [ 2, 99,  3,  1,  4],\n",
       "       [ 2,  5,  4,  3,  5],\n",
       "       [ 4,  4,  5,  4, 99]])"
      ]
     },
     "execution_count": 550,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 560,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([16, 12, 18, 16, 13])"
      ]
     },
     "execution_count": 560,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# column sums of the above matrix (not including the missing values denoted by 99)\n",
    "foo = np.sum((M!=99)*M,0)\n",
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 561,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5, 4, 5, 5, 4])"
      ]
     },
     "execution_count": 561,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of ratings per item (i.e. per column)\n",
    "bar = np.sum((M!=99),0)\n",
    "bar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 562,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3.2 ,  3.  ,  3.6 ,  3.2 ,  3.25])"
      ]
     },
     "execution_count": 562,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# column averages\n",
    "col_averages = foo/bar # elementwise division\n",
    "col_averages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 563,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  1.8 ,  -1.  ,   0.4 ,   0.8 ,  -0.25],\n",
       "       [ -0.2 ,  -2.  ,  -1.6 ,   0.8 ,  -2.25],\n",
       "       [ -1.2 ,  99.  ,  -0.6 ,  -2.2 ,   0.75],\n",
       "       [ -1.2 ,   2.  ,   0.4 ,  -0.2 ,   1.75],\n",
       "       [  0.8 ,   1.  ,   1.4 ,   0.8 ,  99.  ]])"
      ]
     },
     "execution_count": 563,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_step1 = []\n",
    "for i,row in enumerate(M.T): # take transpose of the M_step1 and consider the rows\n",
    "    M_step1 += map(lambda x: x-col_averages[i] if x!=99 else 99, row)\n",
    "\n",
    "M_step1 = (np.array(M_step1).reshape(5,5)).T # need to take the transpose again\n",
    "M_step1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 564,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1.75, -5.25, -3.25,  2.75,  4.  ])"
      ]
     },
     "execution_count": 564,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# row sums of the above matrix\n",
    "foo = np.sum((M!=99)*M_step1,1)\n",
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 565,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5, 5, 4, 5, 4])"
      ]
     },
     "execution_count": 565,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of ratings per user (i.e. per row)\n",
    "bar = np.sum((M!=99),1)\n",
    "bar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 566,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.35  , -1.05  , -0.8125,  0.55  ,  1.    ])"
      ]
     },
     "execution_count": 566,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# row averages\n",
    "row_averages = foo/bar # elementwise division\n",
    "row_averages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 568,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  1.45000000e+00,  -1.35000000e+00,   5.00000000e-02,\n",
       "          4.50000000e-01,  -6.00000000e-01],\n",
       "       [  8.50000000e-01,  -9.50000000e-01,  -5.50000000e-01,\n",
       "          1.85000000e+00,  -1.20000000e+00],\n",
       "       [ -3.87500000e-01,   9.90000000e+01,   2.12500000e-01,\n",
       "         -1.38750000e+00,   1.56250000e+00],\n",
       "       [ -1.75000000e+00,   1.45000000e+00,  -1.50000000e-01,\n",
       "         -7.50000000e-01,   1.20000000e+00],\n",
       "       [ -2.00000000e-01,   1.11022302e-16,   4.00000000e-01,\n",
       "         -2.00000000e-01,   9.90000000e+01]])"
      ]
     },
     "execution_count": 568,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_step2 = []\n",
    "for i,row in enumerate(M_step1):\n",
    "    M_step2 += map(lambda x: x-row_averages[i] if x!=99 else 99, row)\n",
    "\n",
    "M_step2 = np.array(M_step2).reshape(5,5)\n",
    "M_step2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, the two methods produce different normalized matrices, but they are indeed close."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}