梯度下降算法是机器学习领域中非常常用的优化算法。本文通过对梯度下降算法、AdaGrad算法、SGD算法、动量算法以及牛顿动量算法的介绍，将比较基础的梯度下降算法变种介绍给读者。
目的
对于一个含参的函数，通过不断求解当前点的梯度值，并以该梯度值成负比例的步长不断更新所求点，以求解出使其函数值最小的一组参数。
思想
对于一个含参的函数，以与函数在当前点梯度（近似）成负比例的步长来不断更新该参数，使其不断向该参数偏导为0的点逼近，以找到函数的局部最小值。 当我们从损失函数的某一点出发，在该点附近做出以常数η为参数的一个邻域，根据微积分所学的知识可知，我们在该邻域上一定可以找出一个找到极小值。我们以该极小值点为下一步我们需要跟进的点，更新之后我们再在该点附近做出以常数η为参数的一个邻域并重复以上过程。通过这样的不断更新，我们理论上一定可以找出一个全局的极小值点或者是导数为0的驻点。
关于在某一邻域上如何找到该邻域上的局部最小值点。我们可以通过泰勒展开，该邻域上的损失函数可以近似写成 $L(\theta)=L(a,b)+u(\theta_1-a)+v(\theta_2-b)$也就是我们所熟知的全微分方程。令 $\Delta\theta_1=\theta_1-a;\Delta\theta_2=\theta_2-b$ 因为L(a,b)为一个常数，所以L的极小值直接取决于 u+ v同时我们可以将其书写成向量的形式$(\Delta\theta_1,\Delta\theta_2)·(u,v)$显然$(\Delta\theta_1,\Delta\theta_2)$与(u,v)反向时L最小，即
$$
\begin{bmatrix}
\Delta\theta_1 \\\\
\Delta\theta_2
\end{bmatrix}
=-\eta
\begin{bmatrix}
u \\\\
v
\end{bmatrix}
$$其中u和v分别为函数的偏导数值且η取值越小该结果越准确。
实现
用均方误差构造一个以函数f为自变量的二元损失函数 ：
(因为f = w*x + b所以也可以看出以w和b为自变量的函数)1
L(f)=L(w,b)=((y - (w * x + b))**2).sum()/len(x)
首先考虑只有一个参数 w 的损失函数，随机的选取一个初始点，计算此时 L 对 w 的微分，然后顺着切线下降的方向更改 w 的值1
w = w - grad(w)*learning_rate
此后，w会不断靠近微分近似为0的点以达成目标。同样方法求出所有参数的值。而实际上我们所需要的是不断同时更新损失函数所需要的所有参数的值，我们在编程中只需要让所有参数的更新在同一次迭代过程中更新即可，因为当迭代次数足够多的时候，每一次的迭代都可以看成在很短的一个小时间段中进行，因此每次迭代的不同参数更新可以近似看成时在同一时间段所更新的，即达到了我们要求梯度下降同时更新损失函数中含有的所有参数的要求。
问题
学习率的不确定性所带来的一系列问题，比如若学习率过大，导致每次更新的步长过大，而过大的步长有可能并不符合实际更新的情况，导致了过大的学习率会使不断更新的参数在最值点上方震荡，甚至直接跨过最值点使损失函数值不断增大，无法逼近最值点；如果学习率过小，尽管较小的学习率符合我们梯度下降的数学原理，可以求得较为准确的符合我们预期的参数值。但是同时，过小的学习率会使更新的速度较慢，在计算中往往导致浪费计算机时间与性能，在我们的日常实际生活运用中可能会等不及出结果。
优化思路
通常刚开始，初始点会距离极值点比较远，所以使用大一点的学习率。而更新好几次参数之后呢，此时的参数点比较靠近最低点，故而可适当减小学习率。即随着次数的增加，使学习率的大小与更新次数呈负相关，例如采取将学习率除以次数加一的开根号$lr/\sqrt{t+1} \quad$等方法。
优化算法
AdaGrad算法（适应性梯度算法）：
每个参数的学习率都除上之前该参数所有微分的均方根[。为每一个参数保留一个学习率以提升在稀疏梯度上的性能。1
2lr_b += b_grad ** 2
b -= lr/np.sqrt(lr_b) * b_grad
适应性梯度算法中的学习率($\eta_t/\sigma_t$)由两部分组成，其中 $\eta_t=\eta/\sqrt{t+1} \quad$即随着迭代次数的增加，不断削减学习率使每次更新的步长不断变小。$\sigma_t=\sqrt{\frac{\sum_{i=1}^t(g^i)^2\quad}{(t+1)}} \quad$即之前该参数所有微分和的均方根，用此作为分母用意在：如果走到当前点的微分过小，可以控制学习率让其步长适当增大一点；如果走到当前点的微分过大，通过控制学习率使其步长适当减小一点。如此，得到我们的学习率$\frac{\eta_t}{\sigma_t}=\frac{\eta}{\sqrt{\sum_{i=1}^t(g^i)^2\quad} \quad}g^t$接下来给出更本质的解释：适应性梯度算法中学习率近似于(|一阶导数|/二阶导数)。对于只有一个自变量的函数，我们可以用其一阶导数来表示该点的下降速率。但是对于有多个自变量的函数，每更新一次，所选取合适点的标准如果只有一阶导数唯一一个衡量标准显然是不合适的。而二次微分可以在一定程度上反映出当前点到偏导为0的驻点的距离。综合考虑着这两个因子，可以较好地提供出一个符合我们期望的学习率。而对于二次微分，我们用一次微分的均方根来表示，它可以在一定程度上反映二次微分的大小。例如如果二次微分较小，则一次微分图像斜率较缓，那么一次微分的均方根相对而言会较小。适应性梯度算法最好的举例便是一元二次函数 ，其最佳步长为 即|2ax+b|/2a上下分别是该一元二次函数的一次微分和二次微分。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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122import matplotlib.pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D
import random
w_init = 4.2
b_init = -150
def f(x):
return w_init * x + b_init
def initDate():
x_data = []
y_data = []
for i in range(10):
x = random.randint(-99,99)
x_data.append(x)
y_data.append(f(x)+f(x)/10*random.randint(-1,1))
# 给数据加点噪声，使过程更加真实一点
return x_data,y_data
def exhaustion(x_data,y_data):
# 通过穷举法试探出使均方误差最小的一组b&w
x = np.arange(-abs(1.5*b_init),abs(1.5*b_init),abs(b_init)/20) #bias
Y= np.arange(-abs(1.5*w_init),abs(1.5*w_init),abs(w_init)/20) #weight
Z = np.zeros((len(x),len(y)))
X,Y = np.meshgrid(x,y)
#return两个矩阵,X的行向量是向量x的简单复制,Y的列向量是向量y的简单复制
x_data = np.array(x_data)
y_data = np.array(y_data)
for i in range(len(x)):
for j in range(len(y)):
b = x[i]
w = y[j]
Z[j][i] = ((y_data - b - w * x_data)**2).sum()/len(x_data)
# Z值最小的那一组x[i]y[j]就是我们所期望的使f值最小的b，w
return X,Y,Z
def gradientDescent(x_data,y_data):
#initial:
b = 0
w = 0
lr = 1 # learning rate
iteration = 100000
b_history = [b]
w_history = [w]
# 我们实际用gandient descent求出的b&w
lr_b = 0
lr_w = 0
for i in range(iteration):
#不断向偏导为0的驻点靠拢，以获取均方误差最小的一组解w、b
x = np.array(x_data)
y = np.array(y_data)
b_grad = -2.0*(y - b - w*x)
w_grad = -2.0*(y - b - w*x)*x
b_grad = b_grad.sum()/len(x)
w_grad = w_grad.sum()/len(x)
lr_b += b_grad ** 2
lr_w += w_grad ** 2
#update parameters:
b -= lr/np.sqrt(lr_b) * b_grad
w -= lr/np.sqrt(lr_w) * w_grad
#store parameters for plotting:
b_history.append(b)
w_history.append(w)
return b_history,w_history
def getPicture(b_history,w_history,X,Y,Z):
plt.figure('gradient_descent')
plt.contourf(X,Y,Z,50,alpha=0.5,cmap=plt.get_cmap('jet'))
plt.plot([b_init],[w_init],'x',ms=12,markeredgewidth=3,color='orange')
plt.plot(b_history,w_history,'o-',ms=3,lw=1.5,color='black')
plt.xlim(-abs(1.5*b_init),abs(1.5*b_init))
plt.ylim(-abs(1.5*w_init),abs(1.5*w_init))
plt.xlabel(r'$b$',fontsize=16)
plt.ylabel(r'$w$',fontsize=16)
def get3D(b_history,w_history,X,Y,Z):
#为了画好看的三维图并考虑到memory error强行又弄了组数据
b_h = b_history[::1000]
w_h = w_history[::1000]
B,W = np.meshgrid(b_h,w_h)
Q = np.zeros(len(b_h))
for i in range(len(b_h)):
for n in range(len(x_data)):
Q[i] = Q[i] + (y_data[n] - b_h[i] - w_h[i] * x_data[n])**2
Q[i] = Q[i]/len(x_data) # 均方误差
ax = Axes3D(plt.figure('三维图'))
ax.plot_surface(X,Y,Z,cmap = 'rainbow')
ax.plot([b_init],[w_init],'x',ms=12,markeredgewidth=3,color = 'orange')
ax.plot(b_h,w_h,Q,'o-',ms=3,lw=1.5,color='black')
ax.set_xlabel('--b--')
ax.set_ylabel('--w--')
ax.set_zlabel('--z--')
ax.set_title('3D')
def initPicture(b,w):
plt.figure('initial')
x = np.linspace(-99,99)
y_init = f(x) # 所求目标函数的函数值
y_grad = w*x+b # 梯度下降求出的函数所对应的函数值
plt.plot(x,y_init,'.')
plt.plot(x,y_grad)
if __name__ == '__main__':
x_data,y_data = initDate() # 获取实验数据
X,Y,Z = exhaustion(x_data,y_data) # X&Y为网格图，Z为其函数值
b_history,w_history = gradientDescent(x_data,y_data)
b = b_history[-1];print(b)
w = w_history[-1];print(w)
getPicture(b_history,w_history,X,Y,Z) # 绘制图像
get3D(b_history,w_history,X,Y,Z)
initPicture(b,w)
plt.show()
SGD算法（Stochastic Gradient Descent随机梯度下降算法）：
随机梯度下降算法与基础的梯度下降极为相似，唯一的不同点在于它是从某一个样本点出发而并非像梯度下降算法那样每次都考虑整体的数值同时更新。随机梯度下降算法的优点是很明显的，计算的速度和效率要比普通的梯度下降快得多。而这样所带来的缺点就是随机梯度下降算法的路线可能会不断抖动，并且可能优化过程充满震荡，但同时，正是因为这种大幅度的震荡，有时可以解决大部分梯度下降算法都会面临的一个绝对难题，即“陷进”局部最小值点。大部分梯度下降算法在优化过程中很可能会被困在某个驻点，而随机梯度下降算法有时可以通过优化过程的抖动而逃离当前的局部最小值点。这也是很多自适应优化算法在实际训练出的结果都不如随机梯度下降算法的原因。
Momentum算法（动量算法）：
momentum即动量，该算法在普通的梯度下降中引入了动量这个因子是因为普通的梯度下降算法，在每一次更新完成后在当前点的附近邻域上所求得的局部最小值点的方向很大可能是和之前一步的方向几乎相反的，这就导致了普通梯度下降算法在更新当前点时很容易不断震荡，效率低下不符合我们的期望。由此我们采用了动量算法，即增加一个变量v表示速度更新，在每次参数更新的时候加上计算出的当前的速度更新值v= γ· v - η·grad（其中参数γ为衰减权重，一般为0.9，可以让早期的梯度对当前梯度的影响越来越小）其中这个0.9倍上一个点的梯度下降方向就表示了当前该点的动量，让该动量与当前点的梯度方向做矢量和。之后将原参数更新θ = θ + v即可。这样每次更新就会多更新一部分上一次迭代的更新量，来平滑这一次迭代的梯度。从物理的角度来解释，就像是一个小球在滚落的过程中会受其自身的历史动量所影响，所以才称为动量算法。动量算法中学习率越大（实际情况中一般学习率比较小，例如0.001），当前梯度对现在更新的影响也就越大；v中含有所有速度更新值，可以反映历史时刻梯度方向。而由于动量积攒了历史的梯度，如点P前一刻的梯度与当前的梯度方向几乎相反。因此原本在P点原本要大幅徘徊的梯度，主要受到前一时刻的影响，而导致在当前时刻的梯度幅度减小。要是当前时刻的梯度与历史时刻梯度方向相似，这种趋势在当前时刻则会加强；要是不同，则当前时刻的梯度方向减弱。
NAG算法（牛顿动量算法Nesterov accelerated gradient）：
由之前所说，动量算法每下降一步都是由前面下降方向的一个累积和当前点的梯度方向组合而成。那么既然每一步都要将两个梯度方向（历史梯度、当前梯度）做一个合并再下降，那为什么不先按照历史梯度往前走那么一小步，按照前面一小步位置的“超前梯度”来做梯度合并呢？所以牛顿动量算法和动量算法唯一的区别就在于它的梯度不是根据当前参数位置，而是根据先走了一步本来计划要走的一步后达到参数的位置计算出来的。具体做法为先临时更新θ’ = θ + γ· v然后计算临时点的梯度grad’并计算出速度更新v= γ· v - η·grad’最后应用更新θ = θ + v即可。牛顿动量算法其实是相比于动量算法多考虑了本次梯度相对于上次梯度的变化量，而这个变化量本质是对于目标函数二阶导的近似。
