商业运营产品智能化系列之二——隐式马尔科夫模型应用

前言

在商业运营产品中，存在着很多线索相关的工作。而线索相关的工作，需要同各式各样的公司名称打交道。例如，在线索判重功能中，需要对“公司名称”的各个部分进行标注，提取之中的各个部分，用于后续各种各样的处理，举例如下，下述公司名可以标注为如下部分：

上述标注，存在两个难点：

1）标注的前提是：正确的分词，如果分词不正确，标注也没有什么意义。

2）相同的一个词，在不同的场景下具有不同的含义，比如“北京理工大学”这个名称，北京就不能当作地域词，否则就无法区分“北京理工大学”和“上海理工大学”了。

在本文中，提出一种基于隐式马尔科夫模型的标注方法，可以同时进行分词和标注。在下文中，首先介绍此算法的理论依据，再引出本文算法，最后是总结与展望。

理论基础

为什么使用隐式马尔科夫模型？主要原因是简单且有效。

隐式马尔科夫模型是一个并不复杂的模型，到目前为止，它一直被认为是解决大多数自然语言处理问题最为快速、有效的方法。

--数学之美

首先，隐式马尔科夫模型是一种基于统计的自然语言处理方法。所谓统计自然语言处理方法，在数学模型上同通信是相通的，看作一个编解码和传输的过程。

怎样根据接收端的观测信号O1、O2、O3，……来推断出发送的的信息S1、S2、S3？只需要找出从所有的源组合中找到最可能产生O1、O2、O3序列的那一个序列。用概率语言描述即：

根据贝叶斯公式：

由于P(o1, o2, o3)是确定的，所以上式等价于：

这个式子可以用隐式马尔可夫模型来估计。

隐式马尔可夫模型有两个假设，可以用来简化上面的式子：

1）假设隐藏的马尔科夫链在任意时刻t的隐含状态只依赖于其前一时刻的隐含状态，与其他时候的隐含状态及可见状态无关，也与时刻t无关。

使用此假设：

2）假设任意时刻的可见状态只依赖于该时刻的马尔科夫链的隐含状态，与其他可见状态无关（独立输出假设）。

所以，

算法描述

本文中的算法，同时完成分词和标注两项工作。首先，介绍一下相关概念：

候选词：即句子中每个可能成为一个词的字序列，比如“北京百度网讯科技有限公司”中，“北”，“北京“，“北京百”，“京百”都是候选词，每个词可以用一个索引表示(a, b]，a为起始的索引，b为结束索引，前开后闭。如“京百”即(0,2]，下图为形象化表示。

标注值：标注值为：地域（A）、主体词（N）、修饰词（C）、结尾词（E）、子分类词（P）、子结尾词（F）。

我们的目的即找到如下序列

找到了上述序列，即完成了分词和标注。本文中的算法，首先通过有向无环图的形式表示所有可能的序列，然后通过维特比算法找出概率最大的路径。

第一步：构建有向无环图

首先给出此图的形象化表述，后文介绍其含义：

上图中每一列为一个“状态”，即处理到句子中的每个字作为一个状态，在后文的维特比算法中，依次处理每个状态。

上图中每一圆圈作为一个“可能值”，是一个二元值：（候选关键词的结束索引，标注值）。

上图中线的含义如下，假设连接了两个端点：左端点为（，A），右端点为（1,N），这条线就表示一个候选关键词（0,1]，标注值为N。通过上述定义，就可以明白：为什么上图中有的圆圈中间没有连线了，因为不能代表一个有效的候选关键字。

最终，我们得到的分词和标注，即上图中的一个路径，假设为：

start ->（2，A）->（5，N）->（9，F）

那么，对应的结果序列为

【（，2], A】，【（2，5], N】，【（5，9], F】，即得到了三个词，标注值分别为A N F。

在下一部分中，将介绍如何计算此路径。

备注：在这一步，为了便于后续计算，需要计算出所有候选词为某一标注的概率（即马尔科夫模型中的发射概率)，如

第二步，使用维特比算法求解

维特比算法是一种动态规划算法，可以寻找上述有向无环图的两点之间的“最短路径”，在我们的场景中，即从头到尾的最大概率的路径。维特比算法的详细描述请参考：

https://baike.baidu.com/item/维特比算法/7765534

使用维特比算法依次处理每个状态（列），针对每个“可能值”（圆圈），计算到达这个圆圈的最大概率。计算的规则举例如下：

假设处理到了m这个节点，如何计算到这个节点的最大概率？可由如下公式求得：

其中：PMAX：即i，j，k三个节点的最大概率，为已知值，在上一个状态计算时已经计算出来。

PTrans(n->m)：即马尔科夫模型中的转移概率，对于i和m两个节点来说，即A标注值到N标注值的转移概率。

PEmit：即边上代表的候选字的发射概率，即上一步计算出来的概率。

由于（1，X）到（，X）是不可能的状态，所以不需要计算，因此本算法的复杂度为：

其中：N为字数，D为类别数。

通过上述算法，在业务中取得了不错的效果。

展望

实现此功能还有其它一些算法，比如CRF（条件随机场），破除了隐式马尔科夫模型的两个假设，将问题feture化，可以定义种类丰富的特征函数，所以隐式马尔科夫模型可以等价于一个CRF模型。CRF功能更加强大，模型也更为复杂，人工设计特征比较困难，随着深度学习研究的发展，可以采用循环神经网络（Recurrent Neural Network，RNN等序列模型能够处理序列元素之间前后关联问题，能够从原始输入文本中学习特征表示，而更加适合序列标注任务（参考paddlepaddle模型库），感兴趣的同学可以尝试一下。

尽管有上述更优化的解决方案，HMM以简单的算法，不错的效果，仍不失一种可以快速解决标注问题的利器。

作者：张志强——一个信奉“须求其所以然”的老程序员，关注于商业运营产品的研发工作。

编辑：徐全刚 胡建华 王岩嵬

欢迎关注我们的微信号：