优化与随机梯度下降

简介

在上一节中，我们介绍了图像分类任务中的两个关键部分：

评分函数。该函数可以将原始图像像素信息映射为分类评分值。（e.g. 线性函数）
损失函数。该函数可以根据分类评分值和训练集图像数据实际分类标签的关系，衡量某个参数及的质量的好坏。损失函数也有很多种版本和不同的实现方式（例如：Softmax 或 SVM）。

在上一节中，我们讲到的线性函数对应的形式是 $f(x_i,W) = W x_i$ ，而 SVM 实现的公式是：

L = \frac{1}{N} \sum_i \sum_{j\neq y_i}[max(0, f(x_i;W)_j-f(x_i;W)_{y_i} + 1) + \alpha R(W)]

对于图像数据 $x_i$ ，如果基于参数集 $W$ 做出的分类预测和真实情况比较一致，那么计算出来的损失函数值 $L$ 就会很低。而我们这一节将要介绍的是第三个也是最后一个关键部分：最优化（Optimization）。最优化是能寻找能使得损失函数中最小化的参数 $W$ 的过程。

**铺垫：**为了理解了这三个部分是如何相互的，我们将回到第一个部分（基于参与的函数映射），然后将其拓展为一个远比线性函数复杂的函数：首先是神经网络，然后就是卷积神经网络。而损失函数和最优化过程这两个将会保持相对稳定。

损失函数可视化

在本课程中，我们所讨论的损失函数通常都定义在高维空间中（比如，在 CIFAR-10 中一个线性分类器的权值矩阵大小是 $[10\times 3073]$ ，也就是说一共有30730个参数），这样将其可视化就很困难。然而也不是完全没有办法，我们可以通过沿射线（1维）或沿平面（2维）对高维空间进行切片，就能得到一些直观的感知。例如，我们可以随机生成一个权值矩阵 $W$ (在高维空间中对应一个点)，然后沿一条射线行进，并沿途记录损失函数值。也就是说，我们生成了一个随机方向 $W_1$ 并沿着这个方向计算损失值，计算方法是根据不同的 $a$ 值来计算 $L(W + a W_1)$ 。这个过程可以生成一个图表，其 x 轴是 $a$ 值，y 轴是损失函数值。同样的方法还可以用在二维空间上，通过改变 $L(W + a W_1 + b W_2)$ ，从而给出一个二维图像。在图像中， $a$ 和 $b$ 可以分别用 x 轴和 y 轴表示，而损失函数的值可以用颜色变化表示：

一个无正则化的多类 SVM 损失函数的图示。前两张图都代表只有一个样本数据，最后一个是 CIFAR-10 中的 100 个数据。左： $a$ 值的变化在某个维度方向上对应的损失值的变化。中和右：两个维度方向上的损失值切片图，其中蓝色部分代表损失值在该处较低，红色部分代表损失值在该处较高。注意损失函数是分段线性的。多个样本的损失值就是总体的平均值，所以右边的碗装结构就是许多分段线性结构的平均值（比如中间那个）

我们可以通过数学公式来解释损失函数的分段线性结构。对于一个单独的数据，损失函数的计算公式如下：

L_i = \sum_{j\neq y_i} \left[ \max(0, w_j^Tx_i - w_{y_i}^Tx_i + 1) \right]

通过公式我们可以看到，每个样本的数据损失值都是以 $W$ 作为参数的线性函数的总和（零阈值来源于 $max(0,-)$ 函数）。 $W$ 的每一行（即 $w_j$ ），有时候前面是一个正号（比如对应错误分类的时候），有时候前面是一个负号（比如对应正确分类的时候）。为了进一步地解释，我们可以假设有一个简单的数据集，其中包含有 3 个只有 1 个维度的点，数据集中的数据点有 3 个类别。那么，完整的无正则化的 SVM 损失值计算如下：

