CS231n（3）：损失函数与最优化

本文主要参考Convolutional Neural Networks for Visual Recognition[1]课程笔记。

预备知识

k-NN在训练时只是记住了所有的样本，占用空间大，在识别时需和训练集的所有图片比较，耗费时间长。因此，需要开发新的方法克服kNN存在的问题，新方法包含两个关键部分：

1. 评分函数（score function）：将输入图像映射为所属类别的评分；
2. 损失函数（loss function）：度量预测的评分与真实结果之间的一致性，也称为代价（cost）函数或目标（objective）函数。当评分函数输出结果与真实结果之间差异越大，损失函数输出越大。

训练时，通过最小化损失函数，得到评分函数的参数；分类时，通过对输入图像所属类别评分，判断图像的类别。

训练集图像$\mathbf x_i\in\mathbb R^D(i=1,2,\ldots,N)$对应的标签$y_i\in 1,2,\ldots,K$，表示训练集有$N$张图像，每个图像表示为一个$D$维向量，图像可分为$K$个类别。对于CIFAR-10数据集，$N=50000,D=32\times 32\times 3,K=10$。评分函数$f:\mathbb R^D\mapsto \mathbb R^K$将图像数据映射为所属类别的评分。

线性分类器

线性分类器（linear classifier）就是一个评分函数，它是一个线性映射 \begin{equation} f(\mathbf x_i,\mathbf W, \mathbf b)=\mathbf W\mathbf x_i+\mathbf b， \label{multiclass-linear-classifier-1} \end{equation} 其中，$\mathbf x_i$表示图像展成的$D\times 1$维的向量，$\mathbf W$是$K\times D$维的权值矩阵，$\mathbf b$是$K\times 1$维的偏移向量（bias vector）。对CIFAR-10数据集，该映射输入的输入是3072维向量，输出属于这10个类别的评分。$\mathbf W$的用每行表示一个分类器，因此可以并行计算。一旦得到这些参数$\{\mathbf W,\mathbf b\}$之后，不必像k-NN一样存储整个训练集，只需保存参数即可¹。

图 1: 线性分类器示意 [JPG]

上图展示了线性分类器计算过程，将图像简化为4个像素代替，🐶的得分最高导致了🐱误判为🐶，这并不是一个良好的分类器。权值的正负号表示了某个位置的像素对分类结果是赞成还是反对，权值的大小表示强弱程度，从这个角度看就是投票模型。

线性分类器可以理解为模版匹配（template matching），$\mathbf W$的每一行对应一个模版，通过图像与模版的内积（inner product）²判断图像与哪个模版最相似。从这个角度看，线性分类器也是最近邻分类器，并且只需和每类学习到的唯一模版比较，效率更高，匹配时采用内积而非$L_1$或$L_2$度量距离。

图 2: 线性分类器权值矩阵图像化 [JPG]

上图用图像的方式展示了线性分类器在CIFAR-10上学到的权值矩阵，这些图像相当于从每类学习到的模版。

若将图像追加一个值为1的“特征”，可将偏移向量$\mathbf b$合并到权值矩阵$\mathbf W$中，公式\eqref{multiclass-linear-classifier-1}可改写为更简练的形式 \begin{equation} f(\mathbf x_i,\mathbf W)=\mathbf W\mathbf x_i。 \label{multiclass-linear-classifier-2} \end{equation}

在机器学习中，将输入特征归一化是常用的技术。在实际中，将图像的每维特征（像素）减去均值中心化，对图像而言就是将每张图像减去平均图像，得到新图像的像素取值范围是$[-127,127]$。还可进一步将特征取值规范化到$[-1,1]$区间。

在线性分类器（评分函数）基础上，通过定义不同损失函数，可得到具备不同特性的多分类支持向量机和softmax分类器。

多分类支持向量机

图 3: 损失函数示意图 [JPG]

支持向量机期望评分函数在固定边界$\Delta$控制下，正确分类比错误分类输出更高的评分。$f(\mathbf x_i,\mathbf W)_j$表示图像$\mathbf x_i$属于类别$j$的评分，多分类支持向量机的损失函数定义为 \begin{equation} L_i = \sum_{j\neq y_i}\max(0, f(\mathbf x_i,\mathbf W)_j-f(\mathbf x_i,\mathbf W)_{y_i}+\Delta)， \label{eq:m-svm-loss} \end{equation} 损失函数期望正确分类比错误分类输出更小的值。支持向量机期望正确分类比错误分类至少多得分$\Delta$，这样就没有损失，如上图所示，如果任何类别的评分落在红色区间，就会有损失累加。作出好的预测等价于最小化损失。

$\max(0,\cdots)$一般称为hinge损失，也称为最大边界损失（max-margin loss），$L_2$-SVM的平方损失$\max(0,\cdots)^2$惩罚力度更强。hinge损失比平方hinge损失更标准通用，但有的数据集平方hinge损失效果更好，可以通过交叉验证选择损失度量方式。

