梯度下降、随机梯度下降、批量梯度下降

引言

李航老师在《统计学习方法》中将机器学习的三要素总结为:模型、策略和算法。其大致含义如下:

模型:其实就是机器学习训练的过程中所要学习的条件概率分布或者决策函数。

策略:就是使用一种什么样的评价,度量模型训练过程中的学习好坏的方法,同时根据这个方法去实施的调整模型的参数,以期望训练的模型将来对未知的数据具有最好的预测准确度。

算法:算法是指模型的具体计算方法。它基于训练数据集,根据学习策略,从假设空间中选择最优模型,最后考虑用什么样的计算方法去求解这个最优模型。

很多时候机器学习工程师又戏称调参工程师, 由此可见参数调优时作为机器学习工程师必须掌握的一项核心技能。

这篇文章的目的旨在对常用的参数调优算法进行一次梳理便于随时翻阅。

1. 梯度下降法(Gradient Descent)

1.1 一般解释

$f(x)$在$x_0$的梯度:就是$f(x)$变化最快的方向。梯度下降法是一个最优化算法,通常也称为最速下降法

假设$f(x)$是一座山,站在半山腰,往x方向走1米,高度上升0.4米,也就是说x方向上的偏导是 0.4;往y方向走1米,高度上升0.3米,也就是说y方向上的偏导是 0.3;这样梯度方向就是 (0.4 , 0.3),也就是往这个方向走1米,所上升的高度最高。梯度不仅仅是$f(x)$在某一点变化最快的方向,而且是上升最快的方向;如果想下山,下降最快的方向就是逆着梯度的方向,这就是梯度下降法,又叫最速下降法。

1.2 梯度下降算法用途

最速下降法是求解无约束优化问题最简单和最古老的方法之一,虽然现在已经不具有实用性,但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向的,最速下降法越接近目标值,步长越小,前进越慢。

在梯度下降算法中,都是围绕以下这个式子展开:

其中在上面的式子中$h_θ(x)$代表,输入为x的时候的其当时θ参数下的输出值,与y相减则是一个相对误差,之后再平方乘以1/2,并且其中:

这里我列举了一个简单的例子,当然实际的x可以有n多个维度。我们知道曲面上方向导数的最大值的方向就代表了梯度的方向,因此我们在做梯度下降的时候,应该是沿着梯度的反方向进行权重的更新,可以有效的找到全局的最优解。这个θ的更新过程可以描述为:

这里就是根据每一个 x 的分量以及当时的偏差值进行 θ 的更新,其中 α 为步长,这个参数如果设置的太大,那么很容易就在最优值附加徘徊;相反,如果设置的太小,则会导致收敛速度过慢。

关于步长和学习速率的关系,这里提一下其实这两个是一个概念,叫法不一样,最优化问题中叫步长,但一般在神经网络中也叫学习速率。

1.3 梯度下降、随机梯度下降、批量梯度下降

  • 梯度下降:梯度下降就是上面的推导,要留意,在梯度下降中,对于θ的更新,所有的样本都有贡献,也就是参与调整θ.其计算得到的是一个标准梯度。因而理论上来说一次更新的幅度是比较大的。如果样本不多的情况下,当然是这样收敛的速度会更快啦~

  • 随机梯度下降:可以看到多了随机两个字,随机也就是说用样本中的一个例子来近似所有的样本,来调整θ,因而随机梯度下降是会带来一定的问题,因为计算得到的并不是准确的一个梯度,容易陷入到局部最优解中。随机梯度下降每次迭代只使用一个样本,迭代一次计算量为n2,当样本个数m很大的时候,随机梯度下降迭代一次的速度要远高于批量梯度下降方法。

  • 批量梯度下降:其实批量的梯度下降就是一种折中的方法,他用了一些小样本来近似全部的,其本质就是随机指定一个例子替代样本不太准,而且批量的话还是非常可以反映样本的一个分布情况的。批量梯度下降最小化所有训练样本的损失函数,使得最终求解的是全局的最优解,即求解的参数是使得风险函数最小,但是对于大规模样本问题效率低下。

  • 概括

    随机梯度下降是通过每个样本来迭代更新一次,如果样本量很大的情况(例如几十万),那么可能只用其中几万条或者几千条的样本,就已经将theta迭代到最优解了,对比批量梯度下降,迭代一次需要用到十几万训练样本,一次迭代不可能最优,如果迭代10次的话就需要遍历训练样本10次。但是,SGD伴随的一个问题是噪音较BGD要多,使得SGD并不是每次迭代都向着整体最优化方向。

    随机梯度下降每次迭代只使用一个样本,迭代一次计算量为n2,当样本个数m很大的时候,随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解:随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价,换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

  • 对批量梯度下降法和随机梯度下降法的总结:

    批量梯度下降—最小化所有训练样本的损失函数,使得最终求解的是全局的最优解,即求解的参数是使得风险函数最小,但是对于大规模样本问题效率低下。

    随机梯度下降—最小化每条样本的损失函数,虽然不是每次迭代得到的损失函数都向着全局最优方向, 但是大的整体的方向是向全局最优解的,最终的结果往往是在全局最优解附近,适用于大规模训练样本情况。

