### 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 **Decoding problem**:

*λ = (A, B,*

*π***and an observation sequence**

*)***, how do we choose the corresponding optimal hidden state sequence (most likely sequence)**

*O = o*_{1}, o_{2}, …, o_{T}**that can best explain the observations.**

*Q = q*_{1}, q_{2}, …, q_{T}###
**Explain decoding problem of HMM with example**

**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
^{2}= 4 possible likelihood estimates.

- If N = 6 and T = 4,
then 6
^{4}= 1296 possible likelihood estimates.

- For longer sentences, it will be too high.

###
**What is the solution to handle decoding problem of HMM? **

**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