支持向量机

1.支持向量机最简单的情况是线性可分支持向量机,或硬间隔支持向量机。构建它的条件是训练数据线性可分。其学习策略是最大间隔法。可以表示为凸二次规划问题,其原始最优化问题为 minw,b12w2minw,b12w2

s.t.yi(wxi+b)10,i=1,2,,Ns.t.yi(wxi+b)10,i=1,2,,N

求得最优化问题的解为wwbb,得到线性可分支持向量机,分离超平面是

wx+b=0wx+b=0

分类决策函数是

f(x)=sign(wx+b)f(x)=sign(wx+b)

最大间隔法中,函数间隔与几何间隔是重要的概念。

线性可分支持向量机的最优解存在且唯一。位于间隔边界上的实例点为支持向量。最优分离超平面由支持向量完全决定。 二次规划问题的对偶问题是 min12Ni=1Nj=1αiαjyiyj(xixj)Ni=1αimin12Ni=1Nj=1αiαjyiyj(xixj)Ni=1αi

s.t.Ni=1αiyi=0s.t.Ni=1αiyi=0

αi0,i=1,2,,Nαi0,i=1,2,,N

通常,通过求解对偶问题学习线性可分支持向量机,即首先求解对偶问题的最优值

aa,然后求最优值wwbb,得出分离超平面和分类决策函数。

2.现实中训练数据是线性可分的情形较少,训练数据往往是近似线性可分的,这时使用线性支持向量机,或软间隔支持向量机。线性支持向量机是最基本的支持向量机。

对于噪声或例外,通过引入松弛变量ξiξi,使其“可分”,得到线性支持向量机学习的凸二次规划问题,其原始最优化问题是

minw,b,ξ12w2+CNi=1ξiminw,b,ξ12w2+CNi=1ξi

s.t.yi(wxi+b)1ξi,i=1,2,,Ns.t.yi(wxi+b)1ξi,i=1,2,,N

ξi0,i=1,2,,Nξi0,i=1,2,,N

求解原始最优化问题的解wwbb,得到线性支持向量机,其分离超平面为

wx+b=0wx+b=0

分类决策函数为

f(x)=sign(wx+b)f(x)=sign(wx+b)

线性可分支持向量机的解ww唯一但bb不唯一。对偶问题是

minα12Ni=1Nj=1αiαjyiyj(xixj)Ni=1αiminα12Ni=1Nj=1αiαjyiyj(xixj)Ni=1αi

s.t.Ni=1αiyi=0s.t.Ni=1αiyi=0

0αiC,i=1,2,,N0αiC,i=1,2,,N

线性支持向量机的对偶学习算法,首先求解对偶问题得到最优解αα,然后求原始问题最优解wwbb,得出分离超平面和分类决策函数。

对偶问题的解αα中满αi>0αi>0的实例点xixi称为支持向量。支持向量可在间隔边界上,也可在间隔边界与分离超平面之间,或者在分离超平面误分一侧。最优分离超平面由支持向量完全决定。

线性支持向量机学习等价于最小化二阶范数正则化的合页函数

Ni=1[1yi(wxi+b)]++λw2Ni=1[1yi(wxi+b)]++λw2

3.非线性支持向量机

对于输入空间中的非线性分类问题,可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题,在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里,目标函数和分类决策函数都只涉及实例与实例之间的内积,所以不需要显式地指定非线性变换,而是用核函数来替换当中的内积。核函数表示,通过一个非线性转换后的两个实例间的内积。具体地,K(x,z)K(x,z)是一个核函数,或正定核,意味着存在一个从输入空间x到特征空间的映射XHXH,对任意XX,有

K(x,z)=ϕ(x)ϕ(z)K(x,z)=ϕ(x)ϕ(z)

对称函数K(x,z)K(x,z)为正定核的充要条件如下:对任意xiX,i=1,2,,mxiX,i=1,2,,m,任意正整数mm,对称函数K(x,z)K(x,z)对应的Gram矩阵是半正定的。

所以,在线性支持向量机学习的对偶问题中,用核函数K(x,z)K(x,z)替代内积,求解得到的就是非线性支持向量机

f(x)=sign(Ni=1αiyiK(x,xi)+b)f(x)=sign(Ni=1αiyiK(x,xi)+b)

4.SMO算法

SMO算法是支持向量机学习的一种快速算法,其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题,并对子问题进行解析求解,直到所有变量满足KKT条件为止。这样通过启发式的方法得到原二次规划问题的最优解。因为子问题有解析解,所以每次计算子问题都很快,虽然计算子问题次数很多,但在总体上还是高效的。

