Hidden Markov Model Solved Exercise

Question:

1. Mr. X is happy someday and angry on other days. We can only observe when he smiles, frowns, laughs, or yells but not his actual emotional state. Let us start on day 1 in the happy state. There can be only one state transition per day. It can be either to happy state or angry state. The HMM is shown below;

Assume that q_t is the state on day t and o_t is the observation on day t. Answer the following questions;

(a) What is P(q₂ = Happy)?

(b) What is P(o₂ = frown)?

(c) What is P(q₂ = Happy | o₂ = frown)?

(d) What is P(o₁ = frown o₂ = frown o₃ = frown o₄ = frown o₅ = frown, q₁ = Happy q₂ = Angry q₃ = Angry q₄ = Angry q₅ = Angry) if π = [0.7, 0.3]?

Solution:

(a) What is P(q₂ = Happy)?

The question is to find the probability of Mr. X is Happy on day 2. It is given that the first day he was Happy. For the second day, we need to find the transition probability P(q₂ = Happy | q₁ = Happy).

P(q₂ = Happy | q₁ = Happy) = 0.8

(b) What is P(o₂ = frown)?

We need to find the probability of observation frown on day 2. But we don’t know the states whether he is happy or not on day 2 (we know he was happy on day 1). Hence, the probability of the observation is the sum of products of observation probabilities and all possible hidden state transitions.

P(o₂ = frown) = P(o₂ = frown | q₂ = Happy) + P(o₂ = frown | q₂ = Angry)

            = P(Happy | Happy)* P(frown | Happy) + P(Angry | Happy)* P(frown | Angry)

            = (0.8 * 0.1) + (0.2 * 0.5) = 0.08 + 0.1 = 0.18

(c) What is P(q₂ = Happy | o₂ = frown)?

Here, we need to find the probability of hidden state on day 2 as Happy given the observation on that day as frown. This conditional probability cannot be calculated directly. Hence, we apply Bayes’ rule to solve as follows;

P(q₂ = Happy | o₂ = frown) = (P(o₂ = f| q₂ = H) * P(q₂ = H)) / P(o₂ = f)

                                                = (P(Happy | Happy)* P(frown | Happy)) / 0.18

[Note: 0.18 is taken from the answer for question (b)]

                                                = (0.8 * 0.1) / 0.18 = 0.08 / 0.18 = 0.4444

(d) What is P(o₁ = frown o₂ = frown o₃ = frown o₄ = frown o₅ = frown, q₁ = Happy q₂ = Angry q₃ = Angry q₄ = Angry q₅ = Angry) if π = [0.7, 0.3]?

Here, we need to find the probability of the observation sequence “frown frown frown frown frown” given the state sequence “Happy Angry Angry Angry Angry”. π is the initial probabilities.

P(f f f f f, H A A A A)  

            = P(f|H)*P(f|A)*P(f|A)*P(f|A)*P(f|A)*P(H)*P(A|H)*P(A|H)*P(A|H)*P(A|H)

            = 0.1 * 0.5 * 0.5 * 0.5 * 0.5 * 0.7 * 0.2 * 0.2 * 0.2 * 0.2

            = 0.000007

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

Related Links:

• Go to Hidden Markov Model Formal Definition page

• Go to Natural Language Processing (NLP) home

• Go to NLP Glossary - Dictionary page

How to calculate the tranisiton and emission probabilities in HMM from a corpus?

Solved exercise in HMM, Exercise with solutions in hidden markov model, solutions to exercises in natural language processing

Maximum Likelihood Estimate in HMM 

Calculate emission probability in HMM

how to calculate transition probabilities in hidden markov model

how to calculate bigram and trigram transition probabilities solved exercise

solved problems in hidden markov model

Probabilistic Context Free Grammar PCFG - How to derive probabilities for production rules from treebank

Probabilistic Context Free Grammar (PCFG) - How to calculate probabilities for production rules from Treebank?

PCFG Solved Exercise

Question:

Consider the following 3 trees as a Treebank and derive a Probabilistic Context Free Grammar(PCFG) from this Treebank. [Derive the probabilities of production rules]

Solution:

Let us assume that the given Treebank is the training corpus. It consists of common start symbol S, set of non-terminals, set of terminal symbols and production rules. Each rule derives a non-terminal to another set of non-terminals or combination of terminals and non-terminals. PCFG will consist of these rules with the probability for each rule.

The probability estimate for a rule A → s can be calculated using Maximum Likelihood estimate. Here, s is a sequence of terminals and non-terminals. It is from (T U V)*, infinite set of strings. [Refer here for formal definition of CFG]

The probability estimate of a production rule can be written as,

Let us use this equation to derive the probabilities;

1. If you look at the Treebank, the common start symbol S is derived to NP and VP. This is the rule S → NP VP.

In the given Treebank, the rule S → NP VP appears 3 times and S on the Left Hand Side (LHS) appears 3 times.

2. V1 and SBAR derived from VP. Hence, VP → V1 SBAR.

3. Next rule, SBAR → COMP S.

4. Let us choose one rule that has only the terminal symbol on its RHS. For example, the rule, NP → John is one such rule (We refer it as lexicon).

The other probabilities can be calculated as shown above. As a result, we get the grammar and the corresponding probabilities for the PCFG as follows;

Rule	Probability
S → NP VP SBAR → COMP S COMP → that VP → V1 SBAR | VP ADVP | V2 NP → Sally NP → John|Bill|Fred|Jeff V1 → said|declared|pronounced V2 → snored|ran|swam ADVP → loudly | quickly |elegantly	1 1 1 1/3 1/3 1/6 1/3 1/3 1/3

**********

Related links:

• Go to Probabilistic Context Free Grammar (PCFG) Home

• Go to Natural Language Processing (NLP) home

• Go to NLP Solved Exercise page

• Go to Context Free Grammar (CFG) Formal Definition page

How to derive probabilities for production rules from Treebank using maximum likelihood estimate

PCFG probabilities estimation

How to calculated production rule probability in PCFG using tree banks

Probabilistic context free grammar rule probability estimation using tree banks