理解Duckling中的PCFG

Duckling的描述信息中有这么一段

If you know NLP, Duckling is “almost” a Probabilistic Context Free Grammar. But not exactly! It tries to be more flexible and easier to configure than a formal PCFG. It also tries to learn better from examples.

PCFG不难理解，组合式的规则定义加上概率选择，那么这就是一个PCFG。

理解PCFG可以从Collins的课程入手，

• YouTube搬运: Week 3 - Parsing and Context-Free Grammars¹ & Probabilistic Context-Free Grammars²
• B站搬运: Natural Language Processing, by Michael Collins, Columbia University³
• 课程：Notes on Probabilistic Context-Free Grammars⁴

但是Duckling中的求解并没有使用CYK（代码中的注释如下）：

-- Probabilistic layer
--   Naive Bayes classifier with Laplace smoothing
--   Train one classifier per rule, based on the test corpus.

• 如何理解CYK求解变成了Naive Bayes
• Laplace smoothing又是什么？

1. CYK & Naive Bayes

Duckling中为什么学习方法用Naive Bayes就够了？这是因为在Duckling中的现有规则中没有循环定义的规则（或者说能够产生无限长度结果的规则）。在这个条件下NB足够用来求解，而在循环规则存在的情况下，长规则链的概率一定会更低，这个时候就没法正确求解了。

2. PCFG

定义：一个推导（或者说组合）规则，推导在Duckling中就对应一条rule
$$\text{rule}:\alpha \to \beta$$
定义：推导树的概率
$$\prod _i{\text{rule}}_i=\prod _i({\alpha }_i\to {\beta }_i)=\prod _i\frac{count({\text{rule}}_i)}{{\sum }_{j}count({\text{rule}}_j)}$$

3. Laplace Smoothing

Collins的PCFG讲义中并未提到这个，但是结合Week1中介绍的Discounting Methods⁵的平滑方法也可以强行理解一把。

样本中未出现的推导的概率之和为0，为了让未出现的也能参与推导，定义：未出现的推导的概率之和
$$\frac{|\text{rule}|}{{\sum }_{j}count({\text{rule}}_j)+|\text{rule}|}$$
则每一条未出现的推导的概率：
$$(\alpha \to {\beta }_{\text{unseen}})=\frac{1}{{\sum }_{j}count({\text{rule}}_j)+|\text{rule}|}$$
调整后的样本中出现的推导概率：
$$(\alpha \to {\beta }_i)=\frac{count({\text{rule}}_i)+1}{{\sum }_{j}count({\text{rule}}_j)+|\text{rule}|}$$
可以验证概率之和还是1。

Duckling的代码中未出现推导的概率的分母额外加了个1.0，不太清楚设计目的

最后再加上规则的正负例的比例的先验概率，就能够完整的理解Train和Rank部分的代码了。至于为什么叫Laplace Sooothing，不知道?。

3. 思考

Q1: Naive Bayes够用吗？
A: 也许够，但是NB整合特征没有LR方便，参考Sempre⁶可以在组合样本的过程由Rule引入各种特征。
Q2: 接1问，上深度学习？
A: 问题先要能学习，才能深度学习。

参考文献

---

1. Week 3 - Parsing and Context-Free Grammars ↩︎

2. Week 3 - Probabilistic Context-Free Grammars ↩︎

3. AV: Natural Language Processing, by Michael Collins, Columbia University ↩︎

4. Notes on Probabilistic Context-Free Grammars ↩︎

5. Week 1 - 1.4.2 Discounting Methods ↩︎

6. SEMPRE: Semantic Parsing with Execution ↩︎