{ "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": {}, "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, Chart\n", "\n", "from notebook import psource" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## CONTENTS\n", "\n", "* Overview\n", "* Languages\n", "* HITS\n", "* Question Answering\n", "* CYK Parse\n", "* Chart Parsing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## OVERVIEW\n", "\n", "**Natural Language Processing (NLP)** is a field of AI concerned with understanding, analyzing and using natural languages. This field is considered a difficult yet intriguing field of study, since it is connected to how humans and their languages work.\n", "\n", "Applications of the field include translation, speech recognition, topic segmentation, information extraction and retrieval, and a lot more.\n", "\n", "Below we take a look at some algorithms in the field. Before we get right into it though, we will take a look at a very useful form of language, **context-free** languages. Even though they are a bit restrictive, they have been used a lot in research in natural language processing." ] }, { "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 anbn 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 occurring. 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 `ε`.\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 occurrences. 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 `conjunctions`. 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", "Conjunction -> 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 Conjunction 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 cell below to view the implemenations:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def Lexicon(**rules):\n",
       "    """Create a dictionary mapping symbols to alternative words.\n",
       "    >>> Lexicon(Article = "the | a | an")\n",
       "    {'Article': ['the', 'a', 'an']}\n",
       "    """\n",
       "    for (lhs, rhs) in rules.items():\n",
       "        rules[lhs] = [word.strip() for word in rhs.split('|')]\n",
       "    return rules\n",
       "\n",
       "\n",
       "def Rules(**rules):\n",
       "    """Create a dictionary mapping symbols to alternative sequences.\n",
       "    >>> Rules(A = "B C | D E")\n",
       "    {'A': [['B', 'C'], ['D', 'E']]}\n",
       "    """\n",
       "    for (lhs, rhs) in rules.items():\n",
       "        rules[lhs] = [alt.strip().split() for alt in rhs.split('|')]\n",
       "    return rules\n",
       "\n",
       "\n",
       "class Grammar:\n",
       "\n",
       "    def __init__(self, name, rules, lexicon):\n",
       "        """A grammar has a set of rules and a lexicon."""\n",
       "        self.name = name\n",
       "        self.rules = rules\n",
       "        self.lexicon = lexicon\n",
       "        self.categories = defaultdict(list)\n",
       "        for lhs in lexicon:\n",
       "            for word in lexicon[lhs]:\n",
       "                self.categories[word].append(lhs)\n",
       "\n",
       "    def rewrites_for(self, cat):\n",
       "        """Return a sequence of possible rhs's that cat can be rewritten as."""\n",
       "        return self.rules.get(cat, ())\n",
       "\n",
       "    def isa(self, word, cat):\n",
       "        """Return True iff word is of category cat"""\n",
       "        return cat in self.categories[word]\n",
       "\n",
       "    def cnf_rules(self):\n",
       "        """Returns the tuple (X, Y, Z) for rules in the form:\n",
       "        X -> Y Z"""\n",
       "        cnf = []\n",
       "        for X, rules in self.rules.items():\n",
       "            for (Y, Z) in rules:\n",
       "                cnf.append((X, Y, Z))\n",
       "\n",
       "        return cnf\n",
       "\n",
       "    def generate_random(self, S='S'):\n",
       "        """Replace each token in S by a random entry in grammar (recursively)."""\n",
       "        import random\n",
       "\n",
       "        def rewrite(tokens, into):\n",
       "            for token in tokens:\n",
       "                if token in self.rules:\n",
       "                    rewrite(random.choice(self.rules[token]), into)\n",
       "                elif token in self.lexicon:\n",
       "                    into.append(random.choice(self.lexicon[token]))\n",
       "                else:\n",
       "                    into.append(token)\n",
       "            return into\n",
       "\n",
       "        return ' '.join(rewrite(S.split(), []))\n",
       "\n",
       "    def __repr__(self):\n",
       "        return '<Grammar {}>'.format(self.name)\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(Lexicon, Rules, Grammar)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's build a lexicon and a grammar for the above language:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Lexicon {'Verb': ['is', 'say', 'are'], 'Noun': ['robot', 'sheep', 'fence'], 'Adjective': ['good', 'new', 'sad'], 'Adverb': ['here', 'lightly', 'now'], 'Pronoun': ['me', 'you', 'he'], 'RelPro': ['that', 'who', 'which'], 'Name': ['john', 'mary', 'peter'], 'Article': ['the', 'a', 'an'], 'Preposition': ['to', 'in', 'at'], 'Conjunction': ['and', 'or', 'but'], 'Digit': ['1', '2', '0']}\n", "\n", "Rules: {'S': [['NP', 'VP'], ['S', 'Conjunction', 'S']], 'NP': [['Pronoun'], ['Name'], ['Noun'], ['Article', 'Noun'], ['Article', 'Adjs', 'Noun'], ['Digit'], ['NP', 'PP'], ['NP', 'RelClause']], 'VP': [['Verb'], ['VP', 'NP'], ['VP', 'Adjective'], ['VP', 'PP'], ['VP', 'Adverb']], 'Adjs': [['Adjective'], ['Adjective', 'Adjs']], 'PP': [['Preposition', 'NP']], 'RelClause': [['RelPro', 'VP']]}\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", " Conjunction = \"and | or | but\",\n", " Digit = \"1 | 2 | 0\"\n", ")\n", "\n", "print(\"Lexicon\", lexicon)\n", "\n", "rules = Rules(\n", " S = \"NP VP | S Conjunction S\",\n", " NP = \"Pronoun | Name | Noun | Article Noun \\\n", " | 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": 4, "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": 5, "metadata": {}, "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": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('S', 'NP', 'VP'), ('NP', 'Article', 'Noun'), ('NP', 'Adjective', 'Noun'), ('VP', 'Verb', 'NP'), ('VP', 'Verb', 'Adjective')]\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": [ "'a new robot are in a new new sheep john sheep'" ] }, "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": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def ProbLexicon(**rules):\n",
       "    """Create a dictionary mapping symbols to alternative words,\n",
       "    with probabilities.\n",
       "    >>> ProbLexicon(Article = "the [0.5] | a [0.25] | an [0.25]")\n",
       "    {'Article': [('the', 0.5), ('a', 0.25), ('an', 0.25)]}\n",
       "    """\n",
       "    for (lhs, rhs) in rules.items():\n",
       "        rules[lhs] = []\n",
       "        rhs_separate = [word.strip().split() for word in rhs.split('|')]\n",
       "        for r in rhs_separate:\n",
       "            prob = float(r[-1][1:-1]) # remove brackets, convert to float\n",
       "            word = r[:-1][0]\n",
       "            rhs_rule = (word, prob)\n",
       "            rules[lhs].append(rhs_rule)\n",
       "\n",
       "    return rules\n",
       "\n",
       "\n",
       "def ProbRules(**rules):\n",
       "    """Create a dictionary mapping symbols to alternative sequences,\n",
       "    with probabilities.\n",
       "    >>> ProbRules(A = "B C [0.3] | D E [0.7]")\n",
       "    {'A': [(['B', 'C'], 0.3), (['D', 'E'], 0.7)]}\n",
       "    """\n",
       "    for (lhs, rhs) in rules.items():\n",
       "        rules[lhs] = []\n",
       "        rhs_separate = [alt.strip().split() for alt in rhs.split('|')]\n",
       "        for r in rhs_separate:\n",
       "            prob = float(r[-1][1:-1]) # remove brackets, convert to float\n",
       "            rhs_rule = (r[:-1], prob)\n",
       "            rules[lhs].append(rhs_rule)\n",
       "\n",
       "    return rules\n",
       "\n",
       "\n",
       "class ProbGrammar:\n",
       "\n",
       "    def __init__(self, name, rules, lexicon):\n",
       "        """A grammar has a set of rules and a lexicon.\n",
       "        Each rule has a probability."""\n",
       "        self.name = name\n",
       "        self.rules = rules\n",
       "        self.lexicon = lexicon\n",
       "        self.categories = defaultdict(list)\n",
       "\n",
       "        for lhs in lexicon:\n",
       "            for word, prob in lexicon[lhs]:\n",
       "                self.categories[word].append((lhs, prob))\n",
       "\n",
       "    def rewrites_for(self, cat):\n",
       "        """Return a sequence of possible rhs's that cat can be rewritten as."""\n",
       "        return self.rules.get(cat, ())\n",
       "\n",
       "    def isa(self, word, cat):\n",
       "        """Return True iff word is of category cat"""\n",
       "        return cat in [c for c, _ in self.categories[word]]\n",
       "\n",
       "    def cnf_rules(self):\n",
       "        """Returns the tuple (X, Y, Z, p) for rules in the form:\n",
       "        X -> Y Z [p]"""\n",
       "        cnf = []\n",
       "        for X, rules in self.rules.items():\n",
       "            for (Y, Z), p in rules:\n",
       "                cnf.append((X, Y, Z, p))\n",
       "\n",
       "        return cnf\n",
       "\n",
       "    def generate_random(self, S='S'):\n",
       "        """Replace each token in S by a random entry in grammar (recursively).\n",
       "        Returns a tuple of (sentence, probability)."""\n",
       "        import random\n",
       "\n",
       "        def rewrite(tokens, into):\n",
       "            for token in tokens:\n",
       "                if token in self.rules:\n",
       "                    non_terminal, prob = weighted_choice(self.rules[token])\n",
       "                    into[1] *= prob\n",
       "                    rewrite(non_terminal, into)\n",
       "                elif token in self.lexicon:\n",
       "                    terminal, prob = weighted_choice(self.lexicon[token])\n",
       "                    into[0].append(terminal)\n",
       "                    into[1] *= prob\n",
       "                else:\n",
       "                    into[0].append(token)\n",
       "            return into\n",
       "\n",
       "        rewritten_as, prob = rewrite(S.split(), [[], 1])\n",
       "        return (' '.join(rewritten_as), prob)\n",
       "\n",
       "    def __repr__(self):\n",
       "        return '<Grammar {}>'.format(self.name)\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(ProbLexicon, ProbRules, ProbGrammar)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's build a lexicon and rules for the probabilistic grammar:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Lexicon {'Verb': [('is', 0.5), ('say', 0.3), ('are', 0.2)], 'Noun': [('robot', 0.4), ('sheep', 0.4), ('fence', 0.2)], 'Adjective': [('good', 0.5), ('new', 0.2), ('sad', 0.3)], 'Adverb': [('here', 0.6), ('lightly', 0.1), ('now', 0.3)], 'Pronoun': [('me', 0.3), ('you', 0.4), ('he', 0.3)], 'RelPro': [('that', 0.5), ('who', 0.3), ('which', 0.2)], 'Name': [('john', 0.4), ('mary', 0.4), ('peter', 0.2)], 'Article': [('the', 0.5), ('a', 0.25), ('an', 0.25)], 'Preposition': [('to', 0.4), ('in', 0.3), ('at', 0.3)], 'Conjunction': [('and', 0.5), ('or', 0.2), ('but', 0.3)], 'Digit': [('0', 0.35), ('1', 0.35), ('2', 0.3)]}\n", "\n", "Rules: {'S': [(['NP', 'VP'], 0.6), (['S', 'Conjunction', 'S'], 0.4)], '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)], 'VP': [(['Verb'], 0.3), (['VP', 'NP'], 0.2), (['VP', 'Adjective'], 0.25), (['VP', 'PP'], 0.15), (['VP', 'Adverb'], 0.1)], 'Adjs': [(['Adjective'], 0.5), (['Adjective', 'Adjs'], 0.5)], 'PP': [(['Preposition', 'NP'], 1.0)], 'RelClause': [(['RelPro', 'VP'], 1.0)]}\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", " Conjunction = \"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 Conjunction 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": 10, "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": 11, "metadata": {}, "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": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('S', 'NP', 'VP', 1.0), ('NP', 'Article', 'Noun', 0.6), ('NP', 'Adjective', 'Noun', 0.4), ('VP', 'Verb', 'NP', 0.5), ('VP', 'Verb', 'Adjective', 0.5)]\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": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 is\n", "0.0015749999999999998\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": 14, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def HITS(query):\n",
       "    """The HITS algorithm for computing hubs and authorities with respect to a query."""\n",
       "    pages = expand_pages(relevant_pages(query))\n",
       "    for p in pages.values():\n",
       "        p.authority = 1\n",
       "        p.hub = 1\n",
       "    while not convergence():\n",
       "        authority = {p: pages[p].authority for p in pages}\n",
       "        hub = {p: pages[p].hub for p in pages}\n",
       "        for p in pages:\n",
       "            # p.authority ← ∑i Inlinki(p).Hub\n",
       "            pages[p].authority = sum(hub[x] for x in getInlinks(pages[p]))\n",
       "            # p.hub ← ∑i Outlinki(p).Authority\n",
       "            pages[p].hub = sum(authority[x] for x in getOutlinks(pages[p]))\n",
       "        normalize(pages)\n",
       "    return pages\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "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": 15, "metadata": {}, "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": 16, "metadata": {}, "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": 17, "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": 18, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def CYK_parse(words, grammar):\n",
       "    """ [Figure 23.5] """\n",
       "    # We use 0-based indexing instead of the book's 1-based.\n",
       "    N = len(words)\n",
       "    P = defaultdict(float)\n",
       "\n",
       "    # Insert lexical rules for each word.\n",
       "    for (i, word) in enumerate(words):\n",
       "        for (X, p) in grammar.categories[word]:\n",
       "            P[X, i, 1] = p\n",
       "\n",
       "    # Combine first and second parts of right-hand sides of rules,\n",
       "    # from short to long.\n",
       "    for length in range(2, N+1):\n",
       "        for start in range(N-length+1):\n",
       "            for len1 in range(1, length):  # N.B. the book incorrectly has N instead of length\n",
       "                len2 = length - len1\n",
       "                for (X, Y, Z, p) in grammar.cnf_rules():\n",
       "                    P[X, start, length] = max(P[X, start, length],\n",
       "                                              P[Y, start, len1] * P[Z, start+len1, len2] * p)\n",
       "\n",
       "    return P\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "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": 19, "metadata": {}, "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": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "defaultdict(, {('Article', 0, 1): 0.5, ('Noun', 1, 1): 0.4, ('Verb', 2, 1): 0.5, ('Adjective', 3, 1): 0.5, ('S', 0, 2): 0.0, ('NP', 0, 1): 0.0, ('VP', 1, 1): 0.0, ('NP', 0, 2): 0.12, ('Adjective', 0, 1): 0.0, ('VP', 0, 2): 0.0, ('Verb', 0, 1): 0.0, ('NP', 1, 1): 0.0, ('Adjective', 1, 1): 0.0, ('S', 1, 2): 0.0, ('VP', 2, 1): 0.0, ('NP', 1, 2): 0.0, ('Article', 1, 1): 0.0, ('Noun', 2, 1): 0.0, ('VP', 1, 2): 0.0, ('Verb', 1, 1): 0.0, ('NP', 2, 1): 0.0, ('Adjective', 2, 1): 0.0, ('S', 2, 2): 0.0, ('VP', 3, 1): 0.0, ('NP', 2, 2): 0.0, ('Article', 2, 1): 0.0, ('Noun', 3, 1): 0.0, ('VP', 2, 2): 0.125, ('NP', 3, 1): 0.0, ('S', 0, 3): 0.0, ('NP', 0, 3): 0.0, ('Noun', 1, 2): 0.0, ('VP', 0, 3): 0.0, ('Adjective', 1, 2): 0.0, ('Article', 0, 2): 0.0, ('Adjective', 0, 2): 0.0, ('Verb', 0, 2): 0.0, ('S', 1, 3): 0.0, ('NP', 1, 3): 0.0, ('Noun', 2, 2): 0.0, ('VP', 1, 3): 0.0, ('Adjective', 2, 2): 0.0, ('Article', 1, 2): 0.0, ('Verb', 1, 2): 0.0, ('S', 0, 4): 0.015, ('NP', 0, 4): 0.0, ('Noun', 1, 3): 0.0, ('VP', 0, 4): 0.0, ('Adjective', 1, 3): 0.0, ('Article', 0, 3): 0.0, ('Adjective', 0, 3): 0.0, ('Verb', 0, 3): 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": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{('Article', 0, 1): 0.5, ('Noun', 1, 1): 0.4, ('Verb', 2, 1): 0.5, ('Adjective', 3, 1): 0.5, ('NP', 0, 2): 0.12, ('VP', 2, 2): 0.125, ('S', 0, 4): 0.015}\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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## CHART PARSING\n", "\n", "### Overview\n", "\n", "Let's now take a look at a more general chart parsing algorithm. Given a non-probabilistic grammar and a sentence, this algorithm builds a parse tree in a top-down manner, with the words of the sentence as the leaves. It works with a dynamic programming approach, building a chart to store parses for substrings so that it doesn't have to analyze them again (just like the CYK algorithm). Each non-terminal, starting from S, gets replaced by its right-hand side rules in the chart, until we end up with the correct parses.\n", "\n", "### Implementation\n", "\n", "A parse is in the form `[start, end, non-terminal, sub-tree, expected-transformation]`, where `sub-tree` is a tree with the corresponding `non-terminal` as its root and `expected-transformation` is a right-hand side rule of the `non-terminal`.\n", "\n", "The chart parsing is implemented in a class, `Chart`. It is initialized with a grammar and can return the list of all the parses of a sentence with the `parses` function.\n", "\n", "The chart is a list of lists. The lists correspond to the lengths of substrings (including the empty string), from start to finish. When we say 'a point in the chart', we refer to a list of a certain length.\n", "\n", "A quick rundown of the class functions:" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "* `parses`: Returns a list of parses for a given sentence. If the sentence can't be parsed, it will return an empty list. Initializes the process by calling `parse` from the starting symbol.\n", "\n", "\n", "* `parse`: Parses the list of words and builds the chart.\n", "\n", "\n", "* `add_edge`: Adds another edge to the chart at a given point. Also, examines whether the edge extends or predicts another edge. If the edge itself is not expecting a transformation, it will extend other edges and it will predict edges otherwise.\n", "\n", "\n", "* `scanner`: Given a word and a point in the chart, it extends edges that were expecting a transformation that can result in the given word. For example, if the word 'the' is an 'Article' and we are examining two edges at a chart's point, with one expecting an 'Article' and the other a 'Verb', the first one will be extended while the second one will not.\n", "\n", "\n", "* `predictor`: If an edge can't extend other edges (because it is expecting a transformation itself), we will add to the chart rules/transformations that can help extend the edge. The new edges come from the right-hand side of the expected transformation's rules. For example, if an edge is expecting the transformation 'Adjective Noun', we will add to the chart an edge for each right-hand side rule of the non-terminal 'Adjective'.\n", "\n", "\n", "* `extender`: Extends edges given an edge (called `E`). If `E`'s non-terminal is the same as the expected transformation of another edge (let's call it `A`), add to the chart a new edge with the non-terminal of `A` and the transformations of `A` minus the non-terminal that matched with `E`'s non-terminal. For example, if an edge `E` has 'Article' as its non-terminal and is expecting no transformation, we need to see what edges it can extend. Let's examine the edge `N`. This expects a transformation of 'Noun Verb'. 'Noun' does not match with 'Article', so we move on. Another edge, `A`, expects a transformation of 'Article Noun' and has a non-terminal of 'NP'. We have a match! A new edge will be added with 'NP' as its non-terminal (the non-terminal of `A`) and 'Noun' as the expected transformation (the rest of the expected transformation of `A`)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can view the source code by running the cell below:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
class Chart:\n",
       "\n",
       "    """Class for parsing sentences using a chart data structure.\n",
       "    >>> chart = Chart(E0)\n",
       "    >>> len(chart.parses('the stench is in 2 2'))\n",
       "    1\n",
       "    """\n",
       "\n",
       "    def __init__(self, grammar, trace=False):\n",
       "        """A datastructure for parsing a string; and methods to do the parse.\n",
       "        self.chart[i] holds the edges that end just before the i'th word.\n",
       "        Edges are 5-element lists of [start, end, lhs, [found], [expects]]."""\n",
       "        self.grammar = grammar\n",
       "        self.trace = trace\n",
       "\n",
       "    def parses(self, words, S='S'):\n",
       "        """Return a list of parses; words can be a list or string."""\n",
       "        if isinstance(words, str):\n",
       "            words = words.split()\n",
       "        self.parse(words, S)\n",
       "        # Return all the parses that span the whole input\n",
       "        # 'span the whole input' => begin at 0, end at len(words)\n",
       "        return [[i, j, S, found, []]\n",
       "                for (i, j, lhs, found, expects) in self.chart[len(words)]\n",
       "                # assert j == len(words)\n",
       "                if i == 0 and lhs == S and expects == []]\n",
       "\n",
       "    def parse(self, words, S='S'):\n",
       "        """Parse a list of words; according to the grammar.\n",
       "        Leave results in the chart."""\n",
       "        self.chart = [[] for i in range(len(words)+1)]\n",
       "        self.add_edge([0, 0, 'S_', [], [S]])\n",
       "        for i in range(len(words)):\n",
       "            self.scanner(i, words[i])\n",
       "        return self.chart\n",
       "\n",
       "    def add_edge(self, edge):\n",
       "        """Add edge to chart, and see if it extends or predicts another edge."""\n",
       "        start, end, lhs, found, expects = edge\n",
       "        if edge not in self.chart[end]:\n",
       "            self.chart[end].append(edge)\n",
       "            if self.trace:\n",
       "                print('Chart: added {}'.format(edge))\n",
       "            if not expects:\n",
       "                self.extender(edge)\n",
       "            else:\n",
       "                self.predictor(edge)\n",
       "\n",
       "    def scanner(self, j, word):\n",
       "        """For each edge expecting a word of this category here, extend the edge."""\n",
       "        for (i, j, A, alpha, Bb) in self.chart[j]:\n",
       "            if Bb and self.grammar.isa(word, Bb[0]):\n",
       "                self.add_edge([i, j+1, A, alpha + [(Bb[0], word)], Bb[1:]])\n",
       "\n",
       "    def predictor(self, edge):\n",
       "        """Add to chart any rules for B that could help extend this edge."""\n",
       "        (i, j, A, alpha, Bb) = edge\n",
       "        B = Bb[0]\n",
       "        if B in self.grammar.rules:\n",
       "            for rhs in self.grammar.rewrites_for(B):\n",
       "                self.add_edge([j, j, B, [], rhs])\n",
       "\n",
       "    def extender(self, edge):\n",
       "        """See what edges can be extended by this edge."""\n",
       "        (j, k, B, _, _) = edge\n",
       "        for (i, j, A, alpha, B1b) in self.chart[j]:\n",
       "            if B1b and B == B1b[0]:\n",
       "                self.add_edge([i, k, A, alpha + [edge], B1b[1:]])\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(Chart)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example\n", "\n", "We will use the grammar `E0` to parse the sentence \"the stench is in 2 2\".\n", "\n", "First we need to build a `Chart` object:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "chart = Chart(nlp.E0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And then we simply call the `parses` function:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[0, 6, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], []]]\n" ] } ], "source": [ "print(chart.parses('the stench is in 2 2'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can see which edges get added by setting the optional initialization argument `trace` to true." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Chart: added [0, 0, 'S_', [], ['S']]\n", "Chart: added [0, 0, 'S', [], ['NP', 'VP']]\n", "Chart: added [0, 0, 'NP', [], ['Pronoun']]\n", "Chart: added [0, 0, 'NP', [], ['Name']]\n", "Chart: added [0, 0, 'NP', [], ['Noun']]\n", "Chart: added [0, 0, 'NP', [], ['Article', 'Noun']]\n", "Chart: added [0, 0, 'NP', [], ['Digit', 'Digit']]\n", "Chart: added [0, 0, 'NP', [], ['NP', 'PP']]\n", "Chart: added [0, 0, 'NP', [], ['NP', 'RelClause']]\n", "Chart: added [0, 0, 'S', [], ['S', 'Conjunction', 'S']]\n", "Chart: added [0, 1, 'NP', [('Article', 'the')], ['Noun']]\n", "Chart: added [0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []]\n", "Chart: added [0, 2, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []]], ['VP']]\n", "Chart: added [2, 2, 'VP', [], ['Verb']]\n", "Chart: added [2, 2, 'VP', [], ['VP', 'NP']]\n", "Chart: added [2, 2, 'VP', [], ['VP', 'Adjective']]\n", "Chart: added [2, 2, 'VP', [], ['VP', 'PP']]\n", "Chart: added [2, 2, 'VP', [], ['VP', 'Adverb']]\n", "Chart: added [0, 2, 'NP', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []]], ['PP']]\n", "Chart: added [2, 2, 'PP', [], ['Preposition', 'NP']]\n", "Chart: added [0, 2, 'NP', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []]], ['RelClause']]\n", "Chart: added [2, 2, 'RelClause', [], ['That', 'VP']]\n", "Chart: added [2, 3, 'VP', [('Verb', 'is')], []]\n", "Chart: added [0, 3, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 3, 'VP', [('Verb', 'is')], []]], []]\n", "Chart: added [0, 3, 'S_', [[0, 3, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 3, 'VP', [('Verb', 'is')], []]], []]], []]\n", "Chart: added [0, 3, 'S', [[0, 3, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 3, 'VP', [('Verb', 'is')], []]], []]], ['Conjunction', 'S']]\n", "Chart: added [2, 3, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []]], ['NP']]\n", "Chart: added [3, 3, 'NP', [], ['Pronoun']]\n", "Chart: added [3, 3, 'NP', [], ['Name']]\n", "Chart: added [3, 3, 'NP', [], ['Noun']]\n", "Chart: added [3, 3, 'NP', [], ['Article', 'Noun']]\n", "Chart: added [3, 3, 'NP', [], ['Digit', 'Digit']]\n", "Chart: added [3, 3, 'NP', [], ['NP', 'PP']]\n", "Chart: added [3, 3, 'NP', [], ['NP', 'RelClause']]\n", "Chart: added [2, 3, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []]], ['Adjective']]\n", "Chart: added [2, 3, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []]], ['PP']]\n", "Chart: added [3, 3, 'PP', [], ['Preposition', 'NP']]\n", "Chart: added [2, 3, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []]], ['Adverb']]\n", "Chart: added [3, 4, 'PP', [('Preposition', 'in')], ['NP']]\n", "Chart: added [4, 4, 'NP', [], ['Pronoun']]\n", "Chart: added [4, 4, 'NP', [], ['Name']]\n", "Chart: added [4, 4, 'NP', [], ['Noun']]\n", "Chart: added [4, 4, 'NP', [], ['Article', 'Noun']]\n", "Chart: added [4, 4, 'NP', [], ['Digit', 'Digit']]\n", "Chart: added [4, 4, 'NP', [], ['NP', 'PP']]\n", "Chart: added [4, 4, 'NP', [], ['NP', 'RelClause']]\n", "Chart: added [4, 5, 'NP', [('Digit', '2')], ['Digit']]\n", "Chart: added [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]\n", "Chart: added [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]\n", "Chart: added [2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]\n", "Chart: added [0, 6, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], []]\n", "Chart: added [0, 6, 'S_', [[0, 6, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], []]], []]\n", "Chart: added [0, 6, 'S', [[0, 6, 'S', [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []], [2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], []]], ['Conjunction', 'S']]\n", "Chart: added [2, 6, 'VP', [[2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], ['NP']]\n", "Chart: added [6, 6, 'NP', [], ['Pronoun']]\n", "Chart: added [6, 6, 'NP', [], ['Name']]\n", "Chart: added [6, 6, 'NP', [], ['Noun']]\n", "Chart: added [6, 6, 'NP', [], ['Article', 'Noun']]\n", "Chart: added [6, 6, 'NP', [], ['Digit', 'Digit']]\n", "Chart: added [6, 6, 'NP', [], ['NP', 'PP']]\n", "Chart: added [6, 6, 'NP', [], ['NP', 'RelClause']]\n", "Chart: added [2, 6, 'VP', [[2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], ['Adjective']]\n", "Chart: added [2, 6, 'VP', [[2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], ['PP']]\n", "Chart: added [6, 6, 'PP', [], ['Preposition', 'NP']]\n", "Chart: added [2, 6, 'VP', [[2, 6, 'VP', [[2, 3, 'VP', [('Verb', 'is')], []], [3, 6, 'PP', [('Preposition', 'in'), [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], []]], []]], ['Adverb']]\n", "Chart: added [4, 6, 'NP', [[4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], ['PP']]\n", "Chart: added [4, 6, 'NP', [[4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]], ['RelClause']]\n", "Chart: added [6, 6, 'RelClause', [], ['That', 'VP']]\n" ] }, { "data": { "text/plain": [ "[[0,\n", " 6,\n", " 'S',\n", " [[0, 2, 'NP', [('Article', 'the'), ('Noun', 'stench')], []],\n", " [2,\n", " 6,\n", " 'VP',\n", " [[2, 3, 'VP', [('Verb', 'is')], []],\n", " [3,\n", " 6,\n", " 'PP',\n", " [('Preposition', 'in'),\n", " [4, 6, 'NP', [('Digit', '2'), ('Digit', '2')], []]],\n", " []]],\n", " []]],\n", " []]]" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "chart_trace = Chart(nlp.E0, trace=True)\n", "chart_trace.parses('the stench is in 2 2')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try and parse a sentence that is not recognized by the grammar:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[]\n" ] } ], "source": [ "print(chart.parses('the stench 2 2'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An empty list was returned." ] }, { "cell_type": "code", "execution_count": null, "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.7.6" } }, "nbformat": 4, "nbformat_minor": 1 }