solutions/20200929/Vector_space_retrieval.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vector space retrieval\n",
    "\n",
    "This exercise is about scoring a (toy-sized) document collection against a query using various retrieval functions instantiated in the vector space model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ipytest\n",
    "import math\n",
    "import operator\n",
    "import pytest\n",
    "\n",
    "from abc import ABC, abstractmethod\n",
    "\n",
    "ipytest.autoconfig()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Term-document matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "TD_MATRIX = {\n",
    "    'beijing': [0, 1, 0, 0, 1],\n",
    "    'dish': [0, 1, 0, 0, 1],\n",
    "    'duck': [3, 2, 2, 0, 1],\n",
    "    'rabbit': [0, 0, 1, 1, 0],\n",
    "    'recipe': [0, 0, 1, 1, 1],\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scoring\n",
    "\n",
    "The general scoring function is \n",
    "\n",
    "$$score(d,q) = \\sum_{t \\in q} w_{t,d} \\times w_{t,q}$$\n",
    "\n",
    "where $w_{t,d}$ is the term's weight in the document and $w_{t,q}$ is the term's weight in the query.\n",
    "\n",
    "The `Scorer` class below provides an abstract implementation of the above function. For a specific instantiation,  you'll need to create a child class and implement `_get_query_term_weight()` and `_get_doc_term_weight()`.\n",
    "\n",
    "For your convenience, the collection is provided in the form of a term-document matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AbstractScorer(ABC):\n",
    "    def __init__(self, td_matrix):\n",
    "        self._td_matrix = td_matrix\n",
    "        self._num_docs = len(td_matrix[list(td_matrix.keys())[0]])\n",
    "        self._query_terms = None\n",
    "\n",
    "    def _parse_query(self, query):\n",
    "        \"\"\"Parses the input query to a sequence of vocabulary terms and stores it in a member variable.\"\"\"\n",
    "        self._query_terms = []\n",
    "        for term in query.split():\n",
    "            if term in self._td_matrix:\n",
    "                self._query_terms.append(term)\n",
    "\n",
    "        \n",
    "    def score_documents(self, query):\n",
    "        \"\"\"Score all documents in the collection.\n",
    "        \n",
    "        Params:\n",
    "            query: Query string\n",
    "        \n",
    "        Returns:\n",
    "            List of (document ID, score) tuples ordered by score descending, then by doc ID ascending.\n",
    "        \"\"\"\n",
    "        scores = {doc_id: 0 for doc_id in range(self._num_docs)}\n",
    "        self._parse_query(query)\n",
    "        \n",
    "        for term in set(self._query_terms):\n",
    "            for doc_id in range(self._num_docs):\n",
    "                scores[doc_id] += self._get_doc_term_weight(doc_id, term) * self._get_query_term_weight(term)\n",
    "                \n",
    "        return [(doc_id, score) for doc_id, score in sorted(scores.items(), key=lambda x: (x[1], -x[0]), reverse=True)]\n",
    "        \n",
    "    @abstractmethod\n",
    "    def _get_query_term_weight(self, term):\n",
    "        return 1\n",
    "    \n",
    "    @abstractmethod\n",
    "    def _get_doc_term_weight(self, doc_id, term):\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1: Binary scorer\n",
    "\n",
    "Set $w_{t,d}$ to 1 if $t$ is present in the document otherwise $0$.\n",
    "Similarly, Set $w_{t,q}$ to 1 if $t$ is present in the query otherwise $0$.\n",
    "\n",
    "This method will then score documents based on the number of matching (unique) query terms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryScorer(AbstractScorer):\n",
    "    \n",
    "    def _get_query_term_weight(self, term):\n",
    "        return 1 if term in self._query_terms else 0\n",
    "    \n",
    "    def _get_doc_term_weight(self, doc_id, term):\n",
    "        return 1 if self._td_matrix[term][doc_id] > 0 else 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "..                                                                                 [100%]\n",
      "2 passed in 0.02s\n"
     ]
    }
   ],
   "source": [
    "%%run_pytest[clean]\n",
    "\n",
    "@pytest.mark.parametrize('td_matrix,query,correct_values', [\n",
    "    (TD_MATRIX, 'beijing', [(1, 1), (4, 1), (0, 0), (2, 0), (3, 0)]),\n",
    "    (TD_MATRIX, 'beijing duck recipe', [(4, 3), (1, 2), (2, 2), (0, 1), (3, 1)]),\n",
    "])\n",
    "def test_binary_scorer(td_matrix, query, correct_values):  \n",
    "    scorer = BinaryScorer(td_matrix)\n",
    "    assert scorer.score_documents(query) == correct_values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2: TF scorer\n",
    "\n",
    "Set $w_{t,d}=\\frac{c_{t,d}}{|d|}$, that is, the relative frequency of the term in the document.\n",
    "\n",
    "For $w_{t,q}$, use the frequency (count) of the term in the query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TFScorer(AbstractScorer):\n",
    "    \n",
    "    def __init__(self, td_matrix):\n",
    "        super(TFScorer,self).__init__(td_matrix)\n",
    "        # Pre-compute the length of documents for more efficient scoring.\n",
    "        self._doc_len = {}\n",
    "        for doc_id in range(self._num_docs):\n",
    "            self._doc_len[doc_id] = sum(self._td_matrix[term][doc_id] for term in self._td_matrix.keys())\n",
    "    \n",
    "    def _get_query_term_weight(self, term):\n",
    "        return self._query_terms.count(term)\n",
    "    \n",
    "    def _get_doc_term_weight(self, doc_id, term):\n",
    "        return self._td_matrix[term][doc_id] / self._doc_len[doc_id]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "...                                                                                [100%]\n",
      "3 passed in 0.01s\n"
     ]
    }
   ],
   "source": [
    "%%run_pytest[clean]\n",
    "\n",
    "@pytest.mark.parametrize('td_matrix,query,correct_values', [\n",
    "    (TD_MATRIX, 'beijing', [(1, 0.25), (4, 0.25), (0, 0), (2, 0), (3, 0)]),\n",
    "    (TD_MATRIX, 'duck duck', [(0, 2), (1, 1), (2, 1), (4, 0.5), (3, 0)]),\n",
    "    (TD_MATRIX, 'beijing duck recipe', [(0, 1.0), (1, 0.75), (2, 0.75), (4, 0.75), (3, 0.5)]),\n",
    "])\n",
    "def test_tf_scorer(td_matrix, query, correct_values):  \n",
    "    scorer = TFScorer(td_matrix)\n",
    "    assert scorer.score_documents(query) == correct_values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 3: TD-IDF scorer\n",
    "\n",
    "Implement the scoring function \n",
    "\n",
    "$$score(d,q) = \\sum_{t \\in q} tf_{t,q} \\times tf_{t,d} \\times idf_t$$\n",
    "\n",
    "Use normalized frequencies for TF weight, i.e., $tf_{t,d}=\\frac{c_{t,d}}{|d|}$, where $c_{t,d}$ is the number of occurrences of term $t$ in document $d$ and $|d|$ is the document length (=total number of terms). (Analogously for the query.)\n",
    "\n",
    "Compute IDF values using the following formula: $idf_{t}=\\log \\frac{N}{n_t}$, where $N$ is the total number of documents and $n_t$ is the number of documents that contain term $t$.  Use base-10 the logarithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TFIDFScorer(AbstractScorer):\n",
    "    \n",
    "    def __init__(self, td_matrix):\n",
    "        super(TFIDFScorer,self).__init__(td_matrix)\n",
    "        # Pre-compute the length of documents for more efficient scoring.\n",
    "        self._doc_len = {}\n",
    "        for doc_id in range(self._num_docs):\n",
    "            self._doc_len[doc_id] = sum(self._td_matrix[term][doc_id] for term in self._td_matrix.keys())\n",
    "        # Pre-compute IDF values.\n",
    "        self._idf = {}\n",
    "        for term, freqs in self._td_matrix.items():\n",
    "            nt = sum(1 if f > 0 else 0 for f in freqs)\n",
    "            self._idf[term] = math.log10(self._num_docs / nt)\n",
    "    \n",
    "    def _get_query_term_weight(self, term):\n",
    "        return self._query_terms.count(term) / len(self._query_terms)\n",
    "    \n",
    "    def _get_doc_term_weight(self, doc_id, term):\n",
    "        return self._td_matrix[term][doc_id] / self._doc_len[doc_id] * self._idf[term]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "...                                                                                [100%]\n",
      "3 passed in 0.01s\n"
     ]
    }
   ],
   "source": [
    "%%run_pytest[clean]\n",
    "\n",
    "@pytest.mark.parametrize('td_matrix,query,correct_values', [\n",
    "    (TD_MATRIX, 'beijing', [(1, 0.0995), (4, 0.0995), (0, 0), (2, 0), (3, 0)]),\n",
    "    (TD_MATRIX, 'duck duck', [(0, 0.0969), (1, 0.0485), (2, 0.0485), (4, 0.0242), (3, 0)]),\n",
    "    (TD_MATRIX, 'beijing duck recipe', [(4, 0.0597), (1, 0.0493), (3, 0.0369), (2, 0.0346), (0, 0.0323)]),\n",
    "])\n",
    "def test_tfidf_scorer(td_matrix, query, correct_values):  \n",
    "    scorer = TFIDFScorer(td_matrix)\n",
    "    ranking = scorer.score_documents(query)\n",
    "    assert [x[0] for x in ranking] == [x[0] for x in correct_values]  # Checking ranking\n",
    "    assert [x[1] for x in ranking] == pytest.approx([x[1] for x in correct_values], rel=1e-2)  # Checking scores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Feedback\n",
    "\n",
    "Please give (anonymous) feedback on this exercise by filling out [this form](https://forms.gle/2jPayczbFhEcC9K68)."
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}