\begin{align} L_0 = {}&{} \max(0, w_1^Tx_0 - w_0^Tx_0 + 1) + \max(0, w_2^Tx_0 - w_0^Tx_0 + 1) \\\\ L_1 = {}&{} \max(0, w_0^Tx_1 - w_1^Tx_1 + 1) + \max(0, w_2^Tx_1 - w_1^Tx_1 + 1) \\\\ L_2 = {}&{} \max(0, w_0^Tx_2 - w_2^Tx_2 + 1) + \max(0, w_1^Tx_2 - w_2^Tx_2 + 1) \\\\ L = {}&{} (L_0 + L_1 + L_2)/3 \end{align}

这些例子都是一维的，所以权重 $x_i$ 和权重 $\omega_j$ 都是数字。观察 $\omega_0$ ，可以看到上面的式子中的一些项是 $\omega_0$ 的线性函数，并且每一项都会和 0 做比较，取二者的最大值。我们可以作图如下：

一维数据损失值的展示。x 轴代表单个权重，y 轴代表损失值 $L$ 。数据损失是由多个部分组合而成，其中每个部分要么是权重的独立部分，要么是该权重的线性函数和 0 比较的结果。对于 CIFAR-10，完整的 SVM数据丢失就是这个形状的 30730 维版本。

需要多说一点的是，你可能通过这个图像的碗形形状推测出来它是一个凸函数。关于如何高效地最小化凸函数的论文有很多，你也可以学习斯坦福大学关于凸函数优化的过程。但是一旦我们将函数 $f$ 拓展到圣经网络中，我们的目标函数可能就不再是凸函数了，图像可能也不会想上面一样是个碗装，而是凹凸不平的复杂地形形状。

不可微的损失函数

这是一个技术笔记，你应该注意到：由于 $max()$ 函数的操作，损失函数中存在一些不可导点（kinks），这些点使得损失函数不可微，由于这些不可导点的存在，梯度是没有意义的。但是次梯度依然存在且常常被使用。在本课程中，我们将交换使用梯度和次梯度这两个术语。

优化

重申一下：损失函数可以量化任意一个具体权重集 $W$ 的质量。而最优化的目标就是找到能够最小化损失函数值的 $W$ 。我们现在就向着这个目标前进，实现一个能够最优化损失函数的方法。对于有一些经验的同学，这部分看起来可能有点奇怪，因为我们使用的例子（SVM损失函数）是一个凸函数问题。但是要记得，我们最终的目标不仅仅是对凸函数做优化，二是能够最优化一个神经网络，而对于神经网络是不能简单的使用凸函数的最优化技巧的。

策略1：随机搜索

既然确认一个参数集 $W$ 的好坏蛮简单的，那第一个想到的（差劲的）办法，就是可以随机尝试很多种不同的权重，然后看其中哪个权重最好。过程如下：

# assume X_train is the data where each column is an example (e.g. 3073 x 50,000)  
# assume Y_train are the labels (e.g. 1D array of 50,000)  
# assume the function L evaluates the loss function  
  
bestloss = float("inf") # Python assigns the highest possible float value  
for num in range(1000):  
  W = np.random.randn(10, 3073) * 0.0001 # generate random parameters  
  loss = L(X_train, Y_train, W) # get the loss over the entire training set  
  if loss < bestloss: # keep track of the best solution  
    bestloss = loss  
    bestW = W  
  print 'in attempt %d the loss was %f, best %f' % (num, loss, bestloss)  
  
# prints:  
# in attempt 0 the loss was 9.401632, best 9.401632  
# in attempt 1 the loss was 8.959668, best 8.959668  
# in attempt 2 the loss was 9.044034, best 8.959668  
# in attempt 3 the loss was 9.278948, best 8.959668  
# in attempt 4 the loss was 8.857370, best 8.857370  
# in attempt 5 the loss was 8.943151, best 8.857370  
# in attempt 6 the loss was 8.605604, best 8.605604  
# ... (trunctated: continues for 1000 lines)

在上面的代码中，我们尝试了若干随机生成的权重矩阵 $W$ ，其中某些取证对应的损失值较小，而另一些对应的损失值大些。我们可以把这次随即搜索中找到的最好权重 $W$ 取出，然后在测试集上进行测试：

