最大熵模型

最大熵模型（maximum entropy model）由最大熵原理推导实现

最大熵原理

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

假设离散随机变量$X$的概率分布时$P\left(X\right)$，则其熵是
$$H\left(P\right)=-\sum _{x}P\left(x\right)\log P\left(x\right)$$
熵满足下列不等式：
$$0\le H\left(P\right)\le \log \left|X\right|$$
其中$\left|X\right|$是$X$的取值个数，当且仅当$X$的分布是均匀分布时，右边的等号成立。
这就是说，当$X$服从均匀分布时，熵最大

证明：

$$\begin{array}{rl}& \underset{p_i}{\max }-\sum _{i=1}^n{p}_i\log p_i\\ & \text{ s.t. }\sum _{i=1}^n{p}_i=1\end{array}$$
显然$-{\sum }_{i=1}^n{p}_i\log p_i\ge 0$
当$p_i$中其中一个为$1$，其他为$0$时，$-{\sum }_{i=1}^n{p}_i\log p_i=0$

拉格朗日函数
$$L\left(P,\lambda \right)=-\sum _{i=1}^n{p}_i\log p_i-\lambda \left(\sum _{i=1}^n{p}_i-1\right)$$
求导
$$\frac{\partial L}{\partial p_i}=-\log p_i-1-\lambda =0$$
于是
$$\log p_1=\log p_2=\cdots =\log p_n=-\lambda -1$$
进而
$$p_1=p_2=\cdots =p_n$$

最大熵模型的定义

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

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

给定一个训练数据集
T = { ( x 1 , y 1 ) , ⋯ , ( x N , y N ) } T = \left\{\left(\mathbf{x}_1,y_1\right),\cdots,\left(\mathbf{x}_N,y_N\right)\right\} T={(x1​,y1​),⋯,(xN​,yN​)}
学习的目标是用最大熵原理选择最好的分类模型

首先考虑模型应该满足的条件。给定训练数据集，可以确定联合分布$P\left(X,Y\right)$的经验分布和边缘分布$P\left(X\right)$的经验分布，分别以$\tilde{P}\left(X,Y\right)$和$\tilde{P}\left(X\right)$表示。这里
$$\begin{gathered} \tilde{P}\left(X=\mathbf{x},Y=y\right)=\frac{v\left(X=\mathbf{x},Y=y\right)}{N} \\ \tilde{P}\left(X=\mathbf{x}\right)=\frac{v\left(X=\mathbf{x}\right)}{N} \end{gathered}$$
其中，$v\left(X=\mathbf{x},Y=y\right)$表示训练数据中样本$\left(\mathbf{x},y\right)$出现的频率，$v\left(X=\mathbf{x}\right)$表示训练数据中输入$\mathbf{x}$出现的频率，$N$表示训练样本容量

用特征函数（feature function）$f\left(\mathbf{x},y\right)$描述输入$\mathbf{x}$和输出$y$之间的某一个事实，其定义是
$$f\left(\mathbf{x},y\right)=\{\begin{array}{ll}1,& \mathbf{x}与y满足某一事实\\ 0,& 否则\end{array}$$

特征函数$f\left(x,y\right)$关于经验分布$\tilde{P}\left(X,Y\right)$的期望值，用$E_{\tilde{P}}\left(f\right)$表示
$$E_{\tilde{P}}\left(f\right)=\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f\left(\mathbf{x},y\right)$$
特征函数$f\left(\mathbf{x},y\right)$关于模型$P\left(Y|X\right)$与经验分布$\tilde{P}\left(X\right)$的期望值，用$E_P\left(f\right)$表示

$$E_P\left(f\right)=\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)f\left(\mathbf{x},y\right)$$
如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即
$$E_P\left(f\right)=E_{\tilde{P}}\left(f\right)$$
或者
$$\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)f\left(\mathbf{x},y\right)=\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f\left(\mathbf{x},y\right)$$
上式作为模型学习的约束条件
假设有$n$个特征函数$f_i\left(\mathbf{x},y\right)$，那么就有$n$个约束条件

