最大熵模型
最大熵模型是指在满足约束条件的模型集合中选取熵最大的模型，即不确定性最大的模型。
最大熵原理
最大熵思想：当你要猜一个概率分布时，如果你对这个分布一无所知，那就猜熵最大的均匀分布，如果你对这个分布知道一些情况，那么，就猜满足这些情况的熵最大的分布。
算法推导
按照最大熵原理,我们应该优先保证模型满足已知的所有约束。那么如何得到这些约束呢?
思路是:从训练数据$T$中抽取若干特征,然后要求这些特征在$T$上关于经验分布的期望与它们在模型中关于$p(x,y)$的数学期望相等,这样,一个特征就对应一个约束。
假设训练集为$T={(x1,y1),(x2,y2),…,(xn,yn)}$。则联合分布$P(x,y)$的经验分布和边缘分布$P(x)$的经验分布为：
$$\tilde{P}(x,y)=\tilde{P}(X=x,Y=y)=\frac{count(x,y)}{N}$$
$$\tilde{P}(x)=\tilde{P}(X=x)=\frac{count(x)}{N}$$
我们定义特征函数
$$f(x,y)=
\begin{cases}
1& \text{x,y满足某一事实}\\
0& \text{否则}
\end{cases}$$
设$E_{\tilde{P}}(f)$：表示特征函数$f$在训练数据$T$上关于$\tilde{P}(x,y)$的数学期望：
$$E_{\tilde{P}}(f)=\sum_{x,y}{\tilde{P}(x,y)f(x,y)}
$$
设$E_p(f)$：表示特征函数$f$在模型上关于$P(x,y)$的数学期望
$$E_(f)=\sum_{x,y}{P(x,y)f(x,y)} =\sum_{x,y}{P(x)P(y|x)f(x,y)}
$$
由于$P(x)$是未知的，我们使用$\tilde{P}(x)$来近似表示。于是有
$$E_(f)=\sum_{x,y}{\tilde{P}(x)P(y|x)f(x,y)}
$$
最终我们需要计算的条件概率为：$P(Y|X)$。
我们的条件熵为：
$$
H(P) = -\sum_{x,y}P(x)P(y|x)\log{P(y|x)}
$$
同样，我们需要将$P(x)$的值进行近似处理：
$$
H(P) = -\sum_{x,y}\tilde{P}(x)P(y|x)\log{P(y|x)}
$$
另外，对于任意输入样例，它总是属于某一个输出类别，因而
$$
\sum_{y}P(y|x)=1
$$
因此，现在我们将上述问题转变成了一个有条件的最优化问题：
$$
\begin{aligned}
\max\ \ &{H(P)= -\sum_{x,y}\tilde{P}(x)P(y|x)\log{P(y|x)}}\\
s.t.\ \ &E_{P}(f)=E_{\tilde{P}}(f)\\
&\sum_{y}P(y|x)=1
\end{aligned}
$$
即，
$$
\begin{aligned}
\min\ \ &{-H(P)= \sum_{x,y}\tilde{P}(x)P(y|x)\log{P(y|x)}}\\
s.t.\ \ &E_{P}(f)=E_{\tilde{P}}(f)\\
&\sum_{y}P(y|x)=1
\end{aligned}
$$
这里，将约束最小化的原始问题转换为无约束最优化的对偶问题，通过对偶问题来求解原始问题。
首先，引入拉格朗日乘子$w_0,w_1,…,w_n$，定义拉格朗日函数$L(P,w)$,
$$
\begin{aligned}
L(P,w)=&-H(P)+w_0\left(1-\sum_y{P(y|x)}\right)+\sum_{i=1}^n{w_i(E_{\tilde{P}}(f_i)-E_{P}(f_i))}\\
=&\sum_{x,y}\tilde{P}(x)P(y|x)\log{P(y|x)}+w_0\left(1-\sum_y{P(y|x)}\right)+\sum_{i=1}^n{w_i(E_{\tilde{P}}(f_i)-E_{P}(f_i))}
\end{aligned}
$$
最优化原始问题的对偶问题是：
$$
\max_w{\min_P{L(P,w)}}
$$
由于$L(P,w)$是$P$的凸函数，原始问题的解与对偶问题的解是等价的。
将$L(P,w)$对$P(y│x)$求偏导数，得
$$
\begin{aligned}
\frac{\partial L(P,w)}{\partial P(y│x)}=&\sum_{x,y}{\tilde{P}(x)(\log{P(y|x)}}+1)-\sum_y{w_0}-\sum_{x,y}(\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y))\\
=&\sum_{x,y}\tilde{P}(x)\left(\log{P(y|x)}+1-w_0-\sum_i^nw_if_i(x,y)\right)
\end{aligned}
$$
令偏导数为0，解得
$$
\begin{aligned}
P(y|x)=&\exp({\sum_{i=1}^nw_if_i(x,y)+w_0-1})\\
=&\exp({\sum_{i=1}^nw_if_i(x,y)})\exp({w_0-1})
\end{aligned}
$$
由于
$$
\sum_{y}P(y|x)=1
$$
有，
$$
\sum_{y}P(y|x)=\sum_{y}\exp({\sum_{i=1}^nw_if_i(x,y)})\exp({w_0-1})=1
$$
得，
$$
\exp({w_0-1})=\frac{1}{\sum_{y}\exp({\sum_{i=1}^nw_if_i(x,y)})}
$$
令规范化因子$Z_w (x)$为
$$
Z_w(x)=\sum_{y}\exp({\sum_{i=1}^nw_if_i(x,y)})
$$
此时得到对偶问题的极小解为：
$$
P_w(y|x)=\frac{1}{Z_w(x)}e^{\sum_{i=1}^nw_if_i(x,y)}
$$
这就是我们所需要的最大熵模型下的概率估计。
我们再回顾下推导流程，
- 首先定义我们的约束条件：1、定义特征函数，约束为其在数据集上关于经验分布的期望与它们在模型中的数学期望相等；2、关于x的条件概率总和为1。
- 确定我们的目标：最大化在条件概率分布$P(Y|X)$上的条件熵，在约束上构建构建我们的最优化问题。
- 引进拉格朗日乘子，定义拉格朗日函数，通过求解对偶问题来求解原始问题。
实际上，对偶问题的极大化等价于最大熵模型的极大似然估计。
至此，我们已经得到了最大熵模型的目标估计，而模型中的最优参数则是对偶问题最大时的参数。
具体学习算法有改进的迭代尺度法（IIS）与拟牛顿法。
最大熵与逻辑回归
逻辑回归是最大熵对应类别为两类时的特殊情况，也就是当逻辑回归类别扩展到多类别时，就是最大熵。
其联系在于：指数簇分布的最大熵等价于其指数形式的最大似然界；二项式的最大熵解等价于二项式指数形式(sigmoid)的最大似然，多项式分布的最大熵等价于多项式分布指数形式(softmax)的最大似然。
因此为什么用sigmoid函数，那是因为指数簇分布最大熵的特性的必然性。
另外，逻辑回归模型与最大熵模型都属于对数线性模型。
优缺点
最大熵模型的优点有：
- 最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型,作为经典的分类模型时准确率较高。
- 可以灵活地设置约束条件，通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度。
最大熵模型的缺点有：
- 由于约束函数数量和样本数目有关系，导致迭代过程计算量巨大，实际应用比较难。