局部搜索之改进的梯度下降法

1、Momentum

Momentum梯度下降法(即动量梯度下降法),利用动量的思想提高了迭代效率并保证了正确地收敛。

如上图所示,在该物理系统中有一个小球(质点),它所处的水平方向的位置对应为w的值,而垂直方向对应为损失。设其质量m=1 ,在第i时刻,在单位时间内,该质点受外力而造成的动量改变为:

$Ft = mv_{i} - mv_{i-1}$

因m=1,t=1,可化简为

$F = v_{i} - v_{i-1}$

小球受到的外力F又可以分为两个分量:重力沿斜面向下的力IG和粘滞阻尼力IV
IG的方向与损失的梯度方向相反,取系数为η,表示为IG=-ηg
IV可表示为IV=-cv,c为粘滞阻尼系数

$F = I_{G} + I_{V}$
$ \quad= - ηg - cv$

可推出

$v_{i} - v_{i-1} = - ηg_{i} - cv_{i}$
$v_{i} + cv_{i} = v_{i-1} - ηg_{i} $
$ (1 + c)v_{i} = v_{i-1} - ηg_{i} $

设一个系数α为1/(1+c),上式便近似为

$v_{i} = αv_{i-1} - ηg_{i-1}$

然后对”位置”(参数w)进行更新:

$w_{i} = w_{i-1} + v_{i}t$
$ \Delta w = v_{i}t$
$ \Delta w = αv_{i-1} - ηg_{i-1}$

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# Momentum梯度下降算法
#========================================================

def gradient_descent_with_momentum(X_train, y_train):
'''
Momentum梯度下降算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 初始速度为0
v = 0
# 动量系数
alpha = 0.9
# 初始化参数
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
v = alpha * v - lr * gradient
# 参数更新
w = w + v

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = gradient_descent_with_momentum(X_train, y_train)
print(w)

2、Nesterov Momentum

Nesterov Momentum是Momentum的改进版本,因为有了”预测”功能,所以损失函数收敛更快一些。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# Nesterov Momentum梯度下降算法
#========================================================

def gradient_descent_with_nesterov_momentum(X_train, y_train):
'''
Nesterov Momentum梯度下降算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 初始速度为0
v = 0
# 动量系数
alpha = 0.9
# 初始化参数
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
v_pre = v
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
v = alpha * v - alpha * lr * gradient
v = v + alpha * (v - v_pre) # 提前更新v
# 参数更新
w = w + v

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = gradient_descent_with_nesterov_momentum(X_train, y_train)
print(w)

3、AdaGrad

AdaGrad全称为Adaptive Subgradient(自适应次梯度法),其主要特点在于不断累加每次训练中梯度的平方。
公式如下:

$r_{i} = r_{i-1} + gradient^{2}$
$ \Delta w = - \frac{η}{\sqrt{r_{i}}+ε}$
$ w_{i} = w_{i-1} + \Delta w$

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
63
64
65
66
67
68
69
70
71
72
73
74
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.05
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# AdaGrad算法
#========================================================


def AdaGrad(X_train, y_train):
'''
AdaGrad算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 初始化参数
r = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
r = r + np.square(gradient)
# 参数更新
w = w - lr * gradient /(np.sqrt(r)+1e-8)

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = AdaGrad(X_train, y_train)
print(w)

4、RMSProp

RMSProp全称为Root Mean Square prop(均方根传播法),是AdaGrad的改进算法,其公式和AdaGrad的区别只有r的计算不同。
公式如下:

$ r_{i} = βr_{i-1} + (1-β)gradient^{2}$
$ \Delta w = - \frac{η}{\sqrt{r_{i}}+ε}$
$ w_{i} = w_{i-1} + \Delta w$

可以看出,与AdaGrad不同,RMSProp只会累积近期的梯度信息,对于”遥远的历史”会以指数衰减的形式放弃。
并且AdaGrad算法虽然在凸函数(Convex Functions)上表现较好,但是当目标函数非凸时,算法梯度下降的轨迹所经历的结构会复杂的多,早期梯度对当前训练没有太多意义,此时RMSProp往往表现更好。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.005
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# RMSProp算法
#========================================================


def RMSProp(X_train, y_train):
'''
RMSProp算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 衰减参数
beta = 0.8
# 初始化参数
r = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
r = beta * r + (1 - beta) * np.square(gradient)
# 参数更新
w = w - lr * gradient /(np.sqrt(r)+1e-8)

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = RMSProp(X_train, y_train)
print(w)

