CS231n第二节：线性分类器

传送门

本系列文章基于CS231n课程，记录自己的学习过程，所用视频资料为 2017年版CS231n，阅读材料为CS231n官网2022年春季课程相关材料

上一节介绍了图像分类问题——从固定的类别集合中选出一个标签分配给一张图片的任务，解释了图片分类问题的难点。同时，介绍了KNN分类器，它的原理是将待预测的图片与训练集中的所有图片比较，将最相近的图片的表情作为带预测图片的标签。KNN有很多的缺点，比如需要存储整个训练集，空间利用率低，预测所需的时间长。

本文主要介绍一种更加强大的处理图片分类问题的方法，这一方法可以延伸至神经网络以及CNN。这种方法主要由两部分组成：评价函数和损失函数，前者用于将原始的数据映射成某一分类的得分情况，后者用于量化预测结果和真实结果的差距。接着，我们就可以将图片分类问题转化成一个最优化问题， 即通过改变评价函数的参数最小化损失函数。

SVM和softmax的可视化交互网页

1. 从图像到标签值的映射

首先我们定义一个评价函数，用于将图片的像素映射为每一类别的得分，具体来说，假设我们有一个训练集，其中的每个样本 $x_i \in \R^D$ ，每个样本对应一个标签 $y_i$ ，这里的 $i = 1...N,y_i\in1...K$ ，表示有 $N$ 个样本，$K$ 个不同的类别，所以我们需要做的是定义一个评估函数 $f:\R^D \rightarrow \R^K$，即将D维特征空间的样本映射成一个K维的向量。以CIFAR-10数据集为例，训练集中有50000张图片，则$N=50000$，每张图片为RBG三通道的32*32的图片，则 $D = 32 * 32 * 3 =3072$，一共有10个类别，则 $K = 10$ 。

我们以最简单的线性分类器为例，即我们定义评估函数为 ：

上式表示，我们将图片 $x_i$ 展开成一个大小为 $[D *1]$ 的列向量，$W$ 为一个 $[K*D]$ 的矩阵， $b$ 为$[K*1]$ 的向量，通常我们称 $W$ 为权重， $b$ 为偏置项，它们都是评估函数的参数。

需要关注的是：

• 使用矩阵乘法 $Wx_i$ 的效率很高，因为矩阵乘法通常可以使用并行化处理。
• 我们不会改变输入数据 $(x_i,y_i)$ ,我们通过设置参数 $W,b$ 来改变对于某个数据在每个类别下的得分情况。使用我们的目标是通过某种途径设置参数 $W,b$ 使得整个训练集中的样本的得分情况与各自真实的标签匹配。
• 采用这种方法的好处是，一旦我们通过训练集得到合适的参数 $W,b$ 后，我们就可以丢弃训练集，只要存储所有的参数即可。当遇到一个新的样本，我们可以直接使用这些参数通过评估函数预测它属于哪个类别。这是区别于KNN空间利用率低的一大优势。
• 不同于KNN在预测时需要将待测样本与整个训练集比较，使用这种方法只需要将待测样本与参数矩阵做乘法和加分即可，在时间效率上也是很大的提升

2. 对线性分类器的解释

2.1 直观理解

如下图就是线性分类器的工作过程，对于一张图片，假设是个黑白的 $2*2$ 的图片，我们首先将其展开成一个 $4*1$ 的列向量。假设我们一共有三个类比（猫，狗，船），下图中红色的表示识别猫的分类器，绿色的表示识别狗的分类器，蓝色表示识别船的分类器，三个分类器的参数堆叠在一起组成了评估函数的参数矩阵。将参数矩阵与原始数据相乘并加上对应的偏置项，得到每个分类器的得分，可以看到猫的得分为 -96.8，狗的得分为437.9，这说明，分类器认为这张图片最可能是只狗，最不可能是只猫，对于图中的例子，这无疑是个很不好的结果（因为输入图片是一只猫）。

