Markov Models Example

Foundations of Statistical Natural Language Processing, Markov Models (chapter 9) Example

State Trasition Probability Table

Current State Later State Probability
Cola Pref. (CP) Cola Pref. (CP) 0.7
Cola Pref. (CP) Iced Tea Pref. (IP) 0.3
Iced Tea Pref. (IP) Cola Pref. (CP) 0.5
Iced Tea Pref. (IP) Iced Tea Pref. (IP) 0.5

Observation Probability Table

Current State Cola Iced Tea Lemon Tea
Cola Pref. (CP) 0.6 0.1 0.3
Iced Tea Pref. (IP) 0.1 0.7 0.2

For the observation sequence: {Lemon Tea, Iced Tea, Cola}

Forward Procedure

 
Lem_T
Iced_T
Cola
αCP 1.0 0.21

(1.0*0.3*0.7)

0.0462

(0.21*0.1*0.7 +
0.09*0.7*0.5)

0.021294

(0.0462*0.6*0.7 +
0.0378*0.1*0.5)

αIP 0 0.09

(1.0*0.3*0.3)

0.0378

(0.21*0.1*0.3 +
0.09*0.7*0.5)

0.010206

(0.0462*0.6*0.3 +
0.0378*0.1*0.5)

P   0.3 0.084 0.0315

Backward Procedure

 
Lem_T
Iced_T
Cola
βCP 0.0315

(0.045*0.3*0.7 +
0.245*0.3*0.3)

0.045

(0.6*0.1*0.7 +
0.1*0.1*0.3)

0.6 1.0
βIP 0.029

(0.045*0.2*0.5 +
0.245*0.2*0.5)

0.245

(0.6*0.7*0.5 +
0.1*0.7*0.5)

0.1 1.0
P 0.0315      

Best State Sequence

 
Lem_T
Iced_T
Cola
γCP 1.0 0.3

(0.21*0.045)/
(0.21*0.045 + 0.09*0.245)

0.88

(0.0462*0.6)/
(0.0462*0.6 + 0.0378*0.1)

0.676

0.021294/
(0.021294+0.010206)

γIP 0 0.7

(0.09*0.245)/
(0.21*0.045 + 0.09*0.245)

0.12

(0.0378*0.1)/
(0.0462*0.6 + 0.0378*0.1)

0.324

0.010206/
(0.021294+0.010206)

State CP IP CP CP

Viterbi Algorithm

 
Lem_T
Iced_T
Cola
δCP 1.0 0.21

max{1.0*0.3*0.7, 0*0.2*0.5}

0.0315

max{0.21*0.1*0.7, 0.09*0.7*0.5}

0.019404

max{0.0462*0.6*0.7,
0.0378*0.1*0.5}

δIP 0 0.09

max{1.0*0.3*0.3, 0*0.2*0.5}

0.0315

max{0.21*0.1*0.3, 0.09*0.7*0.5}

0.008316

max{0.0462*0.6*0.3, 0.0378*0.1*0.5}

ψCP   CP IP CP
ψIP   CP IP CP
Xt CP IP CP CP
P(X) 0.019404

max{δi(T+1)}