5、AdaDelta

AdaDelta全称为Adaptive Delta(自适应学习率法),是与RMSProp相同时间对立发展出来的一个算法,在实现上可以看作是RMSProp的一个变种。不需要设置学习率是该算法的一大优势。
公式如下:

$r_{i} = βr_{i-1} + (1-β)gradient^{2}$
$ \Delta w = - \frac{\sqrt{s_{i-1}}+ε}{\sqrt{r_{i}}+ε}$
$ s_{i} = βs_{i-1}* (1-β)\Delta w^{2}$
$ w_{i} = w_{i-1} + \Delta w$

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# AdaDelta算法
#========================================================

def AdaDelta(X_train, y_train):
'''
AdaDelta算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 衰减参数
beta = 0.8
# 初始化参数
r = 1e-5
s = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
r = beta * r + (1 - beta) * np.square(gradient)
# 参数更新
dw = - (np.sqrt(s)+1e-8) * gradient/(np.sqrt(r)+1e-8)
s = beta * s + (1 - beta) * np.square(dw)
w = w + dw

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = AdaDelta(X_train, y_train)
print(w)

6、Adam

Adam可以看作是Momentum与RMSProp的一个结合体,该算法通过计算梯度的一阶矩估计和二阶矩估计而为不同的参数设计独立的自适应性学习率。
公式如下:

$s_{i} = αs_{i-1} + (1-α)gradient$
$r_{i} = βr_{i-1} + (1-β)gradient^{2}$
$s_{ub} = \frac{s_{i}}{1-α^{i}}$
$r_{ub} = \frac{r_{i}}{1-β^{i}}$
$ \Delta w = - η \frac{s_{ub}}{\sqrt{r_{ub}+ε}}$
$ w_{i} = w_{i-1} + \Delta w$

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# Adam算法
#========================================================

def Adam(X_train, y_train):
'''
Adam算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 衰减参数
beta = 0.8
alpha = 0.8
# 初始化参数
r = 1e-5
s = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
s = alpha * s + (1 - alpha) * gradient
r = beta * r + (1 - beta) * np.square(gradient)
s_ub = s / (1 - alpha**(epoch+1))
r_ub = r / (1 - beta**(epoch+1))
# 参数更新
dw = - lr * s_ub/(r_ub+1e-8)**0.5
w = w + dw

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = Adam(X_train, y_train)
print(w)

7、AdaMax

AdaMax是Adam的变种,区别在于r的选取。
公式如下:

$ s_{i} = αs_{i-1} + (1-α)gradient $
$ s_{ub} = \frac{s_{i}}{1-α^{i}} $
$ r_{i} = max(βr_{i-1}, abs(gradient)) $
$ \Delta w = - η \frac{s_{ub}}{r_{i}} $
$ w_{i} = w_{i-1} + \Delta w $

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# AdaMax算法
#========================================================

