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

     

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料