维特比解码算法
维特比算法就是解码算法，它需要解决的是在给定观察 \(O\) 和 HMM 模型的条件下寻找一条最优的状态序列 \(Q\)，使得 \(P(O|Q)\) 概率最大。当然我们可以遍历所有可能状态序列，但这个运算量太大，显然不现实。这里我们就需要用到维特比算法了。
符号定义
我们定义 \(v_t(j)\) 为所有长度为 \(t\) 的路径中寻找概率最大的路径，并且需要满足在 \(t\) 时刻其状态为 \(j\)。哈哈，这里是不是很像前向计算的定义。那么我们有
\[v_t(j) = \max_{q_1,...,q_{t-1}}P(q_0,q_1,...,o_t,q_t=j|\lambda)\]
公式中的 \(\lambda\) 指的是 HMM 模型，它包含了状态转移概率 \(a_{ij}\) (从状态 \(i\) 转移到 \(j\) 的概率，总共有 \(N\) 个状态) 以及从状态到观测的概率密度函数。如果我们使用 GMM-HMM，则参数是高斯均值和高斯协方差。\(P(q_0,q_1,...,o_t,q_t=j|\lambda)\) 是观察为 \(o_1,...,o_t\)，状态为 \(q_0,...,q_{t-1},j\) 的联合概率。\(v_t(j)\) 则为其最大概率。
动态规划
\(t\) 时刻的最优路径一定是基于 \(t-1\) 时刻的最优路径，所以我们可以写出动态规划公式如下
\[v_t(j)=\max {}^{N}_{i=1} v_{t-1}(i)a_{ij}b_j(o_t)\]
这里 \(b_j(o_t)\) 表示在 \(t\) 时刻在状态 \(j\) 观测为 \(o_t\) 的概率。为了回溯最佳路径，我们还需要记下当前最优路径的上一个状态，可以用数组 \(bt_t(j)\)。那么动态规划的初始条件为
\[\begin{aligned} v_1(j)&=a_{0j}b_j(o_1) \ \ 1 \le j \le N \\ bt_1(j)&=0 \end{aligned}\]
注意这里 \(a_{oj}\) 指的是状态的初始概率。接下来我们可以写出递推公式
\[\begin{aligned} v_t(j)&=\max {}^{N}_{i=1} v_{t-1}(i) a_{ij} b_j(o_t) \\ bt_t(j)&=\arg\max {}^{N}_{i=1} v_{t-1}(i) a_{ij} b_j(o_t) \\ j& \in [1,N],t \in [1,T] \end{aligned}\]
最后，我们最优路径概率为 \(v_T(q_F)=\max {}^N_{i=1}v_T(i)a_{iF}\)，最优路径在 \(T\) 时刻的状态为 \(bt_T(q_F)=\arg\max{}^N_{i=1}v_T(i)a_{iF}\)
复杂度推算
维特比算法实际上我们填写的是一张 \(T*N\) 的二维表，每个元素代表了 \(v_t(j)\)。计算每个元素我们需要遍历 \(v_{t-1}(i)\)，其中 \(i \in [1,N]\)。因此复杂度为 \(O(T*N^2)\)。相比于直接的暴力运算，其复杂度为 \(O(N!)\)，要少不少。毕竟一个是多项式时间，一个是指数时间。