【AI】浅谈梯度下降算法（拓展篇）
前言
前导博文：
通过前导博文的学习，想必大家对于梯度下降也有所掌握了，其中在 【AI】浅谈梯度下降算法（实战篇） 博文中有粗略的提到过梯度下降的三大家族，本博文将结合代码实现来细细讲解；
学习率
学习率，想必大家在前导博文中也见过该词，为什么要提到学习率呢，且听我慢慢分析；
首先要知道，梯度下降的中心思想就是迭代地调整参数从而使成本函数最小化。
具体来说，首先使用一个随机的 θ值（这被称为随机初始化），然后逐步改进，每次踏出一步，每一步都尝试降低一点成本函数（如在线性回归中采用 MSE），直到算法收敛出一个最小值，如下图所示：
然而，这其中有一个十分重要的超参数，学习率 Learning Rate，它影响了每一步的步长；
如果学习率太低，算法需要经过大量迭代才能收敛，这将耗费很长时间：
反之，如果学习率太高，这会导致算法发散，值越来越大，最后无法找到好的解决方案：
而且，并不是所有的成本函数看起来都像一个漂亮的碗。有的可能看着像洞、像山脉、像高原或者是各种不规则的地形，导致很难收敛到最小值。
如果随机初始化，算法从左侧起步，那么会收敛到一个局部最小值，而不是全局最小值。如果从右侧起步，那么需要经过很长时间才能越过整片高原，如果停下来太早，将永远达不到全局最小值。
因此，对于学习率的设置显得尤为重要，下面来看看不同的学习率所带来的影响：
def plot_gradient_descent(theta, eta, theta_path=None):
m = len(X_b)
plt.plot(X, y, "b.")
for i in range(max_iters):
if i < 10:
y_predict = X_new_b.dot(theta)
style = "g-" if i > 0 else "r--"
plt.plot(X_new, y_predict, style)
gradients = 2/m * X_b.T.dot(X_b.dot(theta) - y)
theta = theta - eta * gradients
if theta_path is not None:
theta_path.append(theta)
plt.xlabel("$X$", fontsize=18)
plt.title(r"$\eta = {}$".format(eta), fontsize=16)绘制了梯度下降的前十步，虚线表示起点，η\etaη 表示为学习率：
得出结论：
- 左图：在前十步无法找到解决方案，但是只要长时间的迭代就一定可以找到解决方案；
- 中图：效果看起来不错，比较符合预期，几次迭代就收敛出了最终解；
- 右图：算法发散，直接跳过了数据区域，并且每一步都离实际解决方案越来越远；
要找到合适的学习率，可以使用网络搜索。但是可能需要限制迭代次数，这样网络搜索就可以淘汰掉那些收敛耗时太长的模型。
然而怎么限制迭代次数呢？如果设置太低，算法可能在离最优解还很远时就停止了；但是如果设置得太高，模型到达最优解后，继续迭代参数不再变化，又会浪费时间。
一个简单的方法是在开始设置一个非常大的迭代次数，但是当梯度向量的值变得很微小时中断算法，也就是当他的范数变得低于 ε\varepsilonε（称为容差）时，因为这是梯度下降已经（几乎）到达了最小值。
批量梯度下降 BGD
梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新；
- 优点：全局最优解，易于并行实现；
- 缺点：计算代价大，数据量大时，训练过程慢；
要实现梯度下降，需要计算每个模型关于参数 θj的成本函数的梯度。换言之，需要计算的是，如果改变 θj，成本函数会改变多少，即偏导数。以线性回归的成本函数 MSE为例，其偏导数为：
如果不想单独计算这些梯度，可以使用下面的公式对其进行一次性计算。梯度向量`$∇
θ
MSE(θ)$`，包含所有成本函数（每个模型参数一个）的偏导数。
代码实现：
1、随机初始化：
X = 2 * np.random.rand(100, 1)
y = 21 + 5 * X + np.random.randn(100, 1)
X_b = np.c_[np.ones((100, 1)), X]2、设置各参数：
m = 100
eta = 0.1
n_epochs = 1000
theta = np.random.randn(2,1)3、BGD 算法实现：
for epoch in range(n_epochs):
gradients = 2/m * X_b.T.dot(X_b.dot(theta) - y)
theta = theta - eta * gradients
print('theta:\n{}\n'.format(theta))4、绘制图像：
X_new = np.array([[0], [2]])
X_new_b = np.c_[np.ones((2, 1)), X_new]
y_predict = X_new_b.dot(theta)
plt.title(f"$\eta = {0.1}$")
plt.plot(X_new, y_predict, "r-")
plt.plot(X, y, "b.")
plt.show()
批量梯度下降法由于使用了全部样本进行训练，所以当损失函数是凸函数时，理论上可以找到全局最优解，但当训练样本很大时，其训练速度会非常慢，不适用于在线学习的一些项目。为了解决这个问题，随机梯度下降算法被提出。
随机梯度下降 SGD
和批量梯度下降法原理类似，区别在于求梯度时，没有用所有的 m个样本的数据，而是仅仅选取一个样本 j来求梯度；
- 优点：训练速度快；
- 缺点：准确度下降，并不是全局最优，不易于并行实现；
由于算法的随机性质，它比批量梯度下降要不规则得多。成本函数将不再是缓缓降低直到抵达最小值，而是不断上上下下，但是从整体来看，还是在慢慢下降。随着时间的推移，最终会非常接近最小值，但是即使它到达了最小值，依然还会持续反弹，永远不会停止。所以算法停下来的参数值肯定是足够好的，但不是最优的。
当成本函数非常不规则时，随机梯度下降其实可以帮助算法跳出局部最小值，所以 相比批量梯度下降，它对找到全局最小值更有优势 。
因为，随机性的好处在于可以逃离局部最优，但缺点是永远定位不出最小值。 要解决这个困境，有一个办法是逐步降低学习率。开始的步长比较大（这有助于快速进展和逃离局部最小值），然后越来越小，让算法尽量靠近全局最小值，这个过程叫做模拟退火：因为它类似于冶金时融化的金属慢慢冷却的退火过程。
确定每个迭代学习率的函数叫作学习计划。如果学习率降得太快，可能会陷入局部最小值，甚至是停留在走向最小值的半途中。如果学习率太慢，你可能需要太长时间太能跳到差不多最小值附近，如果提早结束训练，可能只得到一个次优的解决方案。
代码实现：
1、初始化过程同上；
2、SGD 算法实现：
为了避免训练速度过慢，随机梯度下降法在训练过程中每次仅针对一个样本进行训练，但进行多次更新。在每一轮新的更新之前，需要对数据样本进行重新洗牌（shuffle）。
for epoch in range(n_epochs):
# 每个轮次开始分批次迭代之前打乱数据索引顺序
arr = np.arange(len(X_b))
np.random.shuffle(arr)
X_b = X_b[arr]
y = y[arr]
for i in range(m):
xi = X_b[i:i+1]
yi = y[i:i+1]
gradients = xi.T.dot(xi.dot(theta)-yi)
theta = theta - eta * gradients
print('theta:\n{}\n'.format(theta))3、绘制图像：
# 在上述代码段内部加入
for i in range(m):
xi = X_b[i:i+1]
yi = y[i:i+1]
gradients = xi.T.dot(xi.dot(theta)-yi)
theta = theta - eta * gradients
if epoch == 0 and i % 5 == 0:
y_predict = X_new_b.dot(theta)
style = "m--" if i > 0 else "r--"
plt.plot(X_new, y_predict, style)
if epoch == 1 and i % 5 == 0:
y_predict = X_new_b.dot(theta)
style = "g--" if i > 0 else "r--"
plt.plot(X_new, y_predict, style)
X_new = np.array([[0], [2]])
X_new_b = np.c_[np.ones((2, 1)), X_new]
y_predict = X_new_b.dot(theta)
plt.title(f"$\eta = {0.1}$")
plt.plot(X_new, y_predict, "k-")
plt.plot(X, y, "b.")
plt.show() 
随机梯度下降法在更新过程中由于是针对单个样本，所以其迭代的方向有时候并不是整体最优的方向，同时其方差较大，导致损失函数值的变动并不是规律的递减，更多的情况可能是波动形状的下降。
为了解决批量梯度下降的速度太慢以及随机梯度下降方差变动过大的情况，一种折中的算法--小批量梯度下降算法被提出，其从全部样本中选取部分样本进行迭代训练。并且在每一轮新的迭代开始之前，对全部样本进行 Shuffle 处理。
小批量梯度下降 MBGD
小批量梯度下降法是批量梯度下降法和随机梯度下降法的折中，也就是对于 m个样本，我们采用 x个样本来迭代，1<x<m。一般可以取 x=10，当然根据样本的数据量，可以调整这个 x 的值；
相对于随机梯度下降算法，小批量梯度下降算法降低了收敛波动性， 即降低了参数更新的方差，使得更新更加稳定。相对于全量梯度下降，其提高了每次学习的速度。并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。一般而言每次更新随 机选择50,256个样本进行学习，但是也要根据具体问题而选择，实践中可以进行多次试验， 选择一个更新速度与更次次数都较适合的样本数。
代码实现：
1、初始化过程同上；
2、动态调整学习率：
t0, t1 = 5, 500
def learning_rate_schedule(t):
return t0 / (t + t1)3、MBGD 算法实现：
theta = np.random.randn(2,1)
for epoch in range(n_epochs):
arr = np.arange(len(X_b))
np.random.shuffle(arr)
X_b = X_b[arr]
y = y[arr]
for i in range(n_batches):
x_batch = X_b[i * batch: i * batch + batch]
y_batch = y[i * batch: i * batch + batch]
gradients = x_batch.T.dot(x_batch.dot(theta)-y_batch)
eta = learning_rate_schedule(epoch * m + i)
theta = theta - eta * gradients
print('theta:\n{}\n'.format(theta))4、绘制图像：
# 在上述代码段内部加入
for i in range(n_batches):
x_batch = X_b[i * batch: i * batch + batch]
y_batch = y[i * batch: i * batch + batch]
gradients = x_batch.T.dot(x_batch.dot(theta)-y_batch)
eta = learning_rate_schedule(epoch * m + i)
theta = theta - eta * gradients
if epoch == 0 and i < 5:
y_predict = X_new_b.dot(theta)
style = "m--" if i > 0 else "r--"
plt.plot(X_new, y_predict, style)
if epoch == 1 and i < 5:
y_predict = X_new_b.dot(theta)
style = "g--" if i > 0 else "r--"
plt.plot(X_new, y_predict, style)
X_new = np.array([[0], [2]])
X_new_b = np.c_[np.ones((2, 1)), X_new]
y_predict = X_new_b.dot(theta)
plt.title(f"$\eta = {0.1}$")
plt.plot(X_new, y_predict, "k-")
plt.plot(X, y, "b.")
plt.show() 
后记
以上三种梯度下降算法仅局限于对训练样本进行变更，且每次迭代更新权重时使用的梯度仅作用于当前状态。由于每一期的样本有好有坏，导致迭代过程是曲折波动的，影响了收敛速度。
下图显示了训练期间参数空间中三种梯度下降算法所采用的路径。它们最终都接近最小值，但是批量梯度下降的路径实际上是在最小值处停止，而随机梯度下降和小批量梯度下降都继续走动。但是，不要忘记批量梯度下降每步需要花费很多时间，如果你使用良好的学习率调度，随机梯度下降和小批量梯度下降也会达到最小值。
让我们比较到目前为止讨论的线性回归算法，m 是训练实例的数量，n是特征的数量。
算法 | mmm 很大 | 核外支持 | nnn 很大 | 超参数 | 要求缩放 |
|---|---|---|---|---|---|
标准方程 | 快 | 否 | 慢 | 0 | 否 |
SVD | 快 | 否 | 慢 | 0 | 否 |
BGD | 慢 | 否 | 快 | 2 | 是 |
SGD | 快 | 是 | 快 | ≥\geq≥2 | 是 |
MBGD | 快 | 是 | 快 | ≥\geq≥2 | 是 |
参考：