隐马尔科夫模型HMM自学 (5-1)Viterbi Algorithm
本来想明天再把后面的部分写好，可是睡觉今天是节日呢？一时情不自禁就有打开电脑..........
找到可能性最大的隐含状态序列
崔晓源 翻译
多数情况下，我们都希望能够根据一个给定的HMM模型，根据观察状态序列找到产生这一序列的潜在的隐含状态序列。
1、穷举搜索方法
我们可以通过穷举的方式列出所有可能隐含状态序列，并算出每一种隐状态序列组合对应的观察状态序列的概率。概率最大的那个组合对应的就是最可能的隐状态序列组合。
Pr(observed sequence | hidden state combination).
比如说上图中的trellis中，最有可能的隐状态序列是使得概率：
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)
得到最大值的序列。
同样这种穷举法的计算量太大了。为了解决这个问题，我们可以利用和Forward algorithm一样的原理--概率的时间不变性来减少计算量。
2.用递归方式减少复杂度
在给定的观察序列和HMM模型下，我们用一种递归的方式找到最有可能的隐状态序列。同样我们滴定部分概率，即在trellis中到达某一中间状态的概率。然后介绍如何在初始时刻t=1和t>1的时刻分别求解这个部分概率。但要注意，这里的部分概率是到达某一中间状态的概率最大的路径而不是所有概率之和。
2.1部分概率和部分最优路径
看如下trellis
对于trellis中的每个中间状态和结束状态，都存在一条到达它的最优路径。他可能是下图这样：
我们这些路径为部分最优路径，每一条 部分最优路径都对应一个关联概率--部分概率
。与Forward algorithm不同
是最有可能到达该状态的一条路径的概率。
(i,t)是所有序列中在t时刻以状态i终止的最大概率。当然它所对应那条路径就是部分最优路径。
(i,t)对于每个i,t都是存在的。这样我们就可以在时间T（序列的最后一个状态）找到整个序列的最优路径。
2b. 计算
‘s 在t = 1的初始值
由于在t=1不存在任何部分最优路径，因此可以用初始状态
向量协助计算。
这一点与Forward Algorithm相同
2c. 计算
‘s 在t > 1 的部分概率
同样我们只用t-1时刻的信息来得到t时刻的部分概率。
由此图可以看出到达X的最优路径是下面中的一条：
(sequence of states), . . ., A, X (sequence of states), . . ., B, X or (sequence of states), . . ., C, X
我们希望找到一条概率最大的。回想马尔科夫一阶模型的假设，一个状态之和它前一时刻的状态有关。
Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)
因此到达X的最大概率就是：
其中第一部分由t-1时刻的部分概率得到，第二部分是状态转移概率，第三部分是混淆矩阵中对应的概率。
（Viterbi Algorithm 待续）