作者:kissg
本节尝试独立于机器学习算法, 单纯地来讲
, 以使梯度下降更具一般性.
- 梯度下降算法 [Gradient Descent, GD]
开始之前, 先放 2 个基本概念, 带着这 2 个认识, 在几乎不具备机器学习知识的前提下, 应该也能很好地读懂本节内容:
作为参数估计的函数, 因此, 机器学习的任务就转变为了最小化成本函数.
- 成本函数 [Cost Function]
梯度下降算法就是一个被广泛使用的优化算法, 它可以用于寻找最小化成本函数的参数值. 用中学数学的语言来描述梯度下降, 是这样的: 当函数 _ 取得最小值时, 求所对应的自变量 的过程_ 此处, 就是机器要学习的参数, 就是用于参数估计的成本函数, 是关于 的函数. 因此, 基本上具备中学数学知识的, 都能理解梯度下降算法.
梯度下降的基本步骤是:
以上就是梯度下降算法最基础也是最核心的概念, 很简单吧.
下面讲讲梯度下降算法的几个变种, 包括: 批量梯度下降 [Batch Gradient Descent, BGD], 随机梯度下降 [Stochastic Gradient Descent, SGD], 小批量梯度下降 [Mini-Batch Gradient Descent, MBGD]
BGD 是梯度下降算法最原始的形式, 其特点是每次更新参数 时, 都使用整个训练集的数据.
BGD 的具体实现是这样的:
因此, BGD 的伪代码形式可以简单地写成:
- repeat { (
- for every j = 0, 1, ..n)
- }
上式中的求和部分 就体现了每一次迭代, 都以整个训练集为对象进行梯度计算.
BGD 得到的是全局最优解, 因为它总是以整个训练集来计算梯度, 这是 BGD 的优点. 但也因此带来了巨大的计算量, 计算迭代速度很很慢.
SGD 每次以一个样本, 而不是整个数据集来计算梯度. 因此, SGD 从成本函数开始, 就不必再求和了, 针对单个样例的成本函数可以写成: (此处的 同样是为了后续计算方便设置的)
于是, SGD 的参数更新规则就可以写成:
SGD 的伪代码形式如下:
- repeat {
- for i = 1,
- ..,
- m { (
- for every j = 0, 1, ..n)
- }
- }
SGD 的关键点在于以随机顺序选取样本. 因为 SGD 存在局部最优困境, 若每次都以相同的顺序选取样本, 其有很大的可能会在相同的地方陷入局部困境, 或者收敛减缓. 因此, 欲使 SGD 发挥更好的效果, 应充分利用
带来的优势: 可以在每次迭代之前 (伪代码中最外围循环), 对训练集进行随机排列.
- 随机化 [Randomise]
因为每次只取一个样本来进行梯度下降, SGD 的训练速度很快, 但会引入噪声, 使准确度下降. 这意味着并不是每次迭代都向着全局最优而去, 即并不是每次迭代都能使成本函数值降低. 不过换个思路的话, 噪声在一定程度上以使算法避免了局部最优.
SGD 的另一个好处是, 可以使用
. 也就是说, 在模型训练好之后, 只要有新的数据到来, 模型都可以利用新的数据进行再学习, 更新参数, 以适应新的变化.
- 在线学习 [online learning]
MBGD 是为解决 BGD 与 SGD 各自缺点而发明的折中算法, 或者说它利用了 BGD 和 SGD 各自优点. 其基本思想是: 每次更新参数时, 使用 n 个样本, 既不是全部, 也不是 1. (SGD 可以看成是 n=1 的 MBGD 的一个特例)
此处就不再给出 MBGD 的成本函数或其求导公式或参数更新规则公式了, 基本同 BGD, 见上.
MBGD 的伪代码如下:
- say b = 10,
- m = 1000,
- repeat {
- for i = 1,
- 11,
- 21,
- ..,
- 991 { (
- for every j = 0, 1, ..n)
- }
- }
总结一下以上 3 个梯度下降算法的优缺点:
梯度下降算法 | 优点 | 缺点 |
---|---|---|
BGD | 全局最优解 | 计算量大, 迭代速度慢, 训练速度慢 |
SGD | 1. 训练速度快 2. 支持在线学习 |
准确度下降, 有噪声, 非全局最优解 |
MBGD | 1. 训练速度较快, 取决于小批量的数目 2. 支持在线学习 |
准确度不如 BGD, 仍然有噪声, 非全局最优解 |
下面将介绍一些梯度下降算法的使用技巧:
以下内容有点深奥, 笔者对一些概念也不甚熟悉, 仅仅是做个记录
我注意到 keras 实现的 SGD 提供了 3 个关键字参数:
,
- decay
,
- momentum
:
- nestrov
使用 BGD 达到极小值时, 整个成本函数的真实梯度会变得很小, 最终减小为 0, 因此 BGD 可以使用固定的学习率; 然而, SGD 中梯度估计引入的噪声源不会在极小点处消失, 因此有必要随着时间的推移逐渐降低学习率, 以保证 SGD 收敛.
实践中, 一般让学习率线性衰减, 直到第 次迭代:
其中, 表示第 k 次迭代, 表示第 次迭代, .
上式中, 需要设置的量包括: 初始学习率 , 最终学习率 以及 终止迭代次数 . 通常取几百的大小, 则设为 的 . 因此, 剩下的主要问题就是选择一个合适的 : 取值太大, 学习曲线会剧烈抖动, 成本会明显增加; 取值太小, 学习过程会变得很缓慢.
上面提到, 在梯度下降中引入动量的概念, 是为了加速学习, 特别是对于处理高曲率 (曲率: 曲线偏离直线的程度), 小但一致的梯度, 或者带噪声的梯度, 有明显的加速效果. 因为动量算法积累了之前梯度指数级衰减的移动平均 (移动平均: 分析时间序列数据的有效工具), 能够继续沿该方向移动, 从而使成本持续减小.
从形式上看, 动量算法引入了 充当速度的角色, 代表参数在参数空间移动的方向和速率. 被设为负梯度的指数衰减平均, 其更新规则如下:
从上式可以得出的一个结论是: 相对于 , 越大, 之前梯度对现在方向的影响就越大.
在引入动量的概念之前, 的更新步长只是梯度范数乘以学习率, 引入动量之后则取决于梯度序列的大小和排列. 当许多连续的梯度指向相同时, 步长最大
Nesterov 动量算法是标准动量算法的变种, 其更新规则如下:
Nesterov 动量算法与标准动量算法的区别在于梯度的计算, 其梯度计算是在施加了当前速度之后, 可以解释为向标准动量方法中添加了一个校正因子.
研究优化算法的收敛率时, 一般会衡量
: , 即当前成本超出最低可能成本的量. SGD 应用于凸问题 (研究定义于凸集中的凸函数最小化的问题) 时, k 步迭代的额外误差量级是 , 在强凸情况下是 . 除非假定额外条件, 否则不能进一步改进.
- 额外误差
指出, 泛化误差的下降速度不会快于 . Bottou and Bousquet 因此认为机器学习任务, 不值得探寻收敛快于 的优化算法, 因为:
- Cramer-Rao 界限
更快的收敛可能对应过拟合
以下是 BGD, SGD, MBGD 的 Python 代码实现, 暂时不包括进阶部分提到的高级内容.
- import numpy as np import pylab from sklearn.datasets.samples_generator import make_regression
- def bgd(alpha, x, y, numIterations) : """Copied from Internet"""m = x.shape[0]#number of samples theta = np.ones(2) J_list = []
- x_transpose = x.transpose() for iter in range(0, numIterations) : hypothesis = np.dot(x, theta) loss = y - hypothesis J = np.sum(loss * *2) / (2 * m)#cost J_list.append(J) print("iter %s | J: %.3f" % (iter, J))
- gradient = np.dot(x_transpose, loss) / m theta += alpha * gradient#update
- pylab.plot(range(numIterations), J_list, "k-") return theta
- def sgd(alpha, x, y, num_iter) : """Writtern by kissg"""m = x.shape[0]#number of samples theta = np.ones(2) J_list = []
- #随机化序列idx = np.random.permutation(y.shape[0]) x,
- y = x[idx],
- y[idx]
- for j in range(num_iter) :
- for i in idx: single_hypothesis = np.dot(x[i], theta) single_loss = y[i] - single_hypothesis gradient = np.dot(x[i].transpose(), single_loss) theta += alpha * gradient#update
- hypothesis = np.dot(x, theta) loss = y - hypothesis J = np.sum(loss * *2) / (2 * m)#cost J_list.append(J) print("iter %s | J: %.3f" % (j, J))
- pylab.plot(range(num_iter), J_list, "r-") return theta
- def mbgd(alpha, x, y, num_iter, minibatches) : """Writtern by kissg"""m = x.shape[0]#number of samples theta = np.ones(2) J_list = []
- for j in range(num_iter) :
- idx = np.random.permutation(y.shape[0]) x,
- y = x[idx],
- y[idx] mini = np.array_split(range(y.shape[0]), minibatches)
- for i in mini: mb_hypothesis = np.dot(x[i], theta) mb_loss = y[i] - mb_hypothesis gradient = np.dot(x[i].transpose(), mb_loss) / minibatches theta += alpha * gradient#update
- hypothesis = np.dot(x, theta) loss = y - hypothesis J = np.sum(loss * *2) / (2 * m)#cost J_list.append(J) print("iter %s | J: %.3f" % (j, J))
- pylab.plot(range(num_iter), J_list, "y-") return theta
- if __name__ == '__main__':
- x,
- y = make_regression(n_samples = 100, n_features = 1, n_informative = 1, random_state = 0, noise = 35) m,
- n = np.shape(x) x = np.c_[np.ones(m), x]#insert column,
- bias alpha = 0.01#learning rate
- pylab.plot(x[: , 1], y, 'o')
- print("\n#***BGD***#\n") theta_bgd = bgd(alpha, x, y, 800) for i in range(x.shape[1]) : y_bgd_predict = theta_bgd * x pylab.plot(x, y_bgd_predict, 'k--')
- print("\n#***SGD***#\n") theta_sgd = sgd(alpha, x, y, 10) for i in range(x.shape[1]) : y_sgd_predict = theta_sgd * x pylab.plot(x, y_sgd_predict, 'r--')
- print("\n#***MBGD***#\n") theta_mbgd = mbgd(alpha, x, y, 50, 10) for i in range(x.shape[1]) : y_mbgd_predict = theta_mbgd * x pylab.plot(x, y_mbgd_predict, 'y--')
- pylab.show() print("Done!")
执行以上代码, 得到 3 类梯度下降算法的函数图像如下图所示.
End.
来源: http://www.36dsj.com/archives/89076