神奇算法之句法分析树的生成

句法分析

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

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

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

句法分析树

样子如下：

         -吃(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……。这样一说是不是就理解了？

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

以上的∑、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迭代算法，不断训练数据，并计算每条规则使用次数作为最大似然计算得到概率的估值，这样不断迭代更新概率，最终得出的概率可以认为是符合最大似然估计的精确值。

总结一下

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