最大熵模型理论及NLP应用总结

转自：https://zhuanlan.zhihu.com/p/56414312

最大熵是概率模型学习的一个准则，将其推广到分类问题得到最大熵模型(maximum entropy model).本部分首先介绍最大熵模型，其次讲述其学习算法，包括改进的迭代尺度算法和拟牛顿法，最后介绍最大熵原理在NLP应用。

PART1 最大熵模型

最大熵模型由最大熵原理推导实现。这里首先叙述一般的最大熵原理，然后讲解最大熵模型的推导，最后给出最大熵模型学习的形式。

1.最大熵原理

最大熵原理认为，学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，所以，最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。

2.最大熵模型的推导

最大熵原理是统计学习的一般原理，将它应用到分类得到最大熵模型。

假设分类模型是一个条件概率分布 $P(Y|X)$ ， $Xin mathcal{X}subseteqmathcal{R}^n$ 表示输入， $Ysubseteqmathcal{Y}$ 表示输出， $mathcal{X}$ 和 $mathcal{Y}$ 分别是输入和输出的集合。这个模型表示的是对于给定的输入 $X$ ，以条件概率 $P(Y|X)$ 输出 $Y$ 。

给定一个训练数据集

$T={(x_1,y_1),(x_2,y_2),.......,(x_N,y_N)}$

学习的目标是用最大熵原理选择最好的分类模型。

首先考虑模型应该满足的条件。给定训练数据集，可以确定联合分布 $P(X,Y)$ 的经验分布和边缘分布 $P(X)$ 的经验分布，分别以 $ar{P}(X,Y)$ 和 $ar{P}(X)$ 表示。这里，

$ar{P}(X=x,Y=y)=frac{v(X=x,Y=y)}{N}$

$ar{P}(X=x)=frac{v(X=x)}{N}$

其中， $v(X=x,Y=y)$ 表示训练数据中样本 $(x,y)$ 出现的频数，v(X=x)表示训练数据中输入 $x$ 出现的频数， $N$ 表示训练样本容量。

