Lecture 3 损失函数和优化

上一个lecture中讲解了线性分类里的评分函数 $f(x_i,W)$ ，以及对线性分类的理解。这次来讲解损失函数以及如何求 $W$ 。

本课重点：

线性分类II——损失函数
优化

1 线性分类II——损失函数

1.1 损失函数的概念

回到之前小猫分类的结果，这个例子中权重值 $W$ 非常差，因为猫分类的得分非常低（-96.8），而狗（437.9）和船（61.95）比较高。于是定义损失函数（Loss Function）（有时也叫代价函数 Cost Function 或目标函数 Objective） $L$ 来衡量我们对结果的不满意程度。当评分函数输出结果与真实结果之间差异越大，损失函数输出越大，反之越小。

图1 实际计算评分函数

对于有N个训练样本对应N个标签的训练集数据

(x_{i},y_{i})

损失函数定义为：

$L=\frac{1}{N} \sum_{i=1}^NL_i(f(x_i,W), y_i)$ ，即每个样本损失函数求和取平均。

目标就是找到一个合适的 $W$ 使 $L$ 最小。

注意：
真正的损失函数L还有一项正则损失R(W)，下面会有说明。

1.2 损失函数的分类

损失函数的具体形式多种多样，下面介绍几个常见的。

1.2.1 多类支持向量机损失 (Multiclass Support Vector Machine Loss)

（CS229介绍过二元SVM，即把样本分为两类。多类SVM是一个推广，可以把样本数据分为多个类别。）

数据损失（data loss）

SVM的损失函数想要SVM在正确分类上的得分始终比不正确分类上的得分高出一个边界值 $\Delta$ 。现在只关于一个数据定义 $L_i$ ，根据之前的描述，第 i 个数据 $(x_{i},y_{i})$ 中包含图像 $x_i$ 的像素和代表正确类别的标签 $y_i$ 。给评分函数输入像素数据，然后通过公式 $f(x_i, W)$ 来计算不同分类类别的分值。这里我们将所有分值存放到 $s$ 中，第 j 个类别的得分就是 $s$ 的第 j 个元素： $s_j = f(x_i, W)_j$ 。针对第 i 个数据的多类SVM的损失函数定义如下：

$L_i = \sum_{j\neq y_i} \max(0, s_j - s_{y_i} + \Delta)$

例子：

直观来看，就是如果评分函数给真实标签的分数比其他某个标签的分数高出 $\Delta$ ，则对该其他标签的损失为0；否则损失就是 $s_j - s_{y_i}+ \Delta$ 。要对所有不正确的分类循环一遍。下面通过具体的例子说明：

图2 Li的计算

简化计算起见，我们只使用三个训练样本，对应三个分类，所以

y_i =0，1，2

对于第1个数据“小猫”来说，评分

s=[3.2, 5.1, -1.7]

其中

s_{y_i}=3.2

如果把

\Delta

设为1，则针对小猫的损失函数:

$L_1 = max(0, 5.1 - 3.2 + 1) +max(0, -1.7 - 3.2 + 1) = max(0, 2.9) + max(0, -3.9) = 2.9 + 0 =2.9$

同理可得 $L_2$ =0， $L_3$ =12.9，所以对整个训练集的损失:L= (2.9 + 0 + 12.9)/3 =5.27。上面可以看到SVM的损失函数不仅想要正确分类类别 $y_i$ 的分数比不正确类别分数高，而且至少要高 $\Delta$ 。如果不满足这点，就开始计算损失值。

注意：

之所以会加入一个 $\Delta$ ，只是为了真实标签的分数比错误标签的分数高出一定的距离，如下图所示，如果其他分类分数进入了红色的区域，甚至更高，那么就开始计算损失；如果没有这些情况，损失值为0：

