{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Learning an alien language"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "__author__ = \"Chris Potts\"\n",
    "__version__ = \"CS224u, Stanford, Spring 2016 term\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "0. [Set-up](#Set-up)\n",
    "0. [The doomsday scenario](#The-doomsday-scenario)\n",
    "0. [In-class bake-off](#In-class-bake-off)\n",
    "0. [The data](#The-data)\n",
    "0. [Objective 1: Oracle accuracy](#Objective-1:-Oracle-accuracy)\n",
    "0. [Objective 2: Predictive accuracy](#Objective-2:-Predictive-accuracy)\n",
    "0. [Objective 3: The translation function](#Objective-3:-The-translation-function)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set-up\n",
    "\n",
    "0. Make sure the `sys.path.append` value is the path to your local [SippyCup repository](https://github.com/wcmac/sippycup). (Alternatively, you can add SippyCup to your Python path; see one of the teaching team if you'd like to do that but aren't sure how.)\n",
    "\n",
    "0. Make sure that [semparse_math_bakeoff_data.py](semparse_math_bakeoff_data.py) is in the current directory (or available via your Python path)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.append('../sippycup')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The doomsday scenario\n",
    "\n",
    "It's an indeterminate time in the future. An alien invasion is imminent.  We have intercepted many of the aliens'  transmissions and begun the process of decoding their language. Luckily, we have found a small database of alien  language statements paired with numbers that seem to be the denotations of  those statements. \n",
    "\n",
    "Linguists, working tirelessly, have translated the numbers into standard arabic notation, but they have made little headway in understanding the meanings of the words and phrases in the statements. Standard bag-of-words classifiers were little help with the high-dimensional output space.\n",
    "\n",
    "You've been called in personally by World President Zahara Jolie-Pitt-Kardashian to complete the translation task. Your goal is to use the available data to induce a lexicon mapping alien words to their associated mathematical concepts. Time is of the essence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In-class bake-off\n",
    "\n",
    "Turn in the \"denotation accuracy\" score you obtain from the the `evaluate_model` use at the end of the \"Objective 2\" section. We'll report on the results in the discussion forum.\n",
    "\n",
    "(You'll probably want to keep going from there to find out whether you cracked the code.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from copy import copy\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The data are available in `semparse_math_bakeoff_data.py`, which contains two lists of SippyCup `Example` instances:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from semparse_math_bakeoff_data import mathbake_train, mathbake_dev"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check out some examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in range(5):\n",
    "    ex = mathbake_train[random.randint(0, len(mathbake_train))]\n",
    "    print(ex.input, ex.denotation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective 1: Oracle accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To start, the goal should be to create a grammar that can find at least one parse with the correct denotation. With that done, we can rely on features and our training data to find weights that favor the correct parses."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The other linguists on the team have extracted the vocabulary, and they can say with confidence that the words in the grammar can be classified as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "integers = ['fribbs', 'volms', 'scincs', 'kugns', 'glarc', 'sherle']\n",
    "predicates = ['sniese', 'thouch', 'sklofg', 'scwokt']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can begin building a crude grammar on this basis. We'll start with an empty one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "from parsing import Grammar\n",
    "\n",
    "# Increasing this value will increase your chances of finding \n",
    "# correct parses, but it will slow everything down.\n",
    "import parsing\n",
    "parsing.MAX_CELL_CAPACITY = 1000\n",
    "\n",
    "gram = Grammar(start_symbol='$E') "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To start, we assume that the integers all have their denotations somewhere in the interval [0,5], and we consider every hypothesis of that form:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from parsing import Rule, add_rule\n",
    "\n",
    "for w, i in itertools.product(integers, range(len(integers))):\n",
    "    add_rule(gram, Rule('$E', w, i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We assume also that there are unary and binary operators, so we add those combination rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Unary connective, as in English \"minus one\":\n",
    "add_rule(gram, Rule('$E', '$UnOp $E', lambda sems: (sems[0], sems[1])))\n",
    "\n",
    "# First stage of binary connective, as in English \"two plus\":\n",
    "add_rule(gram, Rule('$EBO', '$E $BinOp', lambda sems: (sems[1], sems[0])))\n",
    "\n",
    "# Second stage of binary connective, as in English \"(two plus) seven\":\n",
    "add_rule(gram, Rule('$E', '$EBO $E', lambda sems: (sems[0][0], sems[0][1], sems[1])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Determining the semantic space of the operators is harder. The executor from SippyCup's `arithmetic.py` seems like a reasonable place to start:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "unary_ops = {\n",
    "    '~': lambda x: -x\n",
    "}\n",
    "\n",
    "binary_ops = {\n",
    "    '+': lambda x, y: x + y,\n",
    "    '-': lambda x, y: x - y,\n",
    "    '*': lambda x, y: x * y\n",
    "}\n",
    "\n",
    "##################################################\n",
    "#### Consider extending one or both ops dicts ####\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "ops = {key:val for key, val in itertools.chain(unary_ops.items(), binary_ops.items())}\n",
    "\n",
    "def execute(semantics):\n",
    "    if isinstance(semantics, tuple):\n",
    "        op = ops[semantics[0]]\n",
    "        args = [execute(arg) for arg in semantics[1:]]\n",
    "        return op(*args)\n",
    "    else:\n",
    "        return semantics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__TO DO__: bring in the words in `predicates`, in the form of a set of grammar rules like those we added for the integers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "##################################################\n",
    "########## Add your operators rules here ######### \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If all is going well, the vast majority of sentences of the alien language should now have a parse with a correct denotation. That is, our oracle accuracy should be at least 80%. (In fact, if it is this high, it is probably 100% but the target sometimes wasn't included in the sample of parses found during search.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from parsing import parse_input\n",
    "\n",
    "def check_oracle_accuracy(grammar=None, examples=mathbake_train, verbose=True):\n",
    "    oracle = 0\n",
    "    for ex in examples:\n",
    "        # All the denotations for all the parses:\n",
    "        dens = [execute(parse.semantics) for parse in gram.parse_input(ex.input)]\n",
    "        if ex.denotation in dens:\n",
    "            oracle += 1\n",
    "        elif verbose:\n",
    "            print(\"=\" * 70)\n",
    "            print(ex.input)\n",
    "            print(set(dens))\n",
    "            print(ex.denotation)\n",
    "    percent_correct = int(round((oracle/float(len(examples)))*100, 0))\n",
    "    print(\"Oracle accuracy: %s / %s (%s%%)\" % (oracle, len(examples), percent_correct))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "check_oracle_accuracy(grammar=gram, examples=mathbake_train, verbose=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "If your oracle accuracy isn't above 80%, then consider expanding the space of operators defined by `ops` and expanding the space of rules accordingly. __There's no guarantee that the alien language uses precisely the operators given by `ops`!__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Objective 2: Predictive accuracy\n",
    "\n",
    "Your grammar is now successful in that it finds correct parses and associated denotations for the alien language. However, World President Zahara Jolie-Pitt-Kardashian is unlikely to be impressed, because you can't tell her _which_ denotation is correct, and so you can't induce a translation lexicon either. To address this, we need to find feature weights that are effective at using the training data to identify the best hypotheses allowed by the grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can start with the core features given by `scoring.rule_features`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scoring import Model, rule_features\n",
    "from arithmetic import ArithmeticDomain # A source of more feature functions!\n",
    "\n",
    "def arithmetic_features(parse):\n",
    "    features = rule_features(parse)\n",
    "    # Consider adding to the features dict based on properties of\n",
    "    # parse and/or parse.semantics\n",
    "    \n",
    "    \n",
    "    \n",
    "    return features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__TO DO__: Improve on the features returned by `arithmetic_features`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now can build and train the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model = Model(grammar=gram, feature_fn=arithmetic_features, executor=execute)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__TO DO__: improve on the optimizer settings!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from learning import latent_sgd\n",
    "from metrics import DenotationAccuracyMetric\n",
    "\n",
    "##################################################\n",
    "#### Consider improving the optimizer settings ###\n",
    "\n",
    "trained_model = latent_sgd(\n",
    "    model, \n",
    "    mathbake_train, \n",
    "    training_metric=DenotationAccuracyMetric(), \n",
    "    T=10, \n",
    "    eta=0.1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that the model is trained, we can evaluate it on the held-out data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from experiment import evaluate_model\n",
    "from metrics import denotation_match_metrics\n",
    "\n",
    "evaluate_model(\n",
    "    model=trained_model, \n",
    "    examples=mathbake_dev, \n",
    "    examples_label=\"Dev\",\n",
    "    metrics=denotation_match_metrics(),\n",
    "    print_examples=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">Enter your \"denotation accuracy\" score (non-oracle) from the above into the bake-off.</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective 3: The translation function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our primary objective was to learn how to translate the alien language into our own language for math (basic arithmetic). To see how well we did, we can look at the weights the classifier learned for the core rule-based features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from operator import itemgetter\n",
    "from collections import defaultdict\n",
    "\n",
    "def view_lexical_features(weights):\n",
    "    # Get the lexical features:        \n",
    "    feats = [(featname, val) for featname, val in weights.items() \n",
    "             if val > 0.0 and isinstance(featname, str) and featname.startswith('Rule')]\n",
    "    # Get the core parts:\n",
    "    lex = defaultdict(list)\n",
    "    for featname, val in feats:\n",
    "        r = eval(featname)\n",
    "        lex[r.rhs[0]].append((r.sem, val))    \n",
    "    # Restrict to the highest weights for each feature:\n",
    "    for w, vals in lex.items():\n",
    "        maxval = max([x[1] for x in vals])\n",
    "        vals = [x for x in vals if x[1]==maxval]\n",
    "        lex[w] = vals  \n",
    "    # Printout sorted by our own semantic operators:\n",
    "    for featname, vals in sorted(lex.items(), key=(lambda item: str(item[1]))):\n",
    "        for val in vals:\n",
    "            print(\"'%s' means %s (weight %0.02f)\" % (featname, val[0], val[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "view_lexical_features(trained_model.weights)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Are you correct? [Paste in your output from `view_lexical_features` here to find out!](https://web.stanford.edu/class/cs224u/cgi-bin/mathbake/)__"
   ]
  }
 ],
 "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
}