{"id":773,"date":"2019-01-09T08:14:44","date_gmt":"2019-01-09T08:14:44","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=773"},"modified":"2019-01-09T08:56:08","modified_gmt":"2019-01-09T08:56:08","slug":"hmm-baum-welsh-and-viterbi-algorithms","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/hmm-baum-welsh-and-viterbi-algorithms\/","title":{"rendered":"HMM\u2013 Baum Welsh and Viterbi Algorithms"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/h22nGEF8PUo\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>Learning Objectives:<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the three issues of HMM\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To explain the Baum Welsh algorithm for evaluation using the model\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To discuss Viterbi algorithm for decoding\r\n\r\n&nbsp;\r\n\r\n<strong>35.1 Recap: Hidden Markov Model<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As we have already discussed Hidden Markov Model (HMM) is an extension of a Markov model in which the input symbols are not the same as the states.This means we don\u2019t know which state we are in (hence called Hidden State). For example in HMM POS-tagging, the input symbols are the words, states are the part of speech tags. In addition we make two important assumptions namely Markov assumption and Output-Input assumption. <strong>Markov assumption<\/strong> states that the state transition depends only on the origin and destination and the <strong>Output-independent assumption <\/strong>which states that all observation frames are dependent on the state that generated them, not on neighbouring observation frames.<\/p>\r\n&nbsp;\r\n\r\n<strong>35.1.1 Parameters of an HMM:<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">In Hidden Markov Models, S = {s1,\u2026,sn} is a set of states where \u2018n\u2019 is the number of possible states<\/li>\r\n \t<li style=\"text-align: justify\"><strong>Transition probabilities is a two dimensional Matrix <\/strong><em>A=<\/em> <em>a<\/em><em>1,1<\/em><em>,a<\/em><em>1,2<\/em><em>,\u2026,a<\/em><em>n,n<\/em><em>where each a<\/em><em>i,j<\/em><em>represents the probability of transitioning from state s<\/em><em>i<\/em><em>to s<\/em><em>j<\/em><em>.<\/em><\/li>\r\n \t<li style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">Emission probabilities<\/strong><span style=\"text-align: initial;font-size: 1em\">or the observation symbol distribution probabilityis aset B of functions of the form bi (ot) which is the probability of observation otbeing emitted or observed by state si<\/span><\/li>\r\n \t<li style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">Initial state distribution<\/strong><span style=\"text-align: initial;font-size: 1em\">pis the probability that si is a start state<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Therefore we have two model parameters n, the number of states of the HMM and m, the number of distinct observation symbols per state. In addition we have three probability measures A-the transition probability, B-the emission probability and p- the initial probability.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The HMM Formalism is represented as given in Figure 35.1 where {<em>S, K<\/em>, P, <em>A,<\/em> <em>B<\/em>} is the model. Here S is the state and K is the observation. <em>p<\/em> = {pi} are theinitial state probabilities, <em>A<\/em> = {a<em>ij<\/em>} are the state transition probabilities and <em>B<\/em> = {b<em>ik<\/em>} are the observation or emission state probabilities.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-776\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196.png\" alt=\"\" width=\"587\" height=\"115\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 35.1 The HMM Formalism<\/strong><\/p>\r\n&nbsp;\r\n\r\n<strong>35.1.2 Building the observation sequence<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Before we proceed further, let us understand how an observation sequence is generated. Given the above five elements, we can build an observation sequence:<\/p>\r\n<img class=\"aligncenter size-full wp-image-778\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-197.png\" alt=\"\" width=\"185\" height=\"49\" \/>\r\n\r\nwhere T is the number of observations . This observation sequence is built as follows:\r\n\r\n&nbsp;\r\n\r\n1.We first set\u00a0 t=1.\r\n\r\n&nbsp;\r\n\r\n2. Then we choose an initial state\r\n\r\nq<sub>i=<\/sub>S<sub>i<\/sub>\r\n\r\n&nbsp;\r\n<p style=\"text-align: left\">according to the initial distribution.<\/p>\r\n&nbsp;\r\n\r\n3. Then we choose\r\n\r\nO<sub>t<\/sub>=V<sub>k<\/sub>\r\n\r\naccording to the symbol probability distribution.\r\n\r\n&nbsp;\r\n\r\n4. Then we transit to a new state\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">q<\/span><sub style=\"text-align: initial\">t+1=<\/sub>S<sub>j<\/sub>\r\n\r\n<\/div>\r\n<div>\r\n\r\naccording to the state transition probability distribution.\r\n\r\n&nbsp;\r\n\r\n5.\u00a0\u00a0 Then we set t t=t+1, and iterate by returning to step 3 while t&lt;=T\r\n\r\n&nbsp;\r\n\r\n<strong>35.2\u00a0 The Three Problems of HMM<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe following are the three problems associated with HMM:\r\n\r\n&nbsp;\r\n\r\nProblem 1: <strong>Evaluation<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here given the observation sequence <em>O=o<\/em><em>1<\/em><em>,\u2026,o<\/em><em>T<\/em>and an HMM model how do we compute the probability of O given the model?<\/p>\r\n&nbsp;\r\n\r\n<strong>Q1<\/strong>:<strong> How do we compute the probability of a given sequence of observations?<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>A1: <\/strong>Forward \u2013 Backward dynamic programming algorithm \u2013<strong> the Baum Welch algorithm<\/strong>\r\n\r\n&nbsp;\r\n\r\nProblem 2: <strong>Decoding<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here given the observation sequence <em>O=o<\/em><em>1<\/em><em>,\u2026,o<\/em><em>T<\/em>and an HMM model, how do we find the state sequence that best explains the observations?<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>Q2:How to compute the most probable sequence of sequence of observations? s<\/strong><strong>tates, given a<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">A2: Viterbi\u2019s <\/strong><span style=\"text-align: initial;font-size: 1em\">dynamic programming Algorithm<\/span>\r\n\r\n&nbsp;\r\n\r\n<span style=\"font-size: 1em;text-align: initial\">Given an observation sequence, compute the most likely hidden state sequence<\/span>\r\n\r\n&nbsp;\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Problem 3: <\/span><strong style=\"text-align: initial;font-size: 1em\">Learning<\/strong>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\nHere given an observation sequence and set of possible models, which model most closely fits\u00a0 the\u00a0 data? How do we adjust the model parameters\r\n\r\n<img class=\"aligncenter size-full wp-image-780\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-199.png\" alt=\"\" width=\"211\" height=\"44\" \/>\r\n\r\nto maximize\r\n\r\n<img class=\"aligncenter size-full wp-image-781\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-200.png\" alt=\"\" width=\"146\" height=\"48\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>Q3: Given an observation sequence and set of possible models, which model most closely fits the data?<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>A3: The Expectation Maximization (EM) heuristic.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">35.3\u00a0 Markov Assumption with an Example<\/strong>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us discuss the Markov assumptions with an example. Let us assume that we have a sentence with n words. The Markov assumption states that probability of the occurrence of word wi at time t depends only on occurrence of word wi-1 at time t-1.<\/p>\r\n&nbsp;\r\n\r\nThe normal chain rule would be as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-782\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201.png\" alt=\"\" width=\"559\" height=\"102\" \/>\r\n\r\nHowever the Markov Assumption approximates the probability of the sequence of words as:\r\n\r\n<img class=\"aligncenter size-full wp-image-783\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202.png\" alt=\"\" width=\"491\" height=\"99\" \/>\r\n\r\n&nbsp;\r\n\r\nA common way of representing the Hidden Markov Model is the Trellis Diagram shown in Figure 35.2\r\n\r\n<img class=\"aligncenter size-full wp-image-784\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203.png\" alt=\"\" width=\"593\" height=\"274\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 35.2 Trellis Diagram<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">In this diagram we have the starting state s0 which influences the states s1,1,s1,2,s1,3,s1,4 with observation at time t1 being o1 and so on until finally we end up with the states sT,1,sT,2,sT,3,sT,4at time t T.<\/p>\r\n&nbsp;\r\n\r\n<strong>35.4 Problem 1 - Evaluation - Forward and Backward Algorithms<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Here given the observation sequence <\/span><em style=\"text-align: initial;font-size: 1em\">O=o<\/em><em style=\"text-align: initial;font-size: 1em\">1<\/em><em style=\"text-align: initial;font-size: 1em\">,\u2026,o<\/em><em style=\"text-align: initial;font-size: 1em\">T<\/em><span style=\"text-align: initial;font-size: 1em\">and an HMM model we need to compute the probability of O given the model that is we are given a sequence of observations and we need to compute the probability of that specific sequence of observations. This likelihood of a sequence can be determined by either the forward procedure or the backward procedure. We will discuss the Forward algorithm which is essentially a dynamic programming algorithm. Backward algorithm can be similarly explained. The Forward algorithm can be used with two options, one the \u201cAny Path\u201d methodwhere the likelihood is measured using any sequence of states of length T, and the second option the \u201cBest Path\u201d method where we choose an HMM by the probability generated using the best possible sequence of states . Solving the evaluation problem involves the determination of the probability that a particular sequence of symbols O was generated by that model (Figure 35.3). Here the model starts at state q1 with initial probability pq1, followed by the transition probabilities aq1,q2, \u2026\u2026\u2026\u2026\u2026.aqT-1,qT.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-785\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204.png\" alt=\"\" width=\"588\" height=\"210\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>35.4.1 Forward Probabilities:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We need to determine the forward probability that, given an HMM l, at time t the state is i and the partial observation o1 \u2026 ot has been generated that is<\/p>\r\n<img class=\"aligncenter size-full wp-image-786\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205.png\" alt=\"\" width=\"482\" height=\"37\" \/>\r\n<p style=\"text-align: justify\">Here we start from the initial state and calculate the probability of each subsequent state in the forward direction, and hence this probability is called the forward probability.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-787\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206.png\" alt=\"\" width=\"558\" height=\"341\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 35.4 Forward Probability<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The forward probability at a time slice t of a state j is the sum of each the N forward probabilities i at time slice t-1 multiplied by the transition probability of each state i at time slice t-1 to the state j under consideration t time slice t (Figure 35.4). This sum is then multiplied by the emission probability of observing ot at state j.<\/p>\r\n<img class=\"aligncenter size-full wp-image-788\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-207.png\" alt=\"\" width=\"334\" height=\"59\" \/>\r\n\r\n<strong>35.4.2 Forward recursion:<\/strong>\r\n\r\n&nbsp;\r\n\r\nAs we have already discussed forward probability\r\n\r\n<img class=\"aligncenter size-full wp-image-789\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-208.png\" alt=\"\" width=\"330\" height=\"48\" \/>\r\n\r\nis calculated using forward recursion. The initialization is as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-790\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-209.png\" alt=\"\" width=\"195\" height=\"55\" \/>\r\n\r\nHere the initial forward probability of state i at time slice 1 is the product of the initial probability of state i and the probability of emitting the observation o1 at state i at time slice 1. The forward recursion is determined as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-791\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210.png\" alt=\"\" width=\"367\" height=\"99\" \/>\r\n\r\nHere the forward probability at time slice t+1 is determined by considering the forward probabilities of all states at time slot t, the transition probabilities from\u00a0<span style=\"text-align: initial;font-size: 1em\">state i to state j (the state whose forward probability is to be determined) and the emission probability of the observation at time slice t+1 at state j. Finally we have the termination as follows:<\/span>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-792\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211.png\" alt=\"\" width=\"573\" height=\"94\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>35.4.3 Example for the Calculation of Forward Probability<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We show an example for the calculation of forward probabilities (Figure 35.5). Here there are three states which can emit the observations R,G and B. We have the observation sequence R,R,G,B. Now the initial probability shows that the start state is 1. The probability of state 1 emitting R is 0.6, G is 0.2, B is 0.2. The probabilities of state 2 and state 3 being the initial state is 0. The probabilities of state 2 emitting R is 0.2, G is 0.5, B is 0.3.and the probabilities of state 3 emitting R is 0.0, G is 0.3, B is 0.7. The transition probabilities from each state to all the other states are also shown in the Figure. At time slot 1 we have the probability of only state 1 and it emitting R is 0.6. Now let us calculate the forward probabilities of each of the states at the time slice 2 with observation being R.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-793\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212.png\" alt=\"\" width=\"608\" height=\"468\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 35.5 Example for Calculation of Forward Probabilities<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us calculate the forward probabilities of each of the states at the time slice 3 with observation being G.<\/p>\r\n<img class=\"aligncenter size-full wp-image-794\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213.png\" alt=\"\" width=\"554\" height=\"209\" \/>\r\n<p style=\"text-align: justify\">Now let us calculate the forward probabilities of each of the states at the final time slice 4 with final observation of the sequence being B.<\/p>\r\n<img class=\"aligncenter size-full wp-image-795\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214.png\" alt=\"\" width=\"568\" height=\"290\" \/>\r\n\r\n<strong>35.4.4 Forward Algorithm Complexity<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the na\u00efve approach to solving problem 1 the time taken is of the order of 2T*NT computations where T is the number of time slices in the sequence and N is the number of states in the HMM. However the forward algorithm takes time of the order of N2T computations.<\/p>\r\n&nbsp;\r\n\r\n<strong>35.4.5 Backward Probabilities<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Analogous to the forward probability, but just in the other direction that is in the backward direction starting from the last state and traveling to the initial state.\u00a0Now we need to determine the backward probability that given an HMM and given the state at time t is i, the partial observation ot+1 \u2026 oT is generated.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-796\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215.png\" alt=\"\" width=\"572\" height=\"361\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 35.6 Backward Probability<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here we start from the final state and calculate the probability of each preceding state in the backward direction, and hence this probability is called the backward probability. The backward probability at a time slice t of a state j is the sum of each the N forward probabilities i at time slice t+1 multiplied by the transition probability of each state j a t time slice t+1 to the state i under consideration t time slice t (Figure 35.6). This sum is then multiplied by the emission probability of observing ot+1at state j.<\/p>\r\n<img class=\"aligncenter size-full wp-image-797\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216.png\" alt=\"\" width=\"392\" height=\"89\" \/>\r\n\r\n<strong>35.4.6 Backward recursion:<\/strong>\r\n\r\n&nbsp;\r\n\r\nAs we have already discussed backward probability\r\n\r\n<img class=\"aligncenter size-full wp-image-798\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-217.png\" alt=\"\" width=\"332\" height=\"69\" \/>\r\n\r\nis calculated using backward recursion. The initialization is as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-799\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-218.png\" alt=\"\" width=\"345\" height=\"43\" \/>\r\n\r\nHere the initial backward probability of state i at time slice T is 1. The backward recursion is determined as follows:\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-800\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219.png\" alt=\"\" width=\"578\" height=\"79\" \/>\r\n<p style=\"text-align: justify\">Here the backward probability at time slice t is determined b y considering the backward probabilities of all states at time slot t+1, the transition probabilities from state i (the state whose backward probability is to be determined) to state j and the emission probability of the observation at time slice t+1 at state j.<\/p>\r\n&nbsp;\r\n\r\nFinally we have the termination happens when the backward probability of state i at time slice 1 multiplied by the initial probability of state i as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-801\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-220.png\" alt=\"\" width=\"327\" height=\"77\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>35.5\u00a0 Problem 2 \u2013 Decoding \u2013 Viterbi Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Given the observation sequence <em>O=o<\/em><em>1<\/em><em>,\u2026,o<\/em><em>T<\/em>and an HMM model now we want to find the state sequence that best explains the observations . In other words we need to compute the most probable sequence of states, given a sequence of observations. For this decoding we describe Viterbi\u2019s dynamic programming algorithm.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">As we discussed for the solution to Problem 1 (Evaluation) was the efficient determination of the sum of all paths through an HMM. For solving the decoding problem we want to find the path with the highest probability. Here given a set of symbols O determine the most likely sequence of hidden states Q that led to the observations.\u00a0 In\u00a0 other\u00a0 words,\u00a0 we\u00a0 want\u00a0 to\u00a0 find\u00a0 the\u00a0 state\u00a0 sequence Q=q1\u2026qT, which maximizesP(Q|o1,o2,...,oT) that is as follows:<\/p>\r\n<img class=\"aligncenter size-full wp-image-802\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221.png\" alt=\"\" width=\"387\" height=\"77\" \/>\r\n<p style=\"text-align: justify\">Here we see we need to find the states that maximizes the probability of the sequence given the sequence of observations and the HMM model.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">When we want to find the mostprobable state sequence we use the idea that if we know the identity of <em>Q<\/em><em>i<\/em> , then the most probable sequence on <em>i+1,\u2026,n<\/em> does not depend on observations before time <em>i<\/em>.<\/p>\r\n&nbsp;\r\n\r\n<strong>35.5.1 Viterbi Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The purpose of the Viterbi algorithm is to carry out an analysis of the internal processing result for finding the best most likely state sequence. It uses the dynamic programming concept to align state and observation transitions. The Viterbi algorithm is similar to computing the forward probabilities, but instead of\u00a0<span style=\"font-size: 1em;text-align: initial\">summing over transitions from incoming states, we compute the maximum at each and every time slice. While in forward algorithm we have<\/span><\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-804\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-223.png\" alt=\"\" width=\"313\" height=\"51\" \/>\r\n<div>\r\n\r\nin the case of Viterbi recursion we have\r\n\r\n<img class=\"aligncenter size-full wp-image-803\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222.png\" alt=\"\" width=\"417\" height=\"79\" \/>\r\n<p style=\"text-align: justify\">As we can see instead of considering the summation of forward probabilities of all the preceding states, in the case of Viterbi recursion we consider only the transition from the state where the product of the state probability and the transition is the maximum. Figure 35.7 shows the HMM.<\/p>\r\n<img class=\"aligncenter size-full wp-image-805\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224.png\" alt=\"\" width=\"538\" height=\"120\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Figure 35.7 HMM Model<\/strong><\/p>\r\n&nbsp;\r\n\r\nThe forward probability already discussed is as given below:\r\n\r\n<img class=\"aligncenter size-full wp-image-806\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-225.png\" alt=\"\" width=\"309\" height=\"96\" \/>\r\n\r\nSimilarly backward probability has already discussed and is given below:\r\n\r\n<img class=\"aligncenter size-full wp-image-807\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-226.png\" alt=\"\" width=\"325\" height=\"101\" \/>\r\n\r\nThe forward probability and backward probability can be combined:\r\n\r\n<img class=\"aligncenter size-full wp-image-808\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-227.png\" alt=\"\" width=\"327\" height=\"88\" \/>\r\n\r\nThe initialization of the Viterbi algorithm is at time slice 1 and state i.\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-809\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228.png\" alt=\"\" width=\"417\" height=\"59\" \/>\r\n\r\nThen at each recursive step we find the maximum probability from one of the N states as shown by the induction.\r\n\r\n<img class=\"aligncenter size-full wp-image-810\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229.png\" alt=\"\" width=\"577\" height=\"145\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The state sequence which maximizes the probability of seeing the observations to time t-1, landing in state j, and seeing the observation at time t<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Then we find the argument maximum to find the termination condition:<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-811\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230.png\" alt=\"\" width=\"600\" height=\"234\" \/>\r\n\r\n&nbsp;\r\n\r\nIn this way the best sequence of hidden states that gave rise to the given set of observations as given below:\r\n\r\n<img class=\"aligncenter size-full wp-image-812\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-231.png\" alt=\"\" width=\"320\" height=\"152\" \/>\r\n\r\nIn this way the final sequence of states is computed by working backwards given as below:\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-813\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232.png\" alt=\"\" width=\"480\" height=\"61\" \/><img class=\"aligncenter size-full wp-image-814\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233.png\" alt=\"\" width=\"469\" height=\"269\" \/>\r\n\r\n<strong>35.5.2 Example for Viterbi Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This is the same example that we discussed in Section 35.4.3. However here we need to find the maximum values at each step rather than the sum of forward probabilities coming from each step of the induction. Now let us calculate the probabilities of each of the states at the time slice 2 with observation being R.<\/p>\r\n<img class=\"aligncenter size-full wp-image-815\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234.png\" alt=\"\" width=\"443\" height=\"269\" \/>\r\n\r\nThe sequence of hidden states are 1,1,2,3 to get observation sequence R,R,G,B\r\n\r\n<\/div>\r\n<img class=\"aligncenter size-full wp-image-816\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235.png\" alt=\"\" width=\"585\" height=\"346\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 35.8 Example for Viterbi Algorithm<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">We will discuss the solution to the third problem associated with HMM that is the learning of the HMM model with the EM algorithm in the next module.<\/p>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Explained the three issues of HMM<\/li>\r\n \t<li>Discussed the Baum Welsh Forward and Backward algorithms for Evaluation using the model<\/li>\r\n \t<li>Outlined Viterbi algorithm for Decoding<\/li>\r\n<\/ul>\r\n&nbsp;\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on HMM\u2013 Baum Welsh and Viterbi Algorithms<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/h22nGEF8PUo\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n\r\n<strong>Web Links<\/strong>\r\n<ul>\r\n \t<li>studentnet.cs.manchester.ac.uk\/ugt\/COMP24111\/...\/Nai ve-Bayes.ppt<\/li>\r\n \t<li>web.cecs.pdx.edu\/...\/2015BayesTrees...\/2014_0095_Example%20of%20<\/li>\r\n \t<li>https:\/\/cse.sc.edu\/~rose\/587\/PPT\/NaiveBayes.ppt<\/li>\r\n \t<li>www.cs.unc.edu\/~lazebnik\/spring09\/lec20_generative.ppt<\/li>\r\n \t<li>cis-linux1.temple.edu\/~latecki\/Courses\/RobotFall08\/...\/bayesNaive.ppt<\/li>\r\n \t<li>www.cs.bu.edu\/fac\/gkollios\/ada01\/LectNotes\/Bayesian.ppt<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Supporting &amp; Reference Materials<\/strong>\r\n<ul>\r\n \t<li>Tom <a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Mitchell&amp;search-alias=stripbooks\">Mitchell, <\/a>\u201cMachine Learning\u201d,McGraw-Hill Education, 1997<\/li>\r\n \t<li><a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Alpaydin+Ethem&amp;search-alias=stripbooks\">AlpaydinEthem, <\/a>\u201cIntroduction to Machine Learning\u201d, The MIT Press; third edition, 2014<\/li>\r\n \t<li>Christopher M. <a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Bishop&amp;search-alias=stripbooks\">Bishop, <\/a>\u201cPattern Recognition and Machine Learning\u201d,Springer, 2013 <a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Peter+Harrington&amp;search-alias=stripbooks\">Peter Harrington, <\/a>\u201cMachine Learning In Action\u201d, Manning Publications, 2012<\/li>\r\n \t<li><a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Peter+Flach&amp;search-alias=stripbooks\">Peter Flach, <\/a>\u201cMachine Learning: The Art and Science of Algorithms that Make Sense of Data\u201d,Cambridge University Press, 2012<\/li>\r\n \t<li><a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Stephen+Marsland&amp;search-alias=stripbooks\">Stephen Marsland, <\/a>\u201cMachine Learning: An Algorithmic Perspective\u201d, Chapman and Hall\/CRC; 2 edition, 2014<\/li>\r\n \t<li>S. Abu-Mostafa, M. Magdon-Ismail, and H.-T. Lin, \u201cLearning from Data\u201d, AMLBook, 2012.<\/li>\r\n<\/ul>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/h22nGEF8PUo\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of this module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the three issues of HMM<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To explain the Baum Welsh algorithm for evaluation using the model<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To discuss Viterbi algorithm for decoding<\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.1 Recap: Hidden Markov Model<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As we have already discussed Hidden Markov Model (HMM) is an extension of a Markov model in which the input symbols are not the same as the states.This means we don\u2019t know which state we are in (hence called Hidden State). For example in HMM POS-tagging, the input symbols are the words, states are the part of speech tags. In addition we make two important assumptions namely Markov assumption and Output-Input assumption. <strong>Markov assumption<\/strong> states that the state transition depends only on the origin and destination and the <strong>Output-independent assumption <\/strong>which states that all observation frames are dependent on the state that generated them, not on neighbouring observation frames.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.1.1 Parameters of an HMM:<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">In Hidden Markov Models, S = {s1,\u2026,sn} is a set of states where \u2018n\u2019 is the number of possible states<\/li>\n<li style=\"text-align: justify\"><strong>Transition probabilities is a two dimensional Matrix <\/strong><em>A=<\/em> <em>a<\/em><em>1,1<\/em><em>,a<\/em><em>1,2<\/em><em>,\u2026,a<\/em><em>n,n<\/em><em>where each a<\/em><em>i,j<\/em><em>represents the probability of transitioning from state s<\/em><em>i<\/em><em>to s<\/em><em>j<\/em><em>.<\/em><\/li>\n<li style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">Emission probabilities<\/strong><span style=\"text-align: initial;font-size: 1em\">or the observation symbol distribution probabilityis aset B of functions of the form bi (ot) which is the probability of observation otbeing emitted or observed by state si<\/span><\/li>\n<li style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">Initial state distribution<\/strong><span style=\"text-align: initial;font-size: 1em\">pis the probability that si is a start state<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Therefore we have two model parameters n, the number of states of the HMM and m, the number of distinct observation symbols per state. In addition we have three probability measures A-the transition probability, B-the emission probability and p- the initial probability.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The HMM Formalism is represented as given in Figure 35.1 where {<em>S, K<\/em>, P, <em>A,<\/em> <em>B<\/em>} is the model. Here S is the state and K is the observation. <em>p<\/em> = {pi} are theinitial state probabilities, <em>A<\/em> = {a<em>ij<\/em>} are the state transition probabilities and <em>B<\/em> = {b<em>ik<\/em>} are the observation or emission state probabilities.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-776\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196.png\" alt=\"\" width=\"587\" height=\"115\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196.png 587w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196-300x59.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196-65x13.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196-225x44.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-196-350x69.png 350w\" sizes=\"auto, (max-width: 587px) 100vw, 587px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 35.1 The HMM Formalism<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.1.2 Building the observation sequence<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Before we proceed further, let us understand how an observation sequence is generated. Given the above five elements, we can build an observation sequence:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-778\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-197.png\" alt=\"\" width=\"185\" height=\"49\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-197.png 185w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-197-65x17.png 65w\" sizes=\"auto, (max-width: 185px) 100vw, 185px\" \/><\/p>\n<p>where T is the number of observations . This observation sequence is built as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>1.We first set\u00a0 t=1.<\/p>\n<p>&nbsp;<\/p>\n<p>2. Then we choose an initial state<\/p>\n<p>q<sub>i=<\/sub>S<sub>i<\/sub><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: left\">according to the initial distribution.<\/p>\n<p>&nbsp;<\/p>\n<p>3. Then we choose<\/p>\n<p>O<sub>t<\/sub>=V<sub>k<\/sub><\/p>\n<p>according to the symbol probability distribution.<\/p>\n<p>&nbsp;<\/p>\n<p>4. Then we transit to a new state<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">q<\/span><sub style=\"text-align: initial\">t+1=<\/sub>S<sub>j<\/sub><\/p>\n<\/div>\n<div>\n<p>according to the state transition probability distribution.<\/p>\n<p>&nbsp;<\/p>\n<p>5.\u00a0\u00a0 Then we set t t=t+1, and iterate by returning to step 3 while t&lt;=T<\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.2\u00a0 The Three Problems of HMM<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The following are the three problems associated with HMM:<\/p>\n<p>&nbsp;<\/p>\n<p>Problem 1: <strong>Evaluation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here given the observation sequence <em>O=o<\/em><em>1<\/em><em>,\u2026,o<\/em><em>T<\/em>and an HMM model how do we compute the probability of O given the model?<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Q1<\/strong>:<strong> How do we compute the probability of a given sequence of observations?<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>A1: <\/strong>Forward \u2013 Backward dynamic programming algorithm \u2013<strong> the Baum Welch algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Problem 2: <strong>Decoding<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here given the observation sequence <em>O=o<\/em><em>1<\/em><em>,\u2026,o<\/em><em>T<\/em>and an HMM model, how do we find the state sequence that best explains the observations?<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>Q2:How to compute the most probable sequence of sequence of observations? s<\/strong><strong>tates, given a<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">A2: Viterbi\u2019s <\/strong><span style=\"text-align: initial;font-size: 1em\">dynamic programming Algorithm<\/span><\/p>\n<p>&nbsp;<\/p>\n<p><span style=\"font-size: 1em;text-align: initial\">Given an observation sequence, compute the most likely hidden state sequence<\/span><\/p>\n<p>&nbsp;<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Problem 3: <\/span><strong style=\"text-align: initial;font-size: 1em\">Learning<\/strong><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>Here given an observation sequence and set of possible models, which model most closely fits\u00a0 the\u00a0 data? How do we adjust the model parameters<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-780\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-199.png\" alt=\"\" width=\"211\" height=\"44\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-199.png 211w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-199-65x14.png 65w\" sizes=\"auto, (max-width: 211px) 100vw, 211px\" \/><\/p>\n<p>to maximize<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-781\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-200.png\" alt=\"\" width=\"146\" height=\"48\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-200.png 146w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-200-65x21.png 65w\" sizes=\"auto, (max-width: 146px) 100vw, 146px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Q3: Given an observation sequence and set of possible models, which model most closely fits the data?<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>A3: The Expectation Maximization (EM) heuristic.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">35.3\u00a0 Markov Assumption with an Example<\/strong><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us discuss the Markov assumptions with an example. Let us assume that we have a sentence with n words. The Markov assumption states that probability of the occurrence of word wi at time t depends only on occurrence of word wi-1 at time t-1.<\/p>\n<p>&nbsp;<\/p>\n<p>The normal chain rule would be as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-782\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201.png\" alt=\"\" width=\"559\" height=\"102\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201.png 559w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201-300x55.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201-65x12.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201-225x41.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-201-350x64.png 350w\" sizes=\"auto, (max-width: 559px) 100vw, 559px\" \/><\/p>\n<p>However the Markov Assumption approximates the probability of the sequence of words as:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-783\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202.png\" alt=\"\" width=\"491\" height=\"99\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202.png 491w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202-300x60.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202-65x13.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202-225x45.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-202-350x71.png 350w\" sizes=\"auto, (max-width: 491px) 100vw, 491px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>A common way of representing the Hidden Markov Model is the Trellis Diagram shown in Figure 35.2<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-784\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203.png\" alt=\"\" width=\"593\" height=\"274\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203.png 593w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203-300x139.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203-65x30.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203-225x104.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-203-350x162.png 350w\" sizes=\"auto, (max-width: 593px) 100vw, 593px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 35.2 Trellis Diagram<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In this diagram we have the starting state s0 which influences the states s1,1,s1,2,s1,3,s1,4 with observation at time t1 being o1 and so on until finally we end up with the states sT,1,sT,2,sT,3,sT,4at time t T.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.4 Problem 1 &#8211; Evaluation &#8211; Forward and Backward Algorithms<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Here given the observation sequence <\/span><em style=\"text-align: initial;font-size: 1em\">O=o<\/em><em style=\"text-align: initial;font-size: 1em\">1<\/em><em style=\"text-align: initial;font-size: 1em\">,\u2026,o<\/em><em style=\"text-align: initial;font-size: 1em\">T<\/em><span style=\"text-align: initial;font-size: 1em\">and an HMM model we need to compute the probability of O given the model that is we are given a sequence of observations and we need to compute the probability of that specific sequence of observations. This likelihood of a sequence can be determined by either the forward procedure or the backward procedure. We will discuss the Forward algorithm which is essentially a dynamic programming algorithm. Backward algorithm can be similarly explained. The Forward algorithm can be used with two options, one the \u201cAny Path\u201d methodwhere the likelihood is measured using any sequence of states of length T, and the second option the \u201cBest Path\u201d method where we choose an HMM by the probability generated using the best possible sequence of states . Solving the evaluation problem involves the determination of the probability that a particular sequence of symbols O was generated by that model (Figure 35.3). Here the model starts at state q1 with initial probability pq1, followed by the transition probabilities aq1,q2, \u2026\u2026\u2026\u2026\u2026.aqT-1,qT.<\/span><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-785\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204.png\" alt=\"\" width=\"588\" height=\"210\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204.png 588w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204-300x107.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204-225x80.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-204-350x125.png 350w\" sizes=\"auto, (max-width: 588px) 100vw, 588px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.4.1 Forward Probabilities:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We need to determine the forward probability that, given an HMM l, at time t the state is i and the partial observation o1 \u2026 ot has been generated that is<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-786\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205.png\" alt=\"\" width=\"482\" height=\"37\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205.png 482w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205-300x23.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205-65x5.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205-225x17.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-205-350x27.png 350w\" sizes=\"auto, (max-width: 482px) 100vw, 482px\" \/><\/p>\n<p style=\"text-align: justify\">Here we start from the initial state and calculate the probability of each subsequent state in the forward direction, and hence this probability is called the forward probability.<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-787\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206.png\" alt=\"\" width=\"558\" height=\"341\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206.png 558w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206-300x183.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206-225x138.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-206-350x214.png 350w\" sizes=\"auto, (max-width: 558px) 100vw, 558px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 35.4 Forward Probability<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The forward probability at a time slice t of a state j is the sum of each the N forward probabilities i at time slice t-1 multiplied by the transition probability of each state i at time slice t-1 to the state j under consideration t time slice t (Figure 35.4). This sum is then multiplied by the emission probability of observing ot at state j.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-788\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-207.png\" alt=\"\" width=\"334\" height=\"59\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-207.png 334w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-207-300x53.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-207-65x11.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-207-225x40.png 225w\" sizes=\"auto, (max-width: 334px) 100vw, 334px\" \/><\/p>\n<p><strong>35.4.2 Forward recursion:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>As we have already discussed forward probability<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-789\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-208.png\" alt=\"\" width=\"330\" height=\"48\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-208.png 330w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-208-300x44.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-208-65x9.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-208-225x33.png 225w\" sizes=\"auto, (max-width: 330px) 100vw, 330px\" \/><\/p>\n<p>is calculated using forward recursion. The initialization is as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-790\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-209.png\" alt=\"\" width=\"195\" height=\"55\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-209.png 195w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-209-65x18.png 65w\" sizes=\"auto, (max-width: 195px) 100vw, 195px\" \/><\/p>\n<p>Here the initial forward probability of state i at time slice 1 is the product of the initial probability of state i and the probability of emitting the observation o1 at state i at time slice 1. The forward recursion is determined as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-791\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210.png\" alt=\"\" width=\"367\" height=\"99\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210.png 367w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210-300x81.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210-65x18.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210-225x61.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-210-350x94.png 350w\" sizes=\"auto, (max-width: 367px) 100vw, 367px\" \/><\/p>\n<p>Here the forward probability at time slice t+1 is determined by considering the forward probabilities of all states at time slot t, the transition probabilities from\u00a0<span style=\"text-align: initial;font-size: 1em\">state i to state j (the state whose forward probability is to be determined) and the emission probability of the observation at time slice t+1 at state j. Finally we have the termination as follows:<\/span><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-792\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211.png\" alt=\"\" width=\"573\" height=\"94\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211.png 573w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211-300x49.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211-65x11.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211-225x37.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-211-350x57.png 350w\" sizes=\"auto, (max-width: 573px) 100vw, 573px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.4.3 Example for the Calculation of Forward Probability<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We show an example for the calculation of forward probabilities (Figure 35.5). Here there are three states which can emit the observations R,G and B. We have the observation sequence R,R,G,B. Now the initial probability shows that the start state is 1. The probability of state 1 emitting R is 0.6, G is 0.2, B is 0.2. The probabilities of state 2 and state 3 being the initial state is 0. The probabilities of state 2 emitting R is 0.2, G is 0.5, B is 0.3.and the probabilities of state 3 emitting R is 0.0, G is 0.3, B is 0.7. The transition probabilities from each state to all the other states are also shown in the Figure. At time slot 1 we have the probability of only state 1 and it emitting R is 0.6. Now let us calculate the forward probabilities of each of the states at the time slice 2 with observation being R.<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-793\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212.png\" alt=\"\" width=\"608\" height=\"468\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212.png 608w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212-300x231.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212-65x50.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212-225x173.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-212-350x269.png 350w\" sizes=\"auto, (max-width: 608px) 100vw, 608px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 35.5 Example for Calculation of Forward Probabilities<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us calculate the forward probabilities of each of the states at the time slice 3 with observation being G.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-794\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213.png\" alt=\"\" width=\"554\" height=\"209\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213.png 554w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213-300x113.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213-225x85.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-213-350x132.png 350w\" sizes=\"auto, (max-width: 554px) 100vw, 554px\" \/><\/p>\n<p style=\"text-align: justify\">Now let us calculate the forward probabilities of each of the states at the final time slice 4 with final observation of the sequence being B.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-795\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214.png\" alt=\"\" width=\"568\" height=\"290\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214.png 568w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214-300x153.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214-65x33.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214-225x115.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-214-350x179.png 350w\" sizes=\"auto, (max-width: 568px) 100vw, 568px\" \/><\/p>\n<p><strong>35.4.4 Forward Algorithm Complexity<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the na\u00efve approach to solving problem 1 the time taken is of the order of 2T*NT computations where T is the number of time slices in the sequence and N is the number of states in the HMM. However the forward algorithm takes time of the order of N2T computations.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.4.5 Backward Probabilities<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Analogous to the forward probability, but just in the other direction that is in the backward direction starting from the last state and traveling to the initial state.\u00a0Now we need to determine the backward probability that given an HMM and given the state at time t is i, the partial observation ot+1 \u2026 oT is generated.<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-796\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215.png\" alt=\"\" width=\"572\" height=\"361\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215.png 572w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215-300x189.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215-225x142.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-215-350x221.png 350w\" sizes=\"auto, (max-width: 572px) 100vw, 572px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 35.6 Backward Probability<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here we start from the final state and calculate the probability of each preceding state in the backward direction, and hence this probability is called the backward probability. The backward probability at a time slice t of a state j is the sum of each the N forward probabilities i at time slice t+1 multiplied by the transition probability of each state j a t time slice t+1 to the state i under consideration t time slice t (Figure 35.6). This sum is then multiplied by the emission probability of observing ot+1at state j.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-797\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216.png\" alt=\"\" width=\"392\" height=\"89\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216.png 392w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216-300x68.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216-225x51.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-216-350x79.png 350w\" sizes=\"auto, (max-width: 392px) 100vw, 392px\" \/><\/p>\n<p><strong>35.4.6 Backward recursion:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>As we have already discussed backward probability<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-798\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-217.png\" alt=\"\" width=\"332\" height=\"69\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-217.png 332w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-217-300x62.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-217-65x14.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-217-225x47.png 225w\" sizes=\"auto, (max-width: 332px) 100vw, 332px\" \/><\/p>\n<p>is calculated using backward recursion. The initialization is as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-799\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-218.png\" alt=\"\" width=\"345\" height=\"43\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-218.png 345w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-218-300x37.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-218-65x8.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-218-225x28.png 225w\" sizes=\"auto, (max-width: 345px) 100vw, 345px\" \/><\/p>\n<p>Here the initial backward probability of state i at time slice T is 1. The backward recursion is determined as follows:<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-800\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219.png\" alt=\"\" width=\"578\" height=\"79\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219.png 578w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219-300x41.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219-65x9.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219-225x31.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-219-350x48.png 350w\" sizes=\"auto, (max-width: 578px) 100vw, 578px\" \/><\/p>\n<p style=\"text-align: justify\">Here the backward probability at time slice t is determined b y considering the backward probabilities of all states at time slot t+1, the transition probabilities from state i (the state whose backward probability is to be determined) to state j and the emission probability of the observation at time slice t+1 at state j.<\/p>\n<p>&nbsp;<\/p>\n<p>Finally we have the termination happens when the backward probability of state i at time slice 1 multiplied by the initial probability of state i as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-801\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-220.png\" alt=\"\" width=\"327\" height=\"77\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-220.png 327w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-220-300x71.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-220-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-220-225x53.png 225w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.5\u00a0 Problem 2 \u2013 Decoding \u2013 Viterbi Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Given the observation sequence <em>O=o<\/em><em>1<\/em><em>,\u2026,o<\/em><em>T<\/em>and an HMM model now we want to find the state sequence that best explains the observations . In other words we need to compute the most probable sequence of states, given a sequence of observations. For this decoding we describe Viterbi\u2019s dynamic programming algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As we discussed for the solution to Problem 1 (Evaluation) was the efficient determination of the sum of all paths through an HMM. For solving the decoding problem we want to find the path with the highest probability. Here given a set of symbols O determine the most likely sequence of hidden states Q that led to the observations.\u00a0 In\u00a0 other\u00a0 words,\u00a0 we\u00a0 want\u00a0 to\u00a0 find\u00a0 the\u00a0 state\u00a0 sequence Q=q1\u2026qT, which maximizesP(Q|o1,o2,&#8230;,oT) that is as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-802\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221.png\" alt=\"\" width=\"387\" height=\"77\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221.png 387w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221-300x60.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221-65x13.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221-225x45.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-221-350x70.png 350w\" sizes=\"auto, (max-width: 387px) 100vw, 387px\" \/><\/p>\n<p style=\"text-align: justify\">Here we see we need to find the states that maximizes the probability of the sequence given the sequence of observations and the HMM model.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">When we want to find the mostprobable state sequence we use the idea that if we know the identity of <em>Q<\/em><em>i<\/em> , then the most probable sequence on <em>i+1,\u2026,n<\/em> does not depend on observations before time <em>i<\/em>.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.5.1 Viterbi Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The purpose of the Viterbi algorithm is to carry out an analysis of the internal processing result for finding the best most likely state sequence. It uses the dynamic programming concept to align state and observation transitions. The Viterbi algorithm is similar to computing the forward probabilities, but instead of\u00a0<span style=\"font-size: 1em;text-align: initial\">summing over transitions from incoming states, we compute the maximum at each and every time slice. While in forward algorithm we have<\/span><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-804\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-223.png\" alt=\"\" width=\"313\" height=\"51\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-223.png 313w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-223-300x49.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-223-65x11.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-223-225x37.png 225w\" sizes=\"auto, (max-width: 313px) 100vw, 313px\" \/><\/p>\n<div>\n<p>in the case of Viterbi recursion we have<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-803\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222.png\" alt=\"\" width=\"417\" height=\"79\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222.png 417w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222-300x57.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222-65x12.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222-225x43.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-222-350x66.png 350w\" sizes=\"auto, (max-width: 417px) 100vw, 417px\" \/><\/p>\n<p style=\"text-align: justify\">As we can see instead of considering the summation of forward probabilities of all the preceding states, in the case of Viterbi recursion we consider only the transition from the state where the product of the state probability and the transition is the maximum. Figure 35.7 shows the HMM.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-805\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224.png\" alt=\"\" width=\"538\" height=\"120\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224.png 538w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224-300x67.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224-65x14.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224-225x50.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-224-350x78.png 350w\" sizes=\"auto, (max-width: 538px) 100vw, 538px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Figure 35.7 HMM Model<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The forward probability already discussed is as given below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-806\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-225.png\" alt=\"\" width=\"309\" height=\"96\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-225.png 309w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-225-300x93.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-225-65x20.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-225-225x70.png 225w\" sizes=\"auto, (max-width: 309px) 100vw, 309px\" \/><\/p>\n<p>Similarly backward probability has already discussed and is given below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-807\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-226.png\" alt=\"\" width=\"325\" height=\"101\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-226.png 325w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-226-300x93.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-226-65x20.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-226-225x70.png 225w\" sizes=\"auto, (max-width: 325px) 100vw, 325px\" \/><\/p>\n<p>The forward probability and backward probability can be combined:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-808\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-227.png\" alt=\"\" width=\"327\" height=\"88\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-227.png 327w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-227-300x81.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-227-65x17.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-227-225x61.png 225w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/p>\n<p>The initialization of the Viterbi algorithm is at time slice 1 and state i.<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-809\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228.png\" alt=\"\" width=\"417\" height=\"59\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228.png 417w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228-300x42.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228-65x9.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228-225x32.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-228-350x50.png 350w\" sizes=\"auto, (max-width: 417px) 100vw, 417px\" \/><\/p>\n<p>Then at each recursive step we find the maximum probability from one of the N states as shown by the induction.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-810\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229.png\" alt=\"\" width=\"577\" height=\"145\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229.png 577w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229-300x75.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229-65x16.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229-225x57.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-229-350x88.png 350w\" sizes=\"auto, (max-width: 577px) 100vw, 577px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The state sequence which maximizes the probability of seeing the observations to time t-1, landing in state j, and seeing the observation at time t<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Then we find the argument maximum to find the termination condition:<\/span><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-811\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230.png\" alt=\"\" width=\"600\" height=\"234\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230.png 600w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230-300x117.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230-225x88.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-230-350x137.png 350w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>In this way the best sequence of hidden states that gave rise to the given set of observations as given below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-812\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-231.png\" alt=\"\" width=\"320\" height=\"152\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-231.png 320w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-231-300x143.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-231-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-231-225x107.png 225w\" sizes=\"auto, (max-width: 320px) 100vw, 320px\" \/><\/p>\n<p>In this way the final sequence of states is computed by working backwards given as below:<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-813\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232.png\" alt=\"\" width=\"480\" height=\"61\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232.png 480w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232-300x38.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232-65x8.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232-225x29.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-232-350x44.png 350w\" sizes=\"auto, (max-width: 480px) 100vw, 480px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-814\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233.png\" alt=\"\" width=\"469\" height=\"269\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233.png 469w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233-300x172.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233-65x37.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233-225x129.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-233-350x201.png 350w\" sizes=\"auto, (max-width: 469px) 100vw, 469px\" \/><\/p>\n<p><strong>35.5.2 Example for Viterbi Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This is the same example that we discussed in Section 35.4.3. However here we need to find the maximum values at each step rather than the sum of forward probabilities coming from each step of the induction. Now let us calculate the probabilities of each of the states at the time slice 2 with observation being R.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-815\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234.png\" alt=\"\" width=\"443\" height=\"269\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234.png 443w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234-300x182.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234-65x39.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234-225x137.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-234-350x213.png 350w\" sizes=\"auto, (max-width: 443px) 100vw, 443px\" \/><\/p>\n<p>The sequence of hidden states are 1,1,2,3 to get observation sequence R,R,G,B<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-816\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235.png\" alt=\"\" width=\"585\" height=\"346\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235.png 585w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235-300x177.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235-65x38.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235-225x133.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2019\/01\/2-235-350x207.png 350w\" sizes=\"auto, (max-width: 585px) 100vw, 585px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 35.8 Example for Viterbi Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We will discuss the solution to the third problem associated with HMM that is the learning of the HMM model with the EM algorithm in the next module.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Explained the three issues of HMM<\/li>\n<li>Discussed the Baum Welsh Forward and Backward algorithms for Evaluation using the model<\/li>\n<li>Outlined Viterbi algorithm for Decoding<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on HMM\u2013 Baum Welsh and Viterbi Algorithms<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/h22nGEF8PUo\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><strong>Web Links<\/strong><\/p>\n<ul>\n<li>studentnet.cs.manchester.ac.uk\/ugt\/COMP24111\/&#8230;\/Nai ve-Bayes.ppt<\/li>\n<li>web.cecs.pdx.edu\/&#8230;\/2015BayesTrees&#8230;\/2014_0095_Example%20of%20<\/li>\n<li>https:\/\/cse.sc.edu\/~rose\/587\/PPT\/NaiveBayes.ppt<\/li>\n<li>www.cs.unc.edu\/~lazebnik\/spring09\/lec20_generative.ppt<\/li>\n<li>cis-linux1.temple.edu\/~latecki\/Courses\/RobotFall08\/&#8230;\/bayesNaive.ppt<\/li>\n<li>www.cs.bu.edu\/fac\/gkollios\/ada01\/LectNotes\/Bayesian.ppt<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Supporting &amp; Reference Materials<\/strong><\/p>\n<ul>\n<li>Tom <a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Mitchell&amp;search-alias=stripbooks\">Mitchell, <\/a>\u201cMachine Learning\u201d,McGraw-Hill Education, 1997<\/li>\n<li><a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Alpaydin+Ethem&amp;search-alias=stripbooks\">AlpaydinEthem, <\/a>\u201cIntroduction to Machine Learning\u201d, The MIT Press; third edition, 2014<\/li>\n<li>Christopher M. <a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Bishop&amp;search-alias=stripbooks\">Bishop, <\/a>\u201cPattern Recognition and Machine Learning\u201d,Springer, 2013 <a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Peter+Harrington&amp;search-alias=stripbooks\">Peter Harrington, <\/a>\u201cMachine Learning In Action\u201d, Manning Publications, 2012<\/li>\n<li><a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Peter+Flach&amp;search-alias=stripbooks\">Peter Flach, <\/a>\u201cMachine Learning: The Art and Science of Algorithms that Make Sense of Data\u201d,Cambridge University Press, 2012<\/li>\n<li><a href=\"http:\/\/www.amazon.in\/s\/ref=dp_byline_sr_book_1?ie=UTF8&amp;field-author=Stephen+Marsland&amp;search-alias=stripbooks\">Stephen Marsland, <\/a>\u201cMachine Learning: An Algorithmic Perspective\u201d, Chapman and Hall\/CRC; 2 edition, 2014<\/li>\n<li>S. Abu-Mostafa, M. Magdon-Ismail, and H.-T. Lin, \u201cLearning from Data\u201d, AMLBook, 2012.<\/li>\n<\/ul>\n","protected":false},"author":3,"menu_order":34,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-773","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":7,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/773\/revisions"}],"predecessor-version":[{"id":820,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/773\/revisions\/820"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/773\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/media?parent=773"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapter-type?post=773"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/contributor?post=773"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/license?post=773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}