NGram prune

Reference

https://blog.csdn.net/xmdxcsj/article/details/50321613
https://arxiv.org/pdf/cs/0006025.pdf

前置问题：

• 为什么要做模型裁剪？哪些NGram会被裁剪？裁剪的准则是什么？
  模型裁剪原因：在保证效果影响不大的情况下，尽可能减小模型规模，这样可以节省模型加载内存大小和计算时间。
  模型裁剪准则:相对熵。实际工具中设置的阈值是ppl相对变化门限。
  哪些NGram会被裁剪：对于每一个NGram，计算裁剪前后模型相对熵，然后转换成ppl相对变化值，和阈值进行比较，小于阈值，裁掉。

• 没被裁剪的NGram是否需要改变？
  没被裁剪的NGram概率值(条件概率)不变，backoff值重新计算。

• 为什么裁剪不需要其他任何外置文件？（难点与重点）
  重点在于模型本身也有ppl值（或者更严格的说，会有ppl相对值）。
  首先来说，如果我们提供了一个测试集，那我们一定可以得到一个模型在这个测试集上的ppl。我们回想一下每句话ppl的计算过程，然后假设我们提供了一个通用的测试集。那么ppl值计算为：
  
  
  注意上述两个公式中都是，那个代表的是语料中ngram出现的概率，裁剪前后不变。同样的可以和测试集上ppl计算公式比较一下：

理解重点

• 相对熵：
• ppl相对变化：
• 相对熵计算过程：对于每一个NGram(二阶以上)，计算裁剪它前后的相对熵：
  
  
  上面公式转换是重点，裁剪一个NGram以后，发生变化的值只有只有两部分：
• 历史词， 固定到，当前backoff值发生了变化。
• 当前词， 固定到，所有以当前NGram的为历史的NGram backoff概率都发生了变化，另外裁剪的NGram概率也发生了变化，裁掉以前直接获取，裁掉以后需要backoff到低阶获取。

示例如下，如果删除NGram 中的3gram：我 爱 你 ，那么整个模型概率发生变化的有：
p(你|我 爱)
bo(我 爱 w)，所有以我 爱为历史词的NGram其backoff值都发生了变化。
bo(我 爱)，我 爱backoff值也发生了变化。

裁剪流程

1. 给定一个ppl相对变化的门限threshold
2. 计算删除单独一条ngram，模型困惑度的相对变化
3. 挑选出那些低于门限值的ngram，删除，然后重新计算回退权重。