一、基本原理

给定训练样本集，学习的目标即是找到一个划分超平面，这个超平面可以通过线性方程 来描述。
对于样本点，若，则；若，则，令 即
样本空间中，任一点到超平面的距离为，距离超平面最近的几个样本点被称为支持向量(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

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