场景
把一句话按照句法逻辑组织成一棵树，由人来做这件事是可行的，但是由机器来实现是不可思议的，然而算法世界就是这么神奇，把一个十分复杂的过程抽象成仅仅几步操作，甚至不足10行代码，就能让机器完成需要耗费人脑几十亿脑细胞的工作，本文我们来见识一下神奇的句法分析树生成算法
句法分析
先来解释一下句法分析。
句法分析分为句法结构分析和依存关系分析。
句法结构分析也就是短语结构分析，比如提取出句子中的名词短语、动词短语等，最关键的是人可以通过经验来判断的短语结构，那么怎么由机器来判断呢？
句法分析树
样子如下：
-吃(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迭代算法，不断训练数据，并计算每条规则使用次数作为最大似然计算得到概率的估值，这样不断迭代更新概率，最终得出的概率可以认为是符合最大似然估计的精确值。
TODO: 详细实现
参考资料
更多学习
更多实时资讯，前沿技术，生活趣事。尽在【老马啸西风】
交流社群：[交流群信息](https://mp.weixin.qq.com/s/rkSvXxiiLGjl3S-ZOZCr0Q)
