1. 最大熵原理

   最大熵原理是概率模型学习的一个准则，其认为学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。

   通常用约束条件来确定概率模型的集合，然后在集合中选择熵最大的模型。

   直观地，最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是等可能的。最大熵原理通过熵的最大化来表示等可能性，因为当X服从均匀分布时熵最大。

2. 最大熵模型

   最大熵原理应用到分类得到最大熵模型。

   给定训练集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，联合分布P(X,Y)以及边缘分布P(X)的经验分布都可以由训练数据得到：
$$
   \widetilde{P}(X=x,Y=y)=\frac{count(X=x,Y=y)}{N}
   \\ \widetilde{P}(X=x)=\frac{count(X=x)}{N}
$$
   用特征函数f(x,y)描述输入x和输出y之间的某一个事实，特征函数是一个二值函数，当x与y满足某一事实时取1，否则取0。例如，可以令特征x与标签y在训练集出现过时取1，否则取0。

   特征函数f(x,y)关于经验分布$\widetilde{P}(X=x,Y=y)$的期望值为：
$$
   E_{\widetilde{P}}(f)=\sum_{x,y}\widetilde{P}(x,y)f(x,y)
$$
   特征函数f(x,y)关于模型P(Y|X)与经验分布$\widetilde{P}(x)$的期望值为：
$$
   E_{P}(f)=\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)
$$
   如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即：
$$
   \sum_{x,y}\widetilde{P}(x,y)f(x,y)=\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)
$$
   将上式作为模型学习的约束条件，条件数量对应特征函数个数，设所有满足约束条件的模型集合为：
$$
   C=\{P|\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)=\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y),\quad i=1,2,...,n\}
$$
   其中n为特征函数个数。

   定义在条件概率分布P(Y|X)上的条件概率熵为：
$$
   H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\ln{P(y|x)}
$$
   模型集合C中条件熵H(P)最大的模型称为最大熵模型。

3. 最大熵模型的学习

   最大熵模型的学习过程就是求解最大熵模型的过程，等价于求解以下最优化问题：
   $$
   \max H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\ln{P(y|x)}
   \\ s.t. \qquad \sum_{x,y}\widetilde{P}(x,y)f_i(x,y)=\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y),\quad i=1,2,...,n
   \\ \sum_{x,y}P(y|x)\widetilde{P}(x)=1
   $$
   （上式中最后一个约束条件与《统计学习方法》中给出的不同，参考https://zhuanlan.zhihu.com/p/83765331，我认为书中给出的有误，而应该像上式这样才能得出最后的结果。）

   按照最优化问题的习惯，求解与上述问题等价的$\min -H(p)$。

   引入拉格朗日乘子$w_0,w_1,...,w_n$将上述带约束条件的最优化问题转化为无约束的最优化问题，定义拉格朗日函数：
   $$
   L(P,W)=-H(P)+w_0(1-\sum_{x,y}P(y|x)\widetilde{P}(x))+\sum_{i=1}^nw_i(\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y))
   \\ = \sum_{x,y}\widetilde{P}(x)P(y|x)\ln{P(y|x)} +w_0(1-\sum_{x,y}P(y|x)\widetilde{P}(x))+\sum_{i=1}^nw_i(\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y))
   $$
   类似于**SVM**一节，这里最优化的原始问题是：
   $$
   \min_{P\in{C}}\max_wL(P,w)
   $$
   对偶问题是：
   $$
   \max_w\min_{P\in{C}}L(P,w)
   $$
   在上式内部的最小化部分固定w，此时L(P,w)是关于P的函数，用$\theta(P)$表示，对P(y|x)求偏导数得：
   $$
   \frac{\partial{\theta(P)}}{\partial{P(y|x)}}=\widetilde{P}(x)(1+\ln{P(y|x)})-\widetilde{P}(x)w_0-\widetilde{P}(x)\sum_{i=1}^nw_if_i(x,y)
   \\ = \widetilde{P}(x)(1+\ln{P(y|x)}-w_0-\sum_{i=1}^nw_if_i(x,y))
   $$
   令偏导数等于0，因为$\widetilde{P}(x)>0$，所以$1+\ln{P(y|x)}-w_0-\sum_{i=1}^nw_if_i(x,y)=0$，解得：
   $$
   P(y|x)=\frac{e^{\sum_{i=1}^nw_if_i(x,y)}}{e^{1-w_0}}
   $$
   由于$\sum_yP(y|x)=1$，得到P(y|x)关于w的表达式为：
   $$
   P_w(y|x)=\frac{1}{Z_w(x)}e^{\sum_{i=1}^nw_if_i(x,y)}
   \\ Z_w(x)=\sum_ye^{\sum_{i=1}^nw_if_i(x,y)}
   $$
   由上式表示的模型$P_w=P_w(y|x)$就是最大熵模型，w是最大熵模型的参数向量，每一维度为对应特征函数的权重。
   
   令$\boldsymbol{w}=[w_1,w_2,...,w_n]^T, \boldsymbol{f(x,y)}=[f_1(x,y),f_2(x,y),...,f_n(x,y)]$，则：
   $$
   \sum_{i=1}^nw_if_i(x,y)=\boldsymbol{w}^T\boldsymbol{f(x,y)}
   $$
   将$P_w(y|x)$用w表示代入$L(P,W)$的表达式并结合$\sum_{x,y}P(y|x)\widetilde{P}(x)=1$得：
   $$
   L(P,W)=\sum_{x,y}\widetilde{P}(x)P(y|x)(\boldsymbol{w}^T\boldsymbol{f(x,y)}-\ln{Z_w(x)})+\\ 
   \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_{x,y}\widetilde{P}(x)P(y|x)\boldsymbol{w}^T\boldsymbol{f(x,y)}
   \\ = \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_{x,y}\widetilde{P}(x)P(y|x)\ln{Z_w(x)}
   $$
   因为：
   $$
   \sum_{y}\widetilde{P}(x)P(y|x)\ln{Z_w(x)}=\widetilde{P}(x)\ln{Z_w(x)}
   $$
   所以：
   $$
   L(P,W)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_w(x)}
   $$
   所以最大熵模型可以转化为极大化上述函数。接下来考虑$P_w(x,y)$的对数似然函数，即：
   $$
   L_{\widetilde{P}}(P_w)=\ln \prod_{x,y}P(y|x)^{\widetilde{P}(x,y)}=\sum_{x,y}\widetilde{P}(x,y)\ln P(y|x)
   \\ = \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_{x,y}\widetilde{P}(x,y)\ln Z_w(x)
   $$
   因为：
   $$
   \sum_{y}\widetilde{P}(x,y)\ln Z_w(x)=\ln Z_w(x)\sum_{y}\widetilde{P}(x,y)=\ln Z_w(x)\widetilde{P}(x)
   $$
   所以：
   $$
   L_{\widetilde{P}}(P_w)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_w(x)}
   $$
   综上，极大化$L(P,w)$等价于最大熵模型的极大似然估计。

