前言

SVM分类器是一种常用的分类器，使用甚多，却没有详细了解，值此面试佳季，来个详解吧

Part 1 线性分类器

硬间隔支持向量机（硬边）

如果一个线性函数能够将样本完全正确分开，就称这些数据是线性可分的，否则称为非线性可分的。
线性函数：在一维空间是一个点，二维空间是一条直线，三维空间是一个平面，以此类推，可统称为超平面（Hyper Plane）。
对于二类分类问题，训练集 $T = \{({{\text{x}}_{1}},{{{y}}_1}),({{\text{x}}_{2}},{{{y}}_2}),\cdots,({{\text{x}}_{N}},{{{y}}_N})\}$T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，其类别${{{y}}_i}$yi​∈{-1,1}，样本特征向量${\text{x}}_{i}=[x_{i1},x_{i2},\cdots,x_{im}]$xi​=[xi1​,xi2​,⋯,xim​]。线性SVM通过学习得到分离超平面：
${{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}} + {\mathbf{b}} = 0$wT⋅x+b=0
相应的分类决策函数：
$f(x)=sign({{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}} + {\mathbf{b}})$f(x)=sign(wT⋅x+b)


彩色图中，超平面$\text{B}_1$B1​的分类效果更好一点。${b}_{11}$b11​和${b}_{12}$b12​是平行于$\text{B}_1$B1​的，且过离$\text{B}_1$B1​最近的两类样本，这些样本称为支持向量（support vector）。${b}_{11}$b11​和${b}_{12}$b12​之间的距离称为margin：
$margin=\frac{2} {{\left\| {\mathbf{w}} \right\|}}$margin=∥w∥2​
显然，margin更大，则分类正确的确信度更高（与超平面的距离表示分类的确信度，距离越远则分类正确的确信度越高）。
从上图中可观察到：margin以外的样本点对于确定分离超平面没有贡献，换句话说，SVM是有很重要的训练样本（支持向量）所确定的。至此，SVM分类问题可描述为在全部分类正确的情况下，最大化 $\frac{2}{{\left\| {\mathbf{w}} \right\|}}$∥w∥2​（等价于最小化 $\frac{1}{2}{\left\| {\mathbf{w}} \right\|}^2$21​∥w∥2），即线性分类的约束最优化问题：
$\mathop {\min }\limits_w \quad \frac{1}{2}{\left\| {\mathbf{w}} \right\|}^2$wmin​21​∥w∥2
$s.t. \quad {{{y}}_i}*({{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}_i} + {\mathbf{b}})>=1$s.t.yi​∗(wT⋅xi​+b)>=1
${{{y}}_i}$yi​这个公式是通过以下公式改写的
${{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}_i} + {\mathbf{b}}&gt;=1,\quad if\quad{{{y}}_i}=1 \\ {{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}_i} + {\mathbf{b}}&lt;=-1,\quad if\quad{{{y}}_i}=-1$wT⋅xi​+b>=1,ifyi​=1wT⋅xi​+b<=−1,ifyi​=−1

软间隔支持向量机（软边际）

但是新问题出现了，在实际应用中，我们得到的数据并不总是完美的线性可分的，其中可能会有个别噪声点，他们错误的被分类到了其他类中。如果将这些特异的噪点去除后，可以很容易的线性可分。但是，我们对于数据集中哪些是噪声点却是不知道的，如果以之前的方法进行求解，会无法进行线性分开。两种说法：
1、为此，我们引入了铰链损失函数，
$max(0,1-{{{y}}_i}*({{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}_i} + {\mathbf{b}}))$max(0,1−yi​∗(wT⋅xi​+b))
如果${\mathbf{x}_i}$xi​位于边缘的正确一侧，那么这个函数为0。所以我们希望尽量减少：
$\left[ {\frac{1} {n}\sum\limits_{i = 1}^n {\max \left( {0,1 - {{{y}}_i}*({{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}_i} + {\mathbf{b}})} \right)} } \right] + \lambda {\left\| {\mathbf{w}} \right\|}^2$[n1​i=1∑n​max(0,1−yi​∗(wT⋅xi​+b))]+λ∥w∥2
我的理解：当有些数据是噪声或会分类错误时（即左侧值会变大），增加$\lambda$λ，使最小化${\left\| {\mathbf{w}} \right\|}^2$∥w∥2权重增加，即增大margin，从而提高分类准确率。当$\lambda$λ足够小时，这个就类似于硬间隔支持向量机。
2、对每个样本引入一个松弛变量$ξ_i≥0$ξi​≥0，这样约束条件变为：
${{{y}}_i}*({{\mathbf{w}}^{\rm T}} \cdot {\mathbf{x}_i} + {\mathbf{b}})≥1-ξ_i$yi​∗(wT⋅xi​+b)≥1−ξi​
目标函数则变为：
$\mathop {\min }\limits_{w,b,ξ}\quad \frac{1}{2}{\left\| {\mathbf{w}} \right\|}^2+C\sum\limits_{i = 1}^n {{\xi _i}}$w,b,ξmin​21​∥w∥2+Ci=1∑n​ξi​
其中，C为惩罚函数，是调节二者的参数。目标函数有两层含义：

