L8 - tf-idf.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "We introduce the vector space model in this notebook. \n",
    "\n",
    "This notebook is adapted from http://stanford.edu/~rjweiss/public_html/IRiSS2013/text2/notebooks/tfidf.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## From Documents to Bags-of-words\n",
    "\n",
    "In the Vector Space Model (VSM), we view each document as a *bag of words*. (Bag means multiset)\n",
    "\n",
    "In python, the best way to represent a bag is via `collections.counter`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.174  0.711  0.054  0.656  0.928  0.664  0.177  0.23   0.686  0.88 ]\n"
     ]
    }
   ],
   "source": [
    "from pprint import pprint\n",
    "\n",
    "import numpy as np\n",
    "import contextlib\n",
    "\n",
    "@contextlib.contextmanager\n",
    "def printoptions(*args, **kwargs):\n",
    "    original = np.get_printoptions()\n",
    "    np.set_printoptions(*args, **kwargs)\n",
    "    yield \n",
    "    np.set_printoptions(**original)\n",
    "\n",
    "## compact print (numpy array) \n",
    "def cprint(x):\n",
    "    with printoptions(precision=3, suppress=True, linewidth=120):\n",
    "        print(x)        \n",
    "    \n",
    "# test\n",
    "x = np.random.random(10)\n",
    "cprint(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({'loves': 2, 'me': 2, 'more': 1, 'linda': 1, 'julie': 1, 'than': 1})\n",
      "Counter({'me': 2, 'julie': 1, 'loves': 1, 'more': 1, 'jane': 1, 'than': 1, 'likes': 1})\n",
      "Counter({'more': 1, 'baseball': 1, 'basketball': 1, 'he': 1, 'than': 1, 'likes': 1})\n"
     ]
    }
   ],
   "source": [
    "#examples taken from here: http://stackoverflow.com/a/1750187\n",
    "doc_list = ['Julie loves me more than Linda loves me',\n",
    "            'Jane likes me more than Julie loves me',\n",
    "            'He likes basketball more than baseball']\n",
    "\n",
    "bags = []\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "# we use lower() here so that the sorted vocabulary is easier to see.  \n",
    "bags = [Counter(doc.lower().split()) for doc in doc_list]\n",
    "\n",
    "for bag in bags:\n",
    "    print(bag)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we construct the vocabulary and the doc-term matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['baseball',\n",
       " 'basketball',\n",
       " 'he',\n",
       " 'jane',\n",
       " 'julie',\n",
       " 'likes',\n",
       " 'linda',\n",
       " 'loves',\n",
       " 'me',\n",
       " 'more',\n",
       " 'than']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import itertools\n",
    "\n",
    "vocabulary = sorted(list(set(itertools.chain(*[list(b) for b in bags]))))\n",
    "vocabulary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b  b  h  j  j  l  l  l  m  m  t\n",
      "a  a  e  a  u  i  i  o  e  o  h\n",
      "s  s     n  l  k  n  v     r  a\n",
      "e  k     e  i  e  d  e     e  n\n",
      "b  e        e  s  a  s         \n",
      "a  t                           \n",
      "l  b                           \n",
      "l  a                           \n",
      "   l                           \n",
      "   l                           \n"
     ]
    }
   ],
   "source": [
    "def print_vocabulary_vertically(voc, leading_str = '', spacing=2, align=1):\n",
    "    # align = 0: align top; otherwise, align bottom\n",
    "    max_len = max([len(v) for v in voc])\n",
    "    for i in range(max_len):\n",
    "        if align == 0:\n",
    "            line = [v[i] if i < len(v) else ' ' for v in voc]\n",
    "        else:\n",
    "            line = [' ' if i < max_len - len(v) else v[i-max_len] for v in voc]\n",
    "        print('{}{}'.format(leading_str, (' '*spacing).join(line)))\n",
    "\n",
    "print_vocabulary_vertically(vocabulary, align=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Julie loves me more than Linda loves me\n",
      "Jane likes me more than Julie loves me\n",
      "He likes basketball more than baseball\n",
      "\n",
      "    b                           \n",
      "    a                           \n",
      " b  s                           \n",
      " a  k                           \n",
      " s  e                           \n",
      " e  t        j  l  l  l         \n",
      " b  b     j  u  i  i  o     m  t\n",
      " a  a     a  l  k  n  v     o  h\n",
      " l  l  h  n  i  e  d  e  m  r  a\n",
      " l  l  e  e  e  s  a  s  e  e  n\n",
      "----------------------------------------------------------------------\n",
      "[0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 1]\n",
      "[0, 0, 0, 1, 1, 1, 0, 1, 2, 1, 1]\n",
      "[1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "for doc in doc_list:\n",
    "    print(doc)\n",
    "print()\n",
    "vec_list = []\n",
    "print_vocabulary_vertically(vocabulary, leading_str=' ')\n",
    "print('-'*70)\n",
    "for bag in bags:\n",
    "    vec = [bag[v] for v in vocabulary] # Counter['non-existing-key'] = 0\n",
    "    vec_list.append(vec)\n",
    "    print(vec)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we transform raw tf to tf by $1 + \\log(tf)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import log\n",
    "def normalize_tf(tf):\n",
    "    if tf == 0:\n",
    "        return 0.0\n",
    "    else:\n",
    "        return 1.0 + log(tf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "          b                                                               \n",
      "          a                                                               \n",
      "   b      s                                                               \n",
      "   a      k                                                               \n",
      "   s      e                                                               \n",
      "   e      t                    j      l      l      l                     \n",
      "   b      b             j      u      i      i      o             m      t\n",
      "   a      a             a      l      k      n      v             o      h\n",
      "   l      l      h      n      i      e      d      e      m      r      a\n",
      "   l      l      e      e      e      s      a      s      e      e      n\n",
      "--------------------------------------------------------------------------------\n",
      "[[ 0.     0.     0.     0.     1.     0.     1.     1.693  1.693  1.     1.   ]\n",
      " [ 0.     0.     0.     1.     1.     1.     0.     1.     1.693  1.     1.   ]\n",
      " [ 1.     1.     1.     0.     0.     1.     0.     0.     0.     1.     1.   ]]\n"
     ]
    }
   ],
   "source": [
    "tf_vec_list = []\n",
    "for vec in vec_list:\n",
    "    tf_vec_list.append([normalize_tf(val) for val in vec])\n",
    "\n",
    "print_vocabulary_vertically(vocabulary, leading_str='   ', spacing=6)\n",
    "print('-'*80)\n",
    "cprint(np.matrix(tf_vec_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Adding idf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above vectors in `vec_list` only keep track of term frequencies (`tf`s). Now we make each element $w_{d, t} = tf(d, t) \\cdot idf(t)$. \n",
    "\n",
    "Note that the textbook version of idf will have 0 if `df == ndocs`. Therefore, we follow the implementation in Lucene\n",
    "(https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html) which gives: \n",
    "$$idf(t) = 1 + \\log(\\frac{ndocs}{df + 1})$$\n",
    "\n",
    "BTW, on the above page, you can see the detailes and justifications of all major deviations of Lucene's implementation from the standard VSM. You **will** always need to do this to tackle new or specific problems you are facing when you join the workforce, :p. Therefore, a deep understanding of the principles behind the knowledge you learned in the uni is more important. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import log\n",
    "def idf(cnt, ndocs): \n",
    "    # here we use ln(). The base of the log does not matter much. \n",
    "    return 1.0 + log(ndocs/(cnt+1))  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('baseball', 1),\n",
      " ('basketball', 1),\n",
      " ('he', 1),\n",
      " ('jane', 1),\n",
      " ('julie', 2),\n",
      " ('likes', 2),\n",
      " ('linda', 1),\n",
      " ('loves', 3),\n",
      " ('me', 4),\n",
      " ('more', 3),\n",
      " ('than', 3)]\n"
     ]
    }
   ],
   "source": [
    "ndocs = len(doc_list)\n",
    "# voc = [ (v, [b[v] for b in bags]) for v in vocabulary] # if you want to see the individual counts\n",
    "voc = [(v, sum([b[v] for b in bags])) for v in vocabulary]\n",
    "pprint(voc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will eventually record in `voc` the idf values. You can look at the raw `df` value and the resulting `idf` values from the outputs of the above the below cells. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('baseball', 1.4054651081081644),\n",
      " ('basketball', 1.4054651081081644),\n",
      " ('he', 1.4054651081081644),\n",
      " ('jane', 1.4054651081081644),\n",
      " ('julie', 1.0),\n",
      " ('likes', 1.0),\n",
      " ('linda', 1.4054651081081644),\n",
      " ('loves', 0.7123179275482191),\n",
      " ('me', 0.4891743762340093),\n",
      " ('more', 0.7123179275482191),\n",
      " ('than', 0.7123179275482191)]\n",
      "1.4054651081081644\n"
     ]
    }
   ],
   "source": [
    "voc = [(v, idf( sum([b[v] for b in bags]), ndocs)) for v in vocabulary]\n",
    "idf_dict = dict(voc)\n",
    "pprint(voc)\n",
    "print(idf_dict['he'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can look at the final weighted vectors of the documents. \n",
    "\n",
    "We choose to implement it based on matrix operations supported by `numpy`. E.g., to obtained $\\{a_i b_i\\}_{i=1}^n$ from two vector $\\vec{A} = \\{a_i\\}_{i=1}^n$ and $\\vec{B} = \\{b_i\\}_{i=1}^n$, we first construct a diagonal matrix $\\mathbf{D_A}$ whose diagonal elements are $a_i$, then we can obtain the desired result by the standard matrix multiplication of $\\vec{B} \\mathbf{D_A}$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 1.405  0.     0.     0.     0.     0.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     1.405  0.     0.     0.     0.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     0.     1.405  0.     0.     0.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     0.     0.     1.405  0.     0.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     0.     0.     0.     1.     0.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     0.     0.     0.     0.     1.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     0.     0.     0.     0.     0.     1.405  0.     0.     0.     0.   ]\n",
      " [ 0.     0.     0.     0.     0.     0.     0.     0.712  0.     0.     0.   ]\n",
      " [ 0.     0.     0.     0.     0.     0.     0.     0.     0.489  0.     0.   ]\n",
      " [ 0.     0.     0.     0.     0.     0.     0.     0.     0.     0.712  0.   ]\n",
      " [ 0.     0.     0.     0.     0.     0.     0.     0.     0.     0.     0.712]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def build_idf_matrix(idf_vector):\n",
    "    idf_mat = np.zeros((len(idf_vector), len(idf_vector)))\n",
    "    np.fill_diagonal(idf_mat, idf_vector)\n",
    "    return idf_mat\n",
    "\n",
    "idf_matrix = build_idf_matrix([v[1] for v in voc])\n",
    "cprint(idf_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "def l2_normalizer(vec):\n",
    "    denom = np.sum([el**2 for el in vec])\n",
    "    return [(el / math.sqrt(denom)) for el in vec]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.     0.     0.     0.     1.     0.     1.405  1.206  0.828  0.712  0.712]\n",
      " [ 0.     0.     0.     1.405  1.     1.     0.     0.712  0.828  0.712  0.712]\n",
      " [ 1.405  1.405  1.405  0.     0.     1.     0.     0.     0.     0.712  0.712]]\n",
      "\n",
      "After normalization ...\n",
      "[[ 0.     0.     0.     0.     0.404  0.     0.568  0.487  0.335  0.288  0.288]\n",
      " [ 0.     0.     0.     0.565  0.402  0.402  0.     0.286  0.333  0.286  0.286]\n",
      " [ 0.499  0.499  0.499  0.     0.     0.355  0.     0.     0.     0.253  0.253]]\n"
     ]
    }
   ],
   "source": [
    "doc_term_matrix_tfidf = []\n",
    "\n",
    "#performing tf-idf matrix multiplication\n",
    "for vec in tf_vec_list:\n",
    "    doc_term_matrix_tfidf.append(np.dot(vec, idf_matrix))\n",
    "cprint(np.matrix(doc_term_matrix_tfidf)) # np.matrix() just to make it easier to look at\n",
    "\n",
    "\n",
    "#normalizing\n",
    "print('\\nAfter normalization ...')\n",
    "doc_term_matrix_tfidf_l2 = []\n",
    "for tf_vector in doc_term_matrix_tfidf:\n",
    "    doc_term_matrix_tfidf_l2.append(l2_normalizer(tf_vector))\n",
    "\n",
    "cprint(np.matrix(doc_term_matrix_tfidf_l2)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Look at the matrix m before normalization. \n",
    "* `m[0][6] = 1.405`. This is because $tf(d_0, 'linda') = 1$, and $idf('linda') = 1.4054651081081644$. \n",
    "* `m[0][8] = 0.828`. This is because $tf(d_0, 'me') = 1.693$, and $idf('me') = 0.4891743762340093$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Measuring the Similarity of Two Documents\n",
    "\n",
    "We use the cosine to measure the similarity of two weighted vectors. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def normalize(v):\n",
    "    norm = np.linalg.norm(v)\n",
    "    if norm == 0: \n",
    "       return v\n",
    "    return v / norm\n",
    "\n",
    "def cosine(u, v):\n",
    "    a = normalize(u)\n",
    "    b = normalize(v)\n",
    "    return np.inner(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5781798652650999"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosine(doc_term_matrix_tfidf[0], doc_term_matrix_tfidf[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.14544242471587354"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosine(doc_term_matrix_tfidf[0], doc_term_matrix_tfidf[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.28752866083029266"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosine(doc_term_matrix_tfidf[1], doc_term_matrix_tfidf[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modelling a Query as a Document\n",
    "\n",
    "We implement an equivalent form of the `lnc.ltc` model. Therefore, there is no `idf` weighting on the query terms, since it is already used in the document matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "q = 'Linda likes me'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def encode(q, voc):\n",
    "    c = Counter(q.lower().split())\n",
    "    return [normalize_tf(c[v]) if (v in c) else normalize_tf(0) for v in voc]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      b                                             \n",
      "      a                                             \n",
      " b    s                                             \n",
      " a    k                                             \n",
      " s    e                                             \n",
      " e    t              j    l    l    l               \n",
      " b    b         j    u    i    i    o         m    t\n",
      " a    a         a    l    k    n    v         o    h\n",
      " l    l    h    n    i    e    d    e    m    r    a\n",
      " l    l    e    e    e    s    a    s    e    e    n\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 1.0, 0.0, 0.0]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vec_q = encode(q, vocabulary)\n",
    "print_vocabulary_vertically(vocabulary, leading_str=' ', spacing=4)\n",
    "vec_q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scoring Documents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "score of doc[0] = 0.5208482997884292\n",
      "score of doc[1] = 0.4244788020052428\n",
      "score of doc[2] = 0.20488374908794352\n"
     ]
    }
   ],
   "source": [
    "for i, vec in enumerate(vec_list):\n",
    "    print('score of doc[{}] = {}'.format(i, cosine(doc_term_matrix_tfidf[i], vec_q)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def topk(query, k):\n",
    "    v_q = encode(query, vocabulary)\n",
    "    out = []\n",
    "    for i, vec in enumerate(vec_list):\n",
    "        out.append((i, cosine(doc_term_matrix_tfidf[i], v_q)))\n",
    "    answer = sorted(out, key=lambda r: r[1], reverse=True)[:k]\n",
    "    return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 0.352673810629198), (0, 0.34442828548738263), (1, 0.20255422347635244)]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "topk('loves baseball', 3)"
   ]
  },
  {
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}