从上述例子我们可以看出，线性分类器首先将一个RGB通道的图片的每个位置的像素进行加权后求和，将求和后的值作为该分类器所属类别的分数（分数最高的分类器所属的类别作为这张图片的预测类别）。那么线性分类器的原理是什么呢？评估函数通过调整参数，使得其有能力倾向于或者不倾向于图片某个位置的某个颜色。举例来说，对于一张船的图片，图片的周围很可能有很多的蓝色（表示在大海中），那么对于船的分类器就可能对图片四周位置的蓝色通道的权重设置成一个正数，而对相同位置的红色通道和绿色通道的权重设置成一个负数，这样对于某张图，如果满足图片四周位置的蓝色通道的数值大，而其他通道数值小（在图片中表现为四周为蓝色），那么它的评估得分也就会高。

2.2 几何理解

运用线性分类器后，我们将每张图片都转变成了一个 $K$ 维的向量，那么我们可以将其看成 $K$ 维空间中的一个点，同样，对于原来的图片，也可以看成高维空间中的一个点（比如CIFAR-10数据集中的每个图片可以看成3072维空间中的一个点）。由于我们定义每个类别得分为某张图片所有像素的加权和，所有每个类别的得分其实可以看成这个高维空间中的一个超平面，虽然无法可视化高维空间，但是如果将高维空间降维至二维，我们可以尝试可视化每个分类器在做什么：

如上图所示，有三根直线分别代表汽车分类器、鹿分类器、飞机分类器，以红色的汽车分类器为例，如果某个点刚好在线上，则汽车种类的得分为0，红色线上的箭头表示在这个方向上汽车得分为正，在反方向则为负。由此我们可以得出，评估函数中的 $W$ 每一行代表一个分类器，而一个分类器在高维空间中就是一个划分空间的超平面，所以 $W$ 中的每一行就代表一个分类器所对应超平面在空间中的方向，改变 $W$ 的值的效果就是旋转这个超平面。而偏置项 $b$ 其实就是超平面的截距，代表超平面在高维空间中的位置，如果没有偏置项，那么超平面只能过高维坐标系的原点。

2.3 模板匹配角度

对于参数 $W$ 还有一种解释：对于每一行的 $W$ ，其代表了某一类别的模板，当预测图片时，我们将图片分别与每个类别的模板做内积，得到每个类别的评估得分，得分最高的类别作为预测结果。所以，线性分类器其实就是在做模板匹配的过程，而这些模板是从训练集中的图片训练得到的。另外还有一种理解角度，可以把线性分类器看成一种更高效的KNN算法。只是区别在于它不用和KNN一样存下整个训练集，而是将训练集浓缩成一个模板图片 $W$ ，并且将内积作为距离函数，而不是KNN中的L1和L2距离。

如下图是使用CIFAR-10作为训练集训练得到的分类器，从 $W$ 得到每个种类分类器的可视化结果：

观察图片，可以发现一些有意思的事情，马的分类器可视化出来的是一个双头马，这说明在CIFAR-10的训练集中有头朝左和头朝右的马，于是分类器将这种特征合并在模板中。再比如车的分类器，可以隐约看出一个车的形状，并且车的颜色以红色居多，这说明在CIFAR-10的训练集中红色的汽车居多。这也说明了一个问题，当分类器遇到一个其他颜色的车时，它的识别效果可能就会变差，也说明这个分类器的泛化能力不是很好。这是由数据集和模型的局限性导致的，在之后介绍的神经网络中，通过隐藏层，就能比较好的解决这个问题（当然也需要一个更好的数据集）。

2.4 偏置项合并

前面介绍到我们的评估函数为：

参数为 $W$ 和 $b$，这样的形式有些臃肿了，我们可以考虑将两个参数合并成一个矩阵，即在 $W$ 矩阵上新增一列$W_0$，这一列就作为偏置项，相应地我们在输入的向量中增加一维代表 $x_0$ ，值恒定为1，这样 $x_0$ 和 $W_0$ 的内积就等于偏置项 ，合并参数后，我们的评估函数变为：

参数合并的示意图如下：

2.5 数据预处理 normalization

