gradient descent

导读

gradient descent
momentum
RMSProp
adam
鞍点

gradient descent根据每次迭代时计算梯度的样本大小，可以分为bath, mini-batch, SGD；对gd的优化，可通过修改迭代步长或alpha值改进；优化迭代步长的算法有：momentum, RMSProp, adam等；修改alpha值：learning rate decay，learning rate的衰减有不同的方法，以下列举常用的几种
alpha = alpha_0 / (1 + decay_rate * t);
alpha = alpha_0 * 0.95 ** t;
alpha = alpha_0 * k / sqrt(t); ...

本文只讨论标准gd及其对迭代步长优化的算法，假设优化函数为：z = x ** 2 + 5y ** 2,

import matplotlib.pyplot as plt
import numpy as np

#椭圆等高线
x = y = np.linspace(-10, 10, 1000)
x,y = np.meshgrid(x,y)
z =  x ** 2  + 5 * y ** 2

plt.contour(x,y,z)
plt.show()

image.png

gd算法：x := x - alpha * dx, y := y = alpha * dy
其中 dx=2x, dy = 10y，令初始点(x, y) = (8, 9)

plt.contour(x, y, z)
plt.scatter(0,0)
plt.xlabel("x")
plt.ylabel("y")

alpha = 0.01
w = np.array([2, 0, 0, 10]).reshape(2, 2)
t = np.array([9, 8]).reshape(2, 1)
plt.scatter(t[0], t[1])
for i in range(1, 100):
    dt = np.dot(w, t)
    t_step = dt
    t = t - alpha * t_step
    plt.scatter(t[0], t[1])
print("最终值")
print(t[0], t[1])
plt.show()

最终值
[1.2179347] [0.0002361]

image.png

alpha值的设置

def gd(alpha):
    w = np.array([2, 0, 0, 10]).reshape(2, 2)
    t = np.array([9, 8]).reshape(2, 1)
    i = 1
    iter_array = []
    result_array = []
    iter_array.append(i)
    result = t[0] ** 2  + 5 * t[1] ** 2
    result_array.append(result)
    while i < 100:
        dt = np.dot(w, t)
        t_step = dt
        t = t - alpha * t_step
        iter_array.append(i)
        result = t[0] ** 2  + 5 * t[1] ** 2
        result_array.append(result)
        i+=1
    return iter_array, result_array

def get_convergence_iter(i_result_array, threshold):
    i = 0
    while i < len(i_result_array):
        t = i_result_array[i]
        if abs(t) < threshold:
            return i+1
        i+=1
    return i+1

for i in range(1, 20):
    i_new = i / 100
    i_iter_array, i_result_array = gd(i_new)
    print('alpha值：%.2f, 收敛次数：%d' %(i_new,get_convergence_iter(i_result_array, 0.0001)))

for i in [0.01, 0.1, 0.2005]:
    i_iter_array, i_result_array = gd(i)
    plt.plot(i_iter_array, i_result_array, label="alpha:%.4f" %(i))
plt.legend()
plt.show()

alpha值：0.01, 收敛次数：101
alpha值：0.02, 收敛次数：101
alpha值：0.03, 收敛次数：101
alpha值：0.04, 收敛次数：83
alpha值：0.05, 收敛次数：66
alpha值：0.06, 收敛次数：55
alpha值：0.07, 收敛次数：47
alpha值：0.08, 收敛次数：41
alpha值：0.09, 收敛次数：36
alpha值：0.10, 收敛次数：32
alpha值：0.11, 收敛次数：29
alpha值：0.12, 收敛次数：26
alpha值：0.13, 收敛次数：24
alpha值：0.14, 收敛次数：22
alpha值：0.15, 收敛次数：21
alpha值：0.16, 收敛次数：19
alpha值：0.17, 收敛次数：23
alpha值：0.18, 收敛次数：35
alpha值：0.19, 收敛次数：73

image.png

上述结果可知，随着alpha值增加，迭代次数先减小，后增大，最后发散；alpha值需要合理设置，否则优化算法不能收敛

gd的优化

momentum

