第7周

---

十三、支持向量机(Support Vector Machines）

13.1感知机与支持向量机

感知机是二分类的线性分类模型，旨在求出将数据线性划分的分离超平面，利用梯度下降法对损失函数极小化。

支持向量机是定义在特征空间上的间隔最大的的线性分类器，间隔最大使它有别于感知机，还包括核技巧，通过把数据映射到更高维度来进行分类，使得它可以解决非线性问题。

支持向量机包括：线性可分支持向量机，线性支持向量机，非线性支持向量机。

对于线性可分支持向量机，通过硬间隔最大化学习线性分类器。

对于近似线性支持向量机，通过软间隔最大化学习线性分类器。

对于非线性支持向量机，通过核技巧在高维特征空间进行分类。

13.2函数间隔与几何间隔

在分离超平面固定为$w^{T}x+b=0$的时候，$|w^{T}x+b|$表示点$x$到超平面的相对距离。通过观察$w^{T}x+b$和$y$（$y$取1或-1）是否同号，判断分类是否正确，因此定义函数间隔为${\gamma }^{{}^{\prime }}=y(w^{T}x+b)$.

如果$w,b$都变为原来的两倍，超平面没有发生变化，但是函数间隔变为两倍，因此定义几何间隔：$\gamma =\frac{y(w^{T}x+b)}{||w|{|}_2}=\frac{{\gamma }^{{}^{\prime }}}{||w|{|}_2}$

几何间隔才是点到超平面的真正间隔。

13.3 支持向量

在线性可分的情况下，经过分离超平面最近的样本点，且与分离超平面平行的向量称为支持向量，也称作决策边界。

13.4 间隔最大化的直观理解

如果数据集是线性可分的，即存在一条直线把正负样本分开。当然有多条不同的直线可以把正样本和负样本完全分开，这些直线都可以作为决策边界。

但是有些决策边界看起来都不是特别好的选择，支持向量机将会选择黑色的决策边界，相较于粉色或者绿色画的决策界，黑线看起来是更稳健的决策界。在分离正样本和负样本上它显得的更好。数学上来讲，这条黑线距离样本点有更大的距离，这个距离叫做间距(margin)。

当画出这两条额外的蓝线，可以看到黑色的决策界和训练样本之间有更大的最短距离。然而粉线和蓝线离训练样本就非常近，在分离样本的时候就会比黑线表现差。因此，这个距离叫做支持向量机的间距，而这是支持向量机具有鲁棒性（可以分开最难分的点）的原因，因为它努力用一个最大间距来分离样本。因此支持向量机有时被称为最大间距分类器。

并且支持向量很少，所以支持向量机由很少的“重要的”样本确定，使得支持向量机能很好地应用于小样本数据。

事实上，支持向量机现在要比这个大间距分类器所体现得更成熟，尤其是当学习算法会受异常点(outlier) 的影响。比如我们加入一个额外的正样本。

在这里，为了将样本用最大间距分开，也许最终会得到粉色的线，仅仅因为一个异常值，就将决策界从这条黑线变到这条粉线，这显然是不明智的。事实上，如果正则化参数设置的非常大，支持向量机会把决策界从黑线变到粉线，但如果将正则化参数设置的小一点，最终还是会得到黑线，此时为软间隔最大化。实际上应用支持向量机的时候，**当参数不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。**甚至数据不是线性可分的时候，支持向量机也可以给出好的结果。

13.5 大边界分类背后的数学

支持向量机是最大化间隔，所有目标函数为：

$max\gamma =\frac{y(w^{T}x+b)}{||w|{|}_2}s.t{y}_i(w^T{x}_i+b)={\gamma }^{{}^{\prime }(i)}\ge {\gamma }^{{}^{\prime }}(i=1,2,...m)$

一般，我们让函数间隔为1，所以分子为1：

$max\frac{1}{||w|{|}_2}s.t{y}_i(w^T{x}_i+b)\ge 1(i=1,2,...m)$

由于$\frac{1}{||w|{|}_2}$的最大化等同于$\frac{1}{2}||w|{|}_2^2$的最小化。这样SVM的优化函数等价于：

为了简化，仅仅是为了让目标函数更容易被分析。

接下来忽略掉截距，令${\theta }_0=0$。将特征数$n$置为2，因此仅有两个特征$x_1,x_2$，目标函数可以写作：$\frac{1}{2}\left({\theta }_1^2+{\theta }_2^2\right)=\frac{1}{2}{\left(\sqrt{{\theta }_1^2+{\theta }_2^2}\right)}^2$

因此支持向量机做的全部事情，就是极小化参数向量$\theta$范数的平方，或者说长度的平方。

现在我将要看看这些项：${\theta }^{T}x$更深入地理解它们的含义。给定参数向量$\theta $给定一个样本$x$

考察一个单一的训练样本，用一个叉来表示正样本$x^{(i)}$，意思是在水平轴上取值为$x_1^{(i)}$，在竖直轴上取值为$x_2^{(i)}$。将${\theta }_1$画在横轴，将${\theta }_2$ 画在纵轴，那么内积${\theta }^T{x}^{(i)}$ 将会是什么呢？

内积计算的方式就是将训练样本投影到参数向量$\theta$，把投影画成红色。将它称为$p^{(i)}$，用来表示这是第 $i$个训练样本在参数向量$\theta$上的投影。${\theta }^T{x}^{(i)}$将会等于$p$ 乘以向量 $\theta$ 的长度或范数。这就等于${\theta }_1\cdot x_1^{(i)}+{\theta }_2\cdot x_2^{(i)}$。这两种方式是等价的，都可以用来计算$\theta$和$x^{(i)}$之间的内积。

这告诉了我们什么呢？这里表达的意思是：这个${\theta }^T{x}^{(i)}>=1$ 或者${\theta }^T{x}^{(i)}<-1$的,约束是可以被$p^{(i)}\cdot x>=1$这个约束所代替的。因为${\theta }^T{x}^{(i)}=p^{(i)}\cdot \Vert \theta \Vert$ ，将其写入我们的优化目标。我们将会得到没有了约束，${\theta }^T{x}^{(i)}$而变成了$p^{(i)}\cdot \Vert \theta \Vert$。

需要提醒一点，我们之前优化目标函数被写成等于$\frac{1}{2}{\Vert \theta \Vert }^2$。现在，继续使用之前的简化，即${\theta }_0=0$，我们来看一下决策边界（绿线）离训练样本的距离很近，为什么支持向量机不会选择它。

对于选择的参数$\theta$（蓝色向量），事实上参数向量$\theta$是和决策界是90度正交的，因此可以知道决策边界的方向。顺便提一句${\theta }_0=0$的简化仅仅意味着决策界必须通过原点$(0,0)$。现在让我们看一下这对于优化目标函数意味着什么。

假设第一个样本$x^{(1)}$，这个样本到参数$\theta$的投影是短的红线段$p^{(1)}$，它非常短。类似地，第二个训练样本$x^{(2)}$到$\theta$的投影画成粉色$p^{(2)}$，这个投影非常短。$p^{(2)}$事实上是一个负值，$p^{(2)}$是在相反的方向，这个向量和参数向量$\theta$的夹角大于90度，$p^{(2)}$的值小于0。

我们会发现这些$p^{(i)}$将会是非常小的数，因此当我们考察优化目标函数的时候，对于正样本而言，我们需要$p^{(i)}\cdot \Vert \theta \Vert >=1$,但是如果 $p^{(i)}$在这里非常小,那就意味着需要$\theta$的范数非常大.因为如果 $p^{(1)}$ 很小,而我们希望$p^{(1)}\cdot \Vert \theta \Vert >=1$,令其实现的唯一的办法就是这两个数较大。如果 $p^{(1)}$ 小，我们就希望$\theta$的范数大。类似地，对于负样本而言我们需要$p^{(2)}\cdot \Vert \theta \Vert <=-1$。我们已经在这个样本中看到$p^{(2)}$会是一个非常小的数，因此唯一的办法就是$\theta$的范数变大。但是我们的目标函数是找到一个参数$\theta$，它的范数是最小的。因此，这看起来不像是一个好的参数向量$\theta$的选择。

相反的，来看一个不同的决策边界（右图）。这时注意到现在$p^{(1)}$ 和$p^{(2)}$这些投影长度是长多了。如果我们仍然要满足这些约束，$P^{(i)}\cdot \Vert \theta \Vert$>1，则因为$p^{(1)}$变大了，$\theta$的范数就可以变小了。因此这意味着通过选择右边的决策界，而不是左边的那个，支持向量机可以使参数$\theta$的范数变小很多。因此，如果我们想令$\theta$的范数变小，从而令$\theta$范数的平方变小，就能让支持向量机选择右边的决策界。这就是支持向量机如何能有效地产生大间距分类的原因。

我们希望正样本和负样本投影到$\theta$的值大。要做到这一点的唯一方式就是选择这条绿线做决策界。这是大间距决策界来区分开正样本和负样本这个间距的值。这个间距的值就是$p^{(1)},p^{(2)},p^{(3)}$等等的值。通过让间距变大，即通过这些$p^{(1)},p^{(2)},p^{(3)}$等等的值，支持向量机最终可以找到一个较小的$\theta$范数。这正是支持向量机中最小化目标函数的目的。

以上就是为什么支持向量机最终会找到大间距分类器的原因。因为它试图极大化这些$p^{(i)}$的范数，它们是训练样本到决策边界的距离。最后一点，我们的推导自始至终使用了这个简化假设，就是参数${\theta }_0=0$。

如果令${\theta }_0$不是0的话，含义就是希望决策界不通过原点。实际上，支持向量机产生大间距分类器的结论，会被证明同样成立，证明方式是非常类似的，是刚刚做的证明的推广。

现在求解目标函数。由于目标函数$\frac{1}{2}||w|{|}_2^2$是凸函数，根据凸优化理论，我们可以通过拉格朗日函数将优化目标转化为无约束的优化函数。

$L(w,b,\alpha )=\frac{1}{2}||w|{|}_2^2-\sum _{i=1}^m{\alpha }_i[y_i(w^T{x}_i+b)-1]满足{\alpha }_i\ge 0$

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

$\underset{{\alpha }_i\ge 0}{\underbrace{max}}\underset{w,b}{\underbrace{min}}L(w,b,\alpha )$

从上式中，先求优化函数对于$w$和$b$的极小值。接着再求拉格朗日乘子$\alpha$的极大值。

对$w$和$b$分别求偏导并令其等于0

$\frac{\partial L}{\partial w}=0\Rightarrow w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$，这可以求出参数$w$；

$\frac{\partial L}{\partial b}=0\Rightarrow \sum _{i=1}^m{\alpha }_i{y}_i=0$

代入拉格朗日函数，得

$-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\bullet x_j)+\sum _{i=1}^m{\alpha }_i$

