支持向量机（SVM）

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器

SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题

• 优点:泛化错误率低，计算开销不大，结果易解释

• 缺点:对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题

分隔超平面

上面将数据集分隔开来的直线称为分隔超平面 ( separating hyperplane)

在上面给出的例子中，由于数据点都在二维平面上，所 以此时分隔超平面就只是一条直线。但是，如果所给的数据集是三的，那么此时用来分隔数据的就是一个平面

显而易见，更高维的情况可以依此类推。如果数据集是1024维的，那么就需要一个1023维的对象来对数据进行分隔，该对象被称之为超平面(hyperplane)，也就是分类的决策边界

分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据则属于另一个类别

线性可划分

存在一个划分超平面能将训练样本正确分类

而现实人物中，原始样本空间内也许并不在一个能正确划分两类样本的超平面，如下图

对这样的问题, 可将样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分

例如在上图中， 若将原始的二维空间映射到一个合适的三维空间, 就能找到一个合适的划分超平面

比如想要将下图的红点和蓝点变成线性可分的，那么就将映射$y = x$变成映射$y=x^2$，这样就线性可分了

间隔(margin)

对于任意一个超平面，其两侧数据点都距离它有一个最小距离（垂直距离），这两个最小距离的和就是间隔margin

Hard Margin SVM

当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机

svm尝试寻找一个最优决策边界，距离两个类别最近的样本距离最远

在样本空间中，划分超平面可用如下线性方程来描述：

$$w^Tx+b=0$$

其中 $\boldsymbol{w}=\left(w_{1} ; w_{2} ; \ldots ; w_{d}\right)$ 为法向量, 决定了超平面的方向; $b$ 为位移项, 决定了超平面与原点之间的距离

样本空间中任意点 $\boldsymbol{x}$ 到超平面 $(\boldsymbol{w}, b)$ 的距离可写为

$$r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|}$$

假设超平面 $(\boldsymbol{w}, b)$ 能将训练样本正确分类, 即对于 $\left(\boldsymbol{x}_{i}, y_{i}\right) \in D,$ 若 $y_{i}=$ $+1,$ 则有 $\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b>0 ;$ 若 $y_{i}=-1,$ 则有 $\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b<0 .$ 令

$$\left\{\begin{array}{ll} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1, & y_{i}=+1 \\ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1, & y_{i}=-1 \end{array}\right.$$

如上图所示, 距离超平面最近的这几个训练样本点使上式的等号成立, 它们被称为“支持向量”(support vector), 两个异类支持向量到超平面的距离之和为

$$\gamma=\frac{2}{\|\boldsymbol{w}\|}$$

显然, 为了最大化间隔, 仅需最大化 $\|\boldsymbol{w}\|^{-1},$ 这等价于最小化 $\|\boldsymbol{w}\|^{2}$

$$\begin{array}{l} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array}$$

这就是支持向量机(Support Vector Machine, 简称 SVM)的基本型

Soft Margin SVM

当训练数据近似线性可分时，通过软间隔最大化，学习一个线性支持向量机，又称为软间隔支持向量机

前面我们是假定所有的训练样本在样本空间或特征空间中是严格线性可分的，即存在一个超平面能把不同类的样本完全分开，然而现实任务中很难确定这样的超平面（不管是线性超平面还是经过核变换到高维空间的超平面），所以引入松弛变量，允许一些样本出错，但我们希望出错的样本越少越好，所以松弛变量也有限制

具体来说，前面介绍的支持向量机的形式要求所有样本满足约束，即所有的样本必须划分正确，这称为硬间隔，而软间隔则是允许某些样本不满足约束

$$y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1$$

如下图红色圈出了不满足约束的样本

当然, 在最大化间隔的同时, 不满足约束的样本应尽可能少. 于是, 优化目标可写为

$$\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right)$$

其中 $C>0$ 是一个常数, $\ell_{0 / 1}$ 是“0/1损失函数”

$$\ell_{0 / 1}(z)=\left\{\begin{array}{ll} 1, & \text { if } z<0 \\ 0, & \text { otherwise } \end{array}\right.$$

引入“松他变量” (slack variables) $\xi_{i} \geqslant 0,$ 可将上式重写为

$$\min _{\boldsymbol{w}, b, \xi_{i}} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i}$$