图3 Delta示意图
如果car的得分稍微改变一点，损失函数几乎不变，因为损失函数计算的是相对差距是否大于1，所以结果只会改变一点；
损失最小是0，最大无穷；
在训练最开始的时候，往往会给W一个比较小的初值，结果就是s中所有值都很小接近于0，此时的损失L应该等于分类类别数K-1，这里是2。可根据这个判断代码是否有问题；
如果求和的时候，不加 $j\neq y_i$ 这一条件，L会加1；
计算Li时使用平均不用求和，只会缩放L不会影响好坏；而如果使用平方，就会打破平衡，会使坏的更坏，L受到影响。
使用代码表述多类SVM损失，分为非向量化和半向量化两个版本（还有一个全向量化在作业中）：

def L_i(x, y, W):
  """
  非向量化版本。 
  计算单个例子（x，y）的多类svm损失    
  - x 是表示图像的列向量（例如，CIFAR-10中的3073 x 1），附加偏置维度
  - y 是一个给出正确类索引的整数（例如，CIFAR-10中的0到9之间）    
  - W 是权重矩阵（例如，CIFAR-10中的10 x 3073）  """
  delta = 1.0 # 间隔 delta
  scores = W.dot(x) # 得分数组，10 x 1
  correct_class_score = scores[y]
  D = W.shape[0] # 分类的总数,即为10
  loss_i = 0.0
  for j in range(D): # 迭代所有错误分类   
    if j == y:
      # 跳过正确分类的
      continue
    # 第 i 个样本累加损失
    loss_i += max(0, scores[j] - correct_class_score + delta)
  return loss_i

def L_i_vectorized(x, y, W):
  '''
  更快的半向量化实现。 
  half-vectorized指的是这样一个事实：对于单个样本，实现不包含for循环，
  但是在样本外仍然有一个循环（在此函数之外）
  '''
  delta = 1.0
  scores = W.dot(x)
  # 用一个向量操作计算和所有类别的间隔
  margins = np.maximum(0, scores - scores[y] + delta)
  # y处的值应该为0  
  margins[y] = 0
  loss_i = np.sum(margins)
  return loss_i

这里的评分函数 $f(x_i; W) = W x_i$ ，所以损失函数可以写为：

$L_i = \sum_{j\neq y_i} \max(0, w_j^T x_i - w_{y_i}^T x_i + \Delta)$ ，其中 $w_j$ 是 $W$ 的第j行，然后被拉成一个行列向量，与 $x_i$ 列向量做点积。

$max(0,-)$ 函数，常被称为折叶损失（hinge loss）。比如平方折叶损失SVM（即L2-SVM），它使用的是 $max(0,-)^2$ ，将更强烈（平方地而不是线性地）地惩罚过界的边界值。不使用平方是更标准的版本，但是在某些数据集中，平方折叶损失会工作得更好。可以通过交叉验证来决定到底使用哪个。
总之：

我们对于预测训练集数据分类标签的情况总有一些不满意的，而损失函数就能将这些不满意的程度量化。

正则化损失（regularization loss）

假设有一个数据集和一个权重集W能够正确地分类每个数据，即所有 $L_i$ 都为0，那么W是否唯一？其实只要是任意 $\lambda$ >1， $\lambda W$ 都可以满足 $L_i$ 为0，因为把差值放大 $\lambda$ 倍后，仍然会大于 $\Delta$ 。所以，我们希望对某些W添加一些偏好，让我们的W更趋向于希望中的形式，可以通过向损失函数增加一个正则化惩罚（regularization penalty） $R(W)$ 来实现，另外一个目的也是为了让模型更加泛化。

这样就可以得到完整的多类SVM损失函数，它由两个部分组成：数据损失（data loss），即所有样例的平均损失，以及正则化损失（regularization loss）。完整公式如下：

常用的正则化损失：

最常用的R(W)是L2范式，W每个元素平方后加起来作为惩罚项，可以制约大的权重，更希望W的元素分布比较均匀：

$R(W) = \sum_k\sum_l W_{k,l}^2$

除此之外还有L1范式，作为惩罚项更希望一个比较简单的模型，即W中有很多的0：

$R(W) = \sum_k\sum_l \vert W_{k,l}\vert$

L1和L2也可以组合起来：

$R(W) = \sum_k\sum_l \beta W_{k,l}^2 + \vert W_{k,l}\vert$

对正则化损失的理解：

