{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problem set 2: Viterbi Sequence Labeling\n",
    "=====================\n",
    "\n",
    "- This project focuses on sequence labeling with Hidden Markov models and implementing the Viterbi algorithm.\n",
    "- The target domain is part-of-speech tagging on the Universal Dependencies dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict, Counter\n",
    "\n",
    "from gtnlplib import preproc, viterbi, most_common, clf_base\n",
    "from gtnlplib import naive_bayes, scorer, constants, tagger_base, hmm\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "# this enables you to create inline plots in the notebook \n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Data Processing\n",
    "\n",
    "The test data will be released around 48 hours before the deadline.\n",
    "The part-of-speech tags are defined on the [universal dependencies website](http://universaldependencies.org/en/pos/index.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "## Define the file names\n",
    "TRAIN_FILE = constants.TRAIN_FILE\n",
    "DEV_FILE = constants.DEV_FILE\n",
    "TEST_FILE = constants.TEST_FILE # You do not have this for now"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is demo code for using the function `conll_seq_generator()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set([u'ADV', u'NOUN', u'NUM', u'ADP', u'PRON', u'SCONJ', u'PROPN', u'DET', u'SYM', u'INTJ', u'PART', u'PUNCT', u'VERB', u'X', u'AUX', u'CONJ', u'ADJ'])\n"
     ]
    }
   ],
   "source": [
    "## Demo\n",
    "all_tags = set()\n",
    "for i,(words, tags) in enumerate(preproc.conll_seq_generator(TRAIN_FILE,max_insts=100000)):\n",
    "    for tag in tags:\n",
    "        all_tags.add(tag)\n",
    "print all_tags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.1**: Counting words per tag. (* 0.5 points *)\n",
    "\n",
    "Implement `get_tag_word_counts` in `most_common.py`\n",
    "\n",
    "- **Input**: filename for data file, to be passed as argument to `preproc.conll_seq_generation`\n",
    "- **Output**: dict of counters, where keys are tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(most_common);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ADV [(u'so', 371), (u'just', 353), (u'when', 306)]\n",
      "NOUN [(u'time', 385), (u'people', 233), (u'way', 187)]\n",
      "NUM [(u'one', 332), (u'two', 157), (u'2', 129)]\n",
      "ADP [(u'of', 3424), (u'in', 2705), (u'to', 1783)]\n",
      "PRON [(u'I', 3121), (u'you', 1920), (u'it', 1468)]\n",
      "SCONJ [(u'that', 982), (u'if', 450), (u'as', 312)]\n",
      "PROPN [(u'Bush', 211), (u'US', 162), (u'Iraq', 119)]\n",
      "DET [(u'the', 8142), (u'a', 3588), (u'The', 884)]\n",
      "SYM [(u'$', 251), (u'-', 101), (u':)', 34)]\n",
      "INTJ [(u'Please', 141), (u'please', 111), (u'Yes', 34)]\n",
      "PART [(u'to', 3221), (u'not', 805), (u\"n't\", 655)]\n",
      "PUNCT [(u'.', 8645), (u',', 7021), (u'\"', 1352)]\n",
      "VERB [(u'is', 1738), (u'was', 808), (u'have', 748)]\n",
      "X [(u'etc', 39), (u'1', 29), (u'2', 29)]\n",
      "AUX [(u'will', 811), (u'would', 578), (u'can', 578)]\n",
      "CONJ [(u'and', 4843), (u'or', 697), (u'but', 602)]\n",
      "ADJ [(u'other', 268), (u'good', 251), (u'new', 195)]\n"
     ]
    }
   ],
   "source": [
    "# this block uses your code to find the most common words per tag\n",
    "counters = most_common.get_tag_word_counts(TRAIN_FILE)\n",
    "for tag,tag_ctr in counters.iteritems():\n",
    "    print tag,tag_ctr.most_common(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Tagging as classification \n",
    "\n",
    "Now you will implement part-of-speech tagging via classification.\n",
    "\n",
    "Tagging quality is evaluated using evalTagger, which takes three arguments:\n",
    "- a tagger, which is a **function** taking a list of words and a tagset as arguments\n",
    "- an output filename\n",
    "- a test file\n",
    "\n",
    "You will want to use lambda expressions to create the first argument for this function, as shown below.\n",
    "Here's how it works. I provide a tagger that labels everything as a noun."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(tagger_base);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.166891999364\n"
     ]
    }
   ],
   "source": [
    "# here is a tagger that just tags everything as a noun\n",
    "noun_tagger = lambda words, alltags : ['NOUN' for word in words]\n",
    "confusion = tagger_base.eval_tagger(noun_tagger,'nouns',all_tags=all_tags)\n",
    "print scorer.accuracy(confusion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Deliverable 2.1 ** Classification-based tagging. (* 0.5 points *)\n",
    "\n",
    "Now do the same thing, but building your tagger *as a classifier.* To do this, implement `make_classifier_tagger` in `tagger_base.py`. \n",
    "\n",
    "- **Input**: defaultdict of weights\n",
    "- **Output**: function from (list of word tokens, list of all possible tags) --> tags for each word\n",
    "\n",
    "The function that you output should use your predict() function from pset 1. You are free to edit this function if you don't think you got it right in pset 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(tagger_base);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "classifier_noun_tagger = tagger_base.make_classifier_tagger(most_common.get_noun_weights())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.166891999364\n"
     ]
    }
   ],
   "source": [
    "confusion = tagger_base.eval_tagger(classifier_noun_tagger,'all-nouns.preds',all_tags=all_tags)\n",
    "print scorer.accuracy(confusion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.2** Tagging words by their most common tag. (* 0.5 points *)\n",
    "\n",
    "Now build a classifier tagger that tags each word with its most common tag in the training set. To do this, implement `get_most_common_word_weights` in `most_common.py`.\n",
    "\n",
    "Inputs:\n",
    "\n",
    "- training file\n",
    "\n",
    "Outputs:\n",
    "\n",
    "- defaultdict of weights\n",
    "\n",
    "Each word should get the tag that is most frequently associated with it in the training data. If the word does not appear in the training data, the weights should be set so that the tagger outputs 'NOUN'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "theta_mc = most_common.get_most_common_word_weights(constants.TRAIN_FILE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tagger_mc = tagger_base.make_classifier_tagger(theta_mc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[u'PRON', u'AUX', u'AUX', u'NOUN']\n"
     ]
    }
   ],
   "source": [
    "tags = tagger_mc(['They','can','can','fish'],all_tags)\n",
    "print tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[u'DET', u'ADJ', u'NOUN', u'DET', u'NOUN', u'PUNCT']\n"
     ]
    }
   ],
   "source": [
    "tags = tagger_mc(['The','old','man','the','boat','.'],all_tags)\n",
    "print tags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's run your tagger on the dev data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.848337839987\n"
     ]
    }
   ],
   "source": [
    "confusion = tagger_base.eval_tagger(tagger_mc,'most-common.preds',all_tags=all_tags)\n",
    "print scorer.accuracy(confusion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.3** Naive Bayes as a tagger. (* 0.5 points *)\n",
    "\n",
    "Now use a Naive Bayes approach to setting the weights for the classifier tagger. For this, you can copy in your ```naive_bayes.py``` from pset1. If you don't think you got it right, you are free to change it now. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ADJ ADP ADV AUX CONJ DET INTJ NOUN NUM PART PRON PROPN PUNCT SCONJ SYM VERB X\n"
     ]
    }
   ],
   "source": [
    "sorted_tags = sorted(counters.keys())\n",
    "print ' '.join(sorted_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nb_weights = naive_bayes.estimate_nb([counters[tag] for tag in sorted_tags],\n",
    "                                     sorted_tags,\n",
    "                                     .01)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gives weights for each tag-word pair that represent $\\log P(word \\mid tag)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-5.38657494998 -3.92169758048\n",
      "-3.11635765265 -4.29498560641 -14.4453722986\n",
      "-14.4453722986 -15.0676307485 -1.01587097152\n"
     ]
    }
   ],
   "source": [
    "print nb_weights[('ADJ','bad')], nb_weights[(u'ADJ',u'good')]\n",
    "print nb_weights[(u'PRON',u'they')], nb_weights[(u'PRON',u'They')], nb_weights[(u'PRON',u'good')]\n",
    "print nb_weights[(u'PRON',u'.')], nb_weights[(u'NOUN',u'.')], nb_weights[(u'PUNCT',u'.')]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These weights should correspond to probabilities that sum to one for each tag."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "vocab = set([word for tag,word in nb_weights.keys() if word is not constants.OFFSET])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "1.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "print sum(np.exp(nb_weights[('ADJ',word)]) for word in vocab)\n",
    "print sum(np.exp(nb_weights[('DET',word)]) for word in vocab)\n",
    "print sum(np.exp(nb_weights[('PUNCT',word)]) for word in vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have zero weights for OOV terms -- more on this later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print nb_weights[('ADJ','baaaaaaaaad')]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As constructed here, the Naive Bayes tagger also does not correctly estimate weights for the offset, $\\log P(tag)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-2.83321334406\n",
      "-2.83321334406\n",
      "-2.83321334406\n"
     ]
    }
   ],
   "source": [
    "print nb_weights[('VERB'),constants.OFFSET]\n",
    "print nb_weights[('ADV'),constants.OFFSET]\n",
    "print nb_weights[('PRON'),constants.OFFSET]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a result, the accuracy is not as good as the most-common-tag tagger from above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.807181485605\n"
     ]
    }
   ],
   "source": [
    "confusion = tagger_base.eval_tagger(tagger_base.make_classifier_tagger(nb_weights),'nb-simple.preds')\n",
    "dev_acc = scorer.accuracy(confusion)\n",
    "print dev_acc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.4** Fixing the Naive Bayes tagger (* 0.5 points *)\n",
    "\n",
    "Implement ```naive_bayes.estimate_nb_tagger```, which should take two arguments:\n",
    "\n",
    "- A list of word counters for each tag\n",
    "- A smoothing value\n",
    "\n",
    "It should return weights so that \n",
    "\n",
    "- $\\theta[(tag,word)] = \\log P(word \\mid tag)$. If your naive_bayes is correct, it already does this.\n",
    "- $\\theta[(tag,offset)] = \\log P(tag)$. You will need to add some code to make this happen.\n",
    "\n",
    "All probabilities should be smoothed relative frequency estimates. \n",
    "\n",
    "Your implementation should call ```naive_bayes.estimate_nb```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(naive_bayes);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_nb_fixed = naive_bayes.estimate_nb_tagger(counters,.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n"
     ]
    }
   ],
   "source": [
    "# emission weights still sum to one \n",
    "print sum(np.exp(theta_nb_fixed[('ADJ',word)]) for word in vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-7.36649959838 -7.36649959838\n"
     ]
    }
   ],
   "source": [
    "# emission weights are identical to theta_nb\n",
    "print nb_weights[('ADJ','okay')],theta_nb_fixed[('ADJ','okay')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-2.00636661932\n",
      "-2.96505203939\n",
      "-2.39906446122\n"
     ]
    }
   ],
   "source": [
    "# but the offsets are now correct\n",
    "print theta_nb_fixed[('VERB'),constants.OFFSET]\n",
    "print theta_nb_fixed[('ADV'),constants.OFFSET]\n",
    "print theta_nb_fixed[('PRON'),constants.OFFSET]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Offsets should correspond to log-probabilities $\\log P(y)$ such that $\\sum_y P(y) = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.99999999999999978"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(np.exp(theta_nb_fixed[(tag,constants.OFFSET)]) for tag in all_tags)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's apply the tagger"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.848337839987\n"
     ]
    }
   ],
   "source": [
    "confusion = tagger_base.eval_tagger(tagger_base.make_classifier_tagger(theta_nb_fixed),\n",
    "                                    'nb-fixed.preds')\n",
    "dev_acc = scorer.accuracy(confusion)\n",
    "print dev_acc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just as good as the heuristic tagger from above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Viterbi Algorithm\n",
    "\n",
    "In this section you will implement the Viterbi algorithm. To get warmed up, let's work out an example by hand. For simplicity, there are only two tags, **N**OUN and **V**ERB. Here are the parameters:\n",
    "\n",
    "| | Value |\n",
    "| ------------- |:-------------:|\n",
    "| $\\log P_E(\\cdot|N)$ | they: -1, can: -3, fish: -3 |\n",
    "| $\\log P_E(\\cdot|V)$ | they: -11, can: -2, fish: -4 |\n",
    "| $\\log P_T(\\cdot|N)$ | N: -5, V: -2, END: -2 |\n",
    "| $\\log P_T(\\cdot|V)$ | N: -1, V: -3, END: -3 |\n",
    "| $\\log P_T(\\cdot|\\text{START})$ | N :-1, V :-2 |\n",
    "\n",
    "where $P_E(\\cdot|\\cdot)$ is the emission probability and $P_T(\\cdot|\\cdot)$ is the transition probability.\n",
    " \n",
    "In class we discuss the sentence *They can fish*. Now work out a more complicated example: \"*They can can fish*\", where the second \"*can*\" refers to the verb of putting things into cans.\n",
    " \n",
    "** Deliverable 3.1 ** Work out the trellis by hand, and fill in the table in the file ```text-answers.md``` (*0.5 points*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing Viterbi ##\n",
    "\n",
    "Here are some predefined weights, corresponding to the weights from the problem 3.1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "START_TAG = constants.START_TAG\n",
    "TRANS = constants.TRANS\n",
    "END_TAG = constants.END_TAG\n",
    "EMIT = constants.EMIT\n",
    "\n",
    "hand_weights = {('NOUN','they',EMIT):-1,\\\n",
    "                ('NOUN','can',EMIT):-3,\\\n",
    "                ('NOUN','fish',EMIT):-3,\\\n",
    "                ('VERB','they',EMIT):-11,\\\n",
    "                ('VERB','can',EMIT):-2,\\\n",
    "                ('VERB','fish',EMIT):-4,\\\n",
    "                ('NOUN','NOUN',TRANS):-5,\\\n",
    "                ('VERB','NOUN',TRANS):-2,\\\n",
    "                (END_TAG,'NOUN',TRANS):-2,\\\n",
    "                ('NOUN','VERB',TRANS):-1,\\\n",
    "                ('VERB','VERB',TRANS):-3,\\\n",
    "                (END_TAG,'VERB',TRANS):-3,\\\n",
    "                ('NOUN',START_TAG,TRANS):-1,\\\n",
    "                ('VERB',START_TAG,TRANS):-2}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.2** Building HMM features. (*0.5 points*)\n",
    "\n",
    "Implement `hmm_features` in `hmm.py` to compute the HMM features for the function $\\mathbf{f}(\\mathbf{x},y_m,y_{m-1},m)$. \n",
    "\n",
    "Expected behavior is shown below. Note how `constants.EMIT` and `constants.TRANS` are used to distinguish emission and transition features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(hmm);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['they', 'can', 'can', 'fish']\n"
     ]
    }
   ],
   "source": [
    "sentence = \"they can can fish\".split()\n",
    "print sentence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('Noun', 'can', '--EMISSION--'): 1, ('Noun', 'Verb', '--TRANS--'): 1}\n",
      "{('Noun', 'they', '--EMISSION--'): 1, ('Noun', '--START--', '--TRANS--'): 1}\n",
      "{('--END--', 'Verb', '--TRANS--'): 1}\n"
     ]
    }
   ],
   "source": [
    "print hmm.hmm_features(sentence,'Noun','Verb',2)\n",
    "print hmm.hmm_features(sentence,'Noun',START_TAG,0)\n",
    "print hmm.hmm_features(sentence,END_TAG,'Verb',4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.3** The Viterbi recurrence. (*1 point*)\n",
    "\n",
    "Implement `viterbi_step` in `gtnlplib/viterbi.py`. This is the method that will compute the best path score and corresponding back pointer for a given tag and word, which you will call from the main viterbi routine.\n",
    "\n",
    "- **Input 1**: A tag to calculate the best path for\n",
    "- **Input 2**: An index of the word to calculate the best path for\n",
    "- **Input 3**: A list of words to tag\n",
    "- **Input 4**: A feature function, like hmm_feats\n",
    "- **Input 5**: A dict of weights\n",
    "- **Input 6**: A list of all possible tags\n",
    "- **Input 7**: A list of dicts representing the best scores for the previous trellis layer\n",
    "- **Output 1**: The score of the best-scoring sequence\n",
    "- **Output 2**: The feature in the previous trellis layer corresponding to the best score\n",
    "\n",
    "There are a lot of inputs, but the code itself will not be very complex. Make sure you understand what each input represents before starting to write a solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can run your viterbi step on the example in 3.1, by building on the code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(viterbi);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-2, '--START--')\n",
      "(-13, '--START--')\n"
     ]
    }
   ],
   "source": [
    "print viterbi.viterbi_step('NOUN',0,sentence,hmm.hmm_features,hand_weights,{START_TAG:0})\n",
    "print viterbi.viterbi_step('VERB',0,sentence,hmm.hmm_features,hand_weights,{START_TAG:0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-10, 'NOUN')\n",
      "(-6, 'NOUN')\n"
     ]
    }
   ],
   "source": [
    "print viterbi.viterbi_step('NOUN',1,sentence,\n",
    "                           hmm.hmm_features,\n",
    "                           hand_weights,\n",
    "                           {'NOUN':-2,'VERB':-13})\n",
    "print viterbi.viterbi_step('VERB',1,sentence,\n",
    "                           hmm.hmm_features,\n",
    "                           hand_weights,\n",
    "                           {'NOUN':-2,'VERB':-13})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.4** Build the Viterbi trellis. (*0.5 points*)\n",
    "\n",
    "Use `viterbi_step` to implement `build_trellis` in `viterbi.py`\n",
    "\n",
    "This function should take:\n",
    "\n",
    "- A list of tokens to be tagged\n",
    "- A feature function\n",
    "- A defaultdict of weights\n",
    "- A tag set\n",
    "\n",
    "It should output a list of dicts. In each dict should be key-value pairs of the form `tag:(score,prev_tag)`. See the example output below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(viterbi);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "all_tags = ['NOUN','VERB']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# let's change the weights a little\n",
    "hand_weights['NOUN','they',EMIT] = -2\n",
    "hand_weights['VERB','fish',EMIT] = -5\n",
    "hand_weights['VERB','VERB',TRANS] = -2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "trellis = viterbi.build_trellis(sentence,hmm.hmm_features,hand_weights,all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'VERB': (-13, '--START--'), 'NOUN': (-3, '--START--')}\n",
      "{'VERB': (-7, 'NOUN'), 'NOUN': (-11, 'NOUN')}\n",
      "{'VERB': (-11, 'VERB'), 'NOUN': (-11, 'VERB')}\n",
      "{'VERB': (-18, 'VERB'), 'NOUN': (-15, 'VERB')}\n"
     ]
    }
   ],
   "source": [
    "for line in trellis:\n",
    "    print line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.5** Implement the Viterbi algorithm. (*0.5 points*)\n",
    "\n",
    "Specifically, use `build_trellis` to implement `viterbi_tagger` in `viterbi.py`.\n",
    "\n",
    "Your first task will be to figure out the score of the best path, and the final node in the trellis. Use a transition feature involving `constants.END_TAG` to compute this.\n",
    "\n",
    "Then iterate backwards through the trellis to construct the best path.\n",
    "\n",
    "Inputs:\n",
    "\n",
    "- A list of tokens to be tagged\n",
    "- A feature function\n",
    "- A defaultdict of weights\n",
    "- A tag set\n",
    "\n",
    "Outputs:\n",
    "\n",
    "- Best-scoring tag sequence\n",
    "- Score of best-scoring tag sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(viterbi);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(['NOUN', 'VERB', 'VERB', 'NOUN'], -17)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi.viterbi_tagger(sentence,hmm.hmm_features,hand_weights,all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(['NOUN', 'VERB', 'VERB', 'VERB', 'VERB', 'VERB', 'NOUN'], -29)"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi.viterbi_tagger(['they','can','can','can','can','can','fish'],\n",
    "                       hmm.hmm_features,hand_weights,all_tags)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Hidden Markov Model: Estimation\n",
    "\n",
    "You will now implement the estimatation for a hidden Markov model.\n",
    "\n",
    "We'll start with the tag transitions.\n",
    "\n",
    "The following function, which we provide, computes the tag transitions counts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tag_trans_counts = most_common.get_tag_trans_counts(TRAIN_FILE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function returns a dict of counters, where the keys are tags.\n",
    "\n",
    "Each counter is the frequency of tags following a given tag, e.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({u'NOUN': 9676, u'ADJ': 3600, u'PROPN': 1488, u'VERB': 323, u'NUM': 252, u'ADV': 250, u'PUNCT': 201, u'ADP': 185, u'DET': 166, u'PRON': 65, u'SYM': 32, u'X': 16, u'AUX': 16, u'CONJ': 10, u'PART': 4, u'SCONJ': 1})\n",
      "Counter({u'PRON': 3533, u'PROPN': 1466, u'DET': 1259, u'ADV': 997, u'VERB': 826, u'NOUN': 789, u'ADP': 536, u'ADJ': 486, u'SCONJ': 445, u'PUNCT': 433, u'NUM': 406, u'INTJ': 398, u'AUX': 296, u'CONJ': 290, u'X': 243, u'SYM': 97, u'PART': 43})\n"
     ]
    }
   ],
   "source": [
    "print tag_trans_counts['DET']\n",
    "print tag_trans_counts[START_TAG]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 4.1** Estimate transition log-probabilities for an HMM. (*0.5 points*)\n",
    "\n",
    "Implement `compute_transition_weights` in `hmm.py`.\n",
    "\n",
    "You should use the function `get_tag_trans_counts` in `most_common.py`\n",
    "\n",
    "Inputs\n",
    "\n",
    "- Transition counts (from `get_tag_trans_counts`)\n",
    "- Smoothing\n",
    "\n",
    "Outputs\n",
    "\n",
    "- Defaultdict with weights for transition features, in the form $[y_m, y_{m-1}, \\text{TRANS}]$\n",
    "\n",
    "Hints: \n",
    "\n",
    "- Don't forget to assign smoothed probabilities to transitions which do not appear in the counts. \n",
    "- Do not assign probabilities for transitions to the start tag, which can only come first. This will also affect your computation of the denominator, since you are not smoothing the probability of transitions to the start tag.\n",
    "- Don't forget to assign probabilities to transitions to the end tag; this too will affect your denominator.\n",
    "- As always, probabilities should sum to one (this time conditioned on the previous tag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(hmm);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "hmm_trans_weights = hmm.compute_transition_weights(tag_trans_counts,.001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "789 -2.76615186681\n",
      "826 -2.72032347091\n",
      "323 -3.92034540383\n",
      "0 -16.605756102\n",
      "9676 -0.520596847943\n",
      "0 -inf\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print tag_trans_counts[START_TAG]['NOUN'], hmm_trans_weights[('NOUN',START_TAG,TRANS)]\n",
    "print tag_trans_counts[START_TAG]['VERB'], hmm_trans_weights[('VERB',START_TAG,TRANS)]\n",
    "print tag_trans_counts['DET']['VERB'], hmm_trans_weights[('VERB','DET',TRANS)]\n",
    "print tag_trans_counts['DET']['INTJ'], hmm_trans_weights[('INTJ','DET',TRANS)]\n",
    "print tag_trans_counts['DET']['NOUN'], hmm_trans_weights[('NOUN','DET',TRANS)]\n",
    "print tag_trans_counts['VERB'][START_TAG], hmm_trans_weights[(START_TAG,'VERB',TRANS)]\n",
    "#print tag_trans_counts[END_TAG]['VERB'] # will throw key error\n",
    "print hmm_trans_weights[('VERB',END_TAG,TRANS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These log-probabilities should normalize to when summing over $y_m$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "all_tags = tag_trans_counts.keys() + [END_TAG]\n",
    "print sum(np.exp(hmm_trans_weights[(tag,'NOUN',TRANS)]) for tag in all_tags)\n",
    "print sum(np.exp(hmm_trans_weights[(tag,'SYM',TRANS)]) for tag in all_tags)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Deliverable 4.2** (*1 point 4650; 0.5 points 7650*)\n",
    "\n",
    "Now implement `compute_HMM_weights` in `hmm.py`. You should use two functions:\n",
    "\n",
    "- `compute_transition_weights`, which you just implemented\n",
    "- `naive_bayes.estimate_nb`, which you used in part 2 to compute the emission log-probabilities, $\\log P(w \\mid y)$.\n",
    "\n",
    "Inputs:\n",
    "\n",
    "- trainfile\n",
    "- smoothing\n",
    "\n",
    "Output:\n",
    "\n",
    "- defaultdict of hidden Markov model weights\n",
    "\n",
    "A tricky issue is how to handle unseen words and illegal tag-tag transitions. We will have to handle these cases slightly differently:\n",
    "\n",
    "- For illegal transitions, we need to assign zero probability, which is $-\\infty$ log-probability. You can use `-np.inf` for these weights.\n",
    "- For unseen words, we **don't** want to assign zero probability, since unseen words are likely to appear in the test set. Use a defaultdict for this, with log-probability = 0, but don't include this in the normalizer. We'll talk more about whether this is a good solution later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(hmm);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_hmm,_ = hmm.compute_HMM_weights(TRAIN_FILE,.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-7.41746204765 -5.33071419765\n",
      "-4.5722924085 -14.3151646115\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print theta_hmm['NOUN','right',EMIT], theta_hmm['ADV','right',EMIT]\n",
    "print theta_hmm['PRON','she',EMIT], theta_hmm['DET','she',EMIT]\n",
    "print theta_hmm['NOUN','notarealword',EMIT]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "334429"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(theta_hmm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "print sum(np.exp(theta_hmm['NOUN',word,EMIT]) for word in vocab)\n",
    "print sum(np.exp(theta_hmm['DET',word,EMIT]) for word in vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 4.3** (*0.5 points*)\n",
    "\n",
    "We can now combine Viterbi and the HMM weights to compute the tag sequence for the example sentence. Make sure your implementation passes the test for this deliverable, and **explain (in `text-answers.md`) whether you think these predicted tags are correct**, based on your understanding of the universal part-of-speech tag set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([u'PRON', u'AUX', u'AUX', u'NOUN'], -31.294333658962987)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reload(viterbi)\n",
    "viterbi.viterbi_tagger(['they', 'can', 'can', 'fish'],hmm.hmm_features,theta_hmm,all_tags)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 4.4** (*0.5 points*)\n",
    "\n",
    "As shown in the cell below, the HMM weights include a weight of zero for the emission of unseen words. In `text-answers.md`, please explain:\n",
    "\n",
    "- why this is a violation of the HMM probability model explained in the notes;\n",
    "- How, if at all, this will affect the overall tagging."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-7.41746204765 -5.33071419765\n",
      "-4.5722924085 -14.3151646115\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print theta_hmm['NOUN','right',EMIT], theta_hmm['ADV','right',EMIT]\n",
    "print theta_hmm['PRON','she',EMIT], theta_hmm['DET','she',EMIT]\n",
    "print theta_hmm['ADJ','thisworddoesnotappear',EMIT]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 4.5** (*0.5 points*)\n",
    "\n",
    "- Run your HMM tagger on the dev data and test data, using the code blocks below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 From/ADP the/DET AP/NOUN comes/VERB this/DET story/NOUN :/PUNCT\n",
      "1 President/PROPN Bush/PROPN on/ADP Tuesday/PROPN nominated/VERB two/NUM individuals/NOUN to/PART replace/VERB retiring/PART jurists/VERB on/ADP federal/ADJ courts/NOUN in/ADP the/DET Washington/PROPN area/NOUN ./PUNCT\n",
      "2 Bush/PROPN nominated/VERB Jennifer/PROPN M./PROPN Anderson/PROPN for/ADP a/DET 15/NUM -/PUNCT year/NOUN term/NOUN as/ADP associate/NOUN judge/NOUN of/ADP the/DET Superior/PROPN Court/PROPN of/ADP the/DET District/PROPN of/ADP Columbia/PROPN ,/PUNCT replacing/VERB Steffen/ADP W./PROPN Graae/PROPN ./PUNCT\n"
     ]
    }
   ],
   "source": [
    "# this is just for fun\n",
    "for i,(words,_) in enumerate(preproc.conll_seq_generator(DEV_FILE)):\n",
    "    print i, \n",
    "    pred_tags = viterbi.viterbi_tagger(words,hmm.hmm_features,theta_hmm,all_tags)[0]\n",
    "    for word,pred_tag in zip(words,pred_tags):\n",
    "        print \"%s/%s\"%(word,pred_tag),\n",
    "    print\n",
    "    if i >= 2: break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tagger = lambda words, all_tags : viterbi.viterbi_tagger(words,\n",
    "                                                         hmm.hmm_features,\n",
    "                                                         theta_hmm,\n",
    "                                                         all_tags)[0]\n",
    "confusion = tagger_base.eval_tagger(tagger,'hmm-dev-en.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.877047876571\n"
     ]
    }
   ],
   "source": [
    "print scorer.accuracy(confusion)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagger(tagger,'hmm-te-en.preds',testfile=constants.TEST_FILE_UNLABELED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.879024545744\n"
     ]
    }
   ],
   "source": [
    "# you don't have en-ud-test.conllu, so you can't run this\n",
    "te_confusion = scorer.get_confusion('data/en-ud-test.conllu','hmm-te-en.preds')\n",
    "print scorer.accuracy(te_confusion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Part of Speech tagging in Japanese\n",
    "\n",
    "Now you will evaluate the tagger you just implemented on a Japanese dataset that uses the same set of part-of-speech tags.\n",
    "\n",
    "**Deliverable 5.1** (*1 point 4650, 0.5 points 7650*)\n",
    "\n",
    "First, let's compare the tag distributions between Japanese and English. Using your `get_tag_trans_counts`, identify the top three tags that are most likely to follow VERBS and NOUNS in each language. \n",
    "\n",
    "List these tags in `text-answers.md`, and try to explain some of the differences you see. You may want to do a little research about Japanese on [wikipedia](https://en.wikipedia.org/wiki/Japanese_language). (If you really want to dig in, check out this research paper, which describes the annotation of the Japanese dataset that we are using: http://www.lrec-conf.org/proceedings/lrec2016/pdf/122_Paper.pdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from gtnlplib.constants import JA_TRAIN_FILE, JA_DEV_FILE, JA_TEST_FILE_HIDDEN, JA_TEST_FILE\n",
    "from gtnlplib.constants import TRAIN_FILE, START_TAG, END_TAG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tag_trans_counts_en = most_common.get_tag_trans_counts(TRAIN_FILE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tag_trans_counts_ja = most_common.get_tag_trans_counts(JA_TRAIN_FILE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print tag_trans_counts_en['VERB'].most_common(3)\n",
    "print tag_trans_counts_ja['VERB'].most_common(3)\n",
    "print\n",
    "print tag_trans_counts_en['NOUN'].most_common(3)\n",
    "print tag_trans_counts_ja['NOUN'].most_common(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 5.2** (*0.5 points*)\n",
    "\n",
    "Now, run the code below to calculate the HMM weights for Japanese, and evaluate a viterbi tagger on the Japanese dev set and test set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_hmm_ja, all_tags_ja = hmm.compute_HMM_weights(JA_TRAIN_FILE,.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tagger = lambda words, all_tags : viterbi.viterbi_tagger(words,\n",
    "                                                         hmm.hmm_features,\n",
    "                                                         theta_hmm_ja,\n",
    "                                                         all_tags_ja)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "confusion = tagger_base.eval_tagger(tagger,'hmm-dev-ja.preds',testfile=JA_DEV_FILE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.842325019229\n"
     ]
    }
   ],
   "source": [
    "print scorer.accuracy(confusion)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagger(tagger,'hmm-test-ja.preds',testfile=JA_TEST_FILE_HIDDEN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.811956521739\n"
     ]
    }
   ],
   "source": [
    "# you don't have the test file, so you can't run this\n",
    "confusion_te_ja = scorer.get_confusion(JA_TEST_FILE,'hmm-test-ja.preds')\n",
    "print scorer.accuracy(confusion_te_ja)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 6. 7650 \"only\"\n",
    "\n",
    "**Deliverable 6** Research question (*1 point*)\n",
    "\n",
    "Find an example of sequence labeling for a task other than part-of-speech tagging, in a paper at ACL, NAACL, EMNLP, EACL, or TACL, within the last five years (2012-2017). Put your response in `text-answers.md`.\n",
    "\n",
    "List:\n",
    "\n",
    "- The title, authors, and venue of the paper.\n",
    "- What is the task they are trying to solve?\n",
    "- What methods do they use? HMM, CRF, max-margin markov network, something else?\n",
    "- Which features do they use?\n",
    "- What methods and features are most effective?\n",
    "\n",
    "As before, students in 4650 may optionally submit an answer to this question; if you do, you will be graded on the 7650 rubric."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}