对偶问题

现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题

这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解

此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法

这样做的优点在于：

• 一者对偶问题往往更容易求解
• 二者可以自然的引入核函数，进而推广到非线性分类问题

具体来说, 对每条约束添加拉格朗日乘子 $\alpha_{i} \geqslant 0,$ 则该问题的拉格朗日函数可写为

$$L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)$$

其中 $\alpha=\left(\alpha_{1} ; \alpha_{2} ; \ldots ; \alpha_{m}\right) .$ 令 $L(\boldsymbol{w}, b, \boldsymbol{\alpha})$ 对 $\boldsymbol{w}$ 和 $b$ 的偏导为零可得

$$\begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \end{aligned}$$

即可将 $L(\boldsymbol{w}, b, \boldsymbol{\alpha})$ 中的 $\boldsymbol{w}$ 和 $b$ 消去, 就得到的目标函数对偶问题

$$\max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}$$

非线形SVM

当训练数据线性不可分时，通过使用核技巧(kernel trick)及软间隔最大化，学习非线形支持向量机

非线性SVM算法原理

对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机

令 $\phi(x)$ 表示将 $x$ 映射后的特征向量, 于是, 在特征空间中划分超平面所对
应的模型可表示为

$$f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b$$

其中 $\boldsymbol{w}$ 和 $b$ 是模型参数，有

$$\begin{array}{l} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array}$$

其对偶问题是

$$\max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)$$ $$\begin{array}{ll} \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array}$$

由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积

有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积，于是上式可重写为

$$\begin{array}{ll} \max _{\boldsymbol{\alpha}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array}$$

常见的核函数

$$\begin{aligned} &\text { 线性核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\\ &\text { 多项式核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\right)^{d} \quad d \geqslant 1 \text { 为多项式的次数 }\\ &\text { 高斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}}{2 \sigma^{2}}\right) \quad \sigma>0 \text { 为高斯核的带宽(width) }\\ &\text { 拉普拉斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|}{\sigma}\right) \quad \sigma>0\\ &\text { Sigmoid 核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\tanh \left(\beta \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}+\theta\right) \quad \text { tanh 为双曲正切函数, } \beta>0, \theta<0 \end{aligned}$$

二分类扩展到多分类问题

SVM 扩展可解决多个类别分类问题

one-vs-rest

对于每个类，有一个当前类和其他类的二类分类器（one-vs-rest）
将多分类问题转化为 n 个二分类问题

svm解决回归问题

现在我们来考虑回归问题，传统回归模型通常直接基于模型输出 $f(x)$ 与真实输出 $y$ 之 间的差别来计算损失, 当且仅当 $f(\boldsymbol{x})$ 与 $y$ 完全相同时, 损失才为零

与此不同 $,$ 支持向量回归(Support Vector Regression, 简称 SVR)假设我们能容忍 $f(x)$ 与 $y$ 之间最多有 $\epsilon$ 的偏差, 即仅当 $f(\boldsymbol{x})$ 与 $y$ 之间的差别绝对值大于 $\epsilon$ 时才计算损失

如图所示, 这相当于以 $f(x)$ 为中心, 构建了一个宽度为 $2 \epsilon$ 的间隔带, 若训练样本落入此间隔带, 则认为是被预测正确的

于是, SVR 问题可形式化为

$$\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{c}\left(f\left(\boldsymbol{x}_{i}\right)-y_{i}\right)$$

其中 $C$ 为正则化常数, $\ell_{\epsilon}$ 是图 6.7 所示的 $\epsilon$ -不敏感损失 $(\epsilon$ -insensitive loss $)$ 函数

$$\ell_{\epsilon}(z)=\left\{\begin{array}{ll} 0, & \text { if }|z| \leqslant \epsilon \\ |z|-\epsilon, & \text { otherwise } \end{array}\right.$$

参考

机器学习算法（一）SVM

机器学习-周志华

支持向量机（SVM）——原理篇

Machine Learning in Action by Peter Harrington