hmm和Veterbi算法（一）

只是略微的看了些，有点感觉，还未深入，做个记录。

参考： 隐马尔可夫 (HMM)、前 / 后向算法、Viterbi 算法 再次总结

　　　谁能通俗的讲解下 viterbi 算法？

　　　数学之美第二版的第 26 章

本文结构：

　　1.hmm三要素

　　2.维特比算法

　　3.简明例子

hmm三要素：

1.初始概率分布 π

      z1 可能是状态 1，状态 2 ... 状态 n，于是 z1 就有个 N 点分布：

Z1	状态 1	状态 2	...	状态 n
概率	P1	P2	...	Pn

      即：Z1 对应个 n 维的向量。

      上面这个 n 维的向量就是初始概率分布，记做π。

2.状态转移矩阵 A

      但 Z2 就不能简单的 “同上” 完事了，因为 Z2 和 Z1 不独立，所以 Z2 是状态 1 的概率有：Z1 是状态 1 时 Z2 是状态 1，Z1 是状态 2 时 Z2 是状态 1,..., Z1 是状态 n 时 Z2 是状态 1，于是就是下面的表

Z2 Z1	状态 1	状态 2	...	状态 n
状态 1	P11	P12	...	P1n
状态 2	P21	P22	...	P2n
...	...	...	...	...
状态 n	Pn1	Pn2	...	Pnn

       即：Z1->Z2 对应个 n*n 的矩阵。

       同理：Zi -> Zi+1 对应个 n*n 的矩阵。

      上面这些 n*n 的矩阵被称为状态转移矩阵，用 An*n 表示。

      当然了，真要说的话，Zi -> Zi+1 的状态转移矩阵一定都不一样，但在实际应用中一般将这些状态转移矩阵定为同一个，即：只有一个状态转移矩阵。

3.观测矩阵 B

      如果对于 zi 有：状态 1, 状态 2, ..., 状态 n，那 zi 的每一个状态都会从下面的 m 个观测中产生一个：观测 1, 观测 2, ..., 观测 m，所以有如下矩阵：

X Z	观测 1	观测 2	...	观测 m
状态 1	P11	P12	...	P1m
状态 2	P21	P22	...	P2m
...	...	...	...	...
状态 n	Pn1	Pn2	...	Pnm

      这可以用一个 n*m 的矩阵表示，也就是观测矩阵，记做 Bn*m。

      由于 HMM 用上面的π，A，B 就可以描述了，于是我们就可以说：HMM 由初始概率分布π、状态转移概率分布 A 以及观测概率分布 B 确定，为了方便表达，把 A, B, π 用 λ 表示，即：

            λ = (A, B, π)

维特比算法

维特比算法是一个特殊但应用最广的动态规划算法，它是针对篱笆网络的有向图（Lattice）的最短路径问题而提出的。凡是使用隐含马尔可夫模型描述的问题都可以用维特比算法来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。

1.基础概括

（1）如果概率最大的路径 P（或叫最短路径）经过某个点，比如下图中的 X₂₂，那么这条路径上从起始点 S 到 X₂₂ 的这一段子路径 Q，一定是 S 到 X₂₂ 之间的最短路径。否则，用 S 到 X₂₂ 的最短路径 R 替代 Q，便构成了一条比 P 更短的路径，这显然是矛盾的。

（2）从 S 到 E 的路径必定经过第 i 时刻的某个状态，假定第 i 时刻有 k 个状态，那么如果记录了从 S 到第 i 个状态的所有 k 个节点的最短路径，最终的最短路径必经过其中的一条。这样，在任何时刻，只需要考虑非常有限条最短路径即可。

 （3）结合上述两点，假定当我们从状态 i 进入状态 i+1 时，从 S 到状态 i 上各个节点的最短路径已经找到，并且记录在这些节点上，那么在计算从起点 S 到前一个状态 i 所有的 k 个结点的最短路径，以及从这 k 个节点到 X_i+1，j 的距离即可。

2.总结

（1）从点 S 出发，对于第一个状态 X₁ 的各个节点，不妨假定有 n₁ 个，计算出 S 到它们的距离 d(S,X_1i)，其中 X_1i 代表任意状态 1 的节点。因为只有一步，所以这些距离都是 S 到它们各自的最短距离。

（2）对于第二个状态 X₂ 的所有节点，要计算出从 S 到它们的最短距离。对于特点的节点 X_2i，从 S 到它的路径可以经过状态 1 的 n₁ 中任何一个节点 X_1i，对应的路径长度就是 d(S,X_2i) = d(S,X_1i) + d(X_1i,X_2i)。由于 j 有 n₁ 种可能性，我们要一一计算，找出最小值。即：

d(S,X_2i) = min_I=1，n1 d(S,X_1i) + d(X_1i,X_2i)

这样对于第二个状态的每个节点，需要 n₁ 次乘法计算。假定这个状态有 n₂ 个节

点，把 S 这些节点的距离都算一遍，就有 O(n₁·n₂) 次计算。

（3）接下来，类似地按照上述方法从第二个状态走到第三个状态，一直走到最后一个状态，就得到了整个网格从头到尾的最短路径。每一步计算的复杂度都和相邻两个状态 S_i 和 S_i+1 各自的节点数目 n_i，n_i+1 的乘积成正比，即 O(n_i·n_i+1)

（4）假设这个隐含马尔可夫链中节点最多的状态有 D 个节点，也就是说整个网格的宽度为 D，那么任何一步的复杂度不超过 O(D²)，由于网格长度是 N，所以整个维特比算法的复杂度是 O(N·D²)。

 简明例子