隱藏式馬可夫模型

隱藏式馬可夫模型（英語：Hidden Markov Model；縮寫：HMM），或稱作隱性馬可夫模型，是統計模型，用來描述一個含有隱含未知參數的馬可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數。然後利用這些參數來作進一步的分析，例如圖型識別。

在正常的馬可夫模型中，狀態對於觀察者來說是直接可見的。這樣狀態的轉換概率便是全部的參數。而在隱藏式馬可夫模型中，狀態並不是直接可見的，但受狀態影響的某些變數則是可見的。每一個狀態在可能輸出的符號上都有一概率分佈。因此輸出符號的序列能夠透露出狀態序列的一些資訊。

隱藏式馬可夫模型在熱力學、統計力學、物理學、化學、經濟學、金融學、訊號處理、資訊論、圖型識別（如語音辨識、^[1]手寫辨識、手勢辨識、^[2]詞性標記、樂譜跟隨^[3]）、局部放電^[4]及生物資訊科學等領域都有應用。^[5]^[6]

定義編輯

令 $X_{n}$ 、 $Y_{n}$ 為離散時間隨機過程， $n\geq 1$ 。則 $(X_{n},Y_{n})$ 是隱藏式馬可夫模型的條件是：

$X_{n}$ 是馬可夫過程，其行為不可直接觀測（「隱」）；
$\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{1}=x_{1},\ldots ,X_{n}=x_{n}{\bigr )}=\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{n}=x_{n}{\bigr )},$

\forall n\geq 1,\ x_{1},\ldots ,x_{n},

，且對每個鮑萊耳集

A

。

令 $X_{t}$ 、 $Y_{t}$ 為連續時間隨機過程。則 $(X_{t},Y_{t})$ 是隱藏式馬可夫模型的條件是：

$X_{t}$ 是馬可夫過程，其行為不可直接觀測（「隱」）；
$\operatorname {\mathbf {P} } (Y_{t_{0}}\in A\mid \{X_{t}\in B_{t}\}_{t\leq t_{0}})=\operatorname {\mathbf {P} } (Y_{t_{0}}\in A\mid X_{t_{0}}\in B_{t_{0}})$ ,

\forall t_{0}

、每個鮑萊耳集

A,

且每族鮑萊耳集

\{B_{t}\}_{t\leq t_{0}}.

過程狀態 $X_{n}$ （或 $X_{t}$ ）稱作隱狀態， $\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\mid X_{n}=x_{n}{\bigr )}$ （或 $\operatorname {\mathbf {P} } {\bigl (}Y_{t}\in A\mid X_{t}\in B_{t}{\bigr )}$ ）稱作條件概率或輸出概率。

馬可夫模型的演化編輯

下邊的圖示強調了HMM的狀態變遷。有時，明確的表示出模型的演化也是有用的，我們用 x(t₁) 與 x(t₂) 來表達不同時刻 t₁ 和 t₂ 的狀態。

圖中箭頭方向則表示不同資訊間的關聯性，因此可以得知 $x(t)$ 和 $x(t-1)$ 有關，而 $x(t-1)$ 又和 $x(t-2)$ 有關。

而每個 $y(t)$ 只和 $x(t)$ 有關，其中 $x(t)$ 我們稱為隱藏變數（hidden variable），是觀察者無法得知的變數。

隱性馬可夫模型常被用來解決有未知條件的數學問題。

假設隱藏狀態的值對應到的空間有 $N$ 個元素，也就是說在時間 $t$ 時，隱藏狀態會有 $N$ 種可能。

同樣的， $t+1$ 也會有 $N$ 種可能的值，所以從 $t$ 到 $t+1$ 間的關係會有 $N^{2}$ 種可能。

除了 $x(t)$ 間的關係外，每組 $x(t),y(t)$ 間也有對應的關係。

若觀察到的 $y(t)$ 有 $M$ 種可能的值，則從 $x(t)$ 到 $y(t)$ 的輸出模型複雜度為 $O(NM)$ 。如果 $y(t)$ 是一個 $M$ 維的向量，則從 $x(t)$ 到 $y(t)$ 的輸出模型複雜度為 $O(NM^{2})$ 。

Temporal evolution of a hidden Markov model

在這個圖中,每一個時間塊（x(t), y(t)）都可以向前或向後延伸。通常，時間的起點被設置為t=0 或 t=1.

馬可夫模型的概率編輯

假設觀察到的結果為 $Y$

$Y=y(0),y(1),...,y(L-1)$

隱藏條件為 $X$

$X=x(0),x(1),...,x(L-1)$

長度為 $L$ ，則馬可夫模型的概率可以表達為：

$P(Y)=\sum _{X}P(Y\mid X)P(X)\,$

由這個概率模型來看，可以得知馬可夫模型將該時間點前後的資訊都納入考量。

使用隱藏式馬可夫模型編輯

HMM有三個典型(canonical)問題:

預測(filter)：已知模型參數和某一特定輸出序列，求最後時刻各個隱含狀態的概率分佈，即求 $P(x(t)\ |\ y(1),\dots ,y(t))$ 。通常使用前向演算法解決。
平滑(smoothing)：已知模型參數和某一特定輸出序列，求中間時刻各個隱含狀態的概率分佈，即求 $P(x(k)\ |\ y(1),\dots ,y(t)),k<t$ 。通常使用前向-後向演算法解決。
解碼(most likely explanation)：已知模型參數，尋找最可能的能產生某一特定輸出序列的隱含狀態的序列，即求 $P([x(1)\dots x(t)]|[y(1)\dots ,y(t)])$ 。通常使用Viterbi演算法解決。