在前面的过程中，我们都是直接使用原始的图片数据来训练。在机器学习中，对输入的特征进行归一化是一种很普遍的做法。具体来说，我们图片的每个像素的数据范围是 $[0-255]$,然后我们得到训练集中每个位置像素的平均值，得到一个平均像素矩阵，然后将每张图片都减去这个平均像素矩阵，数据范围大约变成$[-127,127]$，更一般的做法是将其归一化至 $[-1,1]$ 的范围。

3. 损失函数

在上一节，我们定义了一个评估函数，通过设置评估函数的参数 $W$ ，我们希望分类器预测类别的得分和真实值接近。但是，有时事实不尽人意，比如我们预测猫的图片，但是分类器给出猫的评分可能为一个很小的负数，然后其他种类的得分非常大，这显然不是我们想要的。那么我们需要一个函数来量化我们对分类器的预测结果的不满意度，即损失函数（或代价函数）。直观来讲，当分类器的效果很好时，损失值将会很低；当分类器的效果很差时，损失值将会很高。

3.1 多分类SVM的损失函数

损失函数的定义方式有很多，先来介绍一种常用的损失函数——多分类SVM的损失函数。多分类SVM的损失函数希望每个图片对应的真实样本的预测得分比其他类别的得分高出一个间隔。我们定义第 $i$ 个样本 $x_i$ 的第 $j$ 个类别的预测得分为 $s_j = f(x_i,W)_j$ 。那么多分类SVM的代价函数如下：

其中 $s_j$ 表示第 $j$ 个类别的得分，$s_{y_i}$ 表示第 $i$ 个样本的真实标签 $y_i$ 的预测得分， $\Delta$ 表示间隔。举例来说，假设我们有三个类别，并得到某个样本的预测得分为 $[13,-7,11]$，假设该样本的真实标签为 $y_i = 0$，假设 $\Delta = 10$ （这是一个超参数，人为设定），那么我们可以得到损失值：

对于第一个类别的预测得分13，不会在损失函数中计算，因为这是真实种类对应的预测得分。接着是第二个类别的预测得分-7，由于该种类的预测得分远小于真实种类的预测得分（13），所以通过与 0 取max的方式 $\max (0,-7-13+10) = 0$，得到其损失值为0。然后是第三个类别的预测得分，虽然也比真实预测得分低，但是它和真实类别的预测得分的差小于间隔 $\Delta = 10$ ，所以得到它的损失值为 8。综上所述，多分类SVM的损失函数希望其他种类的预测得分比真实种类的预测得分相差一个 $\Delta$ 的间隔，如果不满足则会累计误差，可以用下图形象化地表现：

此外还有一点需要说明的，在多分类SVM的损失函数中使用的 $max(0,-)$ 也称为铰链函数，因为它的图像很像一个铰链。有时SVM也会用到平方铰链函数，即$max(0,-)^2$，这时SVM对那些不满足要求的损失值给予更大的惩罚（即对于在间隔内的点）。

3.2 正则化 Regularization

不过对于上述的损失函数，还有一个漏洞。设想一下，我们有一个参数为 $W$ 的分类器可以正确分类数据集中的所有数据，也就是说对于全部数据 $L_i=0$，问题在于，这里的 $W$ 是不唯一的，也就是说可能存在多个不同的参数 $W$ 都可以使得 $L_i = 0$ 。举一个最简单的例子，如果使用参数 $W$ 的分类器在某个数据集下的 $L_i = 0$ ，那么使用参数 $\lambda W,\ \lambda>1$ 的分类器得到的 $L_i$ 也都为0。因为将参数都乘上 $\lambda$，只会使得每个种类的预测得分乘上 $\lambda$，那么 $s_j-s_{y_i}$ 也会乘上 $\lambda$（变量含义见前文），但是损失值已经为0，说明 $s_{j}-s_{y_{i}}+\Delta <0$ ，所以 $\lambda(s_{j}-s_{y_{i}})+\Delta <0$ ，损失函数值依旧为0。

换句话说，我们希望有一种方式可以采取一种合适的偏好来选择一种权重集合来消除这种歧义。我们只需在损失函数后增加一个正则项 $R(W)$ 即可实现，最常用的正则项为平方 $L2$ 正则化，它通过在损失函数中引入权重的平方和来阻碍模型训练时选择大的权重，具体表达式如下：

