支持向量机

什么是支持向量机

• 二分类模型
• 定义为特征空间中最大间隔的线性分类器，优化目标就是使间隔最大化，再后续式子中可以看到这个最大化可以通过凸二次规划求解
• 简单来说，支持向量机就是在高维空间中找到一个超平面来将样本二分类，并使得最近样本离这个超平面的距离最大，鲁棒性最好

函数间隔和几何间隔

函数间隔

二维平面可以用 $ax+by+c=0$ 来表示，超平面实际上就是找到一个高位的平面，其表示为

$w^{T}x+b=0$

其中，x为特征向量

对数据点划分时，超平面距离最近的点间隔越大，分类的鲁棒性越好，超平面对新加进来的点的适应性越强，出错的概率越小。所以优化就是让所选择的超平面能最大化这个间隔(gap)，将间隔定义为 函数间隔和几何间隔

给定一个超平面，其实易得 $|w^{T}x+b|$ 可以表示 点$x_i$ 距离超平面的远近，当 $w^{T}x+b>0$ 时，$x$ 在正类，标签为 1，而当$w^{T}x+b<0$ 时，$x$ 为负类，标签为 -1

可定义如下函数间隔(functional margin)：

$\hat{\gamma }=y(w^{T}x+b)=yf(x)$

其中，y是标签

对于超平面$(w,b)$，我们将所有样本点$(x_i,y_i)$的函数间隔中的最小值作为在训练集$T$ 上的函数间隔

$\hat{\gamma }=min{\hat{\gamma }}_i$

而对于SVM的设计来说，若通过最优化函数间隔来得到超平面则存在一些问题：

• 当参数同比例变化时，函数间隔也会跟着变，但是实际上超平面却没有变化

所以应该使用另一种间隔—几何间隔

几何间隔

几何间隔(geometrical margin) 代表的是数据点到超平面的真实距离，对于超平面$w^{T}x+b=0$ , $w$ 代表的是超平面的法向量，设 $x^{\ast }$ 是超平面外一点在法向量$w$方向上的投影点，$x$ 与超平面距离为$r$，则有$x^{\ast }=x-\gamma \frac{w}{||w||}$ ，$\gamma$是$x$与超平面的距离

又有 $x^{\ast }$ 在超平面上，即 $w^T{x}^{\ast }+b=0$ ，代入即可得到（$w^{T}w=||w|{|}^2$)

$\gamma =\frac{w^{T}x+b}{\Vert w\Vert }=\frac{f(x)}{\Vert w\Vert }$

为了得到$\gamma$的绝对值，令其乘上对应的类别，得到几何间隔的定义

$\tilde{\gamma }=y\gamma =\frac{\hat{\gamma }}{\Vert w\Vert }$

Note

对比函数间隔和几何间隔

• 实际上 函数间隔 就是 $|w^{T}x+b|$
• 而几何间隔就是 点到超平面的距离，通过推导发现可以使用函数间隔来推导表示

最大化间隔和支持向量

优化目标是最大化几何间隔

$\max \tilde{\gamma }{y}_i(w^T{x}_i+b)={\hat{\gamma }}_i\ge \hat{\gamma },i=1,...,n$

含义是在函数间隔的式子中最大化几何间隔中的最小值

一般的，令 $\hat{\gamma }$ 为 1（方便后续推导），使上述目标函数转换为

$\max \frac{1}{\Vert w\Vert }\text{s.t.}{y}_i(w^T{x}_i+b)\ge 1,i=1,...,n$

距离超平面最近的，函数间隔为1的点构成支持向量，所有不是支持向量的点 都有$y(w^T+b)>1$

而间隔 定义为$\gamma =\frac{2}{||w||}$（正负两边的距离和）

为最大化这个间隔，其实就是最大化 $||w|{|}^{-1}$ ，等价于最小化 $||w|{|}^2$，所有将目标式子重写为

$$\begin{array}{rl}& \underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,m.\end{array}$$

Note

为什么平方

只是为了方便优化

这个式子将原本的问题转换成一个带约束的凸二次规划问题。

对偶问题

其实上述式子已经可以求解，但实际上由于SVM的特殊性，一般将原问题转换成它的对偶问题，再对其对偶问题求解。

原因如下：