此外，已知輸出序列，尋找最可能的狀態轉移以及輸出概率.通常使用Baum-Welch演算法以及Viterbi algorithm（英語：Viterbi algorithm）解決。另外,最近的一些方法使用聯結樹演算法（英語：Junction tree algorithm）來解決這三個問題。 ^{[來源請求]}

具體實例編輯

假設你有一個住得很遠的朋友，他每天跟你打電話告訴你他那天做了什麼。你的朋友僅僅對三種活動感興趣：公園散步，購物以及清理房間。他選擇做什麼事情只憑天氣。你對於他所住的地方的天氣情況並不了解，但是你知道總的趨勢。在他告訴你每天所做的事情基礎上，你想要猜測他所在地的天氣情況。

你認為天氣的執行就像一個馬可夫鏈。其有兩個狀態「雨」和「晴」，但是你無法直接觀察它們，也就是說，它們對於你是隱藏的。每天，你的朋友有一定的概率進行下列活動：「散步」、「購物」、「清理」。因為你朋友告訴你他的活動，所以這些活動就是你的觀察數據。這整個系統就是一個隱藏式馬可夫模型（HMM）。

你知道這個地區的總的天氣趨勢，並且平時知道你朋友會做的事情。也就是說這個隱藏式馬可夫模型的參數是已知的。你可以用程式語言（Python）寫下來：

 states = ('Rainy', 'Sunny')
 
 observations = ('walk', 'shop', 'clean')
 
 start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
 transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
 emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
    }

在這些代碼中,start_probability代表了你對於你朋友第一次給你打電話時的天氣情況的不確定性（你知道的只是那個地方平均起來下雨多些）。在這裏，這個特定的概率分佈並非平衡的，平衡概率應該接近（在給定變遷概率的情況下）{'Rainy': 0.571, 'Sunny': 0.429}。 transition_probability 表示基於馬可夫鏈模型的天氣變遷，在這個例子中，如果今天下雨，那麼明天天晴的概率只有30%。代碼emission_probability 表示了你朋友每天做某件事的概率。如果下雨，有50% 的概率他在清理房間；如果天晴，則有60%的概率他在外頭散步。

這個例子在維特比演算法頁上有更多的解釋。

結構架構編輯

下圖展示了實例化HMM的一般結構。橢圓形代表隨機變量，可採用多個數值中的任意一種。隨機變量 $x(t)$ 是t時刻的隱狀態（圖示模型中 $x(t)\in \{x_{1},\ x_{2},\ x_{3}\}$ ）；隨機變量y(t)是t時刻的觀測值（ $y(t)\in \{x_{1},\ x_{2},\ x_{3},\ y_{4}\}$ ）；箭頭表示條件依賴關係。

隱藏式馬可夫模型的時間演化

圖中可清楚看出，給定隱變數 $x(t)$ 在時間t的條件概率分佈只取決於隱變數 $x(t-1)$ 的值，之前的則沒有影響，這就是所謂馬可夫性質。觀測變數 $y(t)$ 同理，只取決於隱變數 $x(t)$ 的值。

在本文所述標準HMM中，隱變數的狀態空間是離散的，而觀測值本身則可以離散（一般來自分類分佈）也可以連續（一般來自正態分佈）。HMM參數有兩類：轉移概率與輸出概率，前者控制 $t-1$ 時刻的隱狀態下，如何選擇t時刻的隱狀態。

隱狀態空間一般假設包含N個可能值，以分類分佈為模型。這意味着，對隱變數在t時刻可能所處的N種狀態中的每種，都有到 $t+1$ 時刻可能的N種狀態的轉移概率，共有 $N^{2}$ 個轉移概率。注意從任意給定狀態轉移的轉移概率之和須為1。於是，轉移概率構成了N階方陣，稱作馬可夫矩陣。由於任何轉移概率都可在已知其他概率的情形下確定，因此共有 $N(N-1)$ 個轉移參數。

此外，對N種可能狀態中的每種，都有一組輸出概率，在給定隱狀態下控制着觀測變數的分佈。這組概率的大小取決於觀測變數的性質，例如，若觀測變數是離散的，有M種值、遵循分類分佈，則有 $M-1$ 個獨立參數，所有隱狀態下共有 $N(M-1)$ 個輸出概率參數。若觀測向量是M維向量，遵循任意多元正態分佈，則將有M個參數控制均值， ${\frac {M(M+1)}{2}}$ 個參數控制協方差矩陣，共有 $N\left(M+{\frac {M(M+1)}{2}}\right)={\frac {NM(M+3)}{2}}=O(NM^{2})$ 個輸出參數。（這時，除非M很小，否則限制觀測向量各元素間協方差的性質可能更有用，例如假設各元素相互獨立，或假設除固定多相鄰元素外，其他元素相互獨立。）

學習編輯

HMM的參數學習任務是指在給定輸出序列或一組序列的情形下，找到一組最佳的狀態轉換和轉移概率。任務通常是根據一組輸出序列，得到HMM參數的最大似然估計值。目前還沒有精確解這問題的可行演算法，可用鮑姆-韋爾奇演算法或Baldi–Chauvin演算法高效地推導出局部最大似然。鮑姆-韋爾奇演算法是最大期望值演算法的特例。

若將HMM用於時間序列預測，則更複雜的貝葉斯推理方法（如馬可夫鏈蒙地卡羅採樣法，MCMC採樣法）已被證明在準確性和穩定性上都優於尋找單一的最大似然模型。^[7]由於MCMC帶來了巨大的計算負擔，在計算可延伸性也很重要時，也可採用貝葉斯推理的變分近似方法，如^[8]。事實上，近似變分推理的計算效率可與期望值最大化相比，而精確度僅略遜於精確的MCMC型貝葉斯推理。