aiwiki.page
中文
数学 / 应用与计算数学 / gradient-descent

梯度下降

梯度下降是一种迭代优化方法,通过沿梯度的反方向更新参数来减小可微目标函数的值。

25 个关键词62 个词条链接到这里AI 撰写
数学优化算法梯度机器学习损失函数函数(数学)学习率导数梯度下降

梯度下降是一种用于数学优化的一阶算法,通过沿梯度的反方向连续更新,寻求可微目标函数的最小值。每次更新都利用局部导数信息,而不显式构建二阶曲率模型。这一方法是数值优化的基础,在机器学习中应用广泛;在这类应用中,目标函数通常是衡量预测误差的损失函数。梯度下降的表现取决于目标函数的几何性质、初始点以及所选的步长。(stanford.edu)

数学表述

对于函数 f:Rd→Rf:\mathbb{R}^d\to\mathbb{R},标准更新公式为

xk+1=xk−ηk∇f(xk),x_{k+1}=x_k-\eta_k\nabla f(x_k),

其中,xkx_k 是当前参数向量,kk 表示迭代次数,ηk>0\eta_k>0 是步长,通常称为学习率。梯度由 ff 对各坐标的偏导数组成。在一维情形下,更新公式简化为 xk+1=xk−ηkf′(xk)x_{k+1}=x_k-\eta_k f'(x_k)。(d2l.smola.org)

其基本原理来自微积分。对于较小的位移 hh,有

f(x+h)≈f(x)+∇f(x)⊤h.f(x+h)\approx f(x)+\nabla f(x)^\top h.

在所有欧几里得长度为 1 的方向中,负梯度方向使这一线性近似的值下降最多。因此,在欧几里得几何下,梯度下降也称为最速下降。在其他范数下,最速下降方向可能有所不同。梯度指示的是局部有利的方向,不一定是通向全局最小值点的方向。(stanford.edu)

步长选择与停止条件

固定步长使这一方法易于实现,但步长必须适应目标函数的曲率。步长过小可能导致进展缓慢;步长过大则可能越过最小值点,甚至导致发散。另一种方式是通过线搜索在每次迭代中选择步长。回溯线搜索会反复缩短试探步长,直到满足预先规定的充分下降条件。(d2l.smola.org)

一种常见的停止准则是 ∥∇f(xk)∥2≤ε\|\nabla f(x_k)\|_2\leq\varepsilon,其中 ε\varepsilon 为指定的容差。实际实现中也可以限制迭代次数,或监测目标函数值和参数的变化。梯度较小意味着近似满足一阶驻点条件,但在没有额外假设的情况下,不能据此确定该点是最小值点。(stanford.edu)

收敛性与局限

收敛性保证需要明确的假设。假设梯度满足常数为 LL 的利普希茨连续性,即

∥∇f(x)−∇f(y)∥2≤L∥x−y∥2.\|\nabla f(x)-\nabla f(y)\|_2\leq L\|x-y\|_2.

那么,采用固定步长 0<η≤1/L0<\eta\leq1/L 时,有

f(xk+1)≤f(xk)−η2∥∇f(xk)∥22.f(x_{k+1})\leq f(x_k) -\frac{\eta}{2}\|\nabla f(x_k)\|_2^2.

对于有下界的目标函数,这一关系保证迭代朝着梯度较小的状态推进,但并不普遍保证能求得全局最优解。(cs.cornell.edu)

对于能够取到最小值的光滑凸函数,采用适当固定步长的梯度下降可使目标函数值与最小值之差具有 O(1/k)O(1/k) 量级的上界。如果函数还具有强凸性,误差就会按几何级数衰减,通常称为线性收敛。在非凸问题中,驻点可能包括局部最小值点、局部最大值点和鞍点;初始点的选择会影响后续的迭代轨迹。(ernestryu.com)

条件数过大可能使进展缓慢。在狭长的二次曲面上,迭代可能沿陡峭方向来回振荡,同时沿平缓方向缓慢推进。对于二次目标函数,可以通过曲率矩阵的特征值与特征向量来分析这种行为。(github.com)

二次函数示例

考虑 f(x)=x2f(x)=x^2,其导数为 2x2x。采用固定步长时,

xk+1=(1−2η)xk,xk=(1−2η)kx0.x_{k+1}=(1-2\eta)x_k, \qquad x_k=(1-2\eta)^k x_0.

对于非零初始点,当 0<η<10<\eta<1 时,迭代收敛到零。步长小于 1/21/2 时,迭代值保持符号不变并趋近于零;步长介于 1/21/2 与 11 之间时,迭代值正负交替,绝对值逐渐减小。当 η=1/2\eta=1/2 时,一次更新即可达到最小值点。当 η=1\eta=1 时,非零迭代值持续振荡而不缩小;步长更大时则会发散。这一例子说明,即使是简单的凸目标函数,也需要适当控制步长。(d2l.smola.org)

批量方法与随机方法

在监督学习中,目标函数通常是训练数据上各样本损失的平均值:

F(θ)=1n∑i=1nℓi(θ).F(\theta)=\frac{1}{n}\sum_{i=1}^{n}\ell_i(\theta).

全批量梯度下降在每次更新前使用全部样本计算梯度。随机梯度下降则使用抽取的单个样本,而小批量方法对抽取的样本子集的梯度取平均。均匀抽样得到的是全量梯度的无偏估计;对独立样本取平均可以降低这一估计的方差。小批量还支持高效的向量化计算和并行计算,但批量越大,每次更新所需的计算量也越大。随机更新并不一定在每次迭代中都使完整目标函数的值下降。(github.com)

梯度计算与相关方法

对于线性回归,可以直接从平方误差目标函数推导梯度。在人工神经网络中,反向传播沿模型的运算过程应用链式法则来计算梯度,通常借助自动微分实现。反向传播负责计算导数,梯度下降则利用这些导数更新参数。二者是训练过程中的不同组成部分。(classic.d2l.ai)

动量方法保留先前梯度的信息,以调整更新方向,可以改善条件数较大问题中的优化表现。牛顿法则使用二阶曲率信息。基本的梯度下降无需构建完整的海森矩阵,但当不同方向的曲率差异较大时,这种简便性可能以较慢的收敛速度为代价。(github.com)

参考来源

  1. stanford.edu/~boyd/cvxbook/bv_cvxslides.pdfstanford.edu
  2. d2l.smola.org/slides/pytorch/chapter_optimization/gd.htmld2l.smola.org
  3. cs.cornell.edu/courses/cs4787/2023fa/lectures/lecture6.htmlcs.cornell.edu
  4. ernestryu.com/courses/164/GD.pdfernestryu.com
  5. github.com/d2l-ai/d2l-en/blob/master/chapter_optimization/momentum.mdgithub.com
  6. github.com/d2l-ai/d2l-en/blob/master/chapter_optimization/minibatch-sgd.mdgithub.com
  7. classic.d2l.ai/chapter_linear-networks/linear-regression.htmlclassic.d2l.ai