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 ■如果把原始空间数据映射到特征空间 那么特征空间中的线性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