本文首先介绍最大熵的原理及含义；接着在分类问题下介绍了最大熵模型的定义，约束条件以及学习（求解）的方法。[待补充]。

最大熵(Maximum Entropy)原理 ^{[1] [2] [3]}

熵

最原始的熵，是从热力学中引入的。

$\Delta S$表示Entropy , 即熵；而Q表示能量，T表示温度。

一位中国学者在翻译“Entropy”时，由于考虑“Entropy是能量与温度T的商，且与火有些关系”，就把“Entropy”翻译为了“熵”这个高大上的名字。

熵表示一个系统在不受外界外界干扰时其内部最稳定的状态。任何粒子的常态都是随机运动，也就是无序运动。如果要让粒子呈现有序化，必须耗费能量。所以，温度（热量）可以看做“有序化”的度量，而熵则可以看作无序化的度量。^[1]

在信息论中，熵特指信息熵。后面出现的熵均指信息熵。

信息熵的计算公式为：

其中X是一个随机变量，$p(x)$表示$X = x$时的概率。熵的取值范围为$0 \le H(x) \le \log(\left | X \right |)$。$\left | X \right |$指随机变量$X$的可能取值的数量。

关于信息熵的含义，有很多种解释，比如说“熵是接收的每条消息中包含的信息的平均量“^[4].我们把$\frac{1}{p(x)}$称作自信息量，这个还是比较有意义的。一般来说，在固定长度的信息中，出现概率越少的东西，表达的信息往往是越多的。所以把概率取倒数、再取对数来表示自信息量——如果某个字符出现概率为1，那么这个字符什么信息也没有；如果对数以2为底，自信息量就是完整表示这个变量信息所需要的比特数。信息量乘以概率，再求和，比较明显的求期望（平均值）公式。所以能够表示信息的平均量。

其他说法如：”信息熵定义了信息的不确定程度“，”定义了信息的混乱度“。这个倒过来想也是有道理的：我们刚刚的例子，当信息全为一个字符时，熵最小，为0。此时信息的不确定程度、混乱度是最低的。这个比较直观。当我们的X服从均匀分布，即每种可能值都是等可能的，可想而知这种情况下信息也是最混乱的，最不确定的（如果我们拿到一段信息，去猜其可能的值，当各可能值是等可能的，那么猜测最不确定；如果知道哪个值的概率最大，那么是更加确定的），此时从熵公式的数学定义上也可以说明，此时熵也是最大的($\log(\left | X \right |)$)。由此我们得出一个结论：”熵的大小，正比于信息的不确定程度（信息的混乱度）“。

强调一遍，”熵越大，代表信息越不确定，越混乱“。

最大熵原理

有了前面的铺垫，最大熵原理就比较好说了：最大熵原理，就是在满足约束条件下，对未知分布最随机、最不确定的推断。

定义包含两点：

1. 要满足约束

2. 最随机，最不确定的推断

关于”最随机，最不确定“的理解：

前面说过，最不确定的情况，就是随机变量满足均匀分布的情况。所以，最大熵也是求一个在约束条件下最均匀的分布。这说明最大熵在预测未知分布时，是未做任何有偏假设的。

最大熵模型

最大熵模型，就是在分类问题下，用最大熵原理求一个满足约束条件的分类模型，并将该模型作为分类最优的模型。

分类问题下，我们的模型定义为刻画类别$Y$在随机变量$X$出现下的分布——输入一个实例$x$（抽象描述为向量$\vec x$），给出其属于各类别的概率——给出后验概率$P(Y | X)$ 。

”后验概率“一说，为个人观点，未在参考资料上看到。对应于先验概率，后验概率可以表述为：在接受了$x$的信息后更新后的各类别的概率。

目标

目标当然是满足约束条件下熵最大的模型。约束条件在下一小节讲。这里我们首先确定，我们要度量什么熵呢。

答案是条件熵$H(Y | X)$。

模型对于随机变量$X$分布的估计，就是给出在给定$x$实例的条件下其属于各类别的条件概率的大小。形式化的描述，就是$p(y|x)$。通过度量该条件概率的熵，即条件熵，我们可以从熵的角度给出最匹配样本集的模型——使条件熵最大的模型。当条件熵最大时，能够保证该模型在约束条件下对$X$的分布有最均匀的估计，这满足最大熵原理。

条件熵的公式为：

关于条件熵公式的推导，更多详细定义，可以查看1 , 或者搜索维基百科。这里只直接记住结论，暂时对该公式过程不清楚。

