基于动态规划的维特比（Viterbi）算法详解
1. 题目描述
维特比算法是一种动态规划算法，用于寻找最可能的隐藏状态序列。在自然语言处理中，它常用于解决序列标注问题，例如：给定一个观测序列（如句子中的单词序列），找出最可能的隐藏状态序列（如每个单词对应的词性标签）。该算法的核心思想是利用动态规划来高效地计算全局最优路径，避免穷举所有可能路径带来的计算开销。
2. 问题形式化
- 假设有一个隐藏状态集合 \(S = \{s_1, s_2, ..., s_N\}\)（例如词性标签集合）。
- 观测序列为 \(O = \{o_1, o_2, ..., o_T\}\)（例如一个长度为 \(T\) 的句子）。
- 定义两个概率模型：
- 转移概率 \(P(s_j | s_i)\)：从状态 \(s_i\) 转移到 \(s_j\) 的概率。
- 发射概率 \(P(o_t | s_j)\)：在状态 \(s_j\) 下生成观测 \(o_t\) 的概率。
- 目标：找到一条状态序列 \(Q = \{q_1, q_2, ..., q_T\}\)，使得条件概率 \(P(Q | O)\) 最大。
3. 动态规划的核心思想
- 将问题分解为子问题：计算到每个时间步 \(t\) 时，以每个状态 \(s_j\) 结尾的所有路径中的最大概率。
- 定义两个关键变量：
- 概率表 \(\delta_t(j)\)：在时间步 \(t\)，以状态 \(s_j\) 结尾的路径的最大概率。
- 路径回溯表 \(\psi_t(j)\)：记录达到 \(\delta_t(j)\) 时，前一个时间步的状态索引。
- 通过递推公式逐步填充这两个表，最后回溯得到全局最优路径。
4. 算法步骤详解
步骤1：初始化（时间步 \(t=1\)）
- 对于每个状态 \(s_j\)（其中 \(j = 1, 2, ..., N\)）：
- 计算初始概率：
\[ \delta_1(j) = P(s_j) \cdot P(o_1 | s_j) \]
这里 $ P(s_j) $ 是初始状态概率（例如句子的第一个词是标签 $ s_j $ 的概率）。
- 由于没有前驱状态，设置回溯指针为初始值（例如 \(\psi_1(j) = 0\)）。
步骤2：递推（时间步 \(t = 2\) 到 \(T\)）
- 对于每个时间步 \(t\) 和每个状态 \(s_j\)：
- 计算所有可能前驱状态 \(s_i\) 的路径概率：
\[ \delta_t(j) = \max_{1 \leq i \leq N} \left[ \delta_{t-1}(i) \cdot P(s_j | s_i) \right] \cdot P(o_t | s_j) \]
这里先找到从 $ t-1 $ 到 $ t $ 的最优转移路径，再乘以当前观测的发射概率。
- 记录最优前驱状态：
\[ \psi_t(j) = \arg\max_{1 \leq i \leq N} \left[ \delta_{t-1}(i) \cdot P(s_j | s_i) \right] \]
步骤3：终止
- 在最后一个时间步 \(T\)，找到全局最大概率和对应的终止状态：
\[ P^* = \max_{1 \leq j \leq N} \delta_T(j), \quad q_T^* = \arg\max_{1 \leq j \leq N} \delta_T(j) \]
步骤4：路径回溯（从 \(t = T-1\) 到 \(1\)）
- 根据回溯表 \(\psi_t\) 逐步向前追溯最优路径：
\[ q_t^* = \psi_{t+1}(q_{t+1}^*) \]
- 最终得到完整的状态序列 \(Q^* = \{q_1^*, q_2^*, ..., q_T^*\}\).
5. 示例说明
假设任务是对句子“苹果很好吃”进行词性标注，状态集为{名词, 形容词}，观测序列为{苹果, 很, 好吃}：
- 初始化：计算“苹果”作为名词或形容词的初始概率（例如 \(P(名词) \cdot P(苹果|名词)\)）。
- 递推：
- 对于“很”，计算从“苹果”的名词/形容词转移到“很”的名词/形容词的概率，结合发射概率 \(P(很|名词)\) 或 \(P(很|形容词)\)。
- 类似处理“好吃”。
- 回溯：从“好吃”的最优标签回溯到“很”和“苹果”的标签。
6. 算法特点
- 时间复杂度：\(O(T \cdot N^2)\)，远优于穷举的 \(O(N^T)\)。
- 空间复杂度：\(O(T \cdot N)\)，用于存储 \(\delta\) 和 \(\psi\) 表。
- 需预先已知转移概率和发射概率（通常从标注数据中统计或通过模型学习）。
7. 在NLP中的应用
- 隐马尔可夫模型（HMM）的解码器。
- 条件随机场（CRF）等模型中的预测步骤。
- 其他序列标注任务，如命名实体识别、语音识别等。