最大熵模型：假设满足所有约束条件的模型集合为
C ≡ { P ∈ P ∣ E p ( f i ) = E P ~ ( f i ) , i = 1 , 2 , ⋯ , n } \mathcal{C}\equiv\left\{P\in\mathcal{P}|E_p\left(f_i\right) = E_{\tilde{P}}\left(f_i\right),\quad i = 1,2,\cdots, n\right\} C≡{P∈P∣Ep​(fi​)=EP~​(fi​),i=1,2,⋯,n}
定义在条件概率分布$P\left(Y|X\right)$上的条件熵为
$$H\left(P\right)=-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log P\left(y|\mathbf{x}\right)$$
则模型集合$\mathcal{C}$中条件熵$H\left(P\right)$最大的模型称为最大熵模型。
（其中$\log =\ln ={\log }_e$）

最大熵模型的学习

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

对于给定的训练数据集 T = { ( x 1 , y 1 ) , ⋯ , ( x N , y N ) } T=\left\{\left(\mathbf{x}_1,y_1\right), \cdots, \left(\mathbf{x}_N, y_N\right)\right\} T={(x1​,y1​),⋯,(xN​,yN​)}以及特征函数$f_i\left(\mathbf{x},y\right)$，最大熵的学习等价于约束最优化问题：
$$\begin{array}{rl}\underset{P\in \mathcal{C}}{\max }& H\left(P\right)=-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log P\left(y|\mathbf{x}\right)\\ s.t.& E_P\left(f_i\right)=E_{\tilde{P}}\left(f_i\right),i=1,2,\cdots ,n\\ & \sum _{y}P\left(y|\mathbf{x}\right)=1\end{array}$$
改成最小化
$$\begin{array}{rl}\underset{P\in \mathcal{C}}{\min }& -H\left(P\right)=\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log P\left(y|\mathbf{x}\right)\\ s.t.& E_P\left(f_i\right)=E_{\tilde{P}}\left(f_i\right),i=1,2,\cdots ,n\\ & \sum _{y}P\left(y|\mathbf{x}\right)=1\end{array}$$

拉格朗日函数
$$\begin{array}{rl}L\left(P,\mathbf{w}\right)& =-H\left(P\right)+w_0\left(1-\sum _{y}P\left(y|\mathbf{x}\right)\right)+\sum _{i=1}^n{w}_i\left(E_{\tilde{P}}\left(f_i\right)-E_P\left(f_i\right)\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log P\left(y|\mathbf{x}\right)+w_0\left(1-\sum _{y}P\left(y|\mathbf{x}\right)\right)\\ & +\sum _{i=1}^n{w}_i\left(\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f\left(\mathbf{x},y\right)-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)f\left(\mathbf{x},y\right)\right)\end{array}$$
原始问题
$$\underset{P\in \mathcal{C}}{\min }\underset{\mathbf{w}}{\max }L\left(P,\mathbf{w}\right)$$
对偶问题
$$\underset{\mathbf{w}}{\max }\underset{P\in \mathcal{C}}{\min }L\left(P,\mathbf{w}\right)$$

目标函数是凸的，约束条件是等式约束，于是满足广义Slater条件, 所以原始问题与对偶问题等价
设
$$\psi \left(\mathbf{w}\right)=\underset{P\in \mathcal{C}}{\min }L\left(P,\mathbf{w}\right)=L\left(P_{\mathbf{w}},\mathbf{w}\right)$$
其中
$$P_{\mathbf{w}}=\arg \underset{P\in \mathcal{C}}{\min }L\left(P,\mathbf{w}\right)=P_{\mathbf{w}}\left(y|\mathbf{x}\right)$$

