[机器学习必知必会]梯度下降法

前言

梯度下降法（gradient descent）是求解无约束最优化问题的一种最常用的方法，它是一种迭代算法，每一步需要求解目标函数的梯度向量。

问题抽象

是上具有一阶连续偏导数的函数，要求解的无约束问题是:， 其中表示目标函数的极小值点

关键概念

• 迭代：选取适当初始值，不断迭代更新的 值，直至收敛
• 梯度下降：负梯度方向是使函数值下降最快的方向，我们在迭代的每一步都以负梯度方向更新的值
• 收敛：给定一个精度，在迭代的每一轮根据梯度函数计算梯度， 时认为收敛
• 学习率：也叫做步长，表示在每一步迭代中沿着负梯度方向前进的距离

直观理解

以下图为例，开始时我们处于黑色圆点的初始值（记为），我们需要尽快找到函数的最小值点，最快的方法就是沿着坡度最陡的方向往下走

算法细节

由于具有一阶连续导函数，若第次迭代值为，则可将在附近进行一阶泰勒展开：

其中在的梯度。
接着我们求出第次的迭代值:

其中是搜索方向，取负梯度方向， 是步长，需满足：

算法实现

• 输入：目标函数，梯度函数，计算精度
• 输出： 的极小值点
• 步骤:
  • 1）取初始值 ，置为0
  • 2）计算
  • 3）计算梯度，当时停止迭代，令 ;否则，令，求，使
  • 4）令，计算，当或时停止迭代，令
  • 5）否则，令，回到3）

算法调优

• 学习率：学习率太小时收敛过慢，但太大时又会偏离最优解
• 初始值：当损失函数是凸函数时，梯度下降法得到的解是全局最优解；当损失函数是非凸函数时，得到的解可能是局部最优解，需要随机选取初始值并在多个局部最优解之间比较
• 归一化：如果不归一化，会收敛得比较慢，典型的情况就是出现“之”字型的收敛路径

注意事项

• 当目标函数是凸函数时，梯度下降法是全局的最优解，一般情况下梯度下降法的解不一定是全局最优解
• 梯度下降法的收敛速度未必是最快的

Reference

图源：https://www.nxpic.org/article/id-330329
《统计学习方法》