4. 基于改进的迭代尺度法（IIS）进行最大熵模型的学习

   IIS的想法是：假设最大熵模型当前的参数向量是$\boldsymbol w$，我们希望找到一个新的参数向量：$\boldsymbol w+\boldsymbol \delta$，使得模型的对数似然函数增大。不断重复这一过程直到找到对数似然函数的最大值。

   更新前后的对数似然函数改变量为：
   $$
   L_{\widetilde{P}}(P_{w+\delta})-L_{\widetilde{P}}(P_w)=(\sum_{x,y}\widetilde{P}(x,y)(\boldsymbol{w+\delta})^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_{w+\delta}(x)})-\\
   (\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_w(x)})
   \\=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln \frac{Z_{w+\delta}(x)}{Z_w(x)}
   $$
   利用不等式$-\ln \alpha \ge 1-\alpha$，得：
   $$
   L_{\widetilde{P}}(P_{w+\delta})-L_{\widetilde{P}}(P_w) \ge \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1 - \sum_{x}\widetilde{P}(x)\frac{Z_{w+\delta}(x)}{Z_w(x)}
   \\=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{\boldsymbol \delta ^T\boldsymbol {f(x,y)}}
   $$
   令$A(\boldsymbol \delta|\boldsymbol w)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{\boldsymbol \delta ^T\boldsymbol {f(x,y)}}$为对数似然函数的改变量的一个下界，因为$\boldsymbol \delta$是一个n维向量，而$A(\boldsymbol \delta|\boldsymbol w)$在e的指数部分有$\boldsymbol \delta$，所以若此时求偏导会导致导数的每一个分量都有$\boldsymbol \delta$。因此，尝试寻找一个新的下界，使得指数部分只存在$\boldsymbol \delta$的单个分量。

   令$f^\#(x,y)=\boldsymbol 1^T\boldsymbol {f(x,y)}$即(x,y)处特征出现的次数，则：
   $$
   A(\boldsymbol \delta|\boldsymbol w)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{f^\#(x,y) \frac{\boldsymbol \delta ^T\boldsymbol {f(x,y)}}{f^\#(x,y)}}
   \\=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{f^\#(x,y) \sum_{i=1}^n\delta_i\frac{f_i(x,y)}{f^\#(x,y)}}
   $$
   由于$\frac{f_i(x,y)}{f^\#(x,y)}\ge0, \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}=1$且e的指数函数为下凸函数，则由琴生不等式得：
   $$
   e^{f^\#(x,y) \sum_{i=1}^n\delta_i\frac{f_i(x,y)}{f^\#(x,y)}} \le \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}e^{f^\#(x,y)\delta_i}
   $$
   所以：
   $$
   A(\boldsymbol \delta|\boldsymbol w) \ge sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}e^{f^\#(x,y)\delta^i}
   $$
   令$B(\boldsymbol \delta|\boldsymbol w) = \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}e^{f^\#(x,y)\delta^i}$为对数似然函数改变量的一个新下界，将其对$\boldsymbol \delta$的任一分量求导得：
   $$
   \frac{\partial B(\boldsymbol \delta|\boldsymbol w)}{\partial \delta_i}=\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x,y)e^{f^\#(x,y)\delta_i}
   $$
   令偏导数等于0得到：
   $$
   \sum_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x,y)e^{f^\#(x,y)\delta_i}=E_{\widetilde P}(f_i)
   $$
   依次对$\boldsymbol \delta$的分量求上式的解即可解出$\boldsymbol \delta$。

   为简化求解过程，一般假设$f^\#(x,y)\delta_i=M$为一常数，即假设对任意的(x,y)，特征出现的次数相同。那么$\delta_i$可显式得出：
   $$
   \delta_i=\frac{1}{M}\ln \frac{E_{\widetilde P}(f_i)}{E_P(f_i)}
   $$
   若$f^\#(x,y)\delta_i$不为常数，则需要通过数值计算求解，如使用牛顿法迭代求解。

5. 补充

   一般实现时，以训练集中出现过的所有的$(i,feature_i,label)$为特征函数，除了在该点取1，其他地方均取0。其中feature为原始特征，i为原始特征索引。所以最大熵模型的特征函数数量与训练集规模、原始特征数量成正比，所以会特别慢，甚至sklearn里面都没有提供它的实现。

   