从式子中可以看出，正则化只是对权重进行的，与训练数据无关，加上正则项后，多分类SVM的损失函数变为：

前半部分表示由于预测样本导致的损失值，后半部分表示权重的损失值，其中 $\lambda$ 是正则化系数，也属于超参数，可以用过交叉验证来选取。不同的正则项有不同的特性，比如 $L2$ 正则项在SVM中使用时，会使得模型偏向于选择使间隔最大的一种权重。最重要的是，正则项可以有效地抑制较大权重的产生，以此来提高泛化能力减小过拟合现象，因为较小的权重意味着输入数据的大小对评估函数的结果不会有太大的影响。

最后需要说明的是，不同于权重，偏置项不会影响输入数据对评估函数输出的影响，所以一般不会对偏置项进行正则化，不过其实在实际应用中，是否对偏置项正则化影响不大。另外，引入正则项后，损失函数永远不可能为0，除非将权值全设为0，但这是很不理智的一件事。

3.3 损失函数的代码实现

3.4 $\Delta$ 的设置

从上面的损失函数可以知道，除了权重以外，还有两个超参数 $\Delta$ 和 $\lambda$ 需要我们手动设置，虽然可以采用交叉验证的方式，但是其实我们对于任何情况，都可以将 $\Delta$ 设置为1。$\Delta$ 和 $\lambda$ 看似是两个不同的超参数，但其实他们有同样的效果：用于平衡数据损失值和正则化损失值。正则项影响的是权重 $W$ 的量级，权重的量级又影响这评估函数的结果：权重量级越大，那么不同种类之间的评估得分相差也就越大，反之相差也就越小，所以正则项控制着评估得分之间的差异，而正则化的强弱是由 $\lambda$ 控制的，通过改变 $\lambda$ 可以任意放大或者缩小这种差异。于是乎， $\Delta$ 数值的大小也就变得没有那么重要了，因为我们可以通过 $\lambda$ 随意控制评估得分差异的大小。因此，我们需要考虑的只有我们允许权值的大小是多少（通过控制正则项系数 $\lambda$）。

4. Softmax 分类器

除了多分类SVM分类器以外，还有一种常见的 Softmax 分类器，Softmax分类器其实就是二元逻辑回归分类器在多分类问题上的延伸。不同于 SVM 将 $f(x_i,W)$ 直接作为每个类别的评估得分，Softmax 分类器使用了一种更为直观的输出，并且有它的概率意义。Softmax 的损失函数中首先也是计算出 $f(x_i,W) = Wx_i$ ，然后使用除法归一化，最后套上log作为损失函数，其中这里的损失函数也称交叉熵损失，公式如下：

上式中的 $f_j$ 表示 $f(x_i,W)$ 的计算结果中的第 $j$ 个元素， $f_{y_i}$ 表示第 $i$ 个数据的真实样本对应的值，上式左边和右边是等价的表达方式。可以看出，Softmax的损失函数首先经过 $\frac{e^{f_{y_{i}}}}{\sum_{j} e^{f_{j}}}$ 归一化，经过这样的处理后，每个类别的评估值都在 $[0,1]$ 之间，并且全部类别的评估值之和为1，变成一个概率分布。转变为一个概率分布后，然后套上一个 $-log()$ 就是最终的损失函数了，其实际就是一个交叉熵损失。

4.1 信息学层面解释

在信息论中有一个交叉熵的概念，它主要用于度量两个概率分布间的差异性信息。在介绍交叉熵之前先介绍一些基本概念。

4.1.1信息量：

信息量的概念在平时生活中也经常遇到，下面举两个例子，比如你获得了两个信息：

• 明天太阳从东边升起
• 明天的双色球彩票号码为1234567

从直观来讲， 第一个信息的信息量比第二个小，因为第一个信息是必然发生的，而第二个信息的发生概率很小。也就是说信息量的大小取决于这个信息消除了多少不确定性，而这个信息所描述的事件发生的概率越小，则这件事情发生了所带来的信息量也就越大，也就是说信息量的大小和事件发生的概率成反比。对于事件 $x$ 信息量的公式定义为：