将上面函数对$\alpha$求极大转化为极小得到目标函数：
$\underset{\alpha }{\underbrace{min}}\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\bullet x_j)-\sum _{i=1}^m{\alpha }_i$

$s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0$

${\alpha }_i\ge 0i=1,2,...m$

具体怎么极小化上式得到对应的$\alpha$，一般需要用到SMO算法，这个算法比较复杂。

前面已知参数$w$如何求，对于$b$，根据KKT条件中的对偶互补条件${\alpha }_i(y_i(w^T{x}_i+b)-1)=0$，如果${\alpha }_j>0$，注意到$y_j^2=1$则，将$w$的表达式代入，则有$b=y_j-w^T{x}_j$。

前面提到设置正则化参数进行软间隔最大化，由于存在样本点的函数间隔小于1，我们让它加上松弛变量使它满足条件，并通过惩罚容忍模型犯一些错。

$min\frac{1}{2}||w|{|}_2^2+C\sum _{i=1}^m{\xi }_i$

$s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i(i=1,2,...m)$

${\xi }_i\ge 0(i=1,2,...m)$

这里,$C>0$为惩罚参数，按之前的方法进行推导，最后唯一不一样的是约束条件：

$\underset{\alpha }{\underbrace{min}}\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\bullet x_j)-\sum _{i=1}^m{\alpha }_i$

