引言

——“举牌子：Support Vector Machines ”

• 一直在犹豫要不要写SVM，因为网上已经有很多详细的SVM原理的解释甚至详细推导，而这东西又庞大复杂，想了解的话直接可以参考。说实话，SVM确实到现在也不是说很懂，感觉最恐怖的是对偶问题后的KKT推导、Mercer定理以及最后的参数求解。随便拿出来一个都是及其晦涩的数学问题。无奈水平不行，只能囫囵吞枣。
• 之所以决定要敲一下SVM的知识，大概是觉得从头到尾写一遍心里才踏实。将来回头看看，自己好像“用心”学过一遍SVM的样子。毕竟这辈子能学几个SVM呢？
• 最后一点，也是最能说服自己的一点，就是想近距离探索SVM的数学之美，向SVM的创始人及研究者致敬，向网络上的写过SVM的博主们学习。
• 下面就进入这个被冠以“迄今为止最强有监督学习分类器”、“让应用数学家真正得到应用”以及“某届G20会场外，被外国小哥高举的Support…”等称号的**机器学习算法——SVM。

---

初识SVM

• 关于SVM最早的一篇文章是由 Bernhard E. Boser等人在1992年发表的A training algorithm for optimal margin classifiers，感兴趣可以拜读一下这篇文章。瞻仰一下0.0（数据挖掘：理论与算法PPT中摘的图，图中引用数据截至2016）：
  
  
• 简单的概括SVM：就是寻找具有最大边缘（间隔）的超平面，位于间隔里面的平行的超平面，都能实现对数据点的线性可分。同时，面对线性不可分的情况，需要适当放宽这个间隔，引入软间隔和松弛因子。而面对更复杂的低维线性不可分的情况，通过使用核函数将数据点映射到高维，进行寻找超平面进行划分。
• 初识SVM主要介绍最大边缘超平面以及支持向量的概念。

---

1. 从线性分类器到最大边缘超平面

(1) 线性分类器

• 对于一个二维空间线性可分问题如下图所示：

