机器学习-4.支持向量机

支持向量机主要内容和目标2/70理解支持向量机SVM的原理和目标掌握支持向量机的计算过程和算法步骤理解软间隔最大化的含义对线性不可分的数据给出(略有错误)的分割面线性可分的数据需要使用“软间隔”目标函数吗？了解核函数的思想了解SMO算法的过程各种概念线性可分支持向量机ization硬间隔最大化hard

margin硬间隔支持向量机线性支持向量机ization软间隔最大化soft

margin软间隔支持向量机非线性支持向量机核函数kernel

function注：以上概念的提法，各个文献并不十分。3/70线性可分支持向量机4/70使用核解决线性不可分5/70分割超平面设C和D为两不相交的凸集，则存在超平面P，P可以将C和D分离。两个集合的距离，定义为两个集合间元素的最短距离。做集合C和集合D最短线段的垂直平分线。7/70分割超平面的思考如何定义两个集合的“最优”分割超平面？找到集合“边界”上的若干点，以这些点为

“基础”计算超平面的方向；以两个集合边界上的这些点的平均作为超平面的“截距”支持向量：supportvector若两个集合有部分相交，如何定义超平面，使得两个集合“尽量”分开？8/70线性分类问题9/70输入数据10/70假设给定一个特征空间上的训练数据集T={(x1,y1),

(x2,y2)…(xN,yN)}其中，xi∈Rn，yi∈{+1,-1}，i=1,2,…N。xi为第i个实例(若n>1，xi为向量)；yi为xi的类标记；当yi=+1时，称xi为正例；当yi=-1时，称xi为负例；(xi,yi)称为样本点。线性可分支持向量机给定线性可分训练数据集，通过间隔最大化得到的分离超平面为yx

wT

x

b相应的分类决策函数

f

x

sign

w该决策函数称为线性可分支持向量机。φ(x)是某个确定的特征空间转换函数，它的作用是将x

到(更高的)维度。最简单直接的：x

x稍后会看到，求解分离超平面问题可以等价为求解相应的凸二次规划问题。11/70整理符号分割平面：wT

x

b

0训练集：x1,x2

,,xn12/70i目标值：y1,y2

,,yn新数据的分类：yx

wT

x

bsignyx

推导目标函数根据题设w,b等比例缩放，则t*y的值同样缩放，从而：yx

wT

x

b

0i

ii

ii

i

y

y

xyx

0

y

1有：

yx

0

y

1w13/70wx

T

i

i

iy

w

x

b

yi

y最大间隔分离超平面目标函数：wwiy

wT

x

bi

i

i

y

yx

14/70x

b

wiTimin

y

w

i

1arg

maxw,b函数间隔和几何间隔i15/70Tw

x

bw分割平面：y

wT

x

b总可以通过等比例缩放w的方法，使得两类点的函数值都满足|

y

|≥1建立目标函数总可以通过等比例缩放w的方法，使得两类点的函数值都满足|

y|≥1约束条件：原目标函数：新目标函数：y

w

x

b

1Ti

i

w

x

b

wiTiimin

y

1arg

maxw,bw16/701arg

maxw,b建立目标函数wiTis.t.max

1w,bi

1,2,,

nb

1,y

w

x

i17/70Ti2min1

w

2x

b

1,

i

1,2,,

nw,bs.t.

y

w

日乘子法原始问题的对偶问题，是极大极小问题

b,w,mLwb,原问题是极小极大问题min

max

Lw,b,

w,biTiw

,

s.t.

y

1

22minw,bw

x

b

1,

i

1,2

NiTi

ixi12

y

w

b1nLw,

b,

1

w

218/70将 日函数L(w,b,a)分别对w，b求偏导并令其为0：日函数i

ii

i

ibwi1i1L

0

0

n

yL

0

w

n

y

x

19/70计算日函数的对偶函数iini10

y

x

wi1nnjiijijinTniiiniiiinT

iiinT

nnniiiTniT

iixyxywbwLij,1

i1i1ni1i1i1i1i1i12212

i11

12

12nbxw1y

i1

T

iixi

yxy

i

bxy0wxywi1

iiybxyww

wi12

T

,,

nT

i

j

i

j

i

jn

ii,

j

1

i1*12a

argmax

y

y

x

x

