3.3.2　HMM關鍵問題

一個HMM可以用一個三元組Φ來表示。圍繞這個三元組和觀測值，存在下面三個基本問題。

·評估問題：給定模型參數和觀測序列，推斷出觀測序列的可能概率。當存在多個模型時，比較它們對應的概率，可以確定描述該觀測序列最合適的HMM。

·解碼問題：給定模型參數和觀測序列，推斷出最可能經歷的隱含狀態。

·學習問題：給定觀測序列，學習得到最適合的HMM參數。

上述三個問題在統一的概率模型下緊密聯系，但側重點各有不同。解決這些問題都要使用動態規劃的基本原則，即將多步決策的過程拆分為多個單步狀態的級聯，從而將復雜問題轉化為每步狀態決策問題來解決。在HMM中，觀測序列和隱含序列包含了多步的轉移，要求取整個序列的優化目標，可以轉化成單步優化的子問題逐個解決。

1. 評估問題

給定一個HMM系統Φ，根據觀測序列X=（X₁，X₂，…，X_T），估計概率P（X|Φ），這時最基本的方法是將所有可能的狀態序列的概率相加：

對于特定的狀態序列S=（s₁，s₂，…，s_T），可以根據馬爾可夫性質計算該序列的聯合概率，再利用輸出獨立假設，可以計算得到如下概率：

其中為了統一，已將計算公式中應該包含的初始概率π_s1改寫為a_s0s1。

仍然以天氣為例，圖3-5中繪制出了連續5天的隱含狀態轉移網格圖。此時對應的觀測序列為“干燥、干燥、舒適、舒適、潮濕”。由于每種隱含狀態下都可能出現三種觀測狀態，因此每個觀測狀態的概率計算都要包含三種可能性。要計算連續5天觀測序列的概率，就需要先遍歷35=243種可能的隱含狀態轉移路徑，再將所有可能的隱含狀態轉移路徑對應概率累加。例如，如果隱含狀態為“晴、晴、多云、多云、陰雨”，則在此條件下產生該觀測序列的概率為（假設第一天為晴天的初始概率為0.6）：

P（X|晴，晴，多云，多云，陰雨）

=P（s₀=晴）P（X₀=干燥|s₀=晴）P（s₁=晴|s₀=晴）

P（X₁=干燥|s₁=晴）P（s₂=多云|s₁=晴）

P（X₂=舒適|s₂=多云）P（s₃=多云|s₂=多云）

P（X₃=舒適|s₃=多云）P（s₄=陰雨|s₃=多云）

P（X₄=潮濕|s₄=陰雨）

=0.6×0.5×0.5×0.5×0.2×0.6×0.4×0.6×0.3×0.8

≈5.2×10-4

顯然，當參數值很大時，這種計算的計算量巨大。需要采用合適的方法減少計算量。

從上面的計算實例中可以觀測到，由于所有的轉移概率、輸出概率都不隨時間變化，因此可以利用馬爾可夫性質和輸出獨立假設，將相鄰兩個時刻的局部輸出概率計算出來。可以通過前向迭代快速計算觀測序列的概率。前向算法（Forward Algorithm）就是遵循了這樣一個思路。可以定義前向概率參數為

它表示HMM在時刻t時，處于狀態i下產生觀測序列的概率。對應到實例中，就是今天是陰雨天，而且先前幾天的觀測序列概率是圖3-5中觀測序列的概率。

根據HMM的兩個假設，前向概率的計算只涉及相鄰兩天的狀態轉移概率P（s_t|s_t-1，Φ）和當天的輸出概率P（X_t|s_t，Φ），即僅依賴參數s_t-1，s_t和X_t，因此時刻t=T的P（X|Φ）可以按算法3-2迭代計算，示意圖如圖3-6所示。

使用前向算法計算前向概率時，只利用了前一個時刻的前向概率值。也就是說，如果知道了昨天各種天氣的前向概率，以及今天的濕度觀測值，那么在計算今天的前向概率時，只要遍歷當前的所有狀態就可以了。由于充分利用了局部路徑的概率，用前向算法計算最終概率時只需要將當前時刻的所有前向概率相加即可，不需要再遍歷所有的可能性，復雜度大幅下降。

在很多應用場合中，可能同時存在多個HMM，這時利用前向算法可以計算在給定每個HMM的條件下一個觀測序列的概率，并由此來選擇最適合這個序列的HMM。例如，在孤立詞語音識別中，每個單詞都可以定義一個HMM，因此可以得到數量較多的HMM。當檢測到一段語音信號時，根據前向算法計算得到每個HMM下該語音出現的概率，就能通過尋找對應此觀測序列最可能的HMM來識別這個單詞。

2. 解碼問題