分离超平面:wTx+b=0wTx+b=0

点到直线距离:r=|wTx+b|||w||2r=|wTx+b|||w||2

||w||2||w||2为2-范数:||w||2=2mi=1w2i||w||2=2mi=1w2i

直线为超平面,样本可表示为:

wTx+b +1wTx+b +1

wTx+b +1wTx+b +1

margin:

函数间隔label(wTx+b) or yi(wTx+b)label(wTx+b) or yi(wTx+b)

几何间隔r=label(wTx+b)||w||2r=label(wTx+b)||w||2,当数据被正确分类时,几何间隔就是点到超平面的距离

为了求几何间隔最大,SVM基本问题可以转化为求解:(r||w||r||w||为几何间隔,(rr为函数间隔)

max r||w||max r||w||

(subject to) yi(wTxi+b)r, i=1,2,..,m(subject to) yi(wTxi+b)r, i=1,2,..,m

分类点几何间隔最大,同时被正确分类。但这个方程并非凸函数求解,所以要先①将方程转化为凸函数,②用拉格朗日乘子法和KKT条件求解对偶问题。

①转化为凸函数:

先令r=1r=1,方便计算(参照衡量,不影响评价结果)

max 1||w||max 1||w||

s.t. yi(wTxi+b)1, i=1,2,..,ms.t. yi(wTxi+b)1, i=1,2,..,m

再将max 1||w||max 1||w||转化成min 12||w||2min 12||w||2求解凸函数,1/2是为了求导之后方便计算。

min 12||w||2min 12||w||2

s.t. yi(wTxi+b)1, i=1,2,..,ms.t. yi(wTxi+b)1, i=1,2,..,m

②用拉格朗日乘子法和KKT条件求解最优值:

min 12||w||2min 12||w||2

s.t. yi(wTxi+b)+10, i=1,2,..,ms.t. yi(wTxi+b)+10, i=1,2,..,m

整合成:

L(w,b,α)=12||w||2+mi=1αi(yi(wTxi+b)+1)L(w,b,α)=12||w||2+mi=1αi(yi(wTxi+b)+1)

推导:min f(x)=minmax L(w,b,α)maxmin L(w,b,α)min f(x)=minmax L(w,b,α)maxmin L(w,b,α)

根据KKT条件:

wL(w,b,α)=wαiyixi=0, w=αiyixiwL(w,b,α)=wαiyixi=0, w=αiyixi

bL(w,b,α)=αiyi=0bL(w,b,α)=αiyi=0

代入L(w,b,)L(w,b,)

min L(w,b,α)=12||w||2+mi=1αi(yi(wTxi+b)+1)min L(w,b,α)=12||w||2+mi=1αi(yi(wTxi+b)+1)

=12wTwmi=1αiyiwTxibmi=1αiyi+mi=1αi=12wTwmi=1αiyiwTxibmi=1αiyi+mi=1αi

=12wTαiyiximi=1αiyiwTxi+mi=1αi=12wTαiyiximi=1αiyiwTxi+mi=1αi

=mi=1αi12mi=1αiyiwTxi

=mi=1αi12mi,j=1αiαjyiyj(xixj)

再把max问题转成min问题:

max mi=1αi12mi,j=1αiαjyiyj(xixj)=min12mi,j=1αiαjyiyj(xixj)mi=1αi

s.t. mi=1αiyi=0,

i0,i=1,2,...,m

以上为SVM对偶问题的对偶形式

kernel

在低维空间计算获得高维空间的计算结果,也就是说计算结果满足高维(满足高维,才能说明高维下线性可分)。

soft margin & slack variable

引入松弛变量ξ0,对应数据点允许偏离的functional margin 的量。

目标函数:

min 12||w||2+Cξis.t. yi(wTxi+b)1ξi

对偶问题:

max mi=1αi12mi,j=1αiαjyiyj(xixj)=min12mi,j=1αiαjyiyj(xixj)mi=1αi

s.t. Cαi0,i=1,2,...,mmi=1αiyi=0,

Sequential Minimal Optimization

首先定义特征到结果的输出函数:u=wTx+b.

因为w=αiyixi

u=yiαiK(xi,x)b

maxmi=1αi12mi=1mj=1αiαjyiyj<ϕ(xi)T,ϕ(xj)>

s.t. mi=1αiyi=0,

αi0,i=1,2,...,m

参考资料:

[1] :Lagrange Multiplier and KKT

[2] :推导SVM

[3] :机器学习算法实践-支持向量机(SVM)算法原理

[4] :Python实现SVM

1
2
3
4
5
6
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt
%matplotlib inline
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# data
def create_data():
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = [
'sepal length', 'sepal width', 'petal length', 'petal width', 'label'
]
data = np.array(df.iloc[:100, [0, 1, -1]])
for i in range(len(data)):
if data[i, -1] == 0:
data[i, -1] = -1
# print(data)
return data[:, :2], data[:, -1]
1
2
X, y = create_data()
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)
1
2
3
plt.scatter(X[:50,0],X[:50,1], label='0')
plt.scatter(X[50:,0],X[50:,1], label='1')
plt.legend()
<matplotlib.legend.Legend at 0x1d96e8af308>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
class SVM:
def __init__(self, max_iter=100, kernel='linear'):
self.max_iter = max_iter
self._kernel = kernel

