知识卡片
Viterbi算法的部分最优路径
Viterbi 算法不像前向算法那样对前驱求和,而是只取使概率最大的那一条路径。定义 δ(i,t) 为所有序列中在时刻 t 以状态 i 终止的最大概率,其对应的路径称部分最优路径;δ(i,t) 对每个 i、t 都存在。递推时,t 时刻取 max:δ(i,t)=max_j[δ(j,t−1)·a_ji]·b_i(ot),即从前一时刻各状态中挑出转移到 i 概率最大的一个,再乘当前观测的发射概率。雨天例子第三天 δ(雨天,3)=0.01107421875 为最大。记录每一步的最大前驱,到末态取全局最大 δ 后沿前驱回溯,就得到整条最优路径,无需枚举所有路径。
结构图:
flowchart TD
A[δ(i,1)=πi·b_i(o1)] --> B[对t≥2:δ(i,t)=max前δ·转移a·发射b]
B --> C[记录每步最大前驱]
C --> D[末态取最大δ]
D --> E[沿前驱回溯得最优路径]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 概率图模型与词性标注 · 查看原书依据
定义δ(i,t)为所有序列中在t时刻以状态i终止时的最大概率。当然它所对应的那条路径就称为部分最优路径。δ(i,t)对于每个i、t都是存在的。这样我们就可以顺藤摸瓜,在序列的最后一个状态找到整个序列的最优路径。
参考来源
- 位置:《机器学习算法原理与编程实践》第11章 概率图模型与词性标注(源文件:extracted/机器学习算法原理与编程实践/_epub-src/OEBPS/text00037.html)
- 结论依据:原文定义 δ(i,t) 为部分最优路径、给出最大概率递推与回溯最优路径的过程,支撑 Viterbi 递推优于求和的说明。
- 原始内容:定义δ(i,t)为所有序列中在t时刻以状态i终止时的最大概率。当然它所对应的那条路径就称为部分最优路径。δ(i,t)对于每个i、t都是存在的。这样我们就可以顺藤摸瓜,在序列的最后一个状态找到整个序列的最优路径。