梯度下降
梯度下降(Gradient Descent)是深度学习中最常见的优化方法。每一步计算损失函数对参数的梯度,然后沿着梯度的负方向更新参数。
直观上就是从最陡峭的方向下山。
使用梯度下降算法时,如果选用所有数据计算梯度,计算量太大,如果随机选择单个训练数据计算,则迭代次数会非常大。实际应用中,会选择一个适当的batch size(16-512)来计算梯度。
当目标函数为凸函数时,梯度下降的解是全局最优解。一般情况下,不能保证是全局最优解。
Momentum
梯度下降只考虑了当前的梯度,Momentum算法使用指数加权平均,把之前的历史梯度和当前梯度融合,确定最终的梯度方向。这样做有平均的效果,错误的梯度方向往往是随机的,通过平均可以消除这样的梯度分量,能够更快收敛,并有一定摆脱局部最优的能力。
Momentum具体算法:
两个超参数$\alpha$和$\beta$分别表示学习率和加权平均系数。
Adagrad
Momentum和梯度下降算法中学习率始终不变,Adagrad算法可以根据梯度调整学习率。算法如下:
- 首先计算出梯度g
- 计算 $\boldsymbol{s} \leftarrow \boldsymbol{s} + \boldsymbol{g} \odot \boldsymbol{g}.$ s初始化为0
- 调整学习率 $\boldsymbol{g}^\prime \leftarrow \frac{\eta}{\sqrt{\boldsymbol{s} + \epsilon}} \odot \boldsymbol{g},$
- 更新 $\boldsymbol{x} \leftarrow \boldsymbol{x} - \boldsymbol{g}^\prime.$
从公式中可以看到,基础学习率为$\eta$,如果梯度在某个方向下降很快,即某个分量很大,则变量s中相应的分量也大,导致这个方向的学习率下降很快,防止跳过最优解。
RMSProp
RMSProp是Adagrad和momentum的结合。在Adagrad的基础上,考虑历史梯度,加入momentum算法中的指数加权平均。实际应用中,RMSProp优于Adagrad。
- $\boldsymbol{s} \leftarrow \gamma \boldsymbol{s} + (1 - \gamma) \boldsymbol{g} \odot \boldsymbol{g}.$
- $\boldsymbol{g}^\prime \leftarrow \frac{\eta}{\sqrt{\boldsymbol{s} + \epsilon}} \odot \boldsymbol{g},$
- $\boldsymbol{x} \leftarrow \boldsymbol{x} - \boldsymbol{g}^\prime.$
Adagrad和RMSProp都是根据梯度的平方(大小)来调整每个分量上的学习率。
Adam
Adam算法结合了momentum和RMSProp,是目前最好的优化算法之一。
- 与momentum类似计算
- 与RMSProp类似计算
- 修正误差,使过去各时刻的权重$\beta^t$和为1.
- 得到最终梯度:
- 更新
牛顿法、拟牛顿法
牛顿法和拟牛顿法是另一类求解优化问题的算法。如果目标函数二次可微,函数f(x)取极小值的必要条件是导数$f\prime(x)=0$,对f(x)泰勒二次展开,得到:
求导并令其等于0,得到:
解得:
扩展到高维情况,一阶导数用梯度代替,二阶导数的倒数用Hessian矩阵的逆矩阵代替。牛顿法要收敛,Hessian矩阵必须正定(所有特征值为正)。如果Hessian矩阵特征值有正有负,则为鞍点。牛顿法利用了二阶偏导数,其收敛速度比梯度下降类算法快,但是求Hessian逆矩阵的计算量往往非常大,因此出现拟牛顿法,近似计算Hessian逆矩阵,如DFP算法、BFGS算法等。
启发式算法
遗产算法、粒子群算法等启发式算法(Heuristic Algorithm)也可以解优化问题。启发式算法往往是模拟自然界生物的行为,在可接受的计算成本内取搜索最优解,但不一定保证收敛。
以遗传算法为例,在解空间内随机生成一组解,作为初始种群。种群之间进行交叉、变异,产生新的一组解。选择一个适应度函数来评价解的优劣,按概率进行选择。如果第i个个体的适应度函数为$f(x_i)$,则它被选择到下一个种群的概率为:
如此不断迭代直到收敛。
目标函数$f(x)=x^2$求最小值,可以令适应度函数为$\frac 1 {x^2}$。考虑两个二进制数[1000,1110], 交叉操作可以将后两位交换,生成[1010,1100]; 变异操作可以将任意一位取反,以最后一位为例,则生成[1001,1111]。