100天搞定机器学习|Day55 最大熵模型

1、熵的定义

熵最早是一个物理学概念，由克劳修斯于1854年提出，它是描述事物无序性的参数，跟热力学第二定律的宏观方向性有关：在不加外力的情况下，总是往混乱状态改变。熵增是宇宙的基本定律，自然的有序状态会自发的逐步变为混沌状态。
1948年，香农将熵的概念引申到信道通信的过程中，从而开创了”信息论“这门学科。香农用“信息熵”来描述随机变量的不确定程度，也即信息量的数学期望。
关于信息熵、条件熵、联合熵、互信息、相对熵、交叉熵请点击蓝字直达

2、最大熵模型
这里引用吴军博士《数学之美》中关于最大熵的论述

最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”

理解最大熵原理，最简单的例子就是掷色子，当我们对这个色子一无所知时，我们一般会假定它每面朝上的概率是均等的，即各点出现的概率均为 1/6。这就保留了最大的不确定性，也就是说让熵达到最大。当我们假定这个色子是韦小宝的，六点朝上的概率是 1/2，这样其他面朝上的概率是多少呢？在无其他信息情况下，其他面朝上的概率均为 1/10.
在满足已知条件前提下，如果没有更多的信息，则那些不确定部分都是“等可能的”。而等可能性通过熵最大化来刻画。最大熵模型要解决的问题就是已知 X，计算 Y 的概率，且尽可能让 Y 的概率最大。

由此，就可以引出最大熵模型的定义：

最大熵模型假设分类模型是一个条件概率分布$P(Y|X)$,X 为特征，Y 为输出。
给定一个训练集${(x^{(1)},y{(1)}), (x^{(2)},y{(2)}), ... ，(x^{(m)},y{(m)})}$,其中 x 为n维特征向量，y 为类别输出。我们的目标就是用最大熵模型选择一个最好的分类类型。
在给定训练集的情况下，我们可以得到总体联合分布$P(X,Y)$的经验分布$\overline{P}(X,Y)$,和边缘分布$P(X)$的经验分布$\overline{P}(X)$。$\overline{P}(X,Y)$即为训练集中 X,Y 同时出现的次数除以样本总数 m，$\overline{P}(X)$即为训练集中 X 出现的次数除以样本总数 m。
用特征函数$f(x,y)$描述输入 x 和输出 y 之间的关系。定义为：

$$
f(x,y)=
\begin{cases}
1& {x与y满足某个关系}\
0& {否则}\end{cases}
$$

可以认为只要出现在训练集中出现的$(x^{(i)},y{(i)})$,其$f(x^{(i)},y{(i)}) = 1$. 同一个训练样本可以有多个约束特征函数。
特征函数$f(x,y)$关于经验分布$\overline{P}(X,Y)$的期望值，用$E_{\overline{P}}(f)$表示为:　
$$
E_{\overline{P}}(f) = \sum\limits_{x,y}\overline{P}(x,y)f(x,y)
$$　　　
特征函数$f(x,y)$关于条件分布$P(Y|X)$和经验分布$\overline{P}(X)$的期望值，用$E_{P}(f)$表示为:
$$
E_{P}(f) = \sum\limits_{x,y}\overline{P}(x)P(y|x)f(x,y)
$$
如果模型可以从训练集中学习，我们就可以假设这两个期望相等。即：
$$
E_{\overline{P}}(f) = E_{P}(f)
$$
上式就是最大熵模型学习的约束条件，假如我们有 M 个特征函数$f_i(x,y) (i=1,2...,M)$就有 M 个约束条件。可以理解为我们如果训练集里有 m 个样本，就有和这 m 个样本对应的 M 个约束条件。
这样我们就得到了最大熵模型的定义如下：
假设满足所有约束条件的模型集合为：
$$E_{\overline{P}}(f_i) = E_{P}(f_i) (i=1,2,...M)$$
定义在条件概率分布$P(Y|X)$上的条件熵为：
$$
H(P) = -\sum\limits_{x,y}\overline{P}(x)P(y|x)logP(y|x)
$$
我们的目标是得到使$H(P)$最大的时候对应的$P(y|x)$,这里可以对$H(P)$加了个负号求极小值，这样做的目的是为了使$-H(P)$为凸函数，方便使用凸优化的方法来求极值。

最大熵模型的学习

最大熵模型的学习等价于约束最优化问题：

$$
\begin{eqnarray}
\max\limits_{P\in\mathcal{C}}& H(P)=-\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\nonumber \
4 E_P(f_k)=E_\tilde{P}(f_k),k=1,2,\cdots,K\nonumber \
&& \sum_yP(y|x)=1\nonumber
\end{eqnarray}
$$

对应的最小化问题为：

$$
\begin{eqnarray}
&\min\limits_{P\in\mathcal{C}}& -H(P)=\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\nonumber \
&s.t.& E_P(f_k)-E_\tilde{P}(f_k)=0,k=1,2,\cdots,K\nonumber \
&& \sum_yP(y|x)=1\nonumber
\end{eqnarray}
$$

引入拉格朗日乘子$\beta_0,\beta_1,\cdots,\beta_K$,定义拉格朗日函数$L(P,\beta)$

