韋爾奇演算法

A. 馬爾可夫演算法不正確的是

馬爾可夫演算法不正確的是參考如下：

前向、後向演算法解決的是一個評估問題，即給定一個模型，求某特定觀測序列的概率，用於評估該序列最匹配的模型。

Baum-Welch演算法解決的是一個模型訓練問題，即參數估計，是一種無監督的訓練方法，主要通過EM迭代實現；

維特比演算法解決的是給定 一個模型和某個特定的輸出序列，求最可能產生這個輸出的狀態序列。如通過海藻變化（輸出序列）來觀測天氣（狀態序列），是預測問題，通信中的解碼問題。

HMM模型一共有三個經典的問題，含三種演算法：

1 、評估問題： 前向演算法

評估觀察序列概率。即給定模型λ=(A,B,Π)λ=(A,B,Π)和觀測序列O={o1,o2,...oT}O={o1,o2,...oT}，計算在模型λλ下觀測序列OO出現的概率P(O|λ)P(O|λ)。這個問題的求解需要用到前向後向演算法，我們在這個系列的第二篇會詳細講解。這個問題是HMM模型三個問題中最簡單的。

2 、學習問題： Baum-Welch演算法(向前向後演算法)

模型參數學習問題。即給定觀測序列O={o1,o2,...oT}O={o1,o2,...oT}，估計模型λ=(A,B,Π)λ=(A,B,Π)的參數，使該模型下觀測序列的條件概率P(O|λ)P(O|λ)最大。這個問題的求解需要用到基於EM演算法的鮑姆-韋爾奇演算法，這個問題是HMM模型三個問題中最復雜的。

3 、解碼問題： Viterbi演算法

預測問題，也稱為解碼問題。即給定模型λ=(A,B,Π)λ=(A,B,Π)和觀測序列O={o1,o2,...oT}O={o1,o2,...oT}，求給定觀測序列條件下，最可能出現的對應的狀態序列，這個問題的求解需要用到基於動態規劃的維特比演算法。

B. 隱馬爾可夫模型（基礎）

假設t時刻的狀態只與t-1時刻的狀態有關，與更早的時刻無關，這一假設稱為一階馬爾可夫假設。如果狀態有n種取值，在t時刻取任何一個值與t-1時刻取任何一個值的條件概率構成了一個n×n的矩陣A，稱為狀態轉移概率矩陣。無論t時刻的狀態值是什麼，在下一時刻一定會轉向n個狀態種一個，因此他們的轉移概率和必須為1。

在實際應用種，人們不能直接觀察到狀態的值，即狀態的值是隱含的，只能得到觀測的值。因此對模型進行擴充，得到隱馬模型。

觀測序列是能得到的值。

狀態序列是因，觀測序列是果，因為處於某種狀態才有了某一觀測值。

定義狀態觀測矩陣B，表示t時刻狀態值為s時的觀測值為v的概率

t時刻的狀態z=i的概率最大狀態序列中，t-1時刻的狀態值，有了這兩個變數，就可以得到維特比演算法。

訓練時給定一組樣本，確定狀態轉移矩陣和觀測矩陣，通過最大似然估計實現。如果已知訓練樣本集中每個觀測序列對應的狀態序列，給定初始狀態如：p0=[0.5, 0.2, 0.3], k步轉化過程為：p0=p0*pk。計算機程序需要利用迭代變數，藉助循環實現。經過多步轉化p0收斂於固定值(穩態)。可以通過最大似然估計得到模型參數。

狀態空間：隱狀態S的取值范圍

觀測空間：觀測狀態O的取值范圍

轉移概率：矩陣各元素都是用概率表示。其值非負，並且各行元素之和等於1。在一定條件下是互相轉移的，故稱為轉移概率矩陣。矩陣中的行數與列數可以相等，也可以不等。當它們相等時，矩陣就是一個方陣。由轉移概率組成的矩陣就是轉移概率矩陣。也就是說構成轉移概率矩陣的元素是一個個的轉移概率不同狀態之間的轉移概率，可以用轉移矩陣表示，記做a

發射概率：初始狀態的概率分布，在知道當前標簽的情況下，發射的概率，記做π

輸出概率：基於當前狀態，不同輸出的概率分布，記做b

模型參數λ = (a, b, π)

1、 齊次假設：即馬爾科夫假設

2、 觀測獨立性假設：觀測值只取決於對應的狀態值，與其他狀態無關

（1）首先, HMM模型表示為: lambda = HMM(A, B, pi), 其中A, B, pi都是模型的參數, 分別稱作: 轉移概率矩陣, 發射概率矩陣和初始概率矩陣.

（2）接著, 我們開始訓練HMM模型, 語料就是事先准備好的一定數量的觀測序列及其對應的隱含序列, 通過極大似然估計求得一組參數, 使由觀測序列到對應隱含序列的概率最大.

（3）在訓練過程中, 為了簡化計算, 馬爾可夫提出一種假設: 隱含序列中每個單元的可能性只與上一個單元有關. 這個假設就是著名的隱含假設.

（4）訓練後, 我們就得到了具備預測能力的新模型: lambda = HMM(A, B, pi), 其中的模型參數已經改變.

（5）之後給定輸入序列(x1, x2, ..., xn), 經過模型計算lambda(x1, x2, ..., xn)得到對應隱含序列的條件概率分布.

（6）最後, 使用維特比演算法從隱含序列的條件概率分布中找出概率最大的一條序列路徑就是我們需要的隱含序列: (y1, y2, ..., yn).

狀態轉移矩陣通過訓練樣本學習得到，採用最大似然估計。

初始狀態取每種值的概率Π，狀態轉移概率矩陣A，觀測概率矩陣B

隱馬爾可夫模型需要解決以下三個問題：

（1）估值問題（觀測序列出現的概率）。給定隱馬爾可夫模型的參數A和B，計算一個觀測序列x出現的概率值p（x）。前向後向演算法

（2）解碼問題（觀測序列最大化的隱含序列）。給定隱馬爾可夫模型的參數A和B以及一個觀測序列x，計算最有可能產生此觀測序列的狀態序列z。

已知一個觀測序列，尋找最有可能產生它的狀態序列。維特比演算法

（3）學習問題。給定隱馬爾可夫模型的結構，但參數未知，給定一組訓練樣本，確定隱馬爾可夫模型的參數A和B。

保姆韋爾奇演算法

隱馬爾可夫模型對條件概率p（x|z）建模，因此是一個生成式模型。