4.1.2 熵（Entropy）：

对于给定的离散随机变量 $X$，以可能性 $P(x_1),⋯,P(x_n)$取值为 $x_1,⋯,x_n$，则 $X$ 的熵为：

信息量度量的是一个具体事件发生所带来的信息，而熵是指该某一事件可能的结果所蕴含的不确定性的平均水平，以抛硬币为例，如果抛一枚质量均匀的硬币，那么朝上还是朝下的概率是相同的，那么此时抛一枚硬币的不确定性是最大的。但如果硬币质量不均匀，正面的概率比反面大很多，那么抛一枚硬币这个事件的不确定性就比均匀硬币要小了。也就是说，熵的概念是衡量某个事件的平均不确定性，而信息量描述的是接受该信息后消除的不确定性的量值。熵的本质其实就是对于一个事件信息量的期望。

4.1.3 相对熵（KL散度）与交叉熵：

KL散度：

这是一种量化两种概率分布P和Q之间差异的方式，又叫相对熵。在概率学和统计学上，我们经常会使用一种更简单的、近似的分布来替代观察数据或太复杂的分布。K-L散度能帮助我们度量使用一个分布来近似另一个分布时所损失的信息量。假设对于同一个随机变量 $x$ 有两个单独的概率分布 $p(x)$ 和 $q(x)$ ，我们可以用KL散度来衡量这两个分布之间的差异，具体来说，如果要比较分布 $q(x)$ 相对于 $p(x)$ 的差异，可以用下列公式：

也就是说，如果使用 $q(x)$ 描述问题，还需要一个增量 $D_{K L}(p \| q)$ ，才能和使用概率分布 $p(x)$ 来描述问题有一样的效果。

交叉熵：

在相对熵公式中，前面一半是 $\sum_{i=1}^{n} p\left(x_{i}\right) \log \left(p\left(x_{i}\right)\right)$ ，可以发现这就是概率分布 $p(x)$ 的熵，而后一半 $\sum_{i=1}^{n} p\left(x_{i}\right) \log \left(q\left(x_{i}\right)\right)$ 就是交叉熵了。它的含义为，使用概率分布 $q$ 来表示概率分布 $p$ 的困难程度。

4.1.4 在分类问题中的应用：

在分类问题中，经常将交叉熵函数与 softmax 函数相关联，这是因为 softmax 函数对一组数据的每个数据进行计算后，可以将这组数据中的每一个都映射到 (0,1) 区间上，并且其和为 1，符合概率的定义，而交叉熵恰恰是对概率分布进行计算，因此通常将 softmax 函数的输出结果作为交叉熵函数的输入，将二者构造为复合函数。在模型训练过程中，通常将每个输入的真实标签值设置为分布 p，预测值设置为分布 q，利用交叉熵函数计算出的值作为损失值用于更新权重。在这里，设 softmax 函数对输入数据 $x$ 预测为第 $i$ 类的概率为 $p_i$ ，输入数据 $x$ 属于第 $i$ 类的真实概率为 $y_i$ ，那么交叉熵函数的形式为：

举个例子，假设有三个类别，输入的数据 $x$ 属于第一类，那么期望的输出为 $p = (1,0,0)$ ，假设有两个权重不同的模型输出分别为 $q_1 = (0.5, 0.2, 0.3)$，$q_2 = (0.8,0.1,0.1)$ ，直观来看，肯定是第二个模型的预测比较精准。那么我们计算一下其交叉熵函数：

可以看到，$q_2$ 对于真实分布 $p$ 的交叉熵更小，说明与真实分布更接近，符合我们的猜想，可以用于评估模型的好坏。

在回头来看Softmax分类器，Softmax首先通过 $\frac{e^{f_i}}{\sum_{j} e^{f_{j}}}$ 将第 $i$ 类的评估得分转变为相应的概率，将整个预测变为一个概率分布，然后我们就可以用交叉熵函数进行求解：

这里的 $y_i$ 指的是真实的概率分布中第 $i$ 类的概率，$log$ 内的就是softmax分类器预测的第 $i$ 类的概率，由于分类问题的真实概率分布肯定是 $[0,0,...1,....,0]$ 的形式（one-hot编码），所以等式可以进一步化简：

