梯度下降法
1️⃣

梯度下降法

梯度下降法的基本思想
目标函数：min⁡x∈Rnf(x)\min_{x\in\mathbb{R}^n} f(\mathbf{x})，f具有一阶连续偏导数。
负梯度方向是使函数值下降最快的方向
根据泰勒展开f(x+Δx)≈f(x)+∇f(x)TΔxf(\mathbf{x+\Delta x})\approx f(\mathbf{x})+\nabla f(\mathbf{x})^T\Delta x
当Δx=−λ∇f(x)\Delta x=-\lambda\nabla f(\mathbf{x})时，有f(x+Δx)<f(x)f(\mathbf{x+\Delta x})<f(\mathbf{x})，λ>0\lambda>0为学习率或步长
一维优化问题：定长梯度下降法
采用固定的步长λ\lambda（学习率）的梯度下降法，但步长λ\lambda不宜太大或太小
迭代过程：
x(k+1)=x(k)−λf′(x(k))x^{(k+1)}=x^{(k)}-\lambda f'(x^{(k)})
多维优化问题：最速下降法
每次迭代选择合适的步长λk\lambda_k，使得目标函数在当前搜索方向上得到最大程度的减少
即转化为一维优化问题
min⁡λkf(x(k)−λk∇f(x(k)))\min_{\lambda_k}f\left(\mathbf{x}^{(k)}-\lambda_k\nabla f(\mathbf{x}^{(k)})\right)
再用梯度下降法或牛顿法求解。
有意思的是，最速下降法每次更新的轨迹都和上一次垂直，且只要∇f(x(k))≠0\nabla f(\mathbf{x}^{(k)})\ne0，则f(x(k+1))<f(x(k))f(\mathbf{x}^{(k+1)})<f(\mathbf{x}^{(k)}).
notion image
例：二次型目标函数的最速下降法
二次型
f(x)=xTAx,A为对称矩阵f(\mathbf{x})=\mathbf{x}^TA\mathbf{x},A为对称矩阵f(x1,x2,…,xn)=a11x12+a22x22+…+annxn2+2a12x1x2+2a13x1x3+…+2a(n−1)nxn−1xn\begin{aligned}f(x_1,x_2,\ldots,x_n)&=a_{11}x_1^2+a_{22}x_2^2+\ldots+a_{nn}x_n^2\\&+2a_{12}x_1x_2+2a_{13}x_1x_3+\ldots+2a_{(n-1)n}x_{n-1}x_n\end{aligned}
即函数的每一项都是二次项。
任意全是二次项的函数都是二次型，当A不是对称矩阵时，可以做如下变换化为对称矩阵的形式：
xTAx=xTATx=xT(12A+12AT)x\mathbf{x}^TA\mathbf{x}=\mathbf{x}^TA^T\mathbf{x}=\mathbf{x}^T(\frac{1}{2}A+\frac{1}{2}A^T)\mathbf{x}
二次型的意义
  • 对于二次函数如f(x)=x2f(x)=x^2增加一次项、常数项不会影响其形状，只是做了位移；
  • 对于二次方程如x2+xy+y2=1x^2+xy+y^2=1增加一次项、常数项也不会改变其形状，只是看上去有些伸缩和位移。
notion image
二次型目标函数的最速下降法
目标函数为
f(x)=xTAx−bTx,A为对称矩阵f(\mathbf{x})=\mathbf{x}^TA\mathbf{x}-\mathbf{b}^T\mathbf{x},A为对称矩阵
其梯度为∇f(x)=Ax−b\nabla f(\mathbf{x})=A\mathbf{x}-\mathbf{b}，Hessian矩阵为H(x)=A=ATH(\mathbf{x})=A=A^T
记gk=∇f(x(k))g_k=\nabla f(\mathbf{x}^{(k)})最速下降法的第k次迭代为求一维优化问题
min⁡λkh(λk)=min⁡λkf(x(k)−λkgk))\min_{\lambda_k}h(\lambda_k)=\min_{\lambda_k}f\left(\mathbf{x}^{(k)}-\lambda_kg_k)\right)h′(λ)=−gkT∇f(x(k)−λgk))=−gkT(Ax(k)−λAgk−b)=λgkTAgk−gkTgk=0⟹λk=gkTgkgkTAgk\begin{aligned}h'(\lambda)&=-g_k^T\nabla f\left(\mathbf{x}^{(k)}-\lambda g_k)\right)\\&=-g_k^T(A\mathbf{x}^{(k)}-\lambda Ag_k-b)\\&=\lambda g_k^TAg_k-g_k^Tg_k\\&=0\end{aligned}\Longrightarrow \lambda_k=\frac{g_k^Tg_k}{g_k^TAg_k}
故的二次目标函数的最速下降法为
x(k+1)=x(k+1)−gkTgkgkTAgkgk\mathbf{x}^{(k+1)}=\mathbf{x}^{(k+1)}-\frac{g_k^Tg_k}{g_k^TAg_k}g_k
 