引入L2范数正则化损失最好的性质就是对大数值权重进行惩罚，可以提升其泛化能力，因为这就意味着没有哪个维度能够独自对于整体分值有过大的影响。举个例子，假设输入向量 $x = [1,1,1,1]$ ，两个权重向量 $w_1 = [1,0,0,0]$ ， $w_2 = [0.25,0.25,0.25,0.25]$ 。那么 $w_1^Tx = w_2^Tx = 1$ 。两个权重向量都得到同样的内积，但是w1的L2惩罚是1.0，而w2的L2惩罚是0.25。因此，根据L2惩罚来看，w2更好，因为它的正则化损失更小。从直观上来看，这是因为w2的权重值更小且更分散，这就会鼓励分类器最终将所有维度上的特征都用起来，而不是强烈依赖其中少数几个维度。这一效果将会提升分类器的泛化能力，并避免过拟合。需要注意的是，和权重不同，偏差没有这样的效果，因为它们并不控制输入维度上的影响强度。因此通常只对权重W正则化，而不正则化偏差b。最后，因为正则化惩罚的存在，不可能在所有的例子中得到0的损失值，这是因为只有当W=0的特殊情况下，才能得到损失值为0。

但是从L1惩罚来看，w1可能会更好一些，当然这里L1惩罚相同，但是一般来说，L1惩罚更希望W比较稀疏，最好是有很多为0的元素，这一特性可以用来在不改变模型的基础上防止过拟合。比如下面的例子中：

图4 L1惩罚用来防止过拟合

假设我们的训练数据得到的模型是蓝色的曲线，可以看出应该是一个多项式函数，比如

f=w_1x_1+w_2x_2^2+w_3x_3^3+w_4x_4^4

。但是当新的绿色数据输入时，显然模型是错误的，更准确的应该是绿色的线。如果我们使用L1惩罚，由于L1惩罚的特性，会希望W变得稀疏，可让

w_2,w_3,w_4

变成接近0的数，这样就可以在不改变模型的情况下，让模型变得简单泛化。

注意：

超参数 $\Delta$ 和 $\lambda$ 应该被设置成什么值？需要通过交叉验证来求得吗？现在看来， $\Delta$ 在绝大多数情况下设为 1 都是安全的。 $\Delta$ 和 $\lambda$ 看起来是两个不同的超参数，但实际上他们一起控制同一个权衡：即损失函数中的数据损失和正则化损失之间的权衡。理解这一点的关键是，权重 $W$ 的大小对于分类分值有直接影响（对他们的差异也有直接影响）：当我们将 $W$ 中值缩小，分类分值之间的差异也变小，反之亦然。因此，不同分类分值之间的边界的具体值 $\Delta=1$ 或 $\Delta=100$ 从某些角度来看是没意义的，因为权重自己就可以控制差异变大和缩小。也就是说，真正的权衡是我们允许权重能够变大到何种程度（通过正则化强度 $\lambda$ 来控制）。
与二元SVM的关系：二元SVM对于第i个数据的损失计算公式是：
$L_i = C \max(0, 1 - y_i w^Tx_i) + R(W)$
其中，C是一个超参数，并且 $y_i\in \{ -1,1 \}$ ，这个公式是多类SVM公式只有两个分类类别的特例，C和 $\lambda$ 的倒数正相关。比如对真实标签为 $y_i=1$ 的数据得分是50，则Li=0。这里只用到了 $y_i=1$ 标签的得分，因为二元SVM的W只有一行，只有一个得分并且是自身分类的得分，只要这个得分和 $y_i$ 的乘积大于1就是预测正确的了。

最终，我们得到了多类SVM损失的完整表达式：

$L = \frac{1}{N} \sum_i \sum_{j\neq y_i} \left[ \max(0, f(x_i; W)_{j} - f(x_i; W)_{y_i} + \Delta) \right] + \lambda \sum_k\sum_l W_{k,l}^2$

接下来要做的，就是找到能够使损失值最小化的权重了。

1.2.2 Softmax分类器损失

