Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Decoding problem of Hidden Markov Model

Decoding problem:

Given an HMM λ = (A, B, π) and an observation sequence O = o1, o2, …, oT, how do we choose the corresponding optimal hidden state sequence (most likely sequence) Q = q1, q2, …, qT 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., NT, 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 22 = 4 possible likelihood estimates.
• If N = 6 and T = 4, then 64 = 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).

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

decoding problem of Hidden Markov Model for POS tagging

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...