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