{"id":562,"date":"2013-08-13T18:39:13","date_gmt":"2013-08-13T22:39:13","guid":{"rendered":"http:\/\/learninglover.com\/blog\/?p=562"},"modified":"2013-08-21T05:38:32","modified_gmt":"2013-08-21T09:38:32","slug":"hidden-markov-models-the-forward-algorithm","status":"publish","type":"post","link":"https:\/\/learninglover.com\/blog\/index.php\/2013\/08\/13\/hidden-markov-models-the-forward-algorithm\/","title":{"rendered":"Hidden Markov Models: The Forward Algorithm"},"content":{"rendered":"<p>I just finished working on <a href=\"http:\/\/www.learninglover.com\/examples.php?id=45\">LEARNINGlover.com: Hidden Marokv Models: The Forward 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 number of 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 Evaluation Problem, which asks the question &#8220;What is the probability that the given sequence of observations O = o<sub>1<\/sub>, o<sub>2<\/sub>, &#8230;, o<sub>T<\/sub> are generated by the HMM <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/lambda.gif\">. In general, this calculation, p{O | <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/lambda.gif\">}, can be calculated by simple probability. However because of the complexity of that calculation, there are more efficient methods. <\/p>\n<p>The forward algorithm is one such method. It creates an auxiliary variable <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/alpha.gif\"><sub>t<\/sub>(i) which is the probability that the model <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/lambda.gif\"> has generated the partially observed sequence o<sub>1<\/sub>, &#8230;, o<sub>t<\/sub>, where 1 <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> t <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> T. This variable can be calculated by the following formula: <\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/alpha.gif\"><sub>t+1<\/sub>(j) = b<sub>j<\/sub>(o<sub>t+1<\/sub>)<img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/csigma.gif\"><sub>i = 1 to N<\/sub>(<img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/alpha.gif\"><sub>t<\/sub>(i)a<sub>ij<\/sub>), where 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, 1 <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> t <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/leqq.gif\"> T-1. <\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/alpha.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 the <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/alpha.gif\"><sub>t<\/sub>(j) variables, we can solve the evaluation problem by p{O | <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/lambda.gif\"> } = <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/csigma.gif\"><sub>i = 1 to N<\/sub> <img decoding=\"async\" src=\"http:\/\/www.learninglover.com\/chars\/alpha.gif\"><sub>T<\/sub>(i)<\/p>\n<p>There is more on this example at <a href=\"http:\/\/www.learninglover.com\/examples.php?id=45\">LEARNINGlover.com: Hidden Marokv Models: The Forward 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 Forward 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-562","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/562","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=562"}],"version-history":[{"count":0,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/562\/revisions"}],"wp:attachment":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=562"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=562"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=562"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}