开发者学堂课程【大数据学习-数学基础及应用：导数、梯度、最优化方法】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/354/detail/4179
导数、梯度、最优化方法
内容介绍：
一、导数、梯度介绍
二、最优化方法及其应用
三、参考资料
一、导数、梯度介绍
1.导数(Derivative)是微积分学中重要的基础概念。一个函数在某一点的导数描述了这个函数这一点附近的变化率。导数的本质是通过极限的概念对函数进行局部的线性逼近。
当函数 f 的自变量在一点x上产生一个增量h时，函数输出值的增量与自变量增量h的比值在 h 趋于0时的极限如果存在，即为 f 在 x 处的导数，记作 f'(xo)。也可写作:
2.偏导数:一个多变量的函数的偏导数是它关于其中一个变量的导数，而保持其他变量恒定。
曲面上的每一点都有无穷多条切线经过这个点，描述这种函数的导数相当困难。偏导数就是选择其中一条切线，并求出它的斜率。
几何意义上偏导数即为函数在坐标轴方向上的变化率。将第一幅图曲面进行横截面切割就可以得到第二幅图曲线效果。
3.方向导数:对于多变量函数，自变量有多个，表示自变量的点在一个区域内变
动，不仅可以移动距离，而且可以按任意的方向来移动同一段距离因此，函数的变化不仅与移动的距离有关，而且与移动的方向有关，函数的变化率是与方向有关的，这也才有了方向导数的定义，即某一点在某一趋近方向上的导数值。
类似于偏导数，区别于：几何意义上方向导数为函数在某点沿着其他特定方向上的变化率，方向不一定是坐标轴的方向，也可能是其他任何坐标方向。
4.梯度:函数在某一点处的方向导数在其梯度方向上达到最大值，此最大值即梯度的范数。沿梯度方向，函数值增加最快。梯度也是一种特殊的方向导数。
二、最优化方法及其应用
1.最优化方法:研究在给定约束或者无约束情况之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。分为无约束化和有约束化两种形式，某些因素也通常被成为决策变量。指标称为目标量。
大部分的机器学习算法的本质都是建立优化模型。通过最优化方法对目标函数(或损失函数)进行优化，从而训练出最好的模型。常见最优化算法:
梯度下降法(Gradient Descent
牛顿和拟牛顿法(Newton's method &Quasi-Newton Methods
2.梯度下降法:最早最简单，也是最为常用的最优化方法。当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，不保证是全局最优解。
上图是非常理想的等梯度线，从该等梯度线布局中可以看出该函数是标准的凸函数。从 x0到 x1再到 x2线性搜索的过程，就是梯度下降的典型过程。中间的等梯度线代表梯度为0，即找到函数值最优的时候。
梯度下降优化思想:用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，越接近目标值，步长越小，前进越慢。
3.在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为批量梯度下降法和随机梯度下降法，以线性回归模型为例
损失函数：真实值和预测值差的平方和达到最小
拟和函数:相当于多项式求和
J(theta):损失函数
theta:参数，要迭代求解的值
m:训练集的样本个数
n:是特征的个数
3.1批量梯度下降的步骤
(1)将J(theta)对 theta 求偏导，得到每个 theta 对应的梯度
(2)最小化风险函数，所以按每个参数 theta 的梯度负方向，来更新每个 theta:
(3)从上式可以看到，每迭代一步都要用到训练集所有的数据，m 代表数据样本的数据，如果 m 很大那么可想而知这种方法的迭代速度会相当的慢。由于这个缺点就衍生出了随机梯度下降。
3.2随机梯度下降的步骤:与批量梯度下降最大的区别损失函数不是训练集所有的数据，而是只针对每个样本。
(1)损失函数对应的是训练集中每个样本的粒度
(2)每个样本的损失函数，对 theta 求偏导得到对应梯度，来更新 theta:（与批量梯度下降一样）
(3)随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大，可能只用到其中几千或者几万条样本，就将theta更新到最优解了。
缺点是不会用到所有的样本量
优点：虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结里往往是在全局最优解附近，适用于大规模训练样本情况。
4.牛顿法
（1）牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。牛顿法最大的特点就在于它的收敛速度很快。
一般求解的时候都是将其展开的泰勒级数的二阶导数这一项，所以他收敛速度很快是因为在提供一阶导前提下提供了二阶导，所以在求解的过程中在二阶导的前提下进行求解，所以收敛速度快。
（2）从几何上来看，之所以牛顿法比梯度下降法快速可以看下图。牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面;通常情况下，二次曲面的拟合会比平面更好所以牛顿法选择的下降路径会更符合真实的最优下降路径。
红色:牛顿法 绿色:梯度下降法
5.拟牛顿法:求解非线性优化问题最有效的的方法之一，也是求解非线性优化问题运用最多的。
一般的牛顿法在泰勒级数展开的时候会展开到二阶导的情况，所以在求解的过程中会计算并且保存非常复杂的 hessian 矩阵， Hessian 矩阵可以理解为以二阶导为元素的矩阵，在计算量和存储量上带来了很大的挑战，
所以拟牛顿本质思想是改善牛顿法每次需要求解复杂的上 Hessian 矩阵的逆矩阵的缺陷，它使用正定矩阵来近似 Hessian 矩阵的逆，从而简化了运算的复杂度。
这里的 Bk 是一个对称正定矩阵，取这个二次模型最优解作为搜索方向，并且得到新的迭代点。大大降低计算量。
常用的拟牛顿法有DFP算法和BFGS/L-BFGS算法
6.OWLQN 在 CTR（点击率，在计算广告中点击率是非常重要的指标）预测中的应用
（1）逻辑回归模型（明星模型）:在线性回归基础上，套用了一个逻辑函数。在各个地方都大量应用。
最大值永远接近1但不为1，最小值接近0不为0，天然表示概率为0-1之间。
P（y=1）表示用户点击广告的概率
P（y=0）表示用户不点击广告的概率
单个样本的后验概率：
原理为：用户不管点不点击广告，相当于伯努利分布的一种形式，概率密度函数。
（2）有了概率密度函数估计出参数最经典的方法就是最大似然法，也就是求函数的最大值，就出现了函数的求极值的情况：逻辑回归模型的极大似然函数：
表示的是单个后验样本概率，当有m个样本的时候，要将每个样本的后验概率连乘起来就得到第一个图片的极大似然函数，为了便于计算，又对似然函数取了 log，将乘方改成相乘的形式，并且在损失函数外侧加了 log，取了对数。最后的目标是使log似然达到最大，但通常情况下是对 log 似然取负值，将最大化改为最小化。
（3）似然最大化可以转化为最小化这个问题 构造了新的函数：
L（x）就是刚才定义的负方向的似然函数，r（x）是加入的正则项，Regularization term，用来对模型空间进行限根制，从而得到一个更“简单”的模型。如果只用l（x）在数据过多的情况下，很容易达到过拟合的状态，在用新数据线上拟合的时候预测效果会非常差，所以添加正则项。常用的正则项有两种：
L1-norm:模型参数服从 Laplace 分布
L2-norm:模型参数服从 Gaussian 分布
L1-norm 和 L2-norm 之间的一个最大区别在于前者可以产生稀疏解，这使它同时具有了特
征选挥的能力，此外，稀疏的特征权重更具有解释意义。
如果使用 L1函数，其中有不可导点，所以一般的梯度下降法，假设函数的所有部分都是可导的这种情况是不成立的，所以要使用新的参数求解方法对参数进行估计，这里就是引用 OWLQN 的原因。
（4）次导数及次微分
如果出现不可导的情况，如何继续求其导数以及微分，如下图
在点 x0（不可求导点）的次导数的集合是一个非空闭区间[a,b]，其中 a（趋近于 x0左侧极限）和 b（趋近于右侧极限），以下是求法：
他们一定存在，且满足 a≤b。所有次导数的集合[a，b]函数f在 x0的次微分。
存在这种不可导点对之前提到的 L-BFGS 算法做衍生，用虚梯度来替代
上面公式代表虚梯度取值，取值有三种情况，分别是大于零、小于零以及其他情况。
第一张图在左次梯度下大于零的情况下，x0 左次梯度大于零，右次梯度也大于零，因为右次梯度永远大于左次梯度，这时的虚梯度会选择左次梯度，左次梯度向着下降的方向前进。
第二张图是右次梯度小于零的情况，此时虚梯度的值会选择右次梯度。
如果不符合以上两种条件说明 x0的左次梯度和右次梯度他们的符号相反，这个时候就已经找到函数的最小点即 x0等于零的时候。
除了用虚梯度代替梯度以为 OWLQN 还加了限制：一维搜索要求不跨越象限：要求更新前权重与更新后权重同方向。因为用的是 L1的范数，所以在坐标轴的参数可能会得到零值，如果跨越的话会违背 L1算法的初衷。
三、参考资料
·结城浩，程序员的数学[1，2，3]，人民邮电出版社，2012
·Jorge Nocedal/Stephen Wright，Numerical Optimization，2000
·张跃辉，矩阵理论与应用，科学出版社，2011
·James M.Van Verth/Lars M.Bishop，Essential Mathematics for Games and Interactive Applications:A Programmer’s Guide，Morgan Kaufmann,2008
