12.支持向量机

12 支持向量机

12.1 优化目标

我们通过回顾逻辑回归，一步步将其修改为SVM。在逻辑回归中，若一个样本对应的$y=1$，我们就想让$h_\theta(x) \approx1$, 也就是让$\theta^Tx >>0$. 若一个样本对应的$y=0$，我们就想让$h_\theta(x) \approx0$, 也就是让$\theta^Tx <<0$.

只考虑一个样本$(x,y)$时，代价函数如下所示：若$y=1$，代价函数关于$z$的曲线如左图中蓝色曲线；若$y=0$，代价函数关于$z$的曲线如右图中蓝色曲线。在SVM中，我们分别用粉色的线段作为新的代价函数。左边的函数称为$cost_1(z)$，右边函数称为 $cost_0(z)$。在之后的优化问题中，这种形式的 cost function 会为 SVM 带来计算上的优势。

SVM的代价函数可以从逻辑回归的代价函数演变而来。主要有3个变化：1.使用之前定义的 $cost_1()$ 和 $cost_0()$ 替换公式中对应的项。2.去掉了$\frac{1}{m}$这个系数（因为对于最优化问题，乘除一个常数是不影响我们得出同样的$\theta$最优值）3.化为$C\times A+B$的形式。（对于逻辑回归，代价函数为$ A +\lambda\times B $，通过设置不同的$\lambda$ 来权衡$A$与$B$的重要性。对于SVM，我们删掉$\lambda$，引入常数$C$，将代价函数改为$ C\times A + B$，通过设置不同的$ C $达到优化目的。在优化过程中，其意义和逻辑回归是一样的。可以理解为$ C = 1 / \lambda$）

得到SVM的代价函数为：

另外，逻辑回归中假设的输出是一个概率值。而 SVM 直接预测$ y = 1$，还是$ y = 0$。

12.2 大间距分类的直观理解 Large Margin Intuition

SVM又被称为大间距分类器

在之前的定义中，只要$\theta^Tx \ge0$就被分为正类，只要$\theta^Tx <0$就被分为负类. 但通过观察SVM的代价函数曲线，发现若$y=1$，我们想要让$\theta^Tx \ge1$，这样才能让$cost_1(z)=0$。同样，若$y=0$，我们想要让$\theta^Tx \le-1$.

当超参数$C$很大时，代价函数就会尽量让第一项等于0. 也就是让：若$y^{(i)}=1$，让$\theta^Tx^{(i)}\ge1$；若$y^{(i)}=0$，让$\theta^Tx^{(i)}\le-1$。

这样SVM会把正负样本以最大的间距margin分开，因此SVM有着更好的鲁棒性。黑线即为SVM分类器。只有当 C 特别大的时候， SVM 才是一个最大间隔分类器。

1.如果想将样本用最大间距分开，即将 C 设置的很大。那么仅因为一个异常点，决策边界会从黑线变成那条粉线，这实在是不明智的。2.如果 C 设置的小一点，最终得到这条黑线。它可以忽略一些异常点的影响，而且当数据线性不可分的时候，也可以将它们恰当分开，得到更好地决策边界。

12.3 大间距分类器背后的数学原理

向量的模长（范数）$||u||=\sqrt{u_1^2+u_2^2}\in \mathbb{R}$.

向量内积$u^Tv=||u||\cdot||v||\cdot cos\theta=||u||\cdot p\in \mathbb{R}$.（这里$p$是向量$v$在向量$u$上投影的长度，是一个数，$uv$同向为正，反向为负）.

根据线代公式$u^Tv=u_1v_1+u_2v_2=v^Tu$

这节将解释为什么当 C 特别大的时候， SVM 会是一个最大间隔分类器？

首先我们假设C很大，$\theta_0=0,n=2$(只有两个特征)。C很大时，我们的优化目标是$min \frac{1}{2}\sum_{j=1}^{n}\theta_j^2=\frac{1}{2}||\theta||^2$. 我们再来看$\theta^Tx^{(i)}=p^{(i)}||\theta||=\theta_1x_1^{(i)}+\theta_2x_2^{(i)}$.

根据上面的内积公式，得到：

SVM如何选择更优的决策边界？

