Lecture9_SVM

1、SVMChapter 14主要內(nèi)容 SVM最大間隔(margin)分類器對偶表示(Dual Representation)Hinge 損失回歸中的SVM稀疏核模型 稀疏：只選擇訓(xùn)練樣本的子集 (Chapter 13 中 D=N) 通過L1 正則達(dá)到稀疏 稀疏向量機(Sparse Vector Machine) 通過自動相關(guān)性確定達(dá)到稀疏 (Automatic Relevancy Determination, ARD) 相關(guān)向量機(Relevance Vector Machine, RVM) 更稀疏 但非凸 通過損失函數(shù) + L2 正則達(dá)到稀疏 支持向量機(Support Vector Mach

2、ine, SVM) 分類：Hinge Loss 回歸：-insensitive Loss SVM 回顧正則化的經(jīng)驗風(fēng)險最?。?分類：將負(fù)log似然損失用 hinge loss代替 回歸：損失函數(shù)用 不敏感損失代替 解是稀疏的：用損失函數(shù)表達(dá)稀疏性而非先驗21,NiiiJL y yww支持向量機(Support Vector Machine) 最大間隔準(zhǔn)則：最大化兩個類最近點之間的距離。這個距離被稱為間隔(margin)。 邊緣上的點被稱為支持向量(support vectors)。我們先假設(shè)分類器是線性可分的。最大間隔準(zhǔn)則 線性分類面： 則有 其中x到分類面的距離r T0fwxw xprwxx

3、w最大間隔準(zhǔn)則 代入得到 當(dāng)x=0時，原點到分類面的距離 TT0p0TTp0fwxrwxrwfrwxw xwww wwwxwTpp02T0fxwxww ww 00fwr 0ww線性判別函數(shù) 線性判別函數(shù)利用一個超平面把特征空間分隔成兩個區(qū)域。 超平面的方向由法向量w確定，它的位置由閾值w0確定。 判別函數(shù)f(x)正比于x點到超平面的代數(shù)距離（帶正負(fù)號） 當(dāng)x點在超平面的正側(cè)時， f(x) 0； 當(dāng)x點在超平面的負(fù)側(cè)時， f(x) 1 1 = 02 wC-SVM 等價于最小化 其中參數(shù)C控制間隔和松弛變量懲罰項之間的平衡 被誤分的點的 ，因此 為被誤分點的數(shù)目的上界，可視為訓(xùn)練誤差 因此參數(shù)C可

4、視為控制最小訓(xùn)練誤差和模型復(fù)雜度的參數(shù)2T01, subject to 1, 2iiiiiCywi ww xii1iC-SVM對偶 對應(yīng)的Lagrangian為01T0111, ,2 1NTiiNNiiiiiiiiLwCy w ww ww xC-SVM KKT Conditions0001010000iTiiiTiiiiiiiiywyw w xw xC-SVM對偶 對Lagrangian求偏導(dǎo)數(shù)，得 上述結(jié)果代入Lagrangian，得到其對偶問題 與線性可分情況相同10NiiiiLywxw1000NiiiLyw0iiiLC 1111 ,2NNNiijijijiijQy yx xC-SVM對偶

5、 最大化目標(biāo)函數(shù) 但限制變?yōu)?最后的決策函數(shù)形式同線性可分情況100NiiiiyC 1111 ,2NNNiijijijiijQy yx x的稀疏性 與線性可分情況類似，一些數(shù)據(jù)點 被正確分類，在支持超平面之外，對預(yù)測沒有貢獻(xiàn) 對 的點，必須滿足 若 ， 則 ，位于支持平面/邊界上 若 ，則 （位于支持平面/邊界里面，或 （被誤分）0i0i01Tiiiyw w xiC0,0iiiC1i1iQP的計算 最流行的SVM訓(xùn)練算法： SMO (sequential minimal optimization ) 坐標(biāo)下降法 在SVM中，因為 ，所以不能單獨改變一個 ，而是每次每次選取一對 做優(yōu)化,ij 0

6、*00wLy1i損失函數(shù) 在C-SVM中， 當(dāng) 其他點： 因此目標(biāo)函數(shù) 可寫成 其中 起到C的作用。該損失函數(shù)稱為Hinge Loss2211T011NNiiiiiiyyww xwwT01,0iiiyww xT01iiiyw w x212iiCwy與Logstic回歸之間的關(guān)系 在Logistic回歸中，令 對應(yīng)的標(biāo)簽的概率為 則負(fù)log似然函數(shù)為損失函數(shù) 再加入二次正則項，得到正則化的Logistic回歸 與SVM的目標(biāo)函數(shù)相比，只是損失函數(shù)不同21,NnlliiiregularizerLyw,log| ,log 1 expnllLyp yy x w1, 1iy |,()iiiip ysig

7、m yx w1 exp1|,1loglog1|,1 expexpTiiiTTiiiTiip yfp y w xx wxx ww xw xw x損失函數(shù) Hingle Loss和logstic誤差均可視為是分類誤差的近似ySVM for 回歸 insensitive loss： 誤差較小時不懲罰 目標(biāo)函數(shù)為 亦可寫成 為凸函數(shù)，但不可微360,if yyLy yyyotherwise21,NiiiJLy yww211,2NiiiJCCLy ywwSVM for 回歸(cond.) 實際應(yīng)用時，再加入松弛變量，用于表示每個點允許在管道外的程度 則目標(biāo)函數(shù)變?yōu)?約束為211,2NiiiJCCwwii

8、iiiiyfyfxx0,0iiSVM for 回歸(cond.) 目標(biāo)函數(shù)變?yōu)?可以證明最優(yōu)解為： 預(yù)測為： 利用kernel trick 核化線性SVM：即用核函數(shù) 代替點積 ：211,2NiiiJCCww1Niiiwx 001NTTiiiywwxw xx x 01,iiiNkywxxx,ik x xTix xSome Examples LIBSVM applet: .tw/cjlin/libsvm/ 39RVM vs. SVM 當(dāng)性能相當(dāng)時，RVM看起來比SVM的模型更稀疏，并且能給出預(yù)測信度的度量 另外，RVM 的機制更通用， 可以用于回歸、兩類分類和多類分類 可以與任意類型的基函數(shù)（不必是以數(shù)據(jù)為中心的PSD核）一起使用 RVM 能自動估計超參數(shù) SVM 通常采用交叉驗證的