支持向量机

Support Vector Machines

代价函数

在逻辑回归中，我们的预测函数为：

$h_{\theta}(x) = \frac{1}{1+e^{-\theta^T x}}$

代价函数为：$cost = -ylogh_{\theta}(x)+(1-y)log(1-h_{\theta}(x))$

当 $y=1 $时，代价函数就为：

$\begin{align*} cost &= -logh_{\theta}(x)\ = -log\frac{1}{1+e^{-z}}, \quad z=\theta^T x \end{align*}$

不难看出，当 $y=1$时，随着 $ z$ 取值变大，预测代价变小，因此，逻辑回归想要在面对正样本 $ y=1$时，获得足够高的预测精度，就希望 $z=\theta^T x \gg 0$ 。而 SVM 则将上图的曲线拉直为下图中的折线，构成了 $y=1$时的代价函数曲线 $cost_1(z)$。

当 $ y=1$ 时，为了预测精度足够高，SVM 希望 $\theta^T x \geq 1$。同样，在 $ y=0$时，SVM 定义了代价函数 $ cost_0(z))$，为了预测精度足够高，SVM 希望 $ \theta^T x \leq -1$：

SVM定义其最小化预测代价的过程为：
$\min\limits_{\theta}C[\sum\limits_{i=1}^{m}y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2$

$h_\theta(x) =\begin{cases}1,\quad \mbox{if $\theta^T x \geq 0$} \\0,\quad \mbox{otherwise}\end{cases}$

而在逻辑回归中，最小化预测代价的过程为：

$
\min\limits_{\theta}\frac{1}{m}[\sum\limits_{i=1}^{m}y^{(i)}(-logh_\theta(x^{(i)}))+(1-y^{(i)})(-log(1-h_\theta(x^{(i)})))] + \frac{\lambda}{2m}\sum\limits_{j=1}^{n}\theta_j^2
$

事实上，我们可以将逻辑回归的代价函数简要描述为：$cost=A+λB$

而 SVM 的代价函数描述为：$cost=CA+B$

即，在逻辑回归中，我们通过正规化参数 $ λ$调节 $A、 B$所占的权重，且 $A$ 的权重与$λ$取值成反比。而在SVM中，则通过参数 $C$调节 $ A、B$所占的权重，且A的权重与$C$的取值成反比。亦即，参数$C
$可以被认为是扮演了 $ \frac{1}{\lambda}$ 的角色。

大间距分类器

SVM 最小化代价函数过程为：

$ \min\limits_{\theta}C[\sum\limits_{i=1}^{m}y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2 $

并且，当 $ y^{(i)}=1$时，SVM 希望 $\theta^Tx^{(i)} \geq 1$；而当 $y^{(i)}=0$时，SVM 希望 $\theta^Tx^{(i)} \leq -1$。则最小化代价函数的过程就可以描述为：

$\begin{align*} & \min\frac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2 \\ \mbox{s.t}. \quad &\theta^T x^{(i)} \geq 1 &\mbox{if $y^{(i)}=1$} \\ & \theta^T x^{(i)} \leq -1 &\mbox{if $y^{(i)}=0$} \end{align*}$

SVM 最终找出的决策边界会是下图中黑色直线所示的决策边界，而不是绿色或者紫色的决策边界。该决策边界保持了与正、负样本都足够大的距离，因此，SVM 是典型的大间距分类器（Large margin classifier）。

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

在这里，如果你加了这个样本，为了将样本用最大间距分开，也许我最终会得到一条类似这样的决策界，对么？就是这条粉色的线，仅仅基于一个异常值，仅仅基于一个样本，就将我的决策界从这条黑线变到这条粉线，这实在是不明智的。而如果正则化参数$C$，设置的非常大，这事实上正是支持向量机将会做的。它将决策界，从黑线变到了粉线，但是如果$C$ 设置的小一点，如果你将C设置的不要太大，则你最终会得到这条黑线，当然数据如果不是线性可分的，如果你在这里有一些正样本或者你在这里有一些负样本，则支持向量机也会将它们恰当分开。因此，大间距分类器的描述，仅仅是从直观上给出了正则化参数$C$非常大的情形，同时，要提醒你$C$的作用类似于$1/\lambda$，$\lambda$是我们之前使用过的正则化参数。这只是$C$非常大的情形，或者等价地 $\lambda$ 非常小的情形。你最终会得到类似粉线这样的决策界，但是实际上应用支持向量机的时候，当$C$不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。甚至当你的数据不是线性可分的时候，支持向量机也可以给出好的结果。

回顾 $C=1/\lambda$，因此：

$C$ 较大时，相当于 $\lambda$ 较小，可能会导致过拟合，高方差。

$C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差。

核函数

在逻辑回归中，我们会通过多项式扩展来处理非线性分类问题：

为了获得上图所示的判定边界，我们的模型可能是${ {\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_θ(x)=f_1+f_2+…+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{ { {\left| x-{ {l}^{(1)}} \right|}^{2}}}{2{ {\sigma }^{2}}})$

其中：${ {\left| x-{ {l}^{(1)}} \right|}^{2}}=\sum{_{j=1}^{n}}{ {({ {x}_{j}}-l_{j}^{(1)})}^{2}}$，为实例$x$中所有特征与地标$l^{(1)}$之间的距离的和。这种距离度量的方式就称之为核函数（Kernel), 最常见的核函数是高斯核函数（Gaussian Kernel）：

$f_i = exp(-\frac{||x-l^{(i)}||^2}{2\delta^2})$

在高斯核函数中，如果样本与标记点足够接近，即$x \approx l^{(i)}$
，则：
$f \approx exp(-\frac{0^2}{2\delta^2}) \approx 1$
如果样本远离标记点，则：$ f\approx exp(-\frac{(\mbox{large number})^2}{2\delta^2})\approx0 $

图中水平面的坐标为 $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_θ(x)=θ_0+θ_1f_1+θ_2f_2+θ_1f_3>0$，因此预测$y=1$。同理可以求出，对于离$l^{(2)}$较近的绿色点，也预测 $y=1$，但是对于蓝绿色的点，因为其离三个地标都较远，预测$y=0$。

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

在使用高斯核函数前，需要做特征缩放（feature scaling），以使 SVM 同等程度地关注到不同的特征。

标记点选取

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

得到新的特征向量：$f \in R^{m+1}$,

$f=\left(\begin{matrix}f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_m \end{matrix}\right) \quad \mbox{其中 $f_0=1$}$

则具备核函数的 SVM 的训练过程如下：
$\min\limits_{\theta}C\big[\sum\limits_{i=1}^{m}y^{(i)}cost_1(\theta^Tf^{(i)})+(1-y^{(i)})cost_0(\theta^Tf^{(i)})\big]+\frac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2$

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

下面是支持向量机的两个参数$C$和$\sigma$的影响：

$C=1/\lambda$

$C$ 较大时，相当于$\lambda$较小，可能会导致过拟合，高方差；

$C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差；

$\sigma$较大时，可能会导致低方差，高偏差；

$\sigma$较小时，可能会导致低偏差，高方差。

使用SVM

作为当今最为流行的分类算法之一，SVM 已经拥有了不少优秀的实现库，如 libsvm 等，因此，我们不再需要自己手动实现 SVM（要知道，一个能用于生产环境的 SVM 模型并非课程中介绍的那么简单）。

在使用这些库时，我们通常需要声明 SVM 需要的两个关键部分：

参数 C
核函数（Kernel）

由于 $ C $可以看做与正规化参数 $ λ$作用相反，则对于 $ C$的调节：

低偏差，高方差，即遇到了过拟合时：减小 $ C$值。
高偏差，低方差，即遇到了欠拟合时：增大 $ C$值。

而对于核函数的选择有这么一些 tips：

当特征维度 $ n$ 较高，而样本规模 $m$ 较小时，不宜使用核函数，否则容易引起过拟合。
当特征维度 $ n$较低，而样本规模 $m$足够大时，考虑使用高斯核函数。不过在使用高斯核函数前，需要进行特征缩放（feature scaling）。
另外，当核函数的参数 $ δ$ 较大时，特征 $f_i$ 较为平缓，即各个样本的特征差异变小，此时会造成欠拟合（高偏差，低方差）：

当 $ δ $ 较小时，特征 $f_i$ 曲线变化剧烈，即各个样本的特征差异变大，此时会造成过拟合（低偏差，高方差）：

不是所有的相似度评估手段都能被用作SVM核函数，他们需要满足 Mercer 理论

多类分类问题

通常，流行的SVM库已经内置了多分类相关的 api，如果其不支持多分类，则与逻辑回归一样，使用 One-vs-All 策略来进行多分类：

轮流选中某一类型 $ i$，将其视为正样本，即 “1” 分类，剩下样本都看做是负样本，即 “0” 分类。
训练 SVM 得到参数$\theta^{(1)}, \theta^{(2)}, …, \theta^{(K)}$ ，即总共获得了 K−1 个决策边界。

分类模型的选择

目前，我们学到的分类模型有：（1）逻辑回归；（2）神经网络；（3）SVM。怎么选择在这三者中做出选择呢？我们考虑特征维度 n 及样本规模 m ：

如果 $n$ 相对于 $m $非常大，例如 $ n=10000$，而 $m \in (10,1000)$: 此时选用逻辑回归或者无核的SVM。
如果 $n$较小，$ m$ 适中，如 $ n \in(1,1000)$，而$m \in(10,10000)$：此时选用核函数为高斯核函数的 SVM。
如果 $n$ 较小，$m$ 较大，如 $n\in(1,1000)$，而 $m>50000$ ：此时，需要创建更多的特征（比如通过多项式扩展），再使用逻辑回归或者无核的 SVM。

神经网络对于上述情形都有不错的适应性，但是计算性能上较慢。