SVM and Softmax

文章目录

斯坦福大学李飞飞团队的公开课CS231n- Convolutional Neural Networks for Visual Recognition, 这篇文章介绍了课程笔记中的线性模型,SVMSoftmax的基本原理, 对应的assignment1中的代码实现见Github

线性模型

  • 基本概念
  1. 评分函数score function : 本质上就是训练得到的线性模型, 输出值为在每个类别上的评分, 最终选择最高分达到分类目的

  2. 误差函数loss function或者代价函数cost function或者目标函数Objective : 衡量模型预测值与真实值之间的差距, 差距越大代价越大, 从而对模型参数优化起到指引作用

  • 评分函数

$$ f(x_i, W, b) = W x_i + b $$

  • 显然上面是一个线性模型, 如果不够了解请看 从线性模型到神经网络 这篇文章

  • 线性模型根据训练数据集去确定$W$和$b$, 一旦训练完成, 模型就确定了, 我们只保留参数就可以了, 对于测试集来说, 通过确定的模型就可以算出得分, 从而得到类别, 与kNN相比不需要和训练集一一比较

  • 如图所示, 假如我们通过训练数据确定了模型的参数$W$和$b$, 我们有一张新的图片$x_i$需要分类, 这样我们通过模型计算评分得到分类结果, 当然图中把猫分类为狗了, 这时就需要误差函数来对模型的相关参数进行迭代优化, 最终使得模型正确分类

  • 图中的线性模型的评分就是一个加权求和, 对于参数$W$的理解, 我们通过训练数据确定的$W$是包含同一类图片的特征信息的, 每行参数代表一类分类器 比如对船舶的分类, 有可能对于蓝色通道内的值的权重就比较大, 最后的到的评分也就比较高

  • 图片是一种高维特征的数据类型 : 我们将一张图片为3通道的数组变换为一个1通道的列向量, 比如在CIFAR-10数据集中, 每个样本是32x32x3像素的, 变换之后是一个3072维的列向量, 我们可以想象这是一个3072维的超几何空间, 然后将这个空间分为10份, 虽然我们无法可视化高维空间, 但是假如我们想象将高维空间压扁成二维的, 我们就可以理解线性模型在干什么, 如图所示

  • 图中的箭头表示正样本评分增长的方向, 显然这些分类边界的方向是由参数集$W$决定的

  • 对于偏置项$b$的理解, 偏置项$b$使得决策变边界更加灵活, 如果没有偏置项那么所有决策边界都将过原点

关于$W$的另一种理解

我们可以将$W$的每一行理解为某一类的一个模板(也叫原型), 对于一张图片的评分, 可以看作是参数矩阵的每一行分别和这个图像做內积运算, 我们知道内既可以用来计算相关程度, 相关性程度越大则內积越大, 评分也就越高, 这样我们就可以找到与原型最相似的类别了; 这就相当于我们拿新的样本数据在和每一类的原型(可以理解为这一类的通用模板)在做KNN, 只是我们把距离换成了內积来评价相似程度, 如图所示

  • 比如在上图中, 正如我们所想, 船舶模板中包含了大量的蓝色像素, 这个模板在和海洋中船舶的图像做内积运算时, 评分就很高。

  • 马模板中有两个方向的头, 这样的话无论样本数据是朝哪个方向, 评分都会很高

编码中的偏置项处理

  • 如图所示, 在处理偏置项的时候, 通常将$W$和$b$合并为一个参数矩阵, 因为跟踪两个参数集使得程序过于笨重, 那么在$x_i$的维数就会增加一维, 在$CIFAR-10$数据集中, 样本$x_i$从3072 x 1 变为 3073 x 1 , $W$从10 x 3072 变为10 x 3073

编码中的数据预处理

  • 数据归一化 : 由于每个像素值在[0,255]之间, 我们将其归一化到[-1,1]之间, 数据中心化的作用在 梯度下降法 里介绍

SVM : 支持向量机

最基本的支持向量机是一种二分类模型, 其基本思想是找到在特征空间上的间隔最大的决策边界, 如下图所示

  • 其实可以理解为逻辑回归的基础上找到最优的决策边界, 该决策边界具有间隔最大化的特征, 因为用逻辑回归训练出来的决策边界可能有多种选择, 间隔最大化的边界鲁棒性最强