momentum算法在梯度的基础上加上指数滑动平均；
gd算法：x := x - alpha * dx；
momentum算法：
vdx = beta * vdx + (1-beta) * dx,
x := x - alpha * vdx
采用SGD或mini-bath训练机器学习或神经网络模型的时候，dw受每次迭代的batch影响，造成步长的摆动，而采用滑动平均可以减少摆动的幅度，从而加快收敛速度。

plt.contour(x, y, z)
plt.scatter(0,0)
plt.xlabel("x")
plt.ylabel("y")

alpha = 0.2005

#gd
w = np.array([2, 0, 0, 10]).reshape(2, 2)
t = np.array([9, 8]).reshape(2, 1)
dy_value = []
for i in range(1, 100):
    dt = np.dot(w, t)
    t_step = dt
    dy_value.append(round(t_step[1][0],2))
    t = t - alpha * t_step
print("gd的更新步长(y值)")
print(dy_value)

#momentum
beta = 0.9
w = np.array([2, 0, 0, 10]).reshape(2, 2)
t = np.array([9, 8]).reshape(2, 1)
plt.scatter(t[0], t[1])
vdt = 0
dy_value = []
for i in range(1, 100):
    dt = np.dot(w, t)
    vdt = beta * vdt + (1-beta) * dt
    t_step = vdt
    dy_value.append(round(t_step[1][0],2))
    t = t - alpha * t_step
    plt.scatter(t[0], t[1])
print("momentum的更新步长(y值)")
print(dy_value)
print("最终值")
print(t[0], t[1])
plt.show()

gd的更新步长(y值)
[80, -80.4, 80.8, -81.21, 81.61, -82.02, 82.43, -82.84, 83.26, -83.67, 84.09, -84.51, 84.93, -85.36, 85.79, -86.21, 86.65, -87.08, 87.51, -87.95, 88.39, -88.83, 89.28, -89.72, 90.17, -90.62, 91.08, -91.53, 91.99, -92.45, 92.91, -93.38, 93.84, -94.31, 94.78, -95.26, 95.73, -96.21, 96.69, -97.18, 97.66, -98.15, 98.64, -99.14, 99.63, -100.13, 100.63, -101.13, 101.64, -102.15, 102.66, -103.17, 103.69, -104.21, 104.73, -105.25, 105.78, -106.31, 106.84, -107.37, 107.91, -108.45, 108.99, -109.53, 110.08, -110.63, 111.19, -111.74, 112.3, -112.86, 113.43, -113.99, 114.56, -115.14, 115.71, -116.29, 116.87, -117.46, 118.04, -118.63, 119.23, -119.82, 120.42, -121.02, 121.63, -122.24, 122.85, -123.46, 124.08, -124.7, 125.32, -125.95, 126.58, -127.21, 127.85, -128.49, 129.13, -129.78, 130.43]
momentum的更新步长(y值)
[8.0, 13.6, 15.91, 14.8, 10.83, 5.09, -1.1, -6.45, -9.97, -11.14, -9.96, -6.9, -2.76, 1.51, 5.06, 7.23, 7.74, 6.65, 4.33, 1.38, -1.56, -3.89, -5.2, -5.35, -4.4, -2.67, -0.57, 1.43, 2.94, 3.71, 3.66, 2.89, 1.61, 0.13, -1.22, -2.19, -2.63, -2.49, -1.87, -0.94, 0.09, 1.0, 1.62, 1.85, 1.69, 1.2, 0.52, -0.19, -0.79, -1.18, -1.29, -1.13, -0.76, -0.27, 0.22, 0.62, 0.85, 0.89, 0.75, 0.47, 0.13, -0.21, -0.47, -0.61, -0.61, -0.5, -0.29, -0.04, 0.18, 0.35, 0.43, 0.42, 0.32, 0.17, 0.0, -0.15, -0.26, -0.31, -0.28, -0.21, -0.1, 0.02, 0.12, 0.19, 0.21, 0.19, 0.13, 0.05, -0.03, -0.1, -0.14, -0.15, -0.13, -0.08, -0.03, 0.03, 0.07, 0.1, 0.1]
最终值
[0.03790624] [-0.00786362]

image.png

momentum算法的效率

