Python 实现简单的梯度下降法

机器学习算法常常可以归结为求解一个最优化问题，而梯度下降法就是求解最优化问题的一个方法。

梯度下降法（gradient descent）或最速下降法（steepest decent），是求解无约束最优化问题的一种最常用的方法。

梯度下降法实现简单，是一种迭代算法，每一步会求解目标函数的梯度向量。

本文分为理论和 Python 代码实践，希望实现简单的梯度下降法，相关代码已放在?GitHub?中。

理论

问题定义

那么什么是目标函数，在机器学习中这常常是一个损失函数。不管怎么称呼，它就是一个函数 $f(x)$，而梯度下降法的目的就是获取这个函数的极小值。

下面给出一个较为正式的问题定义。

假设 $f(x)$ 是 $R^n$ 上具有一阶连续偏导数的函数。需要求解的无约束最优化问题是：

$$underset{xin R^n}{min}f(x)$$

即需要求出目标函数 $f(x)$ 的极小点 $x^*$。

算法思想和推导

要理解梯度下降法，首先要理解梯度和负梯度的概念。

梯度是从 n 维推广出来的概念，类似于斜率。梯度的本意是一个向量，表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。具体定义和公式可以参考百度定义。

举个例子再体会一下梯度是表示方向的一个向量：

对于函数 $f(x_1,x_2)=2x_1^3-x_2^2$ 来说，它的梯度就是 $g(x_1,x_2)=[6x_1^2,-2x_2]$。对于给定点 $[x_1,x_2]$ 的附近处，它在 $[6x_1^2,-2x_2]$ 方向变化率最大，而其负梯度方向就是 $[-6x_1^2,2x_2]$。例如，在点?$[2,3]$ 附近处，它的负梯度方向就是 $[-24,-6]$。在此处，点?$[2,3]$ 向这个方向移动，会使得?$f(x_1,x_2)=2x_1^3-x_2^2$ 值减小的速率最快。反之，如果点?$[2,3]$ 向梯度方向?$[24,6]$?移动，会使得?$f(x_1,x_2)=2x_1^3-x_2^2$ 值增加的速率最快。

?

理解了梯度之后，其实就可以很容易推导出梯度下降法的算法过程了。

梯度下降法的思想，就是选取适当的初值 $x_{0}$，不断迭代更新 $x$ 的值，极小化目标函数，最终收敛。

由于负梯度方向是使函数值下降最快的方向，因此梯度下降在每一步采用负梯度方向更新 $x$ 的值，最终达到函数值最小。

可以看出，梯度下降法采用的是贪心的思想。

根据一阶泰勒展开，当 $x$ 趋近于 $x_k$ 时：

$$f(x)approx f(x_k)+g_{k}(x-x_k)$$

这里，$g_k=g(x_k)=bigtriangledown f(x_k)$ 是 $f(x)$ 在 $x_k$ 的梯度。

我们假设设定了一个初始值 $x_0$，现在需要确定一个 $x_1$，代入上式可得：

$$f(x_1)approx f(x_0)+g_{0}(x_1-x_0)$$

假设 $x_1$ 和 $x_0$ 之间的距离一定时，为了让?$f(x_1)$ 最小（贪心策略），应该有：

$$g_{0}(x_1-x_0)=left | g_{0} right | left | x_1-x_0 right |costheta =-left | g_{0} right | left | x_1-x_0 right |$$

也就是需要让 $x_1-x_0$ 和梯度 $g_{0}$ 的夹角 $theta$ 为 180°，使得 $costheta =-1$。换言之，$x_1-x_0$ 和梯度?$g_{0}$ 方向相反。

由于 $x_1-x_0=-frac{g_0}{left | g_0 right |}left | x_1-x_0 right |$，那么可以得到：

$$x_1=x_0-frac{g_0}{left | g_0 right |}left | x_1-x_0 right |=x_0-g_0lambda_0$$

其中 $lambda_0=frac{left | x_1-x_0 right |}{left | g_0 right |}$ 定义为学习率，它实际上步长除以梯度的模。因此当学习率一定时，步长其实是一直变化的。当梯度较大时，步长也较大；而当梯度较小时，步长也较小。这往往是我们希望的性质，因为当接近于局部最优解时，梯度变得较小，这时往往也需要步长变得更小，以利于找到局部最优解。

同理，我们可以得到 $x_2=x_1-g_1lambda_1$ ，依次类推，有：

$$x_{k+1}=x_k-g_klambda_k$$

其中，学习率?$lambda_k$ 要足够小，使得：

1. 满足泰勒公式所需要的精度。
2. 能够很好地捕捉到极小值。

这是一个显式表达式，可以不断求出 $x_{k+1}$，当满足收敛条件时（如梯度足够小或者 $x_{k+1}$ 更新变化量足够小），退出迭代，此时 $f(x_{k+1})$ 就是一个求解出来的最小函数值。

至此完成了梯度下降法逻辑上的推导。?

Python 代码实现

理论已经足够多了，接下来敲一敲实在的代码吧。

