@[拉格朗日乘子法|对偶问题|KKT条件|核函数|hinge损失]
存在多个超平面将样本划分的情况下，选择对训练样本局部扰动容忍性最好的。
间隔与支持向量划分超平面的法向量为w=(w1;w2;...;wd)w=(w1;w2;...;wd)，则超平面为wTx+b=0wTx+b=0。任一点x到超平面(w,b)距离为
r=∣∣wTx+b∣∣∥w∥.r=|wTx+b|‖w‖.
假设超平面将样本正确分类，则对于(xi,yi)∈D(xi,yi)∈D，若yi=+1yi=+1，有wTxi+b>0wTxi+b>0；若yi=−1yi=−1，有wTxi+b<0wTxi+b<0。令
{wTxi+b≥+1,wTxi+b≤−1,yi=+1yi=−1{wTxi+b≥+1,yi=+1wTxi+b≤−1,yi=−1
则wTx+b=±1wTx+b=±1为”支持向量“，支持向量间距离，即“间隔”为γ=2∥w∥γ=2‖w‖。
欲找到“最大间隔”的超平面，即最大化∥w∥−1‖w‖−1，等价于最小化∥w∥2‖w‖2。于是支持向量基的基本型为
min12∥w∥2min12‖w‖2
s.t.yi(wTxi+b)≥1s.t.yi(wTxi+b)≥1
对偶问题
对基本型问题应用拉格朗日乘子法得到其“对偶问题”，求解对偶问题更高效。基本型的拉格朗日函数为
L(w,b,α)=12∥w∥2+∑i=1mαi(1−yi(wTxi+b))L(w,b,α)=12‖w‖2+∑i=1mαi(1−yi(wTxi+b))
令L对w和b偏导为0，代入L得对偶问题为
max∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjxTixjmax∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjxiTxj
s.t.∑i=1mαiyi=0s.t.∑i=1mαiyi=0
αi≥0αi≥0
上述过程需满足KKT条件
⎧⎩⎨⎪⎪αi≥0yif(xi)−1≥0αi(yif(xi)−1)=0{αi≥0yif(xi)−1≥0αi(yif(xi)−1)=0
SMO算法求解对偶问题。思路是每次选择两个变量αi、αjαi、αj，固定其他参数，求解对偶问题问题更新αi、αjαi、αj，直到收敛。
违背KKT条件程度越大，变量更新后导致的目标函数值减幅越大，所以每次选择的样本尽量有很大的差别。
核函数如果样本不是线性可分的，可将样本从原始空间映射到更高维的特征空间，使样本在高维空间里线性可分。
令φ(x)φ(x)表示将x映射后的特征向量，于是特征空间中划分超平面为f(x)=wTφ(x)+bf(x)=wTφ(x)+b，并有类似上文的原问题及对偶问题。计算对偶问题涉及内积计算，对无穷维计算内积很困难，因此将特征空间的内积定义为原始样本空间的”核函数“。常用核函数：
线性核： κ(xi,xj)=xTixjκ(xi,xj)=xiTxj
无奈的小白菜核：κ(xi,xj)=exp(−∥xi−xj∥22δ2)κ(xi,xj)=exp(−‖xi−xj‖22δ2)
防止过拟合，允许软间隔，即最大化间隔的同时，不满足样本尽可能少并引入松弛变量。于是优化函数为
min12∥w∥2+C∑i=1mι0/1(yi(wTxi+b)−1)min12‖w‖2+C∑i=1mι0/1(yi(wTxi+b)−1)
“0-1损失函数”不连续，一般用替代损失函数，如
hinge损失：ιhinge(z)=max(0,1−z)ιhinge(z)=max(0,1−z)
python sklearn实现 import pandas as pdimport numpy as npfrom sklearn import svmfrom sklearn.model_selection import train_test_split,cross_val_scoreimport matplotlib.pyplot as pltimport matplotlib as mpl# txt也可以用read_csv读成dataframe，.loc取出需要的列 行数表示到某一行iris = pd.read_csv('E:\study\data\iris.txt',sep=',',skiprows=[1])X = iris.loc[:,['sepal length','sepal width']]y = iris.loc[:,['class']]x_train,x_test,y_train,y_test = train_test_split(X,y,test_size=0.3)clf = svm.SVC(C=0.8,kernel='rbf',gamma=20,decision_function_shape='ovr')clf.fit(x_train,y_train)print clf.score(x_test,y_test) #精确度0.778 优缺点
优点：只关心支持向量，模型鲁棒性高，适用小样本。线性可分情况下SVM相当于逻辑回归，可使用非线性核解决线性不可分的情况。
缺点：噪声敏感，对大规模训练样本难以实施，对多分类问题存在困难。