一、基本原理

给定训练样本集，学习的目标即是找到一个划分超平面，这个超平面可以通过线性方程 来描述。
对于样本点，若，则；若，则，令 即
样本空间中，任一点到超平面的距离为，距离超平面最近的几个样本点被称为支持向量(support vector)，使上述不等式成立，因此两类支持向量的间隔(margin)为。

划分超平面、支持向量与间隔
支持向量机的目的是找到能够正确划分训练数据集的最大间隔的划分超平面，即 可重写做 这是一个凸二次规划问题(convex quadratic programming)，最大间隔划分超平面存在唯一性。
为了更好求解上述最优化问题，考虑其对偶问题，首先构造拉格朗日函数： 其中，，令

带入原方程，则得到对偶问题
求出后，即可求得模型为
上述过程需要满足KKT条件，即由上式可知，总有或。这说明训练完成后，最终模型仅与支持向量有关。

二、算法实现

为简明起见，本文采用sklearn的svm包实现二分类问题。首先是二维线性可分问题，如下所示：

import numpy as np
import scipy.io as spio
import matplotlib.pyplot as plt
from sklearn import svm
datafile = 'data1.mat'

def svmLinear():
    data = spio.loadmat(datafile)
    X = data['X']
    y = data['y'].ravel()
    
    svm_linear = svm.SVC(C=1.0,kernel='linear').fit(X,y)
    plot_linearBoundary(X,y,svm_linear)
    
def plot_linearBoundary(X,y,model):
    class1 = np.where(y==1)
    class0 = np.where(y==0)
    plt.plot(X[class1,0].ravel(),X[class1,1].ravel(),'ro')
    plt.plot(X[class0,0].ravel(),X[class0,1].ravel(),'g*')
    plt.xlabel('x1')
    plt.ylabel('x2')
    plt.legend(['y=1','y=-1'])
    
    w = model.coef_
    b = model.intercept_
    xp = np.linspace(min(X[:,0]),max(X[:,0]),100)
    yp = -(w[0,0]*xp+b)/w[0,1]
    plt.plot(xp,yp,'b')
    sv = model.support_vectors_
    plt.scatter(sv[:,0],sv[:,1],s=150,c='none',alpha=0.7,edgecolor='black')
    plt.show()
if __name__ == '__main__':    
    svmLinear()

下图显示了原始数据、支持向量和划分超平面，说明了SVM的分类效果。

二维线性可分情形

以下为二维线性不可分的情形，采用径向基核函数，实现过程如下：

def svmKernel():
    data = spio.loadmat('data2.mat')
    X = data['X']
    y = data['y'].ravel()
    
    svm_notlinear = svm.SVC(C=10,gamma=200,kernel='rbf').fit(X,y)
    plot_notlinearBoundary(X,y,svm_notlinear)
    
def plot_notlinearBoundary(X,y,model):
    class1 = np.where(y==1)
    class0 = np.where(y==0)
    plt.plot(X[class1,0].ravel(),X[class1,1].ravel(),'ro')
    plt.plot(X[class0,0].ravel(),X[class0,1].ravel(),'g*')
    plt.xlabel('x1')
    plt.ylabel('x2')
    plt.legend(['y=1','y=-1'])
    
    x1 = np.linspace(min(X[:,0]),max(X[:,0]),100).reshape(1,-1).transpose()
    x2 = np.linspace(min(X[:,1]),max(X[:,1]),100).reshape(1,-1).transpose()
    X1,X2 = np.meshgrid(x1,x2)
    
    vals = np.zeros(X1.shape)
    for i in range(X1.shape[1]):
        X = np.hstack((X1[:,i].reshape(-1,1),X2[:,i].reshape(-1,1)))
        vals[:,i] = model.predict(X)
    plt.contour(X1,X2,vals,[0,1],color='b')
    sv = model.support_vectors_
    plt.scatter(sv[:,0],sv[:,1],s=150,c='none',alpha=0.7,edgecolor='black')
    plt.show()

if __name__ == '__main__':    
    svmKernel()

下图显示了原始数据、支持向量和划分超平面，说明了SVM的分类效果，之所以有些支持向量分布在外围，是因为在高维空间中其与划分超平面距离较近。

二维线性不可分情形

三、问题探讨

3.1、序列最小优化

可以看到最终得到的优化问题是一个二次规划问题，可以使用二次规划算法求解，对于此问题更高效的做法是序列最小优化(sequential minimial optimization, SMO)。
其基本思路是：先固定之外的参数，求的极值。由于存在约束，若固定单个之外的参数，可由其他变量导出，因此每次选择两个变量和，固定其他参数，重复执行以下步骤：1. 选取一对新的变量和； 2. 固定和以外的参数，通过优化方程计算得到更新后的和。
由约束条件可以得出取值的意义： 对于第1种情况，表明是正常分类，在边界内部；
对于第2种情况，表明是支持向量，在边界上
固定其他变量，考虑和时： 其中是常数。

SMO二变量优化问题

将上式带入到原优化函数中，由于只有两个变量和，因此要求的目标即变成优化函数在如图对角线上的最优值，实质上使得两变量的最优化问题变为单变量的最优化问题。

3.2、核方法

对于一个线性可分的问题，可以用一条直线或者一个平面将其划分，而对于非线性问题（例如异或问题），就无法这样划分。一个解决的思路就是通过非线性变换，将非线性问题转化为线性问题，核方法就是这样的一个方法。其基本想法是：使用一个变换将低维空间的数据映射到高维空间，在新空间中学习到超平面将数据线性可分。
核函数就是一个从原空间到新空间的映射，常见的核函数有：
线性核：
多项式核：
高斯核：
拉普拉斯核：
sigmiod核：

高斯核分类示意图

参考资料

[1] https://github.com/lawlite19/MachineLearning_Python
[2] 周志华 著. 机器学习. 北京:清华大学出版社,2016
[3] 李航 著. 统计学习方法. 北京:清华大学出版社,2012
[4] 史春奇等 著. 机器学习算法背后的理论与优化. 北京:清华大学出版社,2019
[5] Peter Harrington 著. 李锐等 译. 机器学习实战. 北京:人民邮电出版社,2013

不见可欲，使心不乱。 ——《老子》