定义

支持向量机是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器；支持向量机还包括核技巧，使它成为实质上的非线性分类器。

支持向量机学习策略是间隔最大化，形式化为一个求解凸二次规划的问题。

间隔与支持向量

先来看看下面这一组数据的分布，这是一组两种标签的数据，两种标签分别由圆和方块代表。支持向量机的分类方法，是在这组分布中找出一个超平面作为决策边界，将不同类别分开，但能将样本分开的超平面有很多，应该使用哪一个呢？

直观上看，我们应该使用两类训练样本‘正中间’的超平面，因为该超平面对样本的局部扰动的容忍性最好。
在样本空间中，划分超平面可用以下方程表示：
$w^Tx+b=0$wTx+b=0
其中$w=(w_1,w_2,...,w_d)$w=(w1​,w2​,...,wd​)为法向量，决定了超平面的方向；b为位移项，决定了超平面和原点之间的距离。
样本空间中任意点x到超平面（w,b）的距离可写为：
$r=\frac{\vert w^Tx+b\vert}{\vert \vert w \vert\vert}$r=∣∣w∣∣∣wTx+b∣​

假设超平面能将训练样本正确分类，则有：
$\begin{cases} w^Tx_i+b\geq +1, & y_i=+1\\ w^Tx_i+b\leq +1,& y_i=-1 \end{cases}${wTxi​+b≥+1,wTxi​+b≤+1,​yi​=+1yi​=−1​
如下图所示，距离超平面最近的训练样本点使得上式的等号成立，他们称为支持向量，两类支持向量到超平面的距离之和称为间隔，为：
$\gamma=\frac{2}{\vert\vert w\vert\vert}$γ=∣∣w∣∣2​

要想找到最大间隔的超平面，就是要找满足上式中约束参数的$w$w和$b$b，使得$\gamma$γ最大，即：
$max_{ab}\frac{2}{\vert\vert w\vert\vert}$maxab​∣∣w∣∣2​
$s.t. y_i( w^Tx_i+b\geq 1),i=1,2,...,m$s.t.yi​(wTxi​+b≥1),i=1,2,...,m
显然，为了最大化间隔，只需最大化$\frac{1}{\vert\vert w\vert\vert}$∣∣w∣∣1​，等价于最小化$\vert\vert w\vert\vert ^2$∣∣w∣∣2。

故上式可写为：
$max_{ab}\frac{1}{2}{\vert\vert w\vert\vert}^2$maxab​21​∣∣w∣∣2
$s.t. y_i( w^Tx_i+b\geq 1),i=1,2,...,m$s.t.yi​(wTxi​+b≥1),i=1,2,...,m

对偶问题

求解上式，可使用拉格朗日乘子法得到对偶问题。
具体推导略。

核函数

一般我们假设训练样本是线性可分的，即存在一个超平面能将训练样本正确分类；但实际中，原样本空间也许不存在一个能正确划分两类样本的超平面，对于这样问题，我们可将原始样本空间映射到一个更高维的特征空间，使得样本在这个空间里线性可分，那么就需使用核函数。

常用的核函数及对比：

• Linear Kernel 线性核 $k(x_i,x_j)=x_i^{T}x_j$k(xi​,xj​)=xiT​xj​ 线性核函数是最简单的核函数，主要用于线性可分，它在原始空间中寻找最优线性分类器，具有参数少速度快的优势。 如果我们将线性核函数应用在KPCA中，我们会发现，推导之后和原始PCA算法一模一样，这只是线性核函数偶尔会出现等价的形式罢了。

• Polynomial Kernel 多项式核 $k(x_i,y_j)=(x_i^{T}x_j)^d$k(xi​,yj​)=(xiT​xj​)d 也有复杂的形式： $k(x_i,x_j)=(ax_i^{T}x_j+b)^d$k(xi​,xj​)=(axiT​xj​+b)d 其中$d\ge1$d≥1为多项式次数，参数就变多了，多项式核实一种非标准核函数，它非常适合于正交归一化后的数据，多项式核函数属于全局核函数，可以实现低维的输入空间映射到高维的特征空间。其中参数d越大，映射的维度越高，和矩阵的元素值越大。故易出现过拟合现象。

• 径向基函数 高斯核函数 Radial Basis Function（RBF）$k(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{2\sigma^2})$k(xi​,xj​)=exp(−2σ2∣∣xi​−xj​∣∣2​)$\sigma>0$σ>0是高斯核带宽，这是一种经典的鲁棒径向基核，即高斯核函数，鲁棒径向基核对于数据中的噪音有着较好的抗干扰能力，其参数决定了函数作用范围，超过了这个范围，数据的作用就“基本消失”。高斯核函数是这一族核函数的优秀代表，也是必须尝试的核函数。对于大样本和小样本都具有比较好的性能，因此在多数情况下不知道使用什么核函数，优先选择径向基核函数。

• Laplacian Kernel 拉普拉斯核 $k(x_i,x_j)=exp(-\frac{||x_i-x_j||}{\sigma})$k(xi​,xj​)=exp(−σ∣∣xi​−xj​∣∣​)Sigmoid Kernel Sigmoid核 $k(x_i,x_j)=tanh(\alpha x^Tx_j+c)$k(xi​,xj​)=tanh(αxTxj​+c) 采用Sigmoid核函数，支持向量机实现的就是一种多层感知器神经网络。其实还有很多核函数，在参考博客里大家都可以看到这些核函数，对于核函数如何选择的问题，吴恩达教授是这么说的：如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况

【参考资料】
1.西瓜书
2.统计学习方法
3.DataWhale开源学习项目