7.3 最大熵模型：拉格朗日乘子法

最大熵模型：在待选集合C中挑选条件熵最大的条件概率分布（P），并且符合约束条件，P是一个分布，因为是一个分类问题，对于条件概率而言，应该是在x的所有取值上的条件概率和为1，这是关于它是分布的约束。
接下来在熵里面找到最大值对应的条件概率分布。

目的：使f(x)最小的向量x
约束条件：k+l个

简化如下：
f(x)是最优化问题里的目标函数，有n个未知量。ci(x)和hj(x)是相应的约束条件，每个约束条件前面都加一个拉格朗日乘子。
因为ci(x)和hj(x)分别有k+l个约束条件，所以乘子也有k+l个。
所以L包含了n+k+l个未知量，α是k维向量，β同理

最大熵模型：原始问题

考虑关于x的函数，取L的最大值，是对于α和β求L的最大值，找到使L最大的α和β，这样α和β确定了，只剩下x，这个函数就是关于x的。（对哪些未知量求最大值，那些未知量就是确定的了，剩下那个未知量就是得到的关于这个未知量的最终函数了。）

将这个函数记作θP，P是对应原始问题Primal。

θP在有约束的情况下等于目标函数f(x)，其他情况下等于正∞
约束条件里ci(x)是<=0的，如果有一个ci(x)>0，因为αi也大于0，一定可以找到αi，是的使得αici趋于+∞
约束条件里hj(x)=0，如果有hj(x)≠0，也可以找到相应的βj，使βjhj趋于+∞

什么时候使αici(x)得到最大值呢？ci(x)最大值是0，什么时候可以取0，也就是相应αi都取0的时候。同样的hj(x)=0，有这两个约束条件，L=f(x)

原始问题：求目标函数的最小值
目标函数：

求它max，就是求负的它min。统一为f(x)

最大熵模型：对偶问题

对偶问题是为了更好解决原始问题提成
目的：求L的min→对x求最小值
如果对x求最小，函数就是关于α和β的函数

这里的角标D，是对偶dual的首字母。

先对x求min，得到θD，再对它求α、β的max，就是对偶问题d。
d比p*求起来简单

求maxθd，依旧<=minθp
maxθd=d，minθp=p
d<=p
关注点是什么时候相等：

α、β、x*是最优解的话，和下面五条互为充分必要条件。

第一条：L的偏导数为0，这样就知道为什么f、ci、hj是连续可微了，因为要求偏导

最大熵模型的学习问题

已知数据：

除了在T中训练出N个模型，模型还得满足n个特征函数（n个约束）

目的：找到条件概率分布
这样知道x用概率分布函数就知道y

怎么实现概率分布函数的训练？

H(P)是想求的概率分布所对应的熵，特征函数是作为条件出现的。一共n+1个约束条件。

拉格朗日函数L(P,ω)

什么时候原始问题和对偶问题的最优解相同？

凹函数、凸函数

熵函数是严格的凹函数（上凸函数）

对偶问题：
先求拉格朗日函数的min，再求max

先解决min：

对概率分布P求偏导
所得函数是关于拉格朗日乘子的，记作Ψ(ω)，ω包括n+1个拉格朗日乘子：ω0-ωn

每给定一个ω，伴随着一个条件概率分布，记作Pω(y|x)。所以条件概率分布用拉格朗日乘子表示出来了。

可以用规范化因子来表示解

对偶问题的外部极大化问题：

希望找到使Ψ(ω)最大的ω

找到ω，就可以得到对应的条件概率：

例题解释最大熵模型学习过程：

使熵最大化，就是负熵最小化
约束条件在经验分布（波浪线）上：

将目标函数和约束条件写入拉格朗日函数：

因为只有一个特征函数，所以拉格朗日乘子有ω0和ω1
转化成对偶问题：

min考虑求偏导，分别对P(y1)…P(y5)求偏导
内部min问题得到了Ψ(ω)
解决外部极大化问题：

求偏导

最大熵模型：极大似然估计

对应最大熵模型问题，也可以用极大似然的方法估计条件概率分布，去解决分类问题

极大似然估计：找到似然函数
假定已经知道了条件概率分布，再找到样本集，写出所有样本出现的概率表达式，在已知分布的情况下，求条件概率分布的似然函数。那么取什么分布使得似然函数最大呢

