Hidden Markov Models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hidden Markov Models - A look at the Viterbi Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We consider a scenario where the internal states are 'Healthy' and 'Fever'. The observables are the symptoms - 'normal', 'cold' and 'dizzy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "states = ('Healthy', 'Fever')\n",
    "start_p = {'Healthy': 0.6, 'Fever': 0.4}\n",
    "trans_p = {\n",
    "   'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},\n",
    "   'Fever' : {'Healthy': 0.4, 'Fever': 0.6}\n",
    "   }\n",
    "emit_p = {\n",
    "   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},\n",
    "   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6}\n",
    "   }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The viterbi algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def viterbi(obs, states, start_p, trans_p, emit_p):\n",
    "     V = [{}]\n",
    "     for st in states:\n",
    "         V[0][st] = {\"prob\": start_p[st] * emit_p[st][obs[0]], \"prev\": None}\n",
    "      # Run Viterbi when t > 0\n",
    "     for t in range(1, len(obs)):\n",
    "          V.append({})\n",
    "          for st in states:\n",
    "              max_tr_prob = max(V[t-1][prev_st][\"prob\"]*trans_p[prev_st][st] for prev_st in states)\n",
    "              for prev_st in states:\n",
    "                 if V[t-1][prev_st][\"prob\"] * trans_p[prev_st][st] == max_tr_prob:\n",
    "                     max_prob = max_tr_prob * emit_p[st][obs[t]]\n",
    "                     V[t][st] = {\"prob\": max_prob, \"prev\": prev_st}\n",
    "                     break\n",
    "     for line in dptable(V):\n",
    "         print(line)\n",
    "     opt = []\n",
    "     # The highest probability\n",
    "     max_prob = max(value[\"prob\"] for value in V[-1].values())\n",
    "     previous = None\n",
    "     # Get most probable state and its backtrack\n",
    "     for st, data in V[-1].items():\n",
    "         if data[\"prob\"] == max_prob:\n",
    "             opt.append(st)\n",
    "             previous = st\n",
    "             break\n",
    "     # Follow the backtrack till the first observation\n",
    "     for t in range(len(V) - 2, -1, -1):\n",
    "         opt.insert(0, V[t + 1][previous][\"prev\"])\n",
    "         previous = V[t + 1][previous][\"prev\"]\n",
    " \n",
    "     print('The steps of states are ' + ' '.join(opt) + ' with highest probability of %s' % max_prob)\n",
    " \n",
    "def dptable(V):\n",
    "     # Print a table of steps from dictionary\n",
    "     yield \" \".join((\"%9d\" % i) for i in range(len(V)))\n",
    "     for state in V[0]:\n",
    "         yield \"%.7s: \" % state + \" \".join(\"%.7s\" % (\"%f\" % v[state][\"prob\"]) for v in V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of a sequence, let's try it out with a single case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "           0\n",
      "Fever: 0.04000\n",
      "Healthy: 0.30000\n",
      "The steps of states are Healthy with highest probability of 0.3\n"
     ]
    }
   ],
   "source": [
    "obs = (['normal'])\n",
    "viterbi(obs, states, start_p,trans_p,emit_p)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And now, a sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "        0         1         2\n",
      "Fever: 0.04000 0.02700 0.00252\n",
      "Healthy: 0.30000 0.08400 0.02940\n",
      "The steps of states are Healthy Healthy Healthy with highest probability of 0.0294\n"
     ]
    }
   ],
   "source": [
    "obs = ('normal', 'cold', 'normal')\n",
    "viterbi(obs, states, start_p,trans_p,emit_p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}