梯度下降法-Gradient-Descent

1.梯度下降法(Gradientdescent)梯度下降法，通常也叫最速下降法(steepestdescent)，基于这样一个事实：如果实值函数f(x)在点x处可微且有定义，那么函数f(x)在x点沿着负梯度(梯度的反方向)下降最快。假设x是一个向量，考虑f(x)的泰勒展开式：)(,)()())(()()()(12是方向向量为步长标量；其中kkkkkkkkkkkkkkkkddxxxxxfxfxoxxfxfxxf如果想要函数值下降，则要()||()||||||cos(),0kkkkkkfxxfxxfxx。如果想要下降的最快，则需要kkxxf)(取最小值，即cos(),1kkfxx，也就是说，此时x的变化方向(kx的方向)跟梯度)(kxf的方向恰好相反。梯度法迭代公式：||)(||)(1kkkkkxfxfxx那么步长如何选取呢？的确，很难选择一个合适的固定值，如果较小，会收敛很慢；如果较大，可能有时候会跳过最优点，甚至导致函数值增大；因此，最好选择一个变化的步长，在离最优点较远的时候，步长大一点，离最优点较近的时候，步长小一点。k小k大k变化的一个不错的选择是||)(||kkxf，于是牛顿迭代公式变为：)(1kkkxfxx，此时是一个固定值，称为学习率，通常取0.1，该方法称为固定学习率的梯度下降法。另外，我们也可以通过一维搜索来确定最优步长。1.1梯度下降法的一般步骤：Step1给定初始点0x,迭代精度0，k=0.Step2计算)(kxf，如果||)(||kxf,停止；否则，计算搜索方向||)(||)(kkkxfxfdStep3计算最优步长)(minargkkkdxf；Step4更新迭代点kkkkdxx1，令1:kk,转step2。初始点的选取：设),...,(,01,00nxxx，对每一个分量分别独立取值),0(~2,0iiNx梯度下降法简单，计算量小，仅仅需要求一阶导数，对初始点也没有特殊要求，具有整体收敛性。采用精确线搜索的梯度下降法的收敛速度为线性。精确线搜索满足的一阶必要条件，得0)()(1kkkTkkkdxfddxf，由最速下降法得，)(kkxfd，因此有0)()(11kkkkddxfxf，即：相邻两次的搜索方向是相互直交的（投影到二维平面上，就是锯齿形状了）。最后，我们讨论一个问题，这个所谓的最速下降法真的是“最快速”的吗？其实，它只是局部范围内具有最快速性质,对整体求解过程而言，它的下降非常缓慢。例如,我们来看一个常被用来作为最优化算法的performancetest函数：Rosenbrock函数222)(100)1(),(xyxyxf，它在点(1,1)处取得最小值0。此函数具有狭窄弯曲的山谷，最小值(1,1)就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢（之字型下降，越靠近极小点下降越缓慢）。1.2批量梯度法VS随机梯度法梯度下降法每次更新都要对全体样本重新计算整个梯度，这种方法叫做批量梯度法(BatchGradientDescent)，当样本点很多时，这种方法速度很慢；于是，人们不再追求精确计算梯度方向，而是采取一种近似计算的思想，每次只利用一个训练样本计算梯度，来更新x，这种方法叫做随机梯度法（StochasticGradientDescent）。需要特别注意的一点是，随机梯度法最后的最优值不是计算过程中的任何一个kx(注意不是最后一个kx哦),而是计算过程中所有的kx平均值(各分量分别求平均值)，即NkkxNx1*1。通常，SGD能比BGD更快地收敛到最优点，因此更适合大数据的计算。然而，对SGD而言，选择一个合适的终止条件是比较困难的。一个可选的办法是用validation,在验证集上测试当前参数的效果，如果效果可以，就保存起来，当很长一段时间都是此效果的话那么就迭代停止。