北京大学：《模式识别》课程教学资源（课件讲义）第七章 SVM

第七章SVM ■7.1非线性SVM ■72SVM技术 7.3SVM性质 74SVM推广

第七章 SVM „ 7.1 非线性SVM „ 7.2 SVM技术 „ 7.3 SVM性质 „ 7.4 SVM推广

71非线性SVM

7.1 非线性SVM

71非线性SVM 线性分类器的局限: a可变性( flexibility)差; VC维=d+1,d是原始数据x的维数; n很多实际问题不是线性可分的

7.1 非线性SVM „ 线性分类器的局限： „ 可变性(flexibility)差; „ VC维=d+1， d是原始数据x的维数； „ 很多实际问题不是线性可分的

71非线性SVM SⅥM思想: 非线性映射把原始数据变换到高维特征空间: 原始数据空间 特征空间 x→>2(x)=(1n(x),a22(x)…,ap1(x) 在特征空间中,设计线性SVM

7.1 非线性SVM „ SVM思想： „ 非线性映射把原始数据变换到高维特征空间： „ 在特征空间中，设计线性SVM 原始数据空间 特征空间 ( ) ( ( ), ( ) , ( ) 1 1 2 2 x z x a x a x a x → = φ φ L Mφ M

71非线性SVM ■例:XOR问题 二维映射到三维 X=(rx z(x)=(x,z2,z3)=(x2,x2,xx2) (0,0)→>(0,0,0 线性 1)→(1)1 线性可分 不可分 0,1)→>(O,10) 1,0)→>(,0,0)

7.1 非线性SVM „ 例：XOR问题 ( , ), 1 2 x = x x ( ) ( , , ) ( , , ). 1 2 3 1 2 1 2 z x = z z z = x x x x 二维映射到三维 (1,0) (1,0,0). (0,1) (0,1,0), (1,1) (1,1,1), (0,0) (0,0,0), → → → → 线性 线性可分 不可分

71非线性SVM ■线性SWM回顾: 优化函数(二次规划): min+C(∑5) 2 b s t y(x1*+b)≥1 5;≥0

7.1 非线性SVM „ 线性SVM回顾： „ 优化函数（二次规划）： ( ) 21 min 1 2 , , ∑= + ni i w b w C ξ ξ i i w b i s.t. y (x ∗ + ) ≥1−ξ i =1,2,L, n. ≥ 0. ξ i

71非线性SVM ■线性SWM回顾: 对偶形式: max∑c ∑ aa (x:*x J St.0≤c1≤C, 01y7=

7.1 非线性SVM „ 线性SVM回顾： „ 对偶形式： ∑ ∑ = = − ∗ n i j i j i j i j n i i y y x x 1 , 1 ( ) 21 max α α α α s.t. 0 C, i 1,2, ,n. ≤αi ≤ = L 0. 1 ∑ = = n i i i α y

71非线性SVM ■超平面是支持向量的线性组合: y(x*1+b)=10 y(x*1+b)<1

7.1 非线性SVM „ 超平面是支持向量的线性组合： . 1 ∑ = = n i i i i w α y x yi(xi ∗w+ b) =1 0 1 = 0 αi yi(xi ∗w+ b) <1 αi = C

71非线性SVM 判决函数 8(x)=∑aJ(x*x)+b

7.1 非线性SVM „ 判决函数： ( ) ( ) . 1 g x y x x b n i = ∑ i i i ∗ + = α

71非线性SVM ■如果把原始空间数据映射到特征空间 那么特征空间中的线性SVM为: max2a-∑yya(=(x)*(x) s1.0<a.≤C 0 8(x)=∑aJ((x)*(x)+b

7.1 非线性SVM „ 如果把原始空间数据映射到特征空间， 那么特征空间中的线性SVM为： g x y z x z x b n i = ∑ i i i ∗ + =1 ( ) α ( ( ) ( )) ∑ ∑ = = − ∗ n i j i j i j i j n i i y y z x z x 1 , 1 ( ( ) ( )) 21 max α α α α s.t. 0 C, i 1,2, ,n. ≤αi ≤ = L 0. 1 ∑ = = n i i i α y