素心如何天上月 (Yong Sun's Blog): Yong Sun's Blog

这一回我们要介绍的是，如何基于熵对back-off模型进行剪枝（pruning）。

$ make m3_prune
./slmprune ../swap/lm_sc.3gram ../swap/lm_sc.3gm R 100000 1250000 1000000

首先来看熵的定义，设p(x)是随即变量X的概率密度函数，则X的熵为：

注：log均是以2为底的对数，且假定0log 0 = 0。

熵用来描述随机事件的不确定性的大小。熵值越大，不确定性就越高。等式的后半部分表明，熵实际上是log(1/p(X))的期望。假如p(X=x_i)的概率为1/256，那么log(1/p(x_i))=log(256)=8，也就是说要传输x_i所表示的随机事件，需要用8个bit。而H(p)是对这个值的期望（加权平均），即平均信息长度。

再来看看相对熵（即Kullback-Leibler距离）：

它表示的含义是，如果一个随机变量X的分布为p，我们却用概率分布q为其编码，所要多使用的比特位。

条件相对熵的计算公式为：

注：这个公式的证明，请参见 "Elements of Information Theory" （《信息论基础》，机械工业出版社）。

下面来看看如何应用相对熵来对back-off语言模型进行剪枝。下面的分析源自 "Entropy-based Pruning of Backoff Language Models" 一文。

回忆一下back-off模型的一般形式

Ps(Wi|h) = Pd(Wi|h)         -- C(h,Wi) > 0
           bow(h).Ps(Wi|h') -- C(h,Wi) == 0

剪枝的目标，就是要从模型中删除某些有明确估计（explicit estimation，即C(h,Wi) > 0）的n-gram，以降低模型的参数规模，同时尽可能减少准确度的损失。（注意，在剪枝之后，剩余的那些有明确估计的n-gram，其概率并不改变。）

剪枝的步骤是：

1. 选取阈值，
   
2. 分别计算剪去每个n-gram所引起的相对熵的增长，
3. 将增长幅度偏低的那些n-gram从模型中删除，然后重新计算back-off weights。
   

假设从模型中删除(h, w)后，再计算p(w|h)时，就需要进行回退估计（back-off or implicit estimation）了。要保证概率模型的规整性，即sum_w_i p(w_i|h) = 1，bow(h)必须重新计算，记为bow'(h)，则p'(w|h) = bow'(h).p(w|h')。同时，原模型中所有涉及h的回退估计都会受到影响，将这种情况记为BO(wi,h)（实际上就是C(h,w_i) == 0的情况）。我们可以得到：

注意，h和w都是给定的、具体的。且除了(h,w)之外的，原先有明确估计的n-gram，其概率不变，因此相互抵消掉了。

最后（推导过程见上面引用的那篇论文），我们可以得到：


其中，p(h) = p(h₁)p(h₂|h₁)...，并且，我们知道：


那么接下来的问题就是，如何计算bow'(h)了。


计算bow'(h)，就是将计算bow(h)公式分子分母中的求合式中，去掉已经剪枝的w。因为bow(h)是已知的，我们求得分子，也就可以得到分母，然后在分子和分母上分别加上p(w|h)和p(w|h')。这样就可以得到bow'(h)了。

下面来看代码，

slmprune.cpp：

CSlmPruner::Prune()：

从level[N]到level[1]，调用PrunLevel(lvl)进行剪枝。完成后调用CalcBOW()重新计算level[0..N-1]上各节点的back-off weight。

CSlmPruner::PruneLevel(lvl)：

sz[lvl]是level[lvl]中节点的数量，其中包括一个尾节点（pseudo tail），减1为实际的节点数，赋值给n。cut[lvl]中是要剪去的n-gram的数量。分配TNodeInfo[n]数组，赋给pbuf。迭代level[lvl]中的节点，用一个for循环找出该节点的前继节点，然后将这个n-gram放到hw[0..lvl]中，并将各个level上的下标保存在idx[0..lvl]中。判断这个节点是否有子节点（(pn+1)->child > pn->child），如果有子节点，则这个节点不可被剪掉。如果没有子节点，调用CalcDistance(lvl, idx, hw)计算剪掉这个节点所引起的相对熵的增量。将上述信息保存到pbuf中。继续迭代level[lvl]的下一个节点。

迭代完成后，对TNodeInfo数组进行一个堆排序。然后迭代TNodeInfo数组的前cut[lvl]个元素，将level[lvl][pinfo->idx]上节点的概率值标为1.0。然后执行CutLevel()，将标记概率有1.0的节点从level[lvl]中删除，并修改level[lvl-1]前继节点的child下标。将level[lvl]新的大小赋值给sz[lvl]。清理分配的内存空间和成员变量，然后退出。

CSlmPruner::CalcDistance(lvl, idx[], hw[0..lvl])：

首先从parent节点上得到bow(h)，保存在BOW变量中。然后计算p(h)，p(h) = p(hw₁).p(hw₂|hw₁)...p(hw_lvl-1|hw₁hw₂...hw_lvl-2)，保存在PH变量中。然后level[lvl][idx[lvl]]节点上概率值，即为p(w|h)，保存在PHW变量中。调用getPr(lvl-1, hw+2)，得到p(w|h')的概率指，保存在PH_W变量中。

如果cache_level不是lvl-1（那么只可能是-1），或者cache_idx不等于idx[lvl-1]（那么只可能是-1），则将cache_level和cache_idx分别赋值，并且将cache_PA和cache_PB初始化有1.0。迭代父节点的所有子节点[parent->child, (parent+1)->child)，得到每个子节点上的概率值pr（即p(w_i|h)），并从cache_PA中减去；将hw[lvl]赋值为当前子节点的词id，调用getPr(lvl-1, hw+2)，得到概率值p_r（即p(w_i|h')），并从cache_PB中减去。迭代结束之后，PA = sum_{w_i:BO(w_i,h)} P(w_i|h)，而PB = sum_{w_i:BO(w_i,h)} P(w_i|h')。然后分别加上p(w|h)和p(w|h')，相除得到bow'(h)，保存在_BOW中。

最后套用公式，得到D(p||p')，并返回。

CSlmPruner::CalcBOW()，CalcNodeBow(...)：

和上一回中的CSlmBuilder::CalcBOW()和CalcNodeBow(...)基本雷同。就不再赘述了。