假设我们得到了一条绿色的决策边界。因为$\theta$为边界函数的系数，所以以$\theta$为元素的向量和以$\theta$为系数的直线垂直.样本$x^{(1)}$在向量$\theta$上的投影为红色$p^{(1)}$, 样本$x^{(2)}$在向量$\theta$上的投影为粉色$p^{(2)}$.

对于正样本$x^{(1)}$而言，想要$p^{(1)}||\theta||\ge1$，现在$p^{(1)}$长度非常短，就意味着$||\theta||$需要非常大。对于负样本$x^{(2)}$而言，想要$p^{(2)}||\theta||\le-1$，现在$p^{(2)}$长度非常短，就意味着$||\theta||$需要非常大。

但我们的目标函数$min\frac{1}{2}\sum_{j=1}^{n}\theta_j^2=\frac{1}{2}||\theta||^2$是希望最小化参数$\theta$的范数，因此我们希望：投影长度 $p^{(i)}$ 尽可能大。例如下面这条绿色的决策边界，就更好一些：

可以发现此时$p^{(1)}$更大了，想要$p^{(1)}||\theta||\ge1$，$||\theta||$就可以变小了。达到了减低损失函数的目的。

总结：SVM希望正负样本投影到$\theta$的值$p^{(i)}$足够大，实际上这些$p^{(i)}$值就等于间隔margin，也就是最大化了间隔，最终SVM找到了较小的$\theta$的范数，也就是为什么最终找到了大间隔分类器。

12.4 核函数1

接下来我们改造SVM来完成非线性分类问题

我们可以使用高阶多项式来解决非线性分类问题。可以用一系列新的特征 f 来替换模型中的每一项。例如可以令$f_1=x_1,f_2=x_2,f_3=x_1x_2,f_4=x_1^2$, 得到$h_\theta(x)=\theta_0+\theta_1f_1+\theta_2f_2+…$。

特征$f$的选取是多样的，有没有更好的方法来构造特征$f$呢？我们可以利用核函数来计算出新的特征。

我们手动选取一些标记landmarks，分别为$l^{(1)},l^{(2)},l^{(3)}$. 给定一个训练实例$x$，我们用$x$与预先选定的标记 $l^{(1)} ， l^{(2)} ， l^{(3)}$ 的相似程度（核函数）作为新的特征$ f_1 ， f_2 ， f_3$，这里我们使用了高斯核函数。特征$ f_1 ， f_2 ， f_3$的表达式如下：

因为$||x-l^{(1)}||^2=\sum_{j=1}^n(x_j-l_j^{(1)})^2$（忽略了$x_0=0$）.如果训练实例$x$与$l^{(1)}$很近，则$f_1\approx1$；如果训练实例$x$与$l^{(1)}$很远，则$f_1\approx0$.

假设$x$含有两个特征$[x_1,x_2]$，不同的$\sigma$值会有不同效果。图中水平面的坐标为 $x_1， x_2$ , 而垂直坐标轴代表 $f_1$。只有当 $x$ 与 $l^{(1)}$ 重合时， $f_1$ 才具有最大值。特征$f_1$衡量了$x$到标记$l^{(1)}$有多近。随着 $x$ 的改变 $f_1$ 值的变化速率受到 $\sigma^2$ 的控制。 $\sigma^2$越小，曲线越瘦.

假设我们已学到的参数$\theta=[-0.5;1;1;0]$。下图中粉色的点离 $l^{(1)}$ 更近，所以 $f_1$ 接近 1，而 $f_2$ ，$f_3$ 接近 0。因此 $h_\theta(x) \ge 0$，因此预测 $y = 1$；同理，绿色点离 $l^{(2)}$ 较近，也预测$y = 1$；但浅蓝色点离 $l^{(1)}$, $l^{(2)}$ 都较远，预测$y = 0$。

距离 landmarks 近预测为1，距离远预测为0. 图中红色封闭曲线便是决策边界。在预测时我们采用的特征不是训练实例本身的特征，而是通过标记点和核函数计算出的新特征$f_1$ ， $f_2$ ， $f_3$ 。从而训练出了复杂的非线性决策边界.

12.5 核函数2

（1）怎么选取landmarks呢？

我们将每一个样本都作为一个landmark。即$l^{(i)}=x^{(i)}$.

