SharEDITor

自己动手做聊天机器人 十八-神奇算法之句法分析树的生成

大数据 自己动手做聊天机器人 发表于 2016-07-19 16:46:36 阅读8775次


把一句话按照句法逻辑组织成一棵树,由人来做这件事是可行的,但是由机器来实现是不可思议的,然而算法世界就是这么神奇,把一个十分复杂的过程抽象成仅仅几步操作,甚至不足10行代码,就能让机器完成需要耗费人脑几十亿脑细胞的工作,本文我们来见识一下神奇的句法分析树生成算法

请尊重原创,转载请注明来源网站www.shareditor.com以及原始链接地址

句法分析

先来解释一下句法分析。句法分析分为句法结构分析和依存关系分析。

句法结构分析也就是短语结构分析,比如提取出句子中的名次短语、动词短语等,最关键的是人可以通过经验来判断的短语结构,那么怎么由机器来判断呢?

(有关依存关系分析的内容,具体可以看《自己动手做聊天机器人 十二-教你如何利用强大的中文语言技术平台做依存句法和语义依存分析》)

 

句法分析树

样子如下:

         -吃(v)-

|                      |

我(rr)            肉(n)

 

句法结构分析基本方法

分为基于规则的分析方法和基于统计的分析方法。基于规则的方法存在很多局限性,所以我们采取基于统计的方法,目前最成功的是基于概率上下文无关文法(PCFG)。基于PCFG分析需要有如下几个要素:终结符集合、非终结符集合、规则集。

相对于先叙述理论再举实例的传统讲解方法,我更倾向于先给你展示一个简单的例子,先感受一下计算过程,然后再叙述理论,这样会更有趣。

例子是这样的:我们的终结符集合是:∑={我, 吃, 肉,……},这个集合表示这三个字可以作为句法分析树的叶子节点,当然这个集合里还有很多很多的词

我们的非终结符集合是:N={S, VP, ……},这个集合表示树的非页子节点,也就是连接多个节点表达某种关系的节点,这个集合里也是有很多元素

我们的规则集:R={

NN->我    0.5

Vt->吃     1.0

NN->肉   0.5

VP->Vt NN    1.0

S->NN VP 1.0

……

}

这里的句法规则符号可以参考词性标注,后面一列是模型训练出来的概率值,也就是在一个固定句法规则中NN的位置是“我”的概率是0.5,NN推出“肉”的概率是0.5,0.5+0.5=1,也就是左部相同的概率和一定是1。不知道你是否理解了这个规则的内涵

再换一种方法解释一下,有一种句法规则是:

S——|

|        |

NN    VP

          |——|

          Vt     NN

其中NN的位置可能是“我”,也可能是“肉”,是“我”的概率是0.5,是“肉”的概率是0.5,两个概率和必为1。其中Vt的位置一定是“吃”,也就是概率是1.0……。这样一说是不是就理解了?

 

规则集里实际上还有很多规则,只是列举出会用到的几个

请尊重原创,转载请注明来源网站www.shareditor.com以及原始链接地址

以上的∑、N、R都是经过机器学习训练出来的数据集及概率,具体训练方法下面我们会讲到

 

那么如何根据以上的几个要素来生成句法分析树呢?

(1)“我”

词性是NN,推导概率是0.5,树的路径是“我”

(2)“吃”

词性是Vt,推导概率是1.0,树的路径是“吃”

(3)“肉”

词性是NN,概率是0.5,和Vt组合符合VP规则,推导概率是0.5*1.0*1.0=0.5,树的路径是“吃肉”

NN和VP组合符合S规则,推导概率是0.5*0.5*1.0=0.25,树的路径是“我吃肉”

 

所以最终的树结构是:

S——|

|        |

NN    VP

我      |——|

          Vt     NN

          吃     肉

 

上面的例子是比较简单的,实际的句子会更复杂,但是都是通过这样的动态规划算法完成的

提到动态规划算法,就少不了“选择”的过程,一句话的句法结构树可能有多种,我们只选择概率最大的那一种作为句子的最佳结构,这也是“基于概率”上下文无关文法的名字起源。

 

上面的计算过程总结起来就是:设W={ω1ω2ω3……}表示一个句子,其中的ω表示一个词(word),利用动态规划算法计算非终结符A推导出W中子串ωiωi+1ωi+2……ωj的概率,假设概率为αij(A),那么有如下递归公式:

αij(A)=P(A->ωi)

αij(A)=∑∑P(A->BC)αik(B)α(k+1)j(C)

以上两个式子好好理解一下其实就是上面“我吃肉”的计算过程

 

以上过程理解了之后你一定会问,这里面最关键的的非终结符、终结符以及规则集是怎么得来的,概率又是怎么确定的?下面我们就来说明

 

 

句法规则提取方法与PCFG的概率参数估计

这部分就是机器学习的知识了,有关机器学习可以参考《机器学习教程

首先我们需要大量的树库,也就是训练数据。然后我们把树库中的句法规则提取出来生成我们想要的结构形式,并进行合并、归纳等处理,最终得到上面∑、N、R的样子。其中的概率参数计算方法是这样的:

先给定参数为一个随机初始值,然后采用EM迭代算法,不断训练数据,并计算每条规则使用次数作为最大似然计算得到概率的估值,这样不断迭代更新概率,最终得出的概率可以认为是符合最大似然估计的精确值。

 

总结一下

句法分析树生成算法是基于统计学习的原理,根据大量标注的语料库(树库),通过机器学习算法得出非终结符、终结符、规则集及其概率参数,然后利用动态规划算法生成每一句话的句法分析树,在句法分析树生成过程中如果遇到多种树结构,选择概率最大的那一种作为最佳句子结构