def mom(alpha, beta):
    w = np.array([2, 0, 0, 10]).reshape(2, 2)
    t = np.array([9, 8]).reshape(2, 1)
    vdt = 0
    i = 1
    iter_array = []
    result_array = []
    iter_array.append(i)
    result = t[0] ** 2  + 5 * t[1] ** 2
    result_array.append(result)
    while i < 100:
        dt = np.dot(w, t)
        vdt = beta * vdt + (1-beta) * dt
        t_step = vdt
        t = t - alpha * t_step
        iter_array.append(i)
        result = t[0] ** 2  + 5 * t[1] ** 2
        result_array.append(result)
        i += 1
    return iter_array, result_array
beta = 0.9
for i in range(1, 20):
    i_new = i / 10
    i_iter_array, i_result_array = mom(i_new, beta)
    print('alpha值：%.2f, 收敛次数：%d' %(i_new,get_convergence_iter(i_result_array, 0.001)))

for i in [0.01, 0.1, 1]:
    i_iter_array, i_result_array = mom(i, beta)
    plt.plot(i_iter_array, i_result_array, label="alpha:%.2f" %(i))
plt.legend()
plt.show()

alpha值：0.10, 收敛次数：84
alpha值：0.20, 收敛次数：101
alpha值：0.30, 收敛次数：98
alpha值：0.40, 收敛次数：84
alpha值：0.50, 收敛次数：101
alpha值：0.60, 收敛次数：95
alpha值：0.70, 收敛次数：101
alpha值：0.80, 收敛次数：101
alpha值：0.90, 收敛次数：98
alpha值：1.00, 收敛次数：101
alpha值：1.10, 收敛次数：96
alpha值：1.20, 收敛次数：101
alpha值：1.30, 收敛次数：100
alpha值：1.40, 收敛次数：101
alpha值：1.50, 收敛次数：92
alpha值：1.60, 收敛次数：84
alpha值：1.70, 收敛次数：96
alpha值：1.80, 收敛次数：101
alpha值：1.90, 收敛次数：101

image.png

从物理角度理解momentum算法：vdx = beta * vdx + (1-beta) * dw, dw可看作加速度，beta小于1，可看作摩擦力，vdx可看作动量

RMSProp

gd算法的alpha值受限于y轴（y轴斜率大），rmsprop增加了微平方加权平均数，可以消除梯度大的维度的影响，设置更大的alpha值
gd算法：x := x - alpha * dx；
rmsprop算法：
sdx = beta * sdx + (1-beta) * dx ** 2,
x := x - alpha * dx / sqrt(sdx)

plt.contour(x, y, z)
plt.scatter(0,0)
plt.xlabel('x')
plt.ylabel('y')

#rmsprop
alpha = 0.2005
epsilon = 0.00000001
beta = 0.9
w = np.array([2, 0, 0, 10]).reshape(2, 2)
t = np.array([9, 8]).reshape(2, 1)
plt.scatter(t[0], t[1])
sdt = 0
for i in range(1, 100):
    dt = np.dot(w, t)
    sdt = beta * sdt + (1-beta) * dt ** 2
    t_step = dt / (np.sqrt(sdt) + epsilon)
    t = t - alpha * t_step
    plt.scatter(t[0], t[1])
print("最终值")
print(t[0], t[1])
plt.show()

最终值
[-1.6552961e-19] [4.0731588e-20]

image.png

RMSProp算法的效率

def rmsprop(alpha, beta):
    w = np.array([2, 0, 0, 10]).reshape(2, 2)
    t = np.array([9, 8]).reshape(2, 1)
    sdt = 0
    i = 1
    iter_array = []
    result_array = []
    iter_array.append(i)
    result = t[0] ** 2  + 5 * t[1] ** 2
    result_array.append(result)
    while i < 100:
        dt = np.dot(w, t)
        sdt = beta * sdt + (1-beta) * dt ** 2
        t_step = dt / (np.sqrt(sdt)  + epsilon)
        t = t - alpha * t_step
        iter_array.append(i)
        result = t[0] ** 2  + 5 * t[1] ** 2
        result_array.append(result)
        i += 1
    return iter_array, result_array
beta = 0.9
for i in range(1, 20):
    i_new = i / 10
    i_iter_array, i_result_array = rmsprop(i_new, beta)
    print('alpha值：%.2f, 收敛次数：%d' %(i_new,get_convergence_iter(i_result_array, 0.0001)))