在样本集中，我们用经验分布$\tilde p(x)$近似表示$X$原始分布$p(x)$ ， 故我们的条件熵公式可以写为：

其中$\tilde p(x) = \frac{count(x)}{count(all)}$，在样本集给定条件下为已知。

经过这样的变化，条件熵仅与我们的模型目标$p(y | x)$有关。

我们的模型目标定义为

约束条件

引入特征函数

我们的模型，是要去表述随机变量X与Y的关系，可以用$P(X , Y)$来描述。不过，如果我们从实例这个角度去描述，显然数据是很稀疏的，很难在有限数据集上去良好的刻画随机变量X与Y的分布。在这样的情况下，我们引入特征函数这一个概念。特征函数，在概率论上与分布函数是存在密切关系的（看了一些，不过依然不清楚，待以后可能再补充）。特征函数可以完整的刻画随机变量的分布情况，且比分布函数具有更好的性质。当然具体到实际的机器学习问题上，特征函数就是从某个方面刻画了实例与对应类别的关系。

比如分词，对实例（“我”，“S”），一个特征函数可能是：

另一个特征函数是：

针对一个实例，从不同方面抽取特征，来刻画随机变量的内在属性。这可以认为是特征函数的作用。

回到我们的目标，要去表述随机变量X、Y间的关系，我们选择用特征函数$f(X,Y)$来刻画。

更进一步地，用特征函数的期望来刻画。

特征函数上如何约束

我们从样本集的角度以及待求取的模型的角度分别刻画随机变量X、Y。即是，要求 从样本集求得的特征函数期望与从模型角度求得的特征函数期望相等。

我们将从样本集角度求得的特征函数期望称为特征函数的经验期望，记为$E_{\tilde p}(f(x,y))$；将模型角度求得的期望称为特征函数的模型期望，记为$E_{p}(f(x,y))$。

当模型足够好时，二者应该相等 ，故在特征函数上的约束可以表示为：

其中m为特征函数数量。

再说这两个期望该如何求。

期望的公式可以表示为$E(X) = \sum_x{ x p(x)}$ ,其中$p(x)$是$X=x$时的概率。由此我们的特征函数的期望可以表示为:

经验期望和模型期望，就是分别从各自的方面去刻画$p(x,y)$。

对经验期望，认为$ p(x,y) = \tilde p(x,y) = \frac{Count(x,y)}{Count(all)} $

则($\ref{expform}$)从样本集分布的角度可以表示为：

对模型期望，认为$ p(x,y) = \tilde p(x) p(y|x) = \frac{Count(x)}{Count(all)} p(y|x)$

则($\ref{expform}$)从模型预测的角度可以表示为：

故($\ref{expequal}$)可表示为

最后再表述一遍其包含的含义：经验期望表示了训练样本的统计现象的内在属性，同时也要求由模型得到的模型期望能够完整地展现这些统计现象的内在属性。

其他约束

除了上述特征函数期望的约束外，还有从概率意义上的约束，即要求：

最大熵模型的学习^[3]

最大熵模型的学习问题就是最大熵模型的求解问题。而最大熵模型求解可以形式化为约束最优化问题（线性约束下的非线性函数最优化问题）。

给定训练集$\{ (x_1 , y_1 ) , (x_2 , y_2) , \cdots , (x_N , y_N)\}$，以及特征函数$f_i(x,y)$ , $i = 1 , 2 , \cdots , m $ ，最大熵模型的学习等价于约束最优化问题。

按照最优化问题的习惯，我们将求最大值问题改写为等价的求最小化问题(第一步转化)：

到此，最大熵模型的学习问题就转化为了求解($\ref{target}$)($\ref{expconstrain}$)($\ref{probconstrain}$)这一约束条件下的最优化问题。该最优化问题的解，就是最大熵模型学习的解。

我们要将约束下的最优化问题转化为无约束最优化的对偶问题，通过求解对偶问题来求解原始问题。

1

首先，引入拉格朗日乘子（Lagrange）$w_0 , w_1 , w_1 , \cdots , w_m$，定义拉格朗日函数$L(P,w)$ :

定义拉格朗日函数后，则原始约束条件下最优化问题可转化为无约束最优化问题：

($\ref{originprob}$)称为最优化的原始问题。

2

接着，我们先求解对偶问题($\ref{dualprob}$)中极小项，即$min_{p \in C}L(P,w)$。该函数是关于$w$的函数^*，记为：

将$\Psi(w)$称为对偶函数，其解记为

