# 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)}