Maximum Entropy.
1. 熵
熵(entropy)既是不确定性的度量，又是信息的度量。对于某个事件，其熵越大，事件的不确定性越大，我们能从中获得的信息量也越大。若用概率分布$p(x)$描述事件，则离散形式和连续形式的熵分别计算如下：
\[\begin{aligned} S & = -\sum_{x}^{}p(x) \log p(x) \\ S & = -\int_{x}^{}p(x) \log p(x)dx \end{aligned}\]上式中的$\log $通常采用自然对数，也可以用$2$为底。一般地，任何大于$1$的底都是成立的，相当于改变了信息的“单位”。
在定义熵时，我们希望能够构造出一个表示信息量的公式。上述公式并不是灵光一现得到的，而是通过人为定义衡量信息量的“熵”应该有的性质，从而推导出来的。下面以离散形式为例介绍这个推导过程。
“熵”既然用来表示一个概率分布$p(x)$的信息量，则它应该有以下性质：
① 熵是概率分布$p(x)$的函数，并且是光滑函数。
② 熵具有可加性：
\[S[p(x)] = \sum_{x}^{} f(p(x))\]③ 当X和Y是独立随机变量时，有：
\[S[p(x)p(y)] = S[p(x)] + S[p(y)]\]由上述三条性质，即可确定熵的表达式。假设X和Y是二元随机变量，X的概率分布为$p,1-p$，Y的概率分布为$q,1-q$，XY的联合概率分布为$pq,(1-p)q,p(1-q),(1-p)(1-q)$，则按照上述性质，应有：
\[\begin{aligned}& f(pq)+f((1-p)q)+f(p(1-q))+f((1-p)(1-q)) \\&= f(p)+f(1-p)+f(q)+f(1-q) \end{aligned}\]等式左端是自变量的积的形式，右端是单个自变量的形式，不妨通过取对数运算把乘积变成求和。设$f(x)=h(x) \log x$，则有：
\[\begin{aligned} &h(pq) \log (pq)+h((1-p)q) \log ((1-p)q)\\+&h(p(1-q)) \log (p(1-q))+h((1-p)(1-q)) \log ((1-p)(1-q)) \\=& h(p) \log (p)+h(1-p) \log (1-p)+h(q) \log (q)+h(1-q) \log (1-q) \end{aligned}\]上式整理得：
\[\begin{aligned} &[h(pq)+h(p(1-q))-h(p)] \log (p)\\+&[h(pq)+h((1-p)q)-h(q)] \log (q) \\+ &[h((1-p)q)+h((1-p)(1-q))-h(1-p)] \log (1-p) \\+& [h(p(1-q))+h((1-p)(1-q))-h(1-q)] \log (1-q) \\=&0 \end{aligned}\]注意到若$h(\cdot)$取线性函数，则上式每一项的系数为$0$，等式自然满足。因此不妨取$h(x)=\alpha x$，则$f(x)=\alpha x \log x$，对应熵的表达式：
\[S[p(x)] = \sum_{x}^{} \alpha p(x) \log p(x)\]上式中的$\alpha$数值并不重要，只影响信息量的单位，其符号比较重要，因此增加性质：
④ 信息量越大，熵越大。
根据定义④，确定事件的熵应该比不确定事件的熵小。对于确定事件，其熵$S = \sum_{x}^{} \alpha \log 1 = 0$；则对于不确定事件，应满足：
\[S[p(x)] = \sum_{x}^{} \alpha p(x) \log p(x) > 0\]注意到$p(x) \in [0,1]$，因此$\alpha<0$，不妨取$-1$，此即熵的计算公式。
一些特殊的熵：
- 联合熵：多元分布的熵(衡量多元分布的信息量)
- 条件熵：条件分布的熵(衡量已知边缘分布的条件下联合分布的信息量)
2. 最大熵原理 The Maximum Entropy Principle
最大熵原理(Maximum Entropy Principle)指出对于一个未知的概率分布，在只掌握其部分知识的前提下，应选取符合这部分知识的同时使得熵最大的概率分布形式。
(1) 离散形式的最大熵原理
对于某个概率分布$p(x)$，通过生活经验或先验信息可能会获得该分布的部分知识，将其以期望形式给出约束：
\[E[f(x)] = \sum_{x}^{} p(x)f(x) = \tau\]注意到$f(x)=1,\tau=1$时该约束是概率之和为$1$，是一个平凡的约束。一般地，假设有$k$个约束，则最大熵原理等价于一个带有约束的极值问题，采用拉格朗日乘子法求解：
\[\begin{aligned} L(p(x),\lambda) = &-\sum_{x}^{}p(x)\log p(x)-\lambda_0(\sum_{x}^{} p(x)-1)-\lambda_1(\sum_{x}^{} p(x)f_1(x) -\tau_1)\\&- \cdots -\lambda_k(\sum_{x}^{} p(x)f_k(x) -\tau_k) \end{aligned}\]对上式求偏导令其为零$\frac{\partial L}{\partial p(x)}=0$，可得：
\[- \log p(x) -1-\lambda_0-\lambda_1f_1(x)- \cdots -\lambda_kf_k(x)=0\]解得：
\[p(x) = e^{-1-\lambda_0-\sum_{i=1}^{k}\lambda_if_i(x)}\]注意到$\sum_{x}^{} p(x)=1$，因此：
\[\sum_{x}^{} p(x)=\sum_{x}^{} e^{-1-\lambda_0-\sum_{i=1}^{k}\lambda_if_i(x)} = \sum_{x}^{}e^{-1-\lambda_0}e^{-\sum_{i=1}^{k}\lambda_if_i(x)}=1\]因此$e^{-1-\lambda_0}=\frac{1}{\sum_{x}^{}e^{-\sum_{i=1}^{k}\lambda_if_i(x)}}$，将其分母记为归一化因子$Z$，代回原式可得：
\[p(x) = \frac{e^{-\sum_{i=1}^{k}\lambda_if_i(x)}}{\sum_{x}^{}e^{-\sum_{i=1}^{k}\lambda_if_i(x)}} = \frac{1}{Z}e^{-\sum_{i=1}^{k}\lambda_if_i(x)}\]将$p(x)$的表达式代入：
\[\sum_{x}^{} p(x)f_i(x) - \tau_i = 0, \quad (i=1,2,...,k)\]即可解出未知的$\lambda_i$。然而对于一般的$f_i(x)$，上式并没有解析解，甚至数值求解都比较困难。
(2) 连续形式的最大熵原理
对于连续形式的最大熵原理，其求解过程和结果与上一节类似，即求解如下约束最优化问题：
\[\begin{aligned} L(p(x),\lambda) = &-\int_{x}^{}p(x)\log p(x)dx-\lambda_0(\int_{x}^{} p(x)dx-1)-\lambda_1(\int_{x}^{} p(x)f_1(x)dx- \tau_1)\\&-...-\lambda_k(\int_{x}^{} p(x)f_k(x)dx- \tau_k) \end{aligned}\]求解结果如下：
\[p(x) = \frac{e^{-\sum_{i=1}^{k}\lambda_if_i(x)}}{\int_{x}^{}e^{-\sum_{i=1}^{k}\lambda_if_i(x)}dx} = \frac{1}{Z}e^{-\sum_{i=1}^{k}\lambda_if_i(x)}\]求解未知的$\lambda_i$仍然需要将$p(x)$的表达式代入：
\[\int_{x}^{} p(x)f_i(x)dx - \tau_i = 0, \quad (i=1,2,...,k)\]一些特殊形式的连续型最大熵原理可以求得解析解，下面介绍两种形式。
⚪ 已知变量x的均值 $f(x)=x$
($x$的取值为$[0,+∞)$)此时解的形式为：
\[p(x) = \frac{1}{Z}e^{-\lambda x}\]先求归一化因子$Z$：
\[Z = \int_{0}^{+∞} e^{-\lambda x} dx = \frac{1}{\lambda}\]则概率分布可以表示成：
\[p(x) = \lambda e^{-\lambda x}\]引入均值$\tau$约束：
\[\tau = \int_{x}^{} p(x)xdx = \int_{0}^{+∞} \lambda e^{-\lambda x}xdx = \frac{1}{\lambda} \int_{0}^{+∞} e^{-t}tdt = \frac{1}{\lambda}\]故所求概率分布可以表示成：
\[p(x) = \frac{1}{\tau} e^{-\frac{x}{\tau}}\]⚪ 已知变量x的均值和方差 $f_1(x)=x,f_2(x)=x^2$
此时解的形式为：
\[p(x) = \frac{1}{Z}e^{-\lambda_1x-\lambda_2x^2}\]先求归一化因子$Z$：
\[\begin{aligned} Z &= \int_{-∞}^{+∞} e^{-\lambda_1x-\lambda_2x^2} dx = \int_{-∞}^{+∞} e^{-\lambda_2(x+\frac{\lambda_1}{2\lambda_2})^2+\frac{\lambda_1^2}{4\lambda_2}} dx \\ &= e^{\frac{\lambda_1^2}{4\lambda_2}} \int_{-∞}^{+∞} e^{-(\sqrt{\lambda_2}t)^2} \frac{dt}{\sqrt{\lambda_2}} \\ &(\text{由 } \int_{-∞}^{+∞} e^{-x^2}dx=\sqrt{\pi}) \\ &= \sqrt{\frac{\pi}{\lambda_2}}e^{\frac{\lambda_1^2}{4\lambda_2}} \end{aligned}\]则概率分布可以表示成：
\[p(x) = \sqrt{\frac{\lambda_2}{\pi}}e^{-\frac{\lambda_1^2}{4\lambda_2}}e^{-\lambda_1x-\lambda_2x^2}\]引入均值$\tau_1$和方差$\tau_2$约束：
\[\begin{aligned} \tau_1 &= \int_{x}^{} p(x)xdx \\ &= \int_{-∞}^{+∞} \sqrt{\frac{\lambda_2}{\pi}}e^{-\frac{\lambda_1^2}{4\lambda_2}}e^{-\lambda_1x-\lambda_2x^2}xdx \\ &= \sqrt{\frac{\lambda_2}{\pi}}e^{-\frac{\lambda_1^2}{4\lambda_2}} \int_{-∞}^{+∞} e^{-\lambda_2(x+\frac{\lambda_1}{2\lambda_2})^2}e^{\frac{\lambda_1^2}{4\lambda_2}}xdx \\ &= \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2(x+\frac{\lambda_1}{2\lambda_2})^2} (x+\frac{\lambda_1}{2\lambda_2}-\frac{\lambda_1}{2\lambda_2})d(x+\frac{\lambda_1}{2\lambda_2}) \\ &= \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2t^2} tdt + \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2t^2} (-\frac{\lambda_1}{2\lambda_2})dt \\ &= 0+\sqrt{\frac{\lambda_2}{\pi}} (-\frac{\lambda_1}{2\lambda_2}) \sqrt{\frac{\pi}{\lambda_2}} = -\frac{\lambda_1}{2\lambda_2} \end{aligned}\] \[\begin{aligned} \tau_2 &= \int_{x}^{} p(x)x^2dx \\ &= \int_{-∞}^{+∞} \sqrt{\frac{\lambda_2}{\pi}}e^{-\frac{\lambda_1^2}{4\lambda_2}}e^{-\lambda_1x-\lambda_2x^2}x^2dx \\ &= \sqrt{\frac{\lambda_2}{\pi}}e^{-\frac{\lambda_1^2}{4\lambda_2}} \int_{-∞}^{+∞} e^{-\lambda_2(x+\frac{\lambda_1}{2\lambda_2})^2}e^{\frac{\lambda_1^2}{4\lambda_2}}x^2dx \\ &= \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2(x+\frac{\lambda_1}{2\lambda_2})^2}[(x+\frac{\lambda_1}{2\lambda_2})^2-\frac{\lambda_1}{2\lambda_2}(x+\frac{\lambda_1}{2\lambda_2})+\frac{\lambda_1^2}{4\lambda_2^2}]d(x+\frac{\lambda_1}{2\lambda_2}) \\ &= \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2t^2}t^2dt + \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2t^2}(-\frac{\lambda_1}{2\lambda_2}t)dt + \sqrt{\frac{\lambda_2}{\pi}} \int_{-∞}^{+∞} e^{-\lambda_2t^2}(\frac{\lambda_1^2}{4\lambda_2^2})dt \\ &= \sqrt{\frac{\lambda_2}{\pi}}\frac{1}{\lambda_2\sqrt{\lambda_2}}(0+\frac{\sqrt{\pi}}{2})+0+\sqrt{\frac{\lambda_2}{\pi}}\frac{\lambda_1^2}{4\lambda_2^2}\sqrt{\frac{\pi}{\lambda_2}} = -\frac{\lambda_1^2+2\lambda_2}{4\lambda_2^2} \end{aligned}\]联立上式可求得$\lambda_1=-\frac{\tau_1}{(\tau_2-\tau_1^2)}$,$\lambda_2=\frac{1}{2(\tau_2-\tau_1^2)}$，故所求概率分布可以表示成：
\[p(x) = \sqrt{\frac{1}{2\pi (\tau_2-\tau_1^2)}}e^{-\frac{(x-\tau_1)^2}{2(\tau_2-\tau_1^2)}}\]上式即均值为$\tau_1$,方差为$\tau_2-\tau_1^2$的正态分布。
3. 最大熵模型
最大熵模型将分类问题建模为条件分布，将模型的输入和输出都看作随机变量，即求给定输入$x$的条件下输出$y$的概率分布$p(Y|X)$，求解过程依据最大熵原理，即求下述条件熵的极值：
\[S(Y|X) = S[p(x,y)] - S[p(x)]\]输入样本的分布$p(x)$是未知的，但是可以通过对已有样本的大量统计得出其经验分布。因此求条件熵的最大值等价于求$S[p(x,y)]$的最大值。
人为定义输入样本的特征(通常把输入的每个维度看作一个特征)，若输入样本的第$d$维特征满足某一条件(如大于某数值)，且该样本的分类类别为$c$，则可以构造特征函数：
\[\chi(x,y) = \begin{cases} 1, \text{ 当x的第d维特征满足一定条件且y=c时} \\ 0, \text{ 其他情况} \end{cases}\]统计满足该特征函数的样本数比例$\tau=\frac{N_{\chi}}{N}$，则可以引入约束：
\[E[\chi(x,y)] = \sum_{x,y}^{} p(x,y)\chi(x,y) = \tau\]一般地，引入$k$个特征函数作为约束，上式为约束极值问题，由最大熵原理可以得到：
\[p(x,y)=\frac{1}{Z}e^{-\sum_{i=1}^{k}\lambda_i \chi_i(x,y)}, \quad Z=\sum_{x,y}^{} e^{-\sum_{i=1}^{k}\lambda_i \chi_i(x,y)}\]若最终关注$p(y|x)$，结果为：
\[p(y|x) = \frac{p(x,y)}{p(x)} = \frac{1}{Z \times p(x)}e^{-\sum_{i=1}^{k}\lambda_i \chi_i(x,y)}\]最大熵模型形式简单，但求解困难，一般需要通过数值方法求解，一些求解算法可参考Referecne。
