简单经典的支持向量机

SVM：Support Vector Machine。

解决的问题

支持向量机主要解决二分类问题，通过学习高维空间的线性分割边界解决原始数据线性不可分问题。
基础的模型输入是原始数据，输出是高维分割超平面，预测时通过某条数据在超平面的哪一侧表达类别归属。

SVM同时也能应用于多分类、回归及单分类异常检测等问题。

SVC

Support Vector Classification，y ϵ {+1, -1}。

Peter Flach Machine Learning

直觉上，线性可分二分类，最好的分类边界应该是使靠的最近的不同类别的数据分开的越远越好。接近边界的数据能被良好地分开，远离边界的数据，分类自然更没问题。
SVM就是尝试寻找这个分割边界，也就是最大化上图中的红色边界和虚线之间的距离，由于是线性关系，系数可以缩放，为方面处理，令m=1，可得最大化的目标函数是1 / ||w||，等价于：

Andrew NG CS229

注意：y ϵ {+1, -1}，m=1，不等式约束表达数据都在上图边界构成的管道外，保证w是最优化边界的参数。

考虑不等式约束，根据拉格朗日乘子法，目标函数变为：

Andrew NG CS229

再根据拉格朗日对偶问题：

Andrew NG CS229

结合KKT条件，最终的目标函数为：

Andrew NG CS229

注意最终目标函数的形式：

1. 目标函数的变量是拉格朗日乘子α，且只和数据集(x, y)有关，可以通过SMO(sequential minimal optimization)最优化方法方便求解α。
2. 根据KKT约束：α_i * g_i(w) = 0，g_i(w) ≤ 0，可知当g_i = 0，α_i > 0，即在上图最近虚线边界上时；当g_i < 0，α_i = 0。
3. α_i > 0 对应的样本点，称为支持向量，少量的数据参与训练，能有效降低学习的复杂度。
4. 目标函数样本间仅以<内积>形式出现，这是转换为对偶问题后，比较吸引人的形式。
5. 内积形式可以方便地将x打包映射到Φ(x)，而不影响之前的整个推导，边界关于Φ(x)是线性的；Φ(x)一般是个向量，映射后的空间以向量为基本元素的希尔伯特空间，暂且称之为“内积空间”。
6. 内积空间中可以通过核函数技巧，使映射后空间变得更高维复杂，但计算复杂度和原始低维一致。
7. 映射x->Φ(x)的动机来自于低维线性不可分的数据，高维可能可以。

核函数技巧

Kernel Trick，SVM算法的一大利器。

Sergios Theodoridis Machine Learning

x -> Φ(x)，比如:

Andrew NG CS229

但是<Φ(x1), Φ(x2)>的时间复杂度也随着映射空间的复杂而复杂。

核函数技巧的重点通过已知的核函数隐式地实现内积的形式<Φ(x1), Φ(x2)>，并不直接设计Φ；选择核函数的标准也在于能否表达某种<内积>关系。
<Φ(x1), Φ(x2)>表达某种度量关系，可以选择合适的核函数表达这种度量，即k(x1, x2)代替<Φ(x1), Φ(x2)>。

常见的核函数有四种：

National Taiwan University A Practical Guide to Support Vector Classification

可见，以上核函数的计算复杂度都在原始x空间内。
RBF即高斯核函数，示意图如下：

Sergios Theodoridis Machine Learning

polynomial多项式核函数：

Sergios Theodoridis Machine Learning

不同核函数，分类效果，大致如下：

scikit-learn.org svm文档

C-SVC

上述推导的SVM是理想情况下，数据集能够完美划分的情形。实际情况，难免会有一些干扰数据。SVM的一个最常见的变体是采用软间隔，增加L1正则，容忍管道内有一定的数据：

Simon Haykin《Neural Networks and Learning Machines》

ϵ表达点到其分类决策边界的距离，是个绝对值概念，所以称之为L1正则。
C表示管道内接受的异常数据的个数，用来权衡两部分损失函数，是个需要重点调试的超参数。

Andrew NG CS229

根据朗格朗日乘子法：

最终的目标函数变为：

Andrew NG CS229

和理想的SVM相比，朗格朗日乘子α多了个上界约束，其最终约束为：

Andrew NG CS229

分类表达

给定一个样本，预测的时候，SVC如何确定属于哪一个分类呢？

Simon Haykin《Neural Networks and Learning Machines》

其实就是将样本数据代入映射后的高维空间，按照位置，线性判别即可。

LIBSVM: A Library for Support Vector Machines

可见，SVC只能输出样本属于哪一个分类，而不能像其他分类器一样输出概率。

多分类SVC

主流的多分类有one-versus-one和one-versus-all。

1. one-versus-one
   假设有k个类，每两个类训练一个SVC，总共需要训练k(k-1)/2个模型，最后通过投票的方式，确定某一个样本的归属。
2. one-vs-the-rest
   训练k个SVC，每一个区分是否属于某一类，对比k个分类器，选择距离决策面最远的某类：

LIBSVM: A Library for Support Vector Machines

One-class SVM

单分类SVM，只有一个类别，SVM等于是在发现训练数据的数据分布。

LIBSVM: A Library for Support Vector Machines

通过ν控制误差及特征向量个数，ρ是个偏移量，可以理解为适应不同象限不同位置的样本分布。
可以这样直观理解：

datachemeng.com

映射到高维空间后，让所有样本属于同一个类的同时，尽可能让边界离原点距离最远，最终根据边界判断是否为异常数据。

ϵ-SVR

ϵ-INSENSITIVE Support Vector Regression：解决回归问题。
套路和SVC分类一样，拉格朗日乘子、对偶、KKT，选择特征向量，最优化拉格朗日乘子。

类比于分类边界的管道，ϵ-SVR回归的管道是容忍误差ϵ，特征向量对应的点是两个虚线边界上和边界外的样本。

和C-SVC一致，这里线性回归采取的也是绝对值误差：

近似方法为linear ϵ-insensitive loss，在[-ϵ, +ϵ]范围内，误差近似为0，暂且称ϵ为容忍误差：

Sergios Theodoridis Machine Learning

以linear ϵ-insensitive loss为基础，与C-SVC类似，将正则误差项替换为回归的损失，优化的原始目标函数为：

注意参数符号与SVC略有不同，应该不影响阅读。
根据拉格朗日乘子，目标函数为：

经过对偶、KKT条件约束、求导，最终优化的目标函数为：

Sergios Theodoridis Machine Learning

给定样本，预测结果为：

本段的图片来自Sergios Theodoridis的《Machine Learning: A Bayesian and Optimization Perspective》。

复杂度

想到只有支持向量参与学习，SVM的速度应该很快，这是一个小误区，因为确定支持向量本身也是学习的一部分。

以主流的libsvm的复杂度为例：

scikit-learn.svm 文档

可见，复杂度大概为o(n^2) ~ o(n^3)，随着样本的增加，SVM的速度会变得很慢。

代码示例

以scikit-learn SVM相关方法为例。

scikit-learn.svm 二分类

scikit-learn.svm one vs one 多分类

scikit-learn.svm 线性核二分类

scikit-learn.svm 回归

总结

基础的SVM算法通过拉格朗日相关最优化方法，将欧拉空间线性不可分问题映射到希尔伯特空间线性可分，并通过核函数技巧及支持向量选择，在高维空间有效解决二分类问题。
SVM是一个超级经典、技巧性极强的机器学习算法，其解决问题的思路，应该也为后来的神经网络带来了一些启发。

Simon Haykin《Neural Networks and Learning Machines》