【机器学习】1. 线性分类和SVM

HappinessSourceL 2019-06-27

线性分类

线性分类器的原理可以扩展到神经网络甚至是卷积神经网络,因此了解线性分类器是学习后者的基础。线性分类的方法包含2个重要的组成部分:score function和loss function。

符号约定

  • 训练样本$x_i$为D维向量,每一个维度是一个特征值。对于图像来说,每个像素的RGB通道都是特征,比如对于32 x 32 的RGB图像来说,总共有32 x 32 x 3个特征。
  • $i \in { 1 \dots N }$,也就是总共有N个训练样本(也就是说有N张图片用于训练)。
  • $y_i$表示训练样本$x_i$的真实类(ground truth label),$y_i \in { 1 \dots K }$,也就是说总共有K类。

score function

score function将输入$x_i$映射为$x_i$在每一类上的得分:$$f: R^D \mapsto R^K$$
线性分类器的score function就是以下线性函数:
$$f(x_i, W, b) = W x_i + b$$
其中W([K x D]矩阵)和b([K x 1]向量)统称为score function的参数(parameters)。

函数输出是一个K x 1的向量,其中第k项表示$x_i$在第k类的得分。分数越高,表示$x_i$更有可能是这一类。
【机器学习】1. 线性分类和SVM
W和b的第i行决定了第i类的分数,因此W和b的第i行被称为第i类的分类器(classifier)。

为了表示方便,常常为x增加一个维度,这个维度上的值为1,这个时候就可以将b作为W的列向量了:
$$f(x_i, W) = W x_i$$
【机器学习】1. 线性分类和SVM

score function的解释

既然$x_i$是一个D维向量(每一个维度是一个特征),那么我们可以将它看作是D维空间(样本空间)上的一个点。
比如,CIFAR-10训练集中的图像都是32 x 32像素的,因此每个图像拥有的特征数量是32 x 32 x 3 = 3072(每个像素有RGB3个通道的颜色值),每个图片样本就是在3072维中的一个点。这个3072维空间称为样本空间。
根据前面的score function,我们可以推导出计算$x_i$在第k类的得分的公式(也就是第k类的classifier):
$$f_{k} = W_{k1}*x_1+W_{k2}*x_2+...+W_{kn}*x_n+b_k$$

如果我们尝试将这个D维空间(样本空间)画出来:
【机器学习】1. 线性分类和SVM
这张图说明了classifier是如何做分类的:
对于每个classifier,都有一条直线(准确地说是决策边界Decision Boundary)$$f_{k}=W_{k1}*x_1+W_{k2}*x_2+...+W_{kn}*x_n+b_k=0$$(第k类得分等于0的所有点),其中W已经通过训练得到,也就是说这条直线通过训练的到。箭头方向指向$f_{k}$增大的方向。通过这张图,我们能清楚地看出哪些样本在car classifier上的得分大于0,哪些小于0。

训练的含义

对于给定的训练集$$(x_i, y_i), i \in { 1 \dots N }$$,训练出合适的参数W和b(W和b是训练的产物),使得分类器的预测结果尽可能接近于真实类(真实类的得分越高越好,其他类的得分越低越好)。我们用loss function来衡量参数的好坏,训练的过程就是通过调整参数来减小loss的过程。至于要如何调整参数(才能使得loss减小),这属于优化问题(Optimization),常见的优化方法有梯度下降。

用前面D维空间的图来解释,训练就是为每个类寻找一个决策边界,决策边界能将属于这类的样本分到界限的一边(得分大于0),其它样本分到界限的另一边(得分小于0)。

loss function

有时也被称为cost function或the objective。
用于衡量模型(W和b)在输入集上的预测结果与真实标签的拟合程度。“预测更准确”等价于“loss更小”。

有2种loss function比较重要:Multiclass SVM loss和Softmax classifier loss。这篇文章我们专注于Multiclass SVM loss。softmax分类器在另一篇文章讨论。

Multiclass SVM loss

Multiclass SVM loss “期望”正确类的得分比非正确类的得分高$\Delta$ (delta)以上,如果分数没有高出那么多,那么缺少的分数就会累加到loss中。
$$L_i = \sum_{j\neq y_i} \max(0, s_j - s_{y_i} + \Delta)$$
$s_{y_i}$表示$x_i$在正确类的分数,$s_j$表示$x_i$在第j类的分数,$L_i$就是样本$x_i$的SVM loss。这种用$max(0,-)$来计算损失的方法叫做折叶损失(hinge loss)

【机器学习】1. 线性分类和SVM
如上图所示,Multiclass SVM loss希望正确类的分数比所有其他类分数至少高$\Delta$。如果有其他类的得分在红线区域(或更高),那么缺少的分数会累加到loss中;如果没有其他类得分在红线区域,loss就为0。

注意这个公式只计算模型在样本$x_i$上的loss。后面我们会累加它们得到完整的loss。