• 对偶问题更容易求解
• 通过对偶问题求解出现了向量内积的形式，从而更好的引出核函数来处理高维特征空间
• 也更容易引入软间隔（处理噪声和异常值）

对偶问题，顾名思义，是原始问题的等价优化问题，将原始目标的最小化转为它对偶函数的最大化问题

对于上述的二次规划问题，可以先展开为拉格朗日函数

$\mathcal{L}(w,b,\alpha )=\frac{1}{2}||w|{|}^2+{\sum }_{i=1}^n{\alpha }_i(1-y_i(w^T{x}_i+b))$

Note

具体过程

拉格朗日乘子(Lagrange multipliers)可以将约束条件融入到目标函数中，对于原式中的不等式约束$y(w^T{x}_i+b)\ge 0$ ，引入 $\alpha \ge 0$ 来 构造满足 最小化 的乘项

上述问题中，当有的约束不满足时，L的最大值可以是无穷，所有约束都满足时，最大值为 $\frac{1}{2}||w|{|}^2$ ，因此在保证原式求解含义一致性的情况下，原问题等价于

$$\underset{w,b}{\min }\theta (w)=\underset{w,b}{\min }\underset{{\alpha }_i\ge 0}{\max }\mathcal{L}(w,b,\alpha )=p^{\ast }$$

但是这个问题不好求解，一般将 最大最小交换(满足KKT条件，因为是不等式)，变成原问题的对偶问题

对偶问题的构造需要先对 式子 中的$w$ 和 $b$ 求偏导，令偏导等于0

Note

为什么求偏导？

本质上希望消去原始优化问题中的变量，转化为仅关于拉格朗日乘子的问题（利用拉格朗日对偶性(Lagrangian Duality)

这也是可以构造对偶问题的条件），核心思路是通过极值条件简化问题

可得：

$$w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i,$$ $$0=\sum _{i=1}^m{\alpha }_i{y}_i.$$

将两个式子（两个极值条件）代入lagrange function ，可以消去 $w,b$ 得到

$$\begin{array}{rl}\underset{\alpha }{\max }& \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{x}_i^T{x}_j\\ \text{s.t.}& \sum _{i=1}^m{\alpha }_i{y}_i=0,\\ & {\alpha }_i\ge 0,i=1,2,\dots ,m.\end{array}$$

这个式子就是 原式的对偶问题

Note

为什么对偶问题可以求解？

对偶函数其实是 原始问题最优值的下界$g(\alpha )\le 原问题最优解$，最大化（在这个问题里）对偶函数可以接近原始问题的最优解

在SVM中，原始问题是凸优化且满足Slater条件（严格满足约束的可行解），强对偶性成立，也就是可以取等

求解得到:

$$\begin{array}{rl}{w}^{\ast }& =\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\\ b^{\ast }& =-\frac{{\max }_{i:y_i=-1}{w}^{\ast T}{x}_i+{\min }_{i:y_i=1}{w}^{\ast T}{x}_i}{2}\end{array}$$

可以求出 $\alpha ,w,b$ 代入模型 $f(x)=w^{T}x+b$，得到

${\sum }_{i=1}^m{\alpha }_i{y}_i{x}_i^{T}x+b$ 其中，$x_i$ 是支持向量，同时由于满足 KKT(Karush-Kuhn-Tucker)条件，要求

$$\{\begin{array}{l}{\alpha }_i\ge 0;\\ y_{i}f(x_i)-1\ge 0;\\ {\alpha }_i(y_{i}f(x_i)-1)=0.\end{array}$$

可以得知，对样本总有 ${\alpha }_i=0$ 或者 $y_{i}f(x_i)=1$ ，如果前者成立，那么样本就不会影响到模型求和，如果后者成立，则样本点在边界上，是一个支持向量，这说明支持向量机的一个重要性质：训练完成后，大部分训练样本都无需保留，最终模型仅与支持向量有关

Note

如何求解 $\alpha$?

实际上对偶问题是一个二次规划问题，只是这里是对样本数n求解，时间复杂度大，所以提出了一些算法，其中比较知名的有SMO(Sequential Minimal Optimization)

Note

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。

见KKT条件

同时，求解结果中

$$\sum _{i=1}^m{\alpha }_i{y}_i{x}_i^{T}x+b$$

引入了点积，可以自然的引入核函数来解决高维问题

核函数

上述超平面只能解决线性可分问题，对于线性不可分的问题，例如（异或）需要推广到核函数，解决线性不可分问题，常采用映射方式，将低维原始空间映射到高维特征空间，使得数据集在高维空间中线性可分，再使用线性学习器分类，如果原始空间的维度是有限的，那么总存在一个高维特征空间使得样本可分。

$$f(\mathbf{x})={\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})+b$$