20/70继续求minw,bL(w,b,α)对α的极大21/70njnimaxi

1,2,,

n

12n

ni1

j

1i1i

0,s.t.

i

yi

0i1

y

y

x

xi

j

i

j

i整理目标函数：添加负号22/70n2mini

1,2,,

nn

n1

i

j

i

j

i

j

ii1i1

j

1i

0,s.t.

i

yi

0i1

y

y

x

x

n

线性可分支持向量机学习算法构造并求解约束最优化问题23/70求得最优解α*n2mini

1,2,,

nn

n1

i1

j

1i

0,s.t.

i

yi

0i1

y

y

x

x

n

i

j

i

j

i

j

ii1线性可分支持向量机学习算法24/70计算求得分离超平面Njii

ii

i

i

i

x

xi1*i1*b*

y

y

Nw*

y

x

w*x

b*

0分类决策函数f

x

signw*x

b*

举例1min21s.ti1

j

1给定3个数据点：正例点x1=(3,3)T，x2==(4,3)T，负例点x3=(1,1)T，求线性可分支持向量机。目标函数：1

n

ni1

2

3i

0,

i

12

18

2525/70将约束带入目标函数，化简计算对α1，α2求偏导并令其为0，易知s(α1,α2)在点(1.5,-1)处取极值。而该点不满足条件α2≥0，所以，最小值在边界上达到。当α1=0时，最小值s(0,2/13)=-2/13=-0.1538当α2=0时，最小值s(1/4,0)=-1/4=-0.25于是，s(α1,α2)在α1=1/4，α2=0时达到最小，此时，α3=α1+α2=1/4将

1

2

3带入目标函数，得到关于α1，α2的函数：2226/7021

2

1213

1012

21

22s

,

4

分离超平面α1=α3=1/4对应的点x1,x3是支持向量。得到w1=w2=0.5，b=-2因此，分离超平面为分离决策函数为2

221

2

01

x

1

x2

221f

x

sign

1

x

1

x

2N27/70jii

i

ii

i

i

x

xi1*i1*b*

y

带入公式：w*

N

y

y

x

线性支持向量机不一定分类完全正确的超平面就是最好的样本数据本身线性不可分28/70目标函数：线性支持向量机若数据线性不可分，则增加松弛因子ξi≥0，使函数间隔加上松弛变量大于等于1。这样，约束条件变成yi

w

xi

b1i29/70Niw

Ci1212minw,b线性SVM的目标函数N30/70is.t.i

1,2,,

ni

1,2,,

ni1i

0,yi

w

xi

b

1

i

,min

1

w

2

Cw,b,

2带松弛因子的SVM日函数日函数对w,b,

ξ求偏导nni

iini

i

i

ii1i1i12

b

1

y

w

xLw,

b,

,

,

1

w

2

Ci

iii1i

ii1i

i

ibwL

0

C

0L

0

0

n

yL

0

w

n

y

x

31/70带入目标函数32/70将三式带入L中，得到对上式求关于α的极大，得到：i0

Cnin

nji

j

i

j

ix

x

i1i1

j

112

y

y

min

Lw,

b,

,

,

w,b,inn2i1i1

j

1

0，

i

1,2,,

ns.t.

i

yi

0i1C

i

i

0i

0max

1

n

n

y

y

x

x

i

j

i

j

i

j

i最终的目标函数33/70整理，得到对偶问题：nn2mini

1,2,,

ni

j

i

j

i

j

in

n1

i1i1

j

1s.t.

i

yi

0i10

i

C,y

y x

x

线性支持向量机学习算法构造并求解约束最优化问题34/70nniji

j

i

j

i2mini

1,2,,

nx

x

n

n1

i1i1

j

1s.t.

i

yi

0i10

i

C,求得最优解α*

y

y

线性支持向量机学习算法计算求得分离超平面分类决策函数2注意：计算b*时，需要使用满足条件0<αj<C的向量实践中往往取支持向量的所有值取平均，作为b*35/70*i

ii

i

imax

w*

x

min

w*

xi1i：yi

1b*

i：yi

1nw*

y

xw*

x

b*

0f

x

signw*

x

b*损失函数分析36/70绿色：0/1损失蓝色：SVM

Hinge损失函数红色：Logistic损失函数Code37/70核函数可以使用核函数，将原始输入空间到新的特征空间，从而，使得原本线性不可分的样本可能在核空间可分。1

