支持向量机 | Patrick’s Blog

基本概念——线性可分类问题
线性可分
定义
优化问题
小结
非线性问题
软间隔
非线性可分
核函数
对偶问题
定义

基本概念——线性可分类问题

支持向量机是基于统计学习理论的一种实用的机器学习方法。

SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

机器学习算法的时间线：

线性可分

问题：无数条线，哪个直线是最好的？

如何定义这条线？
定义一个衡量每一条线的标准，每条线都能算出来一个性能指标。
哪条线能让这个性能指标最大？

好的决策边界：间隔大

决策边界离两类数据应尽可能远

将平行线插到的向量称为支持向量

让这条线平行移动，直到能够插到某一个或几个圆圈为止

这个距离作为性能指标，绿色线是这个距离最大的一条线

定义

训练数据和标签： $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$

其中 $x_i=\begin{bmatrix} x_{i1} \\ x_{i2} \\ \dots \\ x_{im} \end{bmatrix}$ 为向量， $y_i=1$ 或 $-1$ 为标签。

线性模型： $(w,b)$ $w^\text{T}x+b=0$ （超平面 Hyperplane）

$w$ ：向量，维度与 $x$ 一样 $w=\begin{bmatrix} w_{1} \\ w_{2} \\ \dots \\ w_{m} \end{bmatrix}$ $b$ ：常数

要找到描述这个超平面的线性方程

通过所有 $x$ 和 $y$ 的取值，来算出 $w$ 和 $b$

一个训练集线性可分是指： ${}$ $\{(x_i,y_i)\},i=1∼N$

$\exists (w,b)$ ，使对 $\forall i=1∼N$ ，有：

若 $y_i=+1$ ，则 $w^\text{T}x_i+b\ge0$ 。
若 $y_i=-1$ ，则 $w^\text{T}x_i+b\le0$ 。

统一表示为： $y_i[w^\text{T}x_i+b]\ge 0$

线性可分数据的超平面

当训练数据集线性可分时，存在无穷多个分离超平面可将两类数据正确分开。
感知机利用误分类最小的策略，求得分离超平面，但有无穷多个解。
支持向量机利用间隔最大化求最优分离超平面，解唯一。

优化问题

如何得到间隔最大的超平面

支持向量机做了一个优化问题：

最小化（Minimize） $\lVert w\rVert$

约束条件（Subject to） $y_i[w^\text{T}x_i+b]\ge 1\;(i=1∼N)$

$w^\text{T}+b=0$ 与 $aw^\text{T}+ab=0$ 是同一个平面， $a\in \R^+$

点 $(x_0,y_0)$ 到平面 $w_1x+w_2x+b=0$ 的距离：
$d=\cfrac{|w_1x+w_2x+b|}{\sqrt{w_1^2+w_2^2}}$
向量 $x_0$ 到平面 $w^\text{T}x+b=0$ 的距离：
$d=\cfrac{|w^\text{T}x_0+b|}{\lVert w\rVert}$ ，其中 $\lVert w\rVert=\sqrt{w_1^2+w_2^2+\cdots+w_m^2}$ 。

SVM是最大化间隔的分类算法

用 $a$ 缩放 $(w,b)$ → $(aw,ab)$ ，最终使其在支持向量 $x_0$ 上有： $|w^\text{T}x_0+b|=1$

此时支持向量与平面的距离： $d=\cfrac{1}{\lVert w\rVert}$

最小化 $\lVert w\rVert$ ，其他点大于 $d$

$y_i$ 取正负1，可以协调两个类，也可以改成任意整数，差距就是 $a$

数据集如果线性可分，就能求得 $w$ 和 $b$ ，满足条件：

$\frac{1}{2}\lVert w\rVert^2=\frac{1}{2}(w_1^2+w_2^2+\cdots+w_m^2)$ $\frac{1}{2}$ 是为了求导方便

$y_i[w^\text{T}x_i+b]\ge 1\;(i=1∼N)$

优化问题

