6. 支持向量机

支持向量机是一种二分类算法，通过在高维空间中构建超平面实现对样本的分类

[TOC]

线性可分SVM通过硬间隔最大化求出划分超平面，解决线性分类问题

线性SVM通过软间隔最大化求出划分超平面，解决线性分类问题

非线性SVM利用核函数实现从低维原始空间到高维特征空间的转换，在高维空间上解决非线性分类问题

SVM的学习时个凸二次规划问题，可以用SMO算法快速求解

线性可分SVM

eg：SVM解决二分类问题的思路

线性可分的数据集可以简化为二维平面上的点集。

在直角坐标系中，如果有若干个点位于 $x$ 轴下方，另外若干个点位于 $x$ 轴上方，这两个点集共同构成了一个线性可分的训练数据集，而 $x$ 轴就是将它们区别开的一维超平面，也就是直线。

假设 $x$ 轴上方的点全部位于直线 $y=1$ 上及其上方，$x$ 轴下方的点全部位于直线 $y=-2$ 上及其下方。则任何平行于 $x$ 轴且在 $(-2,1)$ 之间的直线都可以将这个训练集分开。但此时面临选择哪一条直线分类效果最好的问题。

直观上看 $y=-0.5$ 最好，这条分界线正好位于两个边界中间，与两个类别的间隔 可以同时达到最大。当训练集中的数据因为噪音干扰而移动时，这个最优划分超平面的划分精确度受到的影响最小，具有很强的泛化能力

线性可分SVM基本思想

在高维的特征空间上，划分超平面可以用简单的线性方程描述

$\omega^T\cdot X+b=0$

$n$ 维向量 $\omega$ 为法向量，决定了超平面的方向
$b$ 为截距，决定了超平面与高维空间中原点的距离

划分超平面将特征空间分为两部分

法向量所指一侧——正例，$y=+1$
法向量反方向恻——负例，$y=-1$

线性可分支持向量机就是在给定训练数据集的条件下，根据硬间隔最大化学习最优的划分超平面过程

给定超平面后，特征空间中的样本点 $X_i$ 到超平面的距离可以表示为

$\gamma=\frac{\omega^T\cdot X_i+b}{\Vert \omega\Vert}$

这个距离是一个归一化距离——几何间隔

通过合理设置参数 $\omega$ 和 $b$ ，可以使每个样本到达最优划分超平面的距离都不小于 $1$ ，即有 函数间隔

$\omega^T\cdot X_i+b\ge 1,y_i=+1\\ \omega^T\cdot X_i+b\le -1,y_i=-1\\$

函数间隔与几何将的区别在于未归一化和归一化

在特征空间中，距离划分超平面最近的样本点能让函数函数间隔取等号，这些样本点称为 支持向量 ，即有点 $X_{k^+},X_{k^-}$

$\omega^T\cdot X_{k^+}+b= 1,y_{k^+}=+1\\ \omega^T\cdot X_{k^-}+b= -1,y_{k^-}=-1\\$

两个异类支持向量到超平面的距离之和为 $\frac{2}{\Vert \omega\Vert}$ 。

因而对于线性可分的SVM任务就是：在满足上述不等式的条件下，寻找 $\frac{2}{\Vert \omega\Vert}$ 的最大值，最大化 $\frac{2}{\Vert \omega\Vert}$ 等效于最小化 $\frac{1}{2}\Vert \omega\Vert^2$

线性SVM基本思想

当训练集线性不可分时，学习策略变为 软间隔最大化

线性不可分意味着某些样本点距离划分超平面的函数间隔不满足不小于1的约束条件，因而需要对每个样本点引入大于零的松弛变量 $\xi\ge 0$ ，使得函数间隔和松弛变量的和不小于1，即约束条件为

$\omega^T\cdot X_i+b\ge 1-\xi_i,y_i=+1\\ \omega^T\cdot X_i+b\le-1+\xi_i,y_i=-1\\$

相应地，最优化问题中的目标函数演变为 $\frac{1}{2}\Vert \omega\Vert^2+C\sum_\limits{i=1}^n\xi^2_i$ ，其中 $C$ 被称为 惩罚参数

软间隔允许某些样本不满足应间隔的约束，但会限制这些特例的数目

非线性可分SVM

非线性可分问题处理思路

原始空间不存在能够正确划分的超平面

在二维平面直角坐标系中，如果按照与原点之间的距离对数据点进行分类的话，分类模型就成为一个圆，也就是超平面

如果能将样本从原始空间映射到高维特征空间上，在新的特征空间是上样本就可能是线性可分的

若样本的属性数优先，则一定存在一个高维特征空间使样本可分

核技巧

将原始低维空间上的非线性问题转化为新的高维空间上的线性问题，这就是核技巧的基本思想。

当核技巧应用于SVM中时，原始空间与新空间之间的转化是通过非线性变换实现的

假设原始空间是 低维欧几里得空间 $\chi$ ，新空间为 高维希尔伯特空间 $\mathcal{H}$ ，从 $\chi$ 到 $\mathcal{H}$ 的映射可以用函数 $\phi(x):\chi\rightarrow \mathcal{H}$ 表示。核函数可以表示为映射函数内积形式

$K(x,z)=\phi(x)\cdot\phi(z)$

核函数

特点

计算过程在低维空间上完成，避免了高维空间中的复杂计算
对于给定核函数，高维空间 $\mathcal{H}$ 和映射函数 $\phi$ 的取法不唯一

正定核函数

正定核函数充要条件：由函数中任意数据的集合形成的核矩阵都是非正定的

任何一个核函数都隐式定义了一个成为 再生核希尔伯特空间 的特征空间

分类

在支持向量机中，核函数的选择是一个核心问题，常用核函数有：

线性核 ：$K(X,Y)=X^TY$

多项式核 ：$K(X,Y)=(X^TY+c)^d$ ，$c$ 为常数，$d\ge 1$ 为多项式次数

高斯核 ：$K(X,Y)=e^{-\frac{\Vert X-Y\Vert^2}{2\sigma^2}}$ ，$\sigma>0$ 为高斯核带宽

拉普拉斯核 ：$K(X,Y)=e^{-\frac{\Vert X-Y\Vert}{\sigma}}$

sigmod核 ：$K(X,Y)=tanh(\beta X^TY+\theta)$ ，$\beta >0$ ，$\theta <0$

SVM参数求解

将支持向量机的最优化作为原始问题，应用最优化理论中的拉格朗日对偶性，可以通过求解其对偶问题得到原始问题的最优解

在算法实现过程中，支持向量机会遇到大量训练样本下，全局最优解难以求得的情况——SMO算法（序列最小最优化）

支持向量机的学习问题可以形式化为凸二次规划问题的求解，SMO算法的特点是不断将原始的二次规划问题分解为只有两个变量的二次规划子问题，并求解子问题的解析解，直到所有变量满足条件为止

支持向量机的一个重要性质就是当训练完成后，最终模型只与支持向量有关

SVM关键是如何根据支持向量构建解，算法的复杂度也主要取决于支持向量的数目