HMMBasicVer1.1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Theory Behind HMM (Jurafsky Notes):\n",
    "\"\"\" A Markov chain is useful when we need to compute a probability for a sequence of\n",
    "events that we can observe in the world. In many cases, however, the events we are\n",
    "interested in may not be directly observable in the world. For example, in part-of-\n",
    "speech tagging, we don’t observe part-of-speech tags in the world; we see words and have to infer the correct \n",
    "tags from the word sequence. Hence, we call the part-of-speech tags hidden because they are not observed.\n",
    "\"\"\"\n",
    "\"\"\"Imagine that you are a climatologist in the year 2799 studying the history of global\n",
    "warming. You cannot find any records of the weather in Baltimore, Maryland, for\n",
    "the summer of 2007, but you do find Jason Eisner’s diary, which lists how many ice\n",
    "creams Jason ate every day that summer. Our goal is to use these observations to\n",
    "estimate the temperature every day. We’ll simplify this weather task by assuming\n",
    "there are only two kinds of days: cold (C) and hot (H). So the Eisner task is as\n",
    "follows:\n",
    "Given a sequence of observations O, each observation an integer cor-\n",
    "responding to the number of ice creams eaten on a given day, figure\n",
    "out the correct ‘hidden’ sequence Q of weather states (H or C) which\n",
    "caused Jason to eat the ice cream.\"\"\"\n",
    "\"\"\"\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Terminology\n",
    "\"\"\" \n",
    "Q = q1 q2 . . . qN             : Set of N states\n",
    "A = a[i][j] s.t. 1<=i,j<=N     : Transition probability matrix A,s.t a[i][j] is prob of moving from state i to j\n",
    "a[i][j]=P(qj|qi)\n",
    "pi = pi[1],pi[2],...,pi[N]     : Initial prob distr over states. pi[i] is prob of Markov chain starting in state i.\n",
    "O = o[1]o[2]...O[T]            : A Sequence of T Observations, drawn from a Vocab V=v[1]v[2]...,v[v]\n",
    "\"\"\"\n",
    "\"\"\"\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"A first-order hidden Markov model instantiates two simplifying assumptions.\n",
    "First, as with a first-order Markov chain, the probability of a particular state depends\n",
    "only on the previous state:\n",
    "    Markov Assumption: P(qi |q1 ...qi−1) = P(qi|qi−1)\n",
    "Second, the probability of an output observation o[i] depends only on the state that\n",
    "produced the observation qi and not on any other states or any other observations:\n",
    "    Output Independence: P(o[i]|q1 . . qi , . . , qT , o[1] , . . , o[i] , . . , o[T])= P(o[i]|qi)\"\"\"\n",
    "\"\"\"\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"There is a (non-zero) probability of transitioning between any two states. Such an HMM is called \n",
    "a fully connected or ergodic HMM. Sometimes, however, we have HMMs in which many of the transitions \n",
    "between states have zero probability.\"\"\"\n",
    "\"\"\"\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"hidden Markov models should be characterized by three fundamental problems:\n",
    "    Problem 1 (Likelihood): Given an HMM λ = (A, B) and an observation sequence O, determine the \n",
    "    likelihood P(O|λ ).\n",
    "    Problem 2 (Decoding): Given an observation sequence O and an HMM λ =(A, B), discover the best hidden state \n",
    "    sequence Q.\n",
    "    Problem 3 (Learning): Given an observation sequence O and the set of states in the HMM, learn the HMM \n",
    "    parameters A and B.\"\"\"\n",
    "\"\"\"\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "from math import log10\n",
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Likelihood Computation: The Forward Algorithm  O(N*N*T)\n",
    "#Our first problem is to compute the likelihood of a particular observation sequence say 3 1 3?\n",
    "\"\"\"For a Markov chain, where the surface observations are the same as the hidden\n",
    "events, we could compute the probability of 3 1 3 just by following the states labeled\n",
    "3 1 3 and multiplying the probabilities along the arcs. For a hidden Markov model,\n",
    "things are not so simple. We want to determine the probability of an ice-cream\n",
    "observation sequence like 3 1 3, but we don’t know what the hidden state sequence\n",
    "is!\"\"\"\n",
    "#O: Observations, a:State Transition Prob, b:Emission Prob, pi: Initial Prob. \n",
    "#a[i][j]: Prob of transition from state i to state j\n",
    "#b[i][j]: prob of emitting observation j at state i\n",
    "#pi[i]: Initial Prob.of state i\n",
    "#P(O|a,b,pi)=P(O|X=x1,a,b,pi)+P(O|X=x2,a,b,pi)+......+P(O|X=xn,a,b,pi) s.t. x1,x2,....,xn are all possible sequences\n",
    "#alpha[t][i]:Partial Observation sequence upto time t is generated and we are state i\n",
    "#alpha[t][i]= alpha[t-1][0]*a[0][i]*b[i][t]+\n",
    "#    alpha[t-1][1]*a[1][i]*b[i][t]+....+alpha[t-1][n-1]*a[n-1][i]*b[i][t]#Assuming we have n states\n",
    "def computeAlpha(observations,a,b,pi,alphaDP):\n",
    "    statesC=a.shape[0]\n",
    "    timePts=observations.shape[0]\n",
    "    if timePts<1:\n",
    "        return\n",
    "    for i in np.arange(statesC):\n",
    "        alphaDP[0][i]=-(log10(pi[i])+log10(b[i][observations[0]]))#pi[i]*b[i][observations[0]]\n",
    "    for t in np.arange(1,timePts):\n",
    "        for i in np.arange(statesC):\n",
    "            for j in np.arange(statesC):\n",
    "                alphaDP[t][i]=alphaDP[t][i]-(log10(alphaDP[t-1][j])+log10(a[j][i])+log10(b[i][observations[t]]))\n",
    "                #alphaDP[t][i]+=alphaDP[t-1][j]*a[j][i]*b[i][observations[t]]\n",
    "def observationProb(observations,a,b,pi,alphaDP):\n",
    "    computeAlpha(observations,a,b,pi,alphaDP)\n",
    "    print(alphaDP)\n",
    "    timePts=observations.shape[0]\n",
    "    stateC=a.shape[0]\n",
    "    ans=0.0\n",
    "    for i in np.arange(stateC):\n",
    "        ans+=alphaDP[timePts-1][i]\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 1.22184875  0.55284197]\n",
      " [ 1.51910353  2.31304905]\n",
      " [ 2.00706975  0.5087592 ]\n",
      " [ 1.14582722  2.73565275]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3.8814799734520711"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "observations=np.array([0,1,0,2])\n",
    "A=np.array([[0.7,0.3],[0.4,0.6]])\n",
    "B=np.array([[0.1,0.4,0.5],[0.7,0.2,0.1]])\n",
    "pi=np.array([0.6,0.4])\n",
    "alphaDP=np.zeros(shape=(observations.shape[0],A.shape[0]))# Count_of_Observations*Count_of_Hidden_States\n",
    "#Can Easily Optimize Space Requirement of above alphaDP; Only need 2*count_of_Hidden_States Space\n",
    "observationProb(observations,A,B,pi,alphaDP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"\"\"Problem 2 (Decoding): The Viterbi Algorithm -\n",
    "Decoding: Given as input an HMM λ = (A, B, pi) and a sequence of observations O = o1 , o2 , ..., oT\n",
    "find the most probable sequence of states Q = q1 q2 q3 . . . qT \n",
    "\"\"\"\n",
    "\"\"\"Note that the Viterbi algorithm is identical to the forward algorithm except that it takes the max over the\n",
    "previous path probabilities whereas the forward algorithm takes the sum. Note also\n",
    "that the Viterbi algorithm has one component that the forward algorithm doesn’t have: backpointers. The reason \n",
    "is that while the forward algorithm needs to produce an observation likelihood, the Viterbi algorithm must \n",
    "produce a probability and also the most likely state sequence. We can compute this best state sequence by keeping\n",
    "track of the path of hidden states that led to each state, and then at the end backtracing \n",
    "the best path to the beginning (the Viterbi backtrace).\n",
    "\"\"\"\n",
    "def ViterbiAlgo(observations,a,b,pi,viterbiDP,viterbiBackPtr):\n",
    "    statesC=a.shape[0]\n",
    "    timePts=observations.shape[0]\n",
    "    if statesC<1:\n",
    "        return\n",
    "    for i in np.arange(statesC):\n",
    "        viterbiDP[0][i]=-(log10(pi[i])+log10(b[i][observations[0]]))#pi[i]*b[i][observations[0]]\n",
    "    #Doesn't Handle the Case when there is single observation(1 Time Point)\n",
    "    for t in np.arange(1,timePts):\n",
    "        for i in np.arange(statesC):\n",
    "            maxSoFar=0\n",
    "            maxJ=-1\n",
    "            for j in np.arange(statesC):\n",
    "                tempVal=-(log10(viterbiDP[t-1][j])+log10(a[j][i]))#viterbiDP[t-1]*a[j][i]\n",
    "                if tempVal>maxSoFar:\n",
    "                    maxSoFar=tempVal\n",
    "                    maxJ=j\n",
    "            viterbiDP[t][i]=tempVal-log10(b[i][observations[t]])#At State i,Produce observation b[i][observations[t]]\n",
    "            viterbiBackPtr[t][i]=maxJ\n",
    "def getOptimalHiddenStates(observations,a,b,pi,viterbiDP,viterbiBackPtr):\n",
    "    ViterbiAlgo(observations,a,b,pi,viterbiDP,viterbiBackPtr)\n",
    "    print(viterbiDP)\n",
    "    print(viterbiBackPtr)\n",
    "    timePts=observations.shape[0]\n",
    "    stateC=a.shape[0]\n",
    "    ans=0.0\n",
    "    endState=-1\n",
    "    for i in np.arange(stateC):\n",
    "        if ans<alphaDP[timePts-1][i]:\n",
    "            ans=alphaDP[timePts-1][i]\n",
    "            endState=i\n",
    "    stateSeq=np.zeros(shape=(timePts))\n",
    "    stateSeq[timePts-1]=endState#This is where we are adding the Final Optimal State for the Given Observation\n",
    "    i=timePts-2\n",
    "    prevState=endState\n",
    "    while i>=0:\n",
    "        prevState=viterbiBackPtr[i+1][prevState]\n",
    "        stateSeq[i]=prevState\n",
    "        i=i-1\n",
    "    return {\"Probability\":ans,\"Sequence\":stateSeq}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 1.22184875  0.55284197]\n",
      " [ 1.05327901  1.17821775]\n",
      " [ 1.32671445  0.30552515]\n",
      " [ 1.21392304  1.73680179]]\n",
      "[[ 0.  0.]\n",
      " [ 1.  1.]\n",
      " [ 1.  0.]\n",
      " [ 1.  1.]]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/alok/anaconda3/lib/python3.5/site-packages/ipykernel/__main__.py:48: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'Probability': 2.735652754181511, 'Sequence': array([ 1.,  0.,  1.,  1.])}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "observations=np.array([0,1,0,2])\n",
    "A=np.array([[0.7,0.3],[0.4,0.6]])\n",
    "B=np.array([[0.1,0.4,0.5],[0.7,0.2,0.1]])\n",
    "pi=np.array([0.6,0.4])\n",
    "viterbiDP=np.zeros(shape=(observations.shape[0],A.shape[0]))# Count_of_Observations*Count_of_Hidden_States\n",
    "viterbiBackPtr=np.zeros(shape=(observations.shape[0],A.shape[0]))# Count_of_Observations*Count_of_Hidden_States\n",
    "getOptimalHiddenStates(observations,A,B,pi,viterbiDP,viterbiBackPtr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nLet us begin by considering the much simpler case of training a Markov chain rather than a hidden Markov model. Since \\nthe states in a Markov chain are observed, we can run the model on the observation sequence and directly see which path \\nwe took through the model and which state generated each observation symbol. A Markov chain of course has no emission \\nprobabilities B (alternatively, we could view a Markov chain as a degenerate hidden Markov model where all the b proba-\\nbilities are 1.0 for the observed symbol and 0 for all other symbols). Thus, the only probabilities we need to train are \\nthe transition probability matrix A.\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"Problem 3 (HMM Parameter Training): The Forward-Backward/Baum-Welch Algorithm(Special Case of EM Algo) -\n",
    "Given an observation sequence O and the set of possible states in the HMM, learn the HMM \n",
    "parameters λ = (A, B) \n",
    "\"\"\"\n",
    "\"\"\"The input to such a learning algorithm would be an unlabeled sequence of ob-\n",
    "servations O and a vocabulary of potential hidden states Q. Thus, for the ice cream\n",
    "task, we would start with a sequence of observations O = {1, 3, 2, ..., } and the set\n",
    "of hidden states H and C. For the part-of-speech tagging task, we would start with\n",
    "a sequence of observations O = {w1 , w2 , w3 . . .} and a set of hidden states NN, NNS,\n",
    "VBD, IN,... and so on.\n",
    "\"\"\"\n",
    "\"\"\"\n",
    "Let us begin by considering the much simpler case of training a Markov chain rather than a hidden Markov model. Since \n",
    "the states in a Markov chain are observed, we can run the model on the observation sequence and directly see which path \n",
    "we took through the model and which state generated each observation symbol. A Markov chain of course has no emission \n",
    "probabilities B (alternatively, we could view a Markov chain as a degenerate hidden Markov model where all the b proba-\n",
    "bilities are 1.0 for the observed symbol and 0 for all other symbols). Thus, the only probabilities we need to train are \n",
    "the transition probability matrix A.\n",
    "\"\"\"\n",
    "\"\"\"\n",
    "We get the maximum likelihood estimate of the probability a[i][j] of a particular transition between states i and j by \n",
    "counting the number of times the transition was taken, lets say C(i → j), and then normalizing by the total count of all\n",
    "times we took any transition from state i:\n",
    "    a[i][j]=C(i → j)/(Sum(C(i → q))forAll q∈Q)\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nFor an HMM, we cannot compute these counts directly from an observation sequence since we don’t know which path of states \\nwas taken through the machine for a given input. The Baum-Welch algorithm uses two neat intuitions to solve this problem.\\nThe first idea is to iteratively estimate the counts. We will start with an estimate for the transition and observation \\nprobabilities and then use these estimated probabilities to derive better and better probabilities. The second idea is \\nthat we get our estimated probabilities by computing the forward probability for an observation and then dividing that \\nprobability mass among all the different paths that contributed to this forward probability.\\n'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "For an HMM, we cannot compute these counts directly from an observation sequence since we don’t know which path of states \n",
    "was taken through the machine for a given input. The Baum-Welch algorithm uses two neat intuitions to solve this problem.\n",
    "The first idea is to iteratively estimate the counts. We will start with an estimate for the transition and observation \n",
    "probabilities and then use these estimated probabilities to derive better and better probabilities. The second idea is \n",
    "that we get our estimated probabilities by computing the forward probability for an observation and then dividing that \n",
    "probability mass among all the different paths that contributed to this forward probability.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}