假设$f(\mathbf x_i,\mathbf W)＝[13, -7, 11], y_i=0,\Delta=10$，那么 \[ L_i=\max(0, -7-13+10)+\max(0,11-13+10)=8。 \] 上式右边第1项，正确分类得分（13）要高于错误分类（-7），支持向量机只关心是否二者差异至少为10（事实上二者差距为20分），因此输出为0；上式右边第2项，正确分类得分（13）高于错误分类（11），但二者差异只有2，因此损失了8。

将\eqref{multiclass-linear-classifier-2}代入\eqref{eq:m-svm-loss}可得 \begin{equation} L_i = \sum_{j\neq y_i}\max\left(0, \mathbf w_j^T\mathbf x_i - \mathbf w_{y_i}^T\mathbf x_i +\Delta\right)， \end{equation} 其中，$\mathbf w_j^T$是$\mathbf W$的第$j$行元素。

学习（训练）阶段的目标就是期望得到权值矩阵$\mathbf W$，使得正确分类的评分高于其它所有类别，并且使损失函数尽量小。

假设$\mathbf W$将一个数据集的每个样本都正确分类（对所有的$i$，$L_i=0$），$\mathbf W$却不是唯一的存在，当$\lambda>0$时$\lambda\mathbf W$都能胜任。通过正则化惩罚（regularization penalty）$R(\mathbf W)$，可以消除$\mathbf W$的歧义。常用的正则化惩罚抑制$L_2$范数大的$\mathbf W$出现， \[ R(\mathbf W)=\sum_k\sum_l w_{k,l}^2， \] 正则化只针对权值与输入数据无关。因此，多分类支持向量机的损失函数包括两部分，数据损失（data loss）和正则化损失（regularization loss）， \begin{equation} L={1\over N}\sum_i\sum_{j\neq y_i}\max\left(0, \mathbf w_j^T\mathbf x_i - \mathbf w_{y_i}^T\mathbf x_i +\Delta\right)+\lambda \sum_k\sum_lw_{k,l}^2。 \label{eq:regularization-loss-function} \end{equation}

1. 损失函数\eqref{eq:regularization-loss-function}采用\eqref{multiclass-linear-classifier-1}的权值$\mathbf w_j$包含偏移分量$b_j$，但正则化采用\eqref{multiclass-linear-classifier-2}的权值$\mathbf W$不包含偏移向量$\mathbf b$，实际应用中即使正则化了$\mathbf b$对结果影响也不大。
2. 由于增加了正则化项，正常情况下损失函数不可能到达0。
3. 控制正则化力度的参数$\lambda$仍然只能通过交叉验证选择。
4. 采用$L_2$正则化，可以导出支持向量机的最大边界特性。

正则化使得没有哪一个维度可以对评分造成很大的影响，通过惩罚大的权值提高了泛化（generalization）性能，降低了过拟合（overfitting）风险。当$\mathbf x=[1,1,1,1]^T$、$\mathbf w_1=[1,0,0,0]^T$和$\mathbf w_2=[0.25,0.25,0.25,0.25]^T$时，虽然$\mathbf w_1^T\mathbf x=\mathbf w_2^T\mathbf x=1$，但$L_2$对$\mathbf w_1$的惩罚是1对$\mathbf w_2$的惩罚只有0.25，因此结果偏爱$\mathbf w_2$。$L_2$惩罚偏爱取值小且分散的权值向量，最终得到的分类器会尽量考虑所有维度的输入，而非更偏爱哪一个维度³。

$\Delta$和$\lambda$虽是两个不同的参数，但都是相同的折中效果。不需交叉验证选择$\Delta$，直接设置$\Delta=1.0$即可，只需通过交叉验证调节$\lambda$。放大$\mathbf W$可以放大评分，缩小$\mathbf W$也可缩小评分 ，度量评分之间的差距的$\Delta$也同步放大或缩小，而调节$\lambda$可放缩$\mathbf W$，因此固定住$\Delta$只设置$\lambda$即可。

对于二分类支持向量机，损失函数表示为 \[ L=C\sum_{i=1}^N\max\left(0, 1-y_i\mathbf w^T\mathbf x_i\right)+R(\mathbf w)， \] 其中$C$是超参数，$y_i\in\{-1,+1\}$。它可视为本文多分类问题简化为二分类的一个特例，$C$和$\lambda$都有相同的折中作用，$C\propto{1\over \lambda}$。

本文的多分类支持向量机，只是支持向量机解决多分类问题的方法之一。除此之外还有一对多（OVA，one-vs-all）策略和实际中很少使用的多对多（AVA，all-vs-all）。简单的OVA策略能很好处理多分类问题[2]，本文的方法是OVA的增强版[3]，理论上数据损失项可达0，常规的OVA方法则不行。

softmax分类器

