梯度下降算法

梯度下降法是一个最优化算法，通常也称为最速下降法。最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向的，最速下降法越接近目标值，步长越小，前进越慢。

引出梯度下降

对于线性回归问题，最后归结为残差平方和最小的优化问题，一般用的是最小二乘法，如果有解，得到的确实是最优解。很多人听到这个，或许会说：天杀的最小二乘法，因为很多人对它太敏感了。是的，从小到大，天天最小二乘法，能不能来点新花样。这里就用数学算法——梯度下降，来解决这种相对简单的寻优问题。当然了，我们的目标函数还是：

找了好久，我选了这张图片，因为我觉得这张图片很形象：天气骤变，一个人需要快速下山回家，但是他迷路了，不知道怎么回家，他知道自己家位于这座山海拔最低处。环顾四周，怎么样最快下山回家呢。他个子一定（假设1.8m大个子吧），每次迈步子为平时走路最大步长了（假设保持不变），要往哪个方向走才能使得：每迈出一步，自己下降的高度最大呢？只要每步有效下降高度最大，我们完全有理由相信，他会最快下山回家。

所以：他会告诉自己，我每次要找一个最好的下山方向（有点像“贪心”）。

其实，这个图还反映了另外一个问题，对于有多个极值点的情况，不同的初始出发点，梯度下降可能会陷入局部极小值点。就像一句古诗：不识庐山真面目，只缘身在此山中！这时候，就需要多点随机下山解决。当然了，解决线性回归问题的梯度下降是基于误差平方和，只有二次项，不存在多峰问题。

梯度下降的理论基础

我们都现在都知道这个人的任务是什么了：每次要找一个最好的下山方向。数学微分学告诉我们：其实这里的方向就是我们平时所说的：方向导数，它可以衡量函数值沿着某个方向变化的快慢，只要选择了好的方向（导数），就能快速达到（最大/最小值）。

（1）、梯度的定义

这里还是摆一个公式吧，否则看着不符合我的风格。方向导数定义就不扯远了，那是个关于极限的定义。这里给出三元函数梯度定义公式：

显然，让沿着与梯度方向，夹角为0或者180°时函数值增减最快。其实，每个多元函数在任一点会有一个梯度。函数在某一点沿着负梯度方向，函数值是变化最快的。这里就不过多证明了。

（2）、步长的求法

其实，我们可以设定一个指定步长。但是，这个指定步长到底设为多大合适。众所周知，过大会导致越过极小值点；过小在数据量大时会导致迭代次数过多。所以我们需要一套理论可以来科学得计算步长。保证在步长变换过程中，尽管有时可能会走回头路，但总体趋势是向驻点逼近。

这里简单说一下，假设在图中一点沿着梯度方向存在二阶偏导数，就可以泰勒展开到平方项，进而对这个关于步长的函数求导数，导函数零点就是此时最佳步长。详细可以参见运筹学推导。

《运筹学》 第四版  清华大学出版社
       用到的公式主要是步长lambda公式如下：
               

说明：下三角f表示梯度，海赛矩阵，X1，X2这里表示各个变量（这里是两个），对于连续函数，偏导数不分先后，所以不要算两遍，后面写程序会用到！这样每走一步，都会重新设置步长，与定步长相比，是不是更加智能了？

下降停止标志：梯度趋于0，或者小于给定的eps。        

有了这些理论基础后，编程实现就容易多了，下面就编程实现了。

梯度下降的Python实现

（1）、用到的函数：

不同点的梯度函数，海赛矩阵函数，迭代主函数 这里把第一篇《基于最小二乘法的——线性回归拟合（一）》与本文的梯度下降法代码放在一个脚本里，运行结果都有。

程序代码：

（2）、结果展示
*------------梯度下降-----------*
系数为： 2.1672851935 2.5282506525292012
梯度下降拟合次数为： 5
梯度为： 1.2745428915606112e-05
误差为： 9.898083702910405
R方： 0.9558599578256541
在0.05置信水平下，该线性拟合不错!
       

可以看出，梯度为： 1.2745428915606112e-05，已经接近0了，跟据实际精度会有不同。显然，梯度下降这里不存在局部极值点问题，只能是步长迈过去了，但这个点一定是靠近最优解的，误差非常小。

猜你可能喜欢

识别二维码，访问我的个人博客网站

觉得不错，记得点赞分享，更多精彩可以点击【阅读原文】，精彩课程等你来！