按同样的流程计算其对偶问题

$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j⟨\varphi ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)⟩\\ & \text{s.t.}{\alpha }_i\ge 0,i=1,\dots ,n\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

原分类函数为：

$$f(\mathbf{x})=\sum _{i=1}^n{\alpha }_i{y}_i⟨\varphi ({\mathbf{x}}_i),\varphi (\mathbf{x})⟩+b$$

求解只涉及到高维特征空间的内积运算，这个高维度导致计算困难，因此时使用 核函数 来辅助解决

定义 3(核：Kernel)核是一个函数 K，对所有 , E ，满足 $K(\mathbf{x},\mathbf{z})=⟨\varphi (\mathbf{x}),\varphi (\mathbf{z})⟩$ 这里 $\varphi$ 是从匕到内积特征空间F的映射。

核函数可以直接计算隐式映射到高维特征空间后的向量内积，不需要显式的写出映射后的结果，虽然完成了将特征从低维到高维的转换，但最终却是在低维空间中完成向量的内积运算（低维计算，高维表现），避免高维空间无法计算的问题，引入核函数后，对偶问题变为：

$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)\\ & \text{s.t.}{\alpha }_i\ge 0,i=1,\dots ,n\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

求解SOM并代入得分类函数：

$$f(\mathbf{x})=\sum _{i=1}^n{\alpha }_i{y}_{i}K({\mathbf{x}}_i,\mathbf{x})+b$$

尽管核函数的引入带来巨大的便利，其选择是否恰当成了支持向量机的最关键的问题

定理 6.1（核函数）令为输入空间，(，)是定义在×上的对称 函数，则r 是核函数当且仅当对于任意数据 D={a1,a2,..,am}，“核矩阵”(kernel matrix) K 总是半正定的：

$$\mathbf{K}=\left[\begin{array}{ccccc}\kappa ({\mathbf{x}}_1,{\mathbf{x}}_1)& \cdots & \kappa ({\mathbf{x}}_1,{\mathbf{x}}_j)& \cdots & \kappa ({\mathbf{x}}_1,{\mathbf{x}}_m)\\ ⋮& \ddots & ⋮& \ddots & ⋮\\ \kappa ({\mathbf{x}}_i,{\mathbf{x}}_1)& \cdots & \kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)& \cdots & \kappa ({\mathbf{x}}_i,{\mathbf{x}}_m)\\ ⋮& \ddots & ⋮& \ddots & ⋮\\ \kappa ({\mathbf{x}}_m,{\mathbf{x}}_1)& \cdots & \kappa ({\mathbf{x}}_m,{\mathbf{x}}_j)& \cdots & \kappa ({\mathbf{x}}_m,{\mathbf{x}}_m)\end{array}\right]$$

核函数的构造十分困难，一般都是从常见的选取，列出：

软间隔

上述问题解决了两个主要问题：

• 数据线性可分
• 高维解决低维非线性可分

但是当存在噪声(离群值 outlier)，划分出来的平面可能就不是最优值，这对分类的鲁棒性影响很大

为解决这一问题，可以允许某些点不满足约束，可以一定程度的偏移超平面，同时又使得不满足约束的样本尽可能地少，这就是 软间隔 支持向量机

将优化目标变为：

$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^m{\ell }_{0/1}(y_i(w^T{x}_i+b)-1)\\ & {\ell }_{0/1}(z)=\{\begin{array}{ll}1,& \text{if }z<0;\\ 0,& \text{otherwise}.\end{array}\end{array}$$

允许部分小于0，当小于0时其影响置0

但其数学上性质不佳，常用其他函数代替

$$\begin{array}{rl}\text{hinge 损失: }{\ell }_{hinge}(z)& =\max (0,1-z);\\ \text{指数损失(exponential loss): }{\ell }_{exp}(z)& =\exp (-z);\\ \text{对率损失(logistic loss): }{\ell }_{log}(z)& =\log (1+\exp (-z)).\end{array}$$

在支持向量机中选择了hinge损失，引入松弛变量，将目标函数写为：

$$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i\\ \text{s.t.}& y_i(w^T{x}_i+b)\ge 1-{\xi }_i,i=1,\dots ,n\\ & {\xi }_i\ge 0,i=1,\dots ,n\end{array}$$

C是控制权重，用以控制目标与新引入的正则项之间的权重，再进一步展开为Lagrange函数

$$\mathcal{L}(w,b,\xi ,\alpha ,r)=\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1+{\xi }_i)-\sum _{i=1}^n{r}_i{\xi }_i$$