softmax分类器是logistic回归分类器在多分类问题的推广。$f_j(\mathbf z)={e^{z_j}\over\sum_k e^{z_k}}$被称为softmax函数（softmax function），它将实数转换为$[0,1]$区间的值。softmax分类器采用同样的评分函数\eqref{multiclass-linear-classifier-2}，但采用交叉熵损失（cross-entropy loss）函数 \begin{equation} L =-{1\over N}\sum_{i=1}^N\log\left({e^{f_{y_i}}\over\sum_j e^{f_j}}\right)+R(\mathbf W) =-{1\over N}\sum_{i=1}^N\left(f_{y_i}-\log\sum_j e^{f_j}\right)+R(\mathbf W)。 \end{equation}

“真实”分布$p$和估计所得分布$q$之间的交叉熵定义为 \[ H(p,q)=-\sum_xp(x)\log q(x)， \] 交叉熵也可记为熵与Kullback-Leibler散度（divergence）之和的形式 \[ H(p,q)=H(p)+D_{KL}(p\| q)， \] 其中熵$H(p)=-\sum_xp(x)\log p(x)$。对softmax分类器，属于类别$y_i$的概率估值$q={e^{f_{y_i}}\over\sum_j e^{f_j}}$，属于类别$y_i$的“真实”概率$p=1$，因此对本文分类问题$H(p)=0$。最小化代价函数等价于最小化两个分布之间的KL散度。通过交叉熵，期望能预测的分布能在正确分类的类别上概率达到最大。

softmax函数可以视为概率形式 \[ P(y_i|\mathbf x_i;\mathbf W)={e^{f_{y_i}}\over\sum_j e^{f_j}}， \] 表示预测正确分类$y_i$的归一化概率。好的分类结果是$\prod_{i=1}^NP(y_i|\mathbf x_i;\mathbf W)$最大，这可认为是最大似然估计（MLE，maximum likelihood estimation）。正则化项$R(\mathbf W)$可认为源自权值矩阵的高斯先验（Gaussian prior），最小化损失函数相当于最大后验概率估计（maximum a posteriori）。当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计[4, P. 9]。

编程实现时，$e^{f_{y_i}}$和$\sum_j e^{f_j}$的值可能很大，大数值相除不稳定，所以需要采用规范化技巧（normalization trick）。softmax函数可以写为等价的形式 \[ \frac{e^{f_{y_i}}}{\sum_j e^{f_j}}=\frac{Ce^{f_{y_i}}}{C\sum_j e^{f_j}}=\frac{e^{f_{y_i}+\log C}}{\sum_j e^{f_j+\log C}}， \] 提高计算的稳定性，通常选择$\log C=-\max_jf_j$，将评分的最大值规范化为0。

SVM vs. softmax

图 4: SVM和softmax的对比 [PNG]

支持向量机的结果不易理解，softmax分类器给出了所属类别的“概率”解释。事实上，概率分布是平坦还是尖峰依赖于正则化参数$\lambda$。

当线性分类器输出$[1, -2, 0]$时，softmax函数输出“概率” \[ [1, -2, 0]\rightarrow [e^1, e^{-2}, e^0]= [2.71,0.14,1]\rightarrow [0.7,0.04,0.26]。 \] 当增大正则化系数$\lambda$，这可能导致更小的权值，线性分类器的输出假设减小到$[0.5, -1, 0]$，此时softmax函数输出“概率” \[ [0.5, -1, 0]\rightarrow [e^{0.5}, e^{-1}, e^0]= [1.65,0.37,1]\rightarrow [0.55,0.12,0.33]， \] 概率分布变得更均匀。大的正则化系数$\lambda$导致权值变小，类别的输出概率更趋于均匀化（uniform）。因此，softmax函数输出的“概率”之间大小比较有意义，单独看某个“概率”值的大小没有明确意义，也就是相对大小有意义，绝对大小没意义。

多分类支持向量机和softmax分类器，在性能表现上通常很相近。假设$\mathbf x_i$属于第1类，对于$[10, -100, -100]$和$[10, 9, 9]$，多分类支持向量机都不再增加损失函数的值；但对于softmax分类器，$[10, 9, 9]$会比$[10, -100, -100]$让损失函数增加更大的值。softmax分类器永不满足，总是试图让正确的分类概率更大，损失函数的值更小；然而，只要多分类支持向量机满足边界条件，不论评分高低，不再调整评分，这可以看作是多分类支持向量机的一个特性，比如对于一个车辆分类器，它应该关注如何分类轿车和卡车等困难问题，而不应受已经评分很低🐸🐱🐶等的影响。

参考文献

1. [1]F.-F. Li and A. Karpathy, “Linear classification: Support Vector Machine, Softmax.” GitHub, 2015. [Online]
2. [2]R. Rifkin and A. Klautau, “In defense of one-vs-all classification,” Journal of Machine Learning Research, vol. 5, pp. 101–141, 2004.
3. [3]J. Weston and C. Watkins, “Support Vector Machines for Multi-Class Pattern Recognition,” in European Symposium on Artificial Neural Networks, Bruges (Belgium), 1999, pp. 219–224. [Online]
4. [4]李航, 统计学习方法. 北京: 清华大学出版社, 2012.

脚注