$$
\begin{eqnarray}
L(P,\beta)&=& -H(P)+\beta_0(1-\sum_yP(y|x))+\sum_{k=1}^K\beta_k(E_\tilde{P}(f_i)-E_P(f_i)) \nonumber\
&=&\sum{x,y}\tilde{P}(x)P(y|x)\log P(y|x)+\beta_0(1-\sum_yP(y|x))\nonumber\
&+&\sum_{k=1}^K\beta_k(\sum\limits{x,y}\tilde{P}(x,y)f(x,y)-\sum\limits_{x,y}\tilde{P}(x)P(y|x)f(x,y))\nonumber
\end{eqnarray}
$$

将其解记作：
$P_\beta=\arg\min\limits_{P\in\mathcal{C}}L(P,\beta)=P_\beta(y|x)$

求$L(P,β)$对$P(y|x)$的偏导数为 0

$$
\begin{eqnarray}
\frac{\partial L(P,\beta)}{\partial P(y|x)}&=&\sum_{x,y}\tilde{P}(x)(\log P(y|x)+1)-\sum_y\beta_0-\sum_{x,y}(\tilde{P}(x)\sum_{k=1}^K\beta_kf_k(x,y)) \nonumber\
&=&\sum_{x,y}\tilde{P}(x)\Big{(}\log P(y|x)+1-\beta_0-\sum_{k=1}^K\beta_kf_k(x,y)\Big{)}\nonumber\
&=&0\nonumber
\end{eqnarray}
$$

得：

$$
P(y|x)=\exp(\sum\limits_{k=1}^{K\beta_kf_k(x,y)+\beta_0-1)=\frac{\exp(\sum\limits_{k=1}}K\beta_kf_k(x,y))}{\exp(1-\beta_0)}
$$

由$\sum_yP(y|x)=1$
所以

$$
P_\beta(y|x)=\frac{1}{Z_\beta(x)}\exp(\sum\limits_{k=1}^K\beta_k f_k(x,y))
$$

其中$Z_\beta(x)=\sum\limits_y\exp(\sum\limits_{k=1}^K\beta_k f_k(x,y))$

当选定合适的特征函数时，最大熵模型可以导出多项逻辑模型，这个很显然。但二者并不等价，最大熵可以选择其他特征函数。
当选定合适的特征函数时，最大熵模型可以导出多项逻辑模型，这个很显然。但二者并不等价，最大熵可以选择其他特征函数。
记对偶函数为$\Psi(\beta)=\min\limits_{P\in\mathcal{C}}L(P,\beta)=L(P_\beta,\beta)$,接下来最大化$\Psi(\beta)$得到其解$\beta^*$.则最大熵模型为：

$$
P^*=P_{\beta*}(y|x)
$$

可证明，对偶函数等价于条件概率分布$P(Y|X)$的对数似然函数

$$
L_\tilde{P}(P_\beta)=\sum\limits_{x,y}\tilde{P}(x,y)\log P(y|x)
$$

则最大熵模型的学习中的对偶函数极大化等价于最大熵模型的极大似然估计。

3.2 模型对比
最大熵模型与LR模型的关系：
最大熵模型和 LR 模型都属于对数线性模型，LR 及最大熵模型学习一般采用极大似然估计，或正则化的极大似然估计。LR 及最大熵模型学习可以形式化为无约束最优化问题，求解时有改进的迭代尺度法、梯度下降法、拟牛顿法。
逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应类别为二类时的特殊情况，也就是当逻辑回归类别扩展到多类别时，就是最大熵模型。

最大熵模型与决策树模型的关系：
最大熵原理选取熵最大的模型，而决策树的划分目标选取熵最小的划分。原因在于：

最大熵原理认为在满足已知条件之后，选择不确定性最大（即：不确定的部分是等可能的）的模型。也就是不应该再施加任何额外的约束。因此这是一个求最大不确定性的过程，所以选择熵最大的模型。

决策树的划分目标是为了通过不断的划分从而不断的降低实例所属的类的不确定性，最终给实例一个合适的分类。因此这是一个不确定性不断减小的过程，所以选取熵最小的划分。

3.4 关于最大熵和朴素贝叶斯的联系
最大熵和朴素贝叶斯的联系
两者都使用了P(y|x)，区别在于朴素贝叶斯使用先验概率求解，最大熵利用最大化条件熵求解。

朴素贝叶斯倾向于从基本信息中提取新的信息，而最大熵将提取信息的程度进行了量化（就好像强迫自己获得概率一定是要均匀分布一样）。

最大熵模型的 Python 实现

这里就不再贴代码，网上有许多优秀的博主已经共享过了，这里推荐大家看一下
SmirkCao
https://github.com/SmirkCao/Lihang

一个具体的案例是 Dod-o 用最大熵模型来做手写数字识别，正确率 96.9%，运行时长：8.8h
https://github.com/Dod-o/Statistical-Learning-Method_Code

参考文献：
李航《统计学习方法》6.2 最大熵模型
https://www.cnblogs.com/pinard/p/6093948.html
https://www.cnblogs.com/ooon/p/5677098.html
https://blog.csdn.net/ltc844139730/article/details/92011520
http://www.huaxiaozhuan.com/统计学习/chapters/14_maxent.html