Python实现简单的梯度下降法

张明海 發表於 2019-6-30 02:25:00

<h1>Python 实现简单的梯度下降法</h1>
机器学习算法常常可以归结为求解一个最优化问题，而梯度下降法就是求解最优化问题的一个方法。
梯度下降法（gradient descent）或最速下降法（steepest decent），是求解无约束最优化问题的一种最常用的方法。
梯度下降法实现简单，是一种迭代算法，每一步会求解目标函数的梯度向量。
本文分为理论和 Python 代码实践，希望实现简单的梯度下降法，相关代码已放在 GitHub 中。
<h2>理论</h2>
<h3>问题定义</h3>
那么什么是目标函数，在机器学习中这常常是一个损失函数。不管怎么称呼，它就是一个函数 $f(x)$，而梯度下降法的目的就是获取这个函数的极小值。
下面给出一个较为正式的问题定义。
<blockquote>
假设 $f(x)$ 是 $R^n$ 上具有一阶连续偏导数的函数。需要求解的无约束最优化问题是：
$$\underset{x\in R^n}{min}f(x)$$
即需要求出目标函数 $f(x)$ 的极小点 $x^*$。
</blockquote>
<h3>算法思想和推导</h3>
要理解梯度下降法，首先要理解梯度和负梯度的概念。
梯度是从 n 维推广出来的概念，类似于斜率。梯度的本意是一个向量，表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。具体定义和公式可以参考百度定义。
举个例子再体会一下梯度是表示方向的一个向量：
对于函数 $f(x_1,x_2)=2x_1^3-x_2^2$ 来说，它的梯度就是 $g(x_1,x_2)=$。对于给定点 $$ 的附近处，它在 $$ 方向变化率最大，而其负梯度方向就是 $[-6x_1^2,2x_2]$。例如，在点 $$ 附近处，它的负梯度方向就是 $[-24, -6]$。在此处，点 $$ 向这个方向移动，会使得 $f(x_1,x_2)=2x_1^3-x_2^2$ 值减小的速率最快。反之，如果点 $$ 向梯度方向 $$ 移动，会使得 $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 |cos\theta =-\left | g_{0} \right | \left | x_1-x_0 \right |$$
也就是需要让 $x_1-x_0$ 和梯度 $g_{0}$ 的夹角 $\theta$ 为 180°，使得 $cos\theta =-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_0\lambda_0$$
其中 $\lambda_0=\frac{\left | x_1-x_0 \right |}{\left | g_0 \right |}$ 定义为学习率，它实际上步长除以梯度的模。因此当学习率一定时，步长其实是一直变化的。当梯度较大时，步长也较大；而当梯度较小时，步长也较小。这往往是我们希望的性质，因为当接近于局部最优解时，梯度变得较小，这时往往也需要步长变得更小，以利于找到局部最优解。
同理，我们可以得到 $x_2=x_1-g_1\lambda_1$ ，依次类推，有：
$$x_{k+1}=x_k-g_k\lambda_k$$
其中，学习率 $\lambda_k$ 要足够小，使得：
<ol>
<li>满足泰勒公式所需要的精度。</li>
<li>能够很好地捕捉到极小值。</li>
</ol>
这是一个显式表达式，可以不断求出 $x_{k+1}$，当满足收敛条件时（如梯度足够小或者 $x_{k+1}$ 更新变化量足够小），退出迭代，此时 $f(x_{k+1})$ 就是一个求解出来的最小函数值。
至此完成了梯度下降法逻辑上的推导。 
<h2>Python 代码实现</h2>
理论已经足够多了，接下来敲一敲实在的代码吧。
<h3>一维问题</h3>
假设我们需要求解的目标函数是：
$$f(x)=x^2+1$$
<img src="https://img2018.cnblogs.com/blog/1046925/201906/1046925-20190629211500124-1871874583.png">
显然一眼就知道它的最小值是 $x=0$ 处，但是这里我们需要用梯度下降法的 Python 代码来实现。
<div class="cnblogs_code">
<pre> 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 def grad_1d(x):
18 """
19 目标函数的梯度
20 :param x: 自变量，标量
21 :return: 因变量，标量
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 print("局部最小值 x =", cur_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)</pre>
</div>
其输出结果如下：
<div class="cnblogs_code">
<pre>第 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</pre>
</div>
<h3>二维问题</h3>
接下来推广到二维，目标函数设为：
$$f(x,y) = -e^{-(x^2 + y^2)}$$
 
<img src="https://img2018.cnblogs.com/blog/1046925/201906/1046925-20190629232822055-37516335.png">
该函数在 $$ 处有最小值。
<div class="cnblogs_code">
<pre> 1 #!/usr/bin/env python
 2 # -*- coding: utf-8 -*-
 3 """
 4 二维问题的梯度下降法示例
 5 """
 6 import math
 7 import numpy as np
 8
 9
10 def func_2d(x):
11 """
12 目标函数
13 :param x: 自变量，二维向量
14 :return: 因变量，标量
15 """
16 return - math.exp(-(x ** 2 + x ** 2))
17
18
19 def grad_2d(x):
20 """
21 目标函数的梯度
22 :param x: 自变量，二维向量
23 :return: 因变量，二维向量
24 """
25 deriv0 = 2 * x * math.exp(-(x ** 2 + x ** 2))
26 deriv1 = 2 * x * math.exp(-(x ** 2 + x ** 2))
27 return np.array()
28
29
30 def gradient_descent_2d(grad, cur_x=np.array(), learning_rate=0.01, precision=0.0001, max_iters=10000):
31 """
32 二维问题的梯度下降法
33 :param grad: 目标函数的梯度
34 :param cur_x: 当前 x 值，通过参数可以提供初始值
35 :param learning_rate: 学习率，也相当于设置的步长
36 :param precision: 设置收敛精度
37 :param max_iters: 最大迭代次数
38 :return: 局部最小值 x*
39 """
40 print(f"{cur_x} 作为初始值开始迭代...")
41 for i in range(max_iters):
42 grad_cur = grad(cur_x)
43 if np.linalg.norm(grad_cur, ord=2) < precision:
44 break# 当梯度趋近为 0 时，视为收敛
45 cur_x = cur_x - grad_cur * learning_rate
46 print("第", i, "次迭代：x 值为 ", cur_x)
47
48 print("局部最小值 x =", cur_x)
49 return cur_x
50
51
52 if __name__ == '__main__':
53 gradient_descent_2d(grad_2d, cur_x=np.array(), learning_rate=0.2, precision=0.000001, max_iters=10000) </pre>
</div>
$x_0$ 的初始值设为 $$ ，运行后的结果如下：
<div class="cnblogs_code">
<pre>[ 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]</pre>
</div>
我们再试着以初始值 $$ 处开始寻找最小值，即：
<div class="cnblogs_code">
<pre>gradient_descent_2d(grad_2d, cur_x=np.array(), learning_rate=0.2, precision=0.000001, max_iters=10000)</pre>
</div>
结果可能出乎人意料：
<div class="cnblogs_code">
[ 3 -3] 作为初始值开始迭代... 局部最小值 x = [ 3 -3]

</div>
梯度下降法没有找到真正的极小值点！
如果仔细观察目标函数的图像，以及梯度下降法的算法原理，你就很容易发现问题所在了。在 $$ 处的梯度就几乎为 0 了！
<div class="cnblogs_code">
<pre>print(grad_2d(np.array()))</pre>
</div>
<div class="cnblogs_code">
<pre>[ 9.13798785e-08 -9.13798785e-08]</pre>
</div>
由于“梯度过小”，梯度下降法可能无法确定前进的方向了。即使人为增加收敛条件中的精度，也会由于梯度过小，导致迭代中前进的步长距离过小，循环时间过长。
<h2>梯度下降法的局限性</h2>
梯度下降法实现简单，原理也易于理解，但它有自身的局限性，因此有了后面很多算法对它的改进。
对于梯度过小的情况，梯度下降法可能难以求解。
此外，梯度下降法适合求解只有一个局部最优解的目标函数，对于存在多个局部最优解的目标函数，一般情况下梯度下降法不保证得到全局最优解（由于凸函数有个性质是只存在一个局部最优解，所有也有文献的提法是：当目标函数是凸函数时，梯度下降法的解才是全局最优解）。
由于泰勒公式的展开是近似公式，要求迭代步长要足够小，因此梯度下降法的收敛速度并非很快的。
<h2>总结</h2>
以上是对用 Python 实现简单梯度下降法的思考与总结，有何建议和问题请留下您的反馈，谢谢！
原文作者：雨先生 原文链接：https://www.cnblogs.com/noluye/p/11108513.html  许可协议：知识共享署名-非商业性使用 4.0 国际许可协议
  
来源：https://www.cnblogs.com/noluye/p/11108513.html

頁: [1]

琼殿技术论坛's Archiver

Python实现简单的梯度下降法