{"id":821,"date":"2019-01-09T08:56:17","date_gmt":"2019-01-09T08:56:17","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=821"},"modified":"2019-01-09T09:14:03","modified_gmt":"2019-01-09T09:14:03","slug":"hmm-em-algorithm","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/hmm-em-algorithm\/","title":{"rendered":"HMM \u2013 EM Algorithm"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n\r\n
\r\n\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Model Learning in HMM\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To discuss the Expectation Maximization method for parameter estimation\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand parameter estimation using supervised and unsupervised techniques\r\n\r\n \r\n\r\n36.1 Recap: Hidden Markov Model<\/strong>\r\n\r\n \r\n

As we have already discussed a Hidden Markov Model 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 impittant and the sattes<\/p>\r\n \r\n

Markov assumption <\/strong>states that the state transition depends only on the origin and destination and the Output-independent assumption<\/strong> which s all observation frames are dependent on the state that generated them, not on neighbouring observation frames .<\/p>\r\n \r\n\r\n36.1.1 The Three Problems of HMM<\/strong>\r\n\r\n \r\n\r\nThe following are the three problems associated with HMM:\r\n\r\n \r\n\r\nProblem 1: Evaluation<\/strong>\r\n\r\n \r\n\r\nHere given the observation sequence O=o<\/em>1<\/em>,\u2026,o<\/em>T<\/em>and an HMM model how do we compute the probability of O given the model?\r\n\r\n \r\n\r\nQ1<\/strong>:<\/span> How do we compute the probability of a given sequence of observations?<\/strong>\r\n\r\n \r\n\r\nA1: <\/strong>Forward \u2013 Backward dynamic programming algorithm \u2013<\/span> the Baum Welch algorithm<\/strong>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nProblem 2: Decoding<\/strong>\r\n\r\n \r\n

Here given the observation sequence O=o<\/em>1<\/em>,\u2026,o<\/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

\r\n\r\n \r\n\r\nQ2:How to compute the most probable sequence of sequence of observations?\u00a0<\/strong>states, given a<\/strong>\r\n\r\n \r\n\r\nA2: Viterbi\u2019s <\/strong>dynamic programming Algorithm<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nGiven an observation sequence, compute the most likely hidden state sequence\r\n\r\n \r\n\r\nWe have already the solutions to the above two problems in the previous module.\r\n\r\n \r\n\r\nProblem 3 \u2013 Learning \u2013 this is the problem we will be now discussing\r\n\r\n \r\n\r\n36.2 Problem 3: Learning<\/strong>\r\n\r\n \r\n\r\nGiven an observation sequence and set of possible models, which model most\r\n\r\n \r\n\r\nclosely\u00a0\u00a0 fits\u00a0\u00a0\u00a0 the\u00a0\u00a0 data?How\u00a0\u00a0\u00a0 do\u00a0\u00a0 we\u00a0\u00a0 adjust\u00a0\u00a0 the\u00a0\u00a0 model\u00a0\u00a0\u00a0 parameters\r\n\r\n\"\"\r\n\r\n \r\n\r\nto maximize\r\n\r\n\"\"\r\n\r\nQ3: Given an observation sequence and set of possible models, which model most closely fits the data?<\/strong>\r\n\r\n \r\n\r\nA3: The Expectation Maximization (EM) heuristic.<\/strong>\r\n\r\n \r\n\r\nIt is this learning problem that we will be discussing in this module. This is the hardest problem to solve.\r\n\r\n \r\n

Given an observation sequence O = (O1 O2 \u2026 OL), and a class of models, each of the form M = {A,B,p}, which specific model \u201cbest\u201d explains the observations?A solution to the above question enablesthe efficient computation of P(O|M) (the probability that a specific model M produces the observation O). This can be viewed as a learning problem: We want to use the sequence of\u00a0observations in order to \u201ctrain\u201d an HMM and learn the optimal underlying model parameters essentially we are learning the transition and observation probabilities.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

In other words we need to estimate the emission and transition probabilities given observations and assuming that hidden states are observable during the learning process. We need to estimate emission and transition probabilities given observations only.<\/p>\r\n \r\n

Up to now we\u2019ve assumed that we know the underlying model. However often these parameters are estimated on annotated training data, which gives rise to two drawbacks, basically annotation is difficult and\/or expensive and training data is different from the current data. We want to maximize the parameters with respect to the current data, i.e., we\u2019re looking for a model l\u2019, such that<\/p>\r\n \r\n\r\n\"\"\r\n\r\n36.3 Parameter Estimation<\/strong>\r\n\r\n \r\n

We first make an initial guess for the transition probabilities {aij} and observation or emission probabilities {bkm}. We need to then compute the probability that one hidden state follows another given the guessed values of {aij} and {bkm} and sequence of observations which are computed using forward-backward algorithm. We then compute the probability of observed state given a hidden state and the guessed values of {aij} and {bkm} and the sequence of observations again computed using the forward-backward algorithm. Now using these computed probabilities we make an improved guess for the transition and observation probabilities {aij} and {bkm}. We then repeat this process until convergence. It can be shown that this algorithm does in fact converge to correct values for {aij} and {bkm} assuming that the initial guess was close enough.<\/p>\r\n \r\n\r\nThat is given an observation sequence, find the model that is most likely to produce that sequence. Here we use no analytic method. We just assume a model and given a model and observation sequence, we update the model parameters to better fit the observations.\r\n\r\n36.3 Review of Probabilities<\/strong>\r\n\r\n \r\n\r\nLet us now review the different probabilities that we have discussed in connection with HMM.\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\n36.4 Parameter Estimation<\/strong>\r\n\r\n \r\n\r\nThe probability of moving from one state to another:\r\n\r\n\"\"\r\n\r\nand the probability of being in state i\r\n\r\n\"\"\r\n\r\nWith the above probabilities we can recalculate the initial probability, and the transition and emission probabilities.\r\n\r\n<\/div>\r\n
\r\n\r\n\"\"\r\n\r\n36.5 Expectation Maximization<\/strong>\r\n\r\n \r\n\r\nThe forward-backward algorithm is an instance of the more general EM algorithm where\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 The E Step: where we compute the forward and backward probabilities for a given model\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 The M Step where we re-estimate the model parameters\r\n\r\n \r\n\r\nUse the forward-backward (or Baum-Welch) algorithm, which is a hill-climbing algorithm\r\n\r\n \r\n

Using an initial parameter instantiation, the forward-backward algorithm iteratively re-estimates the parameters and improves the probability that given observations are generated by the new parameters.Three parameters need to be re-estimated:<\/p>\r\n \r\n\r\n\u2013\u00a0 Initial state distribution:\r\n\r\n \r\n\r\n\u2013\u00a0 Transition probabilities: ai, j\r\n\r\n \r\n\r\n\u2013\u00a0 Emission probabilities: bi(ot)\r\n\r\n \r\n\r\nRe-estimating Transition Probabilities<\/strong>\r\n\r\n \r\n

Here we need to determine the probability of being in state s i at time t and going to state sj, given the current model and parameters as follows:<\/p>\r\n\"\"\r\n\r\nNow we can calculate the probability as given in Figure 36.2.\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

Here the probability is based on previous values of initial, transition and emission probabilities.<\/p>\r\n \r\n

In other words the probability<\/strong> x<\/strong>t<\/strong> (i,j)<\/strong> between the states i, j at time slice t i<\/strong>s the ratio of the product of the forward probability of state i at time slice t,<\/p>\r\n

the transition probability between states i and j,<\/p>\r\n \r\n

the emission probability of observation symbol ot+1at time slice t+1, at state j, and the backward probability of state j at time slice t+1 and<\/p>\r\n \r\n\r\nthe sum of the products of the terms explained above considered for all N values of i and j.\r\n\r\n\"\"\r\n\r\nDefining\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\nRe-estimating Initial State Probabilities<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n36.6 Explaining EM algorithm with an Example<\/strong>\r\n\r\n \r\n

First let us consider a document corpus as an example. The problem we are trying to solve is tagging of the words of a sentence. An example of such a tagging problem is the Part of Speech (POS) tagging where each word in the sentence is tagged with a POS.<\/p>\r\n \r\n\r\nExample The man eats the sweet mango.\r\n\r\n \r\n\r\nDet Noun\u00a0 Vrb Det\u00a0\u00a0\u00a0\u00a0 ADJ\u00a0\u00a0\u00a0\u00a0 Noun\r\n\r\n \r\n

In the POS tagging problem we want to find the tag sequence t1\u2026tnwith the highest probabilityof the word sequencew1\u2026wn. Here we need to estimate probabilities. Here we need to determine transition probability, emission probability, carry out some type of smoothing since we need to deal with unknown words. The transition probability P(ti|ti-1)is the probability of tag t i following tagti-1. The emission probability is the probability of a tag emitting a particular word.<\/p>\r\n \r\n\r\nThe general idea is as follows:\r\n\r\n \r\n

Start by devising a noisy channel, any model predicts the corpus observations via some hidden structure (tags, parses, \u2026). Initially a guess is made about the\u00a0parameters of the model. It is best to make an educated guess but a random guess can also work.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nAs in any EM algorithm we repeat the following two steps until convergence:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Expectation step: <\/strong>Use current parameters (and observations) to reconstruct hidden structure\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Maximization step: <\/strong>Use that hidden structure (and observations) to re-estimate parameters\r\n\r\n \r\n

Now let us go back to our HMM problem. We want to find out of from all the possible sequences of n tags t1\u2026tn, the single tag sequence such that P(t1\u2026tn|w1\u2026wn) is highest.<\/p>\r\n\"\"\r\n\r\nHat ^ means \u201cour estimate of the best one\u201d and Argmaxx f(x) means \u201cthe x such that f(x) is maximized\u201d.\r\n\r\n \r\n

This equation is guaranteed to give us the best tag sequence . But how to make it operational? How to compute this value? We use the intuition of Bayesian classification where we use Bayes rule to transform into a set of other probabilities that are easier to compute as follows:<\/p>\r\n\"\"\r\n\r\nNow we would like to define likelihood and prior as follows:\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Therefore we find the best tag sequence (POS sequence) for a given sequence of words as the sequence that gives the maximum probability of the product of likelihood (emission probability) and prior (transition probability). Here we assumed we had an already tagged corpus from which we could estimate the required probabilities.<\/p>\r\n \r\n\r\n36.7 Estimation from Untagged Corpus: EM \u2013 Expectation-Maximization<\/strong>\r\n\r\n \r\n

When we use a plain-text corpus and a lexicon to obtain transition and emission probabilities by applying the EM algorithm. The steps are:<\/p>\r\n \r\n\r\n1.Start with some initial model\r\n\r\n \r\n\r\n2. Compute the probability of (virtually) each state sequence given the current model\r\n\r\n \r\n

3. Use this probabilistic tagging to produce probabilistic counts for all parameters, and use these probabilistic counts to estimate a revised model, which increases the likelihood of the observed output W in each iteration<\/p>\r\n \r\n\r\n4.\u00a0\u00a0\u00a0 Repeat until convergence\r\n\r\n \r\n

No <\/em><\/strong>labeled training required. Initialize by lexicon constraints regarding possible POS for each word (cf. \u201cnoisy counting\u201d for PP\u2019s) . In other words we cannot calculate transition probabilities but do have values of emission probabilities. Therefore we start with some random values for the transition probabilities and continue until no improvement occurs.<\/em><\/p>\r\n \r\n\r\nThe EM algorithm is as follows:\r\n