def init_args(self, features, labels):
self.m, self.n = features.shape
self.X = features
self.Y = labels
self.b = 0.0

# 将Ei保存在一个列表里
self.alpha = np.ones(self.m)
self.E = [self._E(i) for i in range(self.m)]
# 松弛变量
self.C = 1.0

def _KKT(self, i):
y_g = self._g(i) * self.Y[i]
if self.alpha[i] == 0:
return y_g >= 1
elif 0 < self.alpha[i] < self.C:
return y_g == 1
else:
return y_g <= 1

# g(x)预测值,输入xi(X[i])
def _g(self, i):
r = self.b
for j in range(self.m):
r += self.alpha[j] * self.Y[j] * self.kernel(self.X[i], self.X[j])
return r

# 核函数
def kernel(self, x1, x2):
if self._kernel == 'linear':
return sum([x1[k] * x2[k] for k in range(self.n)])
elif self._kernel == 'poly':
return (sum([x1[k] * x2[k] for k in range(self.n)]) + 1)**2

return 0

# E(x)为g(x)对输入x的预测值和y的差
def _E(self, i):
return self._g(i) - self.Y[i]

def _init_alpha(self):
# 外层循环首先遍历所有满足0<a<C的样本点,检验是否满足KKT
index_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C]
# 否则遍历整个训练集
non_satisfy_list = [i for i in range(self.m) if i not in index_list]
index_list.extend(non_satisfy_list)

for i in index_list:
if self._KKT(i):
continue

E1 = self.E[i]
# 如果E2是+,选择最小的;如果E2是负的,选择最大的
if E1 >= 0:
j = min(range(self.m), key=lambda x: self.E[x])
else:
j = max(range(self.m), key=lambda x: self.E[x])
return i, j

def _compare(self, _alpha, L, H):
if _alpha > H:
return H
elif _alpha < L:
return L
else:
return _alpha

def fit(self, features, labels):
self.init_args(features, labels)

for t in range(self.max_iter):
# train
i1, i2 = self._init_alpha()

# 边界
if self.Y[i1] == self.Y[i2]:
L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)
H = min(self.C, self.alpha[i1] + self.alpha[i2])
else:
L = max(0, self.alpha[i2] - self.alpha[i1])
H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])

E1 = self.E[i1]
E2 = self.E[i2]
# eta=K11+K22-2K12
eta = self.kernel(self.X[i1], self.X[i1]) + self.kernel(
self.X[i2],
self.X[i2]) - 2 * self.kernel(self.X[i1], self.X[i2])
if eta <= 0:
# print('eta <= 0')
continue

alpha2_new_unc = self.alpha[i2] + self.Y[i2] * (
E1 - E2) / eta #此处有修改,根据书上应该是E1 - E2,书上130-131页
alpha2_new = self._compare(alpha2_new_unc, L, H)

alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (
self.alpha[i2] - alpha2_new)

b1_new = -E1 - self.Y[i1] * self.kernel(self.X[i1], self.X[i1]) * (
alpha1_new - self.alpha[i1]) - self.Y[i2] * self.kernel(
self.X[i2],
self.X[i1]) * (alpha2_new - self.alpha[i2]) + self.b
b2_new = -E2 - self.Y[i1] * self.kernel(self.X[i1], self.X[i2]) * (
alpha1_new - self.alpha[i1]) - self.Y[i2] * self.kernel(
self.X[i2],
self.X[i2]) * (alpha2_new - self.alpha[i2]) + self.b