SVM是最常用的两个分类器之一，而另一个就是Softmax分类器。Softmax分类器可以理解为逻辑回归分类器面对多个分类的一般化归纳，又称为多项式逻辑回归（(Multinomial Logistic Regression）。

损失函数

还是以之前小猫的图片为例：

图5 softmax损失

图片上的内容乍一看有点吓人，下面逐个解释：

$s$ 依然是存放所有分类分值的一维数组， $s=f(x_i,W)$ ， $s_j$ 对应着第 j 个分类的得分，对数据 $x_i$ 的真实标签得分还是 $s_{y_i}$ 。现在这个分数被softmax分类器称作非归一化log概率；
函数 $f_k(s) = \frac{e^{s_k}}{\sum_j e^{s_j}}$ 是 softmax函数，其输入值是一个向量 $s$ ，向量中元素为任意实数的评分值，函数对其进行压缩，输出一个向量，其中每个元素值在0到1之间，且所有元素之和为1。现在可以把这个压缩后的向量看作一个概率分布，分类标签是 k 的概率： $P(Y=k|X=x_i)=\frac{e^{s_k}}{\sum_j e^{s_j}}$ 。这个概率被称作归一化概率，得分的指数形式被称作非归一化概率。
由上所述，真实分类标签的概率： $P(Y=y_i|X=x_i)=\frac{e^{s_{y_i}}}{\sum_j e^{s_j}}$ ，如果这个概率为1就最好不过了。所以我们希望这个概率的对数似然最大化，也就是相当于负对数似然最小。由于概率P在[0, 1]之间，所以 -log(P) 在 0 到正无穷之间，所以我们可以用这个负对数似然作为对于 $x_i$ 的损失函数：
$L_i=-logP(Y=y_i|X=x_i)=-log(\frac{e^{s_{y_i}}}{\sum_j e^{s_j}})$
整个数据集的损失：
$L = \frac{1}{N} \sum_i \left[ -log(\frac{e^{s_{y_i}}}{\sum_j e^{s_j}}) \right] + \lambda R(W)$
SVM中使用的是折叶损失（hinge loss）有时候又被称为最大边界损失（max-margin loss），Softmax分类器中使用的为交叉熵损失（cross-entropy loss），因为使用的是softmax函数，求一个归一化的概率。

根据上面的分析，可以计算出小猫的softmax损失为0.89。损失为0的时候最好，无穷大的时候最差。

图6 小猫的softmax损失计算

注意：

softmax损失这种说法只是为了描述，没有实际意义。softmax损失，最大无穷，最小是0；
给W一个比较小的初值，s中所有值都很小接近于0时，此时的损失L应该等于分类类别数的对数： $logK$ 。可根据这个判断代码是否有问题；
实际代码编写中，由于指数形式的存在，如果得分很高，会得到一个非常大的数。除以大数值可能导致数值计算的不稳定，所以学会使用归一化技巧非常重要。如果在分式的分子和分母都乘以一个常数C，并把它变换到求和之中，就能得到一个从数学上等价的公式：
$\frac{e^{s_{y_i}}}{\sum_j e^{s_j}} = \frac{Ce^{s_{y_i}}}{C\sum_j e^{s_j}} = \frac{e^{s_{y_i} + \log C}}{\sum_j e^{s_j + \log C}}$ 通常将C设为 $log C = -\max_j s_j$ 。该技巧简单地说，就是应该将向量 $s$ 中的数值进行平移，使得最大值为0。代码如下：

s = np.array([123, 456, 789]) # 例子中有3个分类，每个评分的数值都很大
p = np.exp(s) / np.sum(np.exp(s)) # 不好：数值问题，可能导致数值爆炸

# 那么将f中的值平移到最大值为0：
s -= np.max(s) # s变成 [-666, -333, 0]
p = np.exp(s) / np.sum(np.exp(s)) # 现在可以了，将给出正确结果

1.2.3 Softmax和SVM比较

下图有助于区分这 Softmax和SVM这两种分类器：

图7 SoftMax和SVM比较

计算上有不同：
针对一个数据点，SVM和Softmax分类器的不同处理方式的例子。两个分类器都计算了同样的分值向量s（本节中是通过矩阵乘来实现）。不同之处在于对s中分值的解释：SVM分类器将它们看做是分类评分，它的损失函数鼓励正确的分类（本例中是蓝色的类别2）的分值比其他分类的分值高出至少一个边界值。Softmax分类器将这些数值看做是每个分类没有归一化的对数概率，鼓励正确分类的归一化的对数概率变高，其余的变低。SVM的最终的损失值是1.58，Softmax的最终的损失值是0.452，但要注意这两个数值没有可比性。只在给定同样数据，在同样的分类器的损失值计算中，它们才有意义。
损失的绝对数值都无法解释：
SVM的计算是无标定的，而且难以针对所有分类的评分值给出直观解释。Softmax分类器则不同，它允许我们计算出对于所有分类标签的"可能性"。为什么我们要在”可能性“上面打引号呢？这是因为可能性分布的集中或离散程度是由正则化参数λ直接决定的，λ是你能直接控制的一个输入参数。随着正则化参数λ不断增强，权重数值会越来越小，最后输出的概率会接近于均匀分布。这就是说，softmax分类器算出来的概率最好是看成一种对于分类正确性的自信。和SVM一样，数字间相互比较得出的大小顺序是可以解释的，但其绝对值则难以直观解释。
在实际使用中，SVM和Softmax经常是相似的：两种分类器的表现差别很小，不同的人对于哪个分类器更好有不同的看法。相对于Softmax分类器，SVM更加“局部目标化（local objective）”，只要看到正确分类相较于不正确分类，已经得到了比边界值还要高的分数，它就会认为损失值是0，对于数字个体的细节是不关心的。softmax分类器对于分数是永远不会满意的：正确分类总能得到更高的可能性，错误分类总能得到更低的可能性，损失值总是能够更小。

2 优化

现在，我们已经有：

评分函数： $s=f(W,x)=Wx$
损失函数：
SVM 数据损失： $L_i = \sum_{j\neq y_i} \max(0, s_j - s_{y_i} + \Delta)$
Softmax 数据损失： $L_i=-log(\frac{e^{s_{y_i}}}{\sum_j e^{s_j}})$
全损失： $L=\frac{1}{N} \sum_{i=1}^NL_i+R(W)$
以及它们之间的关系：

图8 数据集、参数W、评分函数以及损失函数间的关系

如何寻找最优的 $W$ 呢？

2.1 损失函数可视化

损失函数一般都是定义在高维度的空间中（比如，在CIFAR-10中一个线性分类器的权重矩阵大小是[10x3073]，就有30730个参数），这样要将其可视化就很困难。解决办法是在1维或2维方向上对高维空间进行切片，就能得到一些直观感受。例如，随机生成一个权重矩阵 $W$ ，该矩阵就与高维空间中的一个点对应。然后沿着某个维度方向前进的同时记录损失函数值的变化。换句话说，就是生成一个随机的方向 $W_1$ 并且沿着此方向计算损失值，计算方法是根据不同的 $a$ 值来计算 $L(W + a W_1)$ 。这个过程将生成一个图表，其x轴是值 $a$ ，y轴是损失函数值。同样的方法还可以用在两个维度上，通过改变a,b来计算损失值 $L(W + a W_1 + b W_2)$ ，从而给出二维的图像。在图像中，可以分别用x和y轴表示a, b，而损失函数的值可以用颜色变化表示。下图是一个无正则化的多类SVM的损失函数的图示。左边和中间只有一个样本数据，右边是CIFAR-10中的100个数据，蓝色部分是低损失值区域，红色部分是高损失值区域：

图9 左：a值变化在某个维度方向上对应的的损失值变化中和右：a,b两个维度方向上的损失值切片

上图中注意损失函数的分段线性结构。多个样本的损失值是总体的平均值，所以右边的碗状结构是很多的分段线性结构的平均。可以通过数学公式来解释损失函数的分段线性结构。对于一个单独的数据，有损失函数的计算公式如下：

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

每个样本的数据损失值是以W为参数的线性函数的总和。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$ 和权重 $w_j$ 都是数字。单看 $w_0$ ，可以看到最上面的三个式子每一个都含 $w_0$ 的线性函数，且每一项都会与0比较，取两者的最大值。第一个式子线性函数斜率是负的，后面两个斜率是正的，可作图如下：

上图中，横轴是

w_0

，纵轴是损失，三条线对应三个线性函数，加起来即为右图。

注意：

我们将上面的评分函数 $f$ 扩展到神经网络，目标损失函数就就不再是凸函数了，图像也不会像上面那样是个碗状，而是凹凸不平的复杂地形形状；
由于max操作，损失函数中存在一些不可导点（kinks），比如折点处，这些点使得损失函数不可微，因为在这些不可导点，梯度是没有定义的。但是次梯度（subgradient）依然存在且常常被使用。在本课中，我们将交换使用次梯度和梯度两个术语。某点的次梯度是该点的左右导数之间的任意值。

2.2 优化（Optimization）策略

目标：找到能够最小化损失函数值的W 。

策略一：随机搜索（Random search）

随机尝试很多不同的权重，然后看其中哪个最好。这是一个差劲的初始方案。代码如下：

# 假设X_train的每一列都是一个数据样本（比如3073 x 50000）
# 假设Y_train是数据样本的类别标签（比如一个长50000的一维数组）
# 假设函数L对损失函数进行评价

bestloss = float("inf") # 初始指定一个最高的损失
for num in range(1000):
  W = np.random.randn(10, 3073) * 0.0001 # 随机生成一个10x3073的W矩阵
                                         # 都接近为0
  loss = L(X_train, Y_train, W) # 得到整个训练集的损失
  if loss < bestloss: # 保持最好的解决方式
    bestloss = loss
    bestW = W
  print 'in attempt %d the loss was %f, best %f' % (num, loss, bestloss)

# 输出:
# 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取出，然后去跑测试集：

# 假设X_test尺寸是[3073 x 10000], Y_test尺寸是[10000 x 1]
scores = Wbest.dot(Xte_cols) # 10 x 10000, 每个样本对应10个类得分，共10000
# 找到在每列中评分值最大的索引（即预测的分类）
Yte_predict = np.argmax(scores, axis = 0)
# 以及计算准确率
np.mean(Yte_predict == Yte)
# 返回 0.1555

验证集上表现最好的权重W跑测试集的准确率是15.5%，而完全随机猜的准确率是10%，效果不好！

转变思路：新的策略是从随机权重W开始，然后迭代取优，每次都让它的损失值变得更小一点，从而获得更低的损失值。想象自己是一个蒙着眼睛的徒步者，正走在山地地形上，目标是要慢慢走到山底。在CIFAR-10的例子中，这山是30730维的（因为W是3073x10）。我们在山上踩的每一点都对应一个的损失值，该损失值可以看做该点的海拔高度。

策略二：随机本地搜索

第一个策略可以看做是每走一步都尝试几个随机方向，如果是上山方向就停在原地，如果是下山方向，就向该方向走一步。这次我们从一个随机W开始，然后生成一个随机的扰动 aW ，只有当 W+aW 的损失值变低，我们才会更新。这个过程的具体代码如下：

W = np.random.randn(10, 3073) * 0.001 # 生成随机初始W
bestloss = float("inf")
for i in xrange(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%的分类准确率。

策略三：跟随梯度

前两个策略中，尝试在权重空间中找到一个方向，沿着该方向能降低损失函数的损失值。其实不需要随机寻找方向，因为可以直接计算出最好的方向，这个方向就是损失函数的梯度（gradient）。这个方法就好比是感受我们脚下山体的倾斜程度，然后向着最陡峭的下降方向下山。

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

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

当函数有多个自变量的时候，我们称导数为偏导数，而梯度就是在每个维度上偏导数所形成的向量。设三元函数 $f(x,y,z)$ 在空间区域G内具有一阶连续偏导数，点 $P(x,y,z)\in G$ ，称向量

$\left\{ \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} ,\frac{\partial f}{\partial z} \right\} = \frac{\partial f}{\partial x}\vec{i} +\frac{\partial f}{\partial y}\vec{j} +\frac{\partial f}{\partial z} \vec{k} =f_{x}(x,y,z)\vec{i}+f_{y}(x,y,z)\vec{j}+f_{z}(x,y,z)\vec{k}$

为函数 $f(x,y,z)$ 在点P的梯度，记为：

$grad f(x,y,z)=f_{x}(x,y,z)\vec{i}+f_{y}(x,y,z)\vec{j}+f_{z}(x,y,z)\vec{k}$

2.3 梯度计算

计算梯度有两种方法：一个是缓慢的近似方法（数值梯度法），但实现相对简单。另一个方法（分析梯度法）计算迅速，结果精确，但是实现时容易出错，且需要使用微分。

2.3.1 利用有限差值计算梯度

下面代码是一个输入为函数f和矩阵x，计算f的梯度的通用函数，它返回函数f在点x处的梯度，利用公式 $\frac{df(x)}{dx} = \lim_{h\ \to 0} \frac{f(x + h) - f(x)}{h}$ ，代码对x矩阵所有元素进行迭代，在每个元素上产生一个很小的变化h，通过观察函数值变化，计算函数在该元素上的偏导数。最后，所有的梯度存储在变量grad中：

图10 有限差值计算梯度示意图

代码如下：

def eval_numerical_gradient(f, x):
  """  
  我们是求L关于w的梯度，f就是损失L，x就是权重矩阵w
  一个 f 在 x 处的数值梯度法的简单实现
  - f 是参数 x 的函数，x 是矩阵，比如之前的 w 是10x3073  
  - x 是计算梯度的点
   """ 

  fx = f(x) # 计算x点处的函数值
  grad = np.zeros(x.shape)  # 梯度矩阵也是10x3073
  h = 0.00001  # 近似为0的变化量

  # 对x中所有的索引进行迭代，比如从（0,0）到（9,3072）
  it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])
  # np.nditer是np自带的迭代器
  # flags=['multi_index']表示对 x 进行多重索引 比如(0,0)
  # op_flags=['readwrite']表示不仅可以对x进行read（读取），还可以write（写入）
  while not it.finished:

    # 计算x+h处的函数值
    ix = it.multi_index   #索引从(0,0)开始，即从x矩阵第一行第一列的元素开始
    old_value = x[ix]   # 先将x(0,0)处原值保存
    x[ix] = old_value + h # 增加h
    fxh = f(x) # 计算新的f(x + h)
    x[ix] = old_value # 将x(0,0)处改回原值

    # 计算偏导数
    grad[ix] = (fxh - fx) / h # x(0,0)处的偏导数
    it.iternext() # 到下个维度x(0,1)

  return grad # 最终是计算好的10x3073的梯度矩阵