for i in [0.01, 0.1, 1, 2]:
    i_iter_array, i_result_array = rmsprop(i, beta)
    plt.plot(i_iter_array, i_result_array, label="alpha:%.2f" %(i))
plt.legend()
plt.show()

alpha值：0.10, 收敛次数：101
alpha值：0.20, 收敛次数：70
alpha值：0.30, 收敛次数：51
alpha值：0.40, 收敛次数：40
alpha值：0.50, 收敛次数：33
alpha值：0.60, 收敛次数：27
alpha值：0.70, 收敛次数：23
alpha值：0.80, 收敛次数：20
alpha值：0.90, 收敛次数：18
alpha值：1.00, 收敛次数：16
alpha值：1.10, 收敛次数：14
alpha值：1.20, 收敛次数：13
alpha值：1.30, 收敛次数：12
alpha值：1.40, 收敛次数：11
alpha值：1.50, 收敛次数：10
alpha值：1.60, 收敛次数：9
alpha值：1.70, 收敛次数：8
alpha值：1.80, 收敛次数：7
alpha值：1.90, 收敛次数：7

image.png

adam

adam算法将momentum和rmsprop算法结合起来，
vdx = beta1 * vdx + (1-beta1) * dx,
vdxc = vdx / (1 - beta1 ** t),
sdx = beta2 * sdx + (1 - beta2) * dx ** 2,
sdxc = sdx / (1 - beta2 ** t),
dx := dx - alpha * vdxc / sqrt(sdxc)

plt.contour(x, y, z)
plt.scatter(0,0)
plt.xlabel('x')
plt.ylabel('y')

#adam
alpha = 0.2005
epsilon = 0.00000001
beta1 = 0.9
beta2 = 0.999
w = np.array([2, 0, 0, 10]).reshape(2, 2)
t = np.array([9, 8]).reshape(2, 1)
plt.scatter(t[0], t[1])
vdt = 0
sdt = 0
for i in range(1,100):
    dt = np.dot(w, t)
    vdt = beta1 * vdt + (1-beta1) * dt
    vdtc = vdt / (1 - beta1 ** i)
    sdt = beta2 * sdt + (1-beta2) * dt ** 2
    sdtc = sdt / (1 - beta2 ** i)
    t_step = vdtc / (np.sqrt(sdtc) + epsilon)
    t = t - alpha * t_step
    plt.scatter(t[0], t[1])
print("最终值")
print(t[0], t[1])
plt.show()

最终值
[-0.09618689] [-0.04753836]

image.png

adma算法的效率

def adam(alpha, beta1, beta2):
    w = np.array([2, 0, 0, 10]).reshape(2, 2)
    t = np.array([9, 8]).reshape(2, 1)
    vdt = 0
    sdt = 0
    i = 1
    iter_array = []
    result_array = []
    iter_array.append(i)
    result = t[0] ** 2  + 5 * t[1] ** 2
    result_array.append(result)
    while i < 100:
        dt = np.dot(w, t)
        vdt = beta1 * vdt + (1-beta1) * dt
        vdtc = vdt / (1 - beta1 ** i)
        sdt = beta * sdt + (1-beta) * dt ** 2
        sdtc = sdt / (1 - beta2 ** i)
        t_step = dt / (np.sqrt(sdt)  + epsilon)
        t = t - alpha * t_step
        iter_array.append(i)
        result = t[0] ** 2  + 5 * t[1] ** 2
        result_array.append(result)
        i += 1
    return iter_array, result_array
beta1 = 0.9
beta2 = 0.999
for i in range(1, 20):
    i_new = i / 10
    i_iter_array, i_result_array = adam(i_new, beta1, beta2)
    print('alpha值：%.2f, 收敛次数：%d' %(i_new,get_convergence_iter(i_result_array, 0.0001)))

for i in [0.01, 0.1, 1, 2]:
    i_iter_array, i_result_array = adam(i, beta1, beta2)
    plt.plot(i_iter_array, i_result_array, label="alpha:%.2f" %(i))
plt.legend()
plt.show()

image.png

局部最小与鞍点