if 0 < alpha1_new < self.C:
b_new = b1_new
elif 0 < alpha2_new < self.C:
b_new = b2_new
else:
# 选择中点
b_new = (b1_new + b2_new) / 2

# 更新参数
self.alpha[i1] = alpha1_new
self.alpha[i2] = alpha2_new
self.b = b_new

self.E[i1] = self._E(i1)
self.E[i2] = self._E(i2)
return 'train done!'

def predict(self, data):
r = self.b
for i in range(self.m):
r += self.alpha[i] * self.Y[i] * self.kernel(data, self.X[i])

return 1 if r > 0 else -1

def score(self, X_test, y_test):
right_count = 0
for i in range(len(X_test)):
result = self.predict(X_test[i])
if result == y_test[i]:
right_count += 1
return right_count / len(X_test)

def _weight(self):
# linear model
yx = self.Y.reshape(-1, 1) * self.X
self.w = np.dot(yx.T, self.alpha)
return self.w
1
svm = SVM(max_iter=200)
1
svm.fit(X_train, y_train)
'train done!'
1
svm.score(X_test, y_test)
0.64

scikit-learn实例

1
2
3
from sklearn.svm import SVC
clf = SVC()
clf.fit(X_train, y_train)
SVC()
1
clf.score(X_test, y_test)
0.96

sklearn.svm.SVC

(C=1.0, kernel='rbf', degree=3, gamma='auto', coef0=0.0, shrinking=True, probability=False,tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_function_shape=None,random_state=None)

参数:

  • C:C-SVC的惩罚参数C?默认值是1.0

