How jieba works, part 2

這篇將解釋何謂馬可夫模型 Markov model、隱藏式馬可夫模型 Hidden Markov model (HMM)、與 Viterbi 演算法。

馬可夫模型 Markov model

馬可夫模型是一個用來解釋偽隨機系統的模型。它假設未來事件只受到現在事件影響，不受更早事件影響。

範例：假設你是醫生，從你的臨床經驗來看，一個人身體前一天健康、今天也健康的機率是 0.7；前一天健康、今天生病的機率是 0.3；前一天生病、今天健康的機率是 0.4；前一天生病、今天還是生病的機率是 0.6：

狀態轉換機率 (transition probability)
- P(今天健康|前一天健康) = 0.7
- P(今天生病|前一天健康) = 0.3
- P(今天健康|前一天生病) = 0.4
- P(今天生病|前一天生病) = 0.6

上圖為馬可夫鏈，馬可夫模型的一種。

如果小明今天是健康的，那麼他三天後生病的機率是多少？

第一天初始機率：

D1(健康) = 1.0
D1(生病) = 0.0

第二天：

D2(健康) = D1(健康) * P(健康|前一天健康) + D1(生病) * P(健康|前一天生病)
D2(健康) = 1.0 * 0.7 + 0.0  * 0.4
D2(健康) = 0.7 + 0.0
D2(健康) = 0.7

D2(生病) = D1(健康) * P(生病|前一天健康) + D1(生病) * P(生病|前一天生病)
D2(生病) = 1.0 * 0.3 + 0.0 * 0.6
D2(生病) = 0.3 + 0.0
D2(生病) = 0.3

第三天：

D3(健康) = D2(健康) * P(健康|前一天健康) + D2(生病) * P(健康|前一天生病)
D3(健康) = 0.7 * 0.7 + 0.3 * 0.4
D3(健康) = 0.49 + 0.12
D3(健康) = 0.61

D3(生病) = D2(健康) * P(生病|前一天健康) + D2(生病) * P(生病|前一天生病)
D3(生病) = 0.7 * 0.3 + 0.3 * 0.6
D3(生病) = 0.21 + 0.18
D3(生病) = 0.39

小明三天後生病的機率是 0.39。

隱藏式馬可夫模型 Hidden Markov model (HMM)

但在現實生活中，我們沒有辦法直接知道小明確切的狀態會是如何。我們只能間接地透過一些症狀來診斷小明。例如，小明來看診時會說他在第一天覺得身體正常，第二天感到肚子痛，第三天有嘔吐。

這些症狀就是小明身體實際狀態所發出的訊號。因為我們不知道真正的狀態是如何(健康或生病)，所以稱為隱藏狀態 (hidden state)。

隱藏式馬可夫模型承接馬可夫模型的屬性 (未來狀態只受到現在狀態影響)，但無法直接觀察到狀態，只能從發出的訊號與相關的機率 (emission probability) 對隱藏狀態做猜測。

繼續小明的例子解釋：

小明來看診，對你敘述了過去三天的症狀：

第一天覺得身體正常
第二天感到肚子痛
第三天有嘔吐

你與小明都不知道他確切的身體狀態 (健康或生病)，只能從你的專業經驗與症狀做診斷。

以下是你的專業經驗：

初始狀態機率
- 一個人某天是健康的機率是 0.6
- 一個人某天是生病的機率是 0.4
狀態轉移機率 (transition probability)
- P(健康|前一天健康): 0.7 (前一天健康，今天也健康的機率)
- P(生病|前一天健康): 0.3 (前一天健康，今天生病的機率)
- P(健康|前一天生病): 0.4 (前一天生病，今天健康的機率)
- P(生病|前一天生病): 0.6 (前一天生病，今天也生病的機率)
症狀機率 (發射機率 emission probability)
- P(健康|正常): 0.5 (覺得正常，身體健康的機率)
- P(健康|腹痛): 0.4 (感到腹痛，身體健康的機率)
- P(健康|嘔吐): 0.1 (有嘔吐，身體健康的機率)
- P(生病|正常): 0.1 (覺得正常，身體生病的機率)
- P(生病|腹痛): 0.3 (感到腹痛，身體生病的機率)
- P(生病|嘔吐): 0.6 (有嘔吐，身體生病的機率)

小明在這三天最有可能的身體狀態組合是如何？

我們有兩種隱藏狀態，三天的觀測。總共會有 2^3=8 種可能組合：

哪一個組合才是最有可能的路徑？