用特征函数（feature function） $f(x,y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实。其定义是

$egin{equation} f(x,y)=left{ egin{array}{lr} 1,quad x与y满足某一事实 \ 0,quad 否则 end{array} ight. end{equation}$

它是一个二值函数，当 $x$ 和 $y$ 满足这个事实时取值为1，否则取值为0.

特征函数 $f(x,y)$ 关于经验分布 $ar{P}(X,Y)$ 的期望值，用 $E_{ar{P}}(f)$ 表示

$E_{ar{P}}(f)=sum_{x,y}ar{P}(x,y)f(x,y)$

特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 与经验分布 $ar{P}(X)$ 的期望值，用 $E_{P}(f)$ 表示

$E_P(f)=sum_{x,y}ar{P}(x)P(y|x)f(x,y)$

如果模型能够获取训练数据中的信息，那么就可以假设着两个期望值相等，即

$E_{ar{P}}(f)=E_P(f)$ (*1)

或

$sum_{x,y}ar{P}(x,y)f(x,y)=sum_{x,y}ar{P}(x)P(y|x)f(x,y)$ (*2)

将式(*1)和(*2)作为模型学习的约束条件。假如有 $n$ 个特征函数 $f_i(x,y),i=1,2,...,n$ ，那么就有 $n$ 个约束条件。

Definition1:(最大熵模型)

假设满足所有约束条件的模型集合为

$mathcal{C}equiv {Pin mathcal{P}|E_P(f_i)=E_{ar{P}}(f_i),i=1,2,...,n}$ (*3)

定义在条件概率分布 $P(Y|X)$ 上的条件熵为

$H(P)=-sum_{x,y} ar{P}(x)P(y|x)log P(y|x)$ (*4)

则模型集合 $mathcal{C}$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型。式中的对数为自然对数。

3.最大熵模型学习的形式

最大熵模型的学习过程就是求解最大熵模型的过程。最大熵模型的学习可以形式化为约束最优化问题。

对于给定的训练数据集 $T={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$ 以及特征函数 $f_i(x,y),i=1,2,...,n$ ，最大熵模型的学习等价于约束最优化问题：

$min_{Pin mathcal{C}} quad -H(P)$

$s.t. quad E_P(f)=E_{ar{P}}(f)$ (*5)

$quad quad quad sum_{y}P(y|x)=1$ (*6)

这里，将约束最优化的原始问题转换为无约束最优化的对偶问题。通过求解对偶问题求解最优化问题。

首先，引进拉格朗日乘子 $w_0,w_1,w_2,...,w_n$ ，定义拉格朗日函数 $L(P,w)$ ：

$L(P,w)=-H(P)+w_0(1-sum_{y}P(y|x))+sum_{i=1}^nw_i(E_{P}(f_i)-E_{ar{P}}(f_i))$ (*7)

原始化的原始问题是

$min_{Pin mathcal{C}}max_wL(P,w)$ （*8）

对偶问题是

$max_wmin_{Pinmathcal{C}}L(P,w)$ (*9)

由于拉格朗日函数 $L(P,w)$ 是 $P$ 的凸函数，原始问题(8)的解与对偶问题(9)的解是等价的。这样，可以通过求解对偶问题(*9)来求解原始问题(*8)。

首先，求解对偶问题（*9）内部的极小化问题 $min_{Pinmathcal{C}}L(P,w)$ 。 $min_{Pinmathcal{C}}L(P,w)$ 是 $w$ 函数，将其记作

$Psi(w)=min_{Pinmathcal{C}}L(P,w)=L(P_w,w)$ (*10)

具体地，求 $L(P,w)$ 对 $P(y|x)$ 的偏导数

$frac{partial L(P,w)}{partial P(y|x)}=sum_{x,y}ar{P}(x)(logP(y|x)+1)-sum_y w_0-sum_{x,y}(ar{P}(x)sum_{i=1}^nw_if_i(x,y))$

$quad quad =sum_{x,y}ar{P}(x)(logP(y|x)+1-w_0-sum_{i=1}^nf_i(x,y))$

令偏导数等于0，在 $ar{P}(x)>0$ 的情况下，解得

$P(y|x)=exp(sum_{i=1}^{n}w_if_i(x,y)+w_0-1)=frac{exp(sum_{i=1}^n w_i f_i(x,y))}{exp(1-w_0)}$

由于 $sum_yP(y|x)=1$ ，得

$P_w(y|x)=frac{1}{Z_w(x)}exp(sum_{i=1}^nw_if_i(x,y))$ (*11)

其中，

$Z_w(x)=sum_y exp(sum_{i=1}^n w_if_i(x,y))$ (*12)

之后，求解对偶问题外部的极大化问题

$max_w Psi(w)$

将其解记为 $w^*$ 。

也就是说，可以应用最优化算法求对偶函数 $Psi(w)$ 的极大化，得到 $w^*$ ，用来表示 $P^*in C$ 。这里， $P^*=P_{w^*}=P_{w^*}(y|x)$ 是学习到的最优化模型（最大熵模型）。

4.极大似然估计

从以上最大熵模型学习中可以看出，最大熵模型是由式（*11）、式（*12）表示的条件概率分布。下面证明对偶函数的极大化等价于最大熵模型的极大似然估计。

已知训练数据的经验概率分布 $ar{P}(X,Y)$ ，条件概率分布 $P(Y|X)$ 的对数似然函数表示为

$L_{ar{P}}(P_w)=log Pi_{x,y} P(y|x)^{ar{P}(x,y)}=sum_{x,y}{ar{P}(x,y)} log P(y|x)$

当条件概率分布 $P(y|x)$ 是最大熵模型（*11）和（*12）时，对数似然函数 $L_{ar{P}}(P_w)$ 为

$L_{ar{P}}(P_w)=sum_{x,y}ar{P}(x,y)log P(y|x)$

$=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}w_if_i(x,y)-sum_{x,y}ar{P}(x,y)log Z_w(x)=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}w_if_i(x,y)-sum_{x}ar{P}(x)log Z_w(x)$ （*13）

再看对偶函数，由式（*7）及式（*10）可得

$Psi(w)=sum_{x,y}ar{P}(x)P_w(y|x)log P_w(y|x)+sum_{i=1}^nw_i(sum_{x,y}ar{P}(x,y)f_i(x,y)-sum_{x,y}ar{P}(x)P_w(y|x)f_i(x,y))$

$=sum_{x,y}ar{P}(x,y)sum_{i=1}^nw_if_i(x,y)+sum_{x,y}ar{P}(x)P_w(y|x)(logP_w(y|x)-sum_{i=1}^nw_if_i(x,y))$

$=sum_{x,y}ar{P}(x,y)sum_{i=1}^nw_if_i(x,y)+sum_{x,y}ar{P}(x)P_w(y|x)log Z_w(x)$

$=sum_{x,y}ar{P}(x,y)sum_{i=1}^nw_if_i(x,y)+sum_{x}ar{P}(x)log Z_w(x)$ （*14）

比较（*13）和（*14），可得

$Psi(w)=L_{ar{P}}(P_w)$

既然对偶函数 $Psi(w)$ 等价于对数似然函数 $L_{ar{P}}(P_w)$ ，于是证明了最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计这一事实。

PART2 学习算法

逻辑斯蒂回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。从最优化的观点看，这时的目标函数具有很好的性质，它是光滑的凸函数，因此多种最优化方法都适用，保证能找到全局最优解。常用的方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。

1.改进的迭代尺度法（imporoved iterative scaling,IIS）

$L(w)=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}w_if_i(x,y)-sum_{x}ar{P}(x)log Z_w(x)$