如何做到间隔最大化呢? 首先看一下SVM的惩罚函数Hinge Loss

  • $Hinge Loss$的定义

$$ Hinge loss(x_i)= max(0, 1 - y_i w^Tx_i)$$

  • 利用$Hinge loss(x)$构造的二分类SVM代价函数

$$ L_i = C max(0, 1 - y_i w^Tx_i) + R(W) $$

  • $C$是超参数, $C propto frac{1}{lambda}$, 其作用和$lambda$一样, 后续介绍

  • $y_i in { -1,1 }$

由二分类的SVM代价函数构造多分类的代价函数, 为了方便表示, 令$s=f(x_i, W)_{y_i}-f(x_i, W)_j$, 惩罚函数$ Cost(x_i) $可被定义为:

$$
Cost(x_i) =
begin{cases}
-s+Delta, & text{if $s=f(x_i, W)_{y_i}-f(x_i, W)_j< Delta$ } \[2ex]
0, & text{if $s=f(x_i, W)_{y_i}-f(x_i, W)_j> Delta$ }
end{cases}
$$

$$ =max(0, f(x_i, W)_j-f(x_i, W)_{y_i} + Delta) $$

$$ =max(0, s_j - s_{y_i} + Delta) $$

$$ =max(0, s + Delta) $$

  • 多分类SVM代价函数的定义

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

$$ = sum_{jneq y_i} max(0, w_j^T x_i - w_{y_i}^T x_i + Delta) $$

其中,

  • $s_j = f(x_i, W)_j$代表模型预测的其他类别的评分值, 即除最大值以外的所有类别对应的评分值

  • $ s_{y_i}=y_i $代表模型输出的对应类别评分值, 即在评分向量中的最大值

  • 注意:$j = y_i$其实相等也没关系, 二者相等的时候只是$L_i$增加了一个$Delta$的常数

  • $W_j$指的是, 在$W$矩阵中第$j$类所代表的线性函数的参数

$Delta$的作用

正是由于$Delta$的存在才使得SVM模型可以做到间隔最大化, 为什么这么说呢, 其实当我们判定$y_i-f(x_i, W)> 0$时, 就可以判断模型预测结果是正确的, 但是我们要求$y_i-f(x_i, W)> Delta$时才行, 那么就相当于在SVM模型中添加了一个安全因子, 而这个安全因子将十分靠近决策边界的某些干扰点过滤掉了, 从而产生了最大间隔, 数学上的解释参考吴恩达课程中的Mathematics Behind Large Margin Classification一节

  • 正如图中所示, SVM在做多分类任务时, 该模型希望正确类型的评分至少要比其他类别的评分大$Delta$, 只要其他类的某一评分在红色区间内那么就会产生代价, 反之代价为0, 我们的模型会在这种条件限制下通过训练集来确定模型参数$W$, 这样得到最优模型其决策边界就会产生最大间隔
  • 由图可知, 通过核函数将数据样本从低维空间映射到高维空间, 在低维空间的线性不可分问题在高维空间中就可以找到决策边界了, 当然这个决策边界是(超)平面

正则化

在构造代价函数的时候, 我们常常加入正则惩罚, 在 从线性模型到神经网络 这篇文章中也简单介绍过, 为什么要这样做呢? 假设模型都能够正确地分类, 那么我们训练得到的参数矩阵$W$并不唯一, 我们要选择泛化性能比较好的$W$, 那么就需要给SVM的代价函数引入正则惩罚,

$$ R(W) = sum_ksum_l W_{k,l}^2 $$

  • 上式代表参数矩阵$W$中所有参数的平方和

添加正则项后的SVM损失函数 :

$$ L = underbrace{ frac{1}{N} sum_i L_i }_text{data loss} + underbrace{ lambda R(W) }_text{regularization loss} $$

$$ = frac{1}{N} sum_i sum_{jneq y_i} left[ max(0, f(x_i; W)_j - f(x_i; W)_{y_i} + Delta) right] + lambda sum_ksum_l W_{k,l}^2 $$

  • 数据损失(data loss)正则损失(regularization loss)共同组成

  • $lambda$代表正则惩罚强度