梯度下降代码:

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
import random
#This is a sample to simulate a function y = theta1*x1 + theta2*x2
input_x = [[1,4], [2,5], [5,1], [4,2]]
y = [19,26,19,20]
theta = [1,1]
loss = 10
step_size = 0.001
eps =0.0001
max_iters = 10000
error =0
iter_count = 0
while( loss > eps and iter_count < max_iters):
loss = 0
#这里更新权重的时候所有的样本点都用上了
for i in range (3):
pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]
for i in range (3):
pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
error = 0.5*(pred_y - y[i])**2
loss = loss + error
iter_count += 1
print 'iters_count', iter_count

print 'theta: ',theta
print 'final loss: ', loss
print 'iters: ', iter_count
output:

iters_count 219
iters_count 220
iters_count 221
iters_count 222
iters_count 223
iters_count 224
iters_count 225
theta: [3.0027765778748003, 3.997918297015663]
final loss: 9.68238055213e-05
iters: 225
[Finished in 0.2s]

随机梯度下降代码:

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
# 每次选取一个值,随机一个点更新 θ
import random
#This is a sample to simulate a function y = theta1*x1 + theta2*x2
input_x = [[1,4], [2,5], [5,1], [4,2]]
y = [19,26,19,20]
theta = [1,1]
loss = 10
step_size = 0.001
eps =0.0001
max_iters = 10000
error =0
iter_count = 0
while( loss > eps and iter_count < max_iters):
loss = 0
#每一次选取随机的一个点进行权重的更新
i = random.randint(0,3)
pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]
for i in range (3):
pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
error = 0.5*(pred_y - y[i])**2
loss = loss + error
iter_count += 1
print 'iters_count', iter_count

print 'theta: ',theta
print 'final loss: ', loss
print 'iters: ', iter_count
iters_count 1226
iters_count 1227
iters_count 1228
iters_count 1229
iters_count 1230
iters_count 1231
iters_count 1232
theta: [3.002441488688225, 3.9975844154600226]
final loss: 9.989420302e-05
iters: 1232
[Finished in 0.3s]

批量随机梯度下降代码:

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
# 这里用2个样本点
import random
#This is a sample to simulate a function y = theta1*x1 + theta2*x2
input_x = [[1,4], [2,5], [5,1], [4,2]]
y = [19,26,19,20]
theta = [1,1]
loss = 10
step_size = 0.001
eps =0.0001
max_iters = 10000
error =0
iter_count = 0
while( loss > eps and iter_count < max_iters):
loss = 0

i = random.randint(0,3) #注意这里,我这里批量每次选取的是2个样本点做更新,另一个点是随机点+1的相邻点
j = (i+1)%4
pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]

pred_y = theta[0]*input_x[j][0]+theta[1]*input_x[j][1]
theta[0] = theta[0] - step_size * (pred_y - y[j]) * input_x[j][0]
theta[1] = theta[1] - step_size * (pred_y - y[j]) * input_x[j][1]
for i in range (3):
pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
error = 0.5*(pred_y - y[i])**2
loss = loss + error
iter_count += 1
print 'iters_count', iter_count

print 'theta: ',theta
print 'final loss: ', loss
print 'iters: ', iter_count
.....
iters_count 543
iters_count 544
iters_count 545
iters_count 546
iters_count 547
iters_count 548
iters_count 549
theta: [3.0023012574840764, 3.997553282857357]
final loss: 9.81717138358e-05
iters: 549