An introduction to Inside-Outside Algorithm

  本文主要内容翻译自 JHU 的 Note on the Inside-Outside Algorithm。  

  为了使一个已知的文法具有概率属性,我们需要给每个上下文无关文法的规则一个概率。但是,如何选择这些概率呢?有一种简单的方法,类似于在语言识别中采用的三元模型,根据训练语料训练调整参数,我们也希望根据训练数据对文法规则的概率进行调整。最大似然原理可以帮助我们做这件事情。根据最大似然原理,应该选择那些使训练数据似然最大的规则概率,这是一种可行的方法。这篇文章主要介绍如何利用内向外向算法对上下文无关文法进行参数估计。

  下面用一个具体的例子进行介绍,其中包含一个简单的句子和它的句法分析树。

image

  在上面的句法分析树中,包含了4个 A->BC 形式的上下文无关文法规则,即

S -> N  V

V -> N  P

N -> N  P

P -> PP  N

  另外,还有5个 A->w 形式的词汇规则,即

N -> She

V -> eats

N -> pizza

PP -> without

N -> anchovies

  当然,从纯句法角度,这个句子也存在其他不同的分析结果,其中把单词 anchovies 变成了 hesitation,如下图

image

  现在产生了2个新的上下文无关问方法规则:

V -> V  N  P

N -> hesitation

  在缺乏其他约束条件下,两种分析结果对于每个句子都是合理的。按照句法构成,我们完全可以选择 “pizza without hesitation”的分析结果,尽管从语义角度看这种选择是错误的。概率训练和句法分析的目标之一就是通过统计方法正确区别句子的句法结构。这篇文章以上面的句子和文法来介绍如何实现训练算法。尽管用例文法很简单,但是它完全可以说明该算法的原理。

  假设我们已经给每个上下文无关的文法规则赋予一个概率,表达形式如下

image

  其中要求概率模型的参数非负,并且对于每个非终结符 A 的和为1,即

image

  对我们的文法来说,要求如下:

image

  因此,需要训练的参数只有和名词 N 或者动词 V 有关系的文法规则,而其他规则的概率已经固定为1。

  内向外向算法(inside-outside algorithm)是一种用来重新估计概率上下文无关文法(PCFG)的产生式概率的方法。它从初始设置的参数开始,递归调整参数从而使训练语料的似然增大。

  我们有两个句子:

W1=”She eats pizza without anchovies”

W2=”She eats pizza without hesitation”

  令 T1 和 T2 分别表示前面的两个句法分析树,统计模型赋予这些分析树概率,即

image

  在没有其他约束条件下,每个句子可以有两个句法分析结果。因此,产生如下的分析概率:

image

  对于参数 Φ,训练语料的似然为:

image

  通常,句子 W 的概率为:

image

  上式表示在给定文法下,句子 W 所有可能的分析树的概率和,并且如果训练语料由 W1,W2,…,WN,那么这个语料的似然 L(Φ) 为:

image

  设初始参数为 Φ,内向算法重新估计参数从而获得新的参数 Φ’,使 L(Φ’)>= L(Φ),直到似然接近收敛,训练才停止。在极限条件下,不同的初始参数可能会导致非常大或者非常小的似然,因此,我们说内向外向算法可使训练数据的似然局部最大(locally maximizes)。

  内向外向算法是用来对隐藏模型进行最大似然估计的 EM 算法的一个特例,关于该算法和 EM 算法的关系我们不会具体介绍,只是简单介绍一些更新参数的方法,以及介绍一下如果利用 CYK 算法计算这些更新。对内向外向算法严格数学推导感兴趣的童鞋可以参考 A Derivation of the Inside-Outside Algorithm from the EM Algorithm。

参数更新:

  在这部分中,我们将定义一些表示方法,并且记录参数的更新过程。这个过程非常普通,并且公式看上去有些复杂,下一部分我们将给出如果根据我们简单的文法来计算更新的详细介绍。

  为了记录内向外向算法如何更新这些参数的方便,我们假设这些文法都是符合乔姆斯基范式(Chomsky normal form)。需要注意的是,这里只是一个为了方便描述的假设。在下一部分中,我们会对我们的文法采用内向外向算法来计算更新,我们的简单文法并不是符合乔姆斯基范式的,但是,我们假设我们有一个一般的上下文无关文法 G,其所有的规则要么是 A->B C 形式,其中 A,B,C 都是非终结符,要么是 A->w 的形式,其中 w 是单词。

  假设我们已经对我们的规则概率选择了初始参数 Φ,在给定这些参数和训练语句 W1,W2,…,WN时,估计新参数 Φ’ 的方法如下:

image

  其中:

image

  当规则概率是 Φ 时,cΦ(A->α, Wi ) 是生成句子 Wi 时使用的重写规则 A->α 次数的期望,为了对这些期望做一个公式化表示,需要两个符号。如果从非终结符A开始,并且通过文法中一系列的重写规则,我们能推导一个词串 γ 和非终结符,即

image

  我们称之为 A 推导出 γ,因此,如果可以通过文法对句子 W=W1, W2, …, WN 做句法分析,可以表示为

image

  按照上面引入的符号标记,已知概率文法,那么句子的概率为

image

  在句子 W1, W2, …, WN 中,非终结符 A 产生词串 Wi,…,Wj 所有推导的概率和表示为

image

  于是,我们可以获得文法起始符号 S 推导产生的词串 W1 … Wi-1 A Wj+1 … Wn 的概率,即

image

  其中,α 和 β 分别表示内向概率和外向概率

  现在,我们可以表示计算规则适用次数的期望,对于规则 A->B C ,在句子 W 的推导中使用的规则次数的期望为:

image

  与上式类似,对于词汇规则 A->w ,在句子 W 的推导中使用的规则的期望为:

inside

[……]

阅读全文