lectures/03_HMMs-intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/575_banner.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lecture 3: Introduction to Hidden Markov Models (HMMs)\n",
    "\n",
    "UBC Master of Data Science program, 2023-24\n",
    "\n",
    "Instructor: Varada Kolhatkar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports, LO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Imports "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n",
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import re\n",
    "import sys\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import sys\n",
    "sys.path.append(os.path.join(os.path.abspath(\".\"), \"code\"))\n",
    "from plotting_functions import *\n",
    "import IPython\n",
    "from IPython.display import HTML, display"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Learning outcomes\n",
    "\n",
    "From this lesson you will be able to\n",
    "\n",
    "- explain the motivation for using HMMs\n",
    "- define an HMM\n",
    "- state the Markov assumption in HMMs\n",
    "- explain three fundamental questions for an HMM\n",
    "- apply the forward algorithm given an HMM\n",
    "- explain supervised training in HMMs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 1. Motivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 1.1 Speech recognition\n",
    "\n",
    "- An important component of virtual assistants (e.g., Siri, Cortana, Google Home, Alexa) is speech recognition. \n",
    "- We ask such assistants questions. They convert the question into text, make sense of the question, and return the appropriate answer most of the times. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"800\"\n",
       "            height=\"900\"\n",
       "            src=\"https://www.ibm.com/demos/live/speech-to-text/self-service/home\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "            \n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x141840d40>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "url = \"https://www.ibm.com/demos/live/speech-to-text/self-service/home\"\n",
    "\n",
    "IPython.display.IFrame(url, width=800, height=900)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A number of speech recognition API's are available out there.\n",
    "- You can access them with Python. \n",
    "- A Python module called [`SpeechRecognition`](https://pypi.org/project/SpeechRecognition/) can let you access some of these APIs. \n",
    "    - CMU Sphinx (works offline)\n",
    "    - Google Speech Recognition\n",
    "    - Google Cloud Speech API\n",
    "    - Wit.ai\n",
    "    - Microsoft Bing Voice Recognition\n",
    "    - Houndify API\n",
    "    - IBM Speech to Text\n",
    "    - Snowboy Hotword Detection (works offline)\n",
    "- Usually, you have to pay some money if you want to use these APIs.     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- In speech recognition, you are given a sequence of sound waves and your job is to recognize the corresponding sequence of phonemes or words. \n",
    "- Phonemes: distinct units of sound. For example: \n",
    "    - tree $\\rightarrow$ T R IY\n",
    "    - cat $\\rightarrow$ K AE T\n",
    "    - stats $\\rightarrow$ S T AE T S\n",
    "    - eks $\\rightarrow$ E K S     \n",
    "- There are ~44 phonemes in North American English. \n",
    "- Is it possible to use the ML models we learned in 571, 573, 563 for this problem?\n",
    "- In written text, we know that certain transitions are more likely than others\n",
    "    - \"th\" as in \"this\"\n",
    "    - \"sh\" as in \"shoe\"\n",
    "    - \"ch\" as in \"chair\"\n",
    "    - \"ck\" as in \"back\"\n",
    "- Which transition do you think is easier and more natural/efficient/common for phonemes? \n",
    "    - /s/ to /t/: \"stop\", \"best\", \"fast\"\n",
    "    - /t/ and /r/: \"try\", \"tree\", \"train\"\n",
    "    - /f/ to /v/: \"of value\"\n",
    "    - /s/ to /b/\n",
    "    - In other words is it easier to say \"stop\" or \"of value\"?\n",
    "    \n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Speech recognition is a sequence modeling problem. \n",
    "    - It's a good idea to incorporate sequential information in the model for speech recognition. \n",
    "- Many modern statistical speech recognition systems are based on hidden Markov models. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 1.2 HMMs intuition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Observable Markov models** \n",
    "\n",
    "- Example\n",
    "    - States: {uniformly, are, charming}   \n",
    "\n",
    "![](img/observable_Markov.png)\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/observable_Markov.png\" height=\"600\" width=\"600\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/A.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Hidden phenomenon**\n",
    "\n",
    "Very often the things you observe in the real world can be thought of as a function of some other **hidden** variables.\n",
    "\n",
    "Example 1: \n",
    "- Observations: Acoustic features of the speech signal, hidden states: phonemes that are spoken"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Example 2: \n",
    "- Observations: Words, hidden states: parts-of-speech\n",
    "\n",
    "![](img/hmm_pos_tagging.png)\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/hmm_pos_tagging.png\" height=\"1000\" width=\"1000\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/8.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "More examples\n",
    "\n",
    "- Observations: Encrypted symbols, hidden states: messages\n",
    "- Observations: Exchange rates, hidden states: volatility of the market\n",
    "\n",
    "<!-- ![](img/stock_market_hmm.png) -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recently, neural models have overshadowed HMMs in many areas, especially in NLP and tasks requiring the processing of long sequences. That said, HMMs are not obsolete. Their simplicity, interpretability, and efficiency in modeling temporal or sequential data make them suitable for applications where \n",
    "- the data sequences are not excessively long or\n",
    "- the computational resources are limited\n",
    "\n",
    "HMMS still shine in the following areas:\n",
    "- Speech Recognition\n",
    "- Bioinformatics\n",
    "- Financial Modeling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 2. HMM definition and example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Last week we used the following toy example to demonstrate how do we learn initial state probabilities and transition probabilities in Markov models. \n",
    "\n",
    "- Imagine you're developing a system for a company interested in tailoring its services based on users' emotional states. (Though, remember, this is a simplified and hypothetical scenario to understand HMMs, not a real-world application due to privacy and ethical considerations.)\n",
    "- In this scenario, the company cannot directly know a person's emotional state because it's 'hidden'. However, they can observe behaviors through activity on their platform, like the types of videos watched or search queries. \n",
    "  \n",
    "![](img/activity-seqs.png)\n",
    "<!-- <img src=\"img/activity-seqs.png\" height=\"800\" width=\"800\"> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 2.1 Markov process with hidden variables: Example\n",
    "\n",
    "- Let's simplify above example. \n",
    "- Suppose you have a little robot that is trying to estimate the posterior probability that you are **Happy (H or 🙂)** or **Sad (S or 😔)**, given that the robot has observed whether you are doing one of the following activities: \n",
    "    - **Learning data science (L or 📚)**\n",
    "    - **Eat (E or 🍎)** \n",
    "    - **Cry (C or 😿)** \n",
    "    - **Social media (F)**\n",
    "\n",
    "- The robot is trying to estimate the unknown (hidden) state $Q$, where $Q =H$ when you are happy (🙂) and $Q = S$ when you are sad (😔). \n",
    "- The robot is able to observe the activity you are doing: $O = {L, E, C, F}$ \n",
    "\n",
    "- By observing activities, the goal is to infer the underlying emotional states (the hidden states) and understand the transition patterns between these states.\n",
    "\n",
    "(Attribution: Example adapted from [here](https://www.cs.ubc.ca/~nando/340-2012/lectures/l6.pdf).)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Example questions we are interested in answering are:\n",
    "    - Given an HMM, what is the probability of observation sequence 📚📚😿📚📚? (this lecture)\n",
    "    - - Given an HMM, what is the best possible sequence of state of mind (e.g.,🙂,🙂,😔,🙂,🙂 ) given an observation sequence (e.g., L,L,C,L,L or 📚📚😿📚📚). (next lecture)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "### 2.2 HMM ingredients\n",
    "\n",
    "- State space (e.g., 🙂 (H), 😔 (S))\n",
    "- An initial probability distribution over the states\n",
    "- Transition probabilities\n",
    "- **Emission probabilities** \n",
    "    - Conditional probabilities for all observations given a hidden state\n",
    "    - Example: Below $P(L|🙂) = 0.7$ and $P(L|😔) = 0.1$\n",
    "    \n",
    "![](img/HMM_example_small.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example.png\" height=\"600\" width=\"600\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition of an HMM**\n",
    "\n",
    "- A hidden Markov model (HMM) is specified by the 5-tuple:  $\\{S, Y, \\pi, T, B\\}$ \n",
    "    - $S = \\{s_1, s_2, \\dots, s_n\\}$ is a set of states (e.g., moods)\n",
    "    - **$Y = \\{y_1, y_2, \\dots, y_k\\}$ is output alphabet (e.g., set of activities)**\n",
    "    - $\\pi = {\\pi_1, \\pi_2, \\dots, \\pi_n}$ is discrete initial state probability distribution \n",
    "    - Transition probability matrix $T$, where each $a_{ij}$ represents the probability of moving from state $s_i$ to state $s_j$\n",
    "    - **Emission probabilities B = $b_i(o), i \\in S, o \\in Y\\$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Yielding the state sequence and the observation sequences in an unrolled HMM \n",
    "    - State sequence: $Q = {q_0,q_1, q_2, \\dots q_T}, q_i \\in S$ \n",
    "    - Observation sequence: $O = {o_0,o_1, o_2, \\dots o_T}, o_i \\in Y$\n",
    "<!-- ![](img/HMM_unrolling_timesteps.png) -->\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example.png\" height=\"600\" width=\"600\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_unrolling_timesteps.png\" height=\"700\" width=\"700\"> -->\n",
    "\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Here is an example of an unrolled HMM for six time steps, a possible realization of a sequence of states and a sequence of observations. \n",
    "\n",
    "![](img/HMM_unrolling_timesteps.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_unrolling_timesteps.png\" height=\"800\" width=\"800\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "- Each state produces only a single observation and the sequence of hidden states and the sequence of observations have the same length. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 2.2 HMM assumptions\n",
    "\n",
    "- **The probability of a particular state only depends on the previous state.**\n",
    "    * $P(q_i|q_0,q_1,\\dots,q_{i-1})$ = $P(q_i|q_{i-1})$\n",
    "    \n",
    "- **The probability of an output observation $o_i$ depends only on the state that produces the observation and not on any other state or any other observation.** \n",
    "    * $P(o_i|q_0,q_1,\\dots,q_{i}, o_0,o_1,\\dots,o_{i-1})$ = $P(o_i|q_i)$\n",
    "\n",
    "<!-- ![](img/HMM_unrolling_timesteps.png) -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 2.3 Three fundamental questions for an HMM\n",
    "\n",
    "#### Likelihood\n",
    "Given a model with parameters $\\theta = <\\pi, T, B>$, how do we efficiently compute the likelihood of a particular observation sequence $O$?\n",
    "#### Decoding\n",
    "Given an observation sequence $O$ and a model $\\theta$ how do we choose a state sequence $Q={q_0, q_1, \\dots q_T}$ that best explains the observation sequence?\n",
    "#### Learning\n",
    "Training: Given a large observation sequence $O$ how do we choose the best parameters $\\theta$ that explain the data $O$? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ❓❓ Questions for you"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.1: Select all of the following statements which are **True** (iClicker)\n",
    "\n",
    "**iClicker join link: https://join.iclicker.com/ZTLY**\n",
    "\n",
    "- (A) Emission probabilities in our toy example give us the probabilities of being happy or sad given that you are performing one of the four activities: Learn, Eat, Cry, Facebook.  \n",
    "- (B) In hidden Markov models, the observation at time step $t$ is conditionally independent of previous observations and previous hidden states given the hidden state at time $t$. \n",
    "- (C) In hidden Markov models, given the hidden state at time $t-1$, the hidden state at time step $t$ is conditionally independent of the previous hidden states and observations. \n",
    "- (D) In hidden Markov models, each hidden state has a probability distribution over all observations. \n",
    "\n",
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 3.1: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "- B, C, D\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.2: Discuss the following questions with your neighbour. \n",
    "1. What are the parameters $\\theta$ of a hidden Markov model?\n",
    "2. Below is a hidden Markov model that relates numbers of ice creams eaten by Jason to the weather. Identify observations, hidden states, transition probabilities, and emission probabilities in the model.\n",
    "\n",
    "![](img/ice-cream-hmm.png)\n",
    "\n",
    "<!-- <img src=\"img/ice-cream-hmm.png\" height=\"600\" width=\"600\"> -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/A.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 3.2: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "1. initial state probabilities $\\pi_0$, transition probabilities $T$, emission probabilities $B$\n",
    "2. \n",
    "- Observations: 1, 2, 3\n",
    "- Hidden states: HOT, COLD \n",
    "- transition probabilities: \n",
    "\n",
    "|               | HOT  | COLD |\n",
    "| ------------- |:---------:| -----:|\n",
    "| HOT         | 0.6       | 0.4   |\n",
    "| COLD        | 0.5       | 0.5   |\n",
    "\n",
    "Emission probabilities: \n",
    "|               | 1  | 2 | 3 | \n",
    "| ------------- |:---------:| -----:| -----:|\n",
    "| HOT         | 0.2       | 0.4   | 0.4 |\n",
    "| COLD        | 0.5       | 0.4   | 0.1 |\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Break (~5 mins)\n",
    "\n",
    "![](img/eva-coffee.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Likelihood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In the context of HMMs, the likelihood of an observation sequence is the probability of observing that sequence given a particular set of model parameters $\\theta$. \n",
    "\n",
    "Given a model with parameters $\\theta = <\\pi, T, B>$, how do we efficiently compute the likelihood of a particular observation sequence $O$?\n",
    "\n",
    "- Example: What's the probability of the sequence below? \n",
    "\n",
    "![](img/HMM_example_activity_seq_small.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_activity_seq.png\" height=\"400\" width=\"400\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "- Recall that in HMMs, the observations are dependent upon the hidden states in the same time step. Let's consider a particular state sequence. \n",
    "<br><br>\n",
    "\n",
    "![](img/HMM_likelihood_known_hidden_small.png)\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_likelihood_known_hidden.png\" height=\"500\" width=\"500\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Probability of an observation sequence given the state sequence \n",
    "\n",
    "- Suppose we know both the sequence of hidden states (moods) and the sequence of activities emitted by them. \n",
    "- $P(O|Q) = \\prod\\limits_{i=1}^{T} P(o_i|q_i)$\n",
    "- $P(E L F C|🙂 🙂 😔 😔) = P(E|🙂) \\times P(L|🙂) \\times P(F|😔) \\times P(C|😔)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.1 Joint probability of observations and a possible hidden sequence \n",
    "\n",
    "- Let's consider the joint probability of being in a particular state sequence $Q$ and generating a particular sequence $O$ of activities. \n",
    "\n",
    "- $P(O,Q) = P(O|Q)\\times P(Q) = \\prod\\limits_{i=1}^T P(o_i|q_i) \\times \\prod\\limits_{i=1}^T P(q_i|q_{i-1})$ \n",
    "\n",
    "<br>\n",
    "\n",
    "![](img/HMM_likelihood_unknown_hidden_small.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_likelihood_unknown_hidden.png\" height=\"600\" width=\"500\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "For example, for our toy sequence: \n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "P(E L F C, 🙂 🙂 😔 😔) = & P(🙂|start)\\\\ \n",
    "                          & \\times P(🙂|🙂) \\times P(😔|🙂) \\times P(😔|😔)\\\\\n",
    "                          & \\times P(E|🙂) \\times P(L|🙂) \\times P(F|😔) \\times P(C|😔)\\\\\n",
    "                      = & 0.8 \\times 0.7 \\times 0.3 \\times 0.6 \\times 0.2 \\times 0.7 \\times 0.2 \\times 0.6 \n",
    "\\end{split}\n",
    "\\end{equation}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.2 Total probability of an observation sequence \n",
    "\n",
    "- But we do not know the hidden state sequence $Q$.\n",
    "- We need to look at all combinations of hidden states. \n",
    "- We need to compute the probability of activity sequence (ELFC) by summing over all possible state (mood) sequences.  \n",
    "- $P(O) = \\sum\\limits_Q P(O,Q) = \\sum\\limits_QP(O|Q)P(Q)$\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "P(E L F C) = & P(E L F C,🙂🙂🙂🙂)\\\\ \n",
    "             & + P(E L F C,🙂🙂🙂😔)\\\\\n",
    "             & + P(E L F C,🙂🙂😔😔) + \\dots\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "- Computationally inefficient \n",
    "    - For HMMs with $n$ hidden states and an observation sequence of $T$ observations, there are $n^T$ possible hidden sequences!!\n",
    "    - In real-world problems both $n$ and $T$ are large numbers. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**How to compute $P(O)$ cleverly?**\n",
    "\n",
    "- To avoid this complexity we use **dynamic programming**; we remember the results rather than recomputing them. \n",
    "- We make a **trellis** which is an array of states vs. time.\n",
    "- Note the alternative paths in the trellis. We are covering all the 16 combinations of states. \n",
    "- We compute $\\alpha_i(t)$ at each $(i,t)$, which represents the probability of being in state $i$ at time $t$ after seeing all previous observations and the current observation at time step $t$. \n",
    "\n",
    "![](img/HMM_trellis_small.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_trellis.png\" height=\"400\" width=\"400\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.3 The forward procedure\n",
    "\n",
    "**Intuition**\n",
    "- To compute $\\alpha_j(t)$, we can compute $\\alpha_{i}(t-1)$ for all possible states $i$ and then use our knowledge of $a_{ij}$ and $b_j(o_t)$.\n",
    "- We compute the trellis left-to-right because of the convention of time.\n",
    "- Remember that $o_t$ is fixed and known."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Three steps of the forward procedure.**\n",
    "\n",
    "- Initialization: Compute the $\\alpha$ values for nodes in the first column of the trellis $(t = 0)$.\n",
    "- Induction: Iteratively compute the $\\alpha$ values for nodes in the rest of the trellis $(1 \\leq t < T)$.\n",
    "- Conclusion: Sum over the $\\alpha$ values for nodes in the last column of the trellis $(t = T)$.\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### 3.3.1 The forward procedure: Initialization $\\alpha_🙂(0)$ and $\\alpha_😔(0)$\n",
    "\n",
    "- Compute the nodes in the first column of the trellis $(T = 0)$.\n",
    "    * Probability of starting at state 🙂 and observing the activity E: $\\alpha_🙂(0) = \\pi_🙂 \\times b_🙂(E) = 0.8 \\times 0.2 = 0.16$ \n",
    "    * Probability of starting at state 😔 and observing the activity E: $\\alpha_😔(0) = \\pi_😔 \\times b_😔(E) = 0.2 \\times 0.1 = 0.02$  \n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### 3.3.2 The forward procedure: Induction\n",
    "\n",
    "- Iteratively compute the nodes in the rest of the trellis $(1 \\leq t < T)$.\n",
    "-  To compute $\\alpha_j(t+1)$ we can compute $\\alpha_{i}(t)$ for all possible states $i$ and then use our knowledge of $a_{ij}$ and $b_j(o_{t+1})$ \n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The forward procedure: Induction $\\alpha_🙂(1)$**\n",
    "\n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "\n",
    "- Probability of being at state 🙂 at $t=1$ and observing the activity L\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "\\alpha_🙂(1) = & \\alpha_🙂(0)a_{🙂🙂}b_🙂(L) + \\alpha_😔(0)a_{😔🙂}b_🙂(L)\\\\\n",
    "             = & 0.16 \\times 0.7 \\times 0.7 + 0.02 \\times 0.4 \\times 0.7\\\\ \n",
    "             = & 0.084\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The forward procedure: Induction $\\alpha_😔(1)$**\n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "- Probability of being at state 😔 at $t=1$ and observing the activity L:\n",
    "\\begin{equation}\n",
    "\\begin{split}             \n",
    "\\alpha_😔(1) = & \\alpha_🙂(0)a_{🙂😔}b_😔(L) + \\alpha_😔(0)a_{😔😔}b_😔(L)\\\\\n",
    "             = & 0.16 \\times 0.3 \\times 0.1 + 0.02 \\times 0.6 \\times 0.1\\\\\n",
    "             = & 0.006\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The forward procedure: Induction $\\alpha_🙂(2)$**\n",
    "\n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "\n",
    "- Probability of being at state 🙂 at $t=2$ and observing the activity F\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "\\alpha_🙂(2) = & \\alpha_🙂(1)a_{🙂🙂}b_🙂(F) + \\alpha_😔(1)a_{😔🙂}b_🙂(F)\\\\\n",
    "             = & 0.084 \\times 0.7 \\times 0.0 + 0.006 \\times 0.4 \\times 0.0\\\\ \n",
    "             = & 0.0\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The forward procedure: Induction $\\alpha_😔(2)$**\n",
    "\n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "- Probability of being at state 😔 at $t=2$ and observing the activity F:\n",
    "\\begin{equation}\n",
    "\\begin{split}             \n",
    "\\alpha_😔(2) = & \\alpha_🙂(1)a_{🙂😔}b_😔(F) + \\alpha_😔(1)a_{😔😔}b_😔(F)\\\\\n",
    "             = & 0.084 \\times 0.3 \\times 0.2 + 0.006 \\times 0.6 \\times 0.2\\\\\n",
    "             = & 0.00576\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "<!-- ![](img/HMM_example_trellis.png) -->\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The forward procedure: Induction $\\alpha_🙂(3)$**\n",
    "\n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "\n",
    "- Probability of being at state 🙂 at $t=3$ and observing the activity C:\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "\\alpha_🙂(3) = & \\alpha_🙂(2)a_{🙂🙂}b_🙂(C) + \\alpha_😔(2)a_{😔🙂}b_🙂(C)\\\\\n",
    "             = & 0 \\times 0.7 \\times 0.1 + 0.00576 \\times 0.4 \\times 0.1\\\\ \n",
    "             = & 2.3 \\times 10^{-4}\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The forward procedure: Induction $\\alpha_😔(3)$**\n",
    "\n",
    "- $\\alpha_j(t+1) = \\sum\\limits_{i=1}^n \\alpha_i(t) a_{ij} b_j(o_{t+1})$\n",
    "- Probability of being at state 😔 at $t=3$ and observing the activity C:\n",
    "\\begin{equation}\n",
    "\\begin{split}             \n",
    "\\alpha_😔(3) = & \\alpha_🙂(2)a_{🙂😔}b_😔(C) + \\alpha_😔(2)a_{😔😔}b_😔(C)\\\\\n",
    "             = & 0.0 \\times 0.3 \\times 0.6 + 0.00576 \\times 0.6 \\times 0.6\\\\\n",
    "             = & 2.07 \\times 10^{-3}\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### 3.3.3 The forward procedure: Conclusion\n",
    "\n",
    "- Sum over all possible final states:\n",
    "  * $P(O;\\theta) = \\sum\\limits_{i=1}^{n}\\alpha_i(T-1)$\n",
    "  * $P(E,L,F,C) = \\alpha_🙂(3) + \\alpha_😔(3) = 2.3 \\times 10^{-4} + 2.07 \\times 10^{-3}$ \n",
    "\n",
    "![](img/HMM_example_trellis.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example_trellis.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Recap: The forward algorithm\n",
    "- The forward algorithm computes likelihood of a given observation sequence: $P(O;\\theta)$. \n",
    "- For each state $i$, we calculated $\\alpha_i(0), \\alpha_i(1), \\alpha_i(2), ...\\alpha_i(t)$, which represent the probabilities of being in state $i$ at times $t$ knowing all the observations which came before and at time $t$. \n",
    "- The trellis was computed left to right and top to bottom.\n",
    "- The forward algorithm stores the probabilities of all possible 1-state sequences (from the start), to store all possible 2-state sequences (from the start), to store all possible 3-state sequences (from the start) and so on. \n",
    "\n",
    "![](img/hmm_alpha_values.png)\n",
    "\n",
    "- Sum over all possible final states:\n",
    "  * $P(O;\\theta) = \\sum\\limits_{i=1}^{n}\\alpha_i(T-1)$\n",
    "  * $P(E,L,F,C) = \\alpha_🙂(3) + \\alpha_😔(3) = 0.00023 + 0.00207 = 0.0023$ \n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/hmm_alpha_values.png\" height=\"500\" width=\"500\">  -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 4. Supervised training of HMMs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 4.1 Supervised training of HMMs\n",
    "\n",
    "- Suppose we have training data where we have $O$ and corresponding $Q$, then we can use MLE to learn parameters $\\theta = <\\pi, T, B>$\n",
    "- Get transition matrix and the emission probabilities. \n",
    "    - Suppose $i$, $j$ are unique states from the state space and $k$ is a unique observation.    \n",
    "    - $\\pi_0(i) = P(q_0 = i) = \\frac{Count(q_0 = i)}{\\#sequences}$\n",
    "    - $a_{ij} = P(q_{t+1} = j|q_t = i) = \\frac{Count(i,j)}{Count(i, anything)}$\n",
    "    - $b_i(k) = P(o_{t} = k|q_t = i) = \\frac{Count(i,k)}{Count(i, anything)}$\n",
    "\n",
    "![](img/HMM_unrolling_timesteps.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_unrolling_timesteps.png\" height=\"700\" width=\"700\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "source": [
    "- Suppose we have training data where we have $O$ and corresponding $Q$, then we can use MLE to learn parameters $\\theta = <\\pi, T, B>$\n",
    "    - Count how often $q_{i-1}$ and $q_i$ occur together normalized by how often $q_{i-1}$ occurs with anything: \n",
    "      $p(q_i|q_{i-1}) = \\frac{Count(q_{i-1} q_i)}{Count(q_{i-1} \\text{anything})}$\n",
    "    - Count how often $q_i$ is associated with the observation $o_i$.   \n",
    "      $p(o_i|q_{i}) = \\frac{Count(o_i \\wedge q_i)}{Count(q_{i} \\text{anything})}$    \n",
    "\n",
    "<!-- ![](img/HMM_unrolling_timesteps.png) -->\n",
    "\n",
    "<!-- <center>\n",
    "<img src=\"img/HMM_unrolling_timesteps.png\" height=\"700\" width=\"700\">\n",
    "</center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**In real life, all the calculations above are done with log probabilities for numerical stability.** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 4.2 HMM libraries\n",
    "\n",
    "Usually, practitioners develop there own version of HMMs suitable for their application. But there are some popular libraries:  \n",
    "- [hmmlearn](https://hmmlearn.readthedocs.io/en/latest/)\n",
    "- [pomegranate](https://github.com/jmschrei/pomegranate)\n",
    "- [HTK Toolkit](https://htk.eng.cam.ac.uk/)\n",
    "> Note that there are not many actively maintained off-the-shelf libraries available for supervised training of HMMs. [seqlearn](https://pypi.org/project/seqlearn/) used to be part of `sklearn`. But it's separated now and is not being maintained. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's calculate the likelihood of observing an observation sequence given a particular set of model parameters $\\theta$ using `hmmlearn`. \n",
    "\n",
    "![](img/HMM_example_small.png)\n",
    "\n",
    "<!-- <img src=\"img/HMM_example.png\" height=\"600\" width=\"600\"> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To run the code below successfully, you need install `networkx` and `graphviz`. \n",
    "\n",
    "```\n",
    "conda install -c conda-forge graphviz\n",
    "conda install -c conda-forge python-graphviz\n",
    "conda install -c anaconda networkx\n",
    "conda install -c anaconda pydot\n",
    "conda install --channel conda-forge pygraphviz\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from hmmlearn import hmm\n",
    "\n",
    "# Initializing an HMM\n",
    "states = [\"Happy\", \"Sad\"]\n",
    "n_states = len(states)\n",
    "\n",
    "symbols = [\"Learn\", \"Eat\", \"Cry\", \"Facebook\"]\n",
    "n_observations = len(symbols)\n",
    "\n",
    "model = hmm.CategoricalHMM(\n",
    "    n_components=n_states, random_state=42\n",
    ")  # for discrete observations\n",
    "\n",
    "# Set the initial state probabilities\n",
    "model.startprob_ = np.array([0.8, 0.2])\n",
    "\n",
    "# Set the transition matrix\n",
    "model.transmat_ = np.array([[0.7, 0.3], [0.4, 0.6]])\n",
    "\n",
    "# Set the emission probabilities of shape (n_components, n_symbols)\n",
    "model.emissionprob_ = np.array([[0.7, 0.2, 0.1, 0.0], [0.1, 0.1, 0.6, 0.2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nodes:\n",
      "['happy', 'sad']\n",
      "\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (0)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"110pt\" height=\"133pt\"\n",
       " viewBox=\"0.00 0.00 110.13 132.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 128.5)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-128.5 106.13,-128.5 106.13,4 -4,4\"/>\n",
       "<!-- happy -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>happy</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"33.44\" cy=\"-106.5\" rx=\"33.44\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"33.44\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">happy</text>\n",
       "</g>\n",
       "<!-- happy&#45;&gt;happy -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>happy&#45;&gt;happy</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M63.55,-114.76C75.2,-115.13 84.88,-112.38 84.88,-106.5 84.88,-102.74 80.9,-100.25 74.99,-99.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.29,-95.56 65.06,-98.34 74.79,-102.54 75.29,-95.56\"/>\n",
       "<text text-anchor=\"middle\" x=\"93.5\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">0.7</text>\n",
       "</g>\n",
       "<!-- sad -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>sad</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"33.44\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"33.44\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">sad</text>\n",
       "</g>\n",
       "<!-- happy&#45;&gt;sad -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>happy&#45;&gt;sad</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M22.22,-89.13C18.97,-83.48 15.84,-76.95 14.19,-70.5 12.36,-63.4 12.36,-61.1 14.19,-54 15,-50.85 16.15,-47.68 17.51,-44.61\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"20.47,-46.51 21.93,-36.01 14.24,-43.3 20.47,-46.51\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.06\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">0.3</text>\n",
       "</g>\n",
       "<!-- sad&#45;&gt;happy -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>sad&#45;&gt;happy</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.44,-36.35C33.44,-48.06 33.44,-63.79 33.44,-77.28\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"29.94,-76.9 33.44,-86.9 36.94,-76.9 29.94,-76.9\"/>\n",
       "<text text-anchor=\"middle\" x=\"42.06\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">0.4</text>\n",
       "</g>\n",
       "<!-- sad&#45;&gt;sad -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>sad&#45;&gt;sad</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.97,-26.17C68.95,-26.95 78.44,-24.22 78.44,-18 78.44,-14.11 74.73,-11.59 69.27,-10.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"69.65,-6.95 59.48,-9.91 69.28,-13.94 69.65,-6.95\"/>\n",
       "<text text-anchor=\"middle\" x=\"87.06\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">0.6</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.sources.Source at 0x147a5fb00>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "visualize_hmm(model, states=[\"happy\", \"sad\"]) # user-defined function from code/plotting_functions.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Emission probabilities: \n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Learn</th>\n",
       "      <th>Eat</th>\n",
       "      <th>Cry</th>\n",
       "      <th>Facebook</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Happy</th>\n",
       "      <td>0.7</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0.1</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Sad</th>\n",
       "      <td>0.1</td>\n",
       "      <td>0.1</td>\n",
       "      <td>0.6</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       Learn  Eat  Cry  Facebook\n",
       "Happy    0.7  0.2  0.1       0.0\n",
       "Sad      0.1  0.1  0.6       0.2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"Emission probabilities: \")\n",
    "pd.DataFrame(data=model.emissionprob_, columns=symbols, index=states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- We can calculate the probability of an observation sequence efficiently using the forward algorithm. \n",
    "- In `hmmlearn`, we can use the `.score` method of the hmm model to get the log probabilities. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "obs_seq = np.array([[1], [0], [3], [2]])\n",
    "label_obs_seq = map(lambda x: symbols[x], obs_seq.T[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ?model.score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Log likelihood of sequence ['Eat', 'Learn', 'Facebook', 'Cry'] is -6.073108536148493 \n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    \"Log likelihood of sequence %s is %s \"\n",
    "    % (list(label_obs_seq), model.score(obs_seq))\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ❓❓ Questions for you"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.2: Select all of the following statements which are **True** (iClicker)\n",
    "\n",
    "**iClicker join link: https://join.iclicker.com/ZTLY**\n",
    "\n",
    "- (A) In the forward algorithm we assume that the observation sequence $O$ and the model parameters are fixed and known. \n",
    "- (B) In the forward algorithm, in our notation, $\\alpha_{i}(t)$ represents the probability of being in state $i$ at time $t$ after seeing all the observations including the observation at time step $t$. \n",
    "- (C) In the forward algorithm $\\alpha_i(t)$ does not know anything about the future time steps after the time step $t$. \n",
    "- (D) We conclude the forward procedure by summing over the $\\alpha$ values at the last time step.\n",
    "- (E) You can pass sequences of different lengths when training HMMs.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 3.2: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "- A, B, C, D, E\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ❓❓ Questions for you\n",
    "\n",
    "### Exercise 3.3: Discuss the following question with your neighbour. \n",
    "\n",
    "- The forward procedure using dynamic programming needs only $\\approx 2n^2T$ multiplications compared to the $\\approx(2T)n^T$ multiplications with the naive approach!! Why? Discuss with your neighbour.\n",
    "- Give an advantage of using the forward procedure compared to summing over all possible state combinations of length T. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 3.3: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "\n",
    "The forward procedure is a computationally efficient procedure compared to the method of summing over all possible state combinations of length $T$. The former requires $2Tn^T$ multiplications compared to $2n^2T$ multiplications in the latter, where $N$ is the number of states and $T$ is the number of time steps.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Quick summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Summary\n",
    "\n",
    "- Hidden Markov models (HMMs) model time-series with latent factors.\n",
    "- There are tons of applications associated with them and they are more realistic than Markov models. \n",
    "- The most successful application of HMMs is speech recognition. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "### Important ideas we learned \n",
    "\n",
    "- HMM ingredients\n",
    "    - Hidden states (e.g., Happy, Sad)\n",
    "    - Output alphabet or output symbols (e.g., learn, study, cry, facebook)\n",
    "    - Discrete initial state probability distribution\n",
    "    - Transition probabilities\n",
    "    - Emission probabilities    \n",
    "\n",
    "![](img/HMM_example_small.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/HMM_example.png\" height=\"600\" width=\"600\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Fundamental questions for HMMs \n",
    "\n",
    "- Three fundamental questions for HMMs: \n",
    "    - likelihood\n",
    "    - decoding\n",
    "    - parameter learning \n",
    "- The forward algorithm is a dynamic programming algorithm to efficiently calculate the probability of an observation sequence given an HMM. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Supervised training of HMMs \n",
    "- HMMs for POS tagging.\n",
    "- Not many tools out there for supervised training of HMMs. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Coming up\n",
    "\n",
    "- Decoding: Viterbi algorithm\n",
    "    - Given an HMM model and an observation sequence, how do we efficiently compute the corresponding hidden state sequence. \n",
    "- Unsupervised training of HMMs (Optional)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Resources\n",
    "\n",
    "- [Hidden Markov Models chapter from Jurafsky and Martin](https://web.stanford.edu/~jurafsky/slp3/A.pdf)\n",
    "- Attribution: Many presentation ideas in this notebook are taken from [Frank Rudzicz's slides](http://www.cs.toronto.edu/~frank/csc401/lectures2018/5-HMMs.pdf).\n",
    "- [Jason Eisner's lecture on hidden Markov Models](https://vimeo.com/31374528)\n",
    "- [Jason Eisner's interactive spreadsheet for HMMs](https://cs.jhu.edu/~jason/papers/eisner.hmm.xls)\n",
    "- [Who each player is guarding?](https://www.youtube.com/watch?v=JvNkZdZJBt4)\n",
    "- [The Viterbi Algorithm: A Personal History](https://arxiv.org/pdf/cs/0504020v2.pdf)\n",
    "- [A nice demo of independent vs. Markov vs. HMMs for DNA](https://a-little-book-of-r-for-bioinformatics.readthedocs.io/en/latest/src/chapter10.html)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [conda env:575]",
   "language": "python",
   "name": "conda-env-575-py"
  },
  "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.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}