这里的 $f_{real}$ 表示输入样本所属真实种类对应的评估得分。可以看到此时式子已经和Softmax的损失函数一致了。

4.2 概率层面解释

前面说到 Softmax 分类器首先将评估得分转变为一个概率分布，也就是说我们可以把整个模型当做一个以 $x_i$ 和 $W$ 作为参数的概率分布，即：

由于 $x_i$ 为输入值是不变的，所以模型训练的本质其实也就等价于，确定一个 $W$ 使得 $y_i$ 发生的概率最大，这里的 $y_i$ 表示为输入样本对应的真实种类，所以就转换成了一个极大似然估计（MLE）的问题。由于原始的似然函数是一个连乘的形式，所以加上一个log变成对数似然函数（加上log不会改变极值点的位置，只会改变极值的大小，而我们主要求得位置即可，不关心值的大小，所以没有影响），转变为一个连加的形式方便计算，其最终的表达式也和softmax的损失函数等价。同时，我们可以对正则项 $R(W)=\sum_{k} \sum_{l} W_{k, l}^{2}$ 给出一定解释：实际上，加上这个正则项等价于加入权重的先验概率，使得极大似然估计变成最大后验估计，这里假设权重是服从一个均值为0的高斯先验分布的。

4.3 代码实现

在代码实现的过程中需要注意的是，由于涉及指数运算，所以分子和分母的数据可能会很大，对于两个很大的数字做除法可能会导致精度问题。通常，在实现的过程中，我们使用下面的技巧：

这里的 $C$ 是有我们自己选取的，一般我们设置为 $logC = -max_jf_j$ ，即取评估得分最大值，这样可以使得整体的数据变小的同时不影响结果。代码如下：

f = np.array([123, 456, 789]) # example with 3 classes and each having large scores
p = np.exp(f) / np.sum(np.exp(f)) # Bad: Numeric problem, potential blowup

# instead: first shift the values of f so that the highest number is 0:
f -= np.max(f) # f becomes [-666, -333, 0]
p = np.exp(f) / np.sum(np.exp(f)) # safe to do, gives the correct answer

5. SVM和Softmax对比

上图展示了SVM和Softmax的区别，对于一个输入的数据，两个分类器首先都是计算相同的得分 $f$，但是两者对于得分 $f$ 的解释不同。对于SVM分类器，它将 $f$ 就当做类别的得分，所以它的损失函数时希望正确类别的得分比其他类别高出一个间隔的差距。而Softmax分类器则将 $f$ 处理成对数概率，其损失函数希望归一化后的真实类别的概率尽可能地大（可以从交叉熵和极大似然估计的角度分别理解）。从上图中可以看出SVM的损失值为1.58，Softmax的交叉熵损失为1.04，但这两者是没有可比性的，对于一个损失函数的值只能和相同的损失函数进行比较。

SVM和Softmax的性能差距很小，不过还是有一些差异的。相比于Softmax，SVM更佳，这可以看做是SVM的缺陷也可以看做是SVM的特点，比如说某个样本的预测得分为 $[10,-2,3]$ ，假设第一个类别是其真实类别，并且SVM 的 $\Delta = 1$ ，那么很显然这个预测得分的损失为0。SVM是不关注某个种类的具体得分的，比如说如果预测得分分别为 $[10,-100,-100] \ [10,9,9]$ ，在 $\Delta = 1$ 的情况下，损失值都为0。所以，只要满足真实种类的评估得分比其余都大一个规定的间隔，那么SVM会无视具体的差异的，但是对于Softmax则不同，在Softmax分类器中，$[10,-100,-100]$ 的损失值肯定比 $\ [10,9,9]$ 小，换句话说，Softmax希望的是真实种类的概率尽量大，而其他的尽量小。但是在某种情况下，这也不一定就是SVM的缺陷，比如说某个汽车分类器专注于对卡车和汽车的分类，那么模型的预测得分不应该受到其他种类比如青蛙的影响，只要青蛙的得分保证一定程度地低就够了。