07_problem-solving-example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem-Solving Demo: ANLP Assignment 2\n",
    "\n",
    "We decided to put our money where our mouth is and demonstrate the principles we covered a couple of weeks ago in action."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1: Viterbi Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "First, implement the Viterbi algorithm for finding the optimal state (tag) sequence given the sequence of observations (words). <br><br>\n",
    "In order to test your implementation, verify that you compute the correct state sequence for some examples from Eisner's ice cream model (see lecture) for which the solutions are known.<br><br>\n",
    "Demonstrate that your algorithm computes the correct state sequence for ['3','1','3'] as in the lecture.<br><br>\n",
    "Make sure that your algorithm is correct before proceeding to the other tasks! In order to do this, please also test your module with a longer observation sequence.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "EISNER_STATES = ['C','H']\n",
    "EISNER_INITIAL_PROBS = {'C': 0.2, 'H': 0.8}\n",
    "EISNER_TRANSITIONS = {'C': {'C':0.6, 'H': 0.4}, 'H': {'C':0.3, 'H':0.7}}\n",
    "EISNER_EMISSIONS = {'C': {'1':0.5,'2':0.4,'3':0.1},'H': {'1':0.2, '2':0.4,'3':0.4}}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introducing Assertions\n",
    "\n",
    "Python's `assert` statement is a very handy way to ensure the code you write passes some sanity checks.\n",
    "The way it works is very simple: it does nothing if the expression that follows it is `True` and it raises an exception if that expression is `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-6e6df518a476>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "assert False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Assertions are in fact the way our final solution will be tested, so it's good to also use them while working our way up to it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Making the Problem Concrete\n",
    "\n",
    "Throughout this notebook we will be developing our code against a specific example.\n",
    "\n",
    "It's the same as the test:\n",
    "Given the input sequence `[\"3\", \"1\", \"3\"]` we expect the corresponding sequence of labels to be `[\"H\", \"H\", \"H\"]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Break the Problem Down Further\n",
    "\n",
    "Even having made the problem concrete we can still simplify it even more.\n",
    "This will make it easier for us to pivot and get into writing some code.\n",
    "\n",
    "Let's consider namely the \"base case\" from the slides about the viterbi algorithm (page 43).\n",
    "The math $V_1 (j) =  b_j(y_1) \\cdot a_{0j}$ in our specific case translates to the following english:\n",
    "\n",
    "*multiply the initial probability of state \"H\" by the probability of emitting \"3\" given the state \"H\"*\n",
    "\n",
    "If we look up the numbers from the `EISNER_` constants provided, we arrive at the following numbers:\n",
    "\n",
    "$$0.8 \\cdot 0.4$$\n",
    "\n",
    "Let's make an assertion about them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert base_case('H', '3') == (0.8 * 0.4, 'H')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we run this cell right away we will be told that `base_case` is undefined. Let's fix that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def base_case(state, observation):\n",
    "    return (EISNER_INITIAL_PROBS[state] * EISNER_EMISSIONS[state][observation], state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now if we run the assertion cell, it should pass silently. Hooray, we got the first step!\n",
    "\n",
    "Well, almost. We still need to apply our function to all the states. For now we can simply build a dictionary with it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'C': (0.020000000000000004, 'C'), 'H': (0.32000000000000006, 'H')}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob0 = {state: base_case(state, '3') for state in EISNER_STATES}\n",
    "prob0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the base step taken care of, it's time to tackle the inductive step from the slides.\n",
    "Again, in english that formula reads:\n",
    "\n",
    "*\n",
    "For every state in the previous time step take its probabilty/score and multiply it with\n",
    "* the probability of transitioning from this previous state to the state in the current timestep\n",
    "* the probability of emitting the current observed token given the current state.\n",
    "\n",
    "Take the maximum of all these values.\n",
    "*\n",
    "\n",
    "Just as with the base case, we can plug actual numbers into this and make an assertion about our concrete example using `prob0` which we already computed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert inductive_step(prob0, 'H', '1') == (0.32000000000000006 * 0.7 * 0.2, 'H')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Something about sorting tuples by first element..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max([(1, 2), (2, 3)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 3)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted([(1, 2), (2, 3), (2, 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def inductive_step(previous_paths, current_state, current_obser):\n",
    "    return max((previous_paths[state][0]\n",
    "               * EISNER_TRANSITIONS[state][current_state] \n",
    "               * EISNER_EMISSIONS[current_state][current_obser], state)\n",
    "               for state in previous_paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'C': (0.04800000000000001, 'H'), 'H': (0.044800000000000006, 'H')}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob1 = {state: inductive_step(prob0, state, '1') for state in prob0}\n",
    "prob1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'C': (0.0028800000000000006, 'C'), 'H': (0.012544000000000003, 'H')}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob2 = {state: inductive_step(prob1, state, '3') for state in prob1}\n",
    "prob2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'C': (0.020000000000000004, 'C'), 'H': (0.32000000000000006, 'H')}\n",
      "{'C': (0.04800000000000001, 'H'), 'H': (0.044800000000000006, 'H')}\n",
      "{'C': (0.0028800000000000006, 'C'), 'H': (0.012544000000000003, 'H')}\n"
     ]
    }
   ],
   "source": [
    "print(prob0)\n",
    "print(prob1)\n",
    "print(prob2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have basically built our trellis already! Putting it all together is relatively easy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def trellis(observations):\n",
    "    trel = [{state: base_case(state, observations[0]) for state in EISNER_STATES}]\n",
    "    for indx, obs in enumerate(observations[1:], 1):\n",
    "        trel.append({state: inductive_step(trel[indx - 1], state, obs) for state in trel[indx - 1]})\n",
    "    return trel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'C': (0.020000000000000004, 'C'), 'H': (0.32000000000000006, 'H')},\n",
       " {'C': (0.04800000000000001, 'H'), 'H': (0.044800000000000006, 'H')},\n",
       " {'C': (0.0028800000000000006, 'C'), 'H': (0.012544000000000003, 'H')}]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trellis(['3', '1', '3'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to implement the back-tracking through the trellis.\n",
    "The algorithm in english looks something like this:\n",
    "\n",
    "*Look at the trellis.\n",
    "\n",
    "* for the last row, find max\n",
    "* for the max, take 2nd tuple elem, that's the pointer\n",
    "* go to prev row, look up pointer\n",
    "* in this pointer get the next pointer\n",
    "* rinse and repeat\n",
    "\n",
    "All the while we keep collecting the pointers into a list.\n",
    "\n",
    "This time we don't define any assertions of our own and simply stick to the ones for the `eichner_viterbi` ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'C': (0.04800000000000001, 'H'), 'H': (0.044800000000000006, 'H')}"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.044800000000000006, 'H')"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t[1][pointer]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use tuple unpacking to get the next pointer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(prob, state), pointer = max((val, key) for key, val in t[-1].items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((0.012544000000000003, 'H'), 'H')"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " max((val, key) for key, val in t[-1].items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def eisner_viterbi(observations):\n",
    "    t = trellis(observations)\n",
    "    (prob, state), pointer = max((val, key) for key, val in t[-1].items())\n",
    "    states = [state]\n",
    "    for step in reversed(t[:-1]):\n",
    "        states.append(pointer)\n",
    "        pointer = step[pointer][1]\n",
    "    return list(reversed(states))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['H', 'H', 'H']"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eisner_viterbi(['3', '1', '3'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert eisner_viterbi([\"3\", \"1\", \"3\"]) == [\"H\", \"H\", \"H\"]\n",
    "\n",
    "# from slack\n",
    "assert eisner_viterbi([\"2\", \"1\", \"3\", \"2\", \"1\", \"1\", \"2\"]) == [\"H\", \"H\", \"H\", \"H\", \"C\", \"C\", \"C\"]\n",
    "\n",
    "# from slack\n",
    "assert (eisner_viterbi([\"3\", \"1\", \"3\", \"1\", \"1\", \"3\", \"1\", \"1\", \"1\", \"3\", \"3\", \"3\", \"2\", \"2\", \"2\", \"1\", \"1\"]) ==\n",
    "                       [\"H\", \"H\", \"H\", \"C\", \"C\", \"H\", \"C\", \"C\", \"C\", \"H\", \"H\", \"H\", \"H\", \"H\", \"H\", \"C\", \"C\"] )"
   ]
  }
 ],
 "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}