梯度下降法-Gradient Descent

1. 梯度下降法(Gradient descent)

梯度下降法,通常也叫最速下降法(steepest descent),基于这样一个事实:如果实值函数 f(x) 在点x处可微且有定义,那么函数 f(x) 在 x点沿着负梯度(梯度的反方向)下降最快。

假设x是一个向量,考虑f(x) 的泰勒展开式:

f(xk??xk)?f(xk)??f(xk)?xk?o((?xk)2)?f(xk)??f(xk)?xk,其中?xk?xk?1?xk??kdk(?k为步长标量;dk是方向向量)

如果想要函数值下降,则要?f(xk)?xk?||?f(xk)||?||?xk||?cos??f(xk),?xk??0。如果想要下降的最快,则需要?f(xk)?xk取最小值,即cos??f(xk),?xk???1,也就是说,此时x的变化方向(?xk的方向)跟梯度?f(xk)的方向恰好相反。

xk?1?xk??k梯度法迭代公式:?f(xk)||?f(xk)|| 那么步长如何选取呢?的确,很难选择一个合适的固定值,如果较小,会收敛很慢;如果较大,可能有时候会跳过最优点,甚至导致函数值增大;因此,最好选择一个变化的步长,在离最优点较远的时候,步长大一点,离最优点较近的时候,步长小一点。

小?k大?k变化的?k

一个不错的选择是?k??||?f(xk)||,于是牛顿迭代公式变为:

xk?1?xk???f(xk),

此时?是一个固定值,称为学习率,通常取0.1,该方法称为固定学习率的梯度下降法。 另外,我们也可以通过一维搜索来确定最优步长。

1.1 梯度下降法的一般步骤:

Step1给定初始点

x0,迭代精度??0,k=0.

dk???f(xk)||?f(xk)|| Step2 计算?f(xk),如果||?f(xk)||??,停止;否则,计算搜索方向Step3 计算最优步长

?k?argminf(xk??dk)?;

Step4 更新迭代点

初始点的选取: 设

xk?1?xk??kdk,令k:?k?1, 转step2。

x0?(x0,1,...,x0,n),对每一个分量分别独立取值

x0,i~N(0,?i2)

梯度下降法简单,计算量小,仅仅需要求一阶导数,对初始点也没有特殊要求,具有整体收敛性。采用精确线搜索的梯度下降法的收敛速度为线性。

精确线搜索满足的一阶必要条件,得?f(xk??kdk)Tdk??f(xk?1)dk?0,由最速下降法得,dk???f(xk),因此有??f(xk?1)?f(xk)??dk?1dk?0,即:相邻两次的搜索方

向是相互直交的(投影到二维平面上,就是锯齿形状了)。

最后,我们讨论一个问题,这个所谓的最速下降法真的是“最快速”的吗?其实,它只是局部范围内具有最快速性质,对整体求解过程而言,它的下降非常缓慢。 例如, 我们来看一个常被用来作为最优化算法的performance test函数:Rosenbrock函数

f(x,y)?(1?x)2?100(y?x2)2,它在

点 (1,1) 处取得最小值0。此函数具有狭窄弯曲的山谷,最小值(1,1)就在这些山谷之中,并且谷底很平。优化过程是之字形的向极小值点靠近,速度非常缓慢(\之字型\下降,越靠近极小点下降越缓

慢)。

1.2 批量梯度法VS随机梯度法

梯度下降法每次更新都要对全体样本重新计算整个梯度,这种方法叫做批量梯度法(Batch Gradient Descent),当样本点很多时,这种方法速度很慢;于是,人们不再追求精确计算梯度方向,而是采取一种近似计算的思想,每次只利用一个训练样本计算梯度,来更新x,这种方法叫做随机梯度法(Stochastic Gradient Descent)。需要特别注意的一点是,随机梯度法最后的最优值不是计算过程中的任何一个xk(注意不是最后一个xk哦), 而是计算过

1N程中所有的xk平均值(各分量分别求平均值),即x??xk。

Nk?1*通常,SGD能比BGD更快地收敛到最优点,因此更适合大数据的计算。然而,对SGD而言,选择一个合适的终止条件是比较困难的。一个可选的办法是用validation, 在验证集上测试当前参数的效果,如果效果可以,就保存起来,当很长一段时间都是此效果的话那么就迭代停止。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4