IIS的想法是：假设最大熵模型当前的参数向量是 $w=(w_1,w_2,....,w_n)^T$ ，我们希望找到一个新的参数向量 $w+delta=(w_1+delta_1,w_2+delta_2,...,w_n+delta_n)^T$ ，使得模型的对数似然函数值增大。如果能有这样一种参数向量更新的方法 $au:w ightarrow w+delta$ ，那么就可以重复适用这一方法，直到找到对数似然函数的最大值。

对于给定的经验分布 $ar{P}(x,y)$ ，模型参数从 $w$ 到 $w+delta$ ，对数似然函数的改变量是

$L(w+delta)-L(w)=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)-sum_{x}ar{P}(x)logfrac{Z_{w+delta}(x)}{Z_w(x)}$

利用不等式

$-logalphageq1-alpha,quad alpha>0$

建立对数似然函数改变量的下界：

$L(w+delta)-L(w)geq sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)+1-sum_{x}ar{P}(x)frac{Z_{w+delta}(x)}{Z_w(x)}$

$=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)+1-sum_{x}ar{P}(x)sum_yP_w(y|x)exp(sum_{i=1}^ndelta_i f_i(x,y))$

将右端记为

$A(delta|w)=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)+1-sum_{x}ar{P}(x)sum_yP_w(y|x)exp(sum_{i=1}^ndelta_i f_i(x,y))$

于是有

$L(w+delta)-L(w)geq A(delta|w)$

即 $A(delta|w)$ 是对数似然函数改变量的一个下界。

如果能找到适当的 $delta$ 使下界 $A(delta|w)$ 提高，那么对数似然函数也会提高。然而，函数 $A(delta|w)$ 中的是 $delta$ 一个向量，含有多个变量，不易同时优化。IIS试图一次只优化其中一个变量 $delta_i$ ，而固定其他变量 $delta_j,i e j$ 。

为达到这一目的，IIS进一步降低下界 $A(delta|w)$ 。具体地，IIS引进一个量 $f^{ast}(x,y)$ ，

$f^{ast}(x,y)=sum_i f_i(x,y)$

这样

$A(delta|w)=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)+1-sum_{x}ar{P}(x)sum_yP_w(y|x)exp(f^*(x,y)sum_{i=1}^nfrac{delta_i f_i(x,y)}{f^*(x,y)})$ (*15)

利用指数函数的凸性以及对任意 $i$ ，有 $frac{f_i(x,y)}{f^*(x,y)}geq 0$ 且 $sum_{i=1}^nfrac{f_i(x,y)}{f^*(x,y)}=1$ 这一事实，根据Jensen不等式，得到