目标优化问题是一个凸优化问题中的一种二次规划问题
二次规划（quantity programming）
目标函数是二次项；约束条件是一次项
无解或者一个最小值
二次规划是计算机已解决的问题，其局部极值就是全局极值
用试探方法，求极值，例如梯度下降
多维情况下很困难，有时人眼无法看到所有情况

小结

SVM是最大化间隔（margin）的分类算法
优化问题
训练样本 $\{(x_i,y_i)\}_{i=1∼N}$
优化目标
$\min\frac{1}{2}\|w\|^2$
$s.t.\;\; y_i[w^\text{T}x_i+b]\ge1\;\;(i=1∼N)$
凸优化问题中的二次规划问题

非线性问题

软间隔

训练数据中的特异点，去掉后，剩下大部分样本点组成的集合满足线性可分

引入“软间隔”的概念，允许支持向量机在一些样本上不满足约束

现实中，很难确定合适的核函数使得训练样本在特征空间中线性可分；一个线性可分的结果也很难断定是否是由过拟合造成的。

将线性不可分的学习问题转换为凸二次规划问题，即软间隔最大化

线性支持向量机：

最小化： $\frac{1}{2}\|w\|^2+\boxed{C\sum_{i=1}^{N}\xi_i}$ （ $\xi_i$ 为松弛变量， $C\sum_{i=1}^{N}\xi_i$ 为正则项）

约束条件：

（1） $y_i[w^\text{T}x_i+b]\ge1$

（2） $\xi_i\ge0\;,i=1∼N$

求解得到分离超平面 $w^*x+b^*=0$ ，以及决策函数 $f(x)=sign(w^*x+b^*)$

软间隔参数

尽可能在保持间隔宽阔或限制间隔违例之间找到一个平衡

间隔或限制间隔违例之间的关系由超参数 $C$ 控制， $C$ 越大，间隔越窄，但是违例也更少，反之则间隔越宽，但是违例也越多。

非线性可分

仍然找直线，但是到一个高维空间中找直线

定义一个高维映射 $\phi(x)$ ：低维 $x$ → 高维 $\phi(x)$

例如，最简单的非线性可分问题：异或问题

线性分类器变为一个超平面，把空间分为两个部分

关键思想：

为了解决非线性分割问题，将 $x_i$ 变换到一个高维空间

输入空间： $x_i$ 所在的空间
特征空间：变换后 $\phi(x_i)$ 的空间

如何变换？

利用一个适当的变换 $\phi$ ，使分类变得容易
特征空间中的线性算子等价于输入空间中的非线性算子

变换可能出现的问题：难以得到一个好的分类且计算开销大

需要同时解决两个问题：

最小化 $\|w\|$ 能得到好的分类
利用核函数技巧可以进行有效的计算

核函数

高维映射 $x\rightarrow\phi(x)$

$\begin{cases} y_i[w^{\text{T}}\phi(x_i)+b]\ge1-\xi_i \\ \xi_i\ge 0 \end{cases}$

$\phi(x)$ 是无限维，无法求整体优化

$\phi(x_1)$ 与 $\phi(x_2)$ 两个无限维向量内积：核函数（Kenerl Function）

$K(x_1,x_2)=\phi(x_1)^\text{T}\phi(x_2)$

只要知道一个核函数，不知道无限维映射 $\phi(x_i)$ 的显式表达，仍然可以求解最优

为什么可以通过求内积代替显式 $\phi$ ——对偶问题

假设知道了 $K$ ，如何求解 $\phi(x_i)$ ，让优化问题可求解？

核函数也是有限制的， $K$ 要满足某种特定条件，才能拆成内积， $K(x_1,x_2)$ 能写成 $\phi(x_1)^\text{T}\phi(x_2)$ 的充要条件：

（1）交换性： $K(x_1,x_2)=K(x_2,x_1)$

（2）半正定性： $\forall C_i,x_i\;,i=1,\dots,N$ ，有

$\sum_{i=1}^N\sum_{j=1}^NC_iC_jK(x_i,x_j)\ge0$

高斯核

无限维的特征变换 $\phi(x)$

$K(x,x')=\exp(-(x-x')^2)$

一般形式： $K(x,x')=\exp(-\lambda(x-x')^2)\;,\lambda>0$

对偶问题

定义