sippycup-unit-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/sippycup-small.jpg\" align=\"left\" style=\"padding-right: 30px\"/>\n",
    "\n",
    "<h1 style=\"line-height: 125%\">\n",
    "  SippyCup<br />\n",
    "  Unit 1: Natural language arithmetic\n",
    "</h1>\n",
    "\n",
    "<p>\n",
    "  <a href=\"http://nlp.stanford.edu/~wcmac/\">Bill MacCartney</a><br/>\n",
    "  Spring 2015\n",
    "  <!-- <a href=\"mailto:wcmac@cs.stanford.edu\">wcmac@cs.stanford.edu</a> -->\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"margin: 0px 0px; padding: 10px; background-color: #ddddff; border-style: solid; border-color: #aaaacc; border-width: 1px\">\n",
    "This is Unit 1 of the <a href=\"./sippycup-unit-0.ipynb\">SippyCup codelab</a>.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our first case study is directly inspired by [Liang & Potts 2015][].  We consider the problem of interpreting expressions of natural language arithmetic, such as:\n",
    "\n",
    "  [Liang & Potts 2015]: http://www.annualreviews.org/doi/pdf/10.1146/annurev-linguist-030514-125312\n",
    "\n",
    "    \"one plus one\"\n",
    "    \"minus three minus two\"\n",
    "    \"three plus three minus two\"\n",
    "    \"two times two plus three\"\n",
    "\n",
    "While these phrases are simple enough, they do exhibit some interesting ambiguity.  For example, \"two times two plus three\" exhibits [syntactic ambiguity][]: it could refer to either seven or ten, depending on the [order of operations][].  And \"minus three minus two\" exhibits [lexical ambiguity][]: the first \"minus\" refers to the (unary) negation operator, while the second \"minus\" refers to the (binary) subtraction operator.\n",
    "\n",
    "  [order of operations]: http://en.wikipedia.org/wiki/Order_of_operations\n",
    "  [syntactic ambiguity]: http://en.wikipedia.org/wiki/Syntactic_ambiguity\n",
    "  [lexical ambiguity]: http://en.wikipedia.org/wiki/Lexical_ambiguity\n",
    "\n",
    "Still, as semantic parsing problems go, this one is not very challenging.  It has a small, closed vocabulary, and a limited variety of syntactic structures.  These qualities make the arithmetic domain an ideal vehicle for developing the essential elements of a semantic parsing system.\n",
    "\n",
    "<!--\n",
    ", including:\n",
    "\n",
    "- a semantic representation\n",
    "- example data, for evaluation and training\n",
    "- a context-free grammar\n",
    "- a chart parsing algorithm\n",
    "- semantic attachments\n",
    "- a linear scoring function for parses\n",
    "- weight learning\n",
    "- limited grammar induction\n",
    "-->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example inputs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whenever we begin work on a new domain (that is, application or use case) for semantic parsing, the first order of business is to collect a broad sample of the inputs we want to be able to handle, and to study its properties.  The characteristics of this sample will drive the choice of semantic representation, the style and structure of the grammar, and the selection of features for the scoring model.  It will also serve as the basis of the dataset used for evaluation and for training.  Therefore, it's important that the sample be as *large* and as *realistic* as possible.  It should be representative of the inputs the semantic parser will actually encounter in its intended application.  \n",
    "\n",
    "The central challenge of semantic parsing is linguistic diversity.  There are just a zillion different ways to say the same thing — far, far more than a single person will ever come up with.\n",
    "Therefore, when constructing a set of example inputs, we should strongly prefer naturally-occurring (or \"found\") data reflecting the linguistic output of many different people.  Only in this way can we be confident that our sample reflects the diversity of real-world usage.\n",
    "\n",
    "*However*, for this case study only, we're going to ignore that fine advice.  The arithmetic domain is simple and straightforward, and for now our goals are strictly pedagogical.  So a small, artificial sample of inputs will suffice.  Here's a sample of 17 inputs borrowed from the [companion code][] to [Liang & Potts 2015][].\n",
    "\n",
    "  [companion code]: https://github.com/cgpotts/annualreview-complearning\n",
    "  [Liang & Potts 2015]: http://www.annualreviews.org/doi/pdf/10.1146/annurev-linguist-030514-125312"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "inputs = [\n",
    "    \"one plus one\",\n",
    "    \"one plus two\",\n",
    "    \"one plus three\",\n",
    "    \"two plus two\",\n",
    "    \"two plus three\",\n",
    "    \"three plus one\",\n",
    "    \"three plus minus two\",\n",
    "    \"two plus two\",\n",
    "    \"three minus two\",\n",
    "    \"minus three minus two\",\n",
    "    \"two times two\",\n",
    "    \"two times three\",\n",
    "    \"three plus three minus two\",\n",
    "    \"minus three\",\n",
    "    \"three plus two\",\n",
    "    \"two times two plus three\",\n",
    "    \"minus four\",\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that, even for the arithmetic domain, this sample is quite limited in scope.  It uses only the integers one through four, and it uses only a small number of arithmetic operations.  The [exercises](#arithmetic-exercises) at the end of this unit will challenge you to extend the scope of the problem in various ways.\n",
    "\n",
    "In our [second case study][], we'll look at strategies for extracting a larger and more realistic sample of inputs from search query logs.\n",
    "\n",
    "  [second case study]: ./sippycup-unit-2.ipynb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Semantic representation <a id=\"arithmetic-semantic-representation\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Having collected a sample of inputs, the next order of business is to choose a good semantic representation.  After all, the semantic representation is the desired *output* of the semantic parsing system, so the choice of representation will drive many other decisions.\n",
    "\n",
    "As discussed [earlier](./sippycup-unit-0.ipynb#Designing-a-semantic-representation), our semantic representation should be machine-readable, unambiguous, and easily executable.  For the domain of natural language arithmetic, a natural choice is to use [binary expression trees][], represented in Python by nested tuples.  That is, every semantic representation will be either a number, or a tuple consisting of an operator and one or more arguments, which are themselves semantic representations.  To begin with, we'll define just four operators:\n",
    "`+` (addition),\n",
    "`-` (subtraction),\n",
    "`*` (multiplication), and\n",
    "`~` (negation).\n",
    "Thus, all of the following are valid semantic representations:\n",
    "\n",
    "  [binary expression trees]: http://en.wikipedia.org/wiki/Binary_expression_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sems = [\n",
    "    ('+', 1, 1),                # one plus one\n",
    "    ('-', ('~', 3), 2),         # minus three minus two\n",
    "    ('-', ('+', 3, 3), 2),      # three plus three minus two\n",
    "    ('+', ('*', 2, 2), 3),      # two times two plus three\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's easy to implement an executor which actually performs the arithmetic calculations described by these semantic representations to return a denotation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ops = {\n",
    "    '~': lambda x: -x,\n",
    "    '+': lambda x, y: x + y,\n",
    "    '-': lambda x, y: x - y,\n",
    "    '*': lambda x, y: x * y,\n",
    "}\n",
    "\n",
    "def execute(sem):\n",
    "    if isinstance(sem, tuple):\n",
    "        op = ops[sem[0]]\n",
    "        args = [execute(arg) for arg in sem[1:]]\n",
    "        return op(*args)\n",
    "    else:\n",
    "        return sem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the executor is simple, straightforward, deterministic, and doesn't rely on any linguistic knowledge.  This is a sign that we've chosen a good semantic representation!\n",
    "\n",
    "Let's see the executor in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('+', 1, 1) = 2\n",
      "('-', ('~', 3), 2) = -5\n",
      "('-', ('+', 3, 3), 2) = 4\n",
      "('+', ('*', 2, 2), 3) = 7\n"
     ]
    }
   ],
   "source": [
    "for sem in sems:\n",
    "    print('%s = %d' % (sem, execute(sem)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example data <a id=\"arithmetic-example-data\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've collected a sample of inputs and defined a semantic representation, we can construct a set of *examples* which pair inputs with their target outputs.  Examples have two purposes:\n",
    "\n",
    "1. They can serve as _evaluation data_ to assess the quality of our semantic parser.\n",
    "2. They can serve as _training data_ to improve the system.\n",
    "\n",
    "However, writing down target semantics for a large sample of inputs can be laborious, time-consuming, and error-prone.  Depending on the complexity of the semantic representation, it may also require expert knowledge.  In many domains, it is easier and faster to write down target denotations than to write down target semantics, and the task often can be [crowdsourced][].  As we'll see later, in many cases target denotations alone can suffice for both evaluation and training.\n",
    "\n",
    "  [crowdsourced]: http://en.wikipedia.org/wiki/Crowdsourcing\n",
    "\n",
    "For the arithmetic domain, we'll generate examples which include both semantics and denotations.\n",
    "The SippyCup codebase defines (in [`example.py`](./example.py)) a simple container class called `Example`.  By importing this class, we can define some examples to guide our development.\n",
    "\n",
    "<!-- TODO: consider moving all imports to a block at the end of Unit 0. -->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from example import Example\n",
    "\n",
    "arithmetic_examples = [\n",
    "    Example(input=\"one plus one\", semantics=('+', 1, 1), denotation=2),\n",
    "    Example(input=\"one plus two\", semantics=('+', 1, 2), denotation=3),\n",
    "    Example(input=\"one plus three\", semantics=('+', 1, 3), denotation=4),\n",
    "    Example(input=\"two plus two\", semantics=('+', 2, 2), denotation=4),\n",
    "    Example(input=\"two plus three\", semantics=('+', 2, 3), denotation=5),\n",
    "    Example(input=\"three plus one\", semantics=('+', 3, 1), denotation=4),\n",
    "    Example(input=\"three plus minus two\", semantics=('+', 3, ('~', 2)), denotation=1),\n",
    "    Example(input=\"two plus two\", semantics=('+', 2, 2), denotation=4),\n",
    "    Example(input=\"three minus two\", semantics=('-', 3, 2), denotation=1),\n",
    "    Example(input=\"minus three minus two\", semantics=('-', ('~', 3), 2), denotation=-5),\n",
    "    Example(input=\"two times two\", semantics=('*', 2, 2), denotation=4),\n",
    "    Example(input=\"two times three\", semantics=('*', 2, 3), denotation=6),\n",
    "    Example(input=\"three plus three minus two\", semantics=('-', ('+', 3, 3), 2), denotation=4),\n",
    "    Example(input=\"minus three\", semantics=('~', 3), denotation=-3),\n",
    "    Example(input=\"three plus two\", semantics=('+', 3, 2), denotation=5),\n",
    "    Example(input=\"two times two plus three\", semantics=('+', ('*', 2, 2), 3), denotation=7),\n",
    "    Example(input=\"minus four\", semantics=('~', 4), denotation=-4),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- TODO: Consider whether to divide these into train examples and test examples. -->\n",
    "\n",
    "Note that for examples with syntactically ambiguous inputs, our target semantics and denotations reflects a specific choice about how to resolve the ambiguity which accords with the standard [order of operations][].\n",
    "<!-- TODO: rewrite? -->\n",
    "\n",
    "  [order of operations]: http://en.wikipedia.org/wiki/Order_of_operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Syntactic parsing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, we've defined the problem, and we have a collection of examples which pair inputs with intended outputs.  It's time to get down to business.  How do we actually build a semantic parsing system that can map the example inputs to the target outputs?\n",
    "\n",
    "In order to do *semantic parsing*, we're going to start by doing *syntactic parsing*.  Syntactic parsing is a big topic, and we'll give only a cursory treatment here.  If you haven't seen syntactic parsing before, you might benefit from the fuller exposition in Part III of Jurafsky & Martin, [Speech and Language Processing][].\n",
    "\n",
    "  [Speech and Language Processing]: http://www.cs.colorado.edu/~martin/slp.html\n",
    "\n",
    "In syntactic parsing, the goal is to build a tree structure (a _parse_) over the input which describes what linguists call its [constituency structure][], which basically means how we group the words into larger and larger phrases.  For example, there are two different ways to parse \"minus three minus two\", depending on the order in which we group the words into phrases.  If we start by grouping \"minus three\" into a phrase, we arrive at an answer of -5; if we start by grouping \"three minus two\", we arrive at -1.  We can represent these two parses by adding parentheses to the input, like this:\n",
    "\n",
    "  [constituency structure]: http://en.wikipedia.org/wiki/Phrase_structure_grammar\n",
    "\n",
    "    parse 1        ((minus three) minus two)          yields -5\n",
    "    parse 2        (minus (three minus two))          yields -1\n",
    "\n",
    "Alternatively, we could represent these two parses graphically like this:\n",
    "\n",
    "<img src=\"img/sippycup-figure-11.svg\" width=\"550\"/>\n",
    "In syntactic parsing, we not only group words into phrases, but also assign labels known as _categories_ to each word and phrase.  In SippyCup, we adopt the convention that category names always begin with `$`, so that they are easily distinguished from ordinary words.  For the arithmetic domain, we require only three categories:\n",
    "\n",
    "- `$E`, the category of *expressions*, including both numerals and longer phrases which denote a number.\n",
    "- `$BinOp`, the category of *binary operators*, such as `\"plus\"`, `\"minus\"` (meaning subtraction), and `\"times\"`.\n",
    "- `$UnOp`, the category of *unary operators*, such as `\"minus\"` (meaning negation).\n",
    "\n",
    "If we add category labels to our parses, they look like this:\n",
    "\n",
    "    parse 1        ($E ($E ($UnOp minus) ($E three)) ($BinOp minus) ($E two))\n",
    "    parse 2        ($E ($UnOp minus) ($E ($E three) ($BinOp minus) ($E two)))\n",
    "\n",
    "Or, graphically:\n",
    "\n",
    "<img src=\"img/sippycup-figure-12.svg\" width=\"550\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grammars and rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to build a valid parse tree over an input, we need to know the space of possibilities.  This is the role of the *grammar*, which in SippyCup is a [context-free grammar][] (CFG).  The grammar contains a collection of *rules*, each of which specifies a valid *local subtree*, consisting of a parent and its immediate children.\n",
    "\n",
    "  [context-free grammar]: http://en.wikipedia.org/wiki/Context-free_grammar\n",
    "\n",
    "In these figures, two local subtrees are highlighted in red:\n",
    "\n",
    "<img src=\"img/sippycup-figure-13.svg\" width=\"550\"/>\n",
    "\n",
    "It's kind of like building with Legos.  There are many types of pieces.  Each grammar rule specifies the shape of one type of piece, and how it connects to other pieces.  Starting from the words of the input, you connect pieces into larger and larger structures, always according to the rules.  The set of pieces available defines the space of structures you can build.\n",
    "\n",
    "Here are all the pieces we need to build either of the parse trees above:\n",
    "\n",
    "<img src=\"img/sippycup-figure-14.svg\" width=\"625\"/>\n",
    "\n",
    "A grammar rule has a *left-hand side* (LHS) which is a single category, and a *right-hand side* (RHS) which is a sequence of one or more categories or words.  (Words are also known as *terminals*, and categories as *non-terminals*.)  The LHS specifies the parent of a valid local subtree; the RHS, the children.\n",
    "\n",
    "Here's a simple Python class for representing grammar rules.  You can ignore `sem` for now — we're only concerned with syntax at this point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Rule:\n",
    "    def __init__(self, lhs, rhs, sem=None):\n",
    "        self.lhs = lhs\n",
    "        self.rhs = tuple(rhs.split()) if isinstance(rhs, str) else rhs\n",
    "        self.sem = sem\n",
    "\n",
    "    def __str__(self):\n",
    "        return 'Rule' + str((self.lhs, ' '.join(self.rhs), self.sem))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that while `rhs` is stored as a tuple of strings, the constructor will accept either a tuple of strings or a single space-separated string.  This is purely for convenience; it means that instead of `Rule('$E', ('$E', '$BinOp', $E'))` we can write `Rule('$E', '$E $BinOp $E')`.\n",
    "\n",
    "We can now write down a few grammar rules for the arithmetic domain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "numeral_rules = [\n",
    "    Rule('$E', 'one'),\n",
    "    Rule('$E', 'two'),\n",
    "    Rule('$E', 'three'),\n",
    "    Rule('$E', 'four'),\n",
    "]\n",
    "\n",
    "operator_rules = [\n",
    "    Rule('$UnOp', 'minus'),\n",
    "    Rule('$BinOp', 'plus'),\n",
    "    Rule('$BinOp', 'minus'),\n",
    "    Rule('$BinOp', 'times'),\n",
    "]\n",
    "\n",
    "compositional_rules = [\n",
    "    Rule('$E', '$UnOp $E'),\n",
    "    Rule('$E', '$E $BinOp $E'),\n",
    "]\n",
    "\n",
    "def arithmetic_rules():\n",
    "    return numeral_rules + operator_rules + compositional_rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, these rules are all we need to be able to parse the 17 examples above.\n",
    "\n",
    "There's just one little snag: the parsing algorithm we'll present in the next section requires that the grammar be in [Chomsky normal form][], or CNF. (We'll look at ways to relax this restriction in the [next unit](./sippycup-unit-2.ipynb).) Roughly, CNF requires that every grammar rule have one of two forms:\n",
    "\n",
    "  [Chomsky normal form]: http://en.wikipedia.org/wiki/Chomsky_normal_form\n",
    "\n",
    "- In a *unary lexical rule*, the RHS must consist of exactly one word (terminal).\n",
    "- In a *binary compositional rule*, the RHS must consist of exactly two categories (non-terminals).\n",
    "\n",
    "Actually, we're already pretty close to satisfying these criteria.  All the rules in `numeral_rules` and `operator_rules` are unary lexical rules.  And the first rule in `compositional_rules` is a binary compositional rule.  But the second rule is a problem: it has three categories on the RHS, so it's a *trinary* compositional rule.\n",
    "\n",
    "Fear not!  We can convert our grammar to CNF by *binarizing* the offending rule.  It's easiest to think in terms of local subtrees here.  To binarize a local subtree having more than two children, we just introduce a new node underneath the parent which becomes the new parent of all the children *except* the rightmost.  (If the new node still has more than two children, we just repeat the process.)\n",
    "\n",
    "<img src=\"img/sippycup-figure-15.svg\" width=\"360\"/>\n",
    "\n",
    "We also have to come up with a category for the new node.  Since it spans an `$E` and a `$BinOp`, let's call it `$EBO`.\n",
    "\n",
    "<img src=\"img/sippycup-figure-16.svg\" width=\"360\"/>\n",
    "\n",
    "In terms of grammar rules, we're replacing the (bad) trinary rule with two (good) binary rules, as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "compositional_rules = [\n",
    "    Rule('$E', '$UnOp $E'),\n",
    "    Rule('$EBO', '$E $BinOp'),  # binarized rule\n",
    "    Rule('$E', '$EBO $E'),      # binarized rule\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's define some helper functions which will help us ensure that our grammars are in CNF."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_cat(label):\n",
    "    return label.startswith('$')\n",
    "\n",
    "def is_lexical(rule):\n",
    "    return all([not is_cat(rhsi) for rhsi in rule.rhs])\n",
    "\n",
    "def is_binary(rule):\n",
    "    return len(rule.rhs) == 2 and is_cat(rule.rhs[0]) and is_cat(rule.rhs[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(In a more object-oriented design, these functions might be defined as methods of `Rule`.  However, defining them as static functions is more convenient for the incremental presentation of this codelab.)\n",
    "\n",
    "Now we'll create a `Grammar` class to hold a collection of rules.  We'll store the rules in maps indexed by their right-hand sides, which will facilitate lookup during parsing.  Ignore the `parse_input()` method for now — we'll define it shortly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Grammar:\n",
    "    def __init__(self, rules=[]):\n",
    "        self.lexical_rules = defaultdict(list)\n",
    "        self.binary_rules = defaultdict(list)\n",
    "        for rule in rules:\n",
    "            add_rule(self, rule)\n",
    "        print('Created grammar with %d rules.' % len(rules))\n",
    "        \n",
    "    def parse_input(self, input):\n",
    "        \"\"\"Returns a list of parses for the given input.\"\"\"\n",
    "        return parse_input(self, input)  # defined later\n",
    "\n",
    "def add_rule(grammar, rule):\n",
    "    if is_lexical(rule):\n",
    "        grammar.lexical_rules[rule.rhs].append(rule)\n",
    "    elif is_binary(rule):\n",
    "        grammar.binary_rules[rule.rhs].append(rule)\n",
    "    else:\n",
    "        raise Exception('Cannot accept rule: %s' % rule)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Again, we've defined `add_rule()` as a static function, rather than a member of the `Grammar` class, only because it facilitates the incremental presentation of this codelab.)\n",
    "\n",
    "Let's create a grammar using the rules we defined earlier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created grammar with 11 rules.\n"
     ]
    }
   ],
   "source": [
    "arithmetic_grammar = Grammar(arithmetic_rules())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, we have a grammar.  Now we need to implement a parsing algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chart parsing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next question is, given a grammar and a specific input, how can we find the set of parses for the input which are allowed by the grammar?\n",
    "<!-- TODO: Because the space of possible parses is, in general, exponential, ... -->\n",
    "To solve this problem, we're going to use a variant of the [CYK algorithm][], which is an example of a [chart parsing][] algorithm, and more broadly, of [dynamic programming][].\n",
    "\n",
    "  [CYK algorithm]: http://en.wikipedia.org/wiki/CYK_algorithm\n",
    "  [chart parsing]: http://en.wikipedia.org/wiki/Chart_parser\n",
    "  [dynamic programming]: http://en.wikipedia.org/wiki/Dynamic_programming\n",
    "\n",
    "Chart parsing relies on a data structure known as the *chart*, which has one entry (known as a *cell*) for every possible span in the input.  Spans are identified by a pair of token indices (*i*, *j*), where *i* is the (0-based) index of the leftmost token of the span, and *j* is one greater than the index of the rightmost token of the span.  It follows that *j* – *i* is equal to the length of the span.  For example, if the input is \"one plus two\", then span (0, 1) is \"one\", span (1, 3) is \"plus two\", and span (0, 3) is \"one plus two\".  The chart cell for each span holds a list of possible parses for that span.\n",
    "\n",
    "(TODO: Show diagram of chart, with iteration order marked by arrows.)\n",
    "\n",
    "The chart parsing algorithm works like this:\n",
    "\n",
    "- Split the input into a sequence of tokens.\n",
    "- Construct a chart, which maps from each span of the input to a list of possible parses for that span.\n",
    "- Iterate over all possible spans, working bottom-up, from smaller spans to larger spans.\n",
    "- For each span, and for each grammar rule, if the rule lets you build a parse for the span, add it to the chart.\n",
    "\n",
    "Here's how to express the algorithm in Python.  It's surprisingly simple!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def parse_input(grammar, input):\n",
    "    \"\"\"Returns a list of all parses for input using grammar.\"\"\"\n",
    "    tokens = input.split()\n",
    "    chart = defaultdict(list)  # map from span (i, j) to list of parses\n",
    "    for j in range(1, len(tokens) + 1):\n",
    "        for i in range(j - 1, -1, -1):\n",
    "            apply_lexical_rules(grammar, chart, tokens, i, j)\n",
    "            apply_binary_rules(grammar, chart, i, j)\n",
    "    return chart[(0, len(tokens))]  # return all parses for full span"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The definition of `apply_lexical_rules()` is very simple.  We simply retrieve from the grammar all the lexical rules having the given token span as RHS.  For each such rule, we construct a new instance  of `Parse` (a class we'll define in a moment) and add it to the chart. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def apply_lexical_rules(grammar, chart, tokens, i, j):\n",
    "    \"\"\"Add parses to span (i, j) in chart by applying lexical rules from grammar to tokens.\"\"\"\n",
    "    for rule in grammar.lexical_rules[tuple(tokens[i:j])]:\n",
    "        chart[(i, j)].append(Parse(rule, tokens[i:j]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(By the way, you might wonder why the invocation of `apply_lexical_rules()` appears inside the loop over `i` (and why its arguments include `i`).  Isn't it enough to call it once for each value of `j`?  Yes, for now, it is.  But in the [next unit](./sippycup-unit-2.ipynb), we'll extend the grammar to support lexical rules with multiple words in the RHS, and this code design will make that easier.)\n",
    "\n",
    "The definition of `apply_binary_rules()` is slightly more complicated.  First, we need to iterate over all indices *k* at which the span (*i*, *j*) could be split into two subspans.  For each split point, we consult the chart to see what parses we've already constructed for the two subspans.  Then, for each pair of subspan parses, we retrieve from the grammar all binary rules that could used to combine them.  For each such rule, we construct a new instance  of `Parse` and add it to the chart."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "def apply_binary_rules(grammar, chart, i, j):\n",
    "    \"\"\"Add parses to span (i, j) in chart by applying binary rules from grammar.\"\"\"\n",
    "    for k in range(i + 1, j):  # all ways of splitting the span into two subspans\n",
    "        for parse_1, parse_2 in product(chart[(i, k)], chart[(k, j)]):\n",
    "            for rule in grammar.binary_rules[(parse_1.rule.lhs, parse_2.rule.lhs)]:\n",
    "                chart[(i, j)].append(Parse(rule, [parse_1, parse_2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By the way, it should now be clear why we require the grammar to be in Chomsky normal form.  If we allow rules with three (or more) items on the RHS, then we have to consider all ways of splitting a span into three (or more) subspans.  This quickly becomes both inefficient and unwieldy.  Better to binarize all the rules first.\n",
    "\n",
    "Now what about the `Parse` class?  It's a simple container class which stores the `Rule` used to build the parse and the children to which the rule was applied.  If the rule was a lexical rule, the children are just tokens; if it was a compositional rule, the children are other `Parse`s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Parse:\n",
    "    def __init__(self, rule, children):\n",
    "        self.rule = rule\n",
    "        self.children = tuple(children[:])\n",
    "        self.semantics = compute_semantics(self)  # Ignore this for now -- we'll use it later.\n",
    "        self.score = float('NaN')                 # Ditto.\n",
    "        self.denotation = None                    # Ditto.\n",
    "\n",
    "    def __str__(self):\n",
    "        return '(%s %s)' % (self.rule.lhs, ' '.join([str(c) for c in self.children]))\n",
    "    \n",
    "def compute_semantics(parse):\n",
    "    return None                                   # We'll redefine this later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're finally ready to do some parsing!  Let's see our grammar in action, by applying it to the set of 17 examples we defined above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created grammar with 11 rules.\n",
      "\n",
      "input            one plus one\n",
      "parse 0          ($E ($EBO ($E one) ($BinOp plus)) ($E one))\n",
      "\n",
      "input            one plus two\n",
      "parse 0          ($E ($EBO ($E one) ($BinOp plus)) ($E two))\n",
      "\n",
      "input            one plus three\n",
      "parse 0          ($E ($EBO ($E one) ($BinOp plus)) ($E three))\n",
      "\n",
      "input            two plus two\n",
      "parse 0          ($E ($EBO ($E two) ($BinOp plus)) ($E two))\n",
      "\n",
      "input            two plus three\n",
      "parse 0          ($E ($EBO ($E two) ($BinOp plus)) ($E three))\n",
      "\n",
      "input            three plus one\n",
      "parse 0          ($E ($EBO ($E three) ($BinOp plus)) ($E one))\n",
      "\n",
      "input            three plus minus two\n",
      "parse 0          ($E ($EBO ($E three) ($BinOp plus)) ($E ($UnOp minus) ($E two)))\n",
      "\n",
      "input            two plus two\n",
      "parse 0          ($E ($EBO ($E two) ($BinOp plus)) ($E two))\n",
      "\n",
      "input            three minus two\n",
      "parse 0          ($E ($EBO ($E three) ($BinOp minus)) ($E two))\n",
      "\n",
      "input            minus three minus two\n",
      "parse 0          ($E ($UnOp minus) ($E ($EBO ($E three) ($BinOp minus)) ($E two)))\n",
      "parse 1          ($E ($EBO ($E ($UnOp minus) ($E three)) ($BinOp minus)) ($E two))\n",
      "\n",
      "input            two times two\n",
      "parse 0          ($E ($EBO ($E two) ($BinOp times)) ($E two))\n",
      "\n",
      "input            two times three\n",
      "parse 0          ($E ($EBO ($E two) ($BinOp times)) ($E three))\n",
      "\n",
      "input            three plus three minus two\n",
      "parse 0          ($E ($EBO ($E three) ($BinOp plus)) ($E ($EBO ($E three) ($BinOp minus)) ($E two)))\n",
      "parse 1          ($E ($EBO ($E ($EBO ($E three) ($BinOp plus)) ($E three)) ($BinOp minus)) ($E two))\n",
      "\n",
      "input            minus three\n",
      "parse 0          ($E ($UnOp minus) ($E three))\n",
      "\n",
      "input            three plus two\n",
      "parse 0          ($E ($EBO ($E three) ($BinOp plus)) ($E two))\n",
      "\n",
      "input            two times two plus three\n",
      "parse 0          ($E ($EBO ($E two) ($BinOp times)) ($E ($EBO ($E two) ($BinOp plus)) ($E three)))\n",
      "parse 1          ($E ($EBO ($E ($EBO ($E two) ($BinOp times)) ($E two)) ($BinOp plus)) ($E three))\n",
      "\n",
      "input            minus four\n",
      "parse 0          ($E ($UnOp minus) ($E four))\n"
     ]
    }
   ],
   "source": [
    "arithmetic_grammar = Grammar(arithmetic_rules())\n",
    "for example in arithmetic_examples:\n",
    "    parses = parse_input(arithmetic_grammar, example.input)\n",
    "    print()\n",
    "    print('%-16s %s' % ('input', example.input))\n",
    "    for idx, parse in enumerate(parses):\n",
    "        print('%-16s %s' % ('parse %d' % idx, parse))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should observe that all 17 examples were successfully parsed.  Moreover, the examples which exhibit ambiguity get multiple parses, exactly as expected.\n",
    "\n",
    "Syntactic parsing provides the spine around which we'll build our semantic parsing system.  But now we need to add semantics.\n",
    "<!-- TODO: reword? -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding semantics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to bring semantics into the picture.  Given a parse tree, we'd like to attach a semantic representation to every node in the tree, like this:\n",
    "\n",
    "<img src=\"img/sippycup-figure-18.svg\" width=\"350\"/>\n",
    "\n",
    "How are the semantic representations computed?  Like the parse tree itself, they are computed *bottom-up*.  We begin at the leaf nodes, where the semantics are determined directly by the words: the semantics for \"one\" is `1`, the semantics for \"plus\" is `+`, and so on. This is province of [lexical semantics][].\n",
    "\n",
    "  [lexical semantics]: http://en.wikipedia.org/wiki/Lexical_semantics\n",
    "\n",
    "Then, as we work our way up the tree, the semantic representation for each internal node is computed from the semantics of its children, in a manner that depends on the rule that was used to combine them.  This is the province of *compositional semantics*, and it hinges on the [principle of compositionality][] (often attributed to [Gottlob Frege][]).\n",
    "\n",
    "  [Principle of compositionality]: http://en.wikipedia.org/wiki/Principle_of_compositionality\n",
    "  [Gottlob Frege]: http://en.wikipedia.org/wiki/Gottlob_Frege\n",
    "\n",
    "\n",
    "<div style=\"text-align: center; margin: 20px 100px; padding: 10px 20px 20px 20px; background-color: #eeffdd; border-style: solid; border-color: #bbccaa; border-width: 5px\">\n",
    "<h3>The principle of compositionality</h3>\n",
    "<p>The meaning of a compound expression is a function of the meanings of its parts and the manner of their combination.</p>\n",
    "</div>\n",
    "\n",
    "(The principle of compositionality is central to [Montague grammar][], which provides the theoretical foundation for much academic work in semantic parsing.  However, most formulations of Montague grammar assume the use of the [typed lambda calculus][] for semantic representations.  SippyCup is compatible with this choice, but does not assume it.)\n",
    "\n",
    "  [Montague grammar]: http://en.wikipedia.org/wiki/Montague_grammar\n",
    "  [typed lambda calculus]: http://en.wikipedia.org/wiki/Simply_typed_lambda_calculus\n",
    "\n",
    "Now recall that the rules of our grammar specify valid local subtrees from which we can construct parse trees.  Just as we've added semantic attachments to our parse trees, we'll add semantic attachments to the rules of our grammar. The semantic attachment to a rule specifies how to construct the semantics for the parent (LHS) category.  For a lexical rule, the semantic attachment is simply a semantic representation (or a fragment thereof).  For a compositional rule, the semantic attachment is a function which takes the semantics of the children as input and returns the semantics for the parent.\n",
    "\n",
    "Let's see how this looks in Python.  We need to redefine our rules to include semantic attachments.  For *lexical* rules, the semantic attachments directly specify semantic representations (or fragments thereof):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "numeral_rules = [\n",
    "    Rule('$E', 'one', 1),\n",
    "    Rule('$E', 'two', 2),\n",
    "    Rule('$E', 'three', 3),\n",
    "    Rule('$E', 'four', 4),\n",
    "]\n",
    "\n",
    "operator_rules = [\n",
    "    Rule('$UnOp', 'minus', '~'),\n",
    "    Rule('$BinOp', 'plus', '+'),\n",
    "    Rule('$BinOp', 'minus', '-'),\n",
    "    Rule('$BinOp', 'times', '*'),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For *compositional* rules, the semantic attachments are functions which specify how to construct the semantics of the parent from the semantics of the children.  We'll define these functions using Python's `lambda` syntax, and we'll establish the convention that these lambda functions always have a single parameter called `sems`, which will contain a list of the semantic representations of the children on the RHS of the rule.\n",
    "\n",
    "For example, consider the rule which specifies how to combine a unary operator with its argument.  We can define its semantic attachment like this:\n",
    "\n",
    "    Rule('$E', '$UnOp $E', lambda sems: (sems[0], sems[1]))\n",
    "\n",
    "Now, `sems[0]` refers to the semantics of the child `$UnOp`,\n",
    "and `sems[1]` refers to the semantics of the child `$E`.\n",
    "So this semantic attachment says: take the semantics of the child `$UnOp` and the semantics of the child `$E`, form a pair from them, and return that pair as the semantics for the parent `$E`.\n",
    "\n",
    "For the other two compositional rules — the ones involving binary operators — things are complicated by binarization.  Recall that *before* binarization, we had a single rule, for which we could easily specify a semantic attachment:\n",
    "\n",
    "    Rule('$E', '$E $BinOp $E', lambda sems: (sems[1], sems[0], sems[2]))\n",
    "\n",
    "Note the order of the tuple elements here: first we have `sems[1]`, which refers to the semantics of the child `$BinOp`, and then we have `sems[0]` and `sems[2]`, which refer to the semantics of the child `$E`s.\n",
    "\n",
    "However, *after* binarization, we need to break our semantic construction into stages.  First we combine the semantics of the left child `$E` with the semantics of `$BinOp`, forming a semantic representation for `$EBO` which is an \"incomplete\" tuple:\n",
    "\n",
    "    Rule('$EBO', '$E $BinOp', lambda sems: (sems[1], sems[0]))\n",
    "\n",
    "This semantic representation is incomplete in the sense that it combines a binary operator with a single argument.  (This is a form of [currying][].)\n",
    "\n",
    "  [currying]: http://en.wikipedia.org/wiki/Currying\n",
    "\n",
    "Then we follow through by combining the \"incomplete\" semantics for `$EBO` with the semantics for the right child `$E` to yield the semantic representation for the parent `$E`:\n",
    "\n",
    "    Rule('$E', '$EBO $E', lambda sems: (sems[0][0], sems[0][1], sems[1]))\n",
    "\n",
    "Putting everything together, we get:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "compositional_rules = [\n",
    "    Rule('$E', '$UnOp $E', lambda sems: (sems[0], sems[1])),\n",
    "    Rule('$EBO', '$E $BinOp', lambda sems: (sems[1], sems[0])),\n",
    "    Rule('$E', '$EBO $E', lambda sems: (sems[0][0], sems[0][1], sems[1])),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, these lambda functions tell us *how* to construct the semantics for the parent, given the semantics for the children.  But *when* and *where* do these functions actually get invoked?  There needs to be a function that constructs the semantics for a parse.  Here it is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from types import FunctionType\n",
    "\n",
    "def compute_semantics(parse):\n",
    "    if is_lexical(parse.rule) or not isinstance(parse.rule.sem, FunctionType):\n",
    "        return parse.rule.sem\n",
    "    else:\n",
    "        return parse.rule.sem([child.semantics for child in parse.children])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may recall that `compute_semantics()` was invoked in the constructor for `Parse` shown above.  Thus, SippyCup performs semantic construction \"eagerly\", that is, during parsing.  It's worth noting that this is a design choice — it would also be possible to make semantic construction a separate phase which occurs only after parsing is complete.\n",
    "\n",
    "At this point, we should have all the pieces we need to do semantic parsing.  Let's test that by parsing \"two times two plus three\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created grammar with 11 rules.\n",
      "\n",
      "($E ($EBO ($E two) ($BinOp times)) ($E ($EBO ($E two) ($BinOp plus)) ($E three)))\n",
      "('*', 2, ('+', 2, 3))\n",
      "\n",
      "($E ($EBO ($E ($EBO ($E two) ($BinOp times)) ($E two)) ($BinOp plus)) ($E three))\n",
      "('+', ('*', 2, 2), 3)\n"
     ]
    }
   ],
   "source": [
    "arithmetic_grammar = Grammar(arithmetic_rules())\n",
    "parses = parse_input(arithmetic_grammar, \"two times two plus three\")\n",
    "for parse in parses:\n",
    "    print()\n",
    "    print(parse)\n",
    "    print(parse.semantics)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, it looks like it's working!\n",
    "\n",
    "Next we'd like to evaluate the performance of our semantic grammar on our whole dataset.  The SippyCup codebase includes a number of helper functions (in [`experiment.py`](./experiment.py)) to facilitate empirical evaluations.  But since the code isn't very interesting, we won't reproduce it here — we'll just import it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created grammar with 11 rules.\n",
      "================================================================================\n",
      "Evaluating on 17 examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              one plus one\n",
      "target semantics                   ('+', 1, 1)\n",
      "target denotation                  2\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 1, 1)\n",
      "               denotation      +   2\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              one plus two\n",
      "target semantics                   ('+', 1, 2)\n",
      "target denotation                  3\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 1, 2)\n",
      "               denotation      +   3\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              one plus three\n",
      "target semantics                   ('+', 1, 3)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 1, 3)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two plus two\n",
      "target semantics                   ('+', 2, 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 2, 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two plus three\n",
      "target semantics                   ('+', 2, 3)\n",
      "target denotation                  5\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 2, 3)\n",
      "               denotation      +   5\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus one\n",
      "target semantics                   ('+', 3, 1)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 3, 1)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus minus two\n",
      "target semantics                   ('+', 3, ('~', 2))\n",
      "target denotation                  1\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 3, ('~', 2))\n",
      "               denotation      +   1\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two plus two\n",
      "target semantics                   ('+', 2, 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 2, 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three minus two\n",
      "target semantics                   ('-', 3, 2)\n",
      "target denotation                  1\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('-', 3, 2)\n",
      "               denotation      +   1\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              minus three minus two\n",
      "target semantics                   ('-', ('~', 3), 2)\n",
      "target denotation                  -5\n",
      "\n",
      "semantics accuracy                 0\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                0\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   2\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       -   ('~', ('-', 3, 2))\n",
      "               denotation      -   -1\n",
      "1      0.000   semantics       +   ('-', ('~', 3), 2)\n",
      "               denotation      +   -5\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two times two\n",
      "target semantics                   ('*', 2, 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('*', 2, 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two times three\n",
      "target semantics                   ('*', 2, 3)\n",
      "target denotation                  6\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('*', 2, 3)\n",
      "               denotation      +   6\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus three minus two\n",
      "target semantics                   ('-', ('+', 3, 3), 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 0\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   2\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       -   ('+', 3, ('-', 3, 2))\n",
      "               denotation      +   4\n",
      "1      0.000   semantics       +   ('-', ('+', 3, 3), 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              minus three\n",
      "target semantics                   ('~', 3)\n",
      "target denotation                  -3\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('~', 3)\n",
      "               denotation      +   -3\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus two\n",
      "target semantics                   ('+', 3, 2)\n",
      "target denotation                  5\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 3, 2)\n",
      "               denotation      +   5\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two times two plus three\n",
      "target semantics                   ('+', ('*', 2, 2), 3)\n",
      "target denotation                  7\n",
      "\n",
      "semantics accuracy                 0\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                0\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   2\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       -   ('*', 2, ('+', 2, 3))\n",
      "               denotation      -   10\n",
      "1      0.000   semantics       +   ('+', ('*', 2, 2), 3)\n",
      "               denotation      +   7\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              minus four\n",
      "target semantics                   ('~', 4)\n",
      "target denotation                  -4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('~', 4)\n",
      "               denotation      +   -4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 17 examples:\n",
      "\n",
      "semantics accuracy                 0.824\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.882\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.176\n",
      "spurious ambiguity                 0.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from experiment import evaluate_grammar\n",
    "\n",
    "arithmetic_grammar = Grammar(arithmetic_rules())\n",
    "evaluate_grammar(grammar=arithmetic_grammar, executor=execute, examples=arithmetic_examples)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you look at the bottom of the output, you see that we report the mean values of several evaluation metrics over the 17 examples in the dataset.  (Evaluation metrics are defined in [metrics.py](metrics.py).)  The first two are particularly significant at this point:\n",
    "\n",
    "- The \"semantics accuracy\" metric shows how often the semantics of the parse *at position 0* matched the target semantics in the example.  The result is 0.824, or 14/17.  In other words, there were three examples where the parse at position 0 was *not* correct.\n",
    "- The \"semantics oracle accuracy\" metric shows how often the semantics of *any* parse matched the target semantics in the example.  The result is 1.000, or 17/17.  In other words, in every example we produced some correct parse.\n",
    "\n",
    "The gap between accuracy and oracle accuracy represents an opportunity.  If we had some way of ranking candidate parses so that correct parses were likely to appear higher in the list, then we could bring accuracy closer to oracle accuracy.  (The \"oracle\"  in question is one that magically knows the optimal ranking of candidate parses.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scoring candidate parses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far, we've seen only a couple of cases where the parser found more than one parse for a given input.  But in richer domains, with more complex grammars, it's not unusual to find tens, hundreds, or even thousands of parses for some inputs.  However, the list of candidate parses returned by `parse_input()` appears in arbitrary order.  The first parse is not necessarily the best, and the best parse is not necessarily the first.  Therefore, we'd like to have some way of ranking the candidates, so that more plausible interpretations appear earlier in the list.\n",
    "\n",
    "Consider the example \"`two times two plus three`\".  Because of syntactic ambiguity, there are two possible interpretations, according to whether we perform multiplication first (in accordance with the standard [order of operations][]) or addition first.  Our parser duly produces both parses, but it happens to produce the wrong parse (the one with denotation 10) first, and the right parse (with denotation 7) second.  So this example counts as a loss for the accuracy metric, which only considers the first parse.\n",
    "\n",
    "  [order of operations]: http://en.wikipedia.org/wiki/Order_of_operations\n",
    "\n",
    "An easy way to rank candidate parses is with a linear scoring function.  (This approach will be very familiar if you've had any exposure to machine learning.)  The idea is that we define a vector of [feature functions][], each of which takes a parse as input and returns as output a real number which encodes some salient characteristic of the parse.  We then define a corresponding vector of real-valued weights (one for each feature), and we compute the score for a parse as the [inner product][] of the weight vector and the feature vector.  If $p$ is a parse, $w$ is the weight vector, and $\\phi$ is the vector of feature functions, we can write this as:\n",
    "\n",
    "  [feature functions]: http://en.wikipedia.org/wiki/Feature_(machine_learning)\n",
    "  [inner product]: http://en.wikipedia.org/wiki/Dot_product\n",
    "\n",
    "$ score(p) = \\sum_i w_i \\cdot \\phi_i(p) $\n",
    "<!-- TODO: center this? -->\n",
    "\n",
    "Finally, we sort the candidate parses by score, so that the highest-scoring parses appear first.\n",
    "\n",
    "We now have two problems:\n",
    "\n",
    "  1. **Feature engineering**: defining features which help to discriminate good parses from bad.\n",
    "  2. **Weight learning**: deciding what weight to assign to each feature.\n",
    "  \n",
    "The rest of this section will focus on feature engineering; we'll turn to weight learning in the next section.\n",
    "\n",
    "In the academic literature on semantic parsing, the default starting point for feature engineering is usually with *rule features*.   There is one such feature for each rule in the grammar, and its value for a given parse simply indicates how many times the rule was used in the parse.  We can implement rule features in Python like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def rule_features(parse):\n",
    "    \"\"\"\n",
    "    Returns a map from (string representations of) rules to how often they were\n",
    "    used in the given parse.\n",
    "    \"\"\"\n",
    "    def collect_rule_features(parse, features):\n",
    "        feature = str(parse.rule)\n",
    "        features[feature] += 1.0\n",
    "        for child in parse.children:\n",
    "            if isinstance(child, Parse):\n",
    "                collect_rule_features(child, features)\n",
    "    features = defaultdict(float)\n",
    "    collect_rule_features(parse, features)\n",
    "    return features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, here are the rule features for `\"two times two\"`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       1   Rule('$E', '$EBO $E', <function <lambda> at 0x1043bac80>)\n",
      "       1   Rule('$EBO', '$E $BinOp', <function <lambda> at 0x1043bad08>)\n",
      "       2   Rule('$E', 'two', 2)\n",
      "       1   Rule('$BinOp', 'times', '*')\n"
     ]
    }
   ],
   "source": [
    "parses = parse_input(arithmetic_grammar, \"two times two\")\n",
    "for feature, value in rule_features(parses[0]).items():\n",
    "    print('%8g   %s' % (value, feature))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the rule feature for `Rule('$E', 'two', 2)` has value 2, because that rule was used twice in the parse.\n",
    "\n",
    "Rule features are often quite effective in discriminating good parses from bad.  In cases of lexical ambiguity, rule features can help to identify the preferred interpretation, by assigning a higher weight to one lexical rule with the given RHS than to another.  Likewise, in cases of syntactic ambiguity, rule features can help to identify the more plausible construction.\n",
    "\n",
    "However, rule features won't help us distinguish between the two candidate parses of \"two times two plus three\", because the two parses use exactly the same rules, only in a different order.  Here, let's prove it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of parses: 2\n",
      "Identical rule features? True\n"
     ]
    }
   ],
   "source": [
    "parses = parse_input(arithmetic_grammar, \"two times two plus three\")\n",
    "print('Number of parses:', len(parses))\n",
    "print('Identical rule features?', rule_features(parses[0]) == rule_features(parses[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to discriminate between the two candidate parses of \"two times two plus three\", we need features that explicitly represent operator precedence.  The following feature function will do the job."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def operator_precedence_features(parse):\n",
    "    \"\"\"\n",
    "    Traverses the arithmetic expression tree which forms the semantics of\n",
    "    the given parse and adds a feature (op1, op2) whenever op1 appears\n",
    "    lower in the tree than (i.e. with higher precedence than) than op2.\n",
    "    \"\"\"\n",
    "    def collect_features(semantics, features):\n",
    "        if isinstance(semantics, tuple):\n",
    "            for child in semantics[1:]:\n",
    "                collect_features(child, features)\n",
    "                if isinstance(child, tuple) and child[0] != semantics[0]:\n",
    "                    features[(child[0], semantics[0])] += 1.0\n",
    "    features = defaultdict(float)\n",
    "    collect_features(parse.semantics, features)\n",
    "    return features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make sure it works properly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Semantics ('*', 2, ('+', 2, 3)) yields features {('+', '*'): 1.0}\n",
      "Semantics ('+', ('*', 2, 2), 3) yields features {('*', '+'): 1.0}\n"
     ]
    }
   ],
   "source": [
    "for parse in parses:\n",
    "    print('Semantics %s yields features %s' % (parse.semantics, dict(operator_precedence_features(parse))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks good.  Now we want to make sure that a parse with feature `('*', '+')` will get a higher score (all else being equal) than a parse with feature `('+', '*')`.  That's easy to arrange: we can just assign a weight of 1 to the former feature and a weight of -1 to the latter.  While we're at it, let's assign weights to a few other precedence features in accordance with the standard order of operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "weights = defaultdict(float)\n",
    "weights[('*', '+')] = 1.0\n",
    "weights[('*', '-')] = 1.0\n",
    "weights[('~', '+')] = 1.0\n",
    "weights[('~', '-')] = 1.0\n",
    "weights[('+', '*')] = -1.0\n",
    "weights[('-', '*')] = -1.0\n",
    "weights[('+', '~')] = -1.0\n",
    "weights[('-', '~')] = -1.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need a function that actually computes the score for a parse, given a feature function and a weight vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def score(parse=None, feature_fn=None, weights=None):\n",
    "    \"\"\"Returns the inner product of feature_fn(parse) and weights.\"\"\"\n",
    "    return sum(weights[feature] * value for feature, value in feature_fn(parse).items())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's verify that our preferred interpretation for \"two times two plus three\" gets a higher score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Semantics ('*', 2, ('+', 2, 3)) gets score -1.0\n",
      "Semantics ('+', ('*', 2, 2), 3) gets score  1.0\n"
     ]
    }
   ],
   "source": [
    "for parse in parses:\n",
    "    print('Semantics %s gets score %4.1f' % (parse.semantics, score(parse, operator_precedence_features, weights)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, it works.\n",
    "\n",
    "Now that we have a grammar, scoring, and an executor, it will be convenient to tie all these pieces together in a class called `Model`, which can take an input and generate a ranked list of parses with scores, semantics, and denotations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Model:\n",
    "    def __init__(self,\n",
    "                 grammar=None,\n",
    "                 feature_fn=lambda parse: defaultdict(float),\n",
    "                 weights=defaultdict(float),\n",
    "                 executor=None):\n",
    "        self.grammar = grammar\n",
    "        self.feature_fn = feature_fn\n",
    "        self.weights = weights\n",
    "        self.executor = executor\n",
    "\n",
    "    def parse_input(self, input):\n",
    "        parses = self.grammar.parse_input(input)\n",
    "        for parse in parses:\n",
    "            if self.executor:\n",
    "                parse.denotation = self.executor(parse.semantics)\n",
    "            parse.score = score(parse, self.feature_fn, self.weights)\n",
    "        parses = sorted(parses, key=lambda parse: parse.score, reverse=True)\n",
    "        return parses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's redo the evaluation we ran at the end of the last section, to demonstrate that we've achieved a gain from introducing scoring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "================================================================================\n",
      "Evaluating on 17 examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              one plus one\n",
      "target semantics                   ('+', 1, 1)\n",
      "target denotation                  2\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 1, 1)\n",
      "               denotation      +   2\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              one plus two\n",
      "target semantics                   ('+', 1, 2)\n",
      "target denotation                  3\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 1, 2)\n",
      "               denotation      +   3\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              one plus three\n",
      "target semantics                   ('+', 1, 3)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 1, 3)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two plus two\n",
      "target semantics                   ('+', 2, 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 2, 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two plus three\n",
      "target semantics                   ('+', 2, 3)\n",
      "target denotation                  5\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 2, 3)\n",
      "               denotation      +   5\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus one\n",
      "target semantics                   ('+', 3, 1)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 3, 1)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus minus two\n",
      "target semantics                   ('+', 3, ('~', 2))\n",
      "target denotation                  1\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      1.000   semantics       +   ('+', 3, ('~', 2))\n",
      "               denotation      +   1\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two plus two\n",
      "target semantics                   ('+', 2, 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 2, 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three minus two\n",
      "target semantics                   ('-', 3, 2)\n",
      "target denotation                  1\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('-', 3, 2)\n",
      "               denotation      +   1\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              minus three minus two\n",
      "target semantics                   ('-', ('~', 3), 2)\n",
      "target denotation                  -5\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   2\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      1.000   semantics       +   ('-', ('~', 3), 2)\n",
      "               denotation      +   -5\n",
      "1     -1.000   semantics       -   ('~', ('-', 3, 2))\n",
      "               denotation      -   -1\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two times two\n",
      "target semantics                   ('*', 2, 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('*', 2, 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two times three\n",
      "target semantics                   ('*', 2, 3)\n",
      "target denotation                  6\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('*', 2, 3)\n",
      "               denotation      +   6\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus three minus two\n",
      "target semantics                   ('-', ('+', 3, 3), 2)\n",
      "target denotation                  4\n",
      "\n",
      "semantics accuracy                 0\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   2\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       -   ('+', 3, ('-', 3, 2))\n",
      "               denotation      +   4\n",
      "1      0.000   semantics       +   ('-', ('+', 3, 3), 2)\n",
      "               denotation      +   4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              minus three\n",
      "target semantics                   ('~', 3)\n",
      "target denotation                  -3\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('~', 3)\n",
      "               denotation      +   -3\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              three plus two\n",
      "target semantics                   ('+', 3, 2)\n",
      "target denotation                  5\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('+', 3, 2)\n",
      "               denotation      +   5\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              two times two plus three\n",
      "target semantics                   ('+', ('*', 2, 2), 3)\n",
      "target denotation                  7\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   2\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      1.000   semantics       +   ('+', ('*', 2, 2), 3)\n",
      "               denotation      +   7\n",
      "1     -1.000   semantics       -   ('*', 2, ('+', 2, 3))\n",
      "               denotation      -   10\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "input                              minus four\n",
      "target semantics                   ('~', 4)\n",
      "target denotation                  -4\n",
      "\n",
      "semantics accuracy                 1\n",
      "semantics oracle accuracy          1\n",
      "denotation accuracy                1\n",
      "denotation oracle accuracy         1\n",
      "number of parses                   1\n",
      "spurious ambiguity                 0\n",
      "\n",
      "0      0.000   semantics       +   ('~', 4)\n",
      "               denotation      +   -4\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 17 examples:\n",
      "\n",
      "semantics accuracy                 0.941\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                1.000\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.176\n",
      "spurious ambiguity                 0.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from experiment import evaluate_model\n",
    "\n",
    "arithmetic_model = Model(grammar=arithmetic_grammar,\n",
    "                         feature_fn=operator_precedence_features,\n",
    "                         weights=weights,\n",
    "                         executor=execute)\n",
    "evaluate_model(model=arithmetic_model, examples=arithmetic_examples)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you look at the bottom of the output, you'll see that our semantics accuracy has increased from 0.824 (or 14 of 17) to 0.941 (or 16 of 17).  Hooray, scoring works!  In particular, our operator precedence features now allow us to correctly rank the alternate parses for \"minus three minus two\" and \"two times two minus three\".\n",
    "\n",
    "The remaining error is on \"three plus three minus two\".  Note that in the standard order of operations, operators with same precedence level (such as addition and subtraction) are evaluated left-to-right.  Accordingly, the target semantics performs the addition first.  However, the parse at position 0 performs the subtraction first.  In this case, both parses yield the same denotation, so you might think that this mistake doesn't much matter.  But that's not true in general: if the example were instead \"three minus three plus two\", the denotation would depend on the order of operations.  In the [exercises](#arithmetic-exercises) at the end of this unit, we'll ask you to introduce new features to address this problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learning the scoring model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the previous section, we set the weights of our scoring model \"by hand\".  And it was easy to do so, because the model uses just a handful of features.  Moreover, there was no question about what weights to choose: the sign of each weight was determined by the standard order of operations, and the magnitudes were all the same.\n",
    "\n",
    "In more realistic applications, however, things are often more complicated.  Scoring models can contain hundreds or thousands of features, too many to set by hand.  And, perhaps surprisingly, it's not always obvious whether the weight of a particular feature should be positive or negative, let alone what its magnitude should be.\n",
    "\n",
    "Rather than setting weights by hand, we'd like learn the weights automatically from training data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Learning with stochastic gradient descent (SGD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(TODO ... flesh out this section.  Until this section is fleshed out, please refer to [Liang & Potts 2015][], which describes the application of SGD to semantic parsing with great clarity.  You may also find it useful to examine the [demonstration code][] published as a companion to that paper.  The code here is superficially different but fundamentally the same.)\n",
    "\n",
    "  [Liang & Potts 2015]: http://www.annualreviews.org/doi/pdf/10.1146/annurev-linguist-030514-125312\n",
    "  [demonstration code]: https://github.com/cgpotts/annualreview-complearning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def latent_sgd(model=None, examples=[], training_metric=None, T=10, eta=0.1, seed=None):\n",
    "    print('Running SGD learning on %d examples with training metric: %s' % (\n",
    "        len(examples), training_metric.name()))\n",
    "    if seed:\n",
    "        print('random.seed(%d)' % seed)\n",
    "        random.seed(seed)\n",
    "    model = clone_model(model)\n",
    "    for t in range(T):\n",
    "        random.shuffle(examples)\n",
    "        num_correct = 0\n",
    "        for example in examples:\n",
    "            # Parse input with current weights.\n",
    "            parses = model.parse_input(example.input)\n",
    "            # Get the highest-scoring \"good\" parse among the candidate parses.\n",
    "            good_parses = [p for p in parses if training_metric.evaluate(example, [p])]\n",
    "            if good_parses:\n",
    "                target_parse = good_parses[0]\n",
    "                # Get all (score, parse) pairs.\n",
    "                scores = [(p.score + cost(target_parse, p), p) for p in parses]\n",
    "                # Get the maximal score.\n",
    "                max_score = sorted(scores)[-1][0]\n",
    "                # Get all the candidates with the max score and choose one randomly.\n",
    "                predicted_parse = random.choice([p for s, p in scores if s == max_score])\n",
    "                if training_metric.evaluate(example, [predicted_parse]):\n",
    "                    num_correct += 1\n",
    "                update_weights(model, target_parse, predicted_parse, eta)\n",
    "        print('SGD iteration %d: train accuracy: %.3f' % (t, 1.0 * num_correct / len(examples)))\n",
    "    print_weights(model.weights)\n",
    "    return model\n",
    "\n",
    "def cost(parse_1, parse_2):\n",
    "    return 0.0 if parse_1 == parse_2 else 1.0\n",
    "\n",
    "def clone_model(model):\n",
    "    return Model(grammar=model.grammar,\n",
    "                 feature_fn=model.feature_fn,\n",
    "                 weights=defaultdict(float),  # Zero the weights.\n",
    "                 executor=model.executor)\n",
    "\n",
    "def update_weights(model, target_parse, predicted_parse, eta):\n",
    "    target_features = model.feature_fn(target_parse)\n",
    "    predicted_features = model.feature_fn(predicted_parse)\n",
    "    for f in set(target_features.keys() + predicted_features.keys()):\n",
    "        update = target_features[f] - predicted_features[f]\n",
    "        if update != 0.0:\n",
    "            # print 'update %g + %g * %g = %g\\t%s' % (\n",
    "            #     model.weights[f], eta, update, model.weights[f] + eta * update, f)\n",
    "            model.weights[f] += eta * update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Learning from semantics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's put `latent_sgd()` to the test, by using it to learn weights for our arithmetic model.\n",
    "We'll divide our 17 arithmetic examples into 13 training examples and 4 test examples.\n",
    "Then, we'll use the utility function `train_test()`, defined in [`experiment.py`](./experiment.py), which:\n",
    "\n",
    "- evaluates the *current* model on both the training examples and the test examples\n",
    "- trains the model on the training examples, using `latent_sgd()`\n",
    "- reports the learned weights\n",
    "- evaluates the *trained* model on both the training examples and the test examples\n",
    "\n",
    "Note that `train_test()` has a parameter called `training_metric`, which is passed through to the `latent_sgd()` parameter of the same name.  To begin with, we'll use the `SemanticsAccuracyMetric` as the training metric: thus, a parse will count as correct iff its semantic yield matches the target semantics in the example.  Here we go:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 training examples, 4 test examples\n",
      "================================================================================\n",
      "Evaluating on 13 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 13 examples:\n",
      "\n",
      "semantics accuracy                 0.846\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.923\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.154\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "semantics accuracy                 0.750\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.750\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.250\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Running SGD learning on 13 examples with training metric: semantics accuracy\n",
      "\n",
      "random.seed(1)\n",
      "SGD iteration 0: train accuracy: 0.846\n",
      "SGD iteration 1: train accuracy: 0.846\n",
      "SGD iteration 2: train accuracy: 0.846\n",
      "SGD iteration 3: train accuracy: 0.846\n",
      "SGD iteration 4: train accuracy: 0.846\n",
      "SGD iteration 5: train accuracy: 0.846\n",
      "SGD iteration 6: train accuracy: 1.000\n",
      "SGD iteration 7: train accuracy: 1.000\n",
      "SGD iteration 8: train accuracy: 1.000\n",
      "SGD iteration 9: train accuracy: 1.000\n",
      "\n",
      "Feature weights:\n",
      "     0.6\t('~', '-')\n",
      "     0.6\t('+', '-')\n",
      "    -0.6\t('-', '~')\n",
      "    -0.6\t('-', '+')\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 13 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 13 examples:\n",
      "\n",
      "semantics accuracy                 1.000\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                1.000\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.154\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "semantics accuracy                 0.750\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.750\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.250\n",
      "spurious ambiguity                 0.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from experiment import train_test\n",
    "from metrics import SemanticsAccuracyMetric\n",
    "\n",
    "train_test(model=arithmetic_model,\n",
    "           train_examples=arithmetic_examples[:13],\n",
    "           test_examples=arithmetic_examples[13:],\n",
    "           training_metric=SemanticsAccuracyMetric(),\n",
    "           seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that, while training accuracy increased from 0.846 (11 of 13 correct) to 1.000 (all 13 correct), test accuracy remained stuck at 0.750 (3 of 4 correct).  We seem to have learned *something* from the training data, but whatever we learned did not generalize to the test data.  In fact, if we look at the learned features, we can see exactly what we learned from the training data: that '~' should take precedence over '-' (which is correct, in the sense that it accords with the standard order of operations), and that '+' should take precedence over '-' (which is not correct, in general).  The model learned these specific preferences because the two errors it was making on the training data involved these two precedence pairs.\n",
    "\n",
    "However, the one error we're making on the test data involves a different precedence pair.  If you add the argument `print_examples=True` to `train_test()`, you can see which example we're getting wrong: it's `\"two times two plus three\"`.  In order to get this example right, we need to know that `*` should take precedence over `+`.  But none of the examples in the training data involved this precedence pair, so we haven't learned that.\n",
    "\n",
    "Of course, this failure to improve test accuracy doesn't reflect any problem with `latent_sgd()`.\n",
    "It's merely a consequence of the extremely small size of our training dataset.  With so few training examples, it's not surprising that a test example hinges on a feature not seen in training.  Going forward, we'll strive for larger datasets which are less subject to this kind of sampling noise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Learning from denotations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's clear that we need larger datasets, with more training examples.  But as we noted [above](#arithmetic-example-data), annotating examples with target semantics can be slow, expensive, and error-prone, and may require expert knowledge.  However, annotating examples with target *denotations* can often be faster, cheaper, and more reliable.\n",
    "\n",
    "The arithmetic domain illustrates this nicely.  Writing down the target semantics for `\"minus three minus two\"` (namely, `('-', ('~', 3), 2)`) is a tedious chore that most people probably could not perform reliably.  You need to understand Lisp-y prefix notation.  You need to remember to use the funny `'~'`, instead of the more natural `'-'`, for unary `\"minus\"`.  You need to remember to quote the operators.  And you need to get the order of operations right.\n",
    "\n",
    "By contrast, writing down the target denotation (namely, `-5`) is easy as pie.  The only thing you really need to think about is the order of operations, which most people are capable of mastering.  So if you're asking only for denotations, rather than semantics, you can get more annotations, faster, cheaper, and more reliably, from ordinary people.\n",
    "\n",
    "One of the principal contributions of [Liang et al. 2011][] was to show that it is possible to learn scoring models for semantic parsing using only target denotations, rather than target semantics, as the source of supervision.  The central idea is presented with admirable clarity in [Liang & Potts 2015].\n",
    "\n",
    "  [Liang et al. 2011]: http://www.cs.berkeley.edu/~jordan/papers/liang-jordan-klein-acl2011.pdf\n",
    "  [Liang & Potts 2015]: http://www.annualreviews.org/doi/pdf/10.1146/annurev-linguist-030514-125312\n",
    "\n",
    "In SippyCup, we can change the source of supervision from semantics to denotations simply by changing the training metric from `SemanticsAccuracyMetric` to `DenotationAccuracyMetric`.  With this change, a parse will count as correct iff the denotation of its semantic yield matches the target denotation in the example.\n",
    "\n",
    "Let's begin by repeating the experiment we did a moment ago, but switching to denotations as the source of supervision:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 training examples, 4 test examples\n",
      "================================================================================\n",
      "Evaluating on 13 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 13 examples:\n",
      "\n",
      "semantics accuracy                 0.846\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.923\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.154\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "semantics accuracy                 0.750\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.750\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.250\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Running SGD learning on 13 examples with training metric: denotation accuracy\n",
      "\n",
      "random.seed(1)\n",
      "SGD iteration 0: train accuracy: 0.923\n",
      "SGD iteration 1: train accuracy: 0.923\n",
      "SGD iteration 2: train accuracy: 0.923\n",
      "SGD iteration 3: train accuracy: 0.923\n",
      "SGD iteration 4: train accuracy: 0.923\n",
      "SGD iteration 5: train accuracy: 0.923\n",
      "SGD iteration 6: train accuracy: 1.000\n",
      "SGD iteration 7: train accuracy: 1.000\n",
      "SGD iteration 8: train accuracy: 1.000\n",
      "SGD iteration 9: train accuracy: 1.000\n",
      "\n",
      "Feature weights:\n",
      "     0.6\t('~', '-')\n",
      "     0.6\t('-', '+')\n",
      "    -0.6\t('-', '~')\n",
      "    -0.6\t('+', '-')\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 13 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 13 examples:\n",
      "\n",
      "semantics accuracy                 0.923\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                1.000\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.154\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "semantics accuracy                 0.750\n",
      "semantics oracle accuracy          1.000\n",
      "denotation accuracy                0.750\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.250\n",
      "spurious ambiguity                 0.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from metrics import DenotationAccuracyMetric\n",
    "\n",
    "train_test(model=arithmetic_model,\n",
    "           train_examples=arithmetic_examples[:13],\n",
    "           test_examples=arithmetic_examples[13:],\n",
    "           training_metric=DenotationAccuracyMetric(),\n",
    "           seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we're learning from denotations, the semantics accuracy on the training data did not reach 1.000, as it did before.  One of the [exercises](#arithmetic-exercises) will ask you to investigate why.  However, the denotation accuracy did reach 1.000.\n",
    "\n",
    "To no one's astonishment, performance on the test data did not budge.  As we saw earlier, the sole error on a test example depends on a feature which is not observed in the training data.  Learning from denotations does not solve that problem directly.  However, it opens the door to obtaining larger datasets for training, which may help.\n",
    "\n",
    "The file [`arithmetic.py`](./arithmetic.py) contains a set of 100 \"development\" examples for the arithmetic domain.  These examples are annotated only with denotations, not with semantics.  100 examples is still not huge, but the arithmetic domain is simple enough that it should suffice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 training examples, 4 test examples\n",
      "================================================================================\n",
      "Evaluating on 100 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 100 examples:\n",
      "\n",
      "denotation accuracy                0.640\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   4.520\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "denotation accuracy                0.750\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.250\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Running SGD learning on 100 examples with training metric: denotation accuracy\n",
      "\n",
      "random.seed(1)\n",
      "SGD iteration 0: train accuracy: 0.670\n",
      "SGD iteration 1: train accuracy: 0.850\n",
      "SGD iteration 2: train accuracy: 0.890\n",
      "SGD iteration 3: train accuracy: 0.900\n",
      "SGD iteration 4: train accuracy: 0.900\n",
      "SGD iteration 5: train accuracy: 0.910\n",
      "SGD iteration 6: train accuracy: 0.910\n",
      "SGD iteration 7: train accuracy: 0.930\n",
      "SGD iteration 8: train accuracy: 0.930\n",
      "SGD iteration 9: train accuracy: 0.930\n",
      "\n",
      "Feature weights:\n",
      "     1.2\t('-', '+')\n",
      "     1.1\t('*', '~')\n",
      "     1.1\t('*', '+')\n",
      "     0.7\t('~', '-')\n",
      "     0.5\t('*', '-')\n",
      "     0.0\t('~', '+')\n",
      "    -0.5\t('+', '-')\n",
      "    -1.0\t('-', '*')\n",
      "    -1.1\t('~', '*')\n",
      "    -1.1\t('-', '~')\n",
      "    -1.2\t('+', '~')\n",
      "    -1.2\t('+', '*')\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 100 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 100 examples:\n",
      "\n",
      "denotation accuracy                0.930\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   4.520\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "denotation accuracy                1.000\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   1.250\n",
      "spurious ambiguity                 0.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from arithmetic import arithmetic_dev_examples\n",
    "from metrics import denotation_match_metrics\n",
    "\n",
    "train_test(model=arithmetic_model,\n",
    "           train_examples=arithmetic_dev_examples,\n",
    "           test_examples=arithmetic_examples[13:],\n",
    "           metrics=denotation_match_metrics(),\n",
    "           training_metric=DenotationAccuracyMetric(),\n",
    "           seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that denotation accuracy on the test examples now reaches 1.000 after training.  The sole error is corrected, because the larger training dataset affords ample opportunity to learn that `*` should take precedence over `+`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inducing the lexicon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'd like to automate the process of building a semantic parsing model as much as possible.  Ideally, we'd start from training examples annotated with denotations, run one command, and get back a fully-baked semantic parsing model.  This would make it vastly easier to build models for new domains or in new languages.\n",
    "\n",
    "The weight learning introduced in the previous section brings us one step closer to that goal.  It makes it possible to leverage machine learning, rather than human expertise, in constructing a scoring model for ranking candidate parses.\n",
    "\n",
    "In truth, however, we're still quite far from fully automated model construction.  As things stand, there's one big piece that remains completely manual: grammar engineering.  In the arithmetic domain, we had to write rules that specify that the token `\"one\"` corresponds to the semantic representation `1`, that the token `\"times\"` corresponds to the semantic representation `*`, and so on.  Because the arithmetic domain is simple and the grammar is small, this wasn't especially cumbersome.  But in more realistic domains, grammars can become very large, with thousands of rules.  The burden of manual grammar engineering then becomes a major impediment to rapid progress.\n",
    "\n",
    "Consequently, a major theme in academic research on semantic parsing (and, indeed, syntactic parsing as well) has been [grammar induction][], which means automatically inducing the rules of the grammar from data.  This is a big topic, one that we will touch on only lightly in SippyCup.\n",
    "\n",
    "  [grammar induction]: http://en.wikipedia.org/wiki/Grammar_induction\n",
    "  \n",
    "One approach to inducing the rules of the grammar, explored in [Zettlemoyer & Collins 2005][], reduces the problem to conventional weight learning:\n",
    "\n",
    "- generate all rules possible under certain constraints,\n",
    "- build a linear scoring model with rule features,\n",
    "- use SGD training, as in the previous section, to learn weights for each rule, and then\n",
    "- (optional) prune all but the highest-weight rules\n",
    "\n",
    "  [Zettlemoyer & Collins 2005]: http://people.csail.mit.edu/lsz/papers/zc-uai05.pdf\n",
    "  \n",
    "This strategy has usually been applied only to *lexical* rules, with compositional rules still defined manually.  What does it mean to generate all lexical rules possible?  The basic idea is to build rules from pieces that we find in the training examples.  To generate a lexical rule, we:\n",
    "\n",
    "- choose the LHS from the set of categories which appear in the compositional rules,\n",
    "- choose the RHS from the set of tokens which appear in the example inputs, and\n",
    "- choose the semantics from the set of fragments which appear in the example semantics.\n",
    "\n",
    "This generative process is usually constrained in some way, and much depends on the specific constraints.  If we generate too few rules, we are unlikely to find the ones we need for parsing, and we'll see oracle accuracy stuck near zero.  But if we generate too many, our grammar will be very large, parsing will be exceedingly slow, and training will grind to a halt.\n",
    "\n",
    "One way of constraining the generative process, suggested in [Liang & Potts 2015][], is to assume that we know the proper syntactic category for each token and each semantic fragment, but not the proper mapping between tokens and semantic fragments within the same syntactic category.  In the arithmetic domain, this would mean knowing that the tokens `'plus'`, `'minus'`, and `'times`, and the semantic fragments `'+'`, `'-'`, and `'*'`, all belong to the syntactic category `$BinOp`, but without knowing that `'plus'` corresponds to `'+'`.\n",
    "\n",
    "  [Liang & Potts 2015]: http://www.annualreviews.org/doi/pdf/10.1146/annurev-linguist-030514-125312\n",
    "\n",
    "Let's test this out!  The following function expands a set of rules by generating lexical rules from the [Cartesian product][] of existing lexical tokens and semantic fragments for each category, thereby effective \"forgetting\" the proper mapping between them.\n",
    "\n",
    "  [Cartesian product]: http://en.wikipedia.org/wiki/Cartesian_product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cartesian_product_of_lexical_rules(rules):\n",
    "    \"\"\"\n",
    "    Expands the given collection of rules by iterating through all possible\n",
    "    pairs of existing lexical rules and adding a new rule which combines the RHS\n",
    "    of the first rule with the semantics of the second.\n",
    "    \"\"\"\n",
    "    lexical_rules = [rule for rule in rules if is_lexical(rule)]\n",
    "    expanded_rules = [rule for rule in rules if not is_lexical(rule)]\n",
    "    # Partition rules by lhs.\n",
    "    lexical_rules_by_lhs = defaultdict(list)\n",
    "    for rule in lexical_rules:\n",
    "        lexical_rules_by_lhs[rule.lhs].append(rule)\n",
    "    # In each partition, iterate through cross-product of lexical rules.\n",
    "    for lhs, rules in lexical_rules_by_lhs.items():\n",
    "        sems = set([rule.sem for rule in rules])\n",
    "        for rule, sem in product(rules, sems):\n",
    "            expanded_rules.append(Rule(rule.lhs, rule.rhs, sem))\n",
    "    return expanded_rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see what it looks like when we apply this to our current arithmetic rules."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expanded 11 arithmetic rules into 29 rules\n",
      "\n",
      "Rule('$E', '$UnOp $E', <function <lambda> at 0x1043abc80>)\n",
      "Rule('$EBO', '$E $BinOp', <function <lambda> at 0x1043bad08>)\n",
      "Rule('$E', '$EBO $E', <function <lambda> at 0x1043bac80>)\n",
      "Rule('$BinOp', 'plus', '+')\n",
      "Rule('$BinOp', 'plus', '*')\n",
      "Rule('$BinOp', 'plus', '-')\n",
      "Rule('$BinOp', 'minus', '+')\n",
      "Rule('$BinOp', 'minus', '*')\n",
      "Rule('$BinOp', 'minus', '-')\n",
      "Rule('$BinOp', 'times', '+')\n",
      "Rule('$BinOp', 'times', '*')\n",
      "Rule('$BinOp', 'times', '-')\n",
      "Rule('$E', 'one', 1)\n",
      "Rule('$E', 'one', 2)\n",
      "Rule('$E', 'one', 3)\n",
      "Rule('$E', 'one', 4)\n",
      "Rule('$E', 'two', 1)\n",
      "Rule('$E', 'two', 2)\n",
      "Rule('$E', 'two', 3)\n",
      "Rule('$E', 'two', 4)\n",
      "Rule('$E', 'three', 1)\n",
      "Rule('$E', 'three', 2)\n",
      "Rule('$E', 'three', 3)\n",
      "Rule('$E', 'three', 4)\n",
      "Rule('$E', 'four', 1)\n",
      "Rule('$E', 'four', 2)\n",
      "Rule('$E', 'four', 3)\n",
      "Rule('$E', 'four', 4)\n",
      "Rule('$UnOp', 'minus', '~')\n"
     ]
    }
   ],
   "source": [
    "original_arithmetic_rules = arithmetic_rules()\n",
    "expanded_arithmetic_rules = cartesian_product_of_lexical_rules(original_arithmetic_rules)\n",
    "print(\"Expanded %d arithmetic rules into %d rules\\n\" % (\n",
    "    len(original_arithmetic_rules), len(expanded_arithmetic_rules)))\n",
    "for rule in expanded_arithmetic_rules:\n",
    "    print(rule)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, the expanded rule set pairs every token with every semantic fragment, restricted by syntactic category.\n",
    "\n",
    "In our earlier learning experiments, we used the `operator_precedence_features()`.  But this approach to lexicon induction depends on using rule features, so let's create a feature function which generates both kinds of features:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def arithmetic_features(parse):\n",
    "    features = rule_features(parse)\n",
    "    features.update(operator_precedence_features(parse))\n",
    "    return features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, we're finally ready to run a `train_test()` experiment.  Let's create a model using the expanded rule set and both kinds of features.  Training is going to be a lot slower now, so let's use our original training dataset of 13 examples, and our usual test dataset of 4 examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created grammar with 29 rules.\n",
      "13 training examples, 4 test examples\n",
      "================================================================================\n",
      "Evaluating on 13 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 13 examples:\n",
      "\n",
      "denotation accuracy                0.077\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   136.615\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "denotation accuracy                0.000\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   302.000\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Running SGD learning on 13 examples with training metric: denotation accuracy\n",
      "\n",
      "random.seed(1)\n",
      "SGD iteration 0: train accuracy: 0.154\n",
      "SGD iteration 1: train accuracy: 0.077\n",
      "SGD iteration 2: train accuracy: 0.077\n",
      "SGD iteration 3: train accuracy: 0.154\n",
      "SGD iteration 4: train accuracy: 0.538\n",
      "SGD iteration 5: train accuracy: 0.692\n",
      "SGD iteration 6: train accuracy: 0.615\n",
      "SGD iteration 7: train accuracy: 0.923\n",
      "SGD iteration 8: train accuracy: 0.923\n",
      "SGD iteration 9: train accuracy: 0.846\n",
      "\n",
      "Feature weights:\n",
      "     1.0\t('+', '~')\n",
      "     0.9\tRule('$E', 'two', 2)\n",
      "     0.9\tRule('$E', 'three', 3)\n",
      "     0.9\tRule('$E', 'one', 1)\n",
      "     0.8\tRule('$BinOp', 'times', '*')\n",
      "     0.8\tRule('$BinOp', 'plus', '+')\n",
      "     0.8\t('-', '+')\n",
      "     0.4\tRule('$BinOp', 'minus', '-')\n",
      "    -0.1\t('~', '+')\n",
      "    -0.1\t('~', '*')\n",
      "    -0.1\t('+', '*')\n",
      "    -0.1\t('*', '+')\n",
      "    -0.2\tRule('$BinOp', 'minus', '*')\n",
      "    -0.2\tRule('$BinOp', 'minus', '+')\n",
      "    -0.3\tRule('$E', 'two', 4)\n",
      "    -0.3\tRule('$E', 'two', 3)\n",
      "    -0.3\tRule('$E', 'two', 1)\n",
      "    -0.3\tRule('$E', 'three', 4)\n",
      "    -0.3\tRule('$E', 'three', 2)\n",
      "    -0.3\tRule('$E', 'three', 1)\n",
      "    -0.3\tRule('$E', 'one', 4)\n",
      "    -0.3\tRule('$E', 'one', 3)\n",
      "    -0.3\tRule('$E', 'one', 2)\n",
      "    -0.4\tRule('$BinOp', 'times', '-')\n",
      "    -0.4\tRule('$BinOp', 'times', '+')\n",
      "    -0.4\tRule('$BinOp', 'plus', '-')\n",
      "    -0.4\tRule('$BinOp', 'plus', '*')\n",
      "    -0.4\t('~', '-')\n",
      "    -0.4\t('-', '~')\n",
      "    -0.4\t('+', '-')\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 13 train examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 13 examples:\n",
      "\n",
      "denotation accuracy                1.000\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   136.615\n",
      "spurious ambiguity                 0.000\n",
      "\n",
      "================================================================================\n",
      "Evaluating on 4 test examples\n",
      "\n",
      "--------------------------------------------------------------------------------\n",
      "Over 4 examples:\n",
      "\n",
      "denotation accuracy                0.500\n",
      "denotation oracle accuracy         1.000\n",
      "number of parses                   302.000\n",
      "spurious ambiguity                 0.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "expanded_arithmetic_grammar = Grammar(expanded_arithmetic_rules)\n",
    "expanded_arithmetic_model = Model(grammar=expanded_arithmetic_grammar,\n",
    "                                  feature_fn=arithmetic_features,\n",
    "                                  weights=weights,\n",
    "                                  executor=execute)\n",
    "train_test(model=expanded_arithmetic_model,\n",
    "           train_examples=arithmetic_examples[:13],\n",
    "           test_examples=arithmetic_examples[13:],\n",
    "           metrics=denotation_match_metrics(),\n",
    "           training_metric=DenotationAccuracyMetric(),\n",
    "           seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You will observe not only that denotation accuracy improves dramatically on both training and test datasets, but also that \"correct\" lexical rules (such as the one that pairs `'plus'` with `'+'`) get positive weight, while \"incorrect\" rules (like the one that pairs `'plus'` with `'-'`) get negative weight.  You will also observe that the number of parses is far higher than it was before!  That's because the expanded grammar is much looser and more productive than it was.  But at this point we can begin to imagine schemes for pruning the grammar.\n",
    "\n",
    "There are, of course, a wide variety of approaches to inducing the rules of a semantic grammar from training data, but this simple example should give you some hope that it's possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises <a id=\"arithmetic-exercises\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- TODO: consider ordering. -->\n",
    "\n",
    "Note that some of these exercises ask you to extend the grammar in ways that will be a bit awkward, given the requirement that rules be in Chomsky normal form (CNF).  In the [next unit](./sippycup-unit-2.ipynb), we'll look at ways to relax this restriction by enriching the `Grammar` class.  Don't jump the gun!  Your solutions to these exercises should adhere to the CNF restriction.  It's going to be a bit of a pain in the ass, and that's part of the point.\n",
    "\n",
    "### Straightforward\n",
    "\n",
    "1. How many parses do you get for \"one plus one plus one plus one plus one\"?  Why?\n",
    "\n",
    "1. Extend the grammar to support postfix unary operators, as in \"two squared\" or \"two cubed\".\n",
    "\n",
    "1. Extend the grammar to support divison, as in \"four divided by three\" or \"minus four over two\".\n",
    "\n",
    "1. Extend the grammar to support multi-word operators, as in \"the square root of one\" or \"the average of one and two\".  (You may need to extend the semantic representation and the executor as well.)\n",
    "\n",
    "1. Extend the grammar to parse expressions for very large numbers, such as\n",
    "   \"one million forty eight thousand five hundred seventy six\" or\n",
    "   \"a billion and one\".\n",
    "    \n",
    "1. Extend the grammar to support decimal numbers, such as\n",
    "   \"three point one four one six\" or\n",
    "   \"one point zero zero zero one\".\n",
    "    \n",
    "1. Extend the grammar to support fractions, including [improper fractions][] and [mixed numbers][], such as\n",
    "   \"four thirds\",\n",
    "   \"twenty two over seven\", or\n",
    "   \"two and a quarter\".\n",
    "   \n",
    "1. When we learned from semantics, semantics accuracy on the training examples reached 1.000 after training.  However, when we switched to learning from denotations, it did not.  Explain why.  Be precise and specific.\n",
    "\n",
    "1. When we trained on the 100 examples in `arithmetic_dev_examples`, denotation accuracy on the training examples did not reach 1.000 after training.  Diagnose the errors and describe your findings.  What could help us to eliminate those errors?  (You don't need to implement the fix.  Just give a precise diagnosis.)\n",
    "\n",
    "1. Add features to ensure that subtraction and division are properly [left-associative](http://en.wikipedia.org/wiki/Operator_associativity), so that\n",
    "   \"four minus three plus two\" has denotation 3,\n",
    "   \"four minus three minus two\" has denotation -1, and\n",
    "   \"four over three times two\" has denotation 8/3.\n",
    "    \n",
    "\n",
    "### Challenging\n",
    "\n",
    "1. Implement an \"eager\" version of the arithmetic grammar, in which the semantics of \"plus\" is not simply a symbol (`'+'`), but a lambda function (`lambda x, y: x + y`), and similarly for the other operators.  What else has to change to make this work?  What impact does this have on accuracy?\n",
    "\n",
    "1. When inducing the lexicon, what happens if you drop the restriction that the token and the semantics of a lexical rule must belong to the same syntactic category?  If you encounter obstacles, can they be overcome?\n",
    "\n",
    "[improper fractions]: http://en.wikipedia.org/wiki/Fraction_%28mathematics%29#Proper_and_improper_fractions\n",
    "[mixed numbers]: http://en.wikipedia.org/wiki/Fraction_%28mathematics%29#Mixed_numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright (C) 2015 Bill MacCartney"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}