跳到主要内容

双变量梯度下降

梯度下降利用两个坐标方向上的斜率，寻找 f(x,y)f(x,y) 的最小值。先算一步，看看两个坐标怎样一起更新。

实例​

考虑一个用于演示的房间温度函数：

f(x,y)=85−190x2(x−6)2−y2(y−6)2,(x,y)∈[0,5]2.f(x,y)=85-\frac{1}{90}x^2(x-6)^2-y^2(y-6)^2, \qquad (x,y)\in[0,5]^2.

这个模型与上一篇的桑拿房模型不同，也不是经过标定的物理温度模型。房间的边界不能省略：若不限制定义域，这个多项式向下无界，便不存在可寻找的最冷点。

算出第一步​

从 (x0,y0)=(0.5,0.6)(x_0,y_0)=(0.5,0.6) 出发，取学习率 α=0.05\alpha=0.05。为方便求偏导，令 h(t)=t2(t−6)2h(t)=t^2(t-6)^2。于是 f=85−h(x)/90−h(y)f=85-h(x)/90-h(y)，且 h′(t)=4t(t−3)(t−6)h'(t)=4t(t-3)(t-6)，得到梯度

∇f(x,y)=(−4x(x−3)(x−6)90,  −4y(y−3)(y−6)).\nabla f(x,y)=\left(-\frac{4x(x-3)(x-6)}{90},\;-4y(y-3)(y-6)\right).

起点处有 ∇f(0.5,0.6)≈(−0.3055556,−31.104)\nabla f(0.5,0.6)\approx(-0.3055556,-31.104)。分别减去各分量的 0.050.05 倍：

x1=0.5−0.05(−1136)≈0.5152778,y1=0.6−0.05(−31.104)=2.1552.\begin{aligned} x_1&=0.5-0.05\left(-\frac{11}{36}\right)\approx0.5152778,\\ y_1&=0.6-0.05(-31.104)=2.1552. \end{aligned}

两个梯度分量都必须用旧点计算，再同时更新两个变量。新点仍在房间内，函数值从约 74.41837274.418372 降至 16.24827116.248271。

概念概述​

梯度 ∇f=(∂f∂x,∂f∂y)\nabla f=\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right) 把两个偏导数组成一个向量。梯度非零时，它指向函数瞬时增长最快的方向，其大小就是沿该方向每单位距离的最大变化率。梯度下降沿相反方向，即局部最陡下降方向移动。这只描述局部方向，不能保证任意有限步长都会让函数值下降，也不能保证一定到达最小点。

数学形式​

从当前点 (xk,yk)(x_k,y_k) 更新：

(xk+1,yk+1)=(xk,yk)−α∇f(xk,yk)=(xk,yk)−α(∂f∂x,∂f∂y)(xk,yk).\begin{aligned} (x_{k+1},y_{k+1}) &=(x_k,y_k)-\alpha\nabla f(x_k,y_k)\\ &=(x_k,y_k)-\alpha\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)_{(x_k,y_k)}. \end{aligned}

学习率 α\alpha 同时缩放两个方向上的位移。步长过大会越过最小值，过小则可能收敛缓慢。

双变量算法​

选择初始点 (x0,y0)(x_0,y_0)，计算梯度，反复按更新式移动。房间有盒约束时，每一步都要把新点保留在可行域内，可使用投影更新：

qk+1=Π[0,5]2(qk−α∇f(qk)),qk=(xk,yk),q_{k+1}=\Pi_{[0,5]^2}(q_k-\alpha\nabla f(q_k)), \qquad q_k=(x_k,y_k),

其中 Π\Pi 将各坐标截到 [0,5][0,5] 内。迭代时检查目标值下降和投影梯度残差

∥q−Π[0,5]2(q−α∇f(q))∥2α.\frac{\|q-\Pi_{[0,5]^2}(q-\alpha\nabla f(q))\|_2}{\alpha}.

同时设置迭代上限。迭代点变化小，本身不能证明到达了极小值。有盒约束时，不能只看原始梯度：边界最优点的梯度未必为零。即使投影残差很小，对于这个非凸问题也只是驻点检验。

挑战与注意事项​

这个模型还可以直接求出精确最小值。在 [0,5][0,5] 上，hh 在 33 处取得唯一最大值 8181。分别最大化被减去的两项，得到全局最小点 (3,3)(3,3)，f=3.1f=3.1。相比之下，若从 (0,0)(0,0) 开始，梯度为零，迭代会停在原地而到不了最小点。一般来说，梯度下降可能收敛到局部而非全局最小值；换用不同起点可减轻风险，但不能证明全局最优。

在 (3,3)(3,3) 处，Hessian 为 diag⁡(0.4,36)\operatorname{diag}(0.4,36)。对更新式作局部线性化，可得局部压缩的充分条件 0<α<1/180<\alpha<1/18。因此 0.050.05 已接近 yy 方向的稳定性上限，却在 xx 方向前进缓慢。从给定起点迭代 1000 步可近似得到 (3,3)(3,3)，但这次运行不能证明任意起点都会收敛。

探索关联

这篇笔记还没有文档关联。

同主题的其他笔记 (33)

打开关联网络