Lecture_linear classification

课程链接

线性分类器

图像空间的示意图,其中每个图像是一个点,且有3个分类器.以红色的汽车分类器为例，红线表示空间中汽车分类分数为0的点的集合，红色的箭头表示分值上升的方向。所有红线右边的点的分数值均为正，且线性升高。红线左边的点分值为负，且线性降低. Interactive web demo

评分函数 Score function

线性映射

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

W(Weights 权重) : [K*D] (W的每一行为对应一个分类的模板("原型")) 如果改变其中一行的数字，会看见分类器在空间中对应的直线开始向着不同方向旋转.
x_i(输入数据) : [D*1]
b(bias vector 偏差向量) : [K*1] 允许分类器对应的直线平移.如果没有偏差,无论权重如何,在x_i=0时分类分值始终为0.这样所有分类器的线都不得不穿过原点.

该函数的输出值为对应各类别的score
我们的目的就是找到最优化的参数W、b,即为每一个分类找到最好的模板.
评分函数在正确的分类的位置应当得到最高的评分（score）

偏差和权重的合并Bias trick

image

f(x_i,W,b)=Wx_i+b\rightarrow f(x_i,W) = Wx_i

其中，W[K*D]→W[K*(D+1)], x_i[D,1] → x_i[(D+1),1]

将线性分类器看作模板匹配

Interpretation of linear classifiers as template matching

W的每一行为对应一个分类的模板("原型").注意，船的模板如期望的那样有很多蓝色像素。如果图像是一艘船行驶在大海上，那么这个模板利用内积计算图像将给出很高的分数。

图像数据预处理 Image data preprocessing

对于输入的特征做归一化（normalization）处理
- 对每个特征减去平均值来中心化数据
- 归一. 区间变为[-1,1]

损失函数 Loss function

我们将使用损失函数（Loss Function）（有时也叫代价函数Cost Function或目标函数Objective）来衡量我们对结果的不满意程度。直观地讲，当评分函数输出结果与真实结果之间差异越大，损失函数输出越大，反之越小。，对训练集中数据做出准确分类预测和让损失值最小化这两件事是等价的。

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

image

SVM的损失函数想要SVM在正确分类上的得分始终比不正确分类上的得分高,且至少高出一个边界值delta.如果其他分类分数进入了红色的区域，甚至更高，那么就开始计算损失。如果没有这些情况，损失值为0。我们的目标是找到一些权重，它们既能够让训练集中的数据样例满足这些限制，也能让总的损失值尽可能地低。

Hinge Loss

针对第i个数据的多类SVM的损失函数定义：

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

Data Loss

[图片上传失败...(image-17ebe6-1540026207071)]
$L = { \frac{1}{N} \sum_i L_i }$

正则化 Regularization

防止过拟合：向损失函数增加一个正则化惩罚（regularization penalty） R(W)部分，使其不能完全匹配训练集.
最常用的正则化惩罚是L2范式，L2范式通过对所有参数进行逐元素的平方惩罚来抑制大数值的权重.对大数值权重进行惩罚，可以提升其泛化能力，因为这就意味着没有哪个维度能够独自对于整体分值有过大的影响.
$R(W) = \sum_k\sum_l W_{k,l}^2$

需要注意的是，和权重不同，偏差没有这样的效果，因为它们并不控制输入维度上的影响强度。因此通常只对权重 $W$ 正则化，而不正则化偏差 $b$ 。因为正则化惩罚的存在，不可能在所有的例子中得到0的损失值，这是因为只有当 $W=0$ 的特殊情况下，才能得到损失值为0

完整的多类SVM损失函数

$L = \underbrace{ \frac{1}{N} \sum_i L_i }_\text{data loss} + \underbrace{ \lambda R(W) }_\text{regularization 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$

对于每一个输入数据 $x_i$ 都有一个L值

设置超参 $\Delta$ 和λ

超参数 $\Delta$ 和λ失函数中的数据损失和正则化损失之间的权衡。理解这一点的关键是要知道，权重W的大小对于分类分值有直接影响（当然对他们的差异也有直接影响）：当我们将W中值缩小，分类分值之间的差异也变小，反之亦然。因此，不同分类分值之间的边界的具体值（比如 $\Delta$ =1或 $\Delta$ =100).从某些角度来看是没意义的，因为权重自己就可以控制差异变大和缩小。也就是说，真正的权衡是我们允许权重能够变大到何种程度（通过正则化强度λ来控制）

Softmax分类器

与SVM不同，Softmax的输出（归一化的分类概率）更加直观，并且从概率上可以解释。在Softmax分类器中，函数映射 $f(x_i;W)=Wx_i$ 保持不变，但将这些评分值视为每个分类的未归一化的对数概率，并且将折叶损失（hinge loss）替换为交叉熵损失（cross-entropy loss）

