分词技术中基于统计的分词方法（维特比算法）

本文主要对分词技术中的统计分词方法进行深入探讨。 首先介绍了什么是统计分词以及一般步骤，然后介绍语言模型，最后介绍常见的统计算法（维特比算法）并实现。 分词统计算法。 以下是文章的结构。 这篇文章的内容充满了有用的信息：（阅读整篇文章大约需要20分钟）

内容概述 统计分词

1.统计分词方法

统计分词算法的主要核心是单词是稳定的组合，因此在上下文中，相邻单词同时出现的次数越多，它们组成单词的可能性就越大。 因此，相邻词的概率或频率可以更好地反映该词的可信度。 可以统计训练文本中相邻单词的组合频率，并计算它们之间的相互出现信息。 互现信息反映了汉字之间组合关系的紧密程度。 当紧密度高于某个阈值时，可以认为该词组可以构成一个词。 这种方法也称为无字典分词。

2. 步骤

1.需要建立语言模型

2、将句子进行分词，利用统计方法计算划分结果的概率，得到概率最高的分词方法。 （统计方法如隐马尔可夫模型HMM、条件随机场CRF）

统计语言模型

1. 概念

自然语言处理专家 教授表示：一个句子是否合理取决于它的可能性。 统计语言模型（Model）是用来描述单词、句子甚至整个文档等不同语法单元的概率分布的模型。 它可以用来衡量某个句子或词序列是否符合人们在语言环境中的日常书写。 说话方式。

一个好的统计语言模型依赖于大量的训练数据。 在 20 世纪 70 年代和 80 年代，模型的性能基本上取决于该领域数据的丰富程度。 IBM曾经进行过一次信息检索评估，发现二元模型（Bi-gram）需要数亿个单词才能达到最佳性能，而三元模型（Bi-gram）则需要数十亿个单词才能达到饱和。 。

本世纪初，最流行的统计语言模型无疑是N-gram，它是一种典型的基于稀疏表示的语言模型（ ）； 近年来，随着深度学习的爆发和兴起，以词向量（Word）为代表的分布（ ）为代表的语言模型取得了较好的效果，并深刻影响了自然语言领域其他模型和应用的变革加工。

此外，[7]还提到了基于决策树（Tree）的语言模型、最大熵模型、自适应语言模型（）。

语言模型

2.N-gram语言模型

假设S表示一个有意义的句子，由一系列按特定顺序排列的w1，w2...wn组成，n是句子的长度。 我们想知道S在文本中出现的可能性，也就是S的概率P(S)。如果可以的话，你可以统计历史上人类说过的所有单词，你就会知道这句话出现的概率。 但这种方法并不可行，所以需要一个模型来估计。

标记

展开 P(S) 我们得到：

P(S)=P(w1,w2...wn)

根据条件概率公式：

P(w1,w2...wn)=P(w1)·P(w2|w1)·P(w3|w1,w2)···P(wn|w1,w1...wn-1)

其中 P(w1) 表示第一个单词 w1 出现的概率，P(w2|w1) 是给定第一个单词时第二个单词出现的概率。 单词 wn 出现的概率取决于它之前的所有单词。

计算上，第一个单词的概率 P(w1) 很容易计算，但逐渐估计最后一个单词 P(wn|w1,w1...wn-1) 就太困难了。 这里要介绍一位俄罗斯数学家马尔可夫（），他提出任何单词wi出现的概率只与它前面的单词wi-1有关。 这种假设称为马尔可夫假设。

P(S)=P(w1)·P(w2|w1)·P(w3|w2)·P(wi|w-1)·P(wn|wn-1)

这个统计语言模型是一个二元模型（Model）。

我们来详细分析一下如何得到P(S)：

P(wi|wi-1)=P(wi-1,wi)/P(wi-1)

其中，估计联合概率P(wi-1,wi)和边际概率P(wi-1,wi)，

有了语料，我们只要统计wi-1和wi在文本中相邻出现了多少次，c(wi-1,wi)，

统计 wi-1 在同一文本 c(wi-1) 中出现的次数，然后除以语料库大小 c，计算相对频率：

f(wi-1,wi)=c(wi-1,wi)/c

f(wi-1)=c(wi-1)/c

根据大数定理，只要数据量足够大，相对频率就等于概率，因此：