$$\begin{array}{rl}\frac{\partial L}{\partial P\left(y|\mathbf{x}\right)}& =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)\left(\log P\left(y|\mathbf{x}\right)+1\right)-\sum _y{w}_0-\sum _{\mathbf{x},y}\left(\tilde{P}\left(\mathbf{x}\right)\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)\left(\log P\left(y|\mathbf{x}\right)+1-w_0-\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)\\ & =0\end{array}$$
在$\tilde{P}\left(\mathbf{x}\right)>0$的情况下
$$P\left(y|\mathbf{x}\right)=exp\left(\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)+w_0-1\right)=\frac{exp\left({\sum }_{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)}{exp\left(1-w_0\right)}$$

利用${\sum }_{y}P\left(y|\mathbf{x}\right)=1$,得
$$P_{\mathbf{w}}\left(y|\mathbf{x}\right)=\frac{1}{Z_{\mathbf{w}}\left(\mathbf{x}\right)}exp\left(\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)$$
其中
$$Z_{\mathbf{w}}\left(\mathbf{x}\right)=\sum _{y}exp\left(\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)$$

其中$Z_{\mathbf{w}}\left(\mathbf{x}\right)$称为规范化因子；
$P_{\mathbf{w}}=P_{\mathbf{w}}\left(y|\mathbf{x}\right)$就是最大熵模型。这里$\mathbf{w}$是最大熵模型中的参数向量
之后，求解
$$\max \psi \left(\mathbf{w}\right)$$
令
$${\mathbf{w}}^{\ast }=\arg \underset{\mathbf{w}}{\max }\psi \left(\mathbf{w}\right)$$

极大似然估计

下面证明对偶函数的极大化等价于最大熵模型的极大似然估计

训练数据的经验概率分布$\tilde{P}\left(X,Y\right)$，条件概率分布$P\left(Y|X\right)$的对数似然函数表示为
$$L_{\tilde{P}}\left(P_{\mathbf{w}}\right)=\log {\pi }_{\mathbf{x},y}P{\left(y|\mathbf{x}\right)}^{\tilde{P}\left(\mathbf{x},y\right)}=\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\log P\left(y|\mathbf{x}\right)$$

$$\begin{array}{rl}{L}_{\tilde{P}}\left(P_{\mathbf{w}}\right)& =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\log P\left(y|\mathbf{x}\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\log Z_{\mathbf{w}}\left(\mathbf{x}\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)-\sum _{\mathbf{x}}\tilde{P}\left(\mathbf{x}\right)\log Z_{\mathbf{w}}\left(\mathbf{x}\right)\end{array}$$
接着
$$\begin{array}{rl}\psi \left(\mathbf{w}\right)& =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y,\mathbf{x}\right)\log P_{\mathbf{w}}\left(y|\mathbf{x}\right)\\ & +\sum _{i=1}^n{w}_i\left(\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f_i\left(\mathbf{x},y\right)-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y|\mathbf{x}\right)f_i\left(\mathbf{x},y\right)\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)+\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y|\mathbf{x}\right)\left(\log P_{\mathbf{w}}\left(y|\mathbf{x}\right)-\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y|\mathbf{x}\right)\log Z_{\mathbf{w}}\left(\mathbf{x}\right)\\ & =\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)-\sum _{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)\log Z_{\mathbf{w}}\left(\mathbf{x}\right)\end{array}$$

这样，最大熵模型的学习问题就转化为具体求解对数似然函数极大化或对偶函数极大化的问题

可以将最大熵模型写成更一般的形式
$$\frac{1}{Z_{\mathbf{w}}\left(\mathbf{x}\right)}exp\left(\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)$$
其中
$$Z_{\mathbf{w}}\left(\mathbf{x}\right)=\sum _{y}exp\left(\sum _{i=1}^n{w}_i{f}_i\left(\mathbf{x},y\right)\right)$$
这里$\mathbf{x}\in {\mathbb{R}}^n$为输入， y ∈ { 1 , 2 , ⋯ , K } y\in\left\{1,2,\cdots, K\right\} y∈{1,2,⋯,K}为输出，$\mathbf{w}\in {\mathbb{R}}^n$为权值向量，$f_i\left(\mathbf{x},y\right)$为任意实值特征函数

参考：
统计学习方法(李航)