$exp(sum_{i=1}^nfrac{ f_i(x,y)}{f^*(x,y)}delta_if^*(x,y))leq sum_{i=1}^nfrac{ f_i(x,y)}{f^*(x,y)}exp(delta_if^*(x,y))$

于是（*15）可改写为

$A(delta|w)geq sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)+1-sum_{x}ar{P}(x)sum_yP_w(y|x)sum_{i=1}^nfrac{ f_i(x,y)}{f^*(x,y)}exp(delta_if^*(x,y))$

记上不等式右端为

$B(delta|w)=sum_{x,y}ar{P}(x,y)sum_{i=1}^{n}delta_if_i(x,y)+1-sum_{x}ar{P}(x)sum_yP_w(y|x)sum_{i=1}^nfrac{ f_i(x,y)}{f^*(x,y)}exp(delta_if^*(x,y))$

于是得到

$L(w+delta)-L(w)geq B(delta|w)$

这里， $B(delta|w)$ 是对数似然函数改变量的一个新的（相对不紧的）下界。

求 $B(delta|w)$ 对 $delta_i$ 的偏导数：

$frac{partial B(delta|w)}{partial delta_i}=sum_{x,y}ar{P}(x,y)f_i(x,y)-sum_{x}ar{P}(x)sum_yP_w(y|x)f_i(x,y)exp(delta_i f^*(x,y))$ (*16)

在式（*16）里，除 $delta_i$ 外不含任何其他变量，令偏导数为0得到

$sum_{x}ar{P}(x)sum_yP_w(y|x)f_i(x,y)exp(delta_i f^*(x,y))=E_{ar{P}}(f_i)$ (*17)

于是，依次对 $delta_i$ 求解方程(*17)可以求出 $delta$ 。

算法（改进的迭代尺度算法IIS）

输入：特征函数 $f_1,f_2,...,f_n$ ；经验分布 $ar{P}(X,Y)$ ，模型 $P_w(y|x)$

输出：最优参数值 $w_i^*$ ；最优模型 $P_{w^*}$ 。

（1）对所有 $iin {1,2,...,n}$ ，取初值 $w_i=0$

（2）对每一 $iin {1,2,..,n}$ ：

（a）令 $delta_i$ 是方程

$sum_{x}ar{P}(x)sum_yP_w(y|x)f_i(x,y)exp(delta_i f^*(x,y))=E_{ar{P}}(f_i)$

的解，这里，

$f^*(x,y)=sum_{i=1}^n f_i(x,y)$

（b）更新 $w_i$ 值： $w_ileftarrow w_i+delta_i$

（3）如果不是所有 $w_i$ 都收敛，重复步（2）.

PART3 NLP应用

在网络搜索排名中用到的信息有上千种，如何能把它们结合在一起用好？更普遍的讲，在信息处理中，我们常常知道各种各样但不完全确定的信息，我们需要用一个统一模型将这些信息综合起来。如何综合好，是一门学问。

最大熵模型在形式上是最漂亮、最完美的统计模型，在自然语言处理和金融方面有很多有趣的应用。最大熵模型，就是要保留全部的不确定性，将风险降到最小。

早期，由于最大熵模型计算量大，研究人员一般采用一些类似最大熵模型的近似模型。这一近似，最大熵模型就从完美变得不完美了。于是，不少原来热衷于此的学者又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势是宾夕法尼亚大学马库斯教授的高徒拉纳帕提(Adwait Ratnaparkhi).拉纳帕提成功之处在于他没有对最大熵模型进行近似处理，而是找到了几个最适合最大熵模型而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词）以及主谓宾等句子成分，通过最大熵模型结合起来，做出了当时世界上最好的词性标注系统和句法分析器。从拉纳帕提的成果中，科学家又看到了最大熵模型解决复杂文字信息处理问题的希望。

在2000年前后，由于计算机速度的提升以及训练算法的改进，很多复杂的问题，包括句法分析、语言模型和机器翻译都可以采用最大熵模型了。最大熵模型和一些简单组合了特征的模型相比，效果可以提升几个百分点。