深度学习

发布日期: 2018-04-19

作者: 韦阳

文章字数: 663

阅读时长: 2 分

阅读次数:

关注公众号【算法码上来】，每日算法干货马上就来！

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

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

$\alpha (A,i,j)$定义为内部的potential之和，即以$A$为根结点，短语为${x_{i;j}}$的所有可能的子树的potential之和。
$\beta (A,i,j)$定义为外部的potential之和，即以$A$为根结点，短语为${x_{1;i - 1}}A{x_{j + 1;n}}$的所有可能的子结构的potential之和。

给定文法CFG，输入字符串${x_{1;n}}$，计算inside和outside值。

inside

初始化：
如果$A \to {x_i} \in R$，那么$\alpha (A,i,i) = \varphi (A \to {x_i},i,i,i)$。否则就等于0。
其中$\varphi (A \to {x_i},i,i,i)$为potential值。

类似于CKY算法，自底向上计算inside值：
<!–swig10–>

outside

初始化：

$\beta (S,1,n) = 1$，其余都等于0。

outside值要分为两部分计算：

第一部分是${B \to AC}$，如上图所示。

第二部分是${B \to CA}$，如上图所示。

和inside相反，通过自顶向下计算outside值：
<!–swig14–>

应用

所有可能的句法树potential之和为：
<!–swig15–>
包含产生式$(A \to BC,i,k,j)$的所有可能句法树potential之和是：
<!–swig17–>
存在非终结符$A$，且短语是${x_{i;j}}$的所有可能句法树potential之和是：
<!–swig20–>

PCFG参数估计

参数估计的目的就是为了估计出PCFG的概率$P$，使得所有句子的概率之和最大，采用的是EM迭代法。
首先定义：
<!–swig22–>
这里$P(A \to BC)$是随机初始化的，满足归一化条件就行。
对于语料库的每一条句子，可以计算出：
<!–swig24–>
然后算出期望，更新概率，迭代就行了。