实际中用中心差值公式（centered difference formula）( $[f(x+h) - f(x-h)] / 2 h$ )效果会更好。下面计算权重空间中的某些随机点上，CIFAR-10损失函数的梯度：

# 为了使用上面的代码，需要一个只有一个参数的函数
# (在这里参数就是权重W)所以封装了X_train和Y_train
def CIFAR10_loss_fun(W):
  return L(X_train, Y_train, W)

W = np.random.rand(10, 3073) * 0.001 # 随机权重矩阵
df = eval_numerical_gradient(CIFAR10_loss_fun, W) # 得到梯度矩阵

梯度告诉我们损失函数在每个元素上的斜率，以此来进行更新：

loss_original = CIFAR10_loss_fun(W) # 初始损失值
print 'original loss: %f' % (loss_original, )

# 查看不同步长的效果
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 # 权重空间中的新位置，使用负梯度
  loss_new = CIFAR10_loss_fun(W_new)
  print 'for step size %f new loss: %f' % (step_size, loss_new)

# 输出:
# 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的负方向去更新，这是因为我们希望损失函数值是降低而不是升高。（偏导大于0，损失递增，W需要减小；偏导小于0，损失递减，W需要增大。）
步长的影响：从某个具体的点W开始计算梯度，梯度指明了函数在哪个方向是变化率最大的，即损失函数下降最陡峭的方向，但是没有指明在这个方向上应该迈多大的步子。小步长下降稳定但进度慢，大步长进展快但是风险更大，可能导致错过最优点，让损失值上升。在上面的代码中就能看见反例，在某些点如果步长过大，反而可能越过最低点导致更高的损失值。选择步长（也叫作学习率）将会是神经网络训练中最重要（也是最头痛）的超参数设定之一。
效率问题：计算数值梯度的复杂性和参数的量线性相关。在本例中有30730个参数，所以损失函数每走一步就需要计算30731次损失函数（计算梯度时计算30730次，最终计算一次更新后的。），现代神经网络很容易就有上千万的参数，因此这个问题只会越发严峻。显然这个策略不适合大规模数据。