# Assume X_test is [3073 x 10000], Y_test [10000 x 1]  
scores = Wbest.dot(Xte_cols) # 10 x 10000, the class scores for all test examples  
# find the index with max score in each column (the predicted class)  
Yte_predict = np.argmax(scores, axis = 0)  
# and calculate accuracy (fraction of predictions that are correct)  
np.mean(Yte_predict == Yte)  
# returns 0.1555

验证集上表现最好的权值矩阵 $W$ 跑测试集的准确率是 15.5%，而完全随机猜测的准确率是 10%，这样看来，这个准确率对于这样一个完全不经过大佬的策略来说，还算是不错的23333.

核心思路：迭代优化

当然，我们肯定能做得更好一点。其核心的想法是进行问题的转换：虽然找到最优的权重 $W$ 非常困难，甚至是不可能的（尤其是在 $W$ 中保存整个神经网络的权重的时候），但是如果问题转化为对于一个权值矩阵 $W$ 取优，使其损失值稍微减少一点，那么问题的难度就稍稍降低了一点。

我们的策略是从随机权重开始，然后向更好的方向迭代，从而获取更低的损失值。

关于蒙眼徒步者的比喻

一个可能会有助于理解的比喻是把自己想象成一个蒙着眼睛的徒步者正走在山地上，目标是要慢慢地走到山底。在 CIFAR-10 的例子中，这是一个 30730 维的山（因为 $W = 3073 \times 10$ ）。我们在山上踩的每一个点对应的高度都对应着一个损失值，该损失值可以看作是该点对应的海拔高度。

策略2：随机局部搜索

对于在上一个策略末尾提到的关于蒙眼徒步者的比喻，第一个策略可以看作是每走一步都尝试几个随机方向，如果该方向是向山下的，那么就想着该方向走几步。在本策略中，我们就从一个随机的参数矩阵 $W$ 开始，然后生成一个随机的扰动 $\delta W$ ，只有当 $W + \delta W$ 的损失值变低，我们才会进行更新。这个过程的具体代码如下：

W = np.random.randn(10, 3073) * 0.001 # generate random starting W  
bestloss = float("inf")  
for i in range(1000):  
  step_size = 0.0001  
  Wtry = W + np.random.randn(10, 3073) * step_size  
  loss = L(Xtr_cols, Ytr, Wtry)  
  if loss < bestloss:  
    W = Wtry  
    bestloss = loss  
  print 'iter %d loss is %f' % (i, bestloss)

和之前评估损失函数时使用同样的数据（1000），这个方法可以得到 21.4% 的分类准确率。这个比策略1稍微好一点，但是依然很浪费计算资源的问题。

策略3：跟随梯度

在前两个策略中，我们尝试在权重空间中找到一个方向，沿着这个方向可以显著地降低损失函数的值。其实我们并不需要随机地寻找这么一个方向，而是可以直接计算出最佳的方向并沿着这个方向更新我们的参数，这个方向在数学上来讲是保证函数值最陡下降的方向（至少在下降步长趋近为0时）。这个方向将和损失函数对应的**梯度（gradient）**有关。在我们上面的蒙眼徒步者的比喻中，这个方法就好比是感受我们脚下山体向各个方向的倾斜程度，然后选择最陡峭的下山方向下山。

在一维函数中，斜率是指函数在某一点的瞬时变化率。梯度是函数斜率的一般化表达，它不是一个值，而是一个向量。在输入空间中，梯度是函数在各个维度的斜率组成的向量（同城称之为导数derivative）。对一维函数的求导公式如下：

\frac{df(x)}{dx} = \lim_{h\ \to 0} \frac{f(x + h) - f(x)}{h}

当函数的有多个维度的输入的时候（即有多个自变量），我们称导数为偏导数。而梯度就是在每个维度上偏导数所形成的向量。

梯度计算

梯度的计算有两种办法，一种是缓慢，近似但是简单的方法（数值梯度法），另一种是基于微积分的快速，精确但是更容易出错的方法（分析梯度法）。现在对于两种方法逐一做以介绍。

数值有限差分

上一节中的公式已经给出了数值计算梯度的方法。下面的代码是一个输入函数 $f$ 和向量 $x$ ，计算 $f$ 的梯度的通用函数。它可以返回函数 $f$ 在点 $x$ 处的梯度。