C越大,相当于惩罚松弛变量,希望松弛变量接近0,即对误分类的惩罚增大,趋向于对训练集全分对的情况,这样对训练集测试时准确率很高,但泛化能力弱。C值小,对误分类的惩罚减小,允许容错,将他们当成噪声点,泛化能力较强。

  • kernel :核函数,默认是rbf,可以是‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, ‘precomputed’

    – 线性:u'v

    – 多项式:(gammau'v + coef0)^degree

    – RBF函数:exp(-gamma|u-v|^2)

    – sigmoid:tanh(gammau'v + coef0)

  • degree :多项式poly函数的维度,默认是3,选择其他核函数时会被忽略。

  • gamma : ‘rbf’,‘poly’ 和‘sigmoid’的核函数参数。默认是’auto’,则会选择1/n_features

  • coef0 :核函数的常数项。对于‘poly’和 ‘sigmoid’有用。

  • probability :是否采用概率估计?.默认为False

  • shrinking :是否采用shrinking heuristic方法,默认为true

  • tol :停止训练的误差值大小,默认为1e-3

  • cache_size :核函数cache缓存大小,默认为200

  • class_weight :类别的权重,字典形式传递。设置第几类的参数C为weight*C(C-SVC中的C)

  • verbose :允许冗余输出?

  • max_iter :最大迭代次数。-1为无限制。

  • decision_function_shape :‘ovo’, ‘ovr’ or None, default=None3

  • random_state :数据洗牌时的种子值,int值

主要调节的参数有:C、kernel、degree、gamma、coef0。

第7章支持向量机-习题

习题7.1

  比较感知机的对偶形式与线性可分支持向景机的对偶形式。

解答:
感知机算法的原始形式:
给定一个训练数据集T={(x1,y1),(x2,y2),,(xN,yN)}其中,xiX=Rn,yiY={1,1},i=1,2,,N,求参数w,b,使其为以下损失函数极小化问题的解:minw,bL(w,b)=xiMyi(wxi+b)其中M为误分类点的集合。
上式等价于:minw,bL(w,b)=Ni=1(yi(wxi+b))+


补充: 合页损失函数L(y(wx+b))=[1y(wx+b)]+下标“+”表示以下取正数的函数。[z]+={z,z>00,z0当样本点(xi,yi)被正确分类且函数间隔(确信度)yi(wxi+b)大于1时,损失是0,否则损失是1yi(wxi+b)


感知机算法的对偶形式:
w,b表示为xi,yi的线性组合的形式,求其系数(线性组合的系数)w=Ni=1αiyixi,b=Ni=1αiyi,满足:minw,bL(w,b)=minαiL(αi)=Ni=1(yi(Nj=1αjyjxjxi+Nj=1αjyj))+

线性可分支持向量机的原始问题:
minw,b12w2s.t.yi(wxi+b)10,i=1,2,,N

线性可分支持向量机的对偶问题:
maxα12Ni=1Nj=1αiαjyiyj(xixj)+Ni=1alphais.t.Ni=1αiy+i=0α0,i=1,2,,N根据书上定理7.2,可得w=Ni=1αiyjxi,b=yiNi=1αyi(xixj),可以看出w,b实质上也是将其表示为xi,xj的线性组合形式。

习题7.2

  已知正例点x1=(1,2)T,x2=(2,3)T,x3=(3,3)T,负例点x4=(2,1)T,x5=(3,2)T,试求最大间隔分离平面和分类决策函数,并在图中挂出分离超平面、间隔边界及支持向量。

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%matplotlib inline
from sklearn.svm import SVC

# 加载数据
X = [[1, 2], [2, 3], [3, 3], [2, 1], [3, 2]]
y = [1, 1, 1, -1, -1]

# 训练SVM模型
clf = SVC(kernel='linear', C=10000)
clf.fit(X, y)

print("w =", clf.coef_)
print("b =", clf.intercept_)
print("support vectors =", clf.support_vectors_)
w = [[-1.  2.]]
b = [-2.]
support vectors = [[3. 2.]
 [1. 2.]
 [3. 3.]]

最大间隔分离超平面:x(1)+2x(2)2=0
分类决策函数:f(x)=sign(x(1)+2x(2)2)
支持向量:x1=(3,2)T,x2=(1,2)T,x3=(3,3)T

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import matplotlib.pyplot as plt
import numpy as np

# 绘制数据点
color_seq = ['red' if v == 1 else 'blue' for v in y]
plt.scatter([i[0] for i in X], [i[1] for i in X], c=color_seq)
# 得到x轴的所有点
xaxis = np.linspace(0, 3.5)
w = clf.coef_[0]
# 计算斜率
a = -w[0] / w[1]
# 得到分离超平面
y_sep = a * xaxis - (clf.intercept_[0]) / w[1]
# 下边界超平面
b = clf.support_vectors_[0]
yy_down = a * xaxis + (b[1] - a * b[0])
# 上边界超平面
b = clf.support_vectors_[-1]
yy_up = a * xaxis + (b[1] - a * b[0])
# 绘制超平面
plt.plot(xaxis, y_sep, 'k-')
plt.plot(xaxis, yy_down, 'k--')
plt.plot(xaxis, yy_up, 'k--')
# 绘制支持向量
plt.xlabel('$x^{(1)}$')
plt.ylabel('$x^{(2)}$')
plt.scatter(clf.support_vectors_[:, 0],
clf.support_vectors_[:, 1],
s=150,
facecolors='none',
edgecolors='k')
plt.show()

习题7.3

  线性支持向量机还可以定义为以下形式:minw,b,ξ12w2+CNi=1ξ2is.t.yi(wxi+b)1ξi,i=1,2,,Nξi0,i=1,2,,N试求其对偶形式。

解答:
根据支持向量机的对偶算法,得到对偶形式,由于不能消去变量ξi的部分,所以拉格朗日因子也包含βi
拉格朗日函数为:L(w,b,ξ,α,β)=12w2+CNi=1ξ2i+Ni=1αiNi=1αiξiNi=1αiyi(wxi+b)Ni=1βiξi
分别求w,b,ξ的偏导数:{wL=wNi=1αiyixi=0bL=Ni=1αiyi=0ξL=2Cξiαiβi=0化简可得:{w=Ni=1αiyixi=0Ni=1αiyi=02Cξiαiβi=0
可解得:L=12Ni=1Nj=1αiαjyiyj(xixj)+Ni=1αi14CNi=1(αi+βi)2

习题7.4

  证明内积的正整数幂函数:K(x,z)=(xz)p是正定核函数,这里p是正整数,x,zRn

解答:
根据书中第121页定理7.5可知,如果需要证明K(x,z)是正定核函数,即证明K(x,z)对应的Gram矩阵K=[K(xi,xj)]m×m是半正定矩阵。
对任意c1,c2,,cmR,有mi,j=1cicjK(xi,xj)=mi,j=1cicj(xixj)p=(mi=1cixi)(mj=1cixj)(xixj)p1=(mi=1cixi)2(xixj)p1 p是正整数,p1
p10(xixj)p10
mi,j=1cicjK(xi,xj)0,即Gram矩阵是半正定矩阵。
根据定理7.5,可得K(x,z)是正定核函数,得证。

作者

ฅ´ω`ฅ

发布于

2021-07-30

更新于

2021-08-21

许可协议


评论

0  字
评论
Powered by Waline v1.5.4