首页 资讯 社群 我的社区 搜索

Viterbi(维特比)算法在CRF(条件随机场)中是如何起作用的?

yimo~
2019-11-27 14:51:11

通过阅读本文你将能回答如下问题:

  • 什么是维特比算法?
  • 为什么说维特比算法是一种动态规划算法?
  • 维特比算法具体怎么实现?

首先,让我们简单回顾一下BERT和CRF在命名实体识别中各自的作用:
命名实体识别中,BERT负责学习输入句子中每个字和符号到对应的实体标签的规律,而CRF负责学习相邻实体标签之间的转移规则。详情可以参考这篇文章CRF在命名实体识别中是如何起作用的?。该文章中我们对CRF做了简单易懂的介绍,其中提到CRF的损失函数计算要用到最优路径,因为CRF的损失函数是求最优路径的概率占所有路径概率和的比例,而我们的目标是最大化这个比例。那么这里就涉及到计算最优路径的问题。这里的路径在命名实体识别的例子中,就是最终输出的与句子中的字或符号一 一对应的标签序列。不同标签序列的顺序组成了不同的路径。而CRF就是要找出最正确的那条标签序列路径,也就是说这条标签路径的概率将是所有路径中最大的,那么我们可以穷举出所有可能的标签路径,计算出每条路径的概率和,然后比较出最大的那条,但是这样做的代价太大了,所以crf选择了一种称为维特比的算法来求解此类问题。

维特比算法(英语:Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径。

看看下面这个命名实体识别的例子:

上图共有5层(观测序列的长度),每层3个节点(状态的个数),我们的目标就是找到从第一层到第五层的最优路径。
首先,我们分别计算红、黄、蓝三个节点的输入连线的概率,以红色节点举例,我们先假设红色节点在最优路径上,那么输入到该节点的三条连线中,概率最大的那条一定在最优路径上,同理,我们再分别假设黄色和蓝色节点在最优路径上,我们也能各找到一条概率最大的连线,这样就得到了下面的图:

然后,我们接着刚才的思路继续找后面一层的三条最优的连线:

假设找到的最优连线如下:

然后,接着在后面的层应用这个方法:

此时,看上面最后一张图,我们有了3条候选最优路径,分别是棕色、绿色和紫色,用标签来表达如下:

那么哪条才是最优路径呢?
就是看哪条路径的概率和最大,那条路径就是最优路径。
但是在实际实现的时候,一般会在计算各层的最优候选连线的时候,就记录下前继连线的概率和,并记录下对应的状态节点索引(这里将已经计算出的结果记录下来供后续使用的方式,就是维特比算法被称为动态规划算法的原因),这样到最后一层的时候,最后一层各候选连线中概率最大的,就是在最优路径上的那条连线了,然后从这条连线回溯,找出完整的路径就是最优路径了。

一直在说概率最大的路径,那么这个概率具体指什么呢?
还记得上一篇文章介绍条件随机场(CRF)的时候提到,条件随机场其实是给定了观测序列的马尔可夫随机场,在一阶马尔可夫模型中,定义了以下三个概念:

  • 状态集合Q,对应到上面的例子就是:
    {B-P, I-P, O}
  • 初始状态概率向量Π,对应到上面的例子就是:
    {B-P:0.3, I-P:0.2, O:0.5}
    这里的概率数值是随便假设的,仅为了方便举例说明。
  • 状态转移概率矩阵A:

CRF中给定了观测序列做为先验条件,对应到上面的例子就是:

其中的概率数值同样是随便假设的,为了方便举例。

下图中红色节点的概率(可以看成是一个虚拟的开始节点到该节点的连线的概率)的计算方式如下:
初始状态为B-P的概率Π(B-P) * 该节点的观测概率P(小|B-P)

下图中红色节点的三条连线概率的计算方式如下:
上一层对应节点的概率 * 上层对应节点到该节点的转移概率 * 该节点的观测概率P(明|B-P)

其它层之间的节点连线的概率同理计算可得,然后通过上面介绍的维特比算法过程就可以计算出最优路径了。

用户评论