2.3.2 利用微分分析计算梯度

使用有限差值近似计算梯度比较简单，但缺点在于只是近似（因为我们对于h值是选取了一个很小的数值，但真正的梯度定义中h趋向0的极限），且耗费计算资源太多。得益于牛顿-莱布尼茨的微积分，我们可以利用微分来分析，得到计算梯度的公式（不是近似），用公式计算梯度速度很快，唯一不好的就是实现的时候容易出错。为了解决这个问题，在实际操作时常常将分析梯度法的结果和数值梯度法的结果作比较，以此来检查其实现的正确性，这个步骤叫做梯度检查。

比如我们已知多类SVM的数据损失Li：

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

可以对函数进行微分。比如对 $w_{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$

其中 $1$ 是一个示性函数，如果括号中的条件为真，那么函数值为1，如果为假，则函数值为0。

虽然上述公式看起来复杂，但在代码实现的时候比较简单：只需要计算没有满足边界值的即对损失函数产生贡献的分类的数量，然后乘以 $x_i$ 就是梯度了。注意，这个梯度只是对应正确分类的W的行向量的梯度，那些 $j \neq y_i$ 行的梯度是：

$\nabla_{w_j} L_i = \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) x_i$

一旦将梯度的公式微分出来，代码实现公式并用于梯度更新就比较顺畅了。

