HMM basics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "taken-command",
   "metadata": {},
   "source": [
    "# HMM Basics\n",
    "\n",
    "Probabilistic Modeling and Reasoning 2023-2024, the University of Edinburgh.\n",
    "\n",
    "Hidden Markov Models (HMMs) are one of the fundamental tools in probabilistic modelling, and are widely used in computer vision, and speech and natural language processing (NLP) and many others.\n",
    "\n",
    "In NLP, many current state of the art models can be viewed as advanced versions of HMMs. \n",
    "\n",
    "In this notebook we use a simple language model to explain the basics of HMMs.\n",
    "\n",
    "(Notes by Yao Fu, yao.fu@ed.ac.uk)\n",
    "\n",
    "## Table of Content\n",
    "\n",
    "* Simple HMM Language Model\n",
    "* Parametrisation of a HMM\n",
    "* Generating Sentences by Sampling from a HMM\n",
    "* Rethinking the Independence Assumption"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "biological-military",
   "metadata": {},
   "source": [
    "# Preparations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "played-trash",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.239247Z",
     "start_time": "2022-02-13T12:07:47.237079Z"
    }
   },
   "outputs": [],
   "source": [
    "# We will only need numpy for this tutorial\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alternative-interest",
   "metadata": {},
   "source": [
    "# A simple language example"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ordinary-blackberry",
   "metadata": {},
   "source": [
    "Consider the following simple sentences that discuss cats and dogs:\n",
    "* I like cats \n",
    "* I really like cats\n",
    "* I like really cute cats\n",
    "* Cute Sam likes dogs \n",
    "* Jack loves dogs \n",
    "* Jack really loves small dogs \n",
    "* Charming Sam likes cute dogs \n",
    "\n",
    "These sentences are simple in a way that they are structured like the following\n",
    "* (Adjective) -> Subject -> (Adverb) -> Verb -> (Adjective) -> Object. We call this the _template_ of a sentence.\n",
    "* Note the probabilistic nature: a verb can directly generate an object or a modifier.\n",
    "\n",
    "Consider the simplest sentence template:\n",
    "* Subject -> Verb -> Object\n",
    "\n",
    "To describe a language that uses this template, we can use a Markov Chain to model the template as a sequence of latent states:\n",
    "* $h_1$ = Subject -> $h_2$ = Verb -> $h_3$ = Object\n",
    "\n",
    "This template can generate the following sentences:\n",
    "* I like cats \n",
    "* Jack loves dogs \n",
    "* etc.\n",
    "\n",
    "Specifically, each latent state generates a word:\n",
    "* $h_1$ = Subject -> $v_1$ = {I, Jack}\n",
    "* $h_2$ = Verb -> $v_2$ = {like, loves}\n",
    "* $h_3$ = Object -> $v_3$ = {cats, dogs}\n",
    "\n",
    "We can further have an adjective to modify the subject or the object:\n",
    "* Adjective -> Subject, e.g., Cute Sam\n",
    "* Adjective -> Object, e.g., Cute cats\n",
    "\n",
    "Or an adverb to modify the verb\n",
    "* Adverb -> Verb, e.g., really like\n",
    "\n",
    "By adding these modifiers to the simple template language above and using probabilistic transition and emission distributions we construct a richer language.\n",
    "\n",
    "We now consider modelling this language with HMMs. Formally, we have a sequence of latent states that describe the template of a sentence:\n",
    "\n",
    "$$\n",
    "p(h_{1:T}) = p(h_1)\\prod_{t=2}^T p(h_t | h_{t-1})\n",
    "$$\n",
    "\n",
    "where $p(h_1)$ is the initial state distribution of the Markov chain, $p(h_t | h_{t-1})$ are the Markov chain transitions, each state $h_t$ only depends on the previous state $h_{t-1}$ (not two or more steps, just the previous step), and $T$ is the length of the sentence.\n",
    "\n",
    "Then each latent state generates a word:\n",
    "\n",
    "$$\n",
    "p(v_{1:T} | h_{1:T}) = \\prod_{t = 1}^T p(v_t | h_t)\n",
    "$$\n",
    "\n",
    "where $p(v_t | h_t)$ is the emission distribution and each word $v_t$ only depends on its corresponding latent state $h_t$ (not previous word $v_{h-1}$, nor the previous states).\n",
    "\n",
    "We use the word **dependency structure** or **independence assumptions** to refer to the above two facts, namely $h_t$ only depends on $h_{t-1}$ and $v_t$ only depends on $h_t$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "welsh-charm",
   "metadata": {},
   "source": [
    "# Why is it called Hidden Markov Model?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "owned-scottish",
   "metadata": {},
   "source": [
    "* **Hidden**: the template [Subject -> Verb -> Object] is hidden since typically, we only observed the generated sentence, not its template.\n",
    "* **Markov**: each latent state depends only on its previous state. This is also called the **Markovian** Property.\n",
    "* **Model**: this is a model that we use to describe human language, which may not necessarily be true about our language. A model will usually have gaps to the actual things that are being modeled."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "secret-charles",
   "metadata": {},
   "source": [
    "# Parametrisation of HMM"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "organic-dominant",
   "metadata": {},
   "source": [
    "To model the above simple language with an HMM, we need the following parameters:\n",
    "\n",
    "* initial distribution $p(h_1)$\n",
    "* transition distribution $p(h_t|h_{t-1})$\n",
    "* emission distribution $p(v_t|h_t)$\n",
    "\n",
    "The word **parametrisation** means the specification of the parameters of a model. In the current HMM case, this corresponds to the specification of the above distributions. Because we are modelling a simplistic language model we choose to parametrise the above distributions using (conditional) probability tables.\n",
    "\n",
    "For the initial distribution $p(h_1)$, since all sentences starts with a subject or an adjective that modifies the subject, we assume the following probability\n",
    "\n",
    "| Subject | Adjective | Adverb | Verb | Object | \\<EOS\\> | \n",
    "| ------- | --------- | ------ | ---- | ------ | ------- |\n",
    "| 0.7     | 0.3       | 0      | 0    | 0      | 0       |\n",
    "\n",
    "where the tag `<EOS>` denotes the end-of-sentence. We represent this probability table below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "competitive-sugar",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.247194Z",
     "start_time": "2022-02-13T12:07:47.240571Z"
    }
   },
   "outputs": [],
   "source": [
    "initial = [0.7, 0.3, 0., 0., 0., 0.]\n",
    "id2state = {0: 'Subject', 1: 'Adjective', 2: 'Adverb', 3: 'Verb', 4: 'Object', 5: '<EOS>'}\n",
    "state2id = {id2state[s]: s for s in id2state}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sexual-church",
   "metadata": {},
   "source": [
    "The variable `inital` is a vector of length $N = 6$, $N$ being the number of latent states. \n",
    "\n",
    "We can get the initial state probability by doing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "protected-particle",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.252948Z",
     "start_time": "2022-02-13T12:07:47.248361Z"
    }
   },
   "outputs": [],
   "source": [
    "initial[state2id['Subject']]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "clinical-mandate",
   "metadata": {},
   "source": [
    "For the transition distribution , we assume the following conditional probability table:\n",
    "\n",
    "| -         | Subject | Adjective | Adverb | Verb | Object    | \\<EOS\\> |\n",
    "| -------   | ------- | --------- | ----   | ---- | --------- | ------- |\n",
    "| Subject   | 0       | 0         | 0.3    | 0.7  | 0         | 0       |\n",
    "| Adjective | 0.4     | 0.1       | 0      | 0    | 0.5       | 0       |\n",
    "| Adverb    | 0.0     | 0.3       | 0      | 0.7  | 0         | 0       |\n",
    "| Verb      | 0       | 0.3       | 0.2    | 0    | 0.5       | 0       |\n",
    "| Object    | 0       | 0         | 0      | 0    | 0         | 1       |\n",
    "\n",
    "Note that this is a conditional probability table, since the rows of the table sum to 1. The table is organised so that $p(h_t=k | h_{t-1}=k')$ is in row $k'$ and column $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "metric-therapy",
   "metadata": {},
   "source": [
    "Notice the following:\n",
    "* A subject can transition to a verb (I like), or an adverb that modifies a verb (I really like).\n",
    "* An adjective can modify a subject (Handsome Jack), another adjective (cool handsome Jack), or an object (cute dog)\n",
    "* An adverb modifies a verb (really like) or an adjective (really cute)\n",
    "* A verb may transition to an object (like dogs), to an adjective (like cute dogs), or an adverb (like really cute dogs)\n",
    "* The object is the end state and hence always transitions to the \\<EOS\\>. The table does not contain a row for \\<EOS\\> since we use it to terminate the HMM and it does not transition to any other state.\n",
    "\n",
    "We represent the described transition distribution below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "hungarian-savage",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.255588Z",
     "start_time": "2022-02-13T12:07:47.253601Z"
    }
   },
   "outputs": [],
   "source": [
    "transition = np.array([[0., 0., 0.3, 0.7, 0., 0.], \n",
    "                       [0.4, 0.1, 0., 0., 0.5, 0.], \n",
    "                       [0., 0.3, 0., 0.7, 0., 0.],\n",
    "                       [0., 0.3, 0.2, 0., 0.5, 0.],\n",
    "                       [0., 0., 0., 0., 0., 1.],\n",
    "                      ])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "portuguese-warrior",
   "metadata": {},
   "source": [
    "So the variable `transition` is a $N-1 \\times N$, i.e., $5 \\times 6$ matrix. \n",
    "\n",
    "`transition[i][j]` means the probability from state i to state j.\n",
    "\n",
    "For example, `transition[0][3]` means transition from subject to verb (we start the index from 0)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "reflected-speech",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.257947Z",
     "start_time": "2022-02-13T12:07:47.256499Z"
    }
   },
   "outputs": [],
   "source": [
    "assert(transition[0][3] == transition[state2id['Subject']][state2id['Verb']])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "demographic-aside",
   "metadata": {},
   "source": [
    "With the initial and the transition distributions, we are able to generate sentence templates by sampling from the Markov chain:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "continuous-europe",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.260615Z",
     "start_time": "2022-02-13T12:07:47.258537Z"
    }
   },
   "outputs": [],
   "source": [
    "# Sample the initial state of the Markov chain\n",
    "num_states = len(initial)\n",
    "h = np.random.choice(num_states, p=initial)\n",
    "# Sample subsequent states using the conditional probability table\n",
    "h_total = []\n",
    "h_total.append(h)\n",
    "while(h != state2id['<EOS>']):\n",
    "    h = np.random.choice(num_states, p=transition[h])\n",
    "    h_total.append(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "failing-speaker",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.263093Z",
     "start_time": "2022-02-13T12:07:47.261319Z"
    }
   },
   "outputs": [],
   "source": [
    "print(h_total)\n",
    "print(' '.join([id2state[h] for h in h_total]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "neither-difference",
   "metadata": {},
   "source": [
    "For the emission distribution, we assume:\n",
    "\n",
    "| -         | I    | He   | Jack | Mary | likes | loves | hates | really | extremely | pretty | cute | adorable | cats | dogs | . |\n",
    "| -------   | ---  | ---  | ---- | ---- | ---- | ---- | ---- | ------ | --------- | ------ | ---- | -------- | ---- | ---- | ---- |\n",
    "| Subject   | 0.2  | 0.2  | 0.2  | 0.2  | 0    | 0    | 0    | 0      | 0         | 0      | 0    | 0        | 0.1  | 0.1  | 0   |\n",
    "| Adjective | 0    | 0    | 0    | 0    | 0    | 0    | 0    | 0      | 0         | 0.5    | 0.25 | 0.25     | 0    | 0    |   0 |\n",
    "| Adverb    | 0    | 0    | 0    | 0    | 0    | 0    | 0    | 0.25   | 0.25      | 0.5    | 0    | 0        | 0    | 0    | 0 |\n",
    "| Verb      | 0    | 0    | 0    | 0    | 0.3  | 0.4  | 0.3  | 0      | 0         | 0      | 0    | 0        | 0    | 0    | 0 |\n",
    "| Object    | 0    | 0    | 0.2  | 0.2  | 0    | 0    | 0    | 0      | 0         | 0      | 0    | 0        | 0.3  | 0.3  | 0 |\n",
    "| \\<EOS\\>  | 0    | 0    | 0  | 0  | 0    | 0    | 0    | 0      | 0         | 0      | 0    | 0        | 0  | 0  | 1 |\n",
    "\n",
    "Note, again that the table above represents a conditional probability table, hence each row sums to 1."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "useful-mining",
   "metadata": {},
   "source": [
    "Notice: shared vocabulary. Different states may generate the same words:\n",
    "* In the above emission, the word \"Jack\" and \"Mary\" can be either a subject or an object\n",
    "* Similarly, the word \"pretty\" can be an adjective or an adverb\n",
    "* This shared vocabulary may causes difficulties in inference and learning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "spread-wedding",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.266656Z",
     "start_time": "2022-02-13T12:07:47.263678Z"
    }
   },
   "outputs": [],
   "source": [
    "emission = np.array([\n",
    "    [0.2, 0.2, 0.2, 0.2, 0, 0, 0, 0, 0, 0, 0, 0, 0.1, 0.1, 0.],\n",
    "    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0.5, 0.25, 0.25, 0, 0, 0.],\n",
    "    [0, 0, 0, 0, 0, 0, 0, 0.25, 0.25, 0.5, 0, 0, 0, 0, 0],\n",
    "    [0, 0, 0, 0, 0.3, 0.4, 0.3, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 0, 0.2, 0.2, 0, 0, 0, 0, 0, 0, 0, 0, 0.3, 0.3, 0],\n",
    "    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1.]\n",
    "    ])\n",
    "word2id = {'I': 0, 'He': 1, 'Jack': 2, 'Mary': 3, 'likes': 4, 'loves': 5, 'hates': 6, 'really': 7, 'extremely': 8, 'pretty': 9, 'cute': 10, 'adorable': 11, 'cats': 12, 'dogs': 13, '.': 14}\n",
    "id2word = {word2id[w]: w for w in word2id}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baf86204",
   "metadata": {},
   "source": [
    "It can be helpful to visualise the model with a state-transition diagram:\n",
    "\n",
    "![State-transition diagram of the simple NLP model](./figures/pmr-hmm-nlp-state-diagram.png)\n",
    "\n",
    "Where we have used solid nodes to represent the hidden states, solid arrows to represent the hidden state transitions, and tables with incoming dashed arrows to represent the emissions.\n",
    "\n",
    "Note that a state-transition diagram is just a visualisation of the dynamics of the model, it is _not_ a probabilistic graphical model."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "comfortable-genealogy",
   "metadata": {},
   "source": [
    "# Generating Sentences by Sampling from the HMM"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "italic-possession",
   "metadata": {},
   "source": [
    "To generate sentences, we firstly generate the template of a sentence (latent states), then generate words conditioned on the states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "painted-brick",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-02-13T12:07:47.270553Z",
     "start_time": "2022-02-13T12:07:47.267215Z"
    }
   },
   "outputs": [],
   "source": [
    "def generate(initial, transition, emission):\n",
    "    # Sample the initial state\n",
    "    num_states = len(initial)\n",
    "    num_words = emission.shape[1]\n",
    "\n",
    "    # Sample the subsequent states and words\n",
    "    h = np.random.choice(num_states, p=initial)\n",
    "    h_total = [h]\n",
    "    v_total = []\n",
    "    while(h != state2id['<EOS>']):\n",
    "        v = np.random.choice(num_words, p=emission[h])\n",
    "        v_total.append(v)\n",
    "        h = np.random.choice(num_states, p=transition[h])\n",
    "        h_total.append(h)\n",
    "    v = np.random.choice(num_words, p=emission[h])\n",
    "    v_total.append(v)\n",
    "    return h_total, v_total\n",
    "\n",
    "h_total, v_total = generate(initial, transition, emission)\n",
    "print(h_total)\n",
    "print(' '.join([id2state[h] for h in h_total]))\n",
    "print(v_total)\n",
    "print(' '.join([id2word[v] for v in v_total]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "frequent-waterproof",
   "metadata": {},
   "source": [
    "# Rethinking the Independence Assumption"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "confused-apparatus",
   "metadata": {},
   "source": [
    "Have you noticed something wrong with the above model? \n",
    "\n",
    "If you run the above sampling code multiple times, you may get a result like this:\n",
    "\n",
    "```\n",
    "Adjective Object <EOS>\n",
    "adorable Jack .\n",
    "```\n",
    "\n",
    "This is not a legitimate sentence since it does not contain a verb (every legitimate sentence should contain at least one verb).\n",
    "The reason this sentence is generated is that the object can be directly generated by the adjective, although in this case, the adjective should really generate a subject (rather than the object)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "packed-sacrifice",
   "metadata": {},
   "source": [
    "You may also get the following sample:\n",
    "\n",
    "```\n",
    "Subject Verb Object <EOS>\n",
    "I hates dogs .\n",
    "```\n",
    "\n",
    "The generated sentence is gramatically incorrect since the verb is in the third-person form even though really be in the first-person form. There are two reasons for this: firstly, that our emission distribution does not contain the first-person from of the verb; and secondly, that the use of the first- or second-person forms of a verb may depend on the previous words in the sentence."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "quarterly-spider",
   "metadata": {},
   "source": [
    "Additionally, you may also get a sample like this:\n",
    "\n",
    "```\n",
    "Subject Verb Adverb Adjective Subject Verb Adverb Verb Adjective Object <EOS>\n",
    "dogs love extremely adorable cats love really like adorable dogs .\n",
    "\n",
    "```\n",
    "\n",
    "This is not a legitimate sentence since it contains two subjects (the second subject should really be an object)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "outdoor-witch",
   "metadata": {},
   "source": [
    "Why may these problems occur? \n",
    "\n",
    "Because each latent state depends only on its previous state, while being ignorant about any other possible dependencies. For example, the transition to an object should also depend on whether there already is a verb in the sentence. \n",
    "\n",
    "This problem is a limitation of first-order hidden Markov models, since first-order HMMs cannot model **long-term dependencies**. \n",
    "\n",
    "To fix this problem, one solution is to **increase the dependency order**, e.g., to make the state at step t to depend on all states from 1 to t - 1, rather than just t - 1. We will stop here. If you are interested read [autoregressive language modeling with recurrent neural networks](https://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture06-rnnlm.pdf) for more details."
   ]
  }
 ],
 "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.8.12"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}