这是我参与8月更文挑战的第10天，活动详情查看：8月更文挑战

本文为吴恩达机器学习课程的笔记系列第四篇，主要关于支持向量机（Support Vetor Machines）的算法介绍与推导。

代价函数

回顾逻辑回归中的代价函数中的 $Cost(h_{\theta}(x),y)$ ：

$\begin{aligned}Cost& =y^{(i)}log(h_{\theta}(x))+(1-y^{(i)})log(1-h_{\theta}(x))\\&=y^{(i)}(-log(\dfrac{1}{1+e^{-\theta^{T}x}}))+(1-y^{(i)})(-log(1-\dfrac{1}{1+e^{-\theta^{T}x}}))\\&=-y^{(i)}log(\dfrac{1}{1+e^{-\theta^{T}x}})-(1-y^{(i)})log(1-\dfrac{1}{1+e^{-\theta^{T}x}})\end{aligned}$

先忽略 $i$ ，当 $y=1$ 时，我们希望代价最小，也就是希望 $\theta^{T}x \gg0$ ;当 $y=0$ 时，我们希望代价最小，也就是希望 $\theta^{T}x \ll0$ ，图像如下：

在这里插入图片描述

观察图像，当 $y=1$ 时， $z$ 变大，代价变小，为了获得更高的预测精度，SVM 将曲线拉直成折线，取 $z=1$ 为转折点，之前的逻辑回归是 $z=\theta^{T}x \gg0$ 时，预测的结果接近 $y=1$ ，现在 SVM 改为 $z=\theta^{T}x \gg1$ 时，预测的结果接近 $y=1$ 。当 $y=0$ 时同理。我们将 $y=1,y=0$ 时两个新的代价函数分别命名为 $Cost_1(z),Cost_0(z)$ ，图像如下：

在这里插入图片描述

替换逻辑回归的代价函数中的 $Cost$ ，我们可以得到支持向量机的代价函数：

$J(\theta)=\frac{1}{m}\sum\limits_{i=1}^m [y^{(i)}Cost_1(\theta^T x^{(i)})+(1-y^{(i)})Cost_0(\theta^T x^{(i)})]+\frac{\lambda}{2m}\sum\limits_{j=1}^{n}\theta_j^2$

最小化代价

SVM定义其最小化预测代价的过程为：

$\mathop{min}\limits_{\theta} C\sum\limits_{i=1}^m [y^{(i)}Cost_1(\theta^T x^{(i)})+(1-y^{(i)})Cost_0(\theta^T x^{(i)})]+\frac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2$

可以看出 $\frac{\lambda}{m}$ 被提取出来，上述SVM的代价函数可以简单描述为： $CA+B$ ，不难想出逻辑回归的代价函数同样也可以简单描述为： $A+\lambda B$ 。

事实上，逻辑回归是通过 $\lambda$ 来调节权重，而 SVM 则变换了一下，通过 $C$ 来调节权重。实际上 $C$ 可以认为等价于 $\frac{1}{\lambda}$ 。

假设函数

当通过最小化得到参数 $\theta$ 后，可以代入下面的假设函数进行预测：

$h_{\theta}(x)=\begin{cases}1&if\;\theta^T x\geqslant0 \\0&otherwise\end{cases}$

大间距分类器(Large Margin Intuition)

在前面 SVM 的代价函数中，我们了解到，当 $y=1$ 时，SVM 希望 $\theta^{T}x \gg1$ ；而当 $y=0$ 时，SVM 希望 $\theta^{T}x \ll-1$ 。并且 $C$ 用来调节权重。我们考虑一个特例，假设 $C$ 设置为非常大，则在最小化代价函数的过程中，我们会希望中间的 $A$ 也就是代价函数第一项为在 $y=1，y=0$ 时都为 $0$ ，这样便把最小化问题变成最小化第二项 $B$ 的问题：

$min \dfrac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2 \;\;\;\;\; s.t\begin{cases}\theta^Tx^{(i)}\geqslant 1&if\;y^{(i)}=1 \\\theta^T x^{(i)}\leqslant -1&if\;y^{(i)}=0\end{cases}$

下图的黑线便是 SVM 所做出的决策边界。可以看出黑色的边界与训练样本之间有更大的最短距离，这个距离叫做 SVM 的间距（margin），SVM 其实就是努力选最好的决策边界，因此支持向量机有时被称为大间距分类器。

在这里插入图片描述

数学推导

首先回顾向量内积的知识。假设有两个二维向量 $u$ 和 $v$ ：

$u=\begin{bmatrix}u_1\\u_2\end{bmatrix},v=\begin{bmatrix}v_1\\v_2\end{bmatrix}$

