PCFG中inside和outside算法详解 - WeiYang Bloggodweiyang.com
inside-outside算法是用来预测一棵句法分析树的概率的算法,算法建立在文法是乔姆斯基范式(CFG)的基础之上,CFG的定义见维基百科。一棵句法分析树的potential定义为它包含的产生式的potential乘积,在PCFG中表示概率,在CRF-CFG中表示特征集合的分数。
inside-outside算法需要定义两个变量:
定义为内部的potential之和,即以
为根结点,短语为
的所有可能的子树的potential之和。
定义为外部的potential之和,即以
为根结点,短语为
的所有可能的子结构的potential之和。
给定文法CFG,输入字符串
,计算inside和outside值。
初始化: 如果
,那么
。否则就等于0。 其中
为potential值。
类似于CKY算法,自底向上计算inside值:
初始化:
,其余都等于0。
outside值要分为两部分计算:
第一部分是
,如上图所示。
第二部分是
,如上图所示。
和inside相反,通过自顶向下计算outside值:
所有可能的句法树potential之和为:
包含产生式
的所有可能句法树potential之和是:
存在非终结符
,且短语是
的所有可能句法树potential之和是:
参数估计的目的就是为了估计出PCFG的概率
,使得所有句子的概率之和最大,采用的是EM迭代法。 首先定义:
这里
是随机初始化的,满足归一化条件就行。 对于语料库的每一条句子,可以计算出:
然后算出期望,更新概率,迭代就行了。
首先定义:
其中
为特征函数。 那么我们的目的就是训练特征参数
。 然后定义似然函数为
求偏导为
这里可能有人看不懂,似然函数和偏导是怎么来的呢?下面我详细写一下过程。
似然函数:
所以偏导为:
而
所以偏导就是这么来的。