{"id":633,"date":"2013-08-18T23:46:42","date_gmt":"2013-08-19T03:46:42","guid":{"rendered":"http:\/\/learninglover.com\/blog\/?p=633"},"modified":"2013-08-21T05:37:52","modified_gmt":"2013-08-21T09:37:52","slug":"hidden-markov-models-the-viterbi-algorithm","status":"publish","type":"post","link":"https:\/\/learninglover.com\/blog\/index.php\/2013\/08\/18\/hidden-markov-models-the-viterbi-algorithm\/","title":{"rendered":"Hidden Markov Models: The Viterbi Algorithm"},"content":{"rendered":"<p>I just finished working on <a href=\"http:\/\/www.learninglover.com\/examples.php?id=47\">LEARNINGlover.com: Hidden Marokv Models: The Viterbi Algorithm<\/a>. Here is an introduction to the script. <\/p>\n<p>Suppose you are at a table at a casino and notice that things don&#8217;t look quite right. Either the casino is extremely lucky, or things should have averaged out more than they have. You view this as a pattern recognition problem and would like to understand the number of &#8216;loaded&#8217; dice that the casino is using and how these dice are loaded. To accomplish this you set up a number of Hidden Markov Models, where the loaded die are the latent variables, and would like to determine which of these, if any is more likely to be using.<\/p>\n<p>First lets go over a few things. <\/p>\n<p>We will call each roll of the dice an observation. The observations will be stored in variables <i>o<sub>1<\/sub>, o<sub>2<\/sub>, &#8230;, o<sub>T<\/sub><\/i>, where <i>T<\/i> is the number of total observations. <\/p>\n<p>To generate a hidden Markov Model (HMM) <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/lambda.gif\"> we need to determine 5 parameters:<\/p>\n<ul>\n<li> The N states of the model, defined by S = {S<sub>1<\/sub>, &#8230;, S<sub>N<\/sub>}\n<li> The M possible output symbols, defined by <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/csigma.gif\"> = {<img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/sigma.gif\"><sub>1<\/sub>, <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/sigma.gif\"><sub>2<\/sub>, &#8230;, <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/sigma.gif\"><sub>M<\/sub>}\n<li> The State transition probability distribution A = {a<sub>ij<\/sub>}, where a<sub>ij<\/sub> is the probability that the state at time t+1 is S<sub>j<\/sub>, given that the state at time t is S<sub>i<\/sub>.\n<li> The Observation symbol probability distribution B = {b<sub>j<\/sub>(<img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/sigma.gif\"><sub>k<\/sub>)} where b<sub>j<\/sub>(<img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/sigma.gif\"><sub>k<\/sub>) is the probability that the symbol <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/sigma.gif\"><sub>k<\/sub> is emitted in state S<sub>j<\/sub>.\n<li> The initial state distribution <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/pi.gif\"> = {<img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/pi.gif\"><sub>i<\/sub>}, where <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/pi.gif\"><sub>i<\/sub> is the probability that the model is in state S<sub>i<\/sub> at time t = 0.\n<\/ol>\n<p>The HMMs we&#8217;ve generated are based on two questions. For each question, you have provided 3 different answers which leads to 9 possible HMMs. Each of these models has its corresponding state transition and emission distributions. <\/p>\n<ul>\n<li>How often does the casino change dice?\n<ul>\n<li>0) Dealer Repeatedly Uses Same Dice\n<li>1) Dealer Uniformly Changes Die\n<li>2) Dealer Rarely Uses Same Dice\n<\/ul>\n<li>Which sides on the loaded dice are more likely?\n<ul>\n<li>0) Larger Numbers Are More Likely\n<li>1) All Numbers Are Equally Likely\n<li>2) Smaller Numbers Are More Likely\n<\/ul>\n<\/ul>\n<table>\n<tr>\n<td><\/td>\n<td>How often does the casino change dice?<\/td>\n<\/tr>\n<tr>\n<td>Which sides on <br \/>the loaded dice <br \/>are more likely?<\/td>\n<td>\n<table>\n<tr>\n<td>(0, 0)<\/td>\n<td>(0, 1)<\/td>\n<td>(0, 2)<\/td>\n<\/tr>\n<tr>\n<td>(1, 0)<\/td>\n<td>(1, 1)<\/td>\n<td>(1, 2)<\/td>\n<\/tr>\n<tr>\n<td>(2, 0)<\/td>\n<td>(2, 1)<\/td>\n<td>(2, 2)<\/td>\n<\/tr>\n<\/table>\n<\/td>\n<\/tr>\n<\/table>\n<p>One of the interesting problems associated with Hidden Markov Models is called the Decoding Problem, which asks the question &#8220;What is the most likely sequence of states that the HMM <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/lambda.gif\"> would go through to generate the sequence O = o<sub>1<\/sub>, o<sub>2<\/sub>, &#8230;, o<sub>T<\/sub>? <\/p>\n<p>The Viterbi algorithm finds answers this question using Dynamic Programming. It creates an auxiliary variable <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/delta.gif\"><sub>t<\/sub>(i) which has the highest probability that the partial observation sequence o<sub>1<\/sub>, &#8230;, o<sub>t<\/sub> can have, given that the current state is i. This variable can be calculated by the following formula: <\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/delta.gif\"><sub>t<\/sub>(i) = max<sub>q<sub>1<\/sub>, &#8230;, q<sub>t-1<\/sub> p{q<sub>1<\/sub>, &#8230;, q<sub>t-1<\/sub>, q<sub>t<\/sub> = i, o<sub>1<\/sub>, &#8230;, o<sub>t<\/sub> | <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/delta.gif\">}. <\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/delta.gif\"><sub>1<\/sub>(j) = <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/pi.gif\"><sub>j<\/sub>b<sub>j<\/sub>(o<sub>1<\/sub>), for 1 <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> j <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> N. <\/p>\n<p>Once we have calculated <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/delta.gif\"><sub>t<\/sub>(j) we also keep a pointer to the max state. We can then find the optimal path by looking at arg max <sub>1 <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> j <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> N<\/sub> <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/delta.gif\"><sub>T<\/sub>(j) and then backtrack the sequence of states using the pointer. <\/p>\n<p>There is more on this example at <a href=\"http:\/\/www.learninglover.com\/examples.php?id=47\">LEARNINGlover.com: Hidden Marokv Models: The Viterbi Algorithm<\/a>. <\/p>\n<p>Some further reading on Hidden Markov Models: <\/p>\n<ul>\n<li><a href=\"http:\/\/pure.rhul.ac.uk\/portal\/files\/1446635\/Hidden_Markov_Models_Theory_and_Applications.pdf\">Hidden Markov Models, Theory and Applications<\/a>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>I just finished working on LEARNINGlover.com: Hidden Marokv Models: The Viterbi Algorithm. Here is an introduction to the script. Suppose you are at a table at a casino and notice that things don&#8217;t look quite right. Either the casino is extremely lucky, or things should have averaged out more than they have. You view this [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-633","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=633"}],"version-history":[{"count":0,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/633\/revisions"}],"wp:attachment":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}