2b:null 2c:["$","title",null,{"children":"Hidden-Markov Models | William Pang | Observable"}] 31:T72d,//Credit to: https://gist.github.com/stephband/8237123 function Viterbi(data) { var V = [{}]; //V acts as the "alpha" var path = {}; // Initialize base cases (t == 0) for(var i=0;i 0 for(var t=1;t max[0]) max = [calc,state0]; } V[t][state] = max[0]; newpath[state] = path[max[1]].concat(state); /* Backpointer max[1] = [state0] concat combines two arrays together, yielding a new array with [state0,state] Recall that we only need to know the store the maximum of the previous hidden state for each one of the two current hidden states */ } path = newpath; } var max = [0,null]; for(var i=0;i max[0]) max = [calc,state]; } return [max[0], path[max[1]]]; }32:[{"id":"0ddc4b03b056fe11215f09cd14eb19fb46af0483101c044f408f03e623e638b559c61e88005950760d7e5c317ab6dec071e488d7dad3ecf858a43ec4e2f65fb6","href":"https://static.observableusercontent.com/files/0ddc4b03b056fe11215f09cd14eb19fb46af0483101c044f408f03e623e638b559c61e88005950760d7e5c317ab6dec071e488d7dad3ecf858a43ec4e2f65fb6","name":"Matrix_diagram.jpg","type":"image/jpeg","lastModified":1642993167443.091,"size":154907},{"id":"5b67dd9a41d5765b417e874f7dc024fd7ee0194d119e27f11b813dc4b576cb82f75a52fe445c8fa57dcef13e29da61d358a10c3cd5e86a5d7deafc342dc2e690","href":"https://static.observableusercontent.com/files/5b67dd9a41d5765b417e874f7dc024fd7ee0194d119e27f11b813dc4b576cb82f75a52fe445c8fa57dcef13e29da61d358a10c3cd5e86a5d7deafc342dc2e690","name":"TheDiagram@1.jpg","type":"image/jpeg","lastModified":1643209252084.582,"size":397522},{"id":"db60bf03710bf6a3c9e7cd56cfc0613c60ed8a4b4e4ab15ab368af7c332193e633f6e854f0b2936d364f49edf1e8efdc2061a7752d8027fa4d55c6097e72c920","href":"https://static.observableusercontent.com/files/db60bf03710bf6a3c9e7cd56cfc0613c60ed8a4b4e4ab15ab368af7c332193e633f6e854f0b2936d364f49edf1e8efdc2061a7752d8027fa4d55c6097e72c920","name":"Screen Shot 2022-01-26 at 10.06.47 AM.png","type":"image/png","lastModified":1643209667594.73,"size":167880}] 2f:{"id":"84f7b3352f8dc719","slug":"hidden-markov-models","title":"Hidden-Markov Models","thumbnail":"cf3bedc863d53d9550b34c242c02b1f2317d95bcd52438626085dae7158fddb0","access_level":"public","create_time":"$D2022-01-22T21:36:08.875Z","update_time":"$D2022-01-30T19:11:33.805Z","view_time":null,"first_public_time":"$D2022-01-26T02:07:36.189Z","fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"88df4b53b2fce8d2","login":"will-pang","name":"William Pang","avatar_url":"https://avatars-next.observableusercontent.com/4e5603477ef111cf1fc74cb0aab0dd58ddab37219e1b2a4e5e9c3d082c5532a0","tier":"starter_2024"},"version":905,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"30424cd7adf510bb","login":"williampangbest1","name":"William Pang","avatar_url":"https://avatars-next.observableusercontent.com/4e5603477ef111cf1fc74cb0aab0dd58ddab37219e1b2a4e5e9c3d082c5532a0","tier":null}],"members":[{"type":"individual","id":"30424cd7adf510bb","login":"williampangbest1","name":"William Pang","avatar_url":"https://avatars-next.observableusercontent.com/4e5603477ef111cf1fc74cb0aab0dd58ddab37219e1b2a4e5e9c3d082c5532a0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":2,"collection":{"id":"346a7806b7ef1030","slug":"half-baked","title":"Half-Baked","owner":{"id":"88df4b53b2fce8d2","login":"will-pang","name":"William Pang"}},"type":"notebook","body":{"title":"Hidden-Markov Models","cells":[{"id":0,"value":"# Hidden-Markov Models","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":301,"value":"This example was taken from lecture [slides](https://cs.wmich.edu/elise/courses/cs626/s12/HiddenMarkovModels.pdf) online provided by CS626 at Western Michigan University. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":424,"value":"md `\n## Set up\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":193,"value":"dot`\ndigraph{\nrankdir=\"TB\";\n\na -> b [label=\"0.7\"]\na -> a [label=\"0.3\"]\n\nb -> a [label=\"0.2\"]\nb -> b [label=\"0.8\"]\n\na -> c [style=\"dashed\";label=\"0.6\"]\na -> d [style=\"dashed\";label=\"0.4\"]\nb -> c [style=\"dashed\";label=\"0.4\"]\nb -> d [style=\"dashed\";label=\"0.6\"]\n\na [label=\"Low\"]\nb [label=\"High\"]\nc [shape=\"rectangle\",label=\"Rain\"]\nd [shape=\"rectangle\",label=\"Dry\"]\n{rank=same;a;b}\n{rank=same;c;d}\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":339,"value":"As you can see, this diagram can be confusing and jarring at times. To simplfy this diagram, we can express it in matrices:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":391,"value":"FileAttachment(\"Matrix_diagram.jpg\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":377,"value":"viewof init_mat = pt([[0.4, 0.6]], { title: \"Initial.Probabilities=\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":354,"value":"viewof tran_mat = pt([[0.3, 0.7], [0.2, 0.8]], { title: \"Transition.Matrix=\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":385,"value":"viewof emission_mat = pt([[0.6, 0.4], [0.4, 0.6]], { title: \"Emission.Matrix=\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":427,"value":"md`\n## Intuition\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":430,"value":"md`\nAs part of an assignment for your environmental health sciences class, you're asked to report whether the humidity is low or high by stepping outside of your apartment. However, you were recently binge watching Single's Inferno on Netflix, and therefore refused to step outside of your apartment. While grabbing chips in the kitchen, you inadvertently looked outside the window and noticed that the weather was filled with ${textcolor('rain', 'blue')} yesterday — giving you less motivation to even step outside of your apartment. Thankfully, the weather improved the next day as it was ${textcolor('dry', 'yellow')} — just in time to get out as your wrap up the series!\n\nThe dry/rain weather conditions are known as the **observed states** (as this is something you can see), and the humidity conditions is known as **hidden states** (since we were too lazy to step out of the room!).\n\n> **Task at hand:** To report the most likely sequence of humidity conditions \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":461,"value":"md`\n## The Brute Force Method\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":464,"value":"md`\nSuppose we want to calculate a probability of a sequence of observations in our example: ${textcolor('Dry', 'yellow')} \\u279e ${textcolor('Rain', 'blue')}\n\nDigging back to basic probability, we know that the total possible number of \"hidden state\" combinations is 4. This is because the first observed state only has 2 possible \"hidden\" states, and the second obseved state also has 2 possible \"hidden\" states. \n\n> In general: ${tex`\\text{S}^\\text{O}`} where S is the number of states, and O is the number of observations\n\nNow, let's consider all possible hidden state sequences:\n\nP({'Dry','Rain'}) =
\n**P({'Dry','Rain'},{'Low','Low'})**+
\nP({Dry','Rain'},{'Low','High'})+
\n+P({'Dry','Rain'},{'High','Low'})+
\nP({'Dry','Rain'},{'High','High'})\n\nIf we focus on the **first term** alone and recall the conditional probability formula:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":529,"value":"md`\n${tex.block`\n P(\\text{A,B}) = P(A|B) \\times P(B)\n `}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":539,"value":"md`\nWhile treating A as {'Dry','Rain'} and B as {'Low','Low'}, we get:\n\n**P({'Dry','Rain'},{'Low','Low'})** =
\nP({'Dry','Rain'}|{'Low','Low'})P({'Low','Low'}) \n\nwe can further simplify this as:
\n${tex.block`\nP('Dry'|'Low')P('Rain'|'Low')P('Low')P('Low'|'Low')\n= 0.4 \\times 0.6 \\times 0.4 \\times 0.3\n= 0.0288\n`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":563,"value":"md`\nAs you can see, this is computationally extremely tedious, even when there's only 2 states and 2 observations. We'll cheat here and reveal the hidden state sequence by using the Viterbi Algorithm (more on that really soon):\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":597,"value":"result[1]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":584,"value":"md`\nThe probability can be found by computing:
\nP({'Dry','Rain'},{'High','High'}) =
\nP({'Dry','Rain'}|{'High','High'})P({'High','High'}) \n\nwe can further simplify this as:
\n${tex.block`\nP('Dry'|'High')P('Rain'|'High')P('High')P('High'|'High')\n= 0.6 \\times 0.4 \\times 0.6 \\times 0.8\n= 0.1152\n`}\nVerfiying the probability with the Viterbi Algorithm we also get:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":812,"value":"result[0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":816,"value":"md`\n*Double Check: You can compute the other two states to show that [High \\u279e High] yields the largest probability.*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":609,"value":"md`\n## The Viterbi Algorithm\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":612,"value":"The Viterbi Algorithm is built on the [forward algorithm](https://www.youtube.com/watch?v=9-sPm4CfcD0) and is an example of dynamic programming. This implementation was taken from [Github](https://gist.github.com/stephband/8237123).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":620,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":640,"value":"md`\nLet's up the complexity with an additional state and use a different [example](https://web.stanford.edu/~jurafsky/slp3/A.pdf) from Daniel Jurafsky & James H. Martin at Stanford.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":868,"value":"FileAttachment(\"TheDiagram@1.jpg\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":657,"value":"md`\nSetting up the initial base cases ${tex`\\alpha_1`}, we get:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":626,"value":"dot`digraph{\n rankdir=LR;\n node [shape = circle];\n\n 1 [label=\"H\"]\n 2 [label=\"\\u03C0\"]\n 3 [label=\"C\"]\n\n 2 -> 1;\n 2 -> 3 [label=\"Or\"];\n\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":663,"value":"md`\nThe probabilities for each state is stored in:\n> V[0][state]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":863,"value":"md`\nwhich are the probabilities ${tex`\\alpha_1(H)`} and ${tex`\\alpha_1(C)`} as layed out in the diagram.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":679,"value":"To find the probability for the second state, we first iterate through the j for loop, which indexes the state0 and keeps the i for loop (state) until the j-loop runs its course.\n\n>

state0 represents the \"previous\" state.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":711,"value":"So for j=0 while i=0:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":683,"value":"dot`digraph{\n    rankdir=LR;\n    node [shape = circle];\n\n    1 [label=\"H\"]\n    2 [label=\"\\u03C0\"]\n    3 [label=\"C\"]\n    4 [label=\"H\"]\n    5 [color=\"red\",label=\"C\"]\n\n    1 -> 5 \n    1 -> 4 \n    2 -> 1\n    2 -> 3 [color=\"blue\"];\n\n    3 -> 4\n    3 -> 5 [color=\"blue\"]\n\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":716,"value":"For j=1 we iterate state0, while keeping \"current\" state i=0 the same:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":723,"value":"dot`digraph{\n    rankdir=LR;\n    node [shape = circle];\n\n    1 [label=\"H\"]\n    2 [label=\"\\u03C0\"]\n    3 [label=\"C\"]\n    4 [label=\"H\"]\n    5 [color=\"red\",label=\"C\"]\n\n    1 -> 5 [color=\"blue\"]\n    1 -> 4 \n    2 -> 1 [color=\"blue\"]\n    2 -> 3;\n\n    3 -> 4\n    3 -> 5 \n\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":731,"value":"The goal is to find the sequence of hidden states that yields the **maximum** probability if we had to end at one of our two guesses for the second hidden state (in this case, ${textcolor('cold', 'steelblue')} ). The \"previous\" sequence (i.e. our best guess for the first hidden state) is stored in:\n> max = [calc][state0]","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":779,"value":"md`\ngiven that we must have ${textcolor('cold', 'steelblue')} as our second hidden state. ${textcolor('Cold', 'steelblue')} as second hidden state is stored in:\n> V[t][state]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":738,"value":"Now, lets increment i, so we get j=0 for the inner for loop and i=1 for the outer for loop:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":744,"value":"dot`digraph{\n    rankdir=LR;\n    node [shape = circle];\n\n    1 [label=\"H\"]\n    2 [label=\"\\u03C0\"]\n    3 [label=\"C\"]\n    4 [color=\"red\",label=\"H\"]\n    5 [label=\"C\"]\n\n    1 -> 5 \n    1 -> 4 \n    2 -> 1\n    2 -> 3 [color=\"blue\"];\n\n    3 -> 4 [color=\"blue\"]\n    3 -> 5 \n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":757,"value":"As well as j=1 with i=1:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":761,"value":"dot`digraph{\n    rankdir=LR;\n    node [shape = circle];\n\n    1 [label=\"H\"]\n    2 [label=\"\\u03C0\"]\n    3 [label=\"C\"]\n    4 [color=\"red\",label=\"H\"]\n    5 [label=\"C\"]\n\n    1 -> 5 \n    1 -> 4 [color=\"blue\"]\n    2 -> 1 [color=\"blue\"]\n    2 -> 3 \n\n    3 -> 4 \n    3 -> 5 \n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":769,"value":"Again, the goal is to find the sequence of hidden states that yields the **maximum** probability if we had to end at one of our two guesses for the second hidden state (in this case, ${textcolor('hot', 'red')} ). The \"previous\" sequence (i.e. our best guess for the first hidden state) is stored in:\n> max = [calc][state0]","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":805,"value":"md`\ngiven that we must have ${textcolor('hot', 'red')} as our second hidden state. ${textcolor('Hot', 'red')} as second hidden state is stored in:\n> V[t][state]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":830,"value":"By using recursion, we would continue iterating this process for all the remaining hidden states by adding on the stored probabilities from ${tex`\\alpha_n(H)`} and ${tex`\\alpha_n(C)`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":839,"value":"dot`digraph{\n    rankdir=LR;\n    node [shape = circle];\n\n    1 [label=\"H\"]\n    2 [label=\"\\u03C0\"]\n    3 [label=\"C\"]\n    4 [label=\"H\"]\n    5 [label=\"C\"]\n    6 [label=\"H\"]\n    7 [label=\"C\"]\n\n    1 -> 5 [style=dashed, color=grey]\n    1 -> 4 [style=dashed, color=grey]\n    2 -> 1 [style=dashed, color=grey]\n    2 -> 3 [style=dashed, color=grey]\n\n    3 -> 4 [style=dashed, color=grey]\n    3 -> 5 [style=dashed, color=grey]\n\n    5 -> 6\n    4 -> 7\n    5-> 7\n    4 -> 6\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":888,"value":"If including numbers helps you understand better, please refer to this [diagram](https://web.stanford.edu/~jurafsky/slp3/A.pdf).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":895,"value":"FileAttachment(\"Screen Shot 2022-01-26 at 10.06.47 AM.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":305,"value":"### Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":320,"value":"*Inputting Transition States (For Brute Force Method)*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":324,"value":" result = Viterbi({\n    states: [\n        'Low',\n        'High'\n    ],\n    observations: [\n        'Rain',\n        'Dry'\n    ],\n    start_probability: {\n        'Low': 0.4,\n        'High': 0.6\n    },\n    transition_probability: {\n        'Low' : {'Low': 0.3, 'High': 0.7},\n        'High' : {'High': 0.8, 'Low': 0.2}\n    },\n    emission_probability: {\n        'Low' : {'Rain': 0.6, 'Dry': 0.4},\n        'High' : {'Rain': 0.4, 'Dry': 0.6}\n    }\n});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":344,"value":"*Matrix Visualization*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":347,"value":"import {pt} from \"@fil/pt\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":351,"value":"math = require(\"https://unpkg.com/mathjs@6.2.5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":433,"value":"md`\n*Styling*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":437,"value":"import {textcolor} from \"@observablehq/text-color-annotations-in-markdown\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}}
30:"$2f:body"