Viterbi算法解码过程

https://zhuanlan.zhihu.com/p/63087935

[图片上传失败...(image-a8906b-1587025432526)]

<figcaption style="margin-top: 0.66667em; padding: 0px 1em; font-size: 0.9em; line-height: 1.5; text-align: center; color: rgb(153, 153, 153);">开局一张图，内容全靠编</figcaption>

image

维特比算法作为HMM，CRF中的经典解码算法。

本文试图用简单的例子+图片来帮助理解该算法。

任务／问题是什么？

给定观察序列 [图片上传失败...(image-b17bc5-1587025432527)]

，每个观察点对应一个标注(或称为state) [图片上传失败...(image-676d8c-1587025432527)]

。

我们的任务是解码（decode）x 每个点上所对应的 y 是 y1 , y2 ,还是 y3。

如何解决？

naive：算出每种情况的概率，再取最大值;

[图片上传失败...(image-5538f6-1587025432527)]

复杂度为 [图片上传失败...(image-626996-1587025432527)]

，太大了。L为label(或称为state)的个数，N为输入的长度。我们需要维特比算法来简化。

为什么需要维特比算法？

维特比算法通过DP（动态规划）思想，在每个时间点+每个label上储存到该位置的最大概率。复杂度简化为： [图片上传失败...(image-7a1f8e-1587025432527)]

维特比算法需要什么？

假设我们已经有Transition matrix和Emission matrix

Transition matrix: [图片上传失败...(image-6be6eb-1587025432526)]

, e.g., [图片上传失败...(image-72c382-1587025432526)]

Emission matrix: [图片上传失败...(image-e4f474-1587025432526)]

, e.g., [图片上传失败...(image-aa4c73-1587025432526)]

外加初始每个state的概率 = [图片上传失败...(image-66da6e-1587025432526)]

image

T1: 用来保存每个时间点上，到每个state的最大概率； [图片上传失败...(image-44068c-1587025432526)]

T2:用来保存这个最大概率是从上一个时间点的哪个state过来的；

[图片上传失败...(image-514cd3-1587025432526)]

image

初始化：初始概率 x 发射概率

image

初始化完成

image

从时间点1到时间点2，

从上一时间点A 到 当前时间点A的概率乘以A观测到2的概率：[图片上传失败...(image-1211c4-1587025432526)]

image

同理从B到A

image

同理从C到A

image

求得最大值并保存到T1，T2

image

同理求A到B

image

同理求B到B

image

同理求C到B

image

求得最大值并保存

image

同理求得A，B，C到C

image

求得最大值并保存

image

同理求得时间点2到时间点3，ABC到A的最大值并保存。

image

同理求的ABC到B，最大值并保存。

image

同理求的ABC到C的最大值并保存。

image

在最后时间点上，求argmax可得A为最大，放入解码path中。

image

通过T2可得A是从C过来的，将C放入解码path中。

image

通过T2可得，C是从A过来的，将A放入解码path中。最后反转可得最终解码path为[A,C,A]。

image

点个赞把～