我们作几何图来直观表示，且令 $p$ 表示为 $v$ 投影到 $u$ 的长度，如图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eZnPmNta-1628350970614)(/imgs/向量内积.PNG)]

则向量内积： $(u,v)=u^T v=p\cdot ||u||=u_1v_1+u_2v_2$

其中， $||u||=\sqrt{u_1^2+u_2^2}$ 为 $u$ 的范数，也称长度。需要注意的是， $p$ 是一个有符号的数，当向量 $u,v$ 夹角大于 90°时， $p$ 为负数。

回到 SVM 中，我们假设有两个参数 $\theta$ ，即 $\theta=\begin{bmatrix}\theta_1\\\theta_2\end{bmatrix}$ ，且令 $\theta_0=0$ ，以忽略截距，使得向量 $\theta$ 过原点，则：

$\begin{aligned}min \dfrac{1}{2}\sum\limits_{j=1}^{n}\theta_j^2 & =min \dfrac{1}{2}\sum\limits_{j=1}^{n}(\theta_1^2+\theta_1^2)\\&=min \dfrac{1}{2}\sum\limits_{j=1}^{n}(\sqrt{\theta_1^2+\theta_1^2})^2\\&=min \dfrac{1}{2}\sum\limits_{j=1}^{n}||\theta|| \end{aligned}$

可以看出 SVM 所做的就是极小化参数向量 $\theta$ 的范数（或长度）的平方。

另外，我们可以得到： $\theta^T x^{(i)}=p^{(i)}\cdot||\theta||$ ， $p^{(i)}$ 就是为第 $i$ 个训练样本 $x^{(i)}$ 在参数向量 $\theta$ 上的投影。如下图：

在这里插入图片描述

对 $y^{(i)}=1$ 时，我们希望 $p^{(i)}\cdot||\theta||\geqslant1$ ，如果 $p^{(i)}$ （此时 $p^{(i)}>0$ ）非常小，则 $||\theta||$ 会非常大；同样对 $y^{(i)}=0$ 时，我们希望 $p^{(i)}\cdot||\theta||\leqslant -1$ ，如果 $p^{(i)}$ （此时 $p^{(i)}<0$ ）非常小，则 $||\theta||$ 也会非常大，而这都与我们最初想要最小化参数向量 $\theta$ 的范数的平方相矛盾。所以，我们更希望 $p^{(i)}$ 足够大。

核函数（Kernel）

定义

首先，我们要了解线性可分与非线性可分，如下图，左图的数据集即线性可分，右图即非线性可分。

在这里插入图片描述

线性分类问题我们前面的内容其实已经讨论过，即用一条直线去划分数据集，并使之取得最大的决策边界。而对于非线性问题，回想之前逻辑回归的时候，我们是通过Feature mapping（特征组合）来增加一些特征，从而进行多项式拟合。对于 SVM，多项式回归所带来的高阶不一定起明显作用，因此 SVM 使用的是引入预先选定的地标（landmark）,将样本 $x$ 与地标 $l^{(i)}$ 的相似程度作为新的特征 $f_i$ ：

$f_i = similarity(x,l^{(i)})$

距离度量的 $similarity$ 函数就称为核函数。常见的有高斯核函数： $f_i=exp(-\dfrac{||x-l^{(i)}||^2}{2\sigma^2})$

当 $x$ 与地标 $l^{(i)}$ 之间的距离近似于 $0$ 时， $f_i \approx 1$
当 $x$ 与地标 $l^{(i)}$ 之间的距离足够远时， $f_i \approx 0$

值得注意的是，在使用高斯核函数前，需要进行特征缩放（feature scaling）。

地标选择

通常是根据是训练集的样本数量对应确定地标的数量，且每个地标对应每个样本。这样做的好处在于：我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的。

即假设我们有 $m$ 个样本，则 $l^{(1)=x^{(1)}},l^{(2)=x^{(2)}},..,l^{(m)=x^{(m)}}$ 。可得新的特征 $f^{(i)}$ ：

$f^{(i)} = \begin{bmatrix} f_0^{(i)}=1 \\ f_1^{(i)}=similarity(x^{(i)},l^{(1)})\\… \\f_i^{(i)}=similarity(x^{(i)},l^{(i)})=1 \\… \\ f_m^{(i)}=similarity(x^{(i)},l^{(m)}) \end{bmatrix}$

相应地，最终的 SVM 最小化代价过程：

$\mathop{min}\limits_{\theta} C\sum\limits_{i=1}^m [y^{(i)}Cost_1(\theta^T f^{(i)})+(1-y^{(i)})Cost_0(\theta^T f^{(i)})]+\frac{1}{2}\sum\limits_{j=1}^{n=m}\theta_j^2$