①极大似然原理基于离散分布，对应离散分布可以谈概率问题。但连续概率分布只能谈密度，只能“密度最大化”得到估计值

②研究对象？也就是似然函数的对象，是条件概率分布，是似然函数中的未知量，在x已知时y的条件概率分布

③表达式的形式。求出样本出现的概率，是连乘的形式，为了简化运算，往往求对数，通过对数化，就化乘除为加减，最后得到求和式，似然函数变成对数似然，用这个求解极大似然估计

最大熵模型，它的对数似然函数是什么？

解决最大熵模型的对偶问题，先求min L（P，ω），可以得到关于ω的函数：Ψ（ω）

因为条件概率在y上的求和为1，所以Ψ（ω）第二项为0，简化后：

求解函数的max，也就是ω取什么时Ψ（ω）有max，有三种优化方法：梯度下降法，牛顿法，迭代尺度法

最大熵模型其实就是求解对数似然函数或者说对偶函数的max

最大熵模型的特性：

7.4 最大熵模型：优化算法 -- 最速梯度下降法

梯度下降法和牛顿法是经典，迭代尺度法是专为最大熵模型设计

梯度下降法迭代公式：

用的是一阶泰勒展开

梯度下降包括行走的方向和步长。因为是下山，所以是负梯度，也就是下降最快的方向。方向×步长类似于时间×速度，发生的就是位移

最速下降法，选择一个最优步长，使得函数值min，得到新的迭代点的位置min

（第五步中转（3）为转（2））
输入：因为要求min，所以要有目标函数，粗体θ表示多元。梯度中如果是一元就直接求导，如果是多元就对每个参数求偏导。不需要输入步长，后面可以通过方法选一个最优的，给计算精度ε作为停止条件。
输出：f(θ)取min的时候参数θ*

最大熵模型其实就是求解对数似然函数的max，然后将ω输出。

想找到目标函数的max所对应的ω

但是梯度下降法是求min，所以在目标函数前加负号，就变成求min了，新的目标函数记f（ω）

这个ω是一个n维的参数向量
依次对每个ω求偏导，是梯度向量

对于最大熵模型，梯度下降法具体的算法：
先猜一个初始值

还有输出最优模型，也就是在最优参数下对应的条件概率分布

7.4 最大熵模型：优化算法 -- 牛顿法

牛顿法最初是为了求平方根

每次在相应点处求切线，然后求切线与x轴的交点。切线过上一个迭代点（x(k)，g(x^(k))），斜率是这点的导函数值，就得到了切线方程

令y=0，得到交点

θ（k+1）就是切线与x轴的交点的表达式
牛顿法：

一个函数可微，那么求它的导函数=0，就能得到极小值点，f’(x)=0 也就是g(x)=0，也就是求函数的根

一阶导函数也就是梯度

多元的情况下，一阶导函数就是梯度向量，二阶导函数对应矩阵

拟牛顿法：改进牛顿法

gk是第k个迭代点处的梯度向量，Hk-1是Hessian矩阵的逆，在k个迭代点处Hessian矩阵的逆

找Hk-1的替代

牛顿法算法的依据是迭代公式：

而拟牛顿法是想找到式子中Hk-1的替代

如图展示拟牛顿法中步长和方向，与迭代公式中方向的不同

要进行搜索，就是找最优步长，找最优步长对应的梯度下降法叫最速下降法，找到使函数值最小的步长，加上方向，就可以进行迭代

Hk的条件：对称正定矩阵

拟牛顿条件延伸出DFP算法
将Hk-1记作G，对这个矩阵进行迭代

△G表示Gk+1与Gk之间的差值

拟牛顿法：DFP算法

BFGS算法
利用的另一个拟牛顿条件：

此处对Hk矩阵进行更新，而不是它的逆

Broyden算法

迭代尺度法

P~和fi已知，只有ω未知
于是对数似然函数变为ω的函数：

找到最大的似然值，对应的参数ω就是我们要找的ω*代入最大熵模型就得到结果

迭代就是让下一次的似然函数值比上一次大，找到参数δ

最简单就是算差值：

新得到：

是已知ω情况下关于δ的函数

改进的迭代尺度法IIS：