Markov Models Example

2007-06-23
| No Comments

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

State Trasition Probability Table

Current StateLater StateProbability
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 StateColaIced TeaLemon Tea
Cola Pref. (CP)0.60.10.3
Iced Tea Pref. (IP)0.10.70.2

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

Forward Procedure

 
Lem_T
Iced_T
Cola
αCP1.00.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)

αIP00.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.30.0840.0315

Backward Procedure

 
Lem_T
Iced_T
Cola
βCP0.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.61.0
βIP0.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.11.0
P0.0315   

Best State Sequence

 
Lem_T
Iced_T
Cola
γCP1.00.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)

γIP00.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)

StateCPIPCPCP

Viterbi Algorithm

 
Lem_T
Iced_T
Cola
δCP1.00.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}

δIP00.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 CPIPCP
ψIP CPIPCP
XtCPIPCPCP
P(X)0.019404

max{δi(T+1)}

   

唸書, 學習工作, 研究