求极值解、代入和SOM算法求解$\alpha$

$$\begin{array}{rl}\frac{\partial \mathcal{L}}{\partial w}& =0⟹w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\\ \frac{\partial \mathcal{L}}{\partial b}& =0⟹\sum _{i=1}^n{\alpha }_i{y}_i=0\\ \frac{\partial \mathcal{L}}{\partial {\xi }_i}& =0⟹C-{\alpha }_i-r_i=0,i=1,\dots ,n\end{array}$$

得出的对偶问题：

$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ \text{s.t.}& 0\le {\alpha }_i\le C,i=1,\dots ,n\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

可以看到对偶问题里相比之下只多了一个C作为上限，其他完全相同，因此引入核函数处理线性不可分问题时，便可以使用 硬间隔 里使用的技巧来计算。

多分类

成对分类问题(one-against-one, pairwise classification)

每一对可能train一个支持向量机，适合实际应用，是LIBSVM库的实现方法

$$\begin{array}{rl}\underset{w^{ij},b^{ij},{\xi }_t^{ij}}{\min }& \frac{1}{2}(w^{ij}{)}^T{w}^{ij}+C\sum _t{\xi }_t^{ij}\\ \text{s.t.}& (w^{ij}{)}^T\varphi (x_t)+b^{ij}\ge 1-{\xi }_t^{ij},\text{if }{y}_t=i\\ & (w^{ij}{)}^T\varphi (x_t)+b^{ij}\le -1+{\xi }_t^{ij},\text{if }{y}_t=j\\ & {\xi }_t^{ij}\ge 0\end{array}$$

$$y_{new}^{ij}=\text{sign}\left[(w^{ij}{)}^T\varphi (x_{new})+b^{ij}\right]=\text{sign}\left[\sum _{\begin{array}{c}\text{support}\\ \text{vectors}\end{array}}{y}_t^{ij}{\alpha }_t^{ij}k(x_t,x_{new})+b^{ij}\right]$$

正负代表了其的归属

采用voting strategy机制来分类：

• 每个SVM对新数据做预测，预测结果类别票数加1
• 票数最多的类别就是预测结果
• 平票选择索引小的一类（只是一种处理）

一类对余类(one-against-all)

每类以其余所有作为负类trian支持向量机

$$d_{new}^i=(w^i{)}^T\varphi (x_{new})+b^i=\sum _{\begin{array}{c}\text{support}\\ \text{vectors}\end{array}}{y}_t{\alpha }_t^{i}k(x_t,x_{new})+b^i$$

为避免平票问题，这里去掉了符号函数，如果属于该类，那么结果应该为正，对于新数据，选择预测结果最大的类作为预测

Other

不平衡类

可以设置不同的惩罚项，例如样本数中正类少，负类多，那么正类给更大的惩罚项，负类给小的

交叉验证

通过交叉验证来得到最优参数

只求解一个问题的多欸方法

构造M个决策函数，然后用加和的方式优化所有第m个函数

$$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\sum _{m=1}^M{w}_m^T{w}_m+C\sum _{t=1}^N\sum _{m\ne y_t}{\xi }_t^m\\ \text{s.t.}& w_{y_t}^T\varphi (x_t)+b_{y_t}\ge w_m^T\varphi (x_t)+b_m+2-{\xi }_t^m,t=1,\dots ,N,m\in \{1,\dots ,M\}\setminus \{y_t\}\\ & {\xi }_t^m\ge 0,t=1,\dots ,N,m\in \{1,\dots ,M\}\setminus \{y_t\}\end{array}$$

决策是选择最大的预测值

Refer

• 西瓜书
• 笔记：西瓜书学习笔记(6)—支持向量机 - Heywhale.com
• 多分类：支持向量机原理详解(八): 多类分类SVM - 知乎