def eval_numerical_gradient(f, x):  
  """  
  a naive implementation of numerical gradient of f at x  
  - f should be a function that takes a single argument  
  - x is the point (numpy array) to evaluate the gradient at  
  """  
  fx = f(x) # evaluate function value at original point  
  grad = np.zeros(x.shape)  
  h = 0.00001  
  # iterate over all indexes in x  
  it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])  
  while not it.finished:  
    # evaluate function at x+h  
    ix = it.multi_index  
    old_value = x[ix]  
    x[ix] = old_value + h # increment by h  
    fxh = f(x) # evalute f(x + h)  
    x[ix] = old_value # restore to previous value (very important!)  
    # compute the partial derivative  
    grad[ix] = (fxh - fx) / h # the slope  
    it.iternext() # step to next dimension  
  return grad

按照上面给出的梯度公式，这个代码对于所有维度进行迭代，在每一个维度上产生一个很小的变化 $h$ ，并通过观察函数值的变化来计算函数在该维度上的偏导数。最后，所有的梯度都将存储在变量 grad 中。

实践考量

注意在数学公式中，梯度定义取在 $h \to 0$ 的极限，然而在实践中，我们通常使用一个非常小的值（比如示例代码中的 $10^{-5}$ ）就足够了。在理想情况下，你希望使用不会导致数值问题的最小步长。此外，在实践中，使用中心差值公式（centered difference formula）: $[f(x+h) - f(x-h)] / 2 h$ 效果通常会更好。细节可以参阅wiki。

我们可以使用上面这个公式来计算任何函数在任何点处的梯度。下面计算权重空间中的某些随机点上 CIFAR-10 对应的损失函数的梯度。

# to use the generic code above we want a function that takes a single argument  
# (the weights in our case) so we close over X_train and Y_train  
def CIFAR10_loss_fun(W):  
  return L(X_train, Y_train, W)  
  
W = np.random.rand(10, 3073) * 0.001 # random weight vector  
df = eval_numerical_gradient(CIFAR10_loss_fun, W) # get the gradient

梯度可以告诉我们损失函数在每个维度上对应的斜率，并以此来进行参数更新：

loss_original = CIFAR10_loss_fun(W) # the original loss  
print 'original loss: %f' % (loss_original, )  
  
# lets see the effect of multiple step sizes  
for step_size_log in [-10, -9, -8, -7, -6, -5,-4,-3,-2,-1]:  
  step_size = 10 ** step_size_log  
  W_new = W - step_size * df # new position in the weight space  
  loss_new = CIFAR10_loss_fun(W_new)  
  print 'for step size %f new loss: %f' % (step_size, loss_new)  
  
# prints:  
# original loss: 2.200718  
# for step size 1.000000e-10 new loss: 2.200652  
# for step size 1.000000e-09 new loss: 2.200057  
# for step size 1.000000e-08 new loss: 2.194116  
# for step size 1.000000e-07 new loss: 2.135493  
# for step size 1.000000e-06 new loss: 1.647802  
# for step size 1.000000e-05 new loss: 2.844355  
# for step size 1.000000e-04 new loss: 25.558142  
# for step size 1.000000e-03 new loss: 254.086573  
# for step size 1.000000e-02 new loss: 2539.370888  
# for step size 1.000000e-01 new loss: 25392.214036

向负梯度方向更新

在上面的代码中，为了计算 W_new，请注意我们是向着梯度 df 的负方向进行更新的，这是因为我们希望损失函数的值降低，而不是升高。

步长的影响

梯度给我们指明了函数的最大变化率方向，但是没有指明在这个方向上应该走多远。在后续的部分中我们可以看到，选择合适的步长（即学习率）将会是神经网络训练中最重要（也是最令人头疼）的超参数设定之一。还是在我们上面的蒙眼下山的比喻中，我们可以感觉到我们所在的位置在不同方向上的倾斜程度，但是我们不知道要迈多大的步子。如果我们选择谨慎地小步走，结果可能比较稳定但是收敛较慢（对应学习率较小的情况）。相反，如果我们想要尽快下山而选择大步走，结果可能会适得其反。在上面的代码示例中，你可以看见反例——如果在某些点选择的步长过大，反而可能会越过最低点，造成更高的损失。

