nlp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NATURAL LANGUAGE PROCESSING\n",
    "\n",
    "This notebook covers chapters 22 and 23 from the book *Artificial Intelligence: A Modern Approach*, 3rd Edition. The implementations of the algorithms can be found in [nlp.py](https://github.com/aimacode/aima-python/blob/master/nlp.py).\n",
    "\n",
    "Run the below cell to import the code from the module and get started!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import nlp\n",
    "from nlp import Page, HITS, Lexicon, Rules, Grammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## CONTENTS\n",
    "\n",
    "* Overview\n",
    "* Languages\n",
    "* HITS\n",
    "* Question Answering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## OVERVIEW\n",
    "\n",
    "`TODO...`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LANGUAGES\n",
    "\n",
    "Languages can be represented by a set of grammar rules over a lexicon of words. Different languages can be represented by different types of grammar, but in Natural Language Processing we are mainly interested in context-free grammars.\n",
    "\n",
    "### Context-Free Grammars\n",
    "\n",
    "A lot of natural and programming languages can be represented by a **Context-Free Grammar (CFG)**. A CFG is a grammar that has a single non-terminal symbol on the left-hand side. That means a non-terminal can be replaced by the right-hand side of the rule regardless of context. An example of a CFG:\n",
    "\n",
    "```\n",
    "S -> aSb | e\n",
    "```\n",
    "\n",
    "That means `S` can be replaced by either `aSb` or `e` (with `e` we denote the empty string). The lexicon of the language is comprised of the terminals `a` and `b`, while with `S` we denote the non-terminal symbol. In general, non-terminals are capitalized while terminals are not, and we usually name the starting non-terminal `S`. The language generated by the above grammar is the language a<sup>n</sup>b<sup>n</sup> for n greater or equal than 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Probabilistic Context-Free Grammar\n",
    "\n",
    "While a simple CFG can be very useful, we might want to know the chance of each rule occuring. Above, we do not know if `S` is more likely to be replaced by `aSb` or `e`. **Probabilistic Context-Free Grammars (PCFG)** are built to fill exactly that need. Each rule has a probability, given in brackets, and the probabilities of a rule sum up to 1:\n",
    "\n",
    "```\n",
    "S -> aSb [0.7] | e [0.3]\n",
    "```\n",
    "\n",
    "Now we know it is more likely for `S` to be replaced by `aSb` than by `e`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lexicon\n",
    "\n",
    "The lexicon of a language is defined as a list of allowable words. These words are grouped into the usual classes: `verbs`, `nouns`, `adjectives`, `adverbs`, `pronouns`, `names`, `articles`, `prepositions` and `conjuctions`. For the first five classes it is impossible to list all words, since words are continuously being added in the classes. Recently \"google\" was added to the list of verbs, and words like that will continue to pop up and get added to the lists. For that reason, these first five categories are called **open classes**. The rest of the categories have much fewer words and much less development. While words like \"thou\" were commonly used in the past but have declined almost completely in usage, most changes take many decades or centuries to manifest, so we can safely assume the categories will remain static for the foreseeable future. Thus, these categories are called **closed classes**.\n",
    "\n",
    "An example lexicon for a PCFG (note that other classes can also be used according to the language, like `digits`, or `RelPro` for relative pronoun):\n",
    "\n",
    "```\n",
    "Verb -> is [0.3] | say [0.1] | are [0.1] | ...\n",
    "Noun -> robot [0.1] | sheep [0.05] | fence [0.05] | ...\n",
    "Adjective -> good [0.1] | new [0.1] | sad [0.05] | ...\n",
    "Adverb -> here [0.1] | lightly [0.05] | now [0.05] | ...\n",
    "Pronoun -> me [0.1] | you [0.1] | he [0.05] | ...\n",
    "RelPro -> that [0.4] | who [0.2] | which [0.2] | ...\n",
    "Name -> john [0.05] | mary [0.05] | peter [0.01] | ...\n",
    "Article -> the [0.35] | a [0.25] | an [0.025] | ...\n",
    "Preposition -> to [0.25] | in [0.2] | at [0.1] | ...\n",
    "Conjuction -> and [0.5] | or [0.2] | but [0.2] | ...\n",
    "Digit -> 1 [0.3] | 2 [0.2] | 0 [0.2] | ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grammar\n",
    "\n",
    "With grammars we combine words from the lexicon into valid phrases. A grammar is comprised of **grammar rules**. Each rule transforms the left-hand side of the rule into the right-hand side. For example, `A -> B` means that `A` transforms into `B`. Let's build a grammar for the language we started building with the lexicon. We will use a PCFG.\n",
    "\n",
    "```\n",
    "S -> NP VP [0.9] | S Conjuction S [0.1]\n",
    "\n",
    "NP -> Pronoun [0.3] | Name [0.1] | Noun [0.1] | Article Noun [0.25] |\n",
    "      Article Adjs Noun [0.05] | Digit [0.05] | NP PP [0.1] |\n",
    "      NP RelClause [0.05]\n",
    "\n",
    "VP -> Verb [0.4] | VP NP [0.35] | VP Adjective [0.05] | VP PP [0.1]\n",
    "      VP Adverb [0.1]\n",
    "\n",
    "Adjs -> Adjective [0.8] | Adjective Adjs [0.2]\n",
    "\n",
    "PP -> Preposition NP [1.0]\n",
    "\n",
    "RelClause -> RelPro VP [1.0]\n",
    "```\n",
    "\n",
    "Some valid phrases the grammar produces: \"`mary is sad`\", \"`you are a robot`\" and \"`she likes mary and a good fence`\".\n",
    "\n",
    "What if we wanted to check if the phrase \"`mary is sad`\" is actually a valid sentence? We can use a **parse tree** to constructively prove that a string of words is a valid phrase in the given language and even calculate the probability of the generation of the sentence.\n",
    "\n",
    "![parse_tree](images/parse_tree.png)\n",
    "\n",
    "The probability of the whole tree can be calculated by multiplying the probabilities of each individual rule transormation: `0.9 * 0.1 * 0.05 * 0.05 * 0.4 * 0.05 * 0.3 = 0.00000135`.\n",
    "\n",
    "To conserve space, we can also write the tree in linear form:\n",
    "\n",
    "[S [NP [Name **mary**]] [VP [VP [Verb **is**]] [Adjective **sad**]]]\n",
    "\n",
    "Unfortunately, the current grammar **overgenerates**, that is, it creates sentences that are not grammatically correct (according to the English language), like \"`the fence are john which say`\". It also **undergenerates**, which means there are valid sentences it does not generate, like \"`he believes mary is sad`\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation\n",
    "\n",
    "In the module we have implemented a `Lexicon` and a `Rules` function, which we can combine to create a `Grammar` object.\n",
    "\n",
    "Execute the cells below to view the implemenations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource Lexicon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource Rules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource Grammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's build a lexicon and a grammar for the above language:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lexicon {'Article': ['the', 'a', 'an'], 'Adverb': ['here', 'lightly', 'now'], 'Digit': ['1', '2', '0'], 'Pronoun': ['me', 'you', 'he'], 'Name': ['john', 'mary', 'peter'], 'Adjective': ['good', 'new', 'sad'], 'Conjuction': ['and', 'or', 'but'], 'Preposition': ['to', 'in', 'at'], 'RelPro': ['that', 'who', 'which'], 'Verb': ['is', 'say', 'are'], 'Noun': ['robot', 'sheep', 'fence']}\n",
      "\n",
      "Rules: {'Adjs': [['Adjective'], ['Adjective', 'Adjs']], 'PP': [['Preposition', 'NP']], 'RelClause': [['RelPro', 'VP']], 'VP': [['Verb'], ['VP', 'NP'], ['VP', 'Adjective'], ['VP', 'PP'], ['VP', 'Adverb']], 'NP': [['Pronoun'], ['Name'], ['Noun'], ['Article', 'Noun'], ['Article', 'Adjs', 'Noun'], ['Digit'], ['NP', 'PP'], ['NP', 'RelClause']], 'S': [['NP', 'VP'], ['S', 'Conjuction', 'S']]}\n"
     ]
    }
   ],
   "source": [
    "lexicon = Lexicon(\n",
    "    Verb=\"is | say | are\",\n",
    "    Noun=\"robot | sheep | fence\",\n",
    "    Adjective=\"good | new | sad\",\n",
    "    Adverb=\"here | lightly | now\",\n",
    "    Pronoun=\"me | you | he\",\n",
    "    RelPro=\"that | who | which\",\n",
    "    Name=\"john | mary | peter\",\n",
    "    Article=\"the | a | an\",\n",
    "    Preposition=\"to | in | at\",\n",
    "    Conjuction=\"and | or | but\",\n",
    "    Digit=\"1 | 2 | 0\"\n",
    ")\n",
    "\n",
    "print(\"Lexicon\", lexicon)\n",
    "\n",
    "rules = Rules(\n",
    "    S=\"NP VP | S Conjuction S\",\n",
    "    NP=\"Pronoun | Name | Noun | Article Noun | Article Adjs Noun | Digit | NP PP | NP RelClause\",\n",
    "    VP=\"Verb | VP NP | VP Adjective | VP PP | VP Adverb\",\n",
    "    Adjs=\"Adjective | Adjective Adjs\",\n",
    "    PP=\"Preposition NP\",\n",
    "    RelClause=\"RelPro VP\"\n",
    ")\n",
    "\n",
    "print(\"\\nRules:\", rules)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Both the functions return a dictionary with keys the left-hand side of the rules. For the lexicon, the values are the terminals for each left-hand side non-terminal, while for the rules the values are the right-hand sides as lists.\n",
    "\n",
    "We can now use the variables `lexicon` and `rules` to build a grammar. After we've done so, we can find the transformations of a non-terminal (the `Noun`, `Verb` and the other basic classes do **not** count as proper non-terminals in the implementation). We can also check if a word is in a particular class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How can we rewrite 'VP'? [['Verb'], ['VP', 'NP'], ['VP', 'Adjective'], ['VP', 'PP'], ['VP', 'Adverb']]\n",
      "Is 'the' an article? True\n",
      "Is 'here' a noun? False\n"
     ]
    }
   ],
   "source": [
    "grammar = Grammar(\"A Simple Grammar\", rules, lexicon)\n",
    "\n",
    "print(\"How can we rewrite 'VP'?\", grammar.rewrites_for('VP'))\n",
    "print(\"Is 'the' an article?\", grammar.isa('the', 'Article'))\n",
    "print(\"Is 'here' a noun?\", grammar.isa('here', 'Noun'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can generate random phrases using our grammar. Most of them will be complete gibberish, falling under the overgenerated phrases of the grammar. That goes to show that in the grammar the valid phrases are much fewer than the overgenerated ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a robot is to a robot sad but robot say you 0 in me in a robot at the sheep at 1 good an fence in sheep in me that are in john new lightly lightly here a new good new robot lightly new in sheep lightly'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from nlp import generate_random\n",
    "\n",
    "generate_random(grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HITS\n",
    "\n",
    "### Overview\n",
    "\n",
    "**Hyperlink-Induced Topic Search** (or HITS for short) is an algorithm for information retrieval and page ranking. You can read more on information retrieval in the [text notebook](https://github.com/aimacode/aima-python/blob/master/text.ipynb). Essentially, given a collection of documents and a user's query, such systems return to the user the documents most relevant to what the user needs. The HITS algorithm differs from a lot of other similar ranking algorithms (like Google's *Pagerank*) as the page ratings in this algorithm are dependent on the given query. This means that for each new query the result pages must be computed anew. This cost might be prohibitive for many modern search engines, so a lot steer away from this approach.\n",
    "\n",
    "HITS first finds a list of relevant pages to the query and then adds pages that link to or are linked from these pages. Once the set is built, we define two values for each page. **Authority** on the query, the degree of pages from the relevant set linking to it and **hub** of the query, the degree that it points to authoritative pages in the set. Since we do not want to simply count the number of links from a page to other pages, but we also want to take into account the quality of the linked pages, we update the hub and authority values of a page in the following manner, until convergence:\n",
    "\n",
    "* Hub score = The sum of the authority scores of the pages it links to.\n",
    "\n",
    "* Authority score = The sum of hub scores of the pages it is linked from.\n",
    "\n",
    "So the higher quality the pages a page is linked to and from, the higher its scores.\n",
    "\n",
    "We then normalize the scores by dividing each score by the sum of the squares of the respective scores of all pages. When the values converge, we return the top-valued pages. Note that because we normalize the values, the algorithm is guaranteed to converge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Implementation\n",
    "\n",
    "The source code for the algorithm is given below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource HITS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we compile the collection of pages as mentioned above. Then, we initialize the authority and hub scores for each page and finally we update and normalize the values until convergence.\n",
    "\n",
    "A quick overview of the helper functions functions we use:\n",
    "\n",
    "* `relevant_pages`: Returns relevant pages from `pagesIndex` given a query.\n",
    "\n",
    "* `expand_pages`: Adds to the collection pages linked to and from the given `pages`.\n",
    "\n",
    "* `normalize`: Normalizes authority and hub scores.\n",
    "\n",
    "* `ConvergenceDetector`: A class that checks for convergence, by keeping a history of the pages' scores and checking if they change or not.\n",
    "\n",
    "* `Page`: The template for pages. Stores the address, authority/hub scores and in-links/out-links."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Example\n",
    "\n",
    "Before we begin we need to define a list of sample pages to work on. The pages are `pA`, `pB` and so on and their text is given by `testHTML` and `testHTML2`. The `Page` class takes as arguments the in-links and out-links as lists. For page \"A\", the in-links are \"B\", \"C\" and \"E\" while the sole out-link is \"D\".\n",
    "\n",
    "We also need to set the `nlp` global variables `pageDict`, `pagesIndex` and `pagesContent`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "testHTML = \"\"\"Like most other male mammals, a man inherits an\n",
    "            X from his mom and a Y from his dad.\"\"\"\n",
    "testHTML2 = \"a mom and a dad\"\n",
    "\n",
    "pA = Page(\"A\", [\"B\", \"C\", \"E\"], [\"D\"])\n",
    "pB = Page(\"B\", [\"E\"], [\"A\", \"C\", \"D\"])\n",
    "pC = Page(\"C\", [\"B\", \"E\"], [\"A\", \"D\"])\n",
    "pD = Page(\"D\", [\"A\", \"B\", \"C\", \"E\"], [])\n",
    "pE = Page(\"E\", [], [\"A\", \"B\", \"C\", \"D\", \"F\"])\n",
    "pF = Page(\"F\", [\"E\"], [])\n",
    "\n",
    "nlp.pageDict = {pA.address: pA, pB.address: pB, pC.address: pC,\n",
    "                pD.address: pD, pE.address: pE, pF.address: pF}\n",
    "\n",
    "nlp.pagesIndex = nlp.pageDict\n",
    "\n",
    "nlp.pagesContent ={pA.address: testHTML, pB.address: testHTML2,\n",
    "                   pC.address: testHTML, pD.address: testHTML2,\n",
    "                   pE.address: testHTML, pF.address: testHTML2}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now run the HITS algorithm. Our query will be 'mammals' (note that while the content of the HTML doesn't matter, it should include the query words or else no page will be picked at the first step)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "HITS('mammals')\n",
    "page_list = [\"A\", \"B\", \"C\", \"D\", \"E\", \"F\"]\n",
    "auth_list = [pA.authority, pB.authority, pC.authority, pD.authority, pE.authority, pF.authority]\n",
    "hub_list = [pA.hub, pB.hub, pC.hub, pD.hub, pE.hub, pF.hub]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how the pages were scored:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A: total=0.7696163397038682, auth=0.5583254178509696, hub=0.2112909218528986\n",
      "B: total=0.7795962360479534, auth=0.23657856688600404, hub=0.5430176691619494\n",
      "C: total=0.8204496913590655, auth=0.4211098490570872, hub=0.3993398423019784\n",
      "D: total=0.6316647735856309, auth=0.6316647735856309, hub=0.0\n",
      "E: total=0.7078245882072104, auth=0.0, hub=0.7078245882072104\n",
      "F: total=0.23657856688600404, auth=0.23657856688600404, hub=0.0\n"
     ]
    }
   ],
   "source": [
    "for i in range(6):\n",
    "    p = page_list[i]\n",
    "    a = auth_list[i]\n",
    "    h = hub_list[i]\n",
    "    \n",
    "    print(\"{}: total={}, auth={}, hub={}\".format(p, a + h, a, h))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "The top score is 0.82 by \"C\". This is the most relevant page according to the algorithm. You can see that the pages it links to, \"A\" and \"D\", have the two highest authority scores (therefore \"C\" has a high hub score) and the pages it is linked from, \"B\" and \"E\", have the highest hub scores (so \"C\" has a high authority score). By combining these two facts, we get that \"C\" is the most relevant page. It is worth noting that it does not matter if the given page contains the query words, just that it links and is linked from high-quality pages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## QUESTION ANSWERING\n",
    "\n",
    "**Question Answering** is a type of Information Retrieval system, where we have a question instead of a query and instead of relevant documents we want the computer to return a short sentence, phrase or word that answers our question. To better understand the concept of question answering systems, you can first read the \"Text Models\" and \"Information Retrieval\" section from the [text notebook](https://github.com/aimacode/aima-python/blob/master/text.ipynb).\n",
    "\n",
    "A typical example of such a system is `AskMSR` (Banko *et al.*, 2002), a system for question answering that performed admirably against more sophisticated algorithms. The basic idea behind it is that a lot of questions have already been answered in the web numerous times. The system doesn't know a lot about verbs, or concepts or even what a noun is. It knows about 15 different types of questions and how they can be written as queries. It can rewrite [Who was George Washington's second in command?] as the query [\\* was George Washington's second in command] or [George Washington's second in command was \\*].\n",
    "\n",
    "After rewriting the questions, it issues these queries and retrieves the short text around the query terms. It then breaks the result into 1, 2 or 3-grams. Filters are also applied to increase the chances of a correct answer. If the query starts with \"who\", we filter for names, if it starts with \"how many\" we filter for numbers and so on. We can also filter out the words appearing in the query. For the above query, the answer \"George Washington\" is wrong, even though it is quite possible the 2-gram would appear a lot around the query terms.\n",
    "\n",
    "Finally, the different results are weighted by the generality of the queries. The result from the general boolean query [George Washington OR second in command] weighs less that the more specific query [George Washington's second in command was \\*]. As an answer we return the most highly-ranked n-gram."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}