PCFG中inside和outside算法详解

原文链接：

inside-outside算法是用来预测一棵句法分析树的概率的算法，算法建立在文法是乔姆斯基范式（CFG）的基础之上，CFG的定义见维基百科。一棵句法分析树的potential定义为它包含的产生式的potential乘积，在PCFG中表示概率，在CRF-CFG中表示特征集合的分数。

inside-outside算法需要定义两个变量：

• 定义为内部的potential之和，即以 为根结点，短语为 的所有可能的子树的potential之和。
• 定义为外部的potential之和，即以 为根结点，短语为 的所有可能的子结构的potential之和。

给定文法CFG，输入字符串 ，计算inside和outside值。

inside

初始化：
如果 ，那么 。否则就等于0。
其中 为potential值。

类似于CKY算法，自底向上计算inside值：

outside

初始化：
，其余都等于0。

outside值要分为两部分计算：

第一部分是 ，如上图所示。

第二部分是 ，如上图所示。

和inside相反，通过自顶向下计算outside值：

应用

所有可能的句法树potential之和为：

包含产生式 的所有可能句法树potential之和是：

存在非终结符 ，且短语是 的所有可能句法树potential之和是：

PCFG参数估计

参数估计的目的就是为了估计出PCFG的概率 ，使得所有句子的概率之和最大，采用的是EM迭代法。
首先定义：

这里 是随机初始化的，满足归一化条件就行。
对于语料库的每一条句子，可以计算出：

然后算出期望，更新概率，迭代就行了。

CRF-CFG参数估计

首先定义:

其中 为特征函数。
那么我们的目的就是训练特征参数 。
然后定义似然函数为

求偏导为

这里可能有人看不懂，似然函数和偏导是怎么来的呢？下面我详细写一下过程。

似然函数：

所以偏导为：

而

所以偏导就是这么来的。