机器学习笔记（3）——最大熵模型

最大熵模型，就是在满足所有约束条件（已知部分知识）的模型中，选择一个在其中条件熵最大的作为最大熵模型。

在给出训练数据集的基础上，计算联合分布P（X，Y）的经验分布以及边缘分布P（X）的经验分布。用特征函数f（x，y）表示输入x和输出y之间的某种关系，是值为0，1的二值函数。计算特征函数关于经验分布P（X，Y）的数学期望，还有特征函数关于模型P（Y | X）以及边缘分布P（X）的数学期望。当模型能够获取训练集中的信息，那么假设这两个数学期望相等。也就是满足 ΣP（X，Y）*f（x，y）=  Σ P（Y | X）*P（X），这就是约束条件。满足这一约束条件的模型P（Y | X）会有多个，所以之后的工作就是在选出的模型中选择一个条件熵，即H（P）=  -ΣP（x）P（y | x）logP（y | x）最大的作为最大熵模型。

如何求解最大熵？

将最大值问题改为等价的求最小值问题

即满足约束条件下，求-H（P）=  ΣP（x）P（y | x）logP（y | x）的最小值。

这里用到了拉格朗日乘子法。下面应用了博主stardsd对此的解释，原博地址：https://www.cnblogs.com/sddai/p/5728195.html

设目标函数为f(x)，约束条件为h_k(x)，形如:

      　　s.t. 表示subject to ，“受限于”的意思，l表示有l个约束条件。

　　　则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述，这里主要讲拉格朗日法，因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。

　　　例如给定椭球:

　  　求这个椭球的内接长方体的最大体积。这个问题实际上就是条件极值问题，即在条件      下，求的最大值。

　　  当然这个问题实际可以先根据条件消去 z (消元法)，然后带入转化为无条件极值问题来处理。但是有时候这样做很困难，甚至是做不到的，这时候就需要用拉格朗日乘数法了。  

　　  首先定义拉格朗日函数F(x)：

　　　　　　　　  （ 其中λk是各个约束条件的待定系数。）                                                           

        然后解变量的偏导方程：

      　　　　......,

　　　如果有l个约束条件，就应该有l+1个方程。求出的方程组的解就可能是最优化值（高等数学中提到的极值），将结果带回原方程验证就可得到解。

　　　回到上面的题目，通过拉格朗日乘数法将问题转化为

　　　对求偏导得到

　　　联立前面三个方程得到和，带入第四个方程解之

　　　带入解得最大体积为：

　　　至于为什么这么做可以求解最优化？*上给出了一个比较好的直观解释。

      　举个二维最优化的例子：

    　　　　 min f(x,y)    

    　　　　　 s.t. g(x,y) = c

    　 这里画出z=f(x,y)的等高线（函数等高线定义见百度百科）：

       绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率，和等高线的法线平行。从梯度的方向上来看，显然有d1>d2。绿色的线是约束，也就是说，只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约束，f(x,y)的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束，最小值点应该在哪里呢？显然应该是在f(x,y)的等高线正好和约束线相切的位置，因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高线与目标函数的曲线相切的时候，可能取得最优值。

　　如果我们对约束也求梯度∇g(x,y)，则其梯度如图中绿色箭头所示。很容易看出来，要想让目标函数f(x,y)的等高线和约束相切，则他们切点的梯度一定在一条直线上(f和g的斜率平行)。

　　也即在最优化解的时候：∇f(x,y)=λ（∇g(x,y)-C)    （其中∇为梯度算子; 即：f(x)的梯度 = λ* g(x)的梯度，λ是常数,可以是任何非0实数，表示左右两边同向。）

      即：▽[f(x,y)+λ(g(x,y)−c)]=0λ≠0

　　那么拉格朗日函数： F(x,y)=f(x,y)+λ(g(x,y)−c) 在达到极值时与f(x,y)相等，因为F(x,y)达到极值时g(x,y)−c总等于零。

　　min( F(x,λ) )取得极小值时其导数为0，即▽f(x)+▽∑ni=λihi(x)=0，也就是说f(x)和h(x)的梯度共线。

　　简单的说，在F(x,λ)取得最优化解的时候，即F(x,λ)取极值（导数为0，▽[f(x,y)+λ(g(x,y)−c)]=0）的时候，f(x)与g(x) 梯度共线，此时就是在条件约束g(x)下，f(x)的最优化解。