0x01 梯度下降的算法思想梯度下降Gradient Descent是一种通用的优化算法能够为大范围的问题找到最优解。梯度下降的核心思想就是通过沿着目标函数的梯度负方向不断迭代更新参数从而使目标函数最小化。该算法被广泛应用于机器学习和 AI 中。若将目标函数视为一个超曲面梯度下降的过程即为从曲面上的某一点出发沿着坡度最陡的下坡方向一步步移动直到接近最低点。假设目标函数为J ( θ ) J(\theta)J(θ)其中θ ( θ 1 , θ 2 , … , θ n ) \theta(\theta_1, \theta_2, \dots, \theta_n)θ(θ1,θ2,…,θn)是待优化的参数组成的向量。首先梯度下降使用一个按一定规则初始化的θ \thetaθ值然后逐步改进每次走出一步尝试降低一点J ( θ ) J(\theta)J(θ)的值直到算法收敛。0x02 参数更新过程梯度∇ θ J ( θ ) \nabla_\theta J(\theta)∇θJ(θ)是一个向量其每个分量为函数对相应参数的偏导数即∇ θ J ( θ ) ( ∂ J ( θ ) ∂ θ 1 , ∂ J ( θ ) ∂ θ 2 , … , ∂ J ( θ ) ∂ θ n ) \nabla_\theta J(\theta)\left(\frac{\partial J(\theta)}{\partial \theta_1},\frac{\partial J(\theta)}{\partial\theta_2},\dots, \frac{\partial J(\theta)}{\partial \theta_n} \right)∇θJ(θ)(∂θ1∂J(θ),∂θ2∂J(θ),…,∂θn∂J(θ))梯度的方向表示函数在该点增长最快的方向而梯度的负方向则是函数值下降最快的方向。在每次迭代中参数按如下公式更新θ t 1 θ t − η ⋅ ∇ θ \theta_{t1}\theta_t-\eta\cdot\nabla_\thetaθt1θt−η⋅∇θ其中θ t \theta_tθt是第t tt次迭代后的参数值。η \etaη是学习率Learning Rate控制每次更新的步长。若学习率过低算法要经过大量迭代才能收敛耗费大量时间。若学习率过高算法可能直接越过极小值会导致算法震荡或发散。并不是所有目标函数都是碗状的。有些函数的形状可能会导致算法很难找到最小值。如果从下图的左边出发会陷入局部极小值。从右侧出发则会经过很长时间才能穿越整片高原。0x03 梯度下降的分类在机器学习中根据每次迭代使用的样本量梯度下降可分为三类类型定义与特点优缺点批量梯度下降BGD每次迭代使用全部训练数据计算梯度更新参数。收敛方向稳定但数据量庞大时计算成本高迭代速度慢。随机梯度下降SGD每次迭代仅使用一个样本计算梯度更新参数。计算效率高更新频繁但方向随机性大可能震荡或在最小值附近波动但具有随机性有助于跳出局部最小值。小批量梯度下降MBGD每次迭代使用一小批样本计算梯度更新参数。结合 BGD 和 SGD 的优点既保证收敛稳定性又提高计算效率实际中最常用。0x04 例题P1337 [JSOI2004] 平衡点 / 吊打XXX题目大意给定平面上n nn个点求它们的带权费马点。即求一个绳结所在点( x , y ) (x,y)(x,y)使得∑ i 1 n w i ( x i − x ) 2 ( y i − y ) 2 \sum_{i1}^n w_i\sqrt{(x_i-x)^2(y_i-y)^2}∑i1nwi(xi−x)2(yi−y)2绳结位置到所有点的加权欧拉距离之和最小。这一点可以参考其他题解的物理分析这里就不再赘述。Solution这道题明明是裸的梯度下降呀参数向量θ \thetaθ即为绳结坐标( x , y ) (x,y)(x,y)目标函数J ( x , y ) ∑ i 1 n w i ( x i − x ) 2 ( y i − y ) 2 J(x,y)\sum_{i1}^n w_i\sqrt{(x_i-x)^2(y_i-y)^2}J(x,y)∑i1nwi(xi−x)2(yi−y)2上面的柿子。先画个图看一下每一项。它是一个倒立的圆锥是单谷函数。因此整个目标函数也是单谷函数梯度下降保证收敛到全局最小值。注意到该函数在极小值处不可导因此应该忽略这样的不可导项。求出偏导数∂ J ( x , y ) ∂ x ∑ i 1 n w i ⋅ x − x i ( x − x i ) 2 ( y − y i ) 2 ∂ J ( x , y ) ∂ y ∑ i 1 n w i ⋅ y − y i ( x − x i ) 2 ( y − y i ) 2 \frac{\partial J(x,y)}{\partial x}\sum_{i1}^n w_i \cdot\frac{x-x_i}{\sqrt{(x-x_i)^2(y-y_i)^2}} \\ \frac{\partial J(x,y)}{\partial y}\sum_{i1}^n w_i \cdot\frac{y-y_i}{\sqrt{(x-x_i)^2(y-y_i)^2}}∂x∂J(x,y)i1∑nwi⋅(x−xi)2(y−yi)2x−xi∂y∂J(x,y)i1∑nwi⋅(x−xi)2(y−yi)2y−yi最后我们需要在算法执行过程中动态调整学习率来达到较好的效果这被称为学习率调度。这里采用如下方式进行学习率调度设η t \eta_tηt为第t tt次迭代后的学习率则η t 1 r ⋅ η t \eta_{t1}r\cdot\eta_tηt1r⋅ηt其中0 r 1 0r10r1为学习率衰减因子而初始学习率η 0 \eta_0η0为定值。不断迭代直到η e p s \etaepsηeps或∣ ∇ θ J ( θ ) ∣ e p s |\nabla_\theta J(\theta)|eps∣∇θJ(θ)∣eps即梯度向量的长度小于e p s epseps。这样一开始利用了较大学习率收敛快的优点执行到后面学习率逐渐减小有助与提高精度收敛到极小值。这样很好地平衡了不同学习率的优缺点。Code这里取η 0 100 , r 0.99 , e p s 10 − 6 \eta_0100,r0.99,eps10^{-6}η0100,r0.99,eps10−6。#includeiostream#includeiomanip#includecmathusingnamespacestd;constexprintN1005;constexprdoubleLR100.0,DECAY0.99,EPS1e-6;// 梯度下降超参数初始学习率、衰减因子、精度doublex[N],y[N],w[N];intn;pairdouble,doublegradient(doublecurX,doublecurY){// 计算梯度pairdouble,doublegrad{0.0,0.0};for(inti0;in;i){doubledxcurX-x[i];doubledycurY-y[i];doubledistsqrt(dx*dxdy*dy);if(distEPS)continue;// 避免除零错误grad.firstw[i]*dx/dist;grad.secondw[i]*dy/dist;}returngrad;}intmain(){cin.tie(0)-sync_with_stdio(0);doublecurX0.0,curY0.0,sumW0.0,lrLR;cinn;for(inti0;in;i){cinx[i]y[i]w[i];curXx[i],curYy[i],sumWw[i];}curX/sumW,curY/sumW;// 初始化为所有点加权平均位置玄学优化while(lrEPS){pairdouble,doublegradgradient(curX,curY);// 计算梯度向量doublegradLensqrt(grad.first*grad.firstgrad.second*grad.second);// 梯度向量的长度if(gradLenEPS)break;// 梯度足够小已收敛curX-lr*grad.first;curY-lr*grad.second;lr*DECAY;// 学习率调度}coutfixedsetprecision(3)curX curY;return0;}Update 2025.6.16修改一处公式错误。
