前向式演算法

前向算法（Forward algorithm），在隱馬爾可夫模型（HMM）中，是用於計算「置信狀態」的。置信狀態指根據既往證據推算出的當前狀態的概率分布。這個過程也被叫做「濾波」。前向算法和維特比算法緊密相關但又互不相同。

發展歷史

前向算法是用來解決解碼問題的算法之一。自從語音識別技術^[1]和模式識別技術發展以來，它也越來越普遍地被用在像計算生物學^[2]這樣的使用HMM的領域內。

算法

整個算法的目標是計算聯合概率分布 ${\displaystyle p(x_{t},y_{1:t})}$。為了方便，我們把 ${\displaystyle x(t)}$ 簡寫做 ${\displaystyle x_{t}}$，將 ${\displaystyle (y(1),y(2),...,y(t))}$ 簡寫做 ${\displaystyle y_{1:t}}$。直接計算${\displaystyle p(x_{t},y_{1:t})}$則需要計算所有狀態序列 ${\displaystyle \{x_{1:t-1}\}}$ 的邊緣分布，而它的數量和 ${\displaystyle t}$ 成指數相關。使用這一算法，我們可以利用HMM的條件獨立性質，遞歸地進行計算。

我們令

${\displaystyle \alpha _{t}(x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})}$.

利用鏈式法則來展開${\displaystyle p(x_{t},x_{t-1},y_{1:t})}$，我們可以得到

${\displaystyle \alpha _{t}(x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})}$.

由於 ${\displaystyle y_{t}}$ 和除了 ${\displaystyle x_{t}}$ 之外的一切都條件獨立，而 ${\displaystyle x_{t}}$ 又和 ${\displaystyle x_{t-1}}$ 之外的一切都條件獨立，因此

${\displaystyle \alpha _{t}(x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha _{t-1}(x_{t-1})}$.

這樣，由於 ${\displaystyle p(y_{t}|x_{t})}$ 和 ${\displaystyle p(x_{t}|x_{t-1})}$ 由HMM的輸出概率和狀態轉移概率我們可以很快計算用 ${\displaystyle \alpha _{t-1}(x_{t-1})}$ 計算出${\displaystyle \alpha _{t}(x_{t})}$，並且可以避免遞歸計算。

前向算法可以很容易地被修改來適應其他的HMM變種，比如馬爾可夫跳躍線性系統。

平滑處理

為了能夠使用「未來的歷史」（比如我們在試圖預測過去的某個時點的狀態），我們可以運行後向算法，它是前向算法的一個補充。這一操作被稱為平滑^[為何？]。 前向-後向算法對 ${\displaystyle 1<k<t}$ 計算 ${\displaystyle P(x_{k}|y_{1:t})}$，因此使用了過去和未來的全部信息。

解碼算法

為了解碼最可能的序列，需要使用維特比算法。它會從過去的觀測中試圖推測最可能的狀態序列，也即使 ${\displaystyle P(x_{0:t}|y_{0:t})}$ 最大化的狀態序列。