Natural language processing question bank 06

Assume that we have the Hidden Markov Model (HMM). If each of the states can take on k different values and a total of m different observations are possible (across all states), how many parameters are required to fully define this HMM? Justify your answer.

Question:

Assume that we have the Hidden Markov Model (HMM). If each of the states can take on k different values and a total of m different observations are possible (across all states), how many parameters are required to fully define this HMM? Justify your answer.

Answer:

There are a total of three probability distributions that define the HMM, the initial probability distribution, the transition probability distribution, and the emission probability distribution.

• There are a total of k states, so k parameters are required to define the initial probability distribution.

• For the transition distribution, we can transition from any one of k states to any of the k states (including staying in the same state), so k² parameters are required.

• We need a total of km parameters for the emission probability distribution, since each of the k states can emit each of the m observations.

Thus, the total number of parameters required are k + k² + km. Note that the number of parameters does not depend on the length of the HMMs.

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

Related questions:

• Why is it better to compute likelihood and probability values in log space?

• One common way probabilities are assigned to rules in a PCFG is to use a treebank. When will some rules have a probability of 0.0? What is the problem if some rule has a probability of 0.0? How can it be overcome?

• You are building an ngram model of a corpus. Should you stem the words and do the counts or leave them in the surface form? Give pros and cons and include what characteristics of the corpus might influence your decision.

• List down the features of PCFGs

• How many parameters are required to fully define a Hidden Markov Model?  

• Differentiate between generative and discriminative models.