給定一個HMM系統Φ，以及由系統產生的觀測序列，估計該系統產生此觀測序列時最可能經歷的狀態序列。對應上節的天氣示例，HMM的解碼過程也就是要在所有可能的243種路徑中確定一條最佳路徑，這條最佳路徑對應的就是解碼問題的答案——最佳狀態序列。

使用得最廣的最佳狀態序列定義為在給定觀測序列X的前提下，概率P（S|X，Φ）最大的狀態序列。顯然，遍歷所有可能路徑，直接窮舉對比的方法肯定不實用。與前向算法類似，根據HMM參數中概率不隨時間改變的特點以及HMM的馬爾可夫性質，可以知道，當前時刻最佳狀態的概率只和前一個時刻的各狀態的最佳概率以及一步轉移概率有關。這個性質和動態規劃思想很相似，因此可以使用Viterbi算法來確定HMM中的最佳狀態序列。

定義最佳路徑概率：

它是所有在時刻t時產生了觀測序列，并且結束狀態為i的狀態序列中的最大概率，其迭代計算公式為

式中，第三個等號兩側使用了最佳路徑概率的定義式和輸出獨立假設。最佳路徑概率和前向算法中的局部概率并不相同，最佳路徑概率對應的是最可能的路徑概率，而局部概率是所有概率的累加。

為了得到完整的最佳路徑，必須對每個i和j進行路徑跟蹤。定義B_t（j）為t時刻結束狀態為j的最佳路徑上，前一個時刻的狀態序號。B_t（j）可以記錄最佳路徑下的狀態鄰接關系，起到了后向指針的作用。例如，在圖3-5所示的觀測序列條件下，今天是陰雨天對應的最佳隱含狀態序列是晴、晴、多云、多云、陰雨，那么B_t（j）對應記錄的就是前一天是多云天。

尋找最佳路徑的Viterbi算法的計算步驟見算法3-3。

Viterbi算法采用了回溯方法對觀測序列全體進行匹配，“通盤”考慮了觀測序列的情況，可以有效降低噪聲帶來的干擾。

3. 學習問題

對一個未知的HMM系統Φ，根據系統產生的觀測序列，確定使系統聯合概率最大的模型參數。

評估問題是利用已知的模型參數計算給定隱含狀態序列的概率，解碼問題是利用已知的模型參數找到最佳的隱含狀態序列，它們都依賴于已知的HMM參數。但是對于很多問題來說，人們無法預先知道HMM的參數，只能依靠實際觀測來推測Φ中的各種參數。這個問題是HMM相關問題中最難的。

HMM學習問題是無監督學習的典型實例，其中只有觀測數據，缺少對狀態的描述，因此和GMM的參數估計一樣，可以使用EM算法解決。雖然使用現有理論還無法給出一個完整的表達式來得到使觀測數據概率最大的模型參數，但依然可以選擇最大似然作為最優化目標，使用Baum-Welch迭代算法來估計模型參數。Baum-Welch算法是Baum于1972年在EM算法的基礎上提出的，又由于它同時使用了前向概率和后向概率，因此通常又稱為前向-后向算法。

仿照前向概率，可以定義后向概率為

其中，β_t（i）是在t時刻HMM的狀態為i的條件下，HMM產生部分觀測序列的概率。此時觀測序列都是出現在當前時刻之后，因此后向概率考察的是當前時刻下未來的可能性。

β_t（i）的遞歸計算需要“由后向前”迭代，如圖3-7所示，方法如下。

為描述參數重估計過程，定義γ_t（i，j）表示在模型和觀測序列確定的條件下，時刻t時HMM從狀態i轉移到狀態j的概率：

滿足γ_t（i，j）條件的路徑如圖3-8所示，其中前向概率α從左到右計算，后向概率β從右到左計算。

式（3-17）實際計算的是在當前時刻t時狀態i向狀態j的轉移占所有狀態轉移概率的比值。這樣可以滿足概率的歸一化條件。

同樣地，類似γ_t（i，j），可以定義在模型和觀測序列確定的條件下，時刻t時HMM處于隱含狀態i的概率為V_t（i）：

根據式（3-17）和式（3-18）以及兩個概率的含義，可以得到。兩個公式中都同時包含了前向和后向因素，前向-后向算法的得名就源于此。

由此可以根據觀測序列來計算各參數的期望頻度，并作為HMM參數的估計，如表3-3所示。

估計公式為

其中，表示在觀測序列確定的情況下從狀態i出發的轉移個數的數學期望，表示在觀測序列確定的情況下，從狀態i轉移到狀態j的轉移個數的數學期望。

根據EM算法的性質，在得到模型參數的估計后，可以利用參數估計值替換原來的模型參數重新進行估計。Baum等已經證明，利用估計值重新估計，可得，因此如果迭代地計算式（3-19）的三個式子，不斷循環估計，那么可以得到最大似然意義下的最優模型參數。前向-后向算法得到的最優估計結果只是一個局部最優解，無法保證全局最優。