维特比算法

维特比(Viterbi)算法常见于HMM, CRF等模型的解码过程. 这些模型往往是用来解决序列的在有限状态之间的转移问题, 也就是序列标注问题. 在NLP领域, 对应的任务就类似于实体识别, 词性标注等序列标注问题.

在使用神经网络模型解决这些问题时, 往往会使用到各种解码方法, 让最终得到的标注结果质量更高.

适用任务

• 实体识别

• 词性标注

• 关键词抽取

总之这类任务都有着一些共同点, 以字或词为粒度, 对其进行标注, 但往往更多的以字为粒度进行标注, 因此中文分词的效果会影响词粒度标注的准确性.

另外, 对于每个字(或词), 对其进行标注, 就是对这个字进行一个多分类预测的过程:

• 与普通的多分类有区别的地方是, 普通多分类任务样本之间是没有关系的, 所以分别预测即可. 但序列中字与字之间的类别是有关联的, 所以直接进行多分类得到的结果效果不好, 甚至很多是逻辑错误的. 这也是这种任务需要解码的原因(或者在训练时融入解码, 如BiLSTM+CRF)

• 标注的类别是有限的. 例如实体识别中识别地点, 人名, 机构名等多种实体, 各种标注之间的转移概率矩阵可以在训练之前根据训练语料计算得到.

解码方法

首先以熟悉的HMM中使用维特比进行解码的过程为例. 维特比算法一节中有详细的说明.

简单来说, 我们定义了一个局部概率$\delta$, 这个局部概率表示的是$t$时刻时到达某个状态最可能的路径的概率, 即$\delta_{t}(i)$表示的是$t$时刻到达状态$i$的所有序列概率中最大的概率, 这个最大概率的背后也对应着唯一的此时刻到达此状态的最优路径.

而时间步之间的递推公式, 对$t=2,3,\cdots,T$

$\delta_{t}(i)=\max_{1\leq{j}\leq{N}}[\delta_{t-1}(j)a_{ji}]b_i(o_t), i=1,2,\cdots,N$

这里的$a_{ji}$是标注状态之间的转移概率, $b_i(o_t)$在HMM中的意义当隐藏状态为$i$时, 观测状态为$o_t$的概率. 在神经网络训练的模型当中, 对于每一个时刻, 首先我们没有隐藏和观测两种状态序列; 其次对于每个时间步的标注, 往往是使用softmax得到每个状态的概率, 我们就用这个概率作为当前时刻的概率$b(o_t)$. 注意这里只有$t$时刻的观测$o_t$, 不再有隐藏状态$i$, $j$等等了.

上面只是帮助理解, 公式再这样写肯定就不对了.

然后在序列的最后一个时间步$T$, 我们得到了对应的各个状态局部概率$\delta_{T}(i)$, 选择最优的的概率作为最终的结果:

$P^*=\max_{1\leq{i}\leq{N}}\delta_{T}(i)$

前面已经说过, 每个局部概率都对应着到达此节点的最优路径, 使用反向指针推导回去得到整条序列, 也就是最优的标注序列.

实践

首先我们需要计算一个状态之间的概率转移矩阵存储起来.

然后在计算概率时, 由于是时间的连乘, 随着时间步的增加, 很容易造成结果在精度上的溢出, 这种现象在序列长度很长时很严重.

对此, 在维特比算法的实际操作中, 先用$\log$对概率矩阵和计算得到的此步的标签分类概率进行计算, 然后在维特比算法中, 在计算局部概率时, 就可以转连乘为连加, 因此避免了精度移除的问题, 而且两者是完全等价的.

最后维特比算法在寻找最优路径时, 是先得到最后一个时间步的最优局部概率之后, 再使用反向指针得到的. 在实际操作中, 可以使用key: value的形式, key值为到达当前结点最优路径(状态序列), value值为计算得到的对应的局部概率.

因此整体的实际维特比算法代码如下:

zy = {'00':0.15, 
      '01':0.15, 
      '02':0.7, 
      '10':1.0, 
      '23':0.5, 
      '24':0.5,
      '33':0.5,
      '34':0.5, 
      '40':1.0
     }

zy = {i:np.log(zy[i]) for i in zy.keys()}

这里的zy就是状态转移矩阵, 如果两种状态的转移概率为0, 在zy的key中就不会出现. 概率的数值是根据训练数据估计的. 而且在最后转换为了对数概率.

def viterbi(nodes):
    paths = nodes[0]
    for l in range(1,len(nodes)):
        paths_ = paths.copy()
        paths = {}
        for i in nodes[l].keys():
            nows = {}
            for j in paths_.keys():
                if j[-1]+i in zy.keys():
                    nows[j+i]= paths_[j]+nodes[l][i]+zy[j[-1]+i]
            k = np.argmax(nows.values())
            paths[nows.keys()[k]] = nows.values()[k]
    return paths.keys()[np.argmax(paths.values())]


def predict(i):
    nodes = [dict(zip(['0','1','2','3','4'], k)) for k in np.log(dd['predict'][i][:len(dd['words'][i])])]
    r = viterbi(nodes)
    result = []
    words = dd['words'][i]
    for j in re.finditer('2.*?4|1', r):
        result.append((''.join(words[j.start():j.end()]), np.mean([nodes[k][r[k]] for k in range(j.start(),j.end())])))
    if result:
        result = pd.DataFrame(result)
        return [result[0][result[1].argmax()]]
    else:
        return result

这里的nodes存储了预测得到的序列所有结点的标注概率, 在进入viterbi函数之前, 使用np.log进行了转换, 也转换称为了对数概率.

参考资料

• 基于双向LSTM和迁移学习的seq2seq核心实体识别