分词

对于分词的应用,大多数肯定都见过,例如在使用百度或者谷歌搜索引擎的时候,我们搜索:我是中国人。

一般搜索引擎会把:

我 我是 中国人 我是中国人

相关的内容都搜索出来,这里已经采用了分词的技术,所谓分词就是把一段话合理的拆分成不同的字或者短语,然后进行搜索。

分词领域发展过程中,有很多的分词技术,例如纯粹的按字拆分,或者基于词典的正向反向最大匹配之类的方式。

这些方式都有一个问题就是极度的依赖于字典,字典的丰富程度决定了分词效果的好坏,其次对于未登录的词,处理也不是特别好。

今天要讲的就是使用另一种方法来分词,该方法就是利用隐马尔可夫模型来做中文的分词。

隐马尔可夫

什么是隐马尔可夫?简单来说,隐马模型是一个概率模型,我举个例子:
假设我手里有三个不同的骰子:

  • 第一个骰子是我们平常见的骰子(称这个骰子为D6),6个面,每个面(1,2,3,4,5,6)出现的概率是1/6。
  • 第二个骰子是个四面体(称这个骰子为D4),每个面(1,2,3,4)出现的概率是1/4。
  • 第三个骰子有八个面(称这个骰子为D8),每个面(1,2,3,4,5,6,7,8)出现的概率是1/8。

假设我们开始掷骰子,我们先从三个骰子里挑一个,挑到每一个骰子的概率都是1/3。

然后我们掷骰子,得到一个数字:1,2,3,4,5,6,7,8中的一个。

不停的重复上述过程,我们会得到一串数字,每个数字都是1,2,3,4,5,6,7,8中的一个。

假设最终我们可能得到这么一串数字(掷骰子10次):1 6 3 5 2 7 3 5 2 4。

那么问题来了:请问上面的一串数字的每一个数字,到底是哪一个骰子丢出来的?

隐马模型就是为了计算或者说解决上面的问题,在上面的问题中,假设最终产生的那一串数字:

1
6 3 5 2 7 3 5 2 4

我们称为 可见状态链,然而这个背后还存在另外一层含义,例如前面的提到的,这一串数字可能是如下的骰子列表丢出来的:

1
D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

这个列表叫隐含状态链,也就是我们需要计算的,一般来说HMM中说到的马尔科夫链就是指这个隐含状态链。

在上面的隐含状态链中,每一个隐含状态之间都存在一个转移概率,例如我们有D4 D6 D8三个骰子,当我们第一次用D4丢,第二次用 D6丢,那么这里就有一个转移概率,值得就是从D4 转移到D6的概率。

在隐马模型里面,还有一个概念叫输出概率,什么叫输出概率呢:

六面骰(D6)产生1的输出概率是1/6,产生2,3,4,5,6的概率也都是1/6。
我们同样可以对输出概率进行其他定义。比如,我有一个被赌场动过手脚的六面骰子,掷出来是1的概率更大,是1/2,掷出来是2,3,4,5,6的概率是1/10,这个就是输出概率。

根据丢骰子这个例子,总结下隐马模型可以用来解决如下三类问题:

  • 知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道每次掷出来的都是哪种骰子(隐含状态链)。
  • 还是知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道掷出这个结果的概率。
  • 知道骰子有几种(隐含状态数量),不知道每种骰子是什么(转换概率),观测到很多次掷骰子的结果(可见状态链),我想反推出每种骰子是什么(转换概率)。

到这里对于隐马模型的大概概念性的东西就介绍完了,总结下来我们可以得出,一个隐马模型,有五个元素,也俗称五元祖:

  • S:状态集合:即所有可能的状态所组成的集合。
  • O:观察序列:即实际存在的一个状态的有向序列,如状态o1,o2。。。on,注意状态是存在顺序的。
  • A:状态转移分布,即S中各元素中,两两之间转移的概率值。比如当前是s2,下一个状态是s9的转移概率为s2,9(小于1)。
  • B:每种状态出现的概率分布。
  • π:初始的状态分布

使用隐马尔可夫分词

