隐马尔可夫模型在中文文本分词中应用研究

2017-01-10 02:34王庆福
无线互联科技 2016年13期

王庆福

摘要:文本分词是各个互联网领域中的基础性工作。通过对平台涉及的文本串进行切词处理,对切词之后的短文本串更能够聚合用户。隐马尔可夫模型作为机器学习领域中重要算法,它能够进行各个状态之间的转换,对于文本中词语之间上下文语义关系、词语与词语之间前后向位置关系非常匹配,众多的开源分词工具都基于隐马尔可夫模型。

关键词:文本分词;上下文语义;隐马尔可夫模型

文本分词是互联网中各个行业的基础性工作。文本分词最直接的应用场景应该是在搜索引擎中,一方面需要对搜索引擎爬取到的网站内容进行切词分析,另一方面,也需要对用户输入的短文本查询字符串进行切词分析,度量切词之后的用户查询字符串和网站内容之间的相关性。随着推荐系统的越来越广泛应用,尤其以咨询和新闻类的推荐系统为主要形态,都需要大量的文本切词工作。甚至美团等O2O平台也需要对用户的评论信息和地址信息等进行切词分析。

隐马尔可夫模型作为机器学习中重要算法,是在马尔可夫模型的基础上发展而来,但是它与马尔可夫模型又是截然不同的两个模型。它主要用观测数据来预测原始数据形态,能够根据状态节点之间的转换方式来推测最可能的原始数据形态,这正是文本分词所需要的。文本分词通过对文本串的多种切分方式寻找最佳的切分方式作为当前的切词结果,最佳的切分方式通过隐马尔可夫模型预测获得。

1 隐马尔可夫模型

隐马尔科夫模型(Hidden Markov Model)经常被用在时间序列(例如一段时间内的声音信号,运动物体的位置等物理量)的建模与分析。

它有3个要素:(1)可见随机变量。用来描述人们所感兴趣的物理量,随时间变化。(2)隐含的状态变量。一个假设的存在,每个时间点的物理量背后都对应一个状态量。(3)变量间的关系。用概率的方法(通常是概率密度函数)描述以下3个关系或变量:初始状态量,当前的隐含状态量与下一个隐含状态量间关系(此处还用到马尔科夫假设:当前隐含状态只取决于前一个隐含状态),当前的隐含状态量与可见随机量间关系。

隐含状态变量是假设的存在,并不一定有对应的物理解释,此例状态值取上下左右4个值是为了好理解,实现模型时可以取任意数量的状态值,是一个可调参数。隐含状态变量通常是离散的,可见状态变量可离散可连续。

HMM模型中每个节点代表一个状态变量,状态变量产生观测变量,HMM中当前状态只与前一状态有关,与其他时刻状态无关。状态随时间转移,当前观测变量由当前状态决定。HMM模型的目标通常是给出最有可能的结果,不关心其可信度。

马尔可夫独立性假设是指,对一个节点,在给定它所连接的所有节点的前提下,它与外界是独立的。也就是说,如果你观测到了这个节点直接连接的那些节点的值,那它跟那些不直接连接它的点就是独立的。形式上,我们将其设计成这个样子,边可以传递信息,点与点之间通过边相互影响,如果观测到一个节点的取值或者这个节点的取值是常量,那么别的节点就无法通过这个节点来影响其他节点。所以对一个节点来说,如果用来连接外界的所有节点都被锁住了,那它跟外界就无法传递信息,就独立了。一个HMM有两部分,如图1所示。

(1)状态(state)/状态的转移(transition):描述了HMM的基本骨架,即一个HMM有多少个states以及states之间的转移关系。(2)每一个state的概率分布(probabilitydistributions)可再分为两部分,①带有概率的Markov链,即由某一状态去往下一个状态的转移概率;②每一个state的data probability distributions,语音识别中通常用混合高斯模型(Gaussian Mixture Model)来描述。

2 文本分词

众所周知,在汉语中,词与词之间不存在分隔符(英文中,词与词之间用空格分隔,这是天然的分词标记),词本身也缺乏明显的形态标记,因此,中文信息处理的特有问题就是如何将汉语的字串分割为合理的词语序。主流的中文分词方法有3种:第一类是基于语言学知识的规则方法,如各种形态的最大匹配、最少切分方法;第二类是基于大规模语料库的机器学习方法,这是目前应用比较广泛、效果较好的解决方案,用到的统计模型有N元语言模型、信道一噪声模型、最大期望、HMM等;第三类也是实际的分词系统中用到的,即规则与统计等多类方法的综合。

对于一条完整的句子并不能得到可观测的序列。采用统计语言模型的中文分词,效果已经非常好,可以认为中文分词是一个已经解决了的问题。不过,这又需要训练一个新的马尔可夫模型。因此,通常从左往右扫描句子,然后查找词库,找到最长的词匹配,遇到不认识的字串就分割成单字词。

将词库中的词语按照unicode码排序,可以方便地查找。在分词时,首先将词库读到内存中,然后将句子按照从左往右最长匹配原则查找词库。由于词库按照unicode码排序,所以我们可以采用二分快速查找词组。查找时,首先读取原始句子的第一个字,定位到该字在词库中的起始位置和结束位置,然后进行二分查找即可。在查找的过程中记录起始和结束位置之间所有词的最大长度,然后从最大长度开始查找词库,长度逐一递减,直到找到为止。图2简单描述了分词的过程。

HMM需要训练的参数有3个,即(PI,A,B)。PI表示词性的先验概率,A表示词性之间的状态转移矩阵,B表示词性到词的发射矩阵或者混淆矩阵。采用有监督的方式训练上述3个参数。有监督的方式,即通过统计语料库中的相关信息训练参数。HMM参数训练就是通过分析语料库获得HMM的3个参数。通过解析语料库可以获得:每个词性出现的次数,每个词性及其后继词性出现的次数和词性对应的词。统计完这些信息之后就可以以频率代替概率获得3个参数的值。

获得上述信息之后,可以很容易地统计相关信息,进而利用频率算概率。词性先验概率的计算没有任何难度。隐藏状态转移矩阵按照公式1所示。(1)

在公式1中,#(St-1-St)表示不同的两个词性前后出现的次数,St-1表示词性出现的次数。可观测状态的发射矩阵按照公式2所示。(2)

在公式2中,#(Ot,St)表示某个词和某个词性同时出现的次数。在计算频率的时候,由于有些值非常小,为了避免计算过程中的下溢,可以统一将计算的结果乘以一个较大的数。事实上,对于频数为零或者频数很小的情况,按照古德一图灵估计重新计算,之后求最优隐藏序列需要采用log方式。假设通过分析语料库,最后获得了N个词性,M个词组,则就是一个长度为N的向量,A是一个N×N的句子,B就是一个NXM的矩阵。后面对句子进行词性标注时,要确保分词后的词组都在M中,否则就超出了HMM的处理能力。

一般情况下,完成HMM参数训练之后,可以利用HMM完成一些具体的事情。不过,在这之前对于词性标注系统,还需要进一步分词。采用的分词方法是从左往右,最大匹配模式。但是程序中采用的语料库却倾向于最小匹配模式。所以初次分词的结果有可能不在语料库中。在此将语料库不能识别的词组再次进行分词尝试让算法找到更多的词。

3 结语

文章主要论述隐马尔可夫模型的实际应用场景,分析隐马尔可夫模型的理论基础。隐马尔可夫模型主要通过预测值和观察值之间的状态变化矩阵进行数据预测。语音识别、文本分词等多个领域都涉及隐马尔可夫模型的应用,文章选取了在文本分词中应用展开论述。