在高维的情况下，算法更可能碰到鞍点，而非局部最小点（由于局部最小点需要所有维度在当前点都为凸函数，在高维情况下出现此情况都概率非常小）
鞍点对算法的影响是在平缓区域迭代速度减慢，可用adam等算法增加优化速度

from mpl_toolkits.mplot3d import Axes3D

#鞍点
x = y = np.linspace(-10, 10, 1000)
x,y = np.meshgrid(x,y)
z =  x ** 2  - y ** 2

fig = plt.figure()
ax = fig.gca(projection='3d')
ax.plot_surface(x,y,z,cmap=plt.cm.coolwarm)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
plt.show()

plt.contour(x,y,z)
plt.xlabel('x')
plt.ylabel('y')
plt.show()

image.png

gd在鞍点的表现

#gradient descent
alpha = 0.1
w = np.array([2, 0, 0, -2]).reshape(2, 2)
t_0 = t = np.array([-9, -0.2]).reshape(2, 1)
z_0 = t_0[0][0]**2 - t[1][0] ** 2
t_array = []
z_array = []
for i in range(1, 20):
    dt = np.dot(w, t)
    t_step = dt
    t = t - alpha * t_step
    t_array.append(t)
    z_value = t[0][0] ** 2 - t[1][0] ** 2
    z_array.append(z_value)
print("最终值")
print(t[0], t[1])

fig = plt.figure()
ax = fig.gca(projection='3d')
ax.plot_surface(x,y,z,cmap=plt.cm.coolwarm)
ax.scatter(t_0[0][0], t_0[1][0], z_0)
for i in range(len(t_array)):
    ax.scatter(t_array[i][0], t_array[i][1], z_array[i])
plt.show()

plt.contour(x, y, z)
plt.xlabel("x")
plt.ylabel("y")
plt.scatter(t_0[0], t_0[1])
for i in t_array:
    plt.scatter(i[0], i[1])
plt.show()

最终值
[-0.12970367] [-6.38959999]

image.png

adam在鞍点的表现

gd算法中不能设置过大的alpha值，否则算法不能收敛，使用adam算法时，可以设置较大的alpha值，加快迭代速度；同时adam算法平衡了x和y方向的迭代步长，使算法无须在x方向耗费过长的时间

#adam

alpha = 2
epsilon = 0.00000001
beta1 = 0.9
beta2 = 0.999

w = np.array([2, 0, 0, -2]).reshape(2, 2)
t_0 = t = np.array([-9, -0.2]).reshape(2, 1)
vdt = 0
sdt = 0
t_array = []
z_array = []
for i in range(1,10):
    dt = np.dot(w, t)
    vdt = beta1 * vdt + (1-beta1) * dt
    vdtc = vdt / (1 - beta1 ** i)
    sdt = beta2 * sdt + (1-beta2) * dt ** 2
    sdtc = sdt / (1 - beta2 ** i)
    t_step = vdtc / (np.sqrt(sdtc) + epsilon)
    t = t - alpha * t_step
    t_array.append(t)
    z_value = t[0][0] ** 2 - t[1][0] ** 2
    z_array.append(z_value)
print("最终值")
print(t[0], t[1])

fig = plt.figure()
ax = fig.gca(projection='3d')
ax.plot_surface(x,y,z,cmap=plt.cm.coolwarm)
ax.scatter(t_0[0][0], t_0[1][0], z_0)
for i in range(len(t_array)):
    ax.scatter(t_array[i][0], t_array[i][1], z_array[i])
plt.show()

plt.contour(x, y, z)
plt.xlabel("x")
plt.ylabel("y")
plt.scatter(t_0[0], t_0[1])
for i in t_array:
    plt.scatter(i[0], i[1])
plt.show()

最终值
[3.81504286] [-16.860752]

image.png

最后编辑于：2019.12.23 16:06:08

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,723评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,080评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,604评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,440评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,431评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,499评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,893评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,541评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,751评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,547评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,619评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,320评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,890评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,896评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,137评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,796评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,335评论 2赞 342

gradient descent

导读

alpha值的设置

gd的优化

momentum

momentum算法的效率

RMSProp

RMSProp算法的效率

adam

adma算法的效率

局部最小与鞍点

gd在鞍点的表现

adam在鞍点的表现

推荐阅读更多精彩内容