一排截、基本原理
給定訓(xùn)練樣本集嫌蚤，學(xué)習(xí)的目標(biāo)即是找到一個(gè)劃分超平面，這個(gè)超平面可以通過線性方程
來描述断傲。
對(duì)于樣本點(diǎn)脱吱，若
，則
认罩；若
箱蝠，則
，令
即
樣本空間中垦垂，任一點(diǎn)到超平面的距離為
宦搬，距離超平面最近的幾個(gè)樣本點(diǎn)被稱為支持向量(support vector)，使上述不等式成立劫拗，因此兩類支持向量的間隔(margin)為
间校。
支持向量機(jī)的目的是找到能夠正確劃分訓(xùn)練數(shù)據(jù)集的最大間隔的劃分超平面页慷，即
可重寫做
這是一個(gè)凸二次規(guī)劃問題(convex quadratic programming)憔足，最大間隔劃分超平面存在唯一性胁附。
為了更好求解上述最優(yōu)化問題，考慮其對(duì)偶問題滓彰，首先構(gòu)造拉格朗日函數(shù)：
其中控妻，
，
令
帶入原方程饼暑，則得到對(duì)偶問題
求出后稳析，即可求得模型為
上述過程需要滿足KKT條件洗做，即由上式可知，總有
或
彰居。這說明訓(xùn)練完成后诚纸，最終模型僅與支持向量有關(guān)。
二陈惰、算法實(shí)現(xiàn)
為簡(jiǎn)明起見畦徘，本文采用sklearn的svm包實(shí)現(xiàn)二分類問題。首先是二維線性可分問題抬闯，如下所示：
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()
下圖顯示了原始數(shù)據(jù)井辆、支持向量和劃分超平面，說明了SVM的分類效果溶握。
以下為二維線性不可分的情形杯缺，采用徑向基核函數(shù)，實(shí)現(xiàn)過程如下：
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()
下圖顯示了原始數(shù)據(jù)睡榆、支持向量和劃分超平面萍肆，說明了SVM的分類效果，之所以有些支持向量分布在外圍胀屿，是因?yàn)樵诟呔S空間中其與劃分超平面距離較近塘揣。
三、問題探討
3.1宿崭、序列最小優(yōu)化
可以看到最終得到的優(yōu)化問題是一個(gè)二次規(guī)劃問題亲铡，可以使用二次規(guī)劃算法求解，對(duì)于此問題更高效的做法是序列最小優(yōu)化(sequential minimial optimization, SMO)葡兑。
其基本思路是：先固定之外的參數(shù)奖蔓，求
的極值。由于存在約束
铁孵，若固定單個(gè)
之外的參數(shù)锭硼，
可由其他變量導(dǎo)出，因此每次選擇兩個(gè)變量
和
蜕劝，固定其他參數(shù)檀头，重復(fù)執(zhí)行以下步驟：1. 選取一對(duì)新的變量
和
轰异； 2. 固定
和
以外的參數(shù)，通過優(yōu)化方程計(jì)算得到更新后的
和
暑始。
由約束條件可以得出取值的意義：
對(duì)于第1種情況搭独，表明
是正常分類，在邊界內(nèi)部廊镜；
對(duì)于第2種情況牙肝，表明是支持向量，在邊界上
固定其他變量嗤朴，考慮和
時(shí)：
其中
是常數(shù)配椭。
將上式帶入到原優(yōu)化函數(shù)中，由于只有兩個(gè)變量和
雹姊，因此要求的目標(biāo)即變成優(yōu)化函數(shù)在如圖對(duì)角線上的最優(yōu)值股缸，實(shí)質(zhì)上使得兩變量的最優(yōu)化問題變?yōu)閱巫兞康淖顑?yōu)化問題。
3.2吱雏、核方法
對(duì)于一個(gè)線性可分的問題敦姻，可以用一條直線或者一個(gè)平面將其劃分，而對(duì)于非線性問題（例如異或問題）歧杏，就無法這樣劃分镰惦。一個(gè)解決的思路就是通過非線性變換，將非線性問題轉(zhuǎn)化為線性問題犬绒，核方法就是這樣的一個(gè)方法旺入。其基本想法是：使用一個(gè)變換將低維空間的數(shù)據(jù)映射到高維空間，在新空間中學(xué)習(xí)到超平面將數(shù)據(jù)線性可分懂更。
核函數(shù)就是一個(gè)從原空間到新空間的映射眨业，常見的核函數(shù)有：
線性核：
多項(xiàng)式核：
高斯核：
拉普拉斯核：
sigmiod核：
參考資料
[1] https://github.com/lawlite19/MachineLearning_Python
[2] 周志華 著. 機(jī)器學(xué)習(xí). 北京:清華大學(xué)出版社,2016
[3] 李航 著. 統(tǒng)計(jì)學(xué)習(xí)方法. 北京:清華大學(xué)出版社,2012
[4] 史春奇等 著. 機(jī)器學(xué)習(xí)算法背后的理論與優(yōu)化. 北京:清華大學(xué)出版社,2019
[5] Peter Harrington 著. 李銳等 譯. 機(jī)器學(xué)習(xí)實(shí)戰(zhàn). 北京:人民郵電出版社,2013
不見可欲，使心不亂沮协。 ——《老子》