那么接下来开始讲,如何应用HMM来做分词,在前面提到隐马模型可以解决三类问题,对于分词来说,要解决的就是第三类问题,我已经丢了一堆数字,我想知道这堆数字最有可能是哪个骰子列表丢出来的,那么应用在分词上就是:

我有一句话,我想知道这句话最有可能是哪些词语顺序组合起来的。

假设我们提前已经准备好了语料,内容为:

1
2
我 爱 你 程序员。
他们 两个 人 是 半斤八两。

我们的目标就是根据上面的预料训练出一个隐马模型,然后利用这个模型来进行汉字分词。

首先按照隐马模型需要五元组来划分:

  • O是观察序列,本例中,就是:“我、爱、你、程、序、员、他、们、两、个、人、是、半、斤、八、两”这16个字。
  • S由四种状态构成:词头(如“程”),词中(如“序”)、词尾(如“员”)、单字成词(如“爱”、“你”)
  • A即由一个状态转移到另一个状态的概率集合,本例共有8种状态
    i. 单字成词->单字成词,如:a我 单 -> 单 = 1 则说明 “我”后面一定是单字成词
    ii. 单字成词->词头,如:a我 单 -> 头 = 0则说明 “我” 后面一定不是词头,而 a你 单 -> 头 = 1,则说明“你” 后面一定是词头。
    iii. 词头->词中
    iv. 词头->词尾
    i. 词中->词尾
    ii. 词中->词中
    iii. 词尾->词头
    iv. 词尾->单字成词
  • B由各状态的概率分布构成,如:b我 单 = 1(“我”一定单字成词)。
  • π由初始状态的概率构成,此例中为 π我 = 1/2(以“我”开头的概率为1/2),π他=1/2(以“他”开头的概率为1/2)。

我们可以按照程序来计算出如上的五元组,然后利用该五元组进行分词,具体的计算过程就不贴代码了,因为比较简单,就是纯粹的累加后求比率,将计算的结果保存下来,这个数据就是模型,我们依据训练数据训练出的一个HMM模型。

有了这个模型,接下来开始做分词处理,假如有下面一句话:

1
我爱人是程序员

需要对这句话进行分词,因为首字是“我”,所以是“他”的情况被排除。

  • π我=1/2。
  • “我”后面是单字的概率为1,a我单=1(即只能是单字),其它情况的概率为0
  • “爱”后面是单字的概率为1,a爱单=1,其它情况的概率为0
  • “人”后面是单字的概率为1,a人单=1,其它情况的概率为0
  • “是”后面是词头的概率为1,a是头=1,其它情况的概率为0
  • “程”后面是词中的概率为1,a程中=1,其它情况的概率为0
  • “序”后面是词尾的概率为1,a序尾=1,其它情况的概率为0

在上面我们已经得出了一个列表,一般在分词的时候遇到词尾,就可以结束定义为一个分词方法,所以所有分词的可能性是很多的,例如:

  • “我”为开头,“爱”是单字成词,“人”是单字成词,“是”是单字成词,“程”是词头,“序”是词中,“员”是词尾:
    P1= π我b我单a我单单b爱单a爱单单b人单a人单单b是单a是单头b程头a程头中b序中a序中尾b员尾=1/21111111111111=1/2
  • “我”为开头,“爱”是词头,“人”是词尾,“是”是单字成词,“程”是词头,“序”是词中,“员”是词尾:
    P1= π我b我单a我单头b爱头a爱头尾b人尾a人尾单b是单a是单头b程头a程头中b序中a序中尾b员尾=1/21*
  • “我”为开头,“爱”是词头,“人”是词中,“是”是词尾,“程”是词头,“序”是词中,“员”是词尾:
    P1= π我b我单a我单头b爱头a爱头尾b人中a人中尾b是尾a是尾头b程头a程头中b序中a序中尾b员尾=1/21*

可以看出有很多种分词的方法,那么如何选择最优的一种分词呢?从计算的角度来讲,我们选择概率最大的那个就行了,然而实际情况是种类太多的时候根本没有办法去挨个计算它们的概率。

所以这个时候需要使用另外一种技术:动态路径规划,也就是俗称的维特比 算法,用来寻找最优的,概率最大的路径。

好,到这里利用隐马模型进行分词的介绍就完成了。


扫码手机观看或分享: