02_boolean_model.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "**Disclaimer:** some of the material is borrowed with thanks from http://www.cis.lmu.de/~hs/teach/14s/ir/\n",
    "\n",
    "# Boolean model\n",
    "\n",
    "* The Boolean model is arguably the simplest model to\n",
    "  base an information retrieval system on.\n",
    "* Queries are Boolean expressions, e.g., *Caesar* and *Brutus*\n",
    "* The seach engine returns all documents that satisfy the Boolean expression, but there are exceptions:\n",
    "  * anchor text\n",
    "  * page contains variant of query words: morphology, spelling correction, synonyms\n",
    "* No notion of ranking\n",
    "\n",
    "## Term-document matrix\n",
    "\n",
    "* Rows: terms\n",
    "* Columns: document\n",
    "* $M_{ij}=1$ if term *i* present in document *j*\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Term-document matrix:\n",
      "\n",
      "[[0 0 1 0]\n",
      " [1 0 0 1]\n",
      " [0 0 0 1]\n",
      " [0 1 0 0]\n",
      " [1 1 0 1]\n",
      " [0 0 0 1]\n",
      " [0 0 1 0]\n",
      " [1 0 0 1]\n",
      " [0 0 0 1]\n",
      " [0 0 1 0]\n",
      " [1 0 0 0]\n",
      " [0 0 1 0]]\n",
      "\n",
      "IDX -> terms mapping:\n",
      "\n",
      "['Nothing', 'This', 'and', 'better', 'example', 'great', 'here', 'is', 'long', 'see', 'silly', 'to']\n",
      "\n",
      "term -> IDX mapping:\n",
      "\n",
      "{'silly': 10, 'This': 1, 'and': 2, 'better': 3, 'is': 7, 'example': 4, 'here': 6, 'great': 5, 'see': 9, 'Nothing': 0, 'to': 11, 'long': 8}\n"
     ]
    }
   ],
   "source": [
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "documents=[\"This is a silly example\",\"A better example\",\"Nothing to see here\",\"This is a great and long example\"]\n",
    "cv=CountVectorizer(lowercase=False,binary=True)\n",
    "print(\"Term-document matrix:\\n\")\n",
    "td_matrix=cv.fit_transform(documents).todense().T   #.T transposes the matrix, sklearn maintains document-term\n",
    "print(td_matrix)\n",
    "print(\"\\nIDX -> terms mapping:\\n\")\n",
    "print(cv.get_feature_names())\n",
    "print(\"\\nterm -> IDX mapping:\\n\")\n",
    "print(cv.vocabulary_) # note the _ at the end\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "* Every row is an *incidence vector* of a term - which documents the term appears in\n",
    "* Boolean retrieval in its simplest form:\n",
    "  * Boolean operations on incidence vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "example\n",
      "[[1 1 0 1]]\n",
      "\n",
      "example and great\n",
      "[[0 0 0 1]]\n",
      "\n",
      "not example\n",
      "[[0 0 1 0]]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "t2i=cv.vocabulary_\n",
    "print(\"example\")\n",
    "print(td_matrix[t2i[\"example\"]])\n",
    "print()\n",
    "print(\"example and great\")\n",
    "print(td_matrix[t2i[\"example\"]] & td_matrix[t2i[\"great\"]])\n",
    "print()\n",
    "print(\"not example\")\n",
    "print(1-td_matrix[t2i[\"example\"]]) #1-x does the negation in our case\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can piece it all together:\n",
    "\n",
    "* Accept queries like \"( not example or great ) and Nothing\"\n",
    "* Rewrite them into a Python expression\n",
    "* eval() that expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Query:\"example and not Nothing\"\n",
      "Rewritten: td_matrix[t2i[\"example\"]] & 1 - td_matrix[t2i[\"Nothing\"]]\n",
      "Matching: [[1 1 0 1]]\n",
      "\n",
      "Query:\"not example or great\"\n",
      "Rewritten: 1 - td_matrix[t2i[\"example\"]] | td_matrix[t2i[\"great\"]]\n",
      "Matching: [[0 0 1 1]]\n",
      "\n",
      "Query:\"( not example or great ) and Nothing\"\n",
      "Rewritten: ( 1 - td_matrix[t2i[\"example\"]] | td_matrix[t2i[\"great\"]] ) & td_matrix[t2i[\"Nothing\"]]\n",
      "Matching: [[0 0 1 0]]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Operators and, or, not become &, |, 1 -\n",
    "# Parentheses are left untouched\n",
    "# Everything else interpreted as a term and fed through td_matrix[t2i[\"...\"]]\n",
    "\n",
    "d={\"and\":\"&\",\"or\":\"|\",\"not\":\"1 -\",\"(\":\"(\",\")\":\")\"} # operator replacements\n",
    "def rew_token(t):\n",
    "    return d.get(t,'td_matrix[t2i[\"{}\"]]'.format(t))\n",
    "\n",
    "def rew_query(query): #rewrite every token in the query\n",
    "    return \" \".join(rew_token(t) for t in query.split())\n",
    "\n",
    "def test_query(query):\n",
    "    print(\"Query:\\\"\"+query+\"\\\"\")\n",
    "    print(\"Rewritten:\",rew_query(query))\n",
    "    print(\"Matching:\",eval(rew_query(query)))\n",
    "    print()\n",
    "\n",
    "test_query(\"example and not Nothing\")\n",
    "test_query(\"not example or great\")\n",
    "test_query(\"( not example or great ) and Nothing\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Query:\"not awordwhichdoesnotexist\"\n",
      "Rewritten: 1 - td_matrix[t2i[\"awordwhichdoesnotexist\"]]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Traceback (most recent call last):\n",
      "  File \"<ipython-input-4-69ec74878d51>\", line 5, in <module>\n",
      "    test_query(\"not awordwhichdoesnotexist\") #should match all documents\n",
      "  File \"<ipython-input-3-41857662fdc6>\", line 15, in test_query\n",
      "    print(\"Matching:\",eval(rew_query(query)))\n",
      "  File \"<string>\", line 1, in <module>\n",
      "KeyError: 'awordwhichdoesnotexist'\n"
     ]
    }
   ],
   "source": [
    "# Should match all documents, but crashes instead\n",
    "# This one you will fix as an exercise\n",
    "import traceback\n",
    "try:\n",
    "    test_query(\"not awordwhichdoesnotexist\") #should match all documents\n",
    "except:\n",
    "    traceback.print_exc() #I only need to do this because of IPython"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We now have a rudimentary boolean IR system\n",
    "* It is not that great but ready in < 10 lines of code in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Size constraints\n",
    "\n",
    "* Term-document matrix is vocabulary size times document set size\n",
    "* 1M documents, each 1000 words\n",
    "* 1,000,000 x 1,000 = 1,000,000,000 words of running text\n",
    "* 6 bytes per word -> ~6GB in size\n",
    "* Assume 500,000 unique terms\n",
    "* Term-document matrix has 1,000,000 x 500,000 / 8 / 1024 / 1024 / 1024 -> ~60GB\n",
    "* 60GB of space to index a collection of 6GB of text!\n",
    "* 480GB if we were to use 1B integers to remember the 0/1 values\n",
    "* ...but most of this are zeros...\n",
    "\n",
    "## Sparse representation\n",
    "\n",
    "* Only remember the non-zero entries\n",
    "* For every term, remember a (usually sorted) list of documents in which it appears\n",
    "* This is the famous **inverted index**\n",
    "* Scipy sparse formats: https://docs.scipy.org/doc/scipy-0.18.1/reference/sparse.html\n",
    "  * *CSC* for every column remember the list of rows\n",
    "  * *CSR* for every row remember the list of columns\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "scikit's document-term matrix:\n",
      "  (0, 1)\t1\n",
      "  (0, 7)\t1\n",
      "  (0, 10)\t1\n",
      "  (0, 4)\t1\n",
      "  (1, 4)\t1\n",
      "  (1, 3)\t1\n",
      "  (2, 0)\t1\n",
      "  (2, 11)\t1\n",
      "  (2, 9)\t1\n",
      "  (2, 6)\t1\n",
      "  (3, 1)\t1\n",
      "  (3, 7)\t1\n",
      "  (3, 4)\t1\n",
      "  (3, 5)\t1\n",
      "  (3, 2)\t1\n",
      "  (3, 8)\t1\n",
      "\n",
      "Transposed: (note incorrect sort)\n",
      "  (1, 0)\t1\n",
      "  (7, 0)\t1\n",
      "  (10, 0)\t1\n",
      "  (4, 0)\t1\n",
      "  (4, 1)\t1\n",
      "  (3, 1)\t1\n",
      "  (0, 2)\t1\n",
      "  (11, 2)\t1\n",
      "  (9, 2)\t1\n",
      "  (6, 2)\t1\n",
      "  (1, 3)\t1\n",
      "  (7, 3)\t1\n",
      "  (4, 3)\t1\n",
      "  (5, 3)\t1\n",
      "  (2, 3)\t1\n",
      "  (8, 3)\t1\n",
      "\n",
      "Transposed, and in the correct sparse format:\n",
      "  (0, 2)\t1\n",
      "  (1, 0)\t1\n",
      "  (1, 3)\t1\n",
      "  (2, 3)\t1\n",
      "  (3, 1)\t1\n",
      "  (4, 0)\t1\n",
      "  (4, 1)\t1\n",
      "  (4, 3)\t1\n",
      "  (5, 3)\t1\n",
      "  (6, 2)\t1\n",
      "  (7, 0)\t1\n",
      "  (7, 3)\t1\n",
      "  (8, 3)\t1\n",
      "  (9, 2)\t1\n",
      "  (10, 0)\t1\n",
      "  (11, 2)\t1\n"
     ]
    }
   ],
   "source": [
    "documents=[\"This is a silly example\",\"A better example\",\"Nothing to see here\",\"This is a great and long example\"]\n",
    "cv=CountVectorizer(lowercase=False,binary=True)\n",
    "# Exact same code as above, but I removed the .todense()\n",
    "td_matrix=cv.fit_transform(documents)\n",
    "print(\"scikit's document-term matrix:\")\n",
    "print(td_matrix)\n",
    "print()\n",
    "print(\"Transposed: (note incorrect sort)\")\n",
    "print(td_matrix.T)\n",
    "print()\n",
    "print(\"Transposed, and in the correct sparse format:\")\n",
    "print(td_matrix.T.tocsr())\n",
    "td_matrix=td_matrix.T.tocsr()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Query:\"example and not Nothing\"\n",
      "Rewritten: td_matrix[t2i[\"example\"]].todense() & 1 - td_matrix[t2i[\"Nothing\"]].todense()\n",
      "Matching: [[1 1 0 1]]\n",
      "\n",
      "Query:\"( not example or great ) and Nothing\"\n",
      "Rewritten: ( 1 - td_matrix[t2i[\"example\"]].todense() | td_matrix[t2i[\"great\"]].todense() ) & td_matrix[t2i[\"Nothing\"]].todense()\n",
      "Matching: [[0 0 1 0]]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# The sparse representations do not allow many of the necessary operations, so we need\n",
    "# to make the rows dense, once we retrieve them, not a huge deal for our toy examples\n",
    "def rew_token(t):\n",
    "    return d.get(t,'td_matrix[t2i[\"{}\"]].todense()'.format(t))\n",
    "\n",
    "test_query(\"example and not Nothing\")\n",
    "test_query(\"( not example or great ) and Nothing\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolean retrieval (cont.)\n",
    "\n",
    "* The code above needs `.todense()` to perform the *and / or / not* arithmetics -> inefficient, but simple\n",
    "* Other option - make sure the lists of documents are sorted\n",
    "* AND - intersection of two sorted lists\n",
    "  * Walk the lists (I'll show on the lecture how - it's rather obvious anyway)\n",
    "  * Linear complexity in terms of number of documents\n",
    "  * A good exercise - write a function which takes two lists like those above, and computes their intersection as a new list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Documents for 'example'\n",
      "[0 1 3]\n",
      "\n",
      "Documents for 'great'\n",
      "[3]\n"
     ]
    }
   ],
   "source": [
    "print(\"Documents for 'example'\")\n",
    "print(td_matrix[t2i[\"example\"]].nonzero()[1])\n",
    "print()\n",
    "print(\"Documents for 'great'\")\n",
    "print(td_matrix[t2i[\"great\"]].nonzero()[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Phrase and proximity queries\n",
    "\n",
    "* *\"Stanford university\"* - not the same thing as *Stanford AND university*\n",
    "* The basic inverted index of no help\n",
    "\n",
    "## biword index\n",
    "\n",
    "* Index all word bigrams\n",
    "* \"Stanford university\" becomes a term\n",
    "* \"to be or not to be\" -> \"to be\" and \"be or\" and \"or not\" and \"not to\" + postprocessing\n",
    "* Not a great solution:\n",
    "  * Massive waste of space: blows up the index size quadratically\n",
    "  * Needs postprocessing to weed out the false hits\n",
    "\n",
    "## positional index\n",
    "\n",
    "* For every term, and every document, remember a list of the positions, not just \"1\"\n",
    "* A modification of the sorted list intersection algorithm to answer the query\n",
    "* Also allows proximity queries \"X within N words from Y\"\n",
    "* Quite heavy computationally\n",
    "\n",
    "## combined index\n",
    "\n",
    "* Most common biwords indexed directly\n",
    "* Rest solved with positional indexing\n",
    "* Compromise between the two"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Result ranking\n",
    "\n",
    "* Obviously useful for large document collections\n",
    "* Come up with a number describing the fit of a document to a query\n",
    "* Return top-N documents\n",
    "* Basic observations:\n",
    "  * The more query terms hit, the more relevant the document is\n",
    "  * The more times the query terms hit in the document, the more relevant the document is\n",
    "  * Rare terms are more informative than common terms\n",
    "* Firstly, we don't want to store 0/1, we want to store the count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 1 0]\n",
      " [1 0 0 1]\n",
      " [0 0 0 1]\n",
      " [0 1 0 0]\n",
      " [1 1 0 2]\n",
      " [0 0 0 1]\n",
      " [0 0 3 0]\n",
      " [1 0 0 1]\n",
      " [0 0 0 1]\n",
      " [0 0 2 0]\n",
      " [0 0 1 0]\n",
      " [3 0 0 0]\n",
      " [0 0 1 0]\n",
      " [0 0 0 1]]\n"
     ]
    }
   ],
   "source": [
    "documents=[\"This is a silly silly silly example\",\"A better example\",\"Nothing to see here nor here nor here\",\"This is a great example and a long example too\"]\n",
    "cv=CountVectorizer(lowercase=False)\n",
    "# Exact same code as above, but now I also removed binary=True\n",
    "td_matrix=cv.fit_transform(documents)\n",
    "t2i=cv.vocabulary_\n",
    "td_matrix=td_matrix.T.tocsr()\n",
    "print(td_matrix.todense())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Sum up the counts across query hits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Documents for 'example' and 'better'\n",
      "Hits:\n",
      "  (0, 0)\t1\n",
      "  (0, 1)\t2\n",
      "  (0, 3)\t2\n",
      "Documents: [0 1 3]\n",
      "Scores: [1 2 2]\n"
     ]
    }
   ],
   "source": [
    "print(\"Documents for 'example' and 'better'\")\n",
    "hits=td_matrix[t2i[\"example\"]]+td_matrix[t2i[\"better\"]]\n",
    "print(\"Hits:\",hits,sep=\"\\n\")\n",
    "print(\"Documents:\", hits.nonzero()[1])\n",
    "print(\"Scores:\", hits[hits.nonzero()].A1) #A1 returns itself as flat array\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now we can sort on scores and get an order on documents\n",
    "* Now a document with 2x example hits equally well as document with 1x example and 1x better\n",
    "* Maybe not optimal?\n",
    "* A document with a term occurring 10x is more important, but not ten times so\n",
    "* Usual solution: squeeze the counts through log or similar function (done already at index time)\n",
    "  * $1+log_{10}(tf)$ is a typical formula used"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Just to check we get same numbers as with CountVectorizer:\n",
      "[[ 0.  0.  1.  0.]\n",
      " [ 1.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  1.  0.  2.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  3.  0.]\n",
      " [ 1.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  2.  0.]\n",
      " [ 0.  0.  1.  0.]\n",
      " [ 3.  0.  0.  0.]\n",
      " [ 0.  0.  1.  0.]\n",
      " [ 0.  0.  0.  1.]]\n",
      "Just to check we get same numbers as with CountVectorizer:\n",
      "[[ 0.          0.          1.          0.        ]\n",
      " [ 1.          0.          0.          1.        ]\n",
      " [ 0.          0.          0.          1.        ]\n",
      " [ 0.          1.          0.          0.        ]\n",
      " [ 1.          1.          0.          1.69314718]\n",
      " [ 0.          0.          0.          1.        ]\n",
      " [ 0.          0.          2.09861229  0.        ]\n",
      " [ 1.          0.          0.          1.        ]\n",
      " [ 0.          0.          0.          1.        ]\n",
      " [ 0.          0.          1.69314718  0.        ]\n",
      " [ 0.          0.          1.          0.        ]\n",
      " [ 2.09861229  0.          0.          0.        ]\n",
      " [ 0.          0.          1.          0.        ]\n",
      " [ 0.          0.          0.          1.        ]]\n"
     ]
    }
   ],
   "source": [
    "# Switch from CountVectorizer to TfidfVectorizer\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "# Parameters with which TfidfVectorizer does same thing as CountVectorizer\n",
    "tfv=TfidfVectorizer(lowercase=False,sublinear_tf=False,use_idf=False,norm=None)\n",
    "td_matrix=tfv.fit_transform(documents)\n",
    "t2i=cv.vocabulary_\n",
    "td_matrix=td_matrix.T.tocsr()\n",
    "print(\"Just to check we get same numbers as with CountVectorizer:\")\n",
    "print(td_matrix.todense())\n",
    "\n",
    "# Turn log-squeeze on\n",
    "tfv=TfidfVectorizer(lowercase=False,sublinear_tf=True,use_idf=False,norm=None)\n",
    "td_matrix=tfv.fit_transform(documents)\n",
    "t2i=cv.vocabulary_\n",
    "td_matrix=td_matrix.T.tocsr()\n",
    "print(\"Just to check we get same numbers as with CountVectorizer:\")\n",
    "print(td_matrix.todense())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* and now the *example* and *better* document should rank above the *2x example* document"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Documents for 'example' and 'better'\n",
      "Hits:\n",
      "  (0, 0)\t1.0\n",
      "  (0, 1)\t2.0\n",
      "  (0, 3)\t1.69314718056\n",
      "Documents: [0 1 3]\n",
      "Scores: [ 1.          2.          1.69314718]\n"
     ]
    }
   ],
   "source": [
    "print(\"Documents for 'example' and 'better'\")\n",
    "hits=td_matrix[t2i[\"example\"]]+td_matrix[t2i[\"better\"]]\n",
    "print(\"Hits:\",hits,sep=\"\\n\")\n",
    "print(\"Documents:\", hits.nonzero()[1])\n",
    "print(\"Scores:\", hits[hits.nonzero()].A1) #A1 returns itself as flat array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Informativeness of terms\n",
    "\n",
    "* Not all words are equally informative\n",
    "* Rare words are clearly much more informative than common ones\n",
    "* The query *\"jabberwocky movie cast\"* should put more weight on *jabberwocky*\n",
    "* What we want:\n",
    "  * High positive weight for rare terms\n",
    "  * Low positive weight for common terms\n",
    "* Typical way: IDF *inverse document frequency*\n",
    "  * df_t is the *document frequency* of *t* - number of documents *t* appear in\n",
    "  * $IDF_t=\\frac{N}{df_t}$ inverse document frequency of *t*\n",
    "  * Usually one would squeeze this through log so\n",
    "  * $IDF_t=log_{10}(\\frac{N}{df_t})$\n",
    "\n",
    "## Tf.Idf\n",
    "\n",
    "* An extremely common weighting scheme in IR\n",
    "* Product of term's tf (log-squeezed) with the term's idf (log-squeezed)\n",
    "* Gives a score of that term's hit in a given document\n",
    "  * $(1+log_{10}tf_t)\\cdot log_{10}\\frac{N}{df_t}$\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Just to check we get same numbers as with CountVectorizer:\n",
      "[[ 0.          0.          1.91629073  0.        ]\n",
      " [ 1.51082562  0.          0.          1.51082562]\n",
      " [ 0.          0.          0.          1.91629073]\n",
      " [ 0.          1.91629073  0.          0.        ]\n",
      " [ 1.22314355  1.22314355  0.          2.07096206]\n",
      " [ 0.          0.          0.          1.91629073]\n",
      " [ 0.          0.          4.02155128  0.        ]\n",
      " [ 1.51082562  0.          0.          1.51082562]\n",
      " [ 0.          0.          0.          1.91629073]\n",
      " [ 0.          0.          3.24456225  0.        ]\n",
      " [ 0.          0.          1.91629073  0.        ]\n",
      " [ 4.02155128  0.          0.          0.        ]\n",
      " [ 0.          0.          1.91629073  0.        ]\n",
      " [ 0.          0.          0.          1.91629073]]\n"
     ]
    }
   ],
   "source": [
    "# same as above, but use_idf=True\n",
    "tfv=TfidfVectorizer(lowercase=False,sublinear_tf=True,use_idf=True,norm=None)\n",
    "td_matrix=tfv.fit_transform(documents)\n",
    "t2i=cv.vocabulary_\n",
    "td_matrix=td_matrix.T.tocsr()\n",
    "print(\"Just to check we get same numbers as with CountVectorizer:\")\n",
    "print(td_matrix.todense())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Documents for 'example' and 'better' with full tf.idf weighting\n",
      "Hits:\n",
      "  (0, 0)\t1.22314355131\n",
      "  (0, 1)\t3.13943428319\n",
      "  (0, 3)\t2.07096205533\n",
      "Documents: [0 1 3]\n",
      "Scores: [ 1.22314355  3.13943428  2.07096206]\n"
     ]
    }
   ],
   "source": [
    "print(\"Documents for 'example' and 'better' with full tf.idf weighting\")\n",
    "hits=td_matrix[t2i[\"example\"]]+td_matrix[t2i[\"better\"]]\n",
    "print(\"Hits:\",hits,sep=\"\\n\")\n",
    "print(\"Documents:\", hits.nonzero()[1])\n",
    "print(\"Scores:\", hits[hits.nonzero()].A1) #A1 returns itself as flat array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Doesn't work on toy examples, really, let's index a bit more\n",
    "* http://linguatools.org/tools/corpora/wikipedia-monolingual-corpora/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<article name=\"Amsterdam\">\n",
      "Amsterdam on Alankomaiden pääkaupunki. Amsterdam on väkiluvultaan Alankomaiden suurin kaupunki, huhtikuun alussa 2006 siellä asui 743 905 asukasta eli noin joka 20. hollantilainen asuu varsinaisessa Amsterdamissa. Yhteensä Amsterdamissa ja sitä ympäröivällä kaupunkialueella asuu noin 1 450 000 ihmistä eli vajaa kymmenesosa Alankomaiden asukkaista. Amsterdam sijaitsee Amstelin suistossa IJsselmeerin rannalla Alankomaiden Pohjois-Hollannin provinssissa. Vaikka Amsterdam on Alankomaiden perustuslain mukaan maan pääkaupunki, sijaitsee niin kuningashuone, hallitus, parlamentti kuin korkein oikeuskin Haagissa.\n",
      "Historia\n",
      "Amsterdamin paikalle rakennettiin ensimmäiset puutalot 1200-luvun alkupuolella. Kaupunki linnoitettiin suojaksi vihollisilta; Amstel-joki padottiin nykyisen Damin aukion kohdalta. Padon avulla pystyttiin säätelemään veden korkeuden lisäksi myös kauppaa, sillä se esti merikelpoisia aluksia purjehtimasta yläjuoksulle. Siksi rahti jouduttiinkin siirtämään paikallisiin aluksiin jatkokuljetusta varten. Näin asukkaat saivat tästä koituneet tulot itselleen.\n",
      "Vuonna 1275 Amsterdam sai Hollannin kreiviltä oikeuden kuljettaa rahtia Amstel-joella ilman tulleja, ja sen seurauksena kyseisen joen kauppa monopolisoitui. Amsterdamin mahti kaupankäynnissä vain kasvoi, kun se pystyi viemään yhä useampaa tuotetta muualle Eurooppaan vapaasti, esimerkiksi olutta.\n",
      "Kauppa laajeni ja 1300- ja 1400-luvulla kaupungin asukasluku kasvoi nopeasti. Se kuitenkin kärsi tuhoisista tulipaloista vuosina 1421 ja 1452, jotka hävittivät suuren osan kaupunkia. Sen seurauksena puurakentaminen kiellettiin ja ensisijaiseksi rakennusmateriaaliksi tuli tiili.\n",
      "1400-luvulla hallitsijasukujen väliset avioliitot johtivat siihen, että valtaan tuli maassa Espanjan Kaarle V, joka hallitsi myös Itävaltaa. Espanjan hallinta-aika oli erittäin julmaa. Tärkeänä kauppasatamana Amsterdam kuitenkin säästyi pahimmalta sorrolta ja väkivallalta. Sen väkiluku kolminkertaistui, kun sinne muutti pakolaisia muualta valtakunnasta, myös juutalaisia Portugalista.\n",
      "Jean Calvinin oppien juurruttua maahan Espanja alkoi kurittaa harhaoppisia. Damin aukiolla taas järjestettiin paavin vastaisia mielenosoituksia. Katoliset Espanjan johtajat kielsivät lopulta kalvinismin ja protestanttien vainoaminen jatkui.\n",
      "Vuonna 1578 amsterdamilaiset ryhtyivät kapinaan ja häätivät paavin kannattajat pois kaupungista. Katolisia kirkkoja hävitettiin ja katolisia käännytettiin protestanteiksi.\n",
      "Espanjan vallan loputtua Amsterdamissa alkoivat paremmat ajat. Kaupankäynti laajentui jatkuvasti ja siitä seurannutta kukoistusaikaa kutsutaan Alankomaiden kulta-ajaksi. Amsterdamin elinkeinoelämän mahdollisuudet houkuttelivat kaupunkiin paljon uusia asukkaita. Vanha keskiaikainen kaupunki jäi liian pieneksi ja uusia kanavia alettiin rakentaa. 1600-luvulla kaupungin reunamille muodostui kolmen kanavan Kanavakehä (Grachtengordel), joka on vuodesta 2010 ollut ssa. Kanavat Herengraht, Keizersgracht ja Prinsengracht rakentuivat täyteen toinen toistaan komeampia päätykolmiotaloja. Vauraus johti myös taiteen ja luonnontieteen kehitykseen. Rembrandt, Frans Hals, Vermeer ja Paulus Potter vaikuttivat siihen aikaan, ja heidän työnsä olivat erittäin kysyttyjä vauraamman väestönosan keskuudessa.\n",
      "1700-luvulla Amsterdamista tuli maailman suurin pankkikeskus, mutta kulta-aika oli loppumassa. Ison-Britannian tuhottua maan laivaston sodassa vuonna 1780, alkoi todellinen rappio. Myös Yhdistynyt Itä-Intian kauppakomppania(VOC) teki vararikon vuonna 1791. Neljä vuotta myöhemmin Napoleon valloitti maan ja se oli taas vieraan vallassa.\n",
      "1800-luvulla tilanne Amsterdamissa parani, kun Ranskan valta oli alkanut heiketä. Vuosisadan loppupuolella Amsterdamiin perustettiin suuria puistoja ja museoita, ja elintaso kohosi huomattavasti.\n",
      "Alankomaat pysyi ensimmäisen maailmansodan puolueettomana. 1900-luvun alussa ponnistelut keskittyivät lähinnä maankuivaukseen, jolla pyrittiin lisäämään maataloutta ja elintilaa. Toisessa maailmansodassa maa kuitenkin vallattiin vuonna 1940 ja Amsterdamin juutalaisia vietiin keskitysleireihin, joista he eivät ikinä palanneet. Väestö alkoi nähdä nälkää, kun elintarvikkeiden ja polttoaineen jakelu lopetettiin. Maa vapautettiin vasta vuonna 1945.\n",
      "Toisen maailmansodan jälkeen Amsterdamin suvaitsevaisuus houkutteli paljon hippejä ja muita vaihtoehtokulttuurien edustajia. Kun kaupungin vanhoja rakennuksia oltiin purkamassa, aiheutti tämä suuren vastalausemyrskyn. Näin ollen esimerkiksi Jordaanin alue säästyi. Sittemmin Amsterdamista on kehittynyt yksi maailman suosituimmista kaupunkimatkakohteista, johtuen varmasti historiallisesta keskustasta ja ainutlaatuisesta taidehistoriasta. Nykypäivänä amsterdamilaisten huolenaiheena on ilmaston lämpenemisestä johtuva vedenpinnan nousu, joka uhkaa nousta kriittiselle tasolle. Alankomaissa on tehtävä paljon töitä sen eteen.\n",
      "Maantiede ja ilmasto\n",
      "Amsterdamissa vallitsee lauhkea meri-ilmasto. Sen läheisyys Pohjanmereen vaikuttaa voimakkaasti säätiloihin. Talvet ovat leutoja, lämpötila laskee yhä harvemmin pakkasen puolelle. Kesät ovat yleensä lämpimiä, harvoin kuumia. Syksyt ovat sateisia.\n",
      "Kulttuuri\n",
      "Amsterdam on pienuudestaan huolimatta merkittävä kulttuurikaupunki. Arkkitehtuuri on kaupungissa ainutlaatuista kanaalien hallitessa kaupunkikuvaa. Kaupungissa on useita merkittäviä museoita, muun muassa useita Rembrandtin töitä sisältävä valtionmuseo Rijksmuseum, Vincent van Goghin tuotantoon keskittyvä Van Gogh Museum sekä juutalaisvainojen ajoista kertova Anne Frankin talo.\n",
      "Kaupungissa toimii yksi maailman kuuluisimmista orkestereista, Concertgebouw-orkesteri, joka esiintyy Museumpleinin kupeessa sijaitsevassa Concertgebouw-konserttitalossa. Bimhuis (lähellä keskusrautatieasemaa) keskittyy jazz- sekä improvisoituun musiikkiin. Leidseplein on yksi yöelämän keskuksista, ja sen ympäristössä sijaitsevat Melkweg ja Paradiso ovat areenoita monien eri alojen esiintyjille.\n",
      "Kaupunki on kuuluisa monia vuosisatoja vanhasta suvaitsevaisuuden perinteestä ja siitä onkin muodostunut eurooppalaisen vapaamielisyyden vertauskuva. Prostituutio on laillista, ja punaisten lyhtyjen alue ( ), kannabistuotteita myyvät coffee shopit ja monipuolinen yöelämä (baareja ja kahviloita yhteensä noin 1500) houkuttelevat runsaasti turisteja. Alankomaat ovat kuitenkin päättäneet rajoittaa kannabiksen käyttöä kahviloiden ottaessa käyttöön ns. klubikortit, joita voidaan myöntää vain täysi-ikäisille hollantilaisille.\n",
      "Monumentteja ja rakennuksia\n",
      "Amsterdamin maaperä on huokoista suota. Kovaa hiekkamaata on vasta noin 13 metrin syvyydessä. 1600-luvulta alkaen talot tuettiin paaluttamalla niiden perustukset hiekkamaahan asti. Osa näistä puisista paaluista on mädäntynyt, jolloin talo saattaa vähitellen vajota. Turistikin havaitsee, että vanhat talot voivat olla hiukan vinossa. Vinouden syyksi on esitetty myös tahallista vinoon rakentamista, sillä kanavaan päin kaltevaan taloon voitiin nostaa tavaraa vinssillä helpommin. Tähän viittaa se, että vuonna 1565 määrättiin, että talojen kaltevuus saa olla enintään 1:25.\n",
      "Merkittäviä rakennuksia ja monumentteja:\n",
      "Koninklijk Paleis, kuninkaanlinna\n",
      "Schreierstoren, kyyneltentorni, joka on kaupunginmuurin säilynyt osa\n",
      "tuulimylly De Gooyer\n",
      "Trippenhuis, asekauppiassuvun talo\n",
      "Tiede- ja tekniikkakeskus NEMO, joka esittelee tieteen saavutuksia maallikoille\n",
      "Homomonument, joka on maailman ensimmäinen homoseksuaaleille omistettu muistomerkki, pystytetty toisen maailmansodan homoseksuaalivainojen muistoksi Autojen parkkimaksut kerätään parkkirahastoon ja kunnan liikennerahastoon, joita käytetään autoilun vähentämiseen ja autoilun päästöjen vähentämiseen.\n",
      "Julkinen liikenne Amsterdamissa koostuu lähinnä bussi- ja raitiovaunuverkosta. Tällä hetkellä Amsterdamissa on 16 raitiovaunulinjaa. Kaupungissa on myös neljä metrolinjaa ja viides on rakenteilla. Amsterdamista on hyvät junayhteydet muualle Eurooppaan. Kaupungin kanavia pitkin voi kulkea erilaisilla vesibusseilla. Jotkut vesikulkuneuvot ovat myös vuokrattavissa. Kaupungissa on myös useita ilmaisia lauttayhteyksiä Amstel-joen yli.\n",
      "Lentoasema\n",
      "Vajaan 18 kilometrin etäisyydellä Amsterdamista on Schipholin lentoasema. Se on Hollannin suurin ja matkustajamäärillä mitattuna Euroopan viidenneksi suurin lentoasema. Sen kautta kulki vuonna 2007 yli 47 milj. matkustajaa.\n",
      "Lentoasema on KLM:n kotikenttä. Lentokenttä on 7 metriä merenpinnan alapuolella.\n",
      "Urheilu\n",
      "Amsterdamissa pidettiin kesäolympialaiset 1928. Nykyään Amsterdamissa järjestetään vuosittain Amsterdamin maraton. Kaupungissa järjestetään myös useita rullalautailukilpailuja.\n",
      "Urheiluseurat\n",
      "Kaupungin tunnetuin jalkapalloseura on AFC Ajax. Amsterdamissa on myös muun muassa jääkiekko- ja baseballjoukkueet. Lisäksi kaupungissa on kolme maahockeyseuraa.\n",
      "</article>\n",
      "<article name=\"Aikido\">\n",
      "Aikido ( , suom. harmonian tie) on nykyaikainen japanilainen budō-laji, jonka kehitti Morihei Ueshiba 1900-luvun alkupuolella. Teknisesti tärkein vaikuttaja aikidolle on ollut Daitō-ryū aiki jūjutsu. Aikidolle ominaista on hyökkääjän voimaan ja liikkeeseen mukautuminen ja sen hyväksikäyttö johdattamalla. Ueshiba painotti opetuksessaan myös lajin henkisiä puolia ja pyrkimystä rauhaan. Harjoittelussa tämä näkyy tekniikoiden pehmeydessä - aikidossa vastustajaa ei pyritä vahingoittamaan.\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "zcat fiwiki-20140809-corpus.txt.gz | head -n 40"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import gzip\n",
    "def articles(gzipfile,max_articles=1000):\n",
    "    \"\"\"A function to yield documents, one at a time\"\"\"\n",
    "    with gzip.open(gzipfile,\"rt\") as f:\n",
    "        article=[]\n",
    "        for line in f:\n",
    "            line=line.strip()\n",
    "            article.append(line)\n",
    "            if line==\"</article>\":\n",
    "                yield \" \".join(article)\n",
    "                max_articles-=1\n",
    "                if max_articles==0:\n",
    "                    break\n",
    "                article=[]\n",
    "# Index 50K articles from Wikipedia, turn on lowercasing too\n",
    "tfv_wiki=TfidfVectorizer(input=\"content\",lowercase=True,sublinear_tf=True,use_idf=True,norm=None)\n",
    "td_matrix_wiki=tfv_wiki.fit_transform(articles(\"fiwiki-20140809-corpus.txt.gz\",50000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0      name\n",
      "1.0      article\n",
      "1.11305432843      ja\n",
      "1.19011569707      on\n",
      "1.50000460039      myös\n",
      "1.62696753965      oli\n",
      "1.69136879842      joka\n",
      "1.73190800868      vuonna\n",
      "1.87296392717      se\n",
      "1.90186556724      ovat\n",
      "1.91177105163      ei\n",
      "1.91546109272      sen\n",
      "1.936105359      sekä\n",
      "1.93799412651      mutta\n",
      "2.06521685493      tai\n",
      "2.11805978613      että\n",
      "2.16342684238      hän\n",
      "2.21951261578      jälkeen\n",
      "2.23720493833      jonka\n",
      "2.28766431015      mukaan\n",
      "2.29932965095      kanssa\n",
      "2.31403090933      kun\n",
      "2.3273664381      jossa\n",
      "2.33486107933      vuoden\n",
      "2.34994385961      eli\n",
      "2.35396334404      kuin\n",
      "2.41561959531      kuitenkin\n",
      "2.42190008864      muun\n",
      "2.45879903595      muassa\n",
      "2.47065294936      noin\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "# I will need access to which term is at which position\n",
    "vocab_list=[None]*len(tfv_wiki.vocabulary_)\n",
    "for term,idx in tfv_wiki.vocabulary_.items():\n",
    "    vocab_list[idx]=term\n",
    "\n",
    "# Indirect sort, returns array of indices\n",
    "idf_sorted=np.argsort(tfv_wiki.idf_)\n",
    "# top-30\n",
    "for t_idx in idf_sorted[:30]:\n",
    "    print(tfv_wiki.idf_[t_idx],\"    \",vocab_list[t_idx])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vector-space model\n",
    "\n",
    "* So far we looked at term vectors (rows of the term-document matrix)\n",
    "* We could also think about document vectors (columns of the term-document matrix)\n",
    "* Documents are vectors in a high-dimensional space, terms are the dimensions\n",
    "* Document vectors very high-dimensional but very very sparse\n",
    "* Same for queries - queries can also be seen as vectors in a high-dimensional space\n",
    "* Search:\n",
    "  * similarity between query vector and document vector\n",
    "  * higher similarity means better hit (rank higher)\n",
    "  \n",
    "## Similarity measures\n",
    "\n",
    "* Similarity -> negative distance\n",
    "* Eucledian distance -> affected by vector length\n",
    "* Cosine similarity -> cosine of the angle between query and document vectors\n",
    "  * 1 for total similarity (angle 0)\n",
    "  * -1 for complete opposite\n",
    "  * we only have positive numbers in our vectors, so we are on the [0,1] scale not [-1,1]\n",
    "  * not sensitive to length\n",
    "  * incredibly easy to compute!\n",
    "  * $cos(u,v)=\\frac{u\\cdot v}{||u||\\cdot ||v||}=\\frac{\\sum_i v_i\\cdot u_i}{\\sqrt{\\sum_i u_i^2}\\sqrt{\\sum_i v_i^2}}$\n",
    "  * dot-product of normalized vectors - just multiply the numbers together, really\n",
    "  \n",
    "## Weighting schemes - document, query\n",
    "\n",
    "* Now we can apply different weighting to documents and queries\n",
    "* Typical choice:\n",
    "  * document: log tf, no idf, length-normalized - why no idf?\n",
    "  * query: log tf, log idf, length-normalized\n",
    "  * cosine similarity\n",
    "\n"
   ]
  }
 ],
 "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": 2
}