Python 实现简单的梯度下降法
机器学习算法常常可以归结为求解一个最优化问题,而梯度下降法就是求解最优化问题的一个方法。
梯度下降法(gradient descent)或最速下降法(steepest decent),是求解无约束最优化问题的一种最常用的方法。
梯度下降法实现简单,是一种迭代算法,每一步会求解目标函数的梯度向量。
本文分为理论和 Python 代码实践,希望实现简单的梯度下降法,相关代码已放在GitHub中。
理论
问题定义
那么什么是目标函数,在机器学习中这常常是一个损失函数。不管怎么称呼,它就是一个函数 $f(x)$,而梯度下降法的目的就是获取这个函数的极小值。
下面给出一个较为正式的问题定义。
假设 $f(x)$ 是 $R^n$ 上具有一阶连续偏导数的函数。需要求解的无约束最优化问题是:
$$\underset{x\in 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 |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$ 要足够小,使得:
满足泰勒公式所需要的精度。
能够很好地捕捉到极小值。
这是一个显式表达式,可以不断求出 $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 deffunc_1d(x):9 """
10 目标函数11 :param x: 自变量,标量12 :return: 因变量,标量13 """
14 return x ** 2 + 1
15
16
17 defgrad_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 inrange(max_iters):37 grad_cur =grad(cur_x)38 if abs(grad_cur) <39 break>
40 cur_x = cur_x - grad_cur *learning_rate41 print("第", i, "次迭代:x 值为", cur_x)42
43 print("局部最小值 x =", cur_x)44 returncur_x45
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]$ 处有最小值。
1 #!/usr/bin/env python
2 #-*- coding: utf-8 -*-
3 """
4 二维问题的梯度下降法示例5 """
6 importmath7 importnumpy as np8
9
10 deffunc_2d(x):11 """
12 目标函数13 :param x: 自变量,二维向量14 :return: 因变量,标量15 """
16 return - math.exp(-(x[0] ** 2 + x[1] ** 2))17
18
19 defgrad_2d(x):20 """
21 目标函数的梯度22 :param x: 自变量,二维向量23 :return: 因变量,二维向量24 """
25 deriv0 = 2 * x[0] * math.exp(-(x[0] ** 2 + x[1] ** 2))26 deriv1 = 2 * x[1] * math.exp(-(x[0] ** 2 + x[1] ** 2))27 returnnp.array([deriv0, deriv1])28
29
30 def gradient_descent_2d(grad, cur_x=np.array([0.1, 0.1]), 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 inrange(max_iters):42 grad_cur =grad(cur_x)43 if np.linalg.norm(grad_cur, ord=2) <44 break>
45 cur_x = cur_x - grad_cur *learning_rate46 print("第", i, "次迭代:x 值为", cur_x)47
48 print("局部最小值 x =", cur_x)49 returncur_x50
51
52 if __name__ == '__main__':53 gradient_descent_2d(grad_2d, cur_x=np.array([1, -1]), learning_rate=0.2, precision=0.000001, max_iters=10000)
$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]), learning_rate=0.2, precision=0.000001, 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 实现简单梯度下降法的思考与总结,整个代码示例参见GitHub,有何建议和问题请留下您的反馈,谢谢!
44>39>
如果觉得《python迭代算法_Python实现简单的梯度下降法》对你有帮助,请点赞、收藏,并留下你的观点哦!