The Inside-Outside Algorithm

上篇文章中介绍了一种 parsing 算法 CYK,这篇文章要介绍的 inside-outside 是另一个 parsing 算法。

算法输入

  • 一句话
  • 满足 CNF 的 CFG
  • potential function

什么是 potential function?

对于一个规则 ,使用 代表这个规则的 potential,在这里也就是概率:

因此对于一个 parse tree t ,它的概率为 .

算法输出

表示所有可能的 parse tree 的概率和

对于所有规则 , 定义

也就是所有包括规则 的 parse tree 概率和

以及对于

也就是所有parse tree 中,以 为根节点,叶节点扩散到 这些单词的子树的概率和

我们使用 分别代表 inside 和 outside 算法。

Inside

inside 算法实际上就是把 CYK 中对所有 parse tree 取最大概率的操作换成了求和

以这个 parse tree 为例:

它关于 的 inside tree 就是

同样地,outside tree

这个 outside tree 根节点是 ,叶节点是

易知

Outside

由上述定义知,对于一个 outside tree ,它的 potential 为 ,也就是这个 tree 里所有规则的乘积。

我们使用符号 来代表所有可能的 outside tree 的集合(以 为根节点,扩散到 之间的所有单词),那么

也就是说, 是所有 中 potential 的和。

根据上述定义推出一些性质:

Inside-outside 算法的全部过程如图:

PCFG 中的 EM 算法

掷硬币中的 EM 算法中我们介绍了 EM 算法,EM 算法在 PCFG 中起着非常重要的作用,它的实质是参数的更新。

算法的输入有 个训练样本(n 句话),例如 代表第 个样本中的第一个单词。

为第 轮迭代时所有可能的 parse tree, 为规则 的参数(概率),

初始 可以设为随机值,然后算出 直到收敛。

的更新过程如下,首先需要算出在 次迭代时 下的 expected counts ,那么 就能求得:

那么如何计算 呢?

Expected Counts

为规则 出现在 中的次数, 是代表所有规则概率的 vector,那么有

第一个求和代表所有的训练样本,对于每个训练样本,再求和所有可能的 parse tree。对于每个 parse tree,将条件概率与 count 二者相乘。

因此对于单个训练样本,

可以使用 inside-outside 算法计算 ,如图:

References

Buy me a coffee
Zhao Li /
Published under (CC) BY-NC-SA in categories NLP  tagged with parsing