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\n",
    "from nlp import Lexicon, Rules, Grammar, ProbLexicon, ProbRules, ProbGrammar\n",
    "from nlp import CYK_parse"
   ]
  },
  {
   "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 | ε\n",
    "```\n",
    "\n",
    "That means `S` can be replaced by either `aSb` or `ε` (with `ε` 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 `ε`. **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] | ε [0.3]\n",
    "```\n",
    "\n",
    "Now we know it is more likely for `S` to be replaced by `aSb` than by `e`.\n",
    "\n",
    "An issue with *PCFGs* is how we will assign the various probabilities to the rules. We could use our knowledge as humans to assign the probabilities, but that is a laborious and prone to error task. Instead, we can *learn* the probabilities from data. Data is categorized as labeled (with correctly parsed sentences, usually called a **treebank**) or unlabeled (given only lexical and syntactic category names).\n",
    "\n",
    "With labeled data, we can simply count the occurences. For the above grammar, if we have 100 `S` rules and 30 of them are of the form `S -> ε`, we assign a probability of 0.3 to the transformation.\n",
    "\n",
    "With unlabeled data we have to learn both the grammar rules and the probability of each rule. We can go with many approaches, one of them the **inside-outside** algorithm. It uses a dynamic programming approach, that first finds the probability of a substring being generated by each rule, and then estimates the probability of each rule."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chomsky Normal Form\n",
    "\n",
    "A grammar is in Chomsky Normal Form (or **CNF**, not to be confused with *Conjunctive Normal Form*) if its rules are one of the three:\n",
    "\n",
    "* `X -> Y Z`\n",
    "* `A -> a`\n",
    "* `S -> ε`\n",
    "\n",
    "Where *X*, *Y*, *Z*, *A* are non-terminals, *a* is a terminal, *ε* is the empty string and *S* is the start symbol (the start symbol should not be appearing on the right hand side of rules). Note that there can be multiple rules for each left hand side non-terminal, as long they follow the above. For example, a rule for *X* might be: `X -> Y Z | A B | a | b`.\n",
    "\n",
    "Of course, we can also have a *CNF* with probabilities.\n",
    "\n",
    "This type of grammar may seem restrictive, but it can be proven that any context-free grammar can be converted to CNF."
   ]
  },
  {
   "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 implementation both for probabilistic and non-probabilistic grammars. Both these implementation follow the same format. There are functions for the lexicon and the rules which can be combined to create a grammar object.\n",
    "\n",
    "#### Non-Probabilistic\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 {'Verb': ['is', 'say', 'are'], 'RelPro': ['that', 'who', 'which'], 'Conjuction': ['and', 'or', 'but'], 'Digit': ['1', '2', '0'], 'Noun': ['robot', 'sheep', 'fence'], 'Pronoun': ['me', 'you', 'he'], 'Preposition': ['to', 'in', 'at'], 'Name': ['john', 'mary', 'peter'], 'Article': ['the', 'a', 'an'], 'Adjective': ['good', 'new', 'sad'], 'Adverb': ['here', 'lightly', 'now']}\n",
      "\n",
      "Rules: {'RelClause': [['RelPro', 'VP']], 'S': [['NP', 'VP'], ['S', 'Conjuction', 'S']], 'PP': [['Preposition', 'NP']], 'VP': [['Verb'], ['VP', 'NP'], ['VP', 'Adjective'], ['VP', 'PP'], ['VP', 'Adverb']], 'NP': [['Pronoun'], ['Name'], ['Noun'], ['Article', 'Noun'], ['Article', 'Adjs', 'Noun'], ['Digit'], ['NP', 'PP'], ['NP', 'RelClause']], 'Adjs': [['Adjective'], ['Adjective', 'Adjs']]}\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": [
    "If the grammar is in Chomsky Normal Form, we can call the class function `cnf_rules` to get all the rules in the form of `(X, Y, Z)` for each `X -> Y Z` rule. Since the above grammar is not in *CNF* though, we have to create a new one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "E_Chomsky = Grammar('E_Prob_Chomsky', # A Grammar in Chomsky Normal Form\n",
    "        Rules(\n",
    "           S='NP VP',\n",
    "           NP='Article Noun | Adjective Noun',\n",
    "           VP='Verb NP | Verb Adjective',\n",
    "        ),\n",
    "        Lexicon(\n",
    "           Article='the | a | an',\n",
    "           Noun='robot | sheep | fence',\n",
    "           Adjective='good | new | sad',\n",
    "           Verb='is | say | are'\n",
    "        ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('NP', 'Article', 'Noun'), ('NP', 'Adjective', 'Noun'), ('VP', 'Verb', 'NP'), ('VP', 'Verb', 'Adjective'), ('S', 'NP', 'VP')]\n"
     ]
    }
   ],
   "source": [
    "print(E_Chomsky.cnf_rules())"
   ]
  },
  {
   "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": [
       "'the fence are or 1 say in john that is here lightly to peter lightly sad good at you good here me good at john in an fence to fence at robot lightly and a robot who is here sad sheep in fence in fence at he sad here lightly to 0 say and fence is good in a sad sheep in a fence but he say here'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar.generate_random('S')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Probabilistic\n",
    "\n",
    "The probabilistic grammars follow the same approach. They take as input a string, are assembled from a grammar and a lexicon and can generate random sentences (giving the probability of the sentence). The main difference is that in the lexicon we have tuples (terminal, probability) instead of strings and for the rules we have a list of tuples (list of non-terminals, probability) instead of list of lists of non-terminals.\n",
    "\n",
    "Execute the cells to read the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource ProbLexicon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource ProbRules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource ProbGrammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's build a lexicon and rules for the probabilistic grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lexicon {'Verb': [('is', 0.5), ('say', 0.3), ('are', 0.2)], 'Adjective': [('good', 0.5), ('new', 0.2), ('sad', 0.3)], 'Preposition': [('to', 0.4), ('in', 0.3), ('at', 0.3)], 'Pronoun': [('me', 0.3), ('you', 0.4), ('he', 0.3)], 'Conjuction': [('and', 0.5), ('or', 0.2), ('but', 0.3)], 'Adverb': [('here', 0.6), ('lightly', 0.1), ('now', 0.3)], 'Article': [('the', 0.5), ('a', 0.25), ('an', 0.25)], 'Digit': [('0', 0.35), ('1', 0.35), ('2', 0.3)], 'RelPro': [('that', 0.5), ('who', 0.3), ('which', 0.2)], 'Noun': [('robot', 0.4), ('sheep', 0.4), ('fence', 0.2)], 'Name': [('john', 0.4), ('mary', 0.4), ('peter', 0.2)]}\n",
      "\n",
      "Rules: {'RelClause': [(['RelPro', 'VP'], 1.0)], 'Adjs': [(['Adjective'], 0.5), (['Adjective', 'Adjs'], 0.5)], 'PP': [(['Preposition', 'NP'], 1.0)], 'NP': [(['Pronoun'], 0.2), (['Name'], 0.05), (['Noun'], 0.2), (['Article', 'Noun'], 0.15), (['Article', 'Adjs', 'Noun'], 0.1), (['Digit'], 0.05), (['NP', 'PP'], 0.15), (['NP', 'RelClause'], 0.1)], 'S': [(['NP', 'VP'], 0.6), (['S', 'Conjuction', 'S'], 0.4)], 'VP': [(['Verb'], 0.3), (['VP', 'NP'], 0.2), (['VP', 'Adjective'], 0.25), (['VP', 'PP'], 0.15), (['VP', 'Adverb'], 0.1)]}\n"
     ]
    }
   ],
   "source": [
    "lexicon = ProbLexicon(\n",
    "    Verb=\"is [0.5] | say [0.3] | are [0.2]\",\n",
    "    Noun=\"robot [0.4] | sheep [0.4] | fence [0.2]\",\n",
    "    Adjective=\"good [0.5] | new [0.2] | sad [0.3]\",\n",
    "    Adverb=\"here [0.6] | lightly [0.1] | now [0.3]\",\n",
    "    Pronoun=\"me [0.3] | you [0.4] | he [0.3]\",\n",
    "    RelPro=\"that [0.5] | who [0.3] | which [0.2]\",\n",
    "    Name=\"john [0.4] | mary [0.4] | peter [0.2]\",\n",
    "    Article=\"the [0.5] | a [0.25] | an [0.25]\",\n",
    "    Preposition=\"to [0.4] | in [0.3] | at [0.3]\",\n",
    "    Conjuction=\"and [0.5] | or [0.2] | but [0.3]\",\n",
    "    Digit=\"0 [0.35] | 1 [0.35] | 2 [0.3]\"\n",
    ")\n",
    "\n",
    "print(\"Lexicon\", lexicon)\n",
    "\n",
    "rules = ProbRules(\n",
    "    S=\"NP VP [0.6] | S Conjuction S [0.4]\",\n",
    "    NP=\"Pronoun [0.2] | Name [0.05] | Noun [0.2] | Article Noun [0.15] \\\n",
    "        | Article Adjs Noun [0.1] | Digit [0.05] | NP PP [0.15] | NP RelClause [0.1]\",\n",
    "    VP=\"Verb [0.3] | VP NP [0.2] | VP Adjective [0.25] | VP PP [0.15] | VP Adverb [0.1]\",\n",
    "    Adjs=\"Adjective [0.5] | Adjective Adjs [0.5]\",\n",
    "    PP=\"Preposition NP [1]\",\n",
    "    RelClause=\"RelPro VP [1]\"\n",
    ")\n",
    "\n",
    "print(\"\\nRules:\", rules)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use the above to assemble our probabilistic grammar and run some simple queries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How can we rewrite 'VP'? [(['Verb'], 0.3), (['VP', 'NP'], 0.2), (['VP', 'Adjective'], 0.25), (['VP', 'PP'], 0.15), (['VP', 'Adverb'], 0.1)]\n",
      "Is 'the' an article? True\n",
      "Is 'here' a noun? False\n"
     ]
    }
   ],
   "source": [
    "grammar = ProbGrammar(\"A Simple Probabilistic 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": [
    "If we have a grammar in *CNF*, we can get a list of all the rules. Let's create a grammar in the form and print the *CNF* rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "E_Prob_Chomsky = ProbGrammar('E_Prob_Chomsky', # A Probabilistic Grammar in CNF\n",
    "                             ProbRules(\n",
    "                                S='NP VP [1]',\n",
    "                                NP='Article Noun [0.6] | Adjective Noun [0.4]',\n",
    "                                VP='Verb NP [0.5] | Verb Adjective [0.5]',\n",
    "                             ),\n",
    "                             ProbLexicon(\n",
    "                                Article='the [0.5] | a [0.25] | an [0.25]',\n",
    "                                Noun='robot [0.4] | sheep [0.4] | fence [0.2]',\n",
    "                                Adjective='good [0.5] | new [0.2] | sad [0.3]',\n",
    "                                Verb='is [0.5] | say [0.3] | are [0.2]'\n",
    "                             ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('NP', 'Article', 'Noun', 0.6), ('NP', 'Adjective', 'Noun', 0.4), ('VP', 'Verb', 'NP', 0.5), ('VP', 'Verb', 'Adjective', 0.5), ('S', 'NP', 'VP', 1.0)]\n"
     ]
    }
   ],
   "source": [
    "print(E_Prob_Chomsky.cnf_rules())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lastly, we can generate random sentences from this grammar. The function `prob_generation` returns a tuple (sentence, probability)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a sheep say at the sad sad robot the good new sheep but john at fence are to me who is to robot the good new fence to robot who is mary in robot to 1 to an sad sad sad robot in fence lightly now at 1 at a new robot here good at john an robot in a fence in john the sheep here 2 to sheep good and you is but sheep is sad a good robot or the fence is robot good lightly at a good robot at 2 now good new or 1 say but he say or peter are in you who is lightly and fence say to john to an robot and sheep say and me is good or a robot is and sheep that say good he new 2 which are sad to an good fence that say 1 good good new lightly are good at he sad here but an sheep who say say sad now lightly sad an sad sad sheep or mary are but a fence at he in 1 say and 2 are\n",
      "5.453065905143236e-226\n"
     ]
    }
   ],
   "source": [
    "sentence, prob = grammar.generate_random('S')\n",
    "print(sentence)\n",
    "print(prob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As with the non-probabilistic grammars, this one mostly overgenerates. You can also see that the probability is very, very low, which means there are a ton of generateable sentences (in this case infinite, since we have recursion; notice how `VP` can produce another `VP`, for example)."
   ]
  },
  {
   "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CYK PARSE\n",
    "\n",
    "### Overview\n",
    "\n",
    "Syntactic analysis (or **parsing**) of a sentence is the process of uncovering the phrase structure of the sentence according to the rules of a grammar. There are two main approaches to parsing. *Top-down*, start with the starting symbol and build a parse tree with the given words as its leaves, and *bottom-up*, where we start from the given words and build a tree that has the starting symbol as its root. Both approaches involve \"guessing\" ahead, so it is very possible it will take long to parse a sentence (wrong guess mean a lot of backtracking). Thankfully, a lot of effort is spent in analyzing already analyzed substrings, so we can follow a dynamic programming approach to store and reuse these parses instead of recomputing them. The *CYK Parsing Algorithm* (named after its inventors, Cocke, Younger and Kasami) utilizes this technique to parse sentences of a grammar in *Chomsky Normal Form*.\n",
    "\n",
    "The CYK algorithm returns an *M x N x N* array (named *P*), where *N* is the number of words in the sentence and *M* the number of non-terminal symbols in the grammar. Each element in this array shows the probability of a substring being transformed from a particular non-terminal. To find the most probable parse of the sentence, a search in the resulting array is required. Search heuristic algorithms work well in this space, and we can derive the heuristics from the properties of the grammar.\n",
    "\n",
    "The algorithm in short works like this: There is an external loop that determines the length of the substring. Then the algorithm loops through the words in the sentence. For each word, it again loops through all the words to its right up to the first-loop length. The substring it will work on in this iteration is the words from the second-loop word with first-loop length. Finally, it loops through all the rules in the grammar and updates the substring's probability for each right-hand side non-terminal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation\n",
    "\n",
    "The implementation takes as input a list of words and a probabilistic grammar (from the `ProbGrammar` class detailed above) in CNF and returns the table/dictionary *P*. An item's key in *P* is a tuple in the form `(Non-terminal, start of substring, length of substring)`, and the value is a probability. For example, for the sentence \"the monkey is dancing\" and the substring \"the monkey\" an item can be `('NP', 0, 2): 0.5`, which means the first two words (the substring from index 0 and length 2) have a 0.5 probablity of coming from the `NP` terminal.\n",
    "\n",
    "Before we continue, you can take a look at the source code by running the cell below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource CYK_parse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When updating the probability of a substring, we pick the max of its current one and the probability of the substring broken into two parts: one from the second-loop word with third-loop length, and the other from the first part's end to the remainer of the first-loop length."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "\n",
    "Let's build a probabilistic grammar in CNF:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "E_Prob_Chomsky = ProbGrammar('E_Prob_Chomsky', # A Probabilistic Grammar in CNF\n",
    "                             ProbRules(\n",
    "                                S='NP VP [1]',\n",
    "                                NP='Article Noun [0.6] | Adjective Noun [0.4]',\n",
    "                                VP='Verb NP [0.5] | Verb Adjective [0.5]',\n",
    "                             ),\n",
    "                             ProbLexicon(\n",
    "                                Article='the [0.5] | a [0.25] | an [0.25]',\n",
    "                                Noun='robot [0.4] | sheep [0.4] | fence [0.2]',\n",
    "                                Adjective='good [0.5] | new [0.2] | sad [0.3]',\n",
    "                                Verb='is [0.5] | say [0.3] | are [0.2]'\n",
    "                             ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's see the probabilities table for the sentence \"the robot is good\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "defaultdict(<class 'float'>, {('Noun', 3, 1): 0.0, ('VP', 0, 3): 0.0, ('Article', 1, 1): 0.0, ('Adjective', 2, 1): 0.0, ('NP', 2, 2): 0.0, ('Adjective', 1, 3): 0.0, ('S', 0, 4): 0.015, ('NP', 1, 3): 0.0, ('VP', 1, 3): 0.0, ('VP', 3, 1): 0.0, ('Verb', 1, 1): 0.0, ('Adjective', 2, 2): 0.0, ('NP', 1, 1): 0.0, ('NP', 2, 1): 0.0, ('NP', 1, 2): 0.0, ('Adjective', 0, 3): 0.0, ('Noun', 2, 1): 0.0, ('Verb', 2, 1): 0.5, ('S', 2, 2): 0.0, ('Adjective', 0, 2): 0.0, ('Noun', 2, 2): 0.0, ('Adjective', 0, 1): 0.0, ('Adjective', 3, 1): 0.5, ('Article', 0, 3): 0.0, ('Article', 0, 1): 0.5, ('VP', 0, 2): 0.0, ('Article', 0, 2): 0.0, ('Noun', 1, 1): 0.4, ('VP', 1, 2): 0.0, ('VP', 0, 4): 0.0, ('Article', 1, 2): 0.0, ('S', 1, 3): 0.0, ('NP', 0, 1): 0.0, ('Verb', 0, 3): 0.0, ('Noun', 1, 3): 0.0, ('VP', 2, 2): 0.125, ('S', 1, 2): 0.0, ('NP', 0, 2): 0.12, ('Verb', 0, 2): 0.0, ('Noun', 1, 2): 0.0, ('VP', 2, 1): 0.0, ('NP', 0, 3): 0.0, ('Verb', 0, 1): 0.0, ('S', 0, 2): 0.0, ('VP', 1, 1): 0.0, ('NP', 0, 4): 0.0, ('Article', 2, 1): 0.0, ('NP', 3, 1): 0.0, ('Adjective', 1, 1): 0.0, ('S', 0, 3): 0.0, ('Adjective', 1, 2): 0.0, ('Verb', 1, 2): 0.0})\n"
     ]
    }
   ],
   "source": [
    "words = ['the', 'robot', 'is', 'good']\n",
    "grammar = E_Prob_Chomsky\n",
    "\n",
    "P = CYK_parse(words, grammar)\n",
    "print(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A `defaultdict` object is returned (`defaultdict` is basically a dictionary but with a default value/type). Keys are tuples in the form mentioned above and the values are the corresponding probabilities. Most of the items/parses have a probability of 0. Let's filter those out to take a better look at the parses that matter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('NP', 0, 2): 0.12, ('Adjective', 3, 1): 0.5, ('S', 0, 4): 0.015, ('Verb', 2, 1): 0.5, ('Article', 0, 1): 0.5, ('VP', 2, 2): 0.125, ('Noun', 1, 1): 0.4}\n"
     ]
    }
   ],
   "source": [
    "parses = {k: p for k, p in P.items() if p >0}\n",
    "\n",
    "print(parses)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The item `('Article', 0, 1): 0.5` means that the first item came from the `Article` non-terminal with a chance of 0.5. A more complicated item, one with two words, is `('NP', 0, 2): 0.12` which covers the first two words. The probability of the substring \"the robot\" coming from the `NP` non-terminal is 0.12. Let's try and follow the transformations from `NP` to the given words (top-down) to make sure this is indeed the case:\n",
    "\n",
    "1. The probability of `NP` transforming to `Article Noun` is 0.6.\n",
    "\n",
    "2. The probability of `Article` transforming to \"the\" is 0.5 (total probability = 0.6*0.5 = 0.3).\n",
    "\n",
    "3. The probability of `Noun` transforming to \"robot\" is 0.4 (total = 0.3*0.4 = 0.12).\n",
    "\n",
    "Thus, the total probability of the transformation is 0.12.\n",
    "\n",
    "Notice how the probability for the whole string (given by the key `('S', 0, 4)`) is 0.015. This means the most probable parsing of the sentence has a probability of 0.015."
   ]
  }
 ],
 "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
}