Decoding problem of Hidden Markov Model

Decoding problem of Hidden Markov Model, One of the three fundamental problems to be solved under HMM is Decoding problem, Decoding problem is the way to figure out the best hidden state sequence using HMM

Decoding problem of Hidden Markov Model

Decoding problem: 

Given an HMM λ = (A, B, π) and an observation sequence O = o₁, o₂, …, o_T, how do we choose the corresponding optimal hidden state sequence (most likely sequence) Q = q₁, q₂, …, q_T that can best explain the observations.

Explain decoding problem of HMM with example

Decoding problem is the one which is used to uncover the hidden part of the model. It is used to find the best possible hidden state sequence for a given observation sequence. 

Given an observation sequence and a HMM, the task of the decoder is to find the best hidden state sequence.

This can be achieved as discussed in Evaluation problem. That is, compute P(O|Q) for each possible hidden sequence and choose the one with highest probability score as the best state sequence. But the major problem is the number of possible state sequences for a given observation sequence, ie., N^T, where N is number of hidden states and T is number of observations.

• If number of tags N = 2, and number of words observed T = 2, then 2² = 4 possible likelihood estimates.

• If N = 6 and T = 4, then 6⁴ = 1296 possible likelihood estimates.

• For longer sentences, it will be too high.

What is the solution to handle decoding problem of HMM?

• Dynamic programming using the decoding algorithm (Viterbi algorithm).

*************

Go to NLP Glossary

Go to Natural Language Processing Home page

What are the three fundamental problems associated with  HMM?

Evaluation, Decoding and Learning problems of hidden markov model

Why we need to answer 3 hidden markov model problems

POS tagging and decoding problem in NLP

decoding problem of Hidden Markov Model for POS tagging

POS tagging evaluation using HMM in NLP