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

内向概率:

image

image

  内向算法的过程是自底向上的:

  输入:G=(S, VN, VT, P),字符串 W=w1…wn

  输出:P(w1…wn | G)= βS (1, n)

  1) 初始化:βA (i, i) =P(A -> wi),A∈VN,1 ≤ i ≤n

  2) 递归计算:j 从1到 n,i 从1到 n-j,重复下面的计算

  3) 结束:P(S -> w1…wn | G) = βs (1, n)

外向概率:

image

image

  规则 A->B C 使用次数的数学期望是给定语句条件下,A,B, C 这三个非终结符同时出现的概率。

image

  规则 A->BC 的概率:

image

  而一个词汇规则出现次数的数学期望为:

image

  规则 A->Wi 出现次数的概率:

image

  下面,总结一下内向外向算法的步骤。

  1) 设置初始参数 Φ 并且另所有的规则出现次数 Count(A->α) 为0;

  2) 对训练语料中的每个句子 Wi,计算内向概率 α 和外向概率 β;

  3) 计算在句子 Wi 中的规则 A->α 次数的期望,即 CΦ(A->α, Wi),对于个每个规则 A->α,添加 CΦ(A->α, Wi) 到 Count(A->α),继续处理下一句;

  4) 按上述方法处理每个句子后,重新估计参数

image

  5) 不断的重复上述过程,并设 Φ=Φ’,并利用新的参数计算期望。

  那么如何结束这个过程呢?在每次迭代过程中,我们对每个句子可得

image

  于是,我们可以计算语料的对数似然:

image

  内向外向算法可以保证不减小似然值,因此我们可以根据变化值来决定合适停止迭代,例如当变化差值非常小时,便可以结束迭代。对于大规模训练语料来说,一般采用固定的迭代次数来进行内向外向的训练。

内向外向概率的计算

  内向外向算法的计算通常是通过 CYK 算法的帮助实现的,它的处理方法如下:

  1) 我们需要将文法 G 转还为乔姆斯基范式的形式,在我们的用例文法中,只有一个需要转换的规则 V->V N P,我们需要将其分解成两个规则 N-P->N P 和 V->V N-P,其中引入了一个新的非终结符 N-P,需要注意的是,由于只有一个 N-P 规则,参数 Φ(N-P->N P) 固定为1,因此

image

  上式就是对 Φ(V->V N P) 的参数估计。现在,我们开始对第一个训练语句进行 CYK 分析,填充 CYK 线图,如下:

image

  CYK 算法按照下图的顺序填充每一个格子。

image

  第一步是填充最外侧的斜线覆盖的格子,每个格子填充其对应的单词所关联的非终结符,然后,对于这些非终结符的内向概率 α 可以得到初始化,于是我们得到

image

  并且,我们已经获得了内向概率,即

image

  而其余的内向概率为0。

  在上面的 CYK 线图中,每个格子之包含一个非终结符,然而,实际中一个格子可以包含多个非终结符,那么对每个非终结符的内向概率需要进行更新。例如,假设用单词 “mushrooms”代替单词 ”anchovies” ,由于 “mushrooms” 可以是名词也可以是动词,于是线图最底部的格子如下图:

image

  在这种情况下,我们应该计算内向概率:

image

  一般来讲,填充格子(i, j)的规则的非终结符应该生成词串 Wi … Wj,线图中格子的序号如下图所示:

image

  在上图中,阴影的格子的序号标记为 (2, 4),覆盖词串 W2W3W4

  还回到前面的例子中,我们继续填充下一个斜线包含的格子并更新相应的内向概率,即

image

  其内向概率为

image

  当最后完成线图填充时,我们将得到

image

  其中,内向概率:

image

  上面最后的内向概率则是整个句子的完整概率:

image

  到此已经完成了内向外向算法的内向过程,现在处理外向过程,其处理过程是与内向过程的线图填充顺序相反的。

  首先初始外向概率 β,令 β15(S)=1,而其他所有的外向概率为0,即

image

  外向概率的计算过程是自顶向下的,处理的步骤和内向过程采用的是一样的。对于一个给定的规则,通过父亲节点的外向概率和其邻接非终结符的内向概率来更新每个孩子节点的外向概率。

  现在,我们已经具备了计算规则使用次数的所有必须成分,下面给出一个计算例子:

image

  由于 β23(V)=0,则

  我们继续计算下一个句子 “She eats pizza without hesitation”,对这个句子,计算过程与前面的是一样的,只是除了涉及 φ(N->anchovies) 的内向概率的计算由 φ(N->hesitation) 代替。当我们完成更新这个句子的规则适用次数时,重新计算整体的概率,例如

image

  内向外向算法和 HMM 中使用的前向后想算法本质思想是一致的,其计算过程也是相同的,可以从参考隐马尔可夫模型攻略。至此,内向外向算法全部介绍完毕,在翻译和自己的理解过程中存在很多不妥之处,请各位看官不吝指教。

发表评论

电子邮件地址不会被公开。 必填项已用*标注