2.4 梯度下降（Gradient Descent）

现在可以利用微分公式计算损失函数梯度了，程序重复地计算梯度然后对参数进行更新，这一过程称为梯度下降。

普通梯度下降

# 普通的梯度下降
while True:
  weights_grad = evaluate_gradient(loss_fun, data, weights)
  weights += - step_size * weights_grad # 进行梯度更新

这个简单的循环在所有的神经网络核心库中都有。虽然也有其他实现最优化的方法（比如LBFGS），但是到目前为止，梯度下降是对神经网络的损失函数最优化中最常用的方法。课程中，我们会在它的循环细节增加一些新的东西（比如更新的具体公式），但是核心思想不变，那就是我们一直跟着梯度走，直到结果不再变化。

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

在大规模的应用中（比如ILSVRC挑战赛），训练数据量 N 可以达到百万级量级。如果像这样计算整个训练集，来获得仅仅一个参数的更新就太浪费计算资源了。一个常用的方法通过训练集中的小批量（batches）数据来计算。例如，在目前最高水平的卷积神经网络中，一个典型的小批量包含256个样本，而整个训练集是一百二十万个样本。（CIFAR-10，就有50000个训练样本。）比如这个小批量数据就用来实现一个参数更新：

# 普通的小批量数据梯度下降
while True:
  data_batch = sample_training_data(data, 256) # 从大规模训练样本中提取256个样本
  weights_grad = evaluate_gradient(loss_fun, data_batch, weights)
  weights += - step_size * weights_grad # 参数更新

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

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

2.5 特征提取

直接输入原始像素，效果不好，可以将图像的特征计算出来，便于分类。

常用的特征计算方式：颜色直方图、词袋、计算边缘等，神经网络中是特征是训练过程中得到的。

总结

线性分类器各种细节，可在斯坦福大学开发的一个在线程序观看演示：点击这里

损失函数概述，数据损失与正则损失，多类SVM损失、softmax损失及两者的比较；
W优化策略，梯度计算方法，梯度下降。

最后编辑于：2019.01.13 16:14:43

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