2

1

2多项式核函数：

x

,

x

x

x

cd1核RBF函数：x1,x2

expSigmoid核函数：x1,x2

tanhx1

x2

c在实际应用中，往往依赖先验领域知识/交叉验证等方案才能选择有效的核函数。没有

先验信息，则使用

核函数3388//7700多项式核函数2

,

(

)x

y

x

y

n

i

ixi

x

j

yi

y

jx

x

y

y

i

j

i

jx

y

n

ni1

j

1n

n

i1

j

12

i1

2x,

y

(x

y)

3 1

2

1

1 1

x3

x3

x3

x2

x

x

x2

x3

x

x

x1

x3

x1

x2

x

x

特殊的，若n

3，即：x

x2

x2

i

j39/70ni,

j

1

x

vecx

x

多项式核2

x,

y

(x

y

c)i

jn

n

x

x

y

i

j

i

j

2cx

y

(x

y)x,

y

(x

y

c)i1

j

122

vecxx

40/701

2

3

3

32c2cc2cx

特殊的，若n

3，即核函数41/70核粗线是分割超“平面”其他线是y(x)的等高线绿色圈点是支持向量点42/70核是无穷维的其中2131

22221

2321211!13!2!1!2

21

222

2

1

222xx2

xxx1xxx

3n!xxxxxxTnn2

xxxxxxxx

2!

1211

e

1

n

1

3

12

1

2

12

1

exx

xx

2

2

1

2

12

2

2

1

2

12

xx

12

xx

12

12

12

1

xxn

12n!

n

n3!

3

3

2

2

2

1

xx

2

,2

22

ee

22

2exeex2

2

2

22

2,3

,,22

,n

,

x21

xn1

xx3

xn!

1

11!

2!

3!xe

2

2

1,xx2

x3

xne

1

x

Rn2!

3!

n!43/7044/70核的分类SVM中系数的求解：SMO序列最小最优化Sequential

Minimal

Optimization有多个 日乘子每次只选择其中两个乘子做优化，其他因子认为是常数。将N个解问题，转换成两个变量的求解问题：并且目标函数是凸的。45/70SMO：序列最小最优化目标函数，假设α1和α2是变量，其他是定值：yysyt

0

i

C..N

iii31212NNi3i

i i

2i3i

i

i1

2 2

1 1

1

2

1

2

12222

2211

1221

1

y

y

y

y

y

y

1

2

min

W

1,2

1

,2Njiijixj

xKyy

imin

1,,20,

NiCN

N

N1

i12

i1

j

1..

iisyt

0i1

i

46/70二变量优化问题1

247/70211

2,

y1

y2,

y

yH

minC,

L

max0,1

2

CH

minC,

C

L

max0,1

2

SMO的迭代公式迭代公式：Ngx

i1yii

xi

,

x

b

b

y

,

i

1,2x

,

x

iN

j

1

j

j

j

iiEi

gxi

y

y

oldjnewj

y

j

Ei

Ej

248/70211

1

2

2

1

2x

x

x

,

x

x

,

x

2x

,

x

退出条件49/70nii

iiii

ii

iNgx

y

g

xj

1

1,

C

//

1,

1,y

K

x

,

x

bj

j

j

ii

yi

0i10

i

C,x

C//落在边界内x

0

落在边界上x

0//落在边界外i

1,2,nCode50/70Code51/70惩罚因子的影响52/70核函数的影响53/70SVM分类54/70Unbalanced55/70放大56/70AUCTPFP

TNFPR

TP

FNFPTPR

Receiver

Operating

CharacteristicArea

Under

Curve57/70分类器指标TPTP

FNrecall

TP

FPprecisionTP

TN

FN

FPTPTP

TNaccuracy1F

2

precision

recallprecision

recall1

2

precision

recall

2

precision

recallF

58/700Lift

CurveThe

cumulative

responsecurve

is

sometimes

called

alift

curve,

because

one

cansee

the

increase

over

simplying

randomly

as

howmuch

the

linerepresentingthe

model

performance

islifted

up

over

the

randomperformance

diagonal.59/70计算TP60/70TP

FNrecall

TP

FPprecisionTP

TN

FN

FPTPTP

TNaccuracy1F

2

precision

recallprecision

rec