A.4 解码：Viterbi 算法 - SLP3 中文翻译

对 HMM 这类包含隐藏变量的模型，确定哪个变量序列是某个观察序列的潜在来源，这项任务称为解码（decoding）。在冰淇淋领域中，给定冰淇淋观察序列 3 1 3 和一个 HMM，解码器要找出最佳的隐藏天气序列 H H H。形式化地说：

解码：输入 HMM $\lambda=(A,B)$ 和观察序列 $O=o_1,o_2,\ldots,o_T$ ，找出概率最大的状态序列 $Q=q_1q_2q_3\ldots q_T$ 。

一种直观设想是：对每种可能的隐藏状态序列 HHH、HHC、HCH 等，运行前向算法，计算给定该隐藏状态序列时观察序列的似然；再选择观察似然最大的隐藏状态序列。上一节已经说明，这种方法不可行，因为状态序列的数量随长度呈指数增长。

HMM 最常用的解码算法是 Viterbi 算法。与前向算法一样，Viterbi 是一种使用动态规划网格的动态规划算法。它也与第 2 章的最小编辑距离算法高度相似。

图 A.8　Viterbi 网格：计算冰淇淋事件 3 1 3 在隐藏状态空间中的最佳路径。圆形表示隐藏状态，方形表示观察；空心圆表示非法转移。图中展示两个时间步、两个状态上的 $\nu_t(j)$ 计算。每个单元格按公式 A.14 计算，其所表示的概率定义见公式 A.13。

图 A.8 展示计算观察序列 3 1 3 的最佳隐藏状态序列时所用的 Viterbi 网格。算法从左到右处理观察序列并填充网格。给定自动机 $\lambda$ ，网格中的每个单元格 $\nu_t(j)$ 表示：看到前 $t$ 个观察，并且经过概率最大的状态序列 $q_1,\ldots,q_{t-1}$ 后，HMM 处于状态 $j$ 的概率。计算每个 $\nu_t(j)$ 时，递归选择能够到达该单元格的最大概率路径。形式上：

\nu_t(j)=\max_{q_1,\ldots,q_{t-1}}P(q_1\ldots q_{t-1},o_1,o_2,\ldots,o_t,q_t=j\mid\lambda)\tag{A.13}

注意，我们通过对所有可能的前序状态序列取最大值来表示最大概率路径。与其他动态规划算法相同，Viterbi 递归填充各单元格。假设已经算出时间 $t-1$ 处于各状态的概率，就对通向当前单元格的各种路径扩展取最大值，得到 Viterbi 概率。对时间 $t$ 的给定状态 $q_j$ ：

\nu_t(j)=\max_{i=1}^{N}\nu_{t-1}(i)a_{ij}b_j(o_t)\tag{A.14}

公式 A.14 在扩展已有路径、计算时间 $t$ 的 Viterbi 概率时，将以下三个因子相乘：

$\nu_{t-1}(i)$ ：前一时间步的 Viterbi 路径概率；
$a_{ij}$ ：从前一状态 $q_i$ 到当前状态 $q_j$ 的转移概率；
$b_j(o_t)$ ：当前状态 $j$ 生成观察符号 $o_t$ 的观察似然。

function VITERBI(observations[1..T], state-graph[1..N])
    returns best-path, path-prob
    create path-probability matrix viterbi[N,T]
    for each state s = 1..N                         # 初始化
        viterbi[s,1] ← π_s × b_s(o_1)
        backpointer[s,1] ← 0
    for each time step t = 2..T                    # 递归
        for each state s = 1..N
            viterbi[s,t] ← max_{s'=1..N}
                viterbi[s',t-1] × a_{s',s} × b_s(o_t)
            backpointer[s,t] ← argmax_{s'=1..N}
                viterbi[s',t-1] × a_{s',s} × b_s(o_t)
    best-path-prob ← max_{s=1..N} viterbi[s,T]     # 终止
    best-path-pointer ← argmax_{s=1..N} viterbi[s,T]
    best-path ← 从 best-path-pointer 开始沿 backpointer 反向追踪
    return best-path, best-path-prob

图 A.9　寻找最优隐藏状态序列的 Viterbi 算法。给定观察序列和 HMM $\lambda=(A,B)$ ，算法返回使观察序列似然最大的 HMM 状态路径。

Viterbi 算法与前向算法几乎相同，区别在于 Viterbi 对前序路径概率取最大值，而前向算法对它们求和。Viterbi 还有前向算法没有的组成部分：回溯指针（backpointer）。前向算法只需产生观察似然，Viterbi 则必须同时产生概率和最大似然状态序列。因此，我们记录通向每个状态的最佳隐藏状态路径，如图 A.10 所示；最后从最佳路径的末端反向追踪到起点，这称为 Viterbi 回溯。

图 A.10　Viterbi 回溯。把每条路径扩展到新状态、处理下一个观察时，保留一个指向到达该状态之最佳路径的回溯指针（虚线）。

Viterbi 递归的形式化定义如下。

初始化：

\begin{aligned} \nu_1(j)&=\pi_jb_j(o_1), &&1\leq j\leq N,\\ bt_1(j)&=0, &&1\leq j\leq N. \end{aligned}

递归：

\nu_t(j)=\max_{i=1}^{N}\nu_{t-1}(i)a_{ij}b_j(o_t),\qquad 1\leq j\leq N,\ 1<t\leq T

bt_t(j)=\arg\max_{i=1}^{N}\nu_{t-1}(i)a_{ij}b_j(o_t),\qquad 1\leq j\leq N,\ 1<t\leq T

终止：最佳分数为

P^*=\max_{i=1}^{N}\nu_T(i)

回溯起点为：

q_T^*=\arg\max_{i=1}^{N}\nu_T(i)