公式如下： $\displaystyle Li=-log(\frac{e^{f_{y_i}}}{\sum_je^{f_j}})$ 或等价于 $L_i=-f_{y_i}+log(\sum_je^{f_j})$

softmax函数

函数 $f_j(z)=\frac{e^{z_j}}{\sum_ke^{z_k}}$ 被称作softmax 函数.函数对输入向量z(score值)进行压缩，输出一个向量，其中每个元素值在0到1之间，且所有元素之和为1.
$P(y_i|x_i,W)=\frac{e^{f_{y_i}}}{\sum_je^{f_j}}$
可以解释为是给定图像数据 $x_i$ ，以 $W$ 为参数，分配给正确分类标签 $y_i$ 的归一化概率。从概率论的角度来理解，我们就是在最小化正确分类的负对数概率(令正确分类的概率尽趋近于1，即令错误分类的概率均趋近于0)，这可以看做是在进行最大似然估计（MLE）。

交叉熵

在“真实”分布(未知) $p$ 和估计分布(样本分布) $q$ 之间的交叉熵定义： $\displaystyle H(p,q)=-\sum_xp(x) logq(x)$

交叉熵损失函数“想要”预测分布的所有概率密度都在正确分类上,让预测分布与真实分布保持一致。Softmax分类器所做的就是最小化在估计分类概率（就是上面的 $e^{f_{y_i}}/\sum_je^{f_j}$ ）和“真实”分布之间的交叉熵，在这个解释中，“真实”分布就是所有概率密度都分布在正确的类别上（比如： $p=[0,...1,...,0]$ 中在 $y_i$ 的位置就有一个单独的1）

SVM和Softmax的比较

image

针对一个数据点，SVM和Softmax分类器的不同处理方式的例子。两个分类器都计算了同样的分值向量f（本节中是通过矩阵乘来实现）。不同之处在于对f中分值的解释：

SVM分类器将它们看做是分类评分，它的损失函数鼓励正确的分类（本例中是蓝色的类别2）的分值比其他分类的分值高出至少一个边界值。SVM的最终的损失值是1.58。

Softmax分类器将这些数值看做是每个分类没有归一化的对数概率，鼓励正确分类的归一化的对数概率变高，其余的变低。Softmax的最终的损失值是0.452。但要注意SVM和Softmax的最终损失值(1.58和0.452)两个数值没有可比性。只在给定同样数据，在同样的分类器的损失值计算中，它们才有意义。

Softmax分类器为每个分类提供了“可能性”：可能性分布的集中或离散程度是由正则化参数λ直接决定的，λ是你能直接控制的一个输入参数。随着正则化参数λ不断增强，权重数值会越来越小，最后输出的概率会接近于均匀分布。这就是说，softmax分类器算出来的概率最好是看成一种对于分类正确性的置信水平。

在实际使用中，SVM和Softmax经常是相似的：通常说来，两种分类器的表现差别很小，不同的人对于哪个分类器更好有不同的看法。

SVM更加“局部目标化（local objective）”.SVM对于数字个体的细节是不关心的：如果分数是[10, -100, -100]或者[10, 9, 9]，对于SVM( $\Delta$ =1)来说没什么不同，只要满足超过边界值等于1，那么损失值就等于0。SVM只要边界值被满足了就满意了，不会超过限制去细微地操作具体分数。举例说来，一个汽车的分类器应该把他的大量精力放在如何分辨小轿车和大卡车上，而不应该纠结于如何与青蛙进行区分，因为区分青蛙得到的评分已经足够低了。

softmax分类器对于分数是永远不会满意的：正确分类总能得到更高的可能性，错误分类总能得到更低的可能性，损失值总是能够更小。

小结

定义了从图像像素映射到不同类别的分类评分的评分函数。在本节中，评分函数是一个基于权重W和偏差b的线性函数。
与kNN分类器不同，参数方法的优势在于一旦通过训练学习到了参数，就可以将训练数据丢弃了。同时该方法对于新的测试数据的预测非常快，因为只需要与权重W进行一个矩阵乘法运算。
介绍了偏差技巧，让我们能够将偏差向量和权重矩阵合二为一，然后就可以只跟踪一个矩阵。
定义了损失函数（介绍了SVM和Softmax线性分类器最常用的2个损失函数）。损失函数能够衡量给出的参数集与训练集数据真实类别情况之间的一致性。在损失函数的定义中可以看到，对训练集数据做出良好预测与得到一个足够低的损失值这两件事是等价的。

现在我们知道了如何基于参数，将数据集中的图像映射成为分类的评分，也知道了两种不同的损失函数，它们都能用来衡量算法分类预测的质量。但是，如何高效地得到能够使损失值最小的参数呢？这个求得最优参数的过程被称为最优化，将在下节课中进行介绍。

参考：cs231n assignment1 svm