• margin尽量大
• 误分类的样本点计量少

详细参见：https://www.cnblogs.com/en-heng/p/5965438.html

Part 2 非线性分类

对与非线性可分数据，将数据投影到一个线性可分的空间，然后在那个空间寻找超平面！即

1、首先使用一个非线性映射将数据变换到一个特征空间F，
2、然后在特征空间使用线性学习器分类。

在用SVM处理问题时，如果数据线性不可分，希望通过 将输入空间内线性不可分的数据 映射到 一个高维的特征空间内，使数据在特征空间内是线性可分的，这个映射记作 $ϕ(x)$ϕ(x)，之后优化问题中就会有内积 $ϕi⋅ϕj$ϕi⋅ϕj，这个内积的计算维度会非常大，因此引入了核函数， kernel 可以帮我们很快地做一些计算, 否则将需要在高维空间中进行计算。

1、核函数形式 K(x, y) = <f(x), f(y)>，
2、其中 x, y 为 n 维，f 为 n 维到 m 维的映射，<f(x), f(y)> 表示内积。

一些常见的核函数包括：

核函数	用处	公式
linear kernel	线性可分时，特征数量多时，样本数量多再补充一些特征时，linear kernel可以是RBF kernel的特殊情况	$K(x_i,x_j)=x_i^Tx_j$K(xi​,xj​)=xiT​xj​
Polynomial kernel	image processing，参数比RBF多，取值范围是(0,inf)	$K(x_i,x_j)=(\gamma x_i^Tx_j+r)^d,d>1$K(xi​,xj​)=(γxiT​xj​+r)d,d>1
Gaussian radial basis function (RBF)	通用，线性不可分时，特征维数少 样本数量正常时，在没有先验知识时用，取值在[0,1]	$K(\mathbf{x}_i,\mathbf{x}_j)=exp(-\gamma {\left\| {\mathbf{x_i-x_j}} \right\|}^2)$K(xi​,xj​)=exp(−γ∥xi​−xj​∥2)
Sigmoid kernel	生成神经网络，在某些参数下和RBF很像，可能在某些参数下是无效的	$k(x,y)=tanh(\alpha x^Ty+c)$k(x,y)=tanh(αxTy+c)
Gaussian kernel	通用，在没有先验知识时用	$k(x,y)=exp(-\frac{{\left\| {{x-y}} \right\|}^2}{2\sigma ^2 })$k(x,y)=exp(−2σ2∥x−y∥2​)
Laplace RBF kernel	通用，在没有先验知识时用	$k(x,y)=exp(-\frac{\left\|x-y\right\|}{\sigma})$k(x,y)=exp(−σ∥x−y∥​)
Hyperbolic tangent kernel	neural networks中用	$K(x_i,x_j)=tanh(kx_i \cdot x_j+c)$K(xi​,xj​)=tanh(kxi​⋅xj​+c)
Bessel function of the first kind Kernel	可消除函数中的交叉项	$k(x,y)=\frac{J_{v+1}(\sigma {\left\| {{x-y}} \right\|})}{ {\left\| {{x-y}} \right\|}^{-n(v+1)} }$k(x,y)=∥x−y∥−n(v+1)Jv+1​(σ∥x−y∥)​
ANOVA radial basis kernel	回归问题	$k(x,y)=\sum\limits_{k = 1}^n {\exp {{( - \sigma {{({x^k} - {y^k})}^2})}^d}}$k(x,y)=k=1∑n​exp(−σ(xk−yk)2)d
Linear splines kernel in one-dimension	text categorization，回归问题，处理大型稀疏向量	$k(x,y) = 1 + xy + xy\min (x,y) - \frac{{x + y}}{2}\min {(x,y)^2} + \frac{1}{3}\min {(x,y)^3}$k(x,y)=1+xy+xymin(x,y)−2x+y​min(x,y)2+31​min(x,y)3

调参

在 sklearn 中可以用 grid search 找到合适的 kernel，以及它们的 gamma，C 等参数。
其中有两个重要的参数，即 C（惩罚系数） 和 $\gamma$γ， $\gamma$γ越大，支持向量越少，$\gamma$γ越小，支持向量越多。 而支持向量的个数影响训练和预测的速度。 C 越高，容易过拟合。C 越小，容易欠拟合。