def AdaMax(X_train, y_train):
'''
AdaMax算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 衰减参数
beta = 0.8
alpha = 0.8
# 初始化参数
r = 1e-5
s = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
s = alpha * s + (1 - alpha) * gradient
r = np.maximum(beta * r, np.abs(gradient))
s_ub = s / (1 - alpha**(epoch+1))
# 参数更新
dw = - lr * s_ub/(r+1e-8)
w = w + dw

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = AdaMax(X_train, y_train)
print(w)

8、Nadam

Adam可以看作是Momentum与RMSProp的结合,既然Nesterov的表现较Momentum更优,那么自然也就可以把Nesterov Momentum与RMSProp组合到一起了,于是就有了Nadam。
公式如下:

$ s_{i} = αs_{i-1} + (1-α)gradient $
$ r_{i} = βr_{i-1} + (1-β)gradient^{2} $
$ s_{ub} = \frac{s_{i}}{1-α^{i}} $
$ r_{ub} = \frac{r_{i}}{1-β^{i}} $
$ \Delta w = - \frac{η}{\sqrt{r_{ub}+ε}}(αs_{ub}+ \frac{(1-α)*gradient}{(1-α^{i})}) $
$ w_{i} = w_{i-1} + \Delta w $

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# Nadam算法
#========================================================

def Nadam(X_train, y_train):
'''
Nadam算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 衰减参数
beta = 0.8
alpha = 0.8
# 初始化参数
r = 1e-5
s = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
s = alpha * s + (1 - alpha) * gradient
r = beta * r + (1 - beta) * np.square(gradient)
s_ub = s / (1 - alpha**(epoch+1))
r_ub = r / (1 - beta**(epoch+1))
# 参数更新
dw = - lr /(r_ub+1e-8)**0.5 * (alpha * s_ub + ((1-alpha)/(1 - alpha**(epoch+1) ) * gradient))
w = w + dw

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = Nadam(X_train, y_train)
print(w)

9、NadaMax

按照Nadam同样的思路,可以将Nesterov与AdaMax结合变成NadaMax
公式如下:

$s_{i} = αs_{i-1} + (1-α)gradient$
$r_{i} = βr_{i-1} + (1-β)gradient^{2}$
$s_{ub} = \frac{s_{i}}{1-α^{i}}$
$r_{ub} = \frac{r_{i}}{1-β^{i}}$
$ \Delta w = - \frac{η}{1-α^{i}}\frac{1}{r_{i}}(αs_{i}+ (1-α)*gradient)$
$ w_{i} = w_{i-1} + \Delta w$

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
import math

#========================================================
# 参数设置
#========================================================

# 学习率
learning_rate = 0.001
# 迭代次数
n_epochs = 50000
# 设置阈值
epsilon = 1e-5

#========================================================
# 生成数据集
#========================================================

# 构造训练数据集
x = np.array([[2, 0., 3], [3, 1., 3], [0, 2., 3], [4, 3., 2], [1, 4., 4]])

# 构建一个权重作为数据集的真正的权重
w0 = np.array([[2 ,3, 4]]).T
# 构建标签数据集y=t1*x1+t2*x2+t3*x3+b 即y=x*w+b, 这里b=2
y_train = x.dot(w0) + np.array([[2],[2],[2],[2],[2]]) + np.random.randn(1)

# 构建一个len(x)行1列的单位矩阵x0,然它和x组合,形成[x0, x1, x2, x3],x0=1的数据形式
# 这样可以将y=t1*x1+t2*x2+t3*x3+b变成y=b*x0+t1*x1+t2*x2+t3*x3即y=x*w,其中w应该为[b, *, *, *],则要拟合的w应该是[2,2,3,4]
x0 = np.full((len(x), 1), 1)
X_train = np.hstack([x0, x])

#========================================================
# NadaMax算法
#========================================================

def NadaMax(X_train, y_train):
'''
NadaMax算法的实现
INPUT -> 输入, 目标
'''
lr = learning_rate
# 初始化迭代次数
count = 0
# 衰减参数
beta = 0.8
alpha = 0.8
# 初始化参数
r = 1e-5
s = 1e-5
w = np.random.randn(X_train.shape[1], 1)
before_w = np.zeros((X_train.shape[1], 1))

for epoch in range(n_epochs):
count += 1
error = np.dot(X_train, w) - y_train
gradient = np.dot(X_train.T, error) / X_train.shape[0]
s = alpha * s + (1 - alpha) * gradient
r = np.maximum(beta * r, np.abs(gradient))
s_ub = s / (1 - alpha**(epoch+1))
# 参数更新
dw = - lr /(1-alpha**(epoch+1)) * (1/r) * (alpha * s + (1 - alpha) * gradient)
w = w + dw

# w-before_w表示前后两个参数的变化,当梯度变化很小(在接收的范围内)时,便停止迭代
if np.linalg.norm(w - before_w) < epsilon:
print(count)
break
else:
before_w = w

return w

#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
w = NadaMax(X_train, y_train)
print(w)
0%