维特比算法

动态规划

这是个递归问题
递归思想就是：把问题分解成规模更小，但和原问题有着相同解法的问题。
但是递归低效
递归：1-T的最优，依赖2-T最优,…依赖T-1到T的最优。但是T-1到T的最优是无法

要解决的问题

top1路径：很简单，所有候选到当前帧的cost，M*N的矩阵。
topN路径: 不仅仅考虑跳到当前点的最有路径，全局保留。存在的问题是有些点被剪掉了。可以考虑

HMM 示例

模型

全连接 - 指数级 - 朴素递归法

重复计算子问题

<script src=https://www.gstatic.com/charts/loader.js>

复杂度 $ O(N^{T}) $

这里N=3，T=3。

注意

• 总路径数：$ N^{T}=3^{3}=9 $
• 边的数目：$ N \times N \times T=3 \times 3 \times 3=9 $

维特比算法只是对边进行了复用。

最优路径 - 维特比算法

<script src=https://www.gstatic.com/charts/loader.js>

全局最优：line0
贪心算法会找到 line1

维特比是少计算了？剪枝了？还是并未少计算，只是复用了前面的计算结果。

维特比并未少计算，只是去除了冗余计算量而已。

例如路径 1 7 10

k-best 维特比

通常的维特比算法，如果要取top-k最优路径，那么只能在最后一层取topk，前面默认只缓存top-1。

这样导致所取的top-k并非全局最优top-k。

剪枝算法

top1问题

维特比算法复杂度是 NNT

T上不能缩减，我们只能在N上做手脚。

1. 时间点t，只取top N
2. 累积路径，只取
3. 路径总数上限

topK问题

为了和N区分，这里采用topM。

通常的做法：

剪枝的做法：

FAQ

beam

beam=4指的是n还是似然值。还是当前点的路径数目，剪纸。
当前帧剪纸，比如top 15. log似然当前最优是100，100-12.

平滑

有些转移概率为0的，是否需要平滑？

看具体情况。有些状态根本调不到下一个状态。音素上的跳转概率并没平滑。

每帧出top 60，那么就是60^N的路径，但是有top_thresho.

lattice free

什么鬼？

lattice freee是和传统的鉴别训练区分。latice 网格，传统只给top1。
鉴别性，音素错误率，等准则在训练中要体现。全局性的错误率，softmax只提供了单帧错误率。