将线性分类器计算分数的公式(score function)代入loss function,得到:
$$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行的行向量,因此$w_j^T x_i$就是分数$s_j$(转置是为了将向量转化为1 x D矩阵)。

注意SVM loss不止适用于线性分类器,如果是其他分类器的话,带入对应的score function就好了。

完整的Multiclass SVM loss由以下公式给出:
$$L = \underbrace{ \frac{1}{N} \sum_i L_i } + \underbrace{ \lambda R(W) }$$
左边的部分是data loss,右边的部分是regularization loss(正则化惩罚):$$R(W) = \sum_k\sum_l W_{k,l}^2$$。
data loss和regularization loss分别体现了loss function的两个目标:

  1. data loss体现了loss function希望模型能够更准确地对数据进行分类。
  2. regularization loss体现了loss function倾向于更简单的模型,不希望模型通过复杂的蜿蜒曲折来强行将两类分开。正则化项让loss function倾向于权重更小、更分散的模型(更倾向于 w2=[0.25,0.25,0.25,0.25] 而不是 w1=[1,0,0,0]),增强模型的泛化能力,防止过拟合,可以看看知乎讨论:机器学习中常常提到的正则化到底是什么意思吴恩达机器学习课时51也很好地讲解了正则化的作用。

将$L_i$和$R(W)$的公式代入$L$可以得到完整的Multiclass SVM loss:
$$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$$

Delta和lambda

实际中我们常常将$\Delta$取值为1。
要理解为什么,需要考虑W的尺度和$\Delta$之间的关系:因为将W每个元素放大或缩小任意倍数,分数也会放大或缩小相同倍数,分数之间的差值也会放大或缩小相同倍数;因此,只要W能任意放大缩小,那么限制分数之间的差值为某个具体的值是无意义的,因为这个要求总能通过缩放W达到。
因此,$\Delta$和$\lambda$的作用是重复的:它们都控制data loss与regularization loss之间的权衡。如果$\Delta$增大,训练模型时会倾向于增加W的尺度来防止data loss过大,这个时候受罪的是regularization loss;如果$\lambda$变大,训练模型时会倾向于减小W的尺度来防止regularization loss过大,这个时候受罪的是data loss。

与二元分类SVM(Binary Support Vector Machine)的关系

Multiclass SVM在只有两类的时候也可以直接使用,但是在二分类问题中,更常见的是Binary Support Vector Machine,它是Multiclass SVM用于二分类的改写形式。它对$x_i$计算loss的公式如下:
$$L_i = C \max(0, 1 - y_i w^Tx_i) + R(W)$$
其中$y_i \in \{ -1,1 \}$,本别表示负类和正类。

Binary SVM的W是一个向量,而不是矩阵。Binary SVM的score function:$w^Tx_i$。如果$w^Tx_i>0$,那么预测为正类,否则预测为负类。$w^Tx_i$越大,预测正类的把握越大。

Binary SVM的loss function的含义:
如果样本$x_i$实际上是正类,那么Binary SVM期望分数$w^Tx_i$大于1(否则缺少的分数累加到loss);如果样本实际上是负类,那么Binary SVM期望分数$w^Tx_i$小于-1(否则多出的分数累加到loss)。

Binary SVM和前面的Multiclass SVM本质上是相同的,Binary SVM实际上只是Multiclass SVM的改写形式。我们可以从Multiclass SVM的loss function推导出Binary SVM的loss function:
Binary SVM的score function:正类分数是$w^Tx_i$,负类分数是$-w^Tx_i$。类分数越高,表示预测这一类的把握越大。

Multiclass SVM对每一类都分别有一个分类器(W的一个行向量)用来计算这一类的分数;而Binary SVM只用一个分类器(一个向量w)来得到正类和负类的分数。

用这个score function带入前面多类SVM的loss function,得到
$L_i = \sum_{j\neq y_i} \max(0, w^Tx_i - (-w^Tx_i) + \Delta)$,(当$x_i$标签为负类)
$L_i = \sum_{j\neq y_i} \max(0, -w^Tx_i - w^Tx_i + \Delta)$,(当$x_i$标签为正类)
这两种情况可以归结为:
$L_i = \sum_{j\neq y_i} \max(0, -y_iw^Tx_i + \Delta)$,$y_i \in \{ -1,1 \}$表示标签
令$\Delta=1$,就得到了Binary SVM的loss function。
Binary SVM loss中的系数$C$的作用等价于Multiclass SVM中的$\lambda$,它们都控制着data loss与regularization loss之间的权重比例。
至于Binary SVM loss中的$R(W)$,当我们累加所有样本的$L_i$以后,$R(W)$累加为$NR(W)$,N是输入样本的数量,为已知常数。常数N并没有什么影响,因为$C$会控制好data loss与regularization loss之间的权重比例。


欢迎提出建议或者指出错误!

参考资料

cs231n notes
cs231n 翻译
cs229 notes(有更详细的数学推导)

相关推荐