为什么$\Psi(w)$是关于w的函数？ $L(P,w)$本是$P$（即$p(y|x)$）和$w$的函数，但$min_{p \in C}$运算相当于求出了$P$的值，将其转为仅与$w$有关。当然只有经过这样的处理，外层的$max_{w}$才合理。

很明显，对$P$($p(y|x)$)求偏导，并令导数为0即可求出该关于w的函数$P_{w}$ 。

注意其中的一些技巧： 把$\sum_y{w_0}$变为$\sum_{x,y}{\tilde p(x) w_0}$ ；两个连加运算符内的符号可以在变量不相关时可以更换其位置。

我们令偏导为0，就求得了$p_w$ ，即$\min_{p \in C} L(P,w)$

我们把$e^{1 - w_0}$先定义为$Z_w(x)$，则($\ref{metemp}$)可以表示为

又由于有$\sum_y{p(y|x)} = 1$ ， 我们对上式左右对y求和式，则左边为1，变为：

有

把上面的结论总结一下！

经过上面的推导，我们得到了最大熵模型的表示：

其中

$Z_x(w)$被称为归一化因子（或者规范化因子），保证$\sum_y {P_w(y|x)}$和为1；$f_i(x,y)$是第$i$个特征函数，$w_i$是对应该特征函数的权值。

上述表明了最大熵模型的表示，但我们的最终目标是求最大熵模型，不要忘了上面的对偶问题中，我们只求了$\ref{dualfunc}$ , $\Psi(w) = min_{p \in C}{p(y|x)}$，还有后面的$max_w{\Psi(w)}$

3

第三步,将刚刚求得的模型，即$P_w(y|x)$带入到原始目标——对偶函数$\Psi(w)$中，有

带入约束条件 $\sum_y{p(y|x)} = 1$ 有：

带入$ p(y|x) = \frac{1}{Z_w(x)} e^{\sum_{x,y}x_i f_i(x,y)}) $

消去两项 ,

根据 $\sum_y{p(y|x)} = 1 $ ， 对$\sum_{x,y} \tilde p(x) \frac{1}{Z_w(x)}e^{\sum_{i=1}^m w_i f_i(x,y)} \log Z_w(x) $对$y$求和式

由于$\tilde p(x) $, $\log Z_w(x)$与$y$无关，故

有：

要使$\Psi(w)$最大，与2中思路相同——将$\Psi(w)$对$w$求导，令导数为0即可，即

求得的结果是权值$w$的值，即

《统计学习方法》书上没有再带入公式求导来直接得到一个关于w的代数表达式，不知道是太麻烦还是认为没有必要。在实际工程求解中，即后面书中介绍的，是使用IIS（improved iterative scaling , 改进的迭代尺度法）以及拟牛顿法来求解最后的 w 。

总结最大熵模型学习的步骤

在书上附了一个练习，在具体实例下做了完整的上述3个步骤。这里再总结一下：

1. 一些列问题的转化。

   1. 写出目标$H(y|x)$ , 约束（特征函数期望相等，概率和为1）。

   2. 将目标取反，使用拉格朗日乘子，将约束最优化转为无约束最优化问题($ L(P,w) $)。

   3. 使用极小极大($min_{w}max_{p} L(P,w)$)原始问题表示该优化问题，此为原始问题。

   4. 由于-H(y|x)为凸函数，极小极大的原始问题，转为求极大极小的对偶问题($max_w min_p L(P,w)$)。

2. 求对偶问题内部的极小问题。得到最大熵模型的表示$P_w(y|x)$。

   1. 称$min_p L(P , w)$为对偶问题($\Psi(w)$)

   2. 求对偶问题的解。由于是求最小，就是对其求导，令导数为0。求得对应的$P$的表示($P_w = \arg_p min \Psi(w)$)。

3. 求对偶问题外部的极大问题。得到最终的模型权值向量$w^*$ 。

   1. 把2步求得的最大熵表示$P_w(y|x)$带入对偶问题$\Psi(w)$中

   2. 对$\Psi(w)$ 求导，令其为0，得到对偶问题取得最大值时的$w^*$

根据后续理解，在实际使用中，我们只需要记住最大熵模型的表示形式，即$p(y|x) = \frac{1}{Z_w(x)} \exp(\sum_{i=1}^m w_i f_i(x,y))$。然后带入到$\Psi(w)$中，使用IIS或者拟牛顿法迭代求解即可。

[1] 最大熵模型中的数学推导

[2] 条件随机场综述

[3] 李航 · 《统计学习方法》

[4] 维基百科