我們可以蠻力算出所有路徑的機率，但如果隱藏狀態或是觀察天數增加的話，路徑數量會指數性成長。

使用 Viterbi 演算法可以避免計算所有路徑的機率。

Viterbi 演算法

Viterbi 演算法會在每個路徑的分歧點比較哪一條的機率較高，然後捨棄機率較低的路徑。

我們直接帶入小明的例子做計算：

第一步：算出第一天的隱藏狀態

這天小明覺得身體正常。

D1(健康) = 0.6 * P(健康|正常)
D1(健康) = 0.6 * 0.5
D1(健康) = 0.3

D1(生病) = 0.4 * P(生病|正常)
D1(生病) = 0.4 * 0.1
D1(生病) = 0.04

第二步：找出從第一天到第二天的最佳路徑

第二天的每個隱藏狀態都有兩條潛在路徑(從左往右走)。

抵達D2健康的路徑A與路徑B

抵達D2生病的路徑C與路徑D

我們先看抵達於D2健康的路徑A與路徑B，哪條機率高：

路徑A = D1健康 * P(健康|前一天健康)
路徑A = 0.3 * 0.7
路徑A = 0.21

路徑B = D1生病 * P(生病|前一天健康)
路徑B = 0.04 * 0.3
路徑B = 0.012

路徑A比路徑B機率高，所以抵達於D2健康的路線來自於D1健康。

再來，比較路徑C與路徑D：

路徑C = D1健康 * P(健康|前一天生病)
路徑C = 0.3 * 0.3
路徑C = 0.09

路徑D = D1生病 * P(生病|前一天生病)
路徑D = 0.04 * 0.6
路徑D = 0.024

路徑C比路徑D機率高，所以抵達於D2生病的路線來自於D1健康。

從第一天到第二天的可能路徑如下：

第三步：計算第二天的隱藏狀態機率

現在我們知道第二天的隱藏狀態是來自D1(健康)，可以著手計算隱藏狀態機率。回憶小明第二天感到腹痛。

D2健康 = max(路徑A, 路徑B) * P(健康|腹痛)
D2健康 = 0.21 * 0.4
D2健康 = 0.084

D2生病 = max(路徑C, 路徑D) * P(生病|腹痛)
D2生病 = 0.09 * 0.3
D2生病 = 0.027

第四步：重複第二、三步來算出第三天的隱藏狀態機率

第三天的每個隱藏狀態都有兩條潛在路徑(從左往右走)

抵達D3健康的路徑E與路徑F

抵達D3生病的路徑G與路徑H

我們先看抵達於D3健康的路徑E與路徑F，哪條機率高：

路徑E = D2健康 * P(健康|前一天健康)
路徑E = 0.084 * 0.7
路徑E = 0.0588

路徑F = D2生病 * P(生病|前一天健康)
路徑F = 0.027 * 0.4
路徑F = 0.0108

路徑E比路徑F機率高，所以抵達於D3健康的路線來自於D2健康。

再來，比較路徑G與路徑H：

路徑G = D2健康 * P(健康|前一天生病)
路徑G = 0.3 * 0.3
路徑G = 0.09

路徑H = D2生病 * P(生病|前一天生病)
路徑H = 0.04 * 0.6
路徑H = 0.024

路徑G比路徑H機率高，所以抵達於D3生病的路線來自於D2健康。

從第二天到第三天的可能路徑如下：

注意: 從D1健康到D2生病的路徑因為無法往第三天延續，所以在此捨棄。

最後，計算第三天的隱藏狀態機率。小明在這天嘔吐。

D3健康 = max(路線E, 路線F) * P(健康|嘔吐)
D3健康 = 0.0588 * 0.1
D3健康 = 0.00588

D3生病 = max(路線G, 路線H) * P(生病|嘔吐)
D3生病 = 0.0252 * 0.6
D3生病 = 0.01512

選出最佳路徑

小明在這三天最有可能的身體狀態組合是如何？

D3生病的機率最高。抵達D3生病的路徑來自D2健康，而抵達D2健康的路徑來自D1健康。

答：第一天健康，第二天健康，第三天生病。

接下來回到分詞的例子。回顧在 Part 1 我們用一個前綴字典從『我昨天去上海交通大學與老師討論量子力學』找出了『昨天』、『上海』、『交通』、『量子』，但還是有很多個字尚未分詞。

在 Part 3 我們要將剩下的字 (大、學、與、老、師、討、論、力、學) 用本篇介紹的隱藏式馬可夫模型與 Viterbi 演算法分詞。

結巴分詞解析三部曲, 第二集