HMM warmup (optional).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Intro to Hidden Markov Models (optional)\n",
    "---\n",
    "### Introduction\n",
    "\n",
    "In this notebook, you'll use the [Pomegranate](http://pomegranate.readthedocs.io/en/latest/index.html) library to build a simple Hidden Markov Model and explore the Pomegranate API.\n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "**Note:** You are not required to complete this notebook and it will not be submitted with your project, but it is designed to quickly introduce the relevant parts of the Pomegranate library that you will need to complete the part of speech tagger.\n",
    "</div>\n",
    "\n",
    "The notebook already contains some code to get you started. You only need to add some new functionality in the areas indicated; you will not need to modify the included code beyond what is requested. Sections that begin with **'IMPLEMENTATION'** in the header indicate that you need to fill in code in the block that follows. Instructions will be provided for each section, and the specifics of the implementation are marked in the code block with a 'TODO' statement. Please be sure to read the instructions carefully!\n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "**Note:** Code and Markdown cells can be executed using the `Shift + Enter` keyboard shortcut. Markdown cells can be edited by double-clicking the cell to enter edit mode.\n",
    "</div>\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "**Note:** Make sure you have selected a **Python 3** kernel in Workspaces or the hmm-tagger conda environment if you are running the Jupyter server on your own machine.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Jupyter \"magic methods\" -- only need to be run once per kernel restart\n",
    "%load_ext autoreload\n",
    "%aimport helpers\n",
    "%autoreload 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# import python modules -- this cell needs to be run again if you make changes to any of the files\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "from helpers import show_model\n",
    "from pomegranate import State, HiddenMarkovModel, DiscreteDistribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Build a Simple HMM\n",
    "---\n",
    "You will start by building a simple HMM network based on an example from the textbook [Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu/).\n",
    "\n",
    "> You are the security guard stationed at a secret under-ground installation. Each day, you try to guess whether it’s raining today, but your only access to the outside world occurs each morning when you see the director coming in with, or without, an umbrella.\n",
    "\n",
    "A simplified diagram of the required network topology is shown below.\n",
    "\n",
    "![](_example.png)\n",
    "\n",
    "### Describing the Network\n",
    "\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "$\\lambda = (A, B)$ specifies a Hidden Markov Model in terms of an emission probability distribution $A$ and a state transition probability distribution $B$.\n",
    "</div>\n",
    "\n",
    "HMM networks are parameterized by two distributions: the emission probabilties giving the conditional probability of observing evidence values for each hidden state, and the transition probabilities giving the conditional probability of moving between states during the sequence. Additionally, you can specify an initial distribution describing the probability of a sequence starting in each state.\n",
    "\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "At each time $t$, $X_t$ represents the hidden state, and $Y_t$ represents an observation at that time.\n",
    "</div>\n",
    "\n",
    "In this problem, $t$ corresponds to each day of the week and the hidden state represent the weather outside (whether it is Rainy or Sunny) and observations record whether the security guard sees the director carrying an umbrella or not.\n",
    "\n",
    "For example, during some particular week the guard may observe an umbrella ['yes', 'no', 'yes', 'no', 'yes'] on Monday-Friday, while the weather outside is ['Rainy', 'Sunny', 'Sunny', 'Sunny', 'Rainy']. In that case, $t=Wednesday$, $Y_{Wednesday}=yes$, and $X_{Wednesday}=Sunny$. (It might be surprising that the guard would observe an umbrella on a sunny day, but it is possible under this type of model.)\n",
    "\n",
    "### Initializing an HMM Network with Pomegranate\n",
    "The Pomegranate library supports [two initialization methods](http://pomegranate.readthedocs.io/en/latest/HiddenMarkovModel.html#initialization). You can either explicitly provide the three distributions, or you can build the network line-by-line. We'll use the line-by-line method for the example network, but you're free to use either method for the part of speech tagger."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# create the HMM model\n",
    "model = HiddenMarkovModel(name=\"Example Model\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **IMPLEMENTATION**: Add the Hidden States\n",
    "When the HMM model is specified line-by-line, the object starts as an empty container. The first step is to name each state and attach an emission distribution.\n",
    "\n",
    "#### Observation Emission Probabilities: $P(Y_t | X_t)$\n",
    "We need to assume that we have some prior knowledge (possibly from a data set) about the director's behavior to estimate the emission probabilities for each hidden state. In real problems you can often estimate the emission probabilities empirically, which is what we'll do for the part of speech tagger. Our imaginary data will produce the conditional probability table below. (Note that the rows sum to 1.0)\n",
    "\n",
    "| |  $yes$  | $no$ |\n",
    "| --- | --- | --- |\n",
    "| $Sunny$ |   0.10  | 0.90 |\n",
    "| $Rainy$ | 0.80 | 0.20 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Looks good so far!\n"
     ]
    }
   ],
   "source": [
    "# create the HMM model\n",
    "model = HiddenMarkovModel(name=\"Example Model\")\n",
    "\n",
    "# emission probability distributions, P(umbrella | weather)\n",
    "sunny_emissions = DiscreteDistribution({\"yes\": 0.1, \"no\": 0.9})\n",
    "sunny_state = State(sunny_emissions, name=\"Sunny\")\n",
    "\n",
    "# TODO: create a discrete distribution for the rainy emissions from the probability table\n",
    "# above & use that distribution to create a state named Rainy\n",
    "rainy_emissions = DiscreteDistribution({\"yes\": 0.8, \"no\": 0.2})\n",
    "rainy_state = State(rainy_emissions, name=\"Rainy\")\n",
    "\n",
    "# add the states to the model\n",
    "model.add_states(sunny_state, rainy_state)\n",
    "\n",
    "assert rainy_emissions.probability(\"yes\") == 0.8, \"The director brings his umbrella with probability 0.8 on rainy days\"\n",
    "print(\"Looks good so far!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **IMPLEMENTATION:** Adding Transitions\n",
    "Once the states are added to the model, we can build up the desired topology of individual state transitions.\n",
    "\n",
    "#### Initial Probability $P(X_0)$:\n",
    "We will assume that we don't know anything useful about the likelihood of a sequence starting in either state. If the sequences start each week on Monday and end each week on Friday (so each week is a new sequence), then this assumption means that it's equally likely that the weather on a Monday may be Rainy or Sunny. We can assign equal probability to each starting state by setting $P(X_0=Rainy) = 0.5$ and $P(X_0=Sunny)=0.5$:\n",
    "\n",
    "| $Sunny$ | $Rainy$ |\n",
    "| --- | ---\n",
    "| 0.5 | 0.5 |\n",
    "\n",
    "#### State transition probabilities $P(X_{t} | X_{t-1})$\n",
    "Finally, we will assume for this example that we can estimate transition probabilities from something like historical weather data for the area. In real problems you can often use the structure of the problem (like a language grammar) to impose restrictions on the transition probabilities, then re-estimate the parameters with the same training data used to estimate the emission probabilities. Under this assumption, we get the conditional probability table below. (Note that the rows sum to 1.0)\n",
    "\n",
    "| | $Sunny$ | $Rainy$ |\n",
    "| --- | --- | --- |\n",
    "|$Sunny$| 0.80 | 0.20 |\n",
    "|$Rainy$| 0.40 | 0.60 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Great! You've finished the model.\n"
     ]
    }
   ],
   "source": [
    "# create edges for each possible state transition in the model\n",
    "# equal probability of a sequence starting on either a rainy or sunny day\n",
    "model.add_transition(model.start, sunny_state, 0.5)\n",
    "model.add_transition(model.start, rainy_state, 0.5)\n",
    "\n",
    "# add sunny day transitions (we already know estimates of these probabilities\n",
    "# from the problem statement)\n",
    "model.add_transition(sunny_state, sunny_state, 0.8)  # 80% sunny->sunny\n",
    "model.add_transition(sunny_state, rainy_state, 0.2)  # 20% sunny->rainy\n",
    "\n",
    "# TODO: add rainy day transitions using the probabilities specified in the transition table\n",
    "model.add_transition(rainy_state, sunny_state, 0.4)  # 40% rainy->sunny\n",
    "model.add_transition(rainy_state, rainy_state, 0.6)  # 60% rainy->rainy\n",
    "\n",
    "# finally, call the .bake() method to finalize the model\n",
    "model.bake()\n",
    "\n",
    "assert model.edge_count() == 6, \"There should be two edges from model.start, two from Rainy, and two from Sunny\"\n",
    "assert model.node_count() == 4, \"The states should include model.start, model.end, Rainy, and Sunny\"\n",
    "print(\"Great! You've finished the model.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize the Network\n",
    "---\n",
    "We have provided a helper function called `show_model()` that generates a PNG image from a Pomegranate HMM network. You can specify an optional filename to save the file to disk. Setting the \"show_ends\" argument True will add the model start & end states that are included in every Pomegranate network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAATwAAACICAYAAAB6KVfRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvAOZPmwAAIABJREFUeJzt3XlYVOX7P/D3DAMMi4LsiwLCAEoGsYqCmqJmqamJpmWZmpmYlZlZWdniRyu1b5uWZmmbkgvmUmKCgomRiCQaKCCggOz7vs39+2N+5wQKOsLMHGCe13XN5Xg4c849w8M95zyriIjAMAyjDcRCB8AwDKMpLOExDKM1WMJjGEZrsITHMIzWYAmPYRitwRIewzBagyU8hmG0Bkt4DMNoDZbwGIbRGizhMQyjNSQaPh8bx8YwjDqIlNmJXeExDKM1WMJjGEZrsITHMIzWYAmPYRitoelGi14pJycHAPDXX38hNTUVWVlZyM7ORl5eHgCgtrYWdXV1qK2tBRFBX18fACCVSmFubg5LS0s4ODgAAGQyGTw8PODn5weZTAaRSKm6VoZBRUUFACA+Ph4XL15EdnY2srKycOPGDQBAdXU1Xxabm5sBAHp6etDX18eAAQNgYWEBe3t7AIpy6O7uDh8fH9x///3Q09MT5k1pmEjDE4D2+FbahoYGAEBkZCT27duH2NhYPrFJJBK4ubnB0dERTk5OGDhwIADA2NgYhoaGMDQ0hFgsRmNjIwCgvr4epaWlKC4uRnZ2NgDg2rVruHr1Kpqbm2FpaYmQkBAAwJQpUzBt2jQYGxtr+B0zPRH3d/nXX39h7969OHHiBFJTU/mfOTk5YfDgwXBycoKjoyMAwMTEhC+Hurq6AICmpiY0NDSgvLwcJSUlfHLMzMxEamoqampqYGBggFGjRgEAJk2ahFmzZvFluxdhrbQMwzBtsSu8/+/q1avYtGkTfvnlFwBAXV0dRo0ahUceeQSBgYEAAD8/PxgYGHT7XI2NjUhOTsbp06dx4sQJAMDJkychkUgwa9YsvPTSSwAAHx+fbp+L6V3KysqwZcsWbN++HQCQm5sLDw8PTJs2DUFBQQCA4cOHw8LCotvnksvlSE9PR1xcHKKiogAAx44dQ2VlJcaNG4fly5cDAKZOnQqxuMdfGylXN0REmnz0OBkZGfTYY4+RWCymIUOG0JYtW2jLli1UWFio0TjKyspo27Zt5OXlRVB8MdDUqVPp8uXLGo2DEUZVVRW9+uqrZGRkRObm5rRmzRpas2YNpaamajSOxsZGOnz4ME2ePJlEIhGJRCIaNmwYHTlyRKNxdIFSOUgrE15TUxOtW7eO1q1bR1KplDw9Penw4cMkl8uFDo2IiCIjIykyMpJ8fHxIV1eX1qxZQ01NTUKHxahBREQERUREkL29PVlYWNAXX3xBtbW1QodFRESpqamUmppKoaGhBIBmzJhBBQUFQofVGZbwOlJUVESjR48mY2NjMjY2ps2bN1Nzc7PQYXWotbWVvvzySzI2NqYRI0ZQXl4e5eXlCR0WowItLS304osv8ldRixcvptLSUqHD6lR0dDQ5OzuTra0tnTlzhs6cOSN0SLdSKgf1+BtzhmEYVdGqRov09HRMnDgROjo6OHToEADgvvvuEzIkpaSmpuKxxx5DfX09ACA6OhouLi4CR8V0VX19PaZPn464uDjs2rULABAaGipsUEqorKzE/PnzERkZCQDYt28fpk6dKnBUPKUaLbQi4d28eRMAEBQUBGtraxw7dgwDBgwQIpQuKy0txcMPPwwAKCwsRHx8PGxtbQWOirkXLS0tAIDp06cjPj4e0dHR8PLyEjiqeyOXy7F06VIAwM6dOxEZGYlx48YJHBUAlvAUGhsbMXz4cACKAnf69GmYmZlpOgyVKCsrAwCMHDkSJiYmiIuLg0TCBsv0FmFhYQCAH3/8ESdPnoS/v7/AEXUNlzOeeOIJREZGIikpCU5OTsIGxbqlKKxevZr69etH/fr1o6ysLCFCULnU1FQyNDSkd955R+hQGCVFRkby3Y327dsndDgqUV9fT8OGDaNRo0aRXC4XupeDUjmoT1/hJScnw8fHB19//TUA4Nlnn9Xk6dXq008/xeuvv44rV64AQE/4hmU60djYCFdXVwQHBwMAdu/eLXBEqpOUlAQ/Pz/8+OOPABRXfQJhQ8sYhmHa6tNXeHPmzMGVK1fwzz//aPK0GtHc3AwPDw++wnjbtm0CR8R0Zvv27XjxxReRmZkJALCzsxM4ItVasGAB4uLiACiGaAo0A5B21+FlZ2eTjo4O7dmzR5On1agvv/ySDAwMyMDAgCoqKoQOh+mEq6srLV68WOgw1Obff//l6ycjIyOFCkOpHNRnm/gOHjyIfv369Yr+Tco4fPgwkpOTAQAODg5wdHREcHAwP+/ZkSNHMG/ePCFDZDqQnJyM9PR0/PTTT0KHohKpqan4+eefAQCOjo5wcHCAg4MD3+L8yy+/4KGHHhIyxDvqs7e0EyZMgLm5OcLDwzV1SrXas2cPXyEsEolw6+/NzMwMgwcPhkwm4wsiAIwfPx7u7u4aj5dR2LBhAz777DPk5+f3icleCwsLYWNjA6DjcmhoaAgnJyfIZLJ2c/X5+vpizJgx6gyNNVowDMO01WdvaRMSErBhwwahw1CZESNG8M87uiovKytDWVkZLly4ALFYDLlcDgD8LLmMMBISEjBq1Kg+cXUHANbW1nyjCzeCqa26ujqkpKQgJSUFEomEH12ybds2dV/hKaVPJrzS0lJUVlZCJpMJHYrKODk58SNEuBEXHSEiiEQivu6S3c4KKyMjA5MnTxY6DJUaPXo0AMVY2tbW1k73a2lpgbW1NQDgmWee0URod9UnEx636A5Xf9BXcB1Xjxw50uFVHqelpQXvvPOOpsJi7iA3N7fPlUNu5uX9+/ffcT+xWIy33noLAHrMIkF9MuFxyUBHR0fgSFSLK2jHjh3jW2dvJZFIMHnyZAwbNkyToTGdkMvlfa4ccksecLernTEzM+txo5v6ZMLjcPVYfQVXj9dZsgMUhXDt2rWaCom5i45aMns7boYXPT09NDU1dbiPjo4O3nzzTUilUk2GdleslZZhGK3RJxMet6JTcXGxwJGolp+fH/z8/DpdQUoikeDhhx+Gt7e3hiNjOmNhYYGioiKhw1ApXV1d6Orq3nFVvX79+mHJkiUajEo5fTLhDRw4EPr6+sjIyBA6FJUyMDCAgYFBp/VzLS0tePfddzUbFHNHLi4ufa4cckaPHt1hY4SOjg5ef/11GBoaChDVnfXJhCcSiSCTyZCSkiJ0KGoxevRofmV5jkQiQUhICAICAgSKiumIm5tbny2HgYGBHdbhGRoaYtmyZQJEdHd9MuEBiqRw8uRJocNQixEjRtzWQtbS0oL33ntPoIiYzowePRoXLlxAZWWl0KGoXNvO8ByJRIJVq1bB2NhYgIjurs8mPIZhmFv12ckDIiIiMGvWLJSUlHRpwZ6ysjKkpaUhLS0N165dAwAUFBSgqKgIhYWFKC4uRm1tLQDFjLaNjY1oaGiASCSCvr4+AEBfXx9SqRRGRkawtLQEoBiaY2VlBRsbG8hkMri5uQEAXF1dlY4zKysLzs7OAP7raxgUFITY2Nh7fp+MepWVlcHS0hIHDhzA9OnTlX4d93eZl5eHjIwMpKenIzs7GwBQVFSE4uJi/t+6ujoA/5XDxsZGfgSEvr5+uwdXxqysrGBpaQkrKyvY2dnxo5JkMhlcXFyUrn+zs7NDfn4+/38jIyPk5eXBxMRE6feqItq9iE9lZSWsra2xZcsWLFq0qNP9CgsL8ffff+PcuXM4d+4cLly4AEAxPA1QFBguudjZ2cHKyop/cJftXGGSSqUgIjQ2NgIAGhoa0NjYiJqaGr6lrqioCEVFRbh58yYyMzPb1YFYWlrC19eXr4cLCAhAQEAAnyzbMjMzQ3l5Of//U6dO4cEHH+zqx8Wo0ciRIzF48GB+WqW2uKqJ5ORkJCYm4vz580hMTMS///4LQFGGAMDY2Jgvh9bW1rC0tOQft5ZDfX19/ouwbRJsaGjghyUWFxfzSTMnJwd5eXkA/huaaG9vz7fC+vn5wdfXF/7+/reVxTlz5mDfvn18z4E33ngD77//vuo+POVpd8IDgCeffBLXrl1DfHw8AMUv//Tp0zh+/Dj++OMPAMClS5cgEong5uYGf39/fl6voUOHws3NDYMGDeq0G0h3tba24saNGwCAtLQ0pKamIiEhAQkJCQDAt+55eXnhoYce4ucZCwoKwsyZM3H06FF+RTbuPTI9z44dO7B8+XJ+sH1eXh6ioqIQFRXFX5XX1NTA2NgY3t7e8PHxwQMPPABAceUvk8n4ManqwiXWzMxMZGRkICUlBYmJiQCAxMREZGVlAQCGDRuG8ePHAwBCQkKQmpqK1157DQYGBgAUQ+kEWhWQJbyoqChMmzaNH7wdGRmJ6upqeHh4YOLEiQCAiRMn8sse9jTl5eWIi4vjE3RaWhoAwNTUFDKZDOfPn8exY8cAAJMmTRIyVOYOTp8+jQkTJsDU1BSA4irfzMwMY8eORUhICADgwQcfhLu7u9q+XLurvLwcf/31F6KjoxEdHQ1AcVUqkUjQ3NyMKVOmAAB+/vln9O/fX4gQ2Xx4DMMwbfXJK7zc3Fxs3boVO3bsQHFxMX/bN3fuXMycORMDBw7URBgqx1Va79+/H9988w3S0tJga2sLAHjuuefw/PPP87PRMsLhRvh8++23+Oabb5CZmQlHR0c8/vjjAIDQ0FD4+vr22Ks5ZRUXF+PXX3/FsmXL2k3YMW3aNCxdulTTdcradUubmJiIjz76CIBiPQsLCwssWbIE8+fPx+DBg9V1WsHU1dUhPDycr+f75ptvUFVVhVmzZmH16tW4//77BY5Q+yQmJuKTTz7hp00yNDTE/PnzMX/+/D493O/gwYMYO3YsAEXviO3bt+Pvv//G0KFD+Q7IixYtUvdEAtqxallKSgrNnDmTRCIR+fn5kZ+fH+3evZuamprUcboeq6GhgXbt2kWenp4kFovpiSeeoCeeeILS09OFDq3PO3/+PE2dOpUAkI+PD+3cuZN27txJdXV1QocmmKSkJFqyZAlJpVKSSqVka2tLn332GdXX16vrlErloF6Z8CorKyksLIzCwsJIR0eHPD096ddff1XV4Xs1uVxOe/fupaFDh9LQoUNJIpHQK6+8QjU1NUKH1qfk5ORQaGgohYaGEgAaPnw4HT16VOiwepybN2/SzZs3acWKFWRoaEj29va0Z88edSyf2jcT3sGDB8nOzo4sLCzIwsKCdu3aRXK5XBWH7lNaW1uptbWVvv76azI1NSUnJyc6duyY0GH1es3NzfTxxx+TkZERubi4kIuLCx05ckTosHqFgoICWrhwIYlEIhKJRDRu3DhKTU1V1eGVykG9u9aUYRjmXiibGVX06LKGhgZ67rnnCAAtWLCASkpKqKSkpDuH1BoFBQU0d+5cAkAvv/wyvfzyy9Tc3Cx0WL1KVlYWZWVl0fDhw8nAwIA++OADamhooIaGBqFD63Xi4+MpPj6efH19SSqV0ldffaWKw/aNW9rs7GzKzs4mX19fMjExoQMHDnTlMAwR/fjjj2RkZERGRkYUFBREN2/eVNmxL168SBcvXqQXXniBWlpaVHbcnmD//v1kYmJCJiYm5OnpSf/++6/QIfUJzc3N9NZbb5FYLKbQ0FCqrKykysrKrh6u9ye8lJQUsrOzIzs7O/L09KSMjIx7PQRzi5SUFEpJSSF3d3caPHgwXbt2rcvHqq6uph07dpC3tzdB0eWIAHSn0PY4GzduJJFIxDeSsSs61YuJiSEbGxvy8vIiLy+vrn4R9+6El5SURJaWlhQUFERBQUFUXl7elQ+B6URxcTH5+vqSnZ0dpaamKl15nJCQQAkJCbR48WKSSqUkFotJJBK1S3j5+flqjl4zXn31VRKJRPR///d/QofS52VlZZG7uzv/RdyF7lRK5SDWaMEwjPZQNjOq6KGUGzdukI2NDYWEhFBtbS3V1tbea7ZnlFBZWUkjR44kBwcHcnBwoMLCwg73q6iooC1btpCHhwd/Faerq9vuqq7tozu3yT3F2rVrSUdHh8LDw4UORWtwDZH+/v7k5OREBQUF9/JypXJQjxtaVltbi+DgYDQ3N+Ps2bNCzbygNUpLS/mxxtbW1jh58iT09fURFxeHbdu2AQB++eUXtLS0/FcPcheXLl3qtQuB79q1CwCwYMECbN++HYsXLxY2IC1UUlLCz2AUGxur7GSkvXMsbVhYGPbu3YvExEQ4OjpqIiatd/XqVQCKiR79/f1x48YNXLt2DRKJYp32u60wfysnJyfo6uqipaWFfy33vKWlhV9IvO3PAcXiS7c+72gbt0xg2+e3btPT0+O3cXO1GRgYQCqVwsDAAIaGhjAyMgKgmKXX2NgYlZWV2LhxIwBg1apVWLdu3T29b0Z1MjMzERAQgMmTJ+P7779X5iW9K+GdPXsWABAcHIwffvgB8+bN01hQ2u7cuXMAgBkzZvCTVHbHM888A1dXV0gkEj5pcs872sYlsrZlkXt+6zYiapc0m5ub0dzcjKamptu2cdu5yS3r6+vbPWpqagAo7ipqamqQn5/PD/KPi4vjZw1mhLFv3z7Mnj0bhw4dAgA8+uijd9qdzYfHMAzTVo+4wiMi/pvV1taWn8WX0Swigp+fH0pLS2FlZYXz588D+O9WUi6XK3Wc3377DY888oja4lSHzz//HKtXr8Y///wDAHB3dxc4IgYAHn/8cX7Jg6tXr962HnMbSl3hSVQUV7ccPXoUFy9eBKCY102V8vPzERMT0+nPbWxs4O7uDjs7u26fKzMzE+vWreMXMeltE42KRCJs2rQJ48aNw65du3DfffcBUPx+IiIicOLECX6BIl1dXf4W8lbcKlq9RWNjIzZs2ICwsDC1JjpuwaYff/wRly5dwqBBgxAcHAwAGDBgAEpLSztc61Wbbdy4kV/Zb9euXd1uROoRV3hTpkzh61PulJy6Qi6X8wvcPPzww6iqqsKiRYv4xXrS0tJw+PBh1NXVYefOnfxaF12xf/9+zJo1C7///jt/vt7I19cXbm5u2LNnT7vt9fX1iIqKAgAcOnQIBw8eRFlZWbvkJxKJsGvXLjz99NMaj7urdu/ejfnz5yM7Oxv29vZqOUddXR1GjhwJQPElu2rVKuTk5OCHH34AoFh1bvPmzXjllVfUcv7ebMGCBQCACxcu8BdGHegdE4BWVlaSnp4e/fDDD/TDDz/cS7+bexYSEkIA6Ny5c+22V1RUkIeHB4lEIkpKSqKkpKQun6O4uLi7YQpuy5YtZGxsfNfB8XK5nP766y964403yNXVlVxdXQmAqgaDa8zUqVNp8uTJaj3H+vXrSSwWk1gsppycnNt+vnjxYlq5cqVaY+itYmNjKTY2lgDcaURQ7xhpERcXh6amJkyaNEntK2/169evw+0mJiaYPn06iAhHjx7F0aNHu3wOCwuLLr+2p5g0aRJqamraLRnZEZFIhMDAQKxfv55ftDwjI6PXrI/b2tqK1tZWxMTE8Ktuqcs///wDuVwOuVyOqqqq237+4Ycf8mshM+0FBwcjODgYpqam/B1GVwme8BiGYTRF8EaLixcvwtHR8bYVzTWtoqICwJ072aalpSE+Ph7JyckICgrCjBkz2v1cLpcjNjaWXwmeqydsaWnBqVOnAABisRgjRozAkSNHcPXqVcyZMwcA4ObmhtLSUhw5coQ/nkgkgqenJ7y9vVFbW4tff/0VgKKf2dixY9XWMdvZ2RlmZmZ8fQlXsa4MFxcXtcSkDtwCSNXV1QgICFDruSZOnIi9e/cCAObPn4+DBw+2a9QyMzPj6+/y8/MREREBQPG7njBhAu677z6+DHG/l8ceewwODg78MXJychAREYHly5cjJSUFgKKu1cHBAU8++WS7VdJu3Zfr69Z2X+6KkyuTbcsjAL5McuURgFrKJBe3n58fLly40K1jCZ7wbty4AScnJ0FjuHTpEg4cOAAjIyPMnTv3tp9/+umnABSF5+TJk7h+/TrGjh2LgoICAMDSpUuRkpKCtWvXYv/+/fjqq68AKBJeeXk5wsLCEB4eDgB48skn8d1338HS0hLh4eH4+uuvAQCXL1+Gubk5xGIx5s+fDwB46qmn+OdGRkZ8t5DY2Fh+u7o4OTnhxo0baj2H0K5fv84/d3Z2Vuu55s6dy7fenz9/Hj4+Pti8eTOeeuopfh9upTlbW1tYWVkBAGbPno0dO3bgvvvu45PKn3/+ibVr18LDwwMODg58Qlq0aBGKi4tBREhOTgagWErxrbfeQm5uLt54441O9+WWlmy7r7m5OQDwZbJteQT+K5OaKI+A4nfEfUl1mbKVfSp63Obpp5+mKVOmdKEq895Nnz6dANCqVavovffeo/fee49mzZpFgwcPptWrV3c6355MJiOZTEbLli1rd6xHHnmEHnnkEX5bcnIyX2nftuK+vr6eH1g/duxYfrbhw4cP89vbrovg4+NDPj4+5Ojo2G5m4qVLl9LSpUvp4sWLKvtMOjNmzBhatmxZu/fc1xw4cIAOHDhAAKi1tVXt5yssLKTCwkKaNGkS/3ufMGECTZgw4baGjMuXL9Ply5cJAO3YsaPdz7hyc/z48XbbX3/9dQJAUVFR7bb7+PiQr69vl/fltt9aHolIY+WRiGjlypUUEBDQ2Y97R6OFnp4e37dLU+zt7ZGbm4vc3Fzs27cP48aNw4cfftjp7VhMTAxiYmL4sZUpKSnIyclBeno60tPT+f309fU7fL1UKoVIJIJIJIKLiws/tMrDw4Pfp+3V1GuvvYbXXnsN169f59c4bW5uRkZGBjIyMuDp6dm9D0AJjY2N0NPTg56entrPJZS2708TZdDKygpWVlY4duwY9uzZA0tLS5w4cQInTpyAt7c33+m5q7gxw0OGDGm33cPD47ar9XvZF8Bt5RH4r0xqojwCit9RZ39jyhI84TEMw2iK4AnPxsZGJQPW78XIkSOxZcsWbNmyBUFBQfj222/x5Zdfdrq/vb097O3tce7cObz44otITU2Fi4sL382gq9oOTqc2HcBDQ0MRGhoKZ2dnbN68GQDw+++/49FHH73bAGqVuXnzJmxsbGBjY6OR8wnB1tYWtra2AIDc3FyNnnvOnDlISUnB+PHjMX78eJSUlGDVqlVqOZeOjo5S03rdad9byyPwX5nUlLy8vG6XR8EbLYYMGYL09HR+RgupVKqR83Jj8vbu3Qtvb2+sWLGiXcVwW2+//TYARWPB8ePHYWBggAMHDqgtNi4Rrly5EsuWLcPp06exb98+fPbZZ2o7Z1sVFRXIycm57Xanr+GGkeno6ODixYtwdXVVy3mysrKQnJyMadOmtdtuYWGB7777DgAwePBgxMTEoKKiAqampmqJozt0dHTalUcAGi2TgKIvY3cbRwS/wgsKCkJTUxPi4uIQFxen1nN19M1lZ2eH8PBwEBFmz56N7OxsZGdn8z/PysrCunXrsG7dOsybN4+v++jOlZ2yFixYAEtLS7z77rsQiUQwNzfnW87UKSYmBiKRCCNGjOg1Yzvj4uLg5eUFLy8vvPfee0rVhxkbG8PY2Bje3t44ceKE2mKzsLDAihUr0NjYeFtd4aBBgzBo0CA++XJ1VG2n0eIuBoTWtjy2LZPqlpmZiczMTGRlZWHUqFHdOpbgCc/JyQn3338/wsPD+a4b6sL1tWub0ABg7Nix+N///oeSkhJMmzYN06ZNQ3V1NQDwY3wBIDw8HFVVVfjzzz9x+vRplJeXo7y8HDU1NaiuruYLc0lJCUpKSvjX1dTU8K1E3ABybj9OfX39bfEaGBjghRdewKlTpzrsLqMu4eHhCAwMhKWlpeD9I5UllUqRnJyM5ORkfPDBB/D29oadnR1eeuklnDp1CqdOneq0j+WMGTMQERGhtoaLfv36oa6uDkuWLMGSJUvanefSpUu4dOkSUlJS8NRTT/FfqG5ubnBzc4OTkxPCw8Nx/fp1XLlyBVeuXMG+ffsAAElJSe2+eLkRHG3LGKAoZ42Nje2+8O9lX07b8qjJMrl7927s3r0b5ubmGD16dLeOJXjCYxiG0Rhl+6+o6NGhTz75hKRSKUml0k4XkumqvLw8evvtt+ntt98mPT09AkCenp60detW2rp1K7+fXC7n++lx+xw6dIiIiBYuXEgLFy4kiURCMpmMvv76a9q/fz/p6emRnp4ejRs3jo4fP06hoaEEgIYNG0bDhg2jo0ePUk1NDb344ov8cW1sbOjIkSOUl5dHM2bM4Ld7eXnR+fPnb4u/oKCAbG1tNba4dXZ2NkkkEvrmm280cj5VSUlJ6XBBobaLDfXr14+efPJJ2r9/P9XU1PCvzcvLI11dXfr222/VFl9ISAjNnDmTZs6cSUFBQbR8+XJavHgxmZubk7m5OYWFhXW4WNWOHTvI1NSUjI2Nae7cuTR37lyKjY2lgQMH0ssvv0xXr16lmJgYiomJIWdnZwJAzz77LOXn51N+fj7t2bOH+vfvTwDo3XffpaioKIqKirpt3z179ty2b3Nz82397rjyqKky2dDQQPb29mRvb0+vvvrqnXZVKgf1iOmhqqqq+NEWS5YswYYNGzQZk9Kqq6vbTUDA3Zp0t2/QnURFReHkyZNYv3692s7R1gsvvIADBw4gKytLYw1IqpCdnY3BgwffdT+JRIKWlhbo6uoiJCQEADBz5kycOnUKcXFx/JAsJReOUVp+fj7fIgwohnaVlJTwDSXccMSONDQ0oLm5mS97zc3N0NHRaTdUTFO48ghAI2Vy06ZNfKPhtWvX7jRvZe9a0+Lzzz8HoFg85cKFC/zkk9pu9uzZ2Lx5MwYNGqT2cyUkJGD48OEICAiAl5cX/0fYr18/GBkZwdDQkE8E3HN9ff12HXjb/r/tdu65WCzmZ1DmnnP/3rpdJBLxdVQtLS387Cbco+32goIC+Pr63tP7bZswiIif/QUAdu7cyU88yfyHK48A1F4m09PT8cADD2DlypUAwA/N60TvSnhcwQ4MDIRYLMaZM2f4Vipt8tJLL/E93S0sLKCrq4utW7eq9Zzclaq/vz+qq6vxwAMPoLqWf3JSAAAI1UlEQVS6mm+wqa6uRm1tLerq6vjZjOvr6zXSUq0JYrEYcrkcUqmUbxHdsWMHFi1aJHBkPQNXJjVVHgHFVeyYMWNQWVmJxMREAHftstZ7pngH/vu23blzJwIDAxEWFobt27cLHJXmFRYW8jNXtJ1hQ524GWVzc3ORkJCg9IwnjY2NaGhoQFNTE9/axz3nHlwy5VYVa9tZm6tXkcvl/L/cdu45Vy50dHQgkUigo6PDP7jt3PN7mdWFu7UFgDFjxmDJkiWYMWMG389r1apVGDFiRLvhf9qKK5OaKo8A8Oyzz+Ly5cs4e/asSqtWWCstwzDaQ9nWDRU9lHLo0CESi8X00UcfKfuSPuVuU6ur0ltvvUUSiYQkEsltM2f0NtwU6uigtRYASSQSAkBWVlb09ttvU1ZWFmVlZbU7BvfZBwcH06BBg+jGjRvCvJkeRlPlkYho9erVJJFIbpsN5i6UykE9MuEREX366ackEolo/fr1tH79+nt5KaOkN998k0QiEe3YseO2KYh6I65r061JTkdHh3R0dOjRRx+l3377TampoEpLS8nT05MGDhxIly9f1kD02q21tZXCwsIoLCyMdHR06Pvvv7/XQ/TuhEdEtHXrVhKJRCQSiWjlypUambOsr+P6Vi1ZsqSrBavHMjExIRMTExKJRASAnJyc6OOPP6aCggIqKCi45+NVVFTQ6NGjydTUlKKjoyk6OloNUTPV1dU0ffp0/gvr4MGDXTlM7094REQ//fQT/fTTTySVSikkJETlHZO1SW5uLgUFBVFQUBAZGRlRRESE0CGplJubG7m5udG8efPo9OnTKjlmfX09zZkzh79dXrNmzW2dcZmuS0hIIJlMRtbW1nT69Onu/N6UykGs0YJhGO2hbGZU0aPLLly4QM7OzmRra0u///57dw6llSIiIsjCwoKGDBlCQ4YMoX///VfokFSuvr6e6uvr1XLsbdu20bZt28jAwIACAwNZvV43NDY2UmNjI61bt450dXVp/PjxlJ+f393D9o1b2rbKy8tp7ty5BIAef/xxevzxx1XxQfVpN27coEcffZQA0MKFC6m6upqqq6uFDqvXunTpEg0fPpwkEgmtWLGCVqxYQZWVlUKH1WtERkbyVQ9GRka0ceNGVdXN972Ex/n999/J0dGRHB0dqX///vT+++9TVVWVqg7f65WXl9OaNWtozZo1ZGRkRK6urnTy5Emhw+oz5HI5bdu2jczMzMjMzIysrKxo06ZN7SYkYNo7e/Ysv3jRjBkzaMaMGaru8tN3Ex4RUU1NDdXU1NC6devIxMSEzM3N6aOPPqKPPvqIKioqVHmqXqOkpITef/99MjU15Wfh2Lhxo9pu87RdSUkJlZSU0OrVq8nY2JgsLS1pw4YN/HZtJpfLKSoqisaPH0/jx48nABQcHKzOlu6+nfDaKisro9dff5369+9P/fv3JyMjI3r++ee1op4lKSmJkpKSaOHChSSVSmnAgAH0zjvvUGVlJbvV0qDi4mJavXo1mZiY8N0r5s2bR2fOnBE6NI0qKSmhTZs2kZubGwGgMWPG0JgxYzTRqV2pHMRaaRmG0Ro9ZrYUVeCmZd+1axe++OILpKenw8/Pj5+Kevbs2Rg4cKA6Q9CI69ev81Pic2s3eHh4YPny5Xj66adVPpcbo7y6ujrs3r0bALB161YkJSXBxcUFs2bNQmhoKADc8zRWPVl5eTkOHTrETzsfFRUFfX19PPXUU1i6dCmGDRumqVB61/RQKj8REU6ePIndu3cjIiICAFBZWYnAwEBMnDgRDz30EAAgICCg3XKJPU1zczPi4+Pxxx9/4Pjx4wAU89aZm5sjNDQUTzzxBAB0e65/Rj0SExPxyy+/YP/+/cjKygIAODo6YuLEiQgJCcG4ceMAoFesHdLa2oqEhARER0cDAKKjo3HmzBmIxWL+72nWrFmYPn36HSc0VRPtTnhtcVMXHTt2DL/99huOHz/OzzlnYmKCwMBABAQEwN/fH35+fgDQbnZaTcnLy0NCQgISEhIAKBJbfHw8qqur4ezszBeqKVOmYMKECfxSk0zvwP1ejxw5gujoaJw7d46fyNTDwwN+fn7w9fWFr68vvLy8AABGRkYaj5OIkJmZiQsXLgBQJO3ExEScO3cOVVVVsLe3BwCEhIRg4sSJmDp1Kvr376/xOG/BEt6dXLlyBYDiEvzvv//GuXPnkJ6eDu7zMDU1haurK/8AFEnQ2toaVlZWsLS05L/F9PX1IZVK+aneuUkkuWX5ampqUFRUBEAxt1hRURFu3ryJ9PR0pKenA1DM7lpVVQWRSMSvB+vv74/AwEBMmDABMplMQ58MoylVVVWIjY0FAJw9exbnz59HYmIiysvL+X3s7Ozg4uICmUwGZ2dnAIC1tTUsLS35csglRX19ff7B3bVwcxJycxeWlZUBAIqKilBcXIzi4mLk5OQgIyMDAJCRkYHMzEw0NDTwxxg6dCj8/Pzg7++PsWPHYujQoZr5gO6NUgmPNVowDKM1tPYKryMVFRVISkoCAFy9ehVpaWlIS0vDtWvXACiuztp++3aFSCTCgAEDYGNjAxcXF37dBDc3N7i7u8Pb27sn3B4wAsrMzMTly5cBKK64uAe3nnJRUREqKyu7fR5dXV1YWlrCzs6Ov4OQyWSQyWRwd3eHp6cnANUvaKQm7JZWHZqamlBcXIyioiJ+fYeGhoZ2q8pzt7bcba6RkRGsrKwAKCqnWd0b011cOSwuLu6wHHJ1g21vc6VSKQYMGABAUQ5NTU0Fi18NWMJjGEZrsDo8hmGYtljCYxhGa7CExzCM1mAJj2EYraHphbiVqlhkGIZRB3aFxzCM1mAJj2EYrcESHsMwWoMlPIZhtAZLeAzDaA2W8BiG0Ros4TEMozVYwmMYRmuwhMcwjNZgCY9hGK3BEh7DMFqDJTyGYbQGS3gMw2gNlvAYhtEaLOExDKM1WMJjGEZrsITHMIzWYAmPYRitwRIewzBagyU8hmG0Bkt4DMNoDZbwGIbRGizhMQyjNf4fuQkOCtDQKoYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1058860f0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "show_model(model, figsize=(5, 5), filename=\"example.png\", overwrite=True, show_ends=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Checking the Model\n",
    "The states of the model can be accessed using array syntax on the `HMM.states` attribute, and the transition matrix can be accessed by calling `HMM.dense_transition_matrix()`. Element $(i, j)$ encodes the probability of transitioning from state $i$ to state $j$. For example, with the default column order specified, element $(2, 1)$ gives the probability of transitioning from \"Rainy\" to \"Sunny\", which we specified as 0.4.\n",
    "\n",
    "Run the next cell to inspect the full state transition matrix, then read the . "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The state transition matrix, P(Xt|Xt-1):\n",
      "\n",
      "[[0.  0.5 0.5 0. ]\n",
      " [0.  0.8 0.2 0. ]\n",
      " [0.  0.4 0.6 0. ]\n",
      " [0.  0.  0.  0. ]]\n",
      "\n",
      "The transition probability from Rainy to Sunny is 40%\n"
     ]
    }
   ],
   "source": [
    "column_order = [\"Example Model-start\", \"Sunny\", \"Rainy\", \"Example Model-end\"]  # Override the Pomegranate default order\n",
    "column_names = [s.name for s in model.states]\n",
    "order_index = [column_names.index(c) for c in column_order]\n",
    "\n",
    "# re-order the rows/columns to match the specified column order\n",
    "transitions = model.dense_transition_matrix()[:, order_index][order_index, :]\n",
    "print(\"The state transition matrix, P(Xt|Xt-1):\\n\")\n",
    "print(transitions)\n",
    "print(\"\\nThe transition probability from Rainy to Sunny is {:.0f}%\".format(100 * transitions[2, 1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inference in Hidden Markov Models\n",
    "---\n",
    "Before moving on, we'll use this simple network to quickly go over the Pomegranate API to perform the three most common HMM tasks:\n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "**Likelihood Evaluation**<br>\n",
    "Given a model $\\lambda=(A,B)$ and a set of observations $Y$, determine $P(Y|\\lambda)$, the likelihood of observing that sequence from the model\n",
    "</div>\n",
    "\n",
    "We can use the weather prediction model to evaluate the likelihood of the sequence [yes, yes, yes, yes, yes] (or any other state sequence). The likelihood is often used in problems like machine translation to weight interpretations in conjunction with a statistical language model.\n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "**Hidden State Decoding**<br>\n",
    "Given a model $\\lambda=(A,B)$ and a set of observations $Y$, determine $Q$, the most likely sequence of hidden states in the model to produce the observations\n",
    "</div>\n",
    "\n",
    "We can use the weather prediction model to determine the most likely sequence of Rainy/Sunny states for a known observation sequence, like [yes, no] -> [Rainy, Sunny]. We will use decoding in the part of speech tagger to determine the tag for each word of a sentence. The decoding can be further split into \"smoothing\" when we want to calculate past states, \"filtering\" when we want to calculate the current state, or \"prediction\" if we want to calculate future states. \n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "**Parameter Learning**<br>\n",
    "Given a model topography (set of states and connections) and a set of observations $Y$, learn the transition probabilities $A$ and emission probabilities $B$ of the model, $\\lambda=(A,B)$\n",
    "</div>\n",
    "\n",
    "We don't need to learn the model parameters for the weather problem or POS tagging, but it is supported by Pomegranate.\n",
    "\n",
    "### IMPLEMENTATION: Calculate Sequence Likelihood\n",
    "\n",
    "Calculating the likelihood of an observation sequence from an HMM network is performed with the [forward algorithm](https://en.wikipedia.org/wiki/Forward_algorithm). Pomegranate provides the the `HMM.forward()` method to calculate the full matrix showing the likelihood of aligning each observation to each state in the HMM, and the `HMM.log_probability()` method to calculate the cumulative likelihood over all possible hidden state paths that the specified model generated the observation sequence.\n",
    "\n",
    "Fill in the code in the next section with a sample observation sequence and then use the `forward()` and `log_probability()` methods to evaluate the sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "            Rainy      Sunny      Example Model-start      Example Model-end   \n",
      " <start>      0%         0%               100%                     0%          \n",
      "   yes       40%         5%                0%                      0%          \n",
      "    no        5%        18%                0%                      0%          \n",
      "   yes        5%         2%                0%                      0%          \n",
      "\n",
      "The likelihood over all possible paths of this model producing the sequence ['yes', 'no', 'yes'] is 6.92%\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# TODO: input a sequence of 'yes'/'no' values in the list below for testing\n",
    "observations = ['yes', 'no', 'yes']\n",
    "\n",
    "assert len(observations) > 0, \"You need to choose a sequence of 'yes'/'no' observations to test\"\n",
    "\n",
    "# TODO: use model.forward() to calculate the forward matrix of the observed sequence,\n",
    "# and then use np.exp() to convert from log-likelihood to likelihood\n",
    "forward_matrix = np.exp(model.forward(observations))\n",
    "\n",
    "# TODO: use model.log_probability() to calculate the all-paths likelihood of the\n",
    "# observed sequence and then use np.exp() to convert log-likelihood to likelihood\n",
    "probability_percentage = np.exp(model.log_probability(observations))\n",
    "\n",
    "# Display the forward probabilities\n",
    "print(\"         \" + \"\".join(s.name.center(len(s.name)+6) for s in model.states))\n",
    "for i in range(len(observations) + 1):\n",
    "    print(\" <start> \" if i==0 else observations[i - 1].center(9), end=\"\")\n",
    "    print(\"\".join(\"{:.0f}%\".format(100 * forward_matrix[i, j]).center(len(s.name) + 6)\n",
    "                  for j, s in enumerate(model.states)))\n",
    "\n",
    "print(\"\\nThe likelihood over all possible paths \" + \\\n",
    "      \"of this model producing the sequence {} is {:.2f}%\\n\\n\"\n",
    "      .format(observations, 100 * probability_percentage))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### IMPLEMENTATION: Decoding the Most Likely Hidden State Sequence\n",
    "\n",
    "The [Viterbi algorithm](https://en.wikipedia.org/wiki/Viterbi_algorithm) calculates the single path with the highest likelihood to produce a specific observation sequence. Pomegranate provides the `HMM.viterbi()` method to calculate both the hidden state sequence and the corresponding likelihood of the viterbi path.\n",
    "\n",
    "This is called \"decoding\" because we use the observation sequence to decode the corresponding hidden state sequence. In the part of speech tagging problem, the hidden states map to parts of speech and the observations map to sentences. Given a sentence, Viterbi decoding finds the most likely sequence of part of speech tags corresponding to the sentence.\n",
    "\n",
    "Fill in the code in the next section with the same sample observation sequence you used above, and then use the `model.viterbi()` method to calculate the likelihood and most likely state sequence. Compare the Viterbi likelihood against the forward algorithm likelihood for the observation sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The most likely weather sequence to have generated these observations is ['Rainy', 'Sunny', 'Rainy'] at 2.30%.\n"
     ]
    }
   ],
   "source": [
    "# TODO: input a sequence of 'yes'/'no' values in the list below for testing\n",
    "observations = ['yes', 'no', 'yes']\n",
    "\n",
    "# TODO: use model.viterbi to find the sequence likelihood & the most likely path\n",
    "viterbi_likelihood, viterbi_path = model.viterbi(observations)\n",
    "\n",
    "print(\"The most likely weather sequence to have generated \" + \\\n",
    "      \"these observations is {} at {:.2f}%.\"\n",
    "      .format([s[1].name for s in viterbi_path[1:]], np.exp(viterbi_likelihood)*100)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Forward likelihood vs Viterbi likelihood\n",
    "Run the cells below to see the likelihood of each sequence of observations with length 3, and compare with the viterbi path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The likelihood of observing ['no', 'no', 'yes'] if the weather sequence is...\n",
      "\t('Sunny', 'Sunny', 'Sunny') is 2.59% \n",
      "\t('Sunny', 'Sunny', 'Rainy') is 5.18%  <-- Viterbi path\n",
      "\t('Sunny', 'Rainy', 'Sunny') is 0.07% \n",
      "\t('Sunny', 'Rainy', 'Rainy') is 0.86% \n",
      "\t('Rainy', 'Sunny', 'Sunny') is 0.29% \n",
      "\t('Rainy', 'Sunny', 'Rainy') is 0.58% \n",
      "\t('Rainy', 'Rainy', 'Sunny') is 0.05% \n",
      "\t('Rainy', 'Rainy', 'Rainy') is 0.58% \n",
      "\n",
      "The total likelihood of observing ['no', 'no', 'yes'] over all possible paths is 10.20%\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "\n",
    "observations = ['no', 'no', 'yes']\n",
    "\n",
    "p = {'Sunny': {'Sunny': np.log(.8), 'Rainy': np.log(.2)}, 'Rainy': {'Sunny': np.log(.4), 'Rainy': np.log(.6)}}\n",
    "e = {'Sunny': {'yes': np.log(.1), 'no': np.log(.9)}, 'Rainy':{'yes':np.log(.8), 'no':np.log(.2)}}\n",
    "o = observations\n",
    "k = []\n",
    "vprob = np.exp(model.viterbi(o)[0])\n",
    "print(\"The likelihood of observing {} if the weather sequence is...\".format(o))\n",
    "for s in product(*[['Sunny', 'Rainy']]*3):\n",
    "    k.append(np.exp(np.log(.5)+e[s[0]][o[0]] + p[s[0]][s[1]] + e[s[1]][o[1]] + p[s[1]][s[2]] + e[s[2]][o[2]]))\n",
    "    print(\"\\t{} is {:.2f}% {}\".format(s, 100 * k[-1], \" <-- Viterbi path\" if k[-1] == vprob else \"\"))\n",
    "print(\"\\nThe total likelihood of observing {} over all possible paths is {:.2f}%\".format(o, 100*sum(k)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Congratulations!\n",
    "You've now finished the HMM warmup. You should have all the tools you need to complete the part of speech tagger project."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}