P(wi-1,wi)≈c(wi-1,wi)/c

P(wi-1)≈c(wi-1)/c

得到：

P(wi|wi-1)=c(wi-1,wi)/c(wi-1)

前面提到的单词只与前面的单词相关，形成二元模型； 但在现实生活中，某个单词的出现可能与之前的几个单词有关。 因此，假设文本中的每个单词wi都与前面的N-1个单词相关：

P(wi|w1,w2...wi-1)=P(wi|wi-N+1,wi-N+2...wi-1)

这种假设称为N-1阶马尔可夫假设，语言模型称为N-Gram模型。 实践中，最常用的三元模型是N=3三元模型； 一般情况下N的值比较小。 ，因为N的值越大，需要的计算能力就越大。

代码

下面是基于词典的分词方法的实现。 利用语言模型，在P(S) P(w1)·P(w2)·P(w3)··P(wi)·P(wn)的计算过程中，如果存在某个P(wi )=0，则P(S)=0，计算结果会与实际情况有所偏差。因此，在计算P(w1)·P(w2)·P(w3)··P(wi)·P( wn), 则变换为

-(logP(w1)+logP(w2)+logP(w3)···logP(wi)+logP(wn))

那么概率很小的单词不会导致P(S)为0

4其他语言模型

其他语言模型包括：神经网络语言模型（如）、循环神经网络语言模型、基于决策树的语言模型、最大熵模型和自适应语言模型等。

HMM 和维特比算法

1.隐马尔可夫模型

隐马尔可夫模型（Model，HMM）是一种关于时间序列的统计模型和概率模型。 它描述了由包含未知参数的马尔可夫链生成不可观测的随机状态序列并生成可观测的随机序列的过程。 。 （这里就不进行HMM的讲解了，马尔可夫链等会在另一篇文章中详细讲解）如果对HMM不太清楚，可以先研究一下这篇文章：掌握马尔可夫链和隐马尔可夫模型文章。

2.维特比算法

维特比算法 ( ) 是一种动态规划算法。 维特比算法由 ( ) 于 1967 年提出，用于反卷积以消除数字通信链路中的噪声。 该算法广泛应用于 CDMA 和 GSM 数字蜂窝网络、拨号调制解调器、卫星、深空通信和 802.11 无线网络中的反卷积码。 如今，它也常用于语音识别、关键词识别、计算语言学和生物信息学。 例如，在语音（语音识别）中，声音信号被视为观察到的事件序列，而文本字符串被视为声音信号的隐含原因。 因此，可以将维特比算法应用于声音信号来找到最有可能的文本字符串。

3.维特比算法解决HMM问题

维特比算法用于解决HMM三大问题中的解码问题（给定一个模型和一个观察序列，如何找到与这个观察序列最匹配的状态序列）。 问题描述如下：首先，我们已经知道状态序列X会产生观察序列O：

HMM隐藏状态序列和可观察序列

然而，状态序列X生成的观测序列有多种可能性，每种可能性都有一个概率，如下所示。 例如，wo可能有三种可能性：哦，我，wo

转移概率

那么这个问题实际上就变成了一个最大概率问题。 最大概率理解为最短路径，转化为最短路径问题：（为了标注方便，用下图中的字母标注）

用字母标记

算法求解：接下来使用维特比算法求解最短路径。 它本质上是一种将大问题分解为小问题的动态规划：第一步，A->B：

图A到B

步骤 2. A->B->C：GIF：

动画A到C

图片拆解：

插图 A 到 C

步骤3.A->B->C->D：

GIF：（可以确定3条最短路径A->C）

动画A到D

图片拆解：

图表 A 至 D

步骤4.A->B->C->D->E：

GIF：（可以确定2条最短路径A->D）

动画A到E

图片拆解：

插图 A 到 E

最终得到最短路径A->E，A->B1->C2->D2->E1。 至此，找到“我爱中国”对应概率最高的汉字组合：我爱中国。

结果

4.维特比算法和分词

使用维特比算法进行分词与使用最短路径算法进行分词类似，也是最短路径方法的分词：

如下，假设每个点之间的权重为1：

维特比算法的流程为：

因此，最短路径为1->6->8->9->11，分词结果为[计算语言学、课程、有、意义]

5. 代码实现

以下是基于语言模型和维特比算法的分词的代码实现：