这是一个将步长效果可视化的图例。我们从某个点 $W$ 开始计算梯度（白色箭头所指的即为梯度下降的方向），从图中我们可以看见，梯度可以告诉我们损失函数下降最快的方向。小步长下降稳定但是进度会比较慢，大步长进展很快但是风险更大。采用大步长可能会错过最优点导致损失函数无法收敛到最优。步长（后面称之为学习率）将会成为我们必须仔细调整的最重要的超参数之一。

效率问题

你可能已经注意到了，数值梯度计算的复杂性和参数数量呈线性关系。在我们的示例中一共有 30730 个参数，因此，我们必须要对损失函数进行 30731 次评估以评估梯度并仅执行单个参数更新。现代神经网络会很轻松地达到上千万个参数，显然，这种策略并不适合，我们需要更好的计算策略。

微分计算梯度

使用有限差分方法近似计算梯度是比较简单的，但是缺点在于它终究只是一种近似方法（因为我们必须选择一个小的 h 值，但在真正的梯度定义中是 $\lim_{h\to 0}$ 的极限），而且计算代价过于昂贵。第二个梯度计算方法是利用微分进行分析，它允许我们直接推到得到梯度的直接公式（无近似值），计算速度也相当快，唯一的缺点就是实现的时候容易出错。在实际操作过程中我们往往将两种方法得到的结果进行比较以此来验证实现的正确性，这个步骤叫做梯度检查。

SVM 损失函数在某个数据点上的计算的示例：

L_i = \sum_{j\neq y_i} \left[ \max(0, w_j^Tx_i - w_{y_i}^Tx_i + \Delta) \right]

我们可以对函数进行求导微分，比如我们对 $\omega_{y_i}$ 进行求偏导，我们可以得到：

\nabla_{w_{y_i}} L_i = - \left( \sum_{j\neq y_i} \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) \right) x_i

其中， $\mathbb{1}$ 是一个示性函数，如果括号内的条件为真则取1，否则为0。虽然上面这个公式看起来很吓人，但是代码实现却是比较简单的：我们只需要计算没有满足边界值 $\Delta$ （进而对损失函数产生了贡献）的分类数量，然后乘以 $x_i$ 就是对应的梯度了。注意，这个梯度只对应正确分类的 $W$ 的行向量的梯度，对于哪些不正确分类（即 $j \neq y_i$ ）的行，对应的梯度就是：

\nabla_{\omega_j}L_i = \mathbb{1}(\omega_j^Tx_i - \omega_{y_i}^Tx_i + \Delta > 0) x_i

一旦推导出积分的表达式，我们就可以顺畅地使用代码实现公式并进行梯度更新了。

梯度下降

在上面的部分中，我们已经完成了损失函数的梯度的计算，而重复评估计算梯度然后进行参数更新的过程我们称之为梯度下降。它的普通版本是这样的：

# Vanilla Gradient Descent

while True:  
  weights_grad = evaluate_gradient(loss_fun, data, weights)  
  weights += - step_size * weights_grad # perform parameter update

这个简单的循环在所有神经网络库中都存在。虽然还有其他的实现最优化的方法（比如说 LBFGS），但是到目前为止，梯度下降是最常见和最成熟的损失函数最优化方法。在整个课程的过程中，我们将会在这个循环的基础上添加一些新的花里胡哨的东西（比如具体的更新公式细节），但是核心思想不会发生变化，那就是我们一直遵循梯度来进行参数迭代直到最优结果出现并收敛。

小批量梯度下降（Mini-batch gradient descent）

在大规模应用中（比如 ILSVRC 挑战赛），训练数据量可能会达到百万量级。因此，如果为了获得仅仅一个参数的更新而计算整个训练集的完整损失函数就显得过于浪费了。一种常用的解决办法是计算训练集中的**小批量（batches）**数据。例如，在当前最先进的卷积神经网络中，一个典型的小批量包含 256 个训练样本，而整个训练集的数据量多达 120 万。这份小批量数据就用来实现一个参数更新：