$lambda$和$Delta$在损失函数中控制着数据损失和正则化损失之间的权衡

我们来看一个简单的例子, 假设有一个 $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$ 都等于一, 但是$w_1$的正则惩罚为1, $w_2$的正则惩罚为0.25, 根据正则惩罚值来看, $w_2$更小模型也就更好, 因为$w_2$的参数更小更分散, 也就是说引入正则惩罚之后, 模型的参数更加趋向于更小更分散的参数矩阵, 可以这样理解, 这种矩阵可以考虑到所有维度上的特征值, 相反对于$w_1$来说, 后面三个特征形同虚设, 这样SVM模型就会有最大边界这一良好的性质, 会提高模型的泛化能力, 且避免过拟合

  • 在基础的SVM模型中, 添加核函数做非线性映射, 得到的SVM模型本质上是一种非线性分类器

Softmax

对于Softmax分类器, 我们在 从线性模型到神经网络的逻辑回归部分提到过, 但是没有扩展, 在这里我们好好学习一下, 我们可以理解为利用逻辑回归做多分类任务, 但是我们知道逻辑回归是二分类器, 那么Softmax是怎么做到的呢?

  • Softmax思想: 将每一种类别作为一类, 其他类作为一类, 然后对每一类进行二分类操作, 然后计算每一类基于其他类的概率, 得到在每一类上的分类概率, 选择最大类别输出, 这样就实现了多分类任务

  • Softmax基础

在Softmax模型中, 评分函数$f(x_i; W) = W x_i$保持不变, 但是在代价函数的构造方面, 不同于SVM的Hinge Loss, Softmax采用了交叉熵损失(cross-entropy loss), 正则项也保持与SVM一样,

$$ L_i = -logleft(frac{e^{f_{y_i}}}{ sum_j e^{f_j} }right) $$

$$= -f_{y_i} + logsum_j e^{f_j} $$

式中,

  • $f_j$代表评分向量的中的第$j$个元素

$$f_j(z) = frac{e^{z_j}}{sum_k e^{z_k}}$$

叫做Softmax函数

  • $z$是一个评分向量, $z_k$代表评分向量中第$k$个元素

  • 通过Softmax函数, 我们将评分向量$z$中的每个元素映射到了(0,1)之间, 并且输出的向量$f_z$的所有元素之和为1, 其实可以理解为该样本$x_i$在每一个类别上的概率

实现TODO

  • 数值的稳定性: 由于在计算Softmax函数是存在指数运算导致结果很大, 除以一个非常大的值使得运算不稳定, 所以使用归一化技巧十分重要

$$frac{e^{f_{y_i}}}{sum_j e^{f_j}}
= frac{Ce^{f_{y_i}}}{Csum_j e^{f_j}}
= frac{e^{f_{y_i} + log C}}{sum_j e^{f_j + log C}}$$

  • 在分子和分母同时乘以一个常数项$C$, $C$的取值没有限制, 但是为了限制指数项的不能过大, 通常$log C = -max f_j$, 也就是说将向量$f$中的数值进行平移,使得最大值为0, 这样指数运算的结果就在(0,1)之间了

SVM和Softmax的比较

首先, 单纯的比较两个模型代价函数的值毫无意义, 我们比较一下两种损失函数的构建思想:

  1. 对于SVM, 如果分数是[10, -100, -100]或者[10, 9, 9],对于SVM来说没设么不同,只要满足超过边界值等于1,那么损失值就等于0

  2. 对于softmax分类器,情况则不同。对于[10, 9, 9]来说,计算出的损失值就远远高于[10, -100, -100]的损失值, softmax分类器对于分数是永远不会满意的: 正确分类总能得到更高的可能性, 错误分类总能得到更低的可能性, 损失值总是能够更小, 然而SVM只要边界值被满足了就可以了, 不会超过限制去细微地操作具体分数

通过损失函数的计算, SVM将模型输出理解为分类评分, Softmax将模型输出理解为该类别的概率, 但是注意这种概率是受正则化参数$lambda$影响的, $lambda$影响概率的离散程度, 举个例子

  • $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 $增大, 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$趋于无穷大的时候, Softmax输出趋于均匀分布, 所以不能将Softmax的结果看作为真正的概率, 最好是看成一种对于分类正确的自信