Welcome To My Blog
梯度下降(gradient descent)也叫最速下降(steepest descent),用来求解无约束最优化问题的一种常用方法,结果是局部最优解,对于目标函数为凸的情况,可以得到全局最优解.梯度下降是迭代算法,每一步需要求解目标函数的梯度向量.
采用线搜索的框架
搜索方向取负梯度方向,步长可以通过精确线搜索或非精确线搜索获得
关于步长,之前的文章有提过:Line search and Step length线搜索与步长
泰勒展开简化形式
- 假设f(x)是R^n上具有一阶连续偏导数的函数.要求解的无约束最优化问题是min f(x),x*标识目标函数f(x)的极小点.
- 选取适当的初值x^(0),不断迭代,更新x的值,进行目标函数的极小化,直到收敛.由于负梯度方向是使函数值下降最快的方向,在迭代的每一步,以负梯度方向更新x的值,从而达到减小函数值的目的.
- 因为f(x)具有一阶连续偏导数, 若第k次迭代值为x^(k),则可将f(x)在x^(k)附近进行一阶泰勒展开(Taylor expansion):
算法流程
简化版:
缺点
收敛慢
碗形函数(bowl shape)
蓝色的线是函数的等高线(线上的函数值相等)
从x_0点开始,沿x_0的负梯度方向(与该点切线垂直)的前进适当的步长,函数值会减小
对于该图来说,一次一次迭代可以收敛全局最优点
之字形Zig-Zagging
实际中的等高线可能并没有这么好
下图这样的等高线会导致每次迭代走的是之字形(Zig-Zagging),这样会使得收敛速度很慢
Rosenbrock 函数
对于像Rosenbrock这样的病态函数(pathological functions)来说,等高线如下图
不仅有走之字形(Zig-Zagging)的情况,而且函数图像的底部很平坦,这样每次前进的步长很小,导致收敛速度太慢
The bottom of the valley is very flat. Because of the curved flat valley the optimization is zig-zagging slowly with small stepsizes towards the minimum.
梯度下降的收敛速度比起很多其他方法都慢,如果函数不凸,梯度下降过程中会走更多的之字形,因为总有当前点的梯度方向与当前点到最小点的方向是垂直的情况,也就是说要走很多冤枉路
不可微的函数
对于不可微的函数,就不能直接用梯度下降了,需要进行额外的平滑处理
参考:
李航,统计学习方法