$s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0$

$0\le {\alpha }_i\le C$

13.6 合页损失函数

线性支持向量机还有另外一种解释如下：

$\underset{w,b}{\underbrace{min}}[1-y_i(w\bullet x+b){]}_{+}+\lambda ||w|{|}_2^2$

其中第一项称为合页损失函数，第二项是L2正则化项。

$[z{]}_{+}=\{\begin{array}{ll}z& z>0\\ 0& z\le 0\end{array}$

因此，如果点被正确分类，且函数间隔大于1，损失是0，否则损失是$1-y(w\bullet x+b)$,如下图中的绿线。我们在下图还可以看出其他各种模型损失和函数间隔的关系：对于0-1损失函数，如果正确分类，损失是0，误分类损失1， 如下图黑线，可见0-1损失函数是不可导的。对于感知机模型，感知机的损失函数是$[-y_i(w\bullet x+b){]}_{+}$，这样当样本被正确分类时，损失是0，误分类时，损失是$-y_i(w\bullet x+b)$，如下图紫线。对于逻辑回归之类和最大熵模型对应的对数损失，损失函数如下图红线所示。

13.7 核函数1

回顾我们之前讨论过可以使用高级数的多项式模型来解决无法用直线进行分隔的分类问题：

为了获得上图所示的判定边界，我们的模型可能是${\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2+{\theta }_3{x}_1{x}_2+{\theta }_4{x}_1^2+{\theta }_5{x}_2^2+\cdots$的形式。

我们可以用一系列的新的特征$f$来替换模型中的每一项。例如令：
$f_1=x_1,f_2=x_2,f_3=x_1{x}_2,f_4=x_1^2,f_5=x_2^2$

…得到$h_{\theta }(x)={\theta }_1{f}_1+{\theta }_2{f}_2+...+{\theta }_n{f}_n$。然而，除了对原有的特征进行组合以外，有没有更好的方法来构造$f_1,f_2,f_3$？我们可以利用核函数来计算出新的特征。

给定一个训练样本$x$，我们利用$x$的各个特征与我们预先选定的地标(landmarks)$l^{(1)},l^{(2)},l^{(3)}$的近似程度来选取新的特征$f_1,f_2,f_3$。

例如：$f_1=similarity(x,l^{(1)})=e(-\frac{{\Vert x-l^{(1)}\Vert }^2}{2{\sigma }^2})$

其中：${\Vert x-l^{(1)}\Vert }^2=\sum {}_{j=1}^n{(x_j-l_j^{(1)})}^2$，为实例$x$中所有特征与地标$l^{(1)}$之间的距离的和。上例中的$similarity(x,l^{(1)})$就是核函数，具体而言，这里是一个高斯核函数(Gaussian Kernel)。 注：这个函数与正态分布没什么实际上的关系，只是看上去像而已。

这些地标的作用是什么？如果一个训练样本$x$与地标$l$之间的距离近似于0，则新特征 $f$近似于$e^{-0}=1$，如果训练样本$x$与地标$l$之间距离较远，则$f$近似于$e^{-(一个较大的数)}=0$。

假设我们的训练样本含有两个特征[$x_1$ $x{}_2$]，给定地标$l^{(1)}$与不同的$\sigma$值，见下图：

图中水平面的坐标为 $x_1$，$x_2$，而垂直坐标轴代表$f$。可以看出，只有当$x$与$l^{(1)}$重合时$f$才具有最大值。随着$x$的改变$f$值改变的速率受到${\sigma }^2$的控制。

在下图中，当样本处于洋红色的点位置处，因为其离$l^{(1)}$更近，但是离$l^{(2)}$和$l^{(3)}$较远，因此$f_1$接近1，而$f_2$,$f_3$接近0。因此$h_{\theta }(x)={\theta }_0+{\theta }_1{f}_1+{\theta }_2{f}_2+{\theta }_1{f}_3>0$，因此预测$y=1$。同理可以求出，对于离$l^{(2)}$较近的绿色点，也预测$y=1$，但是对于浅蓝色的点，因为其离三个地标都较远，预测$y=0$。

这样，图中红色的封闭曲线所表示的范围，便是我们依据一个单一的训练样本和我们选取的地标所得出的判定边界，在预测时，我们采用的不是训练样本本身的特征，而是通过核函数计算出的新特征$f_1,f_2,f_3$。

13.8 核函数2

上一节讨论了核函数这个想法，在这一节中，将补充一些缺失的细节，并简单的介绍一下怎么在实际中使用应用这些想法。

如何选择地标？

通常是根据训练集的数量选择地标的数量，即如果训练集中有$m$个样本，则选取$m$个地标，并且令:$l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},.....,l^{(m)}=x^{(m)}$。这样做的好处在于：新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即：

下面我们将核函数运用到支持向量机中，修改我们的支持向量机假设为：

• 给定$x$，计算新特征$f$，当${\theta }^{T}f>=0$ 时，预测 $y=1$，否则反之。

另外，支持向量机也可以不使用核函数，不使用核函数又称为线性核函数(linear kernel)，当我们不采用非常复杂的函数，或者我们的训练集特征非常多而样本非常少的时候，可以采用这种不带核函数的支持向量机。

13.9 使用支持向量机

在高斯核函数之外我们还有其他一些选择，如：

多项式核函数（Polynomial Kernel）

字符串核函数（String kernel）

卡方核函数（ chi-square kernel）

直方图交集核函数（histogram intersection kernel）

等等…

这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足Mercer’s定理，才能被支持向量机的优化软件正确处理。

多类分类问题

假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有$k$个类，则我们需要$k$个模型，以及$k$个参数向量$\theta$。我们同样也可以训练$k$个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能，我们只要直接使用即可。

从逻辑回归模型和支持向量机模型，在两者之间，应该如何选择呢？

下面是一些普遍使用的准则：

$n$为特征数，$m$为训练样本数。

(1)如果相较于$m$而言，$n$要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。

(2)如果$n$较小，而且$m$大小中等，例如$n$在 1-1000 之间，而$m$在10-10000之间，使用高斯核函数的支持向量机。

(3)如果$n$较小，而$m$较大，例如$n$在1-1000之间，而$m$大于50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。

值得一提的是，神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，选择支持向量机的原因主要在于它的代价函数是凸函数，不存在局部最小值。

逻辑回归和不带核函数的支持向量机它们都是非常相似的算法，通常都会做相似的事情，并给出相似的结果。但是根据实现的情况，其中一个可能会比另一个更加有效。

最后，神经网络使用于什么时候呢？ 对于所有的这些问题，设计神经网络也很有可能会非常有效。有一个缺点是，或者说是有时可能不会使用神经网络的原因是：对于许多这样的问题，神经网络训练起来可能会特别慢，但是如果有一个非常好的SVM实现包，它可能会运行得比较快比神经网络快很多，尽管我们在此之前没有展示，但是事实证明，SVM具有的优化问题，是一种凸优化问题。因此，好的SVM优化软件包总是会找到全局最小值，或者接近它的值。对于SVM不需要担心局部最优。

事实上，该用这个算法还是该用那个算法没有太大关系，通常更加重要的是：有多少数据，是否擅长做误差分析和排除学习算法，指出如何设定新的特征变量和找出其他能优化学习算法的方法，通常这些方面会比使用逻辑回归还是SVM这方面更加重要。