一. SVM模型的基本概念

1.1 从线性判别说起

如果需要构建一个分类器将上图中的黄点与蓝点分开，最简单的方法就是在平面中选择一条直线将二者分开，使得所有的黄点与蓝点分属直线的两侧。这样的直线有无穷多种选择，但是什么样的直线是最优的呢？

显而易见的是，中间的红色的分割线的效果会比蓝色虚线与绿色虚线的效果好。原因是，需要分类的样本点普遍距离红线比较远，因而健壮性更强。相反，蓝色虚线与绿色虚线分别距离几个样本点很近，从而在加入新的样本点后，很容易发生错误分类。

1.2 支持向量机(SVM)的基本概念

点到超平面的距离
在上述的分类任务中，为了获取稳健的线性分类器，一个很自然的想法是，找出一条分割线使得两侧样本与该分割线的平均距离足够的远。在欧式空间中，定义一个点𝒙到直线（或者高维空间中的超平面）${\mathbf{w}}^T\mathbf{x}+b=0$的距离公式是：
$$r(x)=(|{\mathbf{w}}^T\mathbf{x}+b|)/(||\mathbf{w}||)$$
在分类问题中，如果这样的分割线或者分割平面能够准确地将样本分开，对于样本${\mathbf{x}}_i,y_i\in D,y_i=\pm 1$ 而言，若$y_i=1$，则有${\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b\ge 1$，反之若$y_i=-1$，则有${\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b\le -1.$

支持向量与间隔
对于满足${\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b=\pm 1$的样本，它们一定落在2个超平面上。这些样本被称为“支持向量（support vector）”，这2个超平面称为最大间隔边界。分属不同类别的样本距离分割平面的距离之和为

𝛾=2/(||𝑤||) 
1

该距离之和被称为“间隔”

二. SVM的目标函数和对偶问题

2.1 支持向量机的优化问题

因此，对于完全线性可分的样本，分类模型的任务就是找出这样的超平面，满足

等价于求解带约束的最小化问题：

2.2 优化问题的对偶问题

一般来说，求解带等式或不等式约束的优化问题时，通常使用拉格朗日乘子法将原问题转换成对偶问题。在SVM的优化问题中，相应的对偶问题为：

对𝐿(𝑤,𝑏,𝛼)求关于𝑤,𝑏,𝛼的偏导数并且令为0，有：

最终的优化问题转化成

解出𝛼后，求出𝑤,𝑏即可得到模型。一般使用SMO算法求解。

2.3 支持向量与非支持向量

注意到，$y_i({\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b)\ge 1$是不等式约束，因此$a_i$需要满足$a_i(y_i({\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b)-1)=0$（这是KKT条件中关于不等式约束的条件）。因此，满足这样的条件的样本${\mathbf{x}}_{\mathbf{i}},y_i$，要么$a_i=0$, 要么$y_i({\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b)-1$。因此对于SVM的训练样本来讲，
如果$a_i=0$，则$\sum 〖a_i-1/2\sum \sum a_i{a}_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_{\mathbf{j}}$的计算中不会出现该样本
如果$y_i({\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b)-1$，则该样本处于最大间隔边界上
从这一点可以看出，大部分训练样本最后都不会对模型的求解有任何影响，仅支持向量影响到模型的求解。

三. 软间隔

3.1 线性不可分

在一般的业务场景中，线性可分是可遇而不可求的。更多是线性不可分的情形，即无法找出这样的超平面可以完全正确地将两类样本分开。
为了解决这个问题，一个方法是我们允许部分样本被错误的分类（但是不能太多！） 。带有错误分类的间隔，称之为“软间隔”。于是，目标函数仍然是带约束的最大化间隔，其中约束条件是，不满足$y_i({\mathbf{w}}^T{\mathbf{x}}_{\mathbf{i}}+b)\ge 1$的样本越少越好。

3.2 损失函数

基于这个思想，我们改写了优化函数

使其变为

可用的损失函数有:

3.3 松弛变量

当使用hinge loss的时候，损失函数变为

3.4 求解带松弛变量的软间隔SVM

令𝐿(𝑤,𝑏,𝛼,𝜂,𝜇)关于𝑤,𝑏, 𝜂的偏导等于0，则有：

3.5 支持向量与非支持向量

四. 核函数

4.1 从低维到高维

线性不可分:

线性可分:

4.2 核函数

4.3 核函数的选择

一些先验经验

1. 如果特征数远远大于样本数 ，使用线性核就可以了
2. 如果特征数和样本数都很大，例如文档分类，一般使用线性核
3. 如果特征数远小于样本数，这种情况一般使用RBF
   或者使用交叉验证法选择最合适的核函数

4.4 SVM模型的优缺点

优点:

1. 适合小样本的分类
2. 泛化能力强
3. 局部最优解一定是全局最优解

缺点:

1. 计算量很大，大规模训练样本很难实施
2. 给出的结果是硬分类而非基于概率的软分类。SVM也可输出概率，但是计算更加复杂

参考:

1. http://www.dataguru.cn/mycourse.php?mod=intro&lessonid=1701