• 解决上图蓝点和红圈的二分类问题，就是要找到一个超平面 w⃗ ⋅x⃗ +b=0$\overrightarrow{w}\cdot \overrightarrow{x}+b=0$使得：
  {w⃗ ⋅x⃗ +b>0x⃗ ∈{红圈数据点}w⃗ ⋅x⃗ +b>0x⃗ ∈{蓝圈数据点}$$\{\begin{array}{r}\overrightarrow{w}\cdot \overrightarrow{x}+b>0\overrightarrow{x}\in \{红圈数据点\}\\ \overrightarrow{w}\cdot \overrightarrow{x}+b>0\overrightarrow{x}\in \{蓝圈数据点\}\end{array}$$
  其中，w⃗ ⋅x⃗ =∑iwixi$\overrightarrow{w}\cdot \overrightarrow{x}=\sum _i{w}_i{x}_i$表示向量w⃗ =(w1,w2)$\overrightarrow{w}=(w_1,w_2)$ 与x⃗ =(x1,x2)$\overrightarrow{x}=(x_1,x_2)$ 内积，这里的数据点用向量x⃗ $\overrightarrow{x}$形式表示。向量w⃗ $\overrightarrow{w}$的方向与超平面垂直。简单证明：设超平面上有两个点x⃗ 1,x⃗ 2${\overrightarrow{x}}_1,{\overrightarrow{x}}_2$，则{w⃗ ⋅x⃗ 1+b=0=w⃗ ⋅x⃗ 2+b}⇒w⃗ ⋅(x⃗ 1−x⃗ 2)=0$\{\overrightarrow{w}\cdot {\overrightarrow{x}}_1+b=0=\overrightarrow{w}\cdot {\overrightarrow{x}}_2+b\}\Rightarrow \overrightarrow{w}\cdot ({\overrightarrow{x}}_1-{\overrightarrow{x}}_2)=0$，即向量w⃗ $\overrightarrow{w}$与超平面垂直。
• 该超平面与分类判决准则可以构成一个线性分类器：
  f(x,w,b)=sign(g(x))=sign(w⋅x+b)$$f(x,w,b)=sign(g(x))=sign(w\cdot x+b)$$
  其中，sign(⋅)$sign(\cdot )$表示符号函数。注：为了方便起见，从这里开始w$w$和x$x$分别表示向量w⃗ $\overrightarrow{w}$和x⃗ $\overrightarrow{x}$（不想每次都要敲\vec -.-，前面那样写主要是想说一下w$w$的方向问题。）

(2) 点到超平面的距离

• 设二维空间存在一个超平面实现二类可分如下图所示：
  

  

• 图中的斜线表示超平面g(x)=w⋅x+b=0$g(x)=w\cdot x+b=0$，二维平面上一点X$X$在超平面的距离投影为X′$X^{\prime }$，则二者关系可表示为X=X′+λw（w表示超平面的梯度向量也就是(1)中的w⃗ ）$X=X^{\prime }+\lambda w（w表示超平面的梯度向量也就是(1)中的\overrightarrow{w}）$。将X$X$带入到g(x)$g(x)$得：

  g(X)=w⋅X+b=w⋅(X′+λw)+b=w⋅X′+b+λw⋅w=0+λw⋅w=λw⋅w$$\begin{array}{rl}g(X)& =w\cdot X+b\\ & =w\cdot (X^{\prime }+\lambda w)+b\\ & =w\cdot X^{\prime }+b+\lambda w\cdot w\\ & =0+\lambda w\cdot w=\lambda w\cdot w\end{array}$$

• 点到超平面的距离即是X$X$与X′$X^{\prime }$之间的距离：

  ||X−X′||=||λw||=|g(X)|w⋅w⋅||w||=|g(X)|||w||$$||X-X^{\prime }||=||\lambda w||=\frac{|g(X)|}{w\cdot w}\cdot ||w||=\frac{|g(X)|}{||w||}$$
  该公式也就是高等数学中的点到平面的距离公式，只不过这里点和平面表达式的系数都用向量表示了。这里没有从函数间隔和几何间隔的角度引入距离。同理直接带入原点坐标可得原点到超平面的距离为|b|||w||$\frac{|b|}{||w||}$。

(2) 最大边缘超平面

• 对于二分类问题，我们的目的就是寻找一个超平面能够实现能正确地进行划分。对于有限的训练集（数据点集）而言，存在无数个这样的超平面。
• 而有的超平面虽然能够对测试集进行很好的划分，但会出现测试数据明明很靠近一个正类却被划分到负类的情况出现。
• 因此我们要选择一个最好的超平面，在划分的时候，不偏不倚，留足两边的空余，从而达到均衡地划分。继而该超平面应用在测试集上时，能够实现稳定平衡地划分，而该平面则被称为最大边缘超平面，所谓边缘就是超平面两边的空余。如下图所示：

• 

• 下面来定量地求这个边缘宽度，假设二维空间存在二分类的数据点，设g(x)=w⋅x+b$g(x)=w\cdot x+b$，对于下图而言：

• 设正类(yi=+1$y_i=+1$)为红色数据点满足g(x)=w⋅xi+b≥1$g(x)=w\cdot x_i+b\ge 1$，负类(yi=−1$y_i=-1$)为蓝色数据点满足g(x)=w⋅xi+b≤−1$g(x)=w\cdot x_i+b\le -1$。设分类超平面为g(x)=w⋅x+b=0$g(x)=w\cdot x+b=0$，则边界上的点到该分类超平面的距离之和为|1|||w||+|−1|||w||=2||w||$\frac{|1|}{||w||}+\frac{|-1|}{||w||}=\frac{2}{||w||}$。我们要求使得该距离之和最大的一组超平面参数。则整个过程用数学公式描述为：
  max2||w||s.t.  yi(w⋅xi+b)≥1$$\begin{gathered} max\frac{2}{||w||} \\ s.t.y_i(w\cdot x_i+b)\ge 1 \end{gathered}$$
  问题等价于
  min 12||w||2s.t.  yi(w⋅xi+b)≥1$$\begin{gathered} min\frac{1}{2}||w|{|}^2 \\ s.t.y_i(w\cdot x_i+b)\ge 1 \end{gathered}$$
  显然，这是个带有约束条件的求极值问题，问题求解在后面。

---

2. 从线性不完全可分到软间隔与松弛变量

(1) 线性不完全可分

• 线性不完全可分（这其实是自己理解的说法）：由于噪声存在或者数据本身分布有偏差（异常分布的点），现实中大多数情况下，很难实现二类问题的完美划分。如下图所示：
• 
• 图中，我们很难找到（或者说不存在）一个具有最大边缘(max margin)能够实现红蓝数据点完全分隔且最大间隔内没有数据点分布的超平面。从而造成原来的约束条件无法被满足，无法求解。

(2) 软间隔与松弛变量

• 针对线性不完全可分的问题，需要引入软间隔(soft margin)的概念：在原来的约束条件上加上一个参数适当放宽原判别准则（限制条件）：
  yi(w⋅xi+b)≥1−ξi$$y_i(w\cdot x_i+b)\ge 1-{\xi }_i$$
  其中，ξi≥0${\xi }_i\ge 0$称为松弛变量。相应地，由于引入了松弛变量，目标函数也得到改变：
  Φ(w)=12||w||2+C∑iξi$$\mathrm{\Phi }(w)=\frac{1}{2}||w|{|}^2+C\sum _i{\xi }_i$$
  其中，C∑iξi$C\sum _i{\xi }_i$为惩罚函数项，对一个异常的点的惩罚（函数）就是这个点到其正确位置（分类判决边界）的距离 （如下图所示）：
  
  
• C$C$为惩罚因子表示异常分布的点对目标函数的贡献权重，C越大表示异常分布的点对目标函数Φ(w)$\mathrm{\Phi }(w)$的影响就越大，使得目标函数对异常分布点的惩罚就越大。
• 因为我们需要12||w||2$\frac{1}{2}||w|{|}^2$尽可能小，同时误分类的异常点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。
• 更多关于软间隔的理解与知识见参考资料。
• 至此，我们同样需要求解一个带约束条件的求极值问题：
  min  12||w||2+C∑iξis.t.  yi(w⋅xi+b)≥1−ξiξi≥0$$\begin{array}{rl}& min\frac{1}{2}||w|{|}^2+C\sum _i{\xi }_i\\ & s.t.y_i(w\cdot x_i+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0\end{array}$$

---

3. 从线性不可分到特征空间映射与核函数

(1) 线性不可分

• 线性不可分定义就不说了直接上图0.0：
  
  
• 对于上图的二分类数据点，普通线性分类器不行，最大间隔超平面和软间隔超平面也无能为力。
• 面对这样的线性不可分问题，通常的思路是找出一个非线性分类边界（比如组合分类器）来实现分类。
• SVM则另辟蹊径，将数据点从原始空间映射到特征空间，而数据在特征空间往往就能实现线性可分。

(2) 特征空间映射

• 原始空间的线性不可分的数据点，经过映射函数φ(x)$\phi (x)$到特征空间（往往是低维到高维的映射），往往就能实现线性可分。下面用图举例说明：
• ① 一维空间向二维空间映射
  
  
• 上图，一维空间不可分，映射到二维空间y=x2$y=x^2$就可以找到一条直线，实现二类完全可分。
• ② 二维空间向二维特征空间映射
• 
• 上图，二维空间不可分，但变换一下坐标空间，也能实现线性可分。
• ③ 二维空间向三维空间的映射
  
  
• ②中的二维空间数据点也能映射到三维空间，同样可以找到一个超平面能够实现在三维空间的线性可分。

(3) 核函数

• 原始空间向特征空间的映射需要借助映射函数φ(x)$\phi (x)$。例如对于数据点xi$x_i$，映射到特征空间就变成了φ(xi)$\phi (x_i)$。而SVM的一大巧妙之处就是映射后的特征空间数据点内积的计算等价于低维空间数据点在映射函数对应的核函数中的计算。
• 这大大降低了运算量，因为有的时候高维空间的计算很复杂，下图是一个将m$m$维向量的映射到特征空间的映射函数的例子：
• 

• 映射后的维度大概是m22$\frac{m^2}{2}$维。则计算映射后的数据内积Φ(xi)T⋅Φ(xj)$\mathrm{\Phi }(x_i{)}^T\cdot \mathrm{\Phi }(x_j)$的时间复杂度为O(n2)$O(n^2)$。而如果使用核函数，则计算复杂度会降低为O(n)$O(n)$，例如：

  K(a,b)=(aT⋅b+1)2=Φ(a)T⋅Φ(b)$$K(a,b)=(a^T\cdot b+1{)}^2=\mathrm{\Phi }(a{)}^T\cdot \mathrm{\Phi }(b)$$
  ，其中a,b$a,b$为m$m$维的向量，Φ(a)$\mathrm{\Phi }(a)$为a$a$经过上面的映射函数后的m22$\frac{m^2}{2}$维向量，看以看出核函数K(a,b)=(aT⋅b+1)2$K(a,b)=(a^T\cdot b+1{)}^2$计算的时间复杂度为O(n)$O(n)$。后面会举例加以说明。

• 常用的核函数主要有：

• ① 多项式核函数：
  K(xi,xj)=(xi⋅xj+1)d$$K(x_i,x_j)=(x_i\cdot x_j+1{)}^d$$
  该核函数对应的映射函数为前面的Φ(x)$\mathrm{\Phi }(x)$，一个n$n$维的向量映射后的特征空间向量Φ(x)$\mathrm{\Phi }(x)$的维度为Cdn+d$C_{n+d}^d$。
• ② 高斯核函数：
  K(xi,xj)=exp(−||xi−xj||22σ2)$$K(x_i,x_j)=exp\left(-\frac{||x_i-x_j|{|}^2}{2{\sigma }^2}\right)$$
  当xi$x_i$和xj$x_j$很接近时，核函数的值约为1；相差很大时，核函数的值约为0。高斯核函数又称为径向基函数。能把原始有限维空间的向量映射到无穷维的特征空间。
• ③ S型核函数：
  K(xi,xj)=tanh(kxi⋅xj+c)$$K(x_i,x_j)=tanh(k{x}_i\cdot x_j+c)$$
  类比高斯核函数能够描述两个向量之间的相似度（0~1之间）。双曲正弦函数tanh(⋅)$tanh(\cdot )$（双极性sigmoid函数）也能作为核函数。同样地，也存在单极性sigmoid核函数。
• 还有很多其他的核函数，Mercer定理可以判断核函数的有效性。如果我们能够判断出核函数是有效的，甚至不需考虑与之对应的特征映射的函数Φ(x)$\mathrm{\Phi }(x)$(实际上Φ(x)$\mathrm{\Phi }(x)$很难求)，就能解决特征空间向量的内积的问题。

---

探索SVM数学之美

• 前面已经大概了解了SVM工作的基本原理，进一步了解SVM的工作原理以及求解问题，则需要深入探索SVM的数学原理。事实上，SVM中有很多晦涩难懂的数学知识，同时也有着让人拍案叫绝的数学推导。
• 下面将介绍SVM的基本数学推导及求解步骤，具体深层次的数学问题可以看附的参考资料。

---

线性可分问题的SVM求解

(1) 原始问题转化成对偶问题

• 在线性可分的SVM问题中，我们需要解决一个带有约束条件的求极值问题：
  min  12||w||2s.t.  yi(w⋅xi+b)≥1$$\begin{array}{rl}& min\frac{1}{2}||w|{|}^2\\ & s.t.y_i(w\cdot x_i+b)\ge 1\end{array}$$
• 带有约束条件（等式约束）的求极值问题一般使用拉格朗日乘法。而上述问题的约束条件含有不等式，则需要将原问题转化为带有KKT条件的广义拉格朗日乘法的对偶问题。主要过程如下：
• 将约束条件表示为h(x)=−yi(w⋅xi+b)+1≤0$h(x)=-y_i(w\cdot x_i+b)+1\le 0$，原问题的拉格朗日乘法表达式为：
  LP(w,b,α)=12||w||2+αh(x)=12||w||2−∑iαiyi(w⋅xi+b)+∑iαi$$\begin{array}{rl}{L}_P(w,b,\alpha )& =\frac{1}{2}||w|{|}^2+\alpha h(x)\\ & =\frac{1}{2}||w|{|}^2-\sum _i{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _i{\alpha }_i\end{array}$$
  求原问题LP$L_P$的极小值，分别对w$w$和b$b$求导得：
  ∂LP∂w=w−∑iαiyixi=0⇒w=∑iαiyixi∂LP∂b=∑iαiyi=0$$\begin{array}{rl}& \frac{\mathrm{\partial }{L}_P}{\mathrm{\partial }w}=w-\sum _i{\alpha }_i{y}_i{x}_i=0\Rightarrow w=\sum _i{\alpha }_i{y}_i{x}_i\\ & \frac{\mathrm{\partial }{L}_P}{\mathrm{\partial }b}=\sum _i{\alpha }_i{y}_i=0\end{array}$$
  带回LP$L_P$得到相应得对偶问题LD$L_D$：
  LD(α)=∑iαi−12∑i,jαiαjyiyj(xi)Txj$$L_D(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i{)}^T{x}_j$$
  满足的KKT$KKT$条件为:
     αi≥0(1)∑iαih(xi)=0(2) h(xi)≤0(3)$$\begin{array}{rl}& {\alpha }_i\ge 0(1)\\ & \sum _i{\alpha }_{i}h(x_i)=0(2)\\ & h(x_i)\le 0(3)\end{array}$$
  同时，LD$L_D$也受约束于
  ∑iαiyi=0$$\sum _i{\alpha }_i{y}_i=0$$
  此时，由原问题LP$L_P$关于w$w$和b$b$求极小值转化为对偶问题LD$L_D$关于α$\alpha$求极大值。且LD$L_D$只包含变量αi${\alpha }_i$。

(2) 引入支持向量求解w$w$和b$b$

• 根据对偶问题以及约束条件，求出αi${\alpha }_i$即可得到w$w$和b$b$，到这里我们就需要引入支持向量了。所谓支持向量就是分布在分类判决超平面（w⋅xs+b=±1$w\cdot x_s+b=\pm 1$）的点xs$x_s$（用向量表示）。可以形象地理解为支撑了两个用于分类判决的超平面。
• 支持向量能够简化w$w$和b$b$的计算， 从KKT条件可得，只有支持向量xs$x_s$对应的αi>0${\alpha }_i>0$，其他数据点xi$x_i$对应的αi${\alpha }_i$都为0。因此计算时只需考虑支持向量：
  w=∑iαiyixi=∑s∈Sαsysxs$$w=\sum _i{\alpha }_i{y}_i{x}_i=\sum _{s\in S}{\alpha }_s{y}_s{x}_s$$
  其中，S$S$为支持向量的集合。
• 对于b$b$：
  取个平均值：ys(w⋅xs+b)=1ys(∑k∈SαkykxTk⋅xs+b)=1y2s(∑k∈SαkykxTk⋅xs+b)=ysb=ys−∑k∈SαkykxTk⋅xsb=1|S|∑s∈S(ys−∑k∈SαkykxTk⋅xs)$$\begin{array}{rl}& y_s(w\cdot x_s+b)=1\\ & y_s(\sum _{k\in S}{\alpha }_k{y}_k{x}_k^T\cdot x_s+b)=1\\ & y_s^2(\sum _{k\in S}{\alpha }_k{y}_k{x}_k^T\cdot x_s+b)=y_s\\ & b=y_s-\sum _{k\in S}{\alpha }_k{y}_k{x}_k^T\cdot x_s\\ 取个平均值：& b=\frac{1}{|S|}\sum _{s\in S}(y_s-\sum _{k\in S}{\alpha }_k{y}_k{x}_k^T\cdot x_s)\end{array}$$
• 下面考虑一个简单的计算例子：
  
• 图中我们已知两个支持向量x1=(1,1),x2=(0,0)$x_1=(1,1),x_2=(0,0)$，对应的类别值分别为y1=+1,y2=−1$y_1=+1,y_2=-1$。则根据原问题的约束条件得:
  ∑i=12αiyi=0⇒α1=α2(1)$$\sum _{i=1}^2{\alpha }_i{y}_i=0\Rightarrow {\alpha }_1={\alpha }_2(1)$$
  考虑对偶问题：
  LD=∑i=12αi−12∑i,j=12αiαjyiyj(xi)Txj=α1+α2−α2=2α1−α21$$L_D=\sum _{i=1}^2{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^2{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i{)}^T{x}_j={\alpha }_1+{\alpha }_2-{\alpha }^2=2{\alpha }_1-{\alpha }_1^2$$
  对LD$L_D$求极大值，则得α1=α2=1${\alpha }_1={\alpha }_2=1$。
• 带入求w$w$和b$b$：
  w=∑i=12αiyixi=(1,1)b=−w⋅x1+1=−1$$\begin{gathered} w=\sum _{i=1}^2{\alpha }_i{y}_i{x}_i=(1,1) \\ b=-w\cdot x_1+1=-1 \end{gathered}$$
• 从而得到最大边缘超平面为：
  g(x)=w⋅x+b=x1+x2−1=0$$g(x)=w\cdot x+b=x_1+x_2-1=0$$
• 最大边缘间隔为：M=2||w||=2–√$M=\frac{2}{||w||}=\sqrt{2}$
• 这只是一个简单的示例，而且问题中只出现了支持向量对应的数据点，没有包含其他数据点。实际问题中求解很复杂，包含其他数据点具体求解αi${\alpha }_i$需要用到SMO算法，这里不再展开。 另外关于拉格朗日对偶问题的转化更多详细信息见参考资料。

(3) 使用SVM判别未知数据点

• 还剩下一个问题，当我们计算出了αi${\alpha }_i$，使用SVM判别一个新数据点x∗$x^{\ast }$的分类，需要计算出w$w$吗？答案是否定的，只需计算：
  y∗=w⋅x∗+b=∑s∈SαsysxTsx∗+b=∑s∈Sαsys⟨xs,x∗⟩+b$$\begin{array}{rl}{y}^{\ast }=w\cdot x^{\ast }+b& =\sum _{s\in S}{\alpha }_s{y}_s{x}_s^T{x}^{\ast }+b\\ & =\sum _{s\in S}{\alpha }_s{y}_s⟨x_s,x^{\ast }⟩+b\end{array}$$
  其中，⟨xs,x∗⟩$⟨x_s,x^{\ast }⟩$表示内积计算。
• 该计算说明，给定一个新的数据点x∗$x^{\ast }$(向量表示)，我们只需计算其与支持向量的内积以及其他必要的计算。就能得出其分类判别值y∗$y^{\ast }$，从而判断其所属类别。

---

带有软间隔的SVM求解

(1) 原始问题转化成对偶问题

• 对于线性不完全可分的软间隔SVM，同样需要求解一个带约束条件的求极值问题：
  min  12||w||2+C∑iξis.t.  yi(w⋅xi+b)≥1−ξiξi≥0$$\begin{array}{rl}& min\frac{1}{2}||w|{|}^2+C\sum _i{\xi }_i\\ & s.t.y_i(w\cdot x_i+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0\end{array}$$
  将约束条件表示为
  {h(x,w,b)=−yi(w⋅xi+b)+1−ξi≤0f(ξ)=−ξi≤0$$\{\begin{array}{rl}& h(x,w,b)=-y_i(w\cdot x_i+b)+1-{\xi }_i\le 0\\ & f(\xi )=-{\xi }_i\le 0\end{array}$$
  利用拉格朗日乘法得到的一个原始问题为：
  LP(w,b,ξ,α,β)=12||w||2+C∑iξi−∑iαi[yi(w⋅xi+b)−1+ξi]−∑iβiξi$$L_P(w,b,\xi ,\alpha ,\beta )=\frac{1}{2}||w|{|}^2+C\sum _i{\xi }_i-\sum _i{\alpha }_i[y_i(w\cdot x_i+b)-1+{\xi }_i]-\sum _i{\beta }_i{\xi }_i$$
  对LP$L_P$求极(小)值得：
  ∂LP∂w=0⇒w=∑iαiyixi∂LP∂b=0⇒∑iαiyi=0∂LP∂ξi=0⇒C=αi+βi$$\begin{array}{rl}& \frac{\mathrm{\partial }{L}_P}{\mathrm{\partial }w}=0\Rightarrow w=\sum _i{\alpha }_i{y}_i{x}_i\\ & \frac{\mathrm{\partial }{L}_P}{\mathrm{\partial }b}=0\Rightarrow \sum _i{\alpha }_i{y}_i=0\\ & \frac{\mathrm{\partial }{L}_P}{\mathrm{\partial }{\xi }_i}=0\Rightarrow C={\alpha }_i+{\beta }_i\end{array}$$
  带回LP$L_P$将原始问题转化为对偶问题LD$L_D$得：
  LD(α)=∑iαi−12∑i,jαiαjyiyjxTixj$$L_D(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$
  约束条件为：
  s.t.  C≥αi≥0∑iαiyi=0$$\begin{array}{rl}s.t.& C\ge {\alpha }_i\ge 0\\ & \sum _i{\alpha }_i{y}_i=0\end{array}$$
  这与不带惩罚函数以及软间隔的线性可分SVM的对偶问题及其相似，唯一的不同就是约束条件αi${\alpha }_i$多了（C≥αi$C\ge {\alpha }_i$）的限制。
• 由KKT条件得：
  ⎧⎩⎨⎪⎪αi=0  ⇒  yi(w⋅xi+b)≥1（1）αi=C  ⇒  yi(w⋅xi+b)≥1（2）0<αi<C  ⇒  yi(w⋅xi+b)=1（3）$$\{\begin{array}{rl}& {\alpha }_i=0\Rightarrow y_i(w\cdot x_i+b)\ge 1（1）\\ & {\alpha }_i=C\Rightarrow y_i(w\cdot x_i+b)\ge 1（2）\\ & 0<{\alpha }_i<C\Rightarrow y_i(w\cdot x_i+b)=1（3）\end{array}$$
  上式(1)表明，在两个分类判决超平面外的数据点的αi=0${\alpha }_i=0$；而位于间隔内的异常点的αi=C${\alpha }_i=C$；最后位于两个分类判决超平面的数据点即支持向量的0<αi<C$0<{\alpha }_i<C$。因此，在后续计算w$w$和b$b$的时候主要考虑支持向量以及位于软间隔内的异常数据点。

(2) SMO算法求解对偶问题

• 上面通过对原问题LP$L_P$的求极小值，转变成了一个求极大值的对偶问题LD$L_D$。即求解使得LD$L_D$最大的一系列αi${\alpha }_i$的值。
• LD$L_D$包含一簇未知数，普通的求极值方法并不适用该问题，所以我们需要借助一些算法工具。SMO算法能够有效地求解该对偶问题。
• SMO算法Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。
• 关于SMO算法的具体工作原理这里不在展开，参考资料有两篇文章讲的很详细能够帮助更好的理解SMO算法。

---

线性不可分问题的SVM求解

(1) 特征空间的内积计算

• 前面已经提到，SVM在处理线性不可分问题时，把原始空间的数据点映射到特征空间，然后就能够通过在特征空间寻找一个超平面将特征空间里的数据点进行线性可分。
• 而从前面线性可分SVM以及带有软间隔SVM求解可知，无论是求解对偶问题，求解超平面关键参数w$w$和b$b$，以及对未知新数据点x∗$x^{\ast }$的类别判别。都牵扯到一个关键的计算xTi⋅xj$x_i^T\cdot x_j$，即所谓的内积计算⟨xi,xj⟩$⟨x_i,x_j⟩$。
• 同样地，当数据点xi,xj$x_i,x_j$通过映射函数φ(⋅)$\phi (\cdot )$映射到特征空间得到特征（高维）数据点φ(xi),φ(xj)$\phi (x_i),\phi (x_j)$时，也需要进行内积运算。实际上，将数据点映射到特征空间的求解和线性可分SVM相同。关键的一步就是特征空间的内积计算。

• 而前面同样也提到，SVM的一点巧妙之处就是能够利用核函数，把特征（一般是高维）空间的内积计算转变为在原始低维空间内数据点的计算，从而大大降低的运算复杂度。

• 下面举简例说明核函数的简化计算：

• 假设原始二维空间有两个数据点a=(a1,b1)，b=(b1,b2)$a=(a_1,b_1)，b=(b_1,b_2)$，映射函数为φ(x)=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢12–√x12–√x2x21x22–√x1x2⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥$\phi (x)=\left[\begin{array}{r}1\\ \sqrt{2}{x}_1\\ \sqrt{2}{x}_2\\ x_1^2\\ x^2\\ \sqrt{2}{x}_1{x}_2\end{array}\right]$，则经过映射后，a$a$和b$b$在特征空间的数据点为φ(a)=[1,2–√a1,2–√a2,a21,a22,2–√a1a2]T,φ(b)=[1,2–√b1,2–√b2,$\phi (a)=[1,\sqrt{2}{a}_1,\sqrt{2}{a}_2,a_1^2,a_2^2,\sqrt{2}{a}_1{a}_2{]}^T,\phi (b)=[1,\sqrt{2}{b}_1,\sqrt{2}{b}_2,$ b21,b22,2–√b1b2]T$b_1^2,b_2^2,\sqrt{2}{b}_1{b}_2{]}^T$。
• 特征空间的内积计算为：
  φ(a)T⋅φ(b)=1+2a1b1+2a2b2+(a1b1)2+(a2b2)2+2a1a2b1b2=1+2a1b1+2a2b2+(a1b1+a2b2)2$$\begin{array}{rl}\phi (a{)}^T\cdot \phi (b)& =1+2a_1{b}_1+2a_2{b}_2+(a_1{b}_1{)}^2+(a_2{b}_2{)}^2+2a_1{a}_2{b}_1{b}_2\\ & =1+2a_1{b}_1+2a_2{b}_2+(a_1{b}_1+a_2{b}_2{)}^2\end{array}$$
• 从前面多项式核函数可知，该映射函数对应的核函数为K(xi,xj)=(1+xTi⋅xj)2$K(x_i,x_j)=(1+x_i^T\cdot x_j{)}^2$，则：
  K(a,b)=(1+([a1,b1]⋅[b1b2]))2=(1+a1b1+a2b2)2=1+2a1b1+2a2b2+(a1b1+a2b2)2$$\begin{array}{rl}K(a,b)& =(1+([a_1,b_1]\cdot \left[\begin{array}{r}{b}_1\\ b_2\end{array}\right]){)}^2\\ & =(1+a_1{b}_1+a_2{b}_2{)}^2\\ & =1+2a_1{b}_1+2a_2{b}_2+(a_1{b}_1+a_2{b}_2{)}^2\end{array}$$
  从而得：
  φ(a)T⋅φ(b)=K(a,b)$$\phi (a{)}^T\cdot \phi (b)=K(a,b)$$
  由此可以看出，核函数可以利用原始空间的数据样本点内积来简化特征高维空间的内积计算。

(2) 特征空间对未知数据点的分类判别

• 将数据点从原始空间映射到特征空间以后，往往就会变得线性可分。这时可以按照映射过后的特征数据点去解决对偶问题，从而求解超平面的关键参数W$W$和B$B$。
• 假设求得特征（高维）空间的判决超平面为WTφ(x)+B=±1$W^T\phi (x)+B=\pm 1$，则对于一个未知原始空间的数据点x∗$x^{\ast }$该如何判别其所属类别值。需要将其带入映射函数φ(⋅)$\phi (\cdot )$，然后按照判决公式求解类别值吗？答案同样也是否定的。
• 事实上，有的时候φ(⋅)$\phi (\cdot )$无从所知或者很难知道其具体形式。所以，从φ(⋅)$\phi (\cdot )$出发求解则会非常麻烦。这时候，核函数就发挥关键作用了。
• 给定一个未知分类原始空间数据点x∗$x^{\ast }$，带入特征空间的分类判别公式得：
  WT⋅φ(x∗)+B=(∑iαiYiφ(xi))T⋅φ(x∗)+B=∑iαiYiφ(xi)T⋅φ(x∗)+B=∑iαiYiK(xi,x∗)+B$$\begin{array}{rl}{W}^T\cdot \phi (x^{\ast })+B& ={\left(\sum _i{\alpha }_i{Y}_i\phi (x_i)\right)}^T\cdot \phi (x^{\ast })+B\\ & =\sum _i{\alpha }_i{Y}_i\phi (x_i{)}^T\cdot \phi (x^{\ast })+B\\ & =\sum _i{\alpha }_i{Y}_{i}K(x_i,x^{\ast })+B\end{array}$$
  可以看出，类别值的最终判决结果只需在原始空间利用核函数即可计算出来，而无需考虑映射函数的参与。

---

敬畏SVM

——“人要常怀敬畏之心”

• 写到这里，关于支持向量机的大致内容算是完结了。这篇跨越五一假期的烂文总算是写完了0.0…..态度也由一开始的致敬变成了敬畏。之所以敬畏，是发现自己到现在还不算完全理解SVM，不仅仅敬畏SVM，同时敬畏经典的数学方法、敬畏复杂难懂的算法以及敬畏富有奇淫巧技的数学家。

---

难点整理

• 经过从头到尾摸索一遍SVM，大致懂了SVM的工作原理。但其中还有很多难点值得思考，由于时间和精力有限就不在深究。主要有3个难点令我印象深刻，这一点在参考资料中也有所体现：
• 一是拉格朗日乘法原始问题到对偶问题转变，以及随之产生的KKT条件。
• 二是关于软间隔的理解，惩罚函数的工作原理以及惩罚因子的确定问题。
• 三是结合KKT条件以及原始问题的约束条件的SMO算法求解问题。

总结与理解

• 这里就不总结复杂的计算原理了，也理解不了。。

• 从基本原理上进行理解和总结：

  • SVM或者从本质上说是线性SVM，其主要目的是寻找一个能够划分类别的（线性）超平面使得该超平面的两边的数据点（样本点）都属于一个类。
  • 对于在原始空间线性可分问题（包括线性完全可分和线性不完全可分），SVM通过有监督的方式利用原始数据样本点（或者说只是一些特殊的数据点：支持向量以及软间隔的异常样本点），去求解线性超平面的参数w$w$（w$w$其实也没必要求，只需求αi${\alpha }_i$）和b$b$。从而最终能够跟据判决分类超平面对未知分类的样本点进行分类。
  • 而对于原始空间线性不可分问题，通常将原始数据样本点映射到特征空间（一般是高维空间）中。然后在高维空间中寻找一个线性超平面，使得该超平面能够实现类别的划分。同时，引入核函数来简化映射后的数据点在高维空间的内积计算。而对于未知分类原始样本点，也能直接带入核函数结合高维空间的判决超平面最终得知其所属类别。

• 再抛去一层基本原理来理解SVM：

  • SVM(支持向量机)之所以称为支持向量机，大概是因为支持向量起到了最为关键的作用。 试想再偌大的样本点中，我们找到了一些分布在两类边界的样本点（支持向量），是不是基本就能确定剩余的样本点类别了。
  • SVM常常会被拿来和Logistic回归分类做比较，在我看来，SVM和Logistic虽说都是寻找一个线性分类界限，但出发点不一样。SVM是以训练集两个类的边界（支持向量）来考虑划分，而Logistic是从训练集的全局来考虑划分。这也就是为什么Logistic受噪声和离群点的影响比较大。当出现一个离群点时，Logistic划定的边界很有可能会改变。而SVM这边划分的边界却可能丝毫不动（因为你离群点并不影响我支持向量）。
  • 举个很形象的例子来理解SVM：楚汉相争，以楚河汉界为界。左边是刘邦的地盘，右边是项羽的地盘。假如我们原本不知道楚河汉界，怎么划定一个界限左边是刘邦的士兵而右边是项羽的士兵。最容易的方法就是找到两边的哨兵，找到了刘邦的哨兵，则可以判断出哨兵左边驻扎的士兵都是刘邦的。同理，项羽的哨兵右边驻扎的士兵都是项羽的。通常由哨兵划分的界限应该是双方能够拉扯的最大空间。这里哨兵即是支持向量，而双方所能拉扯的最大空间楚河汉界就是最大边缘超平面。
  • 不如就畅所欲言（瞎说0.0），假如有几个误入楚地的汉兵或者潜入楚地当间谍的汉兵。他们身在楚地心在汉，而对于他们而言，仅凭楚河汉界将他们断定为楚兵或楚人未免太苛刻了。他们内心在呐喊：“我们是汉兵（汉人），只不过身在楚地”。因此应该有一个放宽的界限或者说是他们内心的“楚河汉界”，来进行划分汉兵和楚兵。而这个放宽的界限或者说内心的“楚河汉界”就是所谓的软间隔。
  • 假如在楚河汉界还没形成之前，一群壮汉在一起准备参军，不知道谁去投靠刘邦谁去投靠项羽。或者一群楚兵和汉兵乔装混在一起，分不出哪个是刘邦的人，哪个是项羽的人。随着刘邦和项羽的一声令下，双方士兵快速分离聚拢，形成两军对阵的架势。这时候从中间画一条界限，就能很明显的划分出哪边是刘邦的人哪边是项羽的人。刘邦和项羽的一声令下就是所谓的映射函数。将汉兵和楚兵拉扯到战场上这个特征空间里。

---

参考资料

清华大学，袁博副教授：【数据挖掘：理论与算法】 课程
如何通俗地讲解对偶问题？尤其是拉格朗日对偶lagrangian duality？ - 彭一洋的回答 - 知乎
拉格朗日乘子法、KKT条件、拉格朗日对偶性
SVM支持向量机三（软间隔处理规则化和不可分情况）
支持向量机原理(二) 线性支持向量机的软间隔最大化模型
支持向量机（三）核函数
支持向量机（五）SMO算法
解密SVM系列（三）：SMO算法原理与实战求解