一维问题

假设我们需要求解的目标函数是：

$$f(x)=x^2+1$$

显然一眼就知道它的最小值是 $x=0$ 处，但是这里我们需要用梯度下降法的 Python 代码来实现。

 1 #!/usr/bin/env python
 2  -*- coding: utf-8 -*-
 3 """
 4 一维问题的梯度下降法示例
 5  6 
 7 
 8 def func_1d(x):
 9     10     目标函数
11     :param x: 自变量，标量
12     :return: 因变量，标量
13     14     return x ** 2 + 1
15 
16 
17  grad_1d(x):
18     19     目标函数的梯度
20 21 22     23     return x * 2
24 
25 
26 def gradient_descent_1d(grad,cur_x=0.1,learning_rate=0.01,precision=0.0001,max_iters=10000):
27     28     一维问题的梯度下降法
29     :param grad: 目标函数的梯度
30     :param cur_x: 当前 x 值，通过参数可以提供初始值
31     :param learning_rate: 学习率，也相当于设置的步长
32     :param precision: 设置收敛精度
33     :param max_iters: 最大迭代次数
34     :return: 局部最小值 x*
35     36     for i in range(max_iters):
37         grad_cur = grad(cur_x)
38         if abs(grad_cur) < precision:
39             break   当梯度趋近为 0 时，视为收敛
40         cur_x = cur_x - grad_cur * learning_rate
41         print("第",i,次迭代：x 值为 ",cur_x)
42 
43     局部最小值 x =44     return cur_x
45 
46 
47 if __name__ == '__main__':
48     gradient_descent_1d(grad_1d,cur_x=10,learning_rate=0.2,precision=0.000001,max_iters=10000)

其输出结果如下：

第 0 次迭代：x 值为  6.0
第 1 次迭代：x 值为  3.5999999999999996
第 2 次迭代：x 值为  2.1599999999999997
第 3 次迭代：x 值为  1.2959999999999998
第 4 次迭代：x 值为  0.7775999999999998
第 5 次迭代：x 值为  0.46655999999999986
第 6 次迭代：x 值为  0.2799359999999999
第 7 次迭代：x 值为  0.16796159999999993
第 8 次迭代：x 值为  0.10077695999999996
第 9 次迭代：x 值为  0.06046617599999997
第 10 次迭代：x 值为  0.036279705599999976
第 11 次迭代：x 值为  0.021767823359999987
第 12 次迭代：x 值为  0.013060694015999992
第 13 次迭代：x 值为  0.007836416409599995
第 14 次迭代：x 值为  0.004701849845759997
第 15 次迭代：x 值为  0.002821109907455998
第 16 次迭代：x 值为  0.0016926659444735988
第 17 次迭代：x 值为  0.0010155995666841593
第 18 次迭代：x 值为  0.0006093597400104956
第 19 次迭代：x 值为  0.0003656158440062973
第 20 次迭代：x 值为  0.0002193695064037784
第 21 次迭代：x 值为  0.00013162170384226703
第 22 次迭代：x 值为  7.897302230536021e-05
第 23 次迭代：x 值为  4.7383813383216124e-05
第 24 次迭代：x 值为  2.8430288029929674e-05
第 25 次迭代：x 值为  1.7058172817957805e-05
第 26 次迭代：x 值为  1.0234903690774682e-05
第 27 次迭代：x 值为  6.1409422144648085e-06
第 28 次迭代：x 值为  3.684565328678885e-06
第 29 次迭代：x 值为  2.210739197207331e-06
第 30 次迭代：x 值为  1.3264435183243986e-06
第 31 次迭代：x 值为  7.958661109946391e-07
第 32 次迭代：x 值为  4.775196665967835e-07
局部最小值 x = 4.775196665967835e-07

二维问题

接下来推广到二维，目标函数设为：

$$f(x,y) = -e^{-(x^2 + y^2)}$$

?

该函数在 $[0,0]$ 处有最小值。

二维问题的梯度下降法示例
 6 import math
 7  numpy as np
 8 
 9 
10  func_2d(x):
11     13     :param x: 自变量，二维向量
14 15     16     return - math.exp(-(x[0] ** 2 + x[1] ** 2))
17 
18 
19  grad_2d(x):
20     22 23     :return: 因变量，二维向量
24     25     deriv0 = 2 * x[0] * math.exp(-(x[0] ** 2 + x[1] ** 226     deriv1 = 2 * x[1] * math.exp(-(x[0] ** 2 + x[1] ** 227      np.array([deriv0,deriv1])
28 
29 
30 def gradient_descent_2d(grad,cur_x=np.array([0.1,0.1]),1)">31         二维问题的梯度下降法
35 36 37 38 39     40     print(f{cur_x} 作为初始值开始迭代...)
41     42         grad_cur =43         if np.linalg.norm(grad_cur,ord=2) <44             45         cur_x = cur_x - grad_cur *46         47 
48     49     50 
51 
52 53     gradient_descent_2d(grad_2d,cur_x=np.array([1,-1]),1)">)

$x_0$ 的初始值设为 $[1,-1]$ ，运行后的结果如下：

[ 1 -1] 作为初始值开始迭代...
第 0 次迭代：x 值为  [ 0.94586589 -0.94586589]
第 1 次迭代：x 值为  [ 0.88265443 -0.88265443]
第 2 次迭代：x 值为  [ 0.80832661 -0.80832661]
第 3 次迭代：x 值为  [ 0.72080448 -0.72080448]
第 4 次迭代：x 值为  [ 0.61880589 -0.61880589]
第 5 次迭代：x 值为  [ 0.50372222 -0.50372222]
第 6 次迭代：x 值为  [ 0.3824228 -0.3824228]
第 7 次迭代：x 值为  [ 0.26824673 -0.26824673]
第 8 次迭代：x 值为  [ 0.17532999 -0.17532999]
第 9 次迭代：x 值为  [ 0.10937992 -0.10937992]
第 10 次迭代：x 值为  [ 0.06666242 -0.06666242]
第 11 次迭代：x 值为  [ 0.04023339 -0.04023339]
第 12 次迭代：x 值为  [ 0.02419205 -0.02419205]
第 13 次迭代：x 值为  [ 0.01452655 -0.01452655]
第 14 次迭代：x 值为  [ 0.00871838 -0.00871838]
第 15 次迭代：x 值为  [ 0.00523156 -0.00523156]
第 16 次迭代：x 值为  [ 0.00313905 -0.00313905]
第 17 次迭代：x 值为  [ 0.00188346 -0.00188346]
第 18 次迭代：x 值为  [ 0.00113008 -0.00113008]
第 19 次迭代：x 值为  [ 0.00067805 -0.00067805]
第 20 次迭代：x 值为  [ 0.00040683 -0.00040683]
第 21 次迭代：x 值为  [ 0.0002441 -0.0002441]
第 22 次迭代：x 值为  [ 0.00014646 -0.00014646]
第 23 次迭代：x 值为  [ 8.78751305e-05 -8.78751305e-05]
第 24 次迭代：x 值为  [ 5.27250788e-05 -5.27250788e-05]
第 25 次迭代：x 值为  [ 3.16350474e-05 -3.16350474e-05]
第 26 次迭代：x 值为  [ 1.89810285e-05 -1.89810285e-05]
第 27 次迭代：x 值为  [ 1.13886171e-05 -1.13886171e-05]
第 28 次迭代：x 值为  [ 6.83317026e-06 -6.83317026e-06]
第 29 次迭代：x 值为  [ 4.09990215e-06 -4.09990215e-06]
第 30 次迭代：x 值为  [ 2.45994129e-06 -2.45994129e-06]
第 31 次迭代：x 值为  [ 1.47596478e-06 -1.47596478e-06]
第 32 次迭代：x 值为  [ 8.85578865e-07 -8.85578865e-07]
第 33 次迭代：x 值为  [ 5.31347319e-07 -5.31347319e-07]
第 34 次迭代：x 值为  [ 3.18808392e-07 -3.18808392e-07]
局部最小值 x = [ 3.18808392e-07 -3.18808392e-07]

我们再试着以初始值 $[3,-3]$ 处开始寻找最小值，即：

gradient_descent_2d(grad_2d,cur_x=np.array([3,-3]),max_iters=10000)

结果可能出乎人意料：

[ 3 -3] 作为初始值开始迭代...
局部最小值 x = [ 3 -3]

梯度下降法没有找到真正的极小值点！

如果仔细观察目标函数的图像，以及梯度下降法的算法原理，你就很容易发现问题所在了。在 $[3,-3]$ 处的梯度就几乎为 0 了！

print(grad_2d(np.array([3,-3])))

[ 9.13798785e-08 -9.13798785e-08]

由于“梯度过小”，梯度下降法可能无法确定前进的方向了。即使人为增加收敛条件中的精度，也会由于梯度过小，导致迭代中前进的步长距离过小，循环时间过长。

梯度下降法的局限性

梯度下降法实现简单，原理也易于理解，但它有自身的局限性，因此有了后面很多算法对它的改进。

对于梯度过小的情况，梯度下降法可能难以求解。

此外，梯度下降法适合求解只有一个局部最优解的目标函数，对于存在多个局部最优解的目标函数，一般情况下梯度下降法不保证得到全局最优解（由于凸函数有个性质是只存在一个局部最优解，所有也有文献的提法是：当目标函数是凸函数时，梯度下降法的解才是全局最优解）。

由于泰勒公式的展开是近似公式，要求迭代步长要足够小，因此梯度下降法的收敛速度并非很快的。

总结

以上是对用 Python 实现简单梯度下降法的思考与总结，有何建议和问题请留下您的反馈，谢谢！

原文作者：雨先生
原文链接：https://www.cnblogs.com/noluye/p/11108513.html?
许可协议：知识共享署名-非商业性使用 4.0 国际许可协议

?

（编辑：北几岛）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!