机器学习中的梯度下降法
算法的核心思想即沿着损失函数的负梯度方向调整参数，以达到损失函数的局部最小值。
θ=θ−η∇J(θ)\theta=\theta-\eta\nabla J(\theta)
θ\theta为训练参数,η\eta为学习率。
以平方损失函数为例：
J(θ;T)=12N∑i(yi−fθ(xi))2J(\theta;T)=\frac{1}{2N}\sum_i(y_i-f_\theta(x_i))^2
T为整个训练数据集，N为训练数据集大小，yiy_i为真实标签，fθ(xi)f_\theta(x_i)为模型预测值。
但在深度学习中，通常对每一个batch进行损失函数的计算和梯度下降法：
J(θ;batch)=12m∑i(yi−fθ(xi))2J(\theta;batch)=\frac{1}{2m}\sum_i(y_i-f_\theta(x_i))^2
m为一个batch的大小。
假设训练数据集中含有N个数据样本，对m的不同取值会有不同影响：
BGD（批量梯度下降法）
每次选用全量的训练样本来更新模型参数，即θ=θ−η∇J(θ;x,y)\theta=\theta-\eta\nabla J(\theta;x,y)
优点：
  • 每次更新都会朝着正确方向进行，最后保证收敛于极值点（凸函数收敛于全局极值，非凸函数可能收敛于局部极值）；
缺点：
  • 每次学习时间过长，如果训练数据集很大需要消耗大量内存，并且不能在线更新。
SGD（随机梯度下降）
每次从训练样本集中随机选择一个样本来进行学习，θ=θ−η∇J(θ;xi,yi)\theta=\theta-\eta\nabla J(\theta;x_i,y_i)
优点：
  • 学习速率快，可以在线更新；
  • 对于非凸函数，由于其随机性，可能会使得优化从当前的局部最小跳到另一个更好的局部最小，这样对于非凸函数，会使得最终收敛于一个较好的局部最小值，甚至全局最小值；
缺点：
  • 每次更新可能并不会朝着整体正确的方向进行，因此可能带来优化扰动；
  • 计算上不能进行并行计算。
MBGD（小批量梯度下降法）
综合了BGD和SGD，在每次更新速度和更新次数中取一个平衡，每次更新随机从训练集中取m<N个样本进行学习，θ=θ−η∇J(θ;xi:i+m,yi:i+m)\theta=\theta-\eta\nabla J(\theta;x_{i:i+m},y_{i:i+m})
优点：
  • 相比于SGD，降低了收敛波动性，即降低了参数更新的方差，使更新更加稳定；
  • 计算上可以并行化；
缺点：
  • 由于样本选择依然存在随机性，故上述方法依然不能保证好的收敛性。
主要存在的挑战有：
  1. 选择学习率困难（过小→收敛慢，过大→妨碍收敛&在最小点附近波动）；
  1. 应在训练期间调整学习率，学习速率逐步减小（但事先制定的规则和阈值可能不适用于所有数据集）；
  1. 使用梯度更新可能会导致所有参数都用相同的学习率更新（当训练数据集是稀疏的，或者特征频率不同，可能不希望参数被相同程度的更新，否则可能使很少出现的特征有较大变化）；
  1. 求高度非凸函数应避免陷入局部最优，但最困难的不是局部最优，而是鞍点。
更多的优化策略（待整理）☟
  • Momentum
  • Nesterov Momentum
  • AdaGrad
  • Adadelta
  • RMSprop
  • Adam
  • Nadam