西瓜书笔记02：支持向量基

2018-08-15 本文已影响0人叫我e卵石

支持向量基

@[拉格朗日乘子法|对偶问题|KKT条件|核函数|hinge损失]

存在多个超平面将样本划分的情况下，选择对训练样本局部扰动容忍性最好的。

间隔与支持向量

划分超平面的法向量为 $w=(w_{1};w_{2};...;w_{d})$ ，则超平面为 $w^{T}x+b=0$ 。任一点x到超平面(w,b)距离为
$r=\frac{\left | w^{T} x+b\right |}{\left \| w \right \|}.$
假设超平面将样本正确分类，则对于 $(x_{i},y_{i})\in D$ ，若 $y_{i}=+1$ ，有 $w^{T}x_{i}+b>0$ ；若 $y_{i}=-1$ ，有 $w^{T}x_{i}+b<0$ 。令
$\left\{\begin{matrix} w^{T}x_{i}+b\geq +1, &y_{i}=+1 \\ w^{T}x_{i}+b\leq -1, &y_{i}=-1 \end{matrix}\right.$
则 $w^{T}x+b=\pm 1$ 为”支持向量“，支持向量间距离，即“间隔”为 $\gamma =\frac{2}{\left \| w \right \|}$ 。

欲找到“最大间隔”的超平面，即最大化 $\left \| w \right \|^{-1}$ ，等价于最小化 $\left \| w \right \|^{2}$ 。于是支持向量基的基本型为
$min \frac{1}{2}\left \| w \right \|^{2}$
$s.t.y_{i}(w^{T}x_{i}+b)\geq 1$

对偶问题

对基本型问题应用拉格朗日乘子法得到其“对偶问题”，求解对偶问题更高效。基本型的拉格朗日函数为
$L(w,b,\alpha )=\frac{1}{2}\left \| w \right \|^{2}+\sum_{i=1}^{m}\alpha _{i}(1-y_{i}(w^{T}x_{i}+b))$
令L对w和b偏导为0，代入L得对偶问题为
$max \sum_{i=1}^{m}\alpha _{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}x_{i}^{T}x_{j}$
$s.t. \sum_{i=1}^{m}\alpha _{i}y_{i}=0$
$\alpha _{i}\geq 0$
上述过程需满足KKT条件
$\left\{\begin{matrix}\alpha _{i}\geq 0\\y_{i} f(x_{i})-1\geq 0\\ \alpha _{i}(y_{i}f(x_{i})-1)=0\end{matrix}\right.$
SMO算法求解对偶问题。思路是每次选择两个变量 $\alpha_{i}、\alpha_{j}$ ，固定其他参数，求解对偶问题问题更新 $\alpha_{i}、\alpha_{j}$ ，直到收敛。

违背KKT条件程度越大，变量更新后导致的目标函数值减幅越大，所以每次选择的样本尽量有很大的差别。

核函数

如果样本不是线性可分的，可将样本从原始空间映射到更高维的特征空间，使样本在高维空间里线性可分。

令 $\varphi (x)$ 表示将x映射后的特征向量，于是特征空间中划分超平面为 $f(x)=w^{T}\varphi (x)+b$ ，并有类似上文的原问题及对偶问题。
计算对偶问题涉及内积计算，对无穷维计算内积很困难，因此将特征空间的内积定义为原始样本空间的”核函数“。

常用核函数：
线性核： $\kappa(x_{i},x_{j})=x_{i}^{T}x_{j}$
高斯核： $\kappa(x_{i},x_{j})=exp(-\frac{\left \| x_{i}-x_{j} \right \|^{2}}{2\delta^{2}})$

软间隔与正则化

防止过拟合，允许软间隔，即最大化间隔的同时，不满足样本尽可能少并引入松弛变量。于是优化函数为
$min \frac{1}{2}\left \| w \right \|^{2}+C\sum_{i=1}^{m}\iota _{0/1}(y_{i}(w^{T}x_{i}+b)-1)$
"0-1损失函数"不连续，一般用替代损失函数，如
hinge损失： $\iota _{hinge}(z)=max(0,1-z)$

python sklearn实现

import pandas as pd
import numpy as np
from sklearn import svm
from sklearn.model_selection import train_test_split,cross_val_score
import matplotlib.pyplot as plt
import 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

优缺点

优点：只关心支持向量，模型鲁棒性高，适用小样本。
缺点：噪声敏感，对大规模训练样本难以实施，对多分类问题存在困难。

tips

如果feature数量很大，跟样本数量差不多，选用LR或者线性核的SVM；
如果feature数量小，样本数量一般，选用高斯核SVM；
如果feature数量小，样本数量多，需要手工添加一些feature变成第一种情况。