# Vanilla Minibatch Gradient Descent

while True:
  data_batch = sample_training_data(data, 256) # sample 256 examples  
  weights_grad = evaluate_gradient(loss_fun, data_batch, weights)  
  weights += - step_size * weights_grad # perform parameter update

这个方法的效果之所以不错，是因为训练集中的各个数据都是相关的。要理解这一点，我们可以想象一种极端一点的情况：在 ILSVRC 中的 120 万个图像是 1000 张不同图像的复制，那么显然这1200张复制图像的梯度就应该是一样的。对比120万张图片的数据损失的均值与只计算1000张的子集的数据损失均值时，结果应该是一样的。实际情况中，数据集肯定不会包含重复图像，那么小批量数据的梯度就是对整个数据集梯度的一个近似。因此，在实践中通过计算小批量数据的梯度可以实现更快速地收敛，并以此来进行更频繁的参数更新。

小批量数据策略有个极端情况，那就是每个批量中只有1个数据样本，这种策略被称为随机梯度下降（Stochastic Gradient Descent 简称 SGD），有时候也被称为在线梯度下降。这种策略在实际应用中相对少见，因为向量化操作的代码一次计算 100 个数据，这要比 100 次计算 1 个数据要高效很多。即使 SGD 在技术上是指每次使用 1 个数据来计算梯度，你还是会听到人们使用 SGD 来指代小批量数据梯度下降（或者用 MGD 来指代小批量数据梯度下降，而 BGD 来指代则相对少见）。小批量数据的大小是一个超参数，但是一般并不需要通过交叉验证来调参。它一般由存储器的限制来决定的，或者干脆设置为同样大小，比如32，64，128等。之所以使用2的指数，是因为在实际中许多向量化操作实现的时候，如果输入数据量是2的倍数，那么运算更快。

小结

信息流的总结图片，数据集中的 $(x,y)$ 是给定的，权重从一个随机数字开始且可以改变。在前向传播过程中，评分函数计算出对应每一个类别的分类评分并存储在向量 $f$ 中。损失函数包含两个部分：数据损失和正则化损失。其中数据损失计算的是分类评分 $f$ 和实际标签 $y$ 之间的差异，而正则化损失则是一个只关于权重的函数。在梯度下降的过程中，我们计算权值矩阵的梯度（如果愿意的话也可以计算数据集上面的梯度），然后依据梯度来实现参数的更新。

在本节课程中，我们：

将损失函数比作了一个高维度的复杂地形，并尝试到达它的最底部。最优化的工作过程可以看做一个蒙着眼睛的徒步者希望摸索着走到山的底部。在例子中，我们可以发现 SVM 的损失函数是分段线性的，并且是碗状的。
提出了迭代优化的思想，从一个随机的权重开始，然后一步步地让损失值变小，直到最小。
函数的梯度给出了该函数最陡峭的上升方向。介绍了利用有限的差值来近似计算梯度的方法，该方法实现简单但是效率较低（有限差值就是 $h$ ，用来计算数值梯度）。
参数更新需要有技巧地设置步长。也叫学习率。如果步长太小，进度稳定但是缓慢，如果步长太大，进度快但是可能有风险。
讨论权衡了数值有限差分和微分计算这两种计算梯度的方法。数值有限差分法计算简单，但结果只是近似且耗费计算资源。微分计算梯度法计算准确迅速但是实现容易出错，而且需要对梯度公式进行推导的数学基本功。因此，在实际中使用分析梯度法，然后使用梯度检查来检查其实现正确与否，其本质就是将分析梯度法的结果与数值梯度法的计算结果对比。
介绍了梯度下降算法，它在循环中迭代地计算梯度并更新参数。

预告

本科的核心内容是：能够理解并计算损失函数关于权重的梯度。这也是设计、训练和理解损失函数的核心能力。在下节课中，我们将介绍如何使用链式法则高效的计算梯度，也就是我们通常所说的**反向传播（back propagation）**机制。这个机制能够对包括卷积神经网络在内的几乎所有类型的神经网络的损失函数进行高效的最优化。

CS231n笔记-第三部分

目录