维特比算法

动态规划

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

要解决的问题

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

HMM 示例

模型

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

重复计算子问题

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

这里N=3,T=3。

注意

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

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

最优路径 - 维特比算法

全局最优: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只提供了单帧错误率。