对于训练样本$(x^{(i)},y^{(i)})$，我们可以计算出特征向量$f^{(i)}=[f_0^{(i)};f_1^{(i)};…;f_m^{(i)}]\in \mathbb{R}^{m+1}$. 最后，若$\theta^Tf^{(i)}\ge0$，预测为1.

（2）将核函数kernel引入SVM

将高斯核函数代入SVM的代价函数中，如下图。这里与之前的代价函数的区别在于用核函数$f$代替了$x$。

（3）简化计算

为了简化计算，在计算正则项 $\theta^T\theta$ 时，用 $\theta^TM\theta$ 代替 $\theta^T\theta$ ，其中 M 是一个矩阵，核函数不同则M不同。
（注：理论上也可以在逻辑回归中使用核函数，但使用 M 简化计算的方法不适用于逻辑回归，计算将非常耗时）

（4）参数的选择

1.参数C：当 C 较大，相当于$\lambda$小，可能会导致过拟合，高方差 variance;
当 C 较小，相当于 $\lambda$ 大，可能会导致欠拟合，高偏差 bias;

2.参数$\sigma^2$：当 $\sigma$ 较大时，图像扁平，可能会导致低方差，高偏差 bias;
当 $\sigma$ 较小时，图像窄尖，可能会导致低偏差，高方差 variance。

12.6 使用SVM

（1）核函数选择

通常使用现有的软件包来最小化 SVM 代价函数。在使用SVM时我们要明确1.参数C 2.核函数的选择

第一种核函数：No kernel（线性核函数linear kernel）。即不使用核函数。线性核函数 SVM 适用于函数简单，或特征n非常多而实例m非常少的情况，想要拟合一个线性决策边界的情况。$h_\theta(x)=g(\theta_0+\theta_1x_1+…+\theta_nx_n)$, predict y=1 if $\theta^Tx\ge0$.

第二种核函数：高斯核函数。适应于特征数n很小，样本数m很大，想要拟合出复杂非线性决策边界的情况。$h_\theta(x)=g(\theta_0+\theta_1f_1+…+\theta_nf_n)$, 另外还需要选择参数$\sigma^2$.

（2）特征缩放

在使用高斯核函数之前要进行特征缩放。这样保障SVM可以关注所有不同的特征变量。而不是只被某一个数值特别大的特征影响。

（3）其他kernel

除高斯核函数、线性核函数之外，还有其他一些选择，如：
多项式核函数(Polynomial Kernel)，字符串核函数(String kernel)，卡方核函数( chi-square kernel) ，直方图交集核函数(histogram intersection kernel) 等。
它们的目标也都是根据训练集和标识之间的距离来构建新特征。但其他核函数都使用很少。

一个核函数需要满足 Mercer’s 定理，才能被 SVM 的优化软件正确处理。

（4）多分类问题

假设我们要分为K个类别，可以使用一对多的方法来解决多分类问题，训练K个SVM：对于第i个SVM，将$y=i$作为正类，其余作为负类。这样可以得到K组参数$\theta$，选择具有最大$(\theta^{(i)})^Tx$的类别$i$，作为预测结果。

但是大多数支持向量机软件包都有内置的多类分类功能，我们只要直接使用即可。

（5）逻辑回归模型和 SVM 的选择

可以根据以下准则进行模型的选择：$n$为特征数，$m$为训练样本数。
(a)如果$n>>m$，例如 $n$ 为10000，而 $m$ 在10-1000之间，即训练集数据量不够支持我们训练一个复杂的非线性模型，选用逻辑回归模型或者不带核函数的 SVM。
(b)如果 $n$ 较小，$m$ 中等，例如 $n$ 在 1-1000 之间，而 $m$ 在 10-10000 之间，使用高斯核函数的 SVM。
(c) 如果 $n$ 较小，$m$ 较大，例如 $n$ 在 1-1000 之间，而 $m$ 大于 50000，则使用 SVM 会非常慢。解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的 SVM。(如果训练集非常大，高斯核函数的 SVM 会非常慢。)

（注：逻辑回归和不带核函数的SVM 非常相似。但是根据实际情况，其中一个可能会更有效。随着 SVM 的复杂度增加、特征数量相当大时，不带核函数的SVM 就会表现得相当突出。）