7.3.7 极大似然估计
最重要的是找到似然函数：
- 首先，假定已知 条件概率分布 ；然后，找到用训练模型的样本集，并根据这个样本集写出所有样本出现的概率表达式；
- 接下来，将表达式记作 条件概率分布 的似然函数，这就意味着：在 已知样本 的情况下，将概率表达式记为条件概率分布的似然函数，这样一来研究对象就变成了条件概率分布
- 原理：取什么样的分布才可以让似然函数最大？
- 强调三个点：
1.离散和连续的问题：上面所提的 原理 是基于离散分布的，因为离散分布可以谈及其概率问题，而对于连续分布则不能谈概率，只能通过密度最大化得到其估计；
2.研究对象是什么：似然函数的研究对象是分布（条件概率分布），也就是似然函数中的未知量，即我们所求的P(y|x)；
3.表达式形式：通常求出样本出现的概率为连乘形式——>为了简化用对数，这样就变成了求和式（此时成为对数似然）进而去求解极大似然估计。
-
过程详解：
现已知一个样本点(x,y)那么其对应概率就是Pw(y|x)m(m表示其出现的次数，m=NP(x,y))，接下来就是考虑所有的点：连乘起来，就得到了以下表达式：
然后为了简化，将上述表达式求个对数，并进行化简：
对于一个确定的训练数据集来说，N是不用考虑的。只需要计算后面那部分就行了。
对数似然函数实际上就是把我们的视角集中在 条件概率分布 上。但是如果只是集中在某些参数上，那么问题就能更进一步的简化，假如说现在集中在w上，直接把用w表示的条件概率带入到似然中就得到了：
这样一来就把对数似然函数完全用w表达出来了，也就是运用极大似然原理所得到的似然函数
在最大熵模型中，原始问题等价于对偶问题（最优化问题）：
这里的第二项括号里的p(y|x)求和必为1，所以第二项一定是0，可以去掉了
-
对于剩下的来说：
第一项：
会发现括号里的第一项可以和第二项的括号里的第一项抵消了，那么他们的求和就是：
在对上面式子里的第二项进行简化：（就是相当于上面关于y的条件概率求和为1）
接下来，根据最大熵模型找到了可以是目标函数最小的分布P(w)并带入到ψ(w)中看看是多少。
不难发现上面的算式和对数似然函数是一样的，这就说明了：
- 对偶函数等价于对数似然函数：
这样一来，接下来就是解函数最大值：w取何值时，函数取最大值？（共有三种方法：梯度下降法、牛顿法、迭代尺度法）
- 最大熵模型特点：
信息熵 表示所含信息的多少，是对于信息量的期望，算式为：
7.4优化算法
-
种类：
迭代尺度法是 专门计算最大熵的，书上还有个拟牛顿法，他和牛顿法的收敛速度更快些。牛顿法用的是二阶泰勒展开
7.4.1 （最速）梯度下降法
其关键在于：走一步看一步
- 算法流程：
不需要输入步长η，因为可以通过方法选出最优
-
应用：
最大熵模型最后就是要去求对数似然/对偶函数的极大值并输出参数w，此时的=这两个函数完全等价（证明过程在上边）；
实际上就是求得目标函数的极大值所对应的w并输出；
只需要在前面乘个-1就变成了求极小值。
转变后的目标函数：
-
具体算法：
特征函数和经验分布用于目标函数和梯度的计算；最后求出最优的w后要带入到Pw(x|y)中以获得最大熵模型所对应的 最优条件概率分布模型并输出
7.4.2 牛顿法
-
算法依据：迭代公式：
-
目的：求解方程根
将零点放大观看：
根据迭代思想，先取一个初始值，然后用迭代公式进行迭代；
此处选择初始值x0=1.4并计算g(x0)：
然后在x0处做切线并将其与x轴的交点记为x1：
如此循环，不断向零点接近：
-
算法：
-
求解极小值：
-
求解极小值算法：
比上面的算法多了个二阶导函数；这里的ε是针对于两次函数的差值而言的
注意：上述方法都是一元的，下面来讲解下多元函数的情况，多元函数的一阶导就是梯度向量，二阶导对应了矩阵（黑塞/海森矩阵）；
-
多元推广：
-
多元算法：这里都是向量形式
例子：
但是，由于逆矩阵在实际应用中求解起来比较麻烦，所以就改进成了拟牛顿法
7.4.3 拟牛顿法
海森矩阵问题： 肯定是个 对称矩阵
1.稠密矩阵：这种情况下求逆的计算量会很大；
2.矩阵的行列式为0：这种情况下矩阵不可逆；
所以拟牛顿法就找了一个海森矩阵的替代品。方法：通过二阶泰勒展开（对于x(k)来求一个矩阵Gk)
此处对x进行求导：（涉及到向量求导，好像和数值求导差不多）
接着带入一个具体值：
进行归类后变成：
就可以得到：yk=Hkδk（这个就是拟牛顿条件了，式子也可以变成Hk-1yk=δk）
-
搜索公式合理性：
从上面的式子中不难看出搜过公式和梯度下降的迭代公式有点像，这也就说明拟牛顿法是结合了牛顿法和梯度下降法的。梯度下降法的两个关键点：1.方向；2.步长；
而牛顿法中的方向就是-Hkgk记为pk(是个向量），步长则是通过 最速下降法 来求得：
此处由于用的是最速下降法，所以用的是一阶泰勒展开：
然后把x-x(k)=λpk带入并将其转化为H：
假设H(k)是正定的，那么它的逆 H-1(k)也是正定的，对应的二次型一定是大于0等，那意味着第二项自然是小于0的——>下个迭代点的f(x)必定<现在的f(x)—>这也就证明了它是满足梯度下降的合理性的
——>H(k)是一个对称正定矩阵
-
拟牛顿条件：
1.Hk-1yk=δk；
2.yk=Hkδk；
每个条件都可以引出一个算法，先来看下第一个条件的算法： -
DFP算法：（用于Hk-1yk=δk这个条件）
目的：为了求得Hk-1，将其记为Gk并进行迭代
1.选择Gk+1:
后面俩是Gk的基础上加的两个附加项，相当于ΔG，实际就代表了Gk和Gk+1之间的差值Δk，只不过就是分解为两个值来表示
为了 符合你和条件 ，两边同时乘上yk并令其等于δk（符合条件1）:
在进行一个变化：
这里的Pk和Qk得是对称的，才能进行上面的变化，
所以要用 向量内积 来进行构建他们俩：
这时候再成上个yk:
那么上面的转变就成立了；
同理可以得：
将上面求得的Pk和Qk带入到公式中得到了Gk+1：
算法：
此处有两个迭代公式（x的和G的），他们俩是交互进行的；
δk=x(k+1)-x(k);
yk=g(k+1)-g(k)
然后是第二个条件的算法：
-
BFGS算法：（用于yk=Hkδk这个条件）
注意：这里是直接对海森矩阵进行迭代更新， 不再是 其逆矩阵了，将跟新矩阵记为B；
和上面差不多的流程：
对Pk和Qk求表达式：
Pkδk=yk：
Qkδk=-Bkδk：
就得到了B的迭代公式：
算法：
注意第三步一开始那个公式就是pk=-Bk-1gk
-
Broyden算法：
定义：实际上就是前两个算法得出的，他们都是拟牛顿法的两个条件，就是让两个方法放在一个公式里，并让他们做一个线性组合：
Gk+1仍符合拟牛顿条件；当α=0时，这里就是BFGS算法，当α=1时，这里就是DFP算法——>这里是个折衷方法
-
应用：将拟牛顿法应用到最大熵模型中：
DFP算法：
（1）到（5）就是DFP算法，不过要求的是w；然后最后一步还要求一个最优模型
BFGS算法：
和上面一样。
上面两种方法的区别
- 梯度下降法：用的是 一阶泰勒展开，只考虑局部—>无全局，是平面问题（易理解和计算）；
- 牛顿法：用的是 二阶泰勒展开，不止考虑了局部方向，还考虑了变化程度（长远，少弯路），是二次曲面问题（考虑全面，但是计算较为麻烦）
拟牛顿法：集大成者⌓‿⌓
7.4.4 改进的迭代尺度法
先看下极大似然估计：
简单来说就是通过概率最大化来求出最符合的分类；
-
求极大值的方法：
1.求导并令导数为0，可以用牛顿法；
2.求极值，可用梯度下降和牛顿法；
3.迭代计算： -
迭代尺度法：
想法：希望下一个迭代值比上一个迭代值的似然函数要大，也就是下图所示：
这样一来，就从找w变成了找δ——>方法：算差值：
由于对数计算较为麻烦，所以改为计算上面这个算式的下界，看他是不是≥0即可，就要用到下面的不等式：-log α ≥ 1-α，有以下几种证明这个不等式的方法：
1.画图，不是瞎的都可以看出来；
2.进行计算，建立函数然后求最值就好；
这一来，就可以用这个不等式来求得刚刚的差值的下界了：
可以把不等式用在波浪线的地方，就有了：
于是乎原来的式子就化成了：
然后把Zw/w+δ(x)用规范化因子展开并进行约分后得到了：
这样一来就得到了
它代表了在已知参数w的情况下所对应的δ 的函数，这样我们只要找到合适的δ使得A(δ|w)>0就能够找到下一个迭代值
- 怎么找δ：按常理来先求个偏导：
发现上面求导后所得的函数第三项还包含有所有的δ，所以不得行；
这时候就引入了新的量：
他代表了(x,y)点满足特征的个数。
不难得到下面两个公式：
-
Jensen不等式：（机器学习中常用，还会用在EM算法上）
定义：:如果f是定义在实数区间[a,b]上的连续凸函数，x1,.....,xn∈[a,b]并且有一组实数λ1,...,λn≥0，满足 所有λi求和等于1 则有：（从凸函数概念所得的不等式）
f(x1)和f(x2)加权求和的值比先x1,x2加权求和后再求函数值大；在统计学上来说就是期望的函数值≤随机变量函数值的期望，也就是下面这个公式：
这样就得到了：
进而得到了新的下界并记为B(δ|w)然后对其求偏导：
其中
这样就可以得到了δi的方程：
-
IIS算法：
输出的w*需要先求得δ*；
第一步的时候先让初始值为wi=0，分子都是1，分母就是对应的y的个数，可以看出条件概率分布变成了等概率分布，这就是最大熵的思想：在一切未知的时候，我们先假设「分布式等概率模型」
