梯度下降 | 彩潭有鲤的札记

type

status

date

slug

summary

梯度

在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。比如函数，分别对求偏导数，求得的梯度向量就是，简称或者。对于在点的具体梯度向量就是 .或者，如果是3个参数的向量梯度，就是，以此类推。

那么这个梯度向量求出来有什么意义呢？

从几何意义上讲，就是函数变化增加最快的地方。具体来说，对于函数，在点，沿着梯度向量的方向就是的方向是增加最快的地方。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，也就是的方向，梯度减少最快，也就是更加容易找到函数的最小值。

梯度下降与梯度上升

在机器学习算法中，在最小化损失函数时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数，和模型参数值。反过来，如果需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。

梯度下降法和梯度上升法是可以互相转化的。比如需要求解损失函数的最小值，这时需要用梯度下降法来迭代求解。但是实际上，可以反过来求解损失函数的最大值，这时梯度上升法就派上用场了。

梯度下降法算法

梯度下降的直观解释

比如我们在一座大山上的某处位置，由于不知道怎么下山，于是决定走一步算一步，也就是在每走到一个位置的时候，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。这样一步步的走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能不能走到山脚，而是到了某一个局部的山峰低处。

梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。

梯度下降的相关概念

步长（Learning rate）：步长决定了在梯度下降迭代的过程中，每一步沿梯度负方向前进的长度。用下山的例子，步长就是在当前这一步所在位置沿着最陡峭最易下山的位置走的那一步的长度

特征（feature）：指的是样本中输入部分，比如2个单特征的样本，则第一个样本特征为，第一个样本输出为

假设函数（hypothesis function）：在监督学习中，为了拟合输入样本，而使用的假设函数，记为。比如对于单个特征的个样本

，可以采用拟合函数如下：

损失函数（loss function）：为了评估模型拟合的好坏，通常用损失函数来度量拟合的程度。损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。在线性回归中，损失函数通常为样本输出和假设函数的差取平方。比如对于个样本，采用线性回归，损失函数为：

表示第个样本特征，表示第个样本对应的输出，为假设函数

梯度下降法的代数方式描述

先决条件：确认优化模型的假设函数和损失函数

比如对于线性回归，假设函数表示为，其中为模型参数，为每个样本的个特征值。这个表示可以简化，增加一个特征，这样

同样是线性回归，对应于上面的假设函数，损失函数为：

损失为什么求平均？好处：不管样本和批量多大，梯度差不多使得调学习率好调（除以谁都没关系，只要最小化损失）

此外常数1/2不会带来本质上的区别，知识在形式上简单一些，表现为对损失函数求导之后常数系数为1

算法相关参数初始化：

主要是初始化，算法终止距离以及步长。在没有任何先验知识的时候，可以将所有的初始化为0，步长初始化为1，在调优的时候再优化。

算法过程

确定当前位置的损失函数的梯度，对于：

用步长乘以损失函数的梯度，得到当前位置下降的距离，即，对应于前面登山例子中的某一步

确定是否所有的，梯度下降的距离都小于，如果小于则算法终止，所有的即为最终结果，否则进入步骤4

更新所有的，对于，其更新表达式如下，更新完毕后继续转入步骤1

用线性回归的例子来具体描述梯度下降，假设样本是，损失函数如前面先决条件所述：

步骤1中对于的偏导数计算如下：

由于样本中没有上式中令所有的为1

步骤4中的更新表达式如下：

可以看出当前点的梯度方向是由所有的样本决定的，加是为了好理解。由于步长也为常数，所以这里可以用一个常数表示

梯度下降法的矩阵方式表述

先决条件：确认优化模型的假设函数和损失函数

对于线性回归，假设函数的矩阵表达方式为：

假设函数为的向量，为的向量，里面有个代数法的模型参数。为维的矩阵。代表样本的个数，代表样本的特征数。

损失函数的表达式为：，样本的输出向量，维度为

算法相关参数初始化： 向量可以初始化为默认值，或者调优后的值。算法终止距离，步长和之前一样

算法过程

确定当前位置的损失函数的梯度，对于向量，其梯度表达式如下：

用步长乘以损失函数的梯度，得到当前位置下降的距离，即，对应于前面登山例子中的某一步

确定向量里面的每个值,梯度下降的距离都小于如果小于则算法终止，当前向量即为最终结果。否则进入步骤4

更新向量，其更新表达式如下，更新完毕后继续转入步骤1

还是用线性回归的例子来具体描述梯度下降：

损失函数对于向量的偏导数计算如下：

步骤4中向量的更新表达式如下：

这里面用到了矩阵求导链式法则和两个矩阵求导的公式

公式1：

公式2：

梯度下降的算法调优

在使用梯度下降时，需要进行调优。哪些地方需要调优呢？

步长选择：可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。

算法参数的初始值选择：初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。

归一化：由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征，求出它的期望和标准差，然后转化为：

这样特征的新期望为0，新方差为1，迭代速度可以大大加快。

梯度下降法大家族（BGD，SGD，MBGD）

批量梯度下降法（Batch Gradient Descent）

批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新。

由于有个样本，这里求梯度的时候就用了所有个样本的梯度数据。

随机梯度下降法（Stochastic Gradient Descent）

随机梯度下降法，和批量梯度下降法原理类似，区别在与求梯度时没有用所有的个样本的数据，而是仅仅选取一个样本来求梯度。对应的更新公式是：

随机梯度下降法批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

那么，有没有一个中庸的办法能够结合两种方法的优点呢？有！这就是小批量梯度下降法。

小批量梯度下降法（Mini-batch Gradient Descent）

小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于个样本，采用个样本来迭代，。对应的更新公式是：

假设

伪代码形式为：

Repeat{

for i=1, 11, 21, 31, ... , 991{

}

梯度下降法和其他无约束优化算法的比较

在机器学习中的无约束优化算法，除了梯度下降以外，还有最小二乘法，此外还有牛顿法和拟牛顿法。

梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。

梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解。相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长。