梯度下降算法

二维梯度下降

背景引入

​ 梯度下降法（gradient descent），又名最速下降法（steepest descent）是求解无约束最优化问题最常用的方法，它是一种迭代方法，每一步主要的操作是求解目标函数的梯度向量，将当前位置的负梯度方向作为搜索方向（因为在该方向上目标函数下降最快，这也是最速下降法名称的由来）。

​ 梯度下降法特点：==越接近目标值，步长越小，下降速度越慢。==

​ 梯度下降法的基本思想可以类比为一个下山的过程。

​ 假设这样一个场景：一个人被困在山上，需要从山上下来(找到山的最低点，也就是山谷)。但此时山上的浓雾很大，导致可视度很低；因此，下山的路径就无法确定，必须利用自己周围的信息一步一步地找到下山的路。这个时候，便可利用梯度下降算法来帮助自己下山。怎么做呢，首先以他当前的所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着下降方向走一步，然后又继续以当前位置为基准，再找最陡峭的地方，再走直到最后到达最低处；同理上山也是如此，只是这时候就变成梯度上升算法了

​ 梯度下降的基本过程就和下山的场景很类似。

​ 首先，我们有一个可微分的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值，也就是山底。根据之前的场景假设，最快的下山的方式就是找到当前位置最陡峭的方向，然后沿着此方向向下走，对应到函数中，就是找到给定点的梯度 ，然后朝着梯度相反的方向，就能让函数值下降的最快！因为梯度的方向就是函数之变化最快的方向(在后面会详细解释)
所以，我们重复利用这个方法，反复求取梯度，最后就能到达局部的最小值，这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向，也就是场景中测量方向的手段。

推导

所谓最快下降方案，无疑是求函数图像中，某点的切线的斜率，函数的变化率

1.单变量的微分，函数只有一个变量时

2.多变量的微分，当函数有多个变量的时候，即分别对每个变量进行求微分

换个方式想想，人想要最快下山，是不是要从最抖的地方开始走，梯度的方向是函数在给定点上升最快的方向，那么梯度的反方向就是函数在给定点下降最快的方向，那么沿着梯度走不但能到终点，而且过程最快

由此，我们开始剖析公式

公式

初始：

$Θ^1=Θ^0-α*J′(Θ^0)→evaluatedatΘ^0$

$Θ^0$代表起始位置，$Θ^{0+1}$代表下一个状态的位置

α代表步长，即也就是学习率，如果学习率不合适可能会导致发生错误

由此推之

$Θ^{n+1}=Θ^n-α*J′(Θ^n)→evaluatedatΘ^n$

注意：

  • 当靠近极小值时收敛速度减慢
  • 下降过程可能会出现 “之字形” 地下降
  • 代码层面需要设置停止运算条件直到到达指定精度或者指定运算次数停止

例题：

用梯度下降法求 $y=x^2/2-2x$的极值。
提示：初始值$x~0=-4$ 学习率 $η=0.9$，终止条件：Δx<ε=0.01。

手写推演：

image

代码和运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import matplotlib.pyplot as plt

# 定义函数 y = x^2 / 2 - 2x
def func(x):
    return x ** 2 / 2 - 2 * x

# 定义函数 y 对 x 的导数
def dfunc(x):
    return x - 2

# 定义梯度下降函数
def gradient_descent(x0, eta, epsilon):
    # 初始化
    x = x0
    v = 0
    delta_x = epsilon + 1
    result_x = [x]
    result_y = [func(x)]

    # 迭代更新参数，直到满足终止条件
    while delta_x > epsilon:
        # 计算导数
        vd = dfunc(x)

        # 更新速度和位置
        v = -eta * vd
        x += v

        # 计算当前点与上一个点的距离
        delta_x = abs(result_x[-1] - x)

        # 保存每次迭代得到的结果
        result_x.append(x)
        result_y.append(func(x))

    return (result_x, result_y)

# 设置初始值、学习率和终止条件
x0 = -4
eta = 0.9
epsilon = 0.01

# 调用梯度下降函数求解
result_x, result_y = gradient_descent(x0, eta, epsilon)

# 输出结果
print("通过梯度下降法求得的极值点横坐标为：", result_x[-1])
print("最终误差：", abs(result_y[-1]))

# 绘制函数图像
x = [i / 10 for i in range(-40, 60)]
y = [func(i) for i in x]
plt.plot(x, y)

# 绘制梯度下降过程图像
plt.plot(result_x, result_y, color='r', marker='o')

# 添加标题
plt.title("y = x^2 / 2 - 2x, η = {}".format(eta))

# 显示图像
plt.show()

运行结果如图

image

梯度下降三种形式（BGD，SGD，MBGD）

批量梯度下降

批量梯度下降法每次都使用训练集中的所有样本更新参数。它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果很大，那么迭代速度就会变得很慢。 优点：可以得出全局最优解。 缺点：样本数据集大时，训练速度慢。

随机梯度下降

由于批梯度下降每跟新一个参数的时候，要用到所有的样本数，所以训练速度会随着样本数量的增加而变得非常缓慢。随机梯度下降正是为了解决这个办法而提出的。它是利用每个样本的损失函数对θ求偏导得到对应的梯度，来更新θ

　随机梯度下降是通过每个样本来迭代更新一次，对比上面的批量梯度下降，迭代一次需要用到所有训练样本（往往如今真实问题训练数据都是非常巨大），一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

小批量梯度下降法

我们从上面两种梯度下降法可以看出，其各自均有优缺点，那么能不能在两种方法的性能之间取得一个折衷呢？即，算法的训练过程比较快，而且也要保证最终参数训练的准确率，而这正是小批量梯度下降法（Mini-batch Gradient Descent，简称MBGD）的初衷。

拓展：二维延展至三维梯度下降

举例

假设有个函数

$f(x,y)=x^2+y^2$

微分得

$f_x’(x,y)=2x$ $f_x’(x,y)=2y$

假设初始起点为(5,5)，步长α=0.4

以此类推$Θ^1=Θ^0−α*J(Θ)=(5,5)−0.2∗(10,10)=(3.0,3.0)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

ax = plt.figure().add_subplot(projection='3d')
def f(x,y):
    return x*x+y*y
def dfx(x):
    return 2*x
def dfy(x):
    return 2*x
a=0.2   #步长
x,y=5,5 #初始x,y位置
gx=[x]   
gy=[y]   
gz=[f(x,y)]
fcu=fch=f(x,y)
ans=0
#算法
while ans <100 and fch> 1e-10: #当次数小于100次或者函数变化小于1e-10就继续进行任务
    ans+=1
    x=x-a*dfx(x)
    y=y-a*dfy(y)
    tmp=f(x,y)
    fch=abs(fcu-tmp)
    fcu=tmp
    gx.append(x)
    gy.append(y)
    gz.append(fcu)
# print("{:.10f}".format(gx[3])) #无限接近0
X=np.arange(-5,5,0.1)
Y=np.arange(-5,5,0.1)
Z=np.array(f(X,Y))
ax.plot(X,Y,Z)
ax.plot(gx,gy,gz)
ax.scatter(gx,gy,gz)
plt.title("$f(x,y)=x^2+y^2$\n$a=%.2f$" % a)
plt.show()

运行结果如图

image