【轉】HMM學習最佳范例五：前向算法1 .

五、前向算法（Forward Algorithm）

計算觀察序列的概率（Finding the probability of an observed sequence）

1.窮舉搜索（ Exhaustive search for solution）
　　給定隱馬爾科夫模型，也就是在模型參數（, A, B)已知的情況下，我們想找到觀察序列的概率。還是考慮天氣這個例子，我們有一個用來描述天氣及與它密切相關的海藻濕度狀態的隱馬爾科夫模型(HMM)，另外我們還有一個海藻的濕度狀態觀察序列。假設連續3天海藻濕度的觀察結果是（干燥、濕潤、濕透）——而這三天每一天都可能是晴天、多云或下雨，對于觀察序列以及隱藏的狀態，可以將其視為網格：

　　網格中的每一列都顯示了可能的的天氣狀態，并且每一列中的每個狀態都與相鄰列中的每一個狀態相連。而其狀態間的轉移都由狀態轉移矩陣提供一個概率。在每一列下面都是某個時間點上的觀察狀態，給定任一個隱藏狀態所得到的觀察狀態的概率由混淆矩陣提供。
　　可以看出，一種計算觀察序列概率的方法是找到每一個可能的隱藏狀態，并且將這些隱藏狀態下的觀察序列概率相加。對于上面那個（天氣）例子，將有3^3 = 27種不同的天氣序列可能性，因此，觀察序列的概率是：
　　Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)
　　用這種方式計算觀察序列概率極為昂貴，特別對于大的模型或較長的序列，因此我們可以利用這些概率的時間不變性來減少問題的復雜度。

2.使用遞歸降低問題復雜度
　　給定一個隱馬爾科夫模型（HMM），我們將考慮遞歸地計算一個觀察序列的概率。我們首先定義局部概率（partial probability）,它是到達網格中的某個中間狀態時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
　　假設一個T-長觀察序列是：
　　　　　
　　
　2a.局部概率(’s)
　　考慮下面這個網格，它顯示的是天氣狀態及對于觀察序列干燥，濕潤及濕透的一階狀態轉移情況：
　　　
　　我們可以將計算到達網格中某個中間狀態的概率作為所有到達這個狀態的可能路徑的概率求和問題。
　　例如，t=2時位于“多云”狀態的局部概率通過如下路徑計算得出：
　　　
　　我們定義t時刻位于狀態j的局部概率為at(j)——這個局部概率計算如下：
　　t ( j )= Pr( 觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
　　對于最后的觀察狀態，其局部概率包括了通過所有可能的路徑到達這些狀態的概率——例如，對于上述網格，最終的局部概率通過如下路徑計算得出：
　　　
　　由此可見，對于這些最終局部概率求和等價于對于網格中所有可能的路徑概率求和，也就求出了給定隱馬爾科夫模型(HMM)后的觀察序列概率。
　　第3節給出了一個計算這些概率的動態示例。