13 - Lesson - Information Retrieval (IR).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2968d3c6",
   "metadata": {},
   "source": [
    "# Information Retrieval (IR)\n",
    "### Goal of lesson\n",
    "- Learn what Information Retrival is\n",
    "- Topic modeling documents\n",
    "- How to use Term Frequency and understand the limitations\n",
    "- Implement Term Frequency by Inverse Document Frequency (TF-IDF)\n",
    "\n",
    "### What is Information Retrievel (IR)\n",
    "- The task of finding relevant documents in respose to a user query\n",
    "- Web search engines are the most visible IR applications ([wiki](https://en.wikipedia.org/wiki/Information_retrieval))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9fa2216",
   "metadata": {},
   "source": [
    "### Topic Modeling\n",
    "- Models for discovering the topics for a set of document\n",
    "    - e.g., it provides us with methods to organize, understand and summarize large collections of textual information.\n",
    "- Topic modeling can be described as a method for finding a group of words that best represents the information."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5170155b",
   "metadata": {},
   "source": [
    "## Approach 1: Term Frequency\n",
    "\n",
    "### Term Frequency\n",
    "- The number of times a term occurs in a document is called its term frequency ([wiki](https://en.wikipedia.org/wiki/Tf–idf#Term_frequency))\n",
    "\n",
    "$\\text{tf}(t, d) = f_{t, d}$: The number of time term $t$ occurs in document $d$.\n",
    "\n",
    "- There are other ways to define term frequency (see [wiki](https://en.wikipedia.org/wiki/Tf–idf#Term_frequency_2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96f0f947",
   "metadata": {},
   "source": [
    "> #### Programming Notes:\n",
    "> - Libraries used\n",
    ">     - [**nltk**](https://www.nltk.org) - Natural Language Toolkit\n",
    ">     - [**os**](https://docs.python.org/3/library/os.html) Miscellaneous operating system interfaces\n",
    ">     - [**math**](https://docs.python.org/3/library/math.html) Do math with Python\n",
    "> - Functionality and concepts used\n",
    ">     - **List/Dict Comprehension** to convert data ([Lecture on **List Comprehension**](https://youtu.be/vCYEvtfXdig))\n",
    ">     - [**sorted**](https://docs.python.org/3/howto/sorting.html) sort stuff\n",
    ">     - [**lambda**](https://docs.python.org/3/tutorial/controlflow.html#lambda-expressions) lambda functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5770e823",
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import nltk\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "80d7caed",
   "metadata": {},
   "outputs": [],
   "source": [
    "corpus = {}\n",
    "\n",
    "for filename in os.listdir('files/holmes/'):\n",
    "    with open(f'files/holmes/{filename}') as f:\n",
    "        content = [word.lower() for word in nltk.word_tokenize(f.read()) if word.isalpha()]\n",
    "        \n",
    "        freq = {word: content.count(word) for word in set(content)}\n",
    "        \n",
    "        corpus[filename] = freq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "8725abc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "for filename in corpus:\n",
    "    corpus[filename] = sorted(corpus[filename].items(), key=lambda x: x[1], reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "85c32270",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "speckled.txt\n",
      "  the: 600\n",
      "  and: 281\n",
      "  of: 276\n",
      "  a: 252\n",
      "  i: 233\n",
      "face.txt\n",
      "  the: 326\n",
      "  i: 298\n",
      "  and: 226\n",
      "  to: 185\n",
      "  a: 173\n",
      "twisted.txt\n",
      "  the: 493\n",
      "  a: 275\n",
      "  and: 270\n",
      "  i: 238\n",
      "  of: 234\n",
      "squires.txt\n",
      "  the: 508\n",
      "  of: 206\n",
      "  and: 169\n",
      "  to: 168\n",
      "  a: 152\n",
      "coronet.txt\n",
      "  the: 466\n",
      "  i: 356\n",
      "  to: 270\n",
      "  and: 238\n",
      "  a: 213\n",
      "carbuncle.txt\n",
      "  the: 463\n",
      "  of: 233\n",
      "  a: 208\n",
      "  and: 199\n",
      "  i: 188\n",
      "treaty.txt\n",
      "  the: 688\n",
      "  i: 348\n",
      "  of: 319\n",
      "  and: 318\n",
      "  to: 316\n",
      "bachelor.txt\n",
      "  the: 401\n",
      "  i: 236\n",
      "  and: 234\n",
      "  to: 233\n",
      "  a: 211\n",
      "patient.txt\n",
      "  the: 346\n",
      "  i: 187\n",
      "  to: 184\n",
      "  and: 172\n",
      "  of: 171\n",
      "bohemia.txt\n",
      "  the: 443\n",
      "  i: 261\n",
      "  and: 254\n",
      "  to: 245\n",
      "  of: 237\n",
      "problem.txt\n",
      "  the: 427\n",
      "  i: 231\n",
      "  to: 209\n",
      "  of: 191\n",
      "  and: 187\n",
      "crooked.txt\n",
      "  the: 438\n",
      "  and: 204\n",
      "  of: 199\n",
      "  i: 184\n",
      "  a: 175\n",
      "engineer.txt\n",
      "  the: 431\n",
      "  i: 313\n",
      "  and: 250\n",
      "  a: 233\n",
      "  to: 215\n",
      "interpreter.txt\n",
      "  the: 353\n",
      "  and: 188\n",
      "  a: 186\n",
      "  to: 178\n",
      "  i: 153\n",
      "gloria_scott.txt\n",
      "  the: 430\n",
      "  and: 273\n",
      "  of: 220\n",
      "  a: 203\n",
      "  i: 188\n",
      "clerk.txt\n",
      "  the: 312\n",
      "  i: 210\n",
      "  a: 186\n",
      "  and: 180\n",
      "  of: 174\n",
      "copper.txt\n",
      "  the: 485\n",
      "  i: 330\n",
      "  and: 275\n",
      "  to: 256\n",
      "  a: 238\n",
      "ritual.txt\n",
      "  the: 482\n",
      "  of: 255\n",
      "  and: 216\n",
      "  i: 200\n",
      "  to: 200\n",
      "blaze.txt\n",
      "  the: 641\n",
      "  of: 242\n",
      "  and: 242\n",
      "  a: 242\n",
      "  to: 238\n",
      "league.txt\n",
      "  the: 460\n",
      "  and: 271\n",
      "  i: 264\n",
      "  a: 239\n",
      "  of: 224\n",
      "boscombe.txt\n",
      "  the: 529\n",
      "  and: 279\n",
      "  i: 273\n",
      "  to: 251\n",
      "  of: 244\n"
     ]
    }
   ],
   "source": [
    "for filename in corpus:\n",
    "    print(filename)\n",
    "    for word, score in corpus[filename][:5]:\n",
    "        print(f'  {word}: {score}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d790c96f",
   "metadata": {},
   "source": [
    "### Problem: Stop of Function Word\n",
    "- words that have little meaning on their own ([wiki](https://en.wikipedia.org/wiki/Stop_word))\n",
    "- Examples: am, by, do, is, which, ....\n",
    "- Student exercise: Remove function words and see result (HINT: nltk has a list of stopwords)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd027d81",
   "metadata": {},
   "source": [
    "## Approach 2: TF-IDF\n",
    "- TF-IDF is a numerical statistic that is intended to reflect how important a word is to a document in a collection or corpus. ([wiki](https://en.wikipedia.org/wiki/Tf–idf))\n",
    "\n",
    "### Inverse Document Frequency\n",
    "- Measure of how common or rare a word is across documents\n",
    "\n",
    "$\\text{idf}(t, D) = \\log{\\frac{N}{|d\\in D : t\\in d|}} = \\log{\\frac{\\text{Total Documents}}{\\text{Number of Documents Containing \"term\"}}}$\n",
    "- $D$: All docments in the corpus\n",
    "- $N$: total number of documents in the corpus $N = |D|$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0657212b",
   "metadata": {},
   "source": [
    "### TF-IDF\n",
    "- Ranking of what words are important in a document by multiplying Term Frequencey (TF) by Inverse Document Frequency (IDF)\n",
    "\n",
    "$\\text{tf-idf}(t, d) = \\text{tf}(t, d)\\cdot \\text{idf}(t, D)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b668a3d",
   "metadata": {},
   "source": [
    "### Example\n",
    "\n",
    "- Document 1: *This is the sample of the day*\n",
    "- Document 2: *This is another sample of the day*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ad4d6ece",
   "metadata": {},
   "outputs": [],
   "source": [
    "doc1 = \"This is the sample of the day\".split()\n",
    "doc2 = \"This is another sample of the day\".split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e86e8ce0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['This', 'is', 'the', 'sample', 'of', 'the', 'day'],\n",
       " ['This', 'is', 'another', 'sample', 'of', 'the', 'day']]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "corpus = [doc1, doc2]\n",
    "corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "8495dca7",
   "metadata": {},
   "outputs": [],
   "source": [
    "tf1 = {word: doc1.count(word) for word in set(doc1)}\n",
    "tf2 = {word: doc2.count(word) for word in set(doc2)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "d21fbfd4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'This': 1, 'of': 1, 'sample': 1, 'is': 1, 'day': 1, 'the': 2}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tf1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "328b2f6c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'This': 1, 'of': 1, 'sample': 1, 'is': 1, 'another': 1, 'day': 1, 'the': 1}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tf2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "75b6f5be",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.0, 2.0)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "term = 'another'\n",
    "ids = 2/sum(term in doc for doc in corpus)\n",
    "\n",
    "tf1.get(term, 0)*ids, tf2.get(term, 0)*ids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5838fde",
   "metadata": {},
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}