周志華-機(jī)器學(xué)習(xí)-西瓜書-全書16章-ppt-Chap06支持向量機(jī)ppt課件

1、第六章：支持向量機(jī),大綱,間隔與支持向量 對(duì)偶問題 核函數(shù) 軟間隔與正則化 支持向量回歸 核方法,引子,線性模型：在樣本空間中尋找一個(gè)超平面, 將不同類別的樣本分開,0,引子,Q:將訓(xùn)練樣本分開的超平面可能有很多, 哪一個(gè)好呢,0,引子,Q:將訓(xùn)練樣本分開的超平面可能有很多, 哪一個(gè)好呢,A:應(yīng)選擇”正中間”, 容忍性好, 魯棒性高, 泛化能力最強(qiáng),0,間隔與支持向量,超平面方程,間隔,0,支持向量,支持向量機(jī)基本型,最大間隔: 尋找參數(shù) 和 , 使得 最大,其中f(x)是目標(biāo)函數(shù)，g(x)為不等式約束，h(x)為等式約束。 若f(x)，h(x)，g(x)三個(gè)函數(shù)都是線性函數(shù)，則該優(yōu)化問題稱為

2、線性規(guī)劃。 若任意一個(gè)是非線性函數(shù)，則稱為非線性規(guī)劃。 若目標(biāo)函數(shù)為二次函數(shù)，約束全為線性函數(shù)，稱為二次規(guī)劃。 若f(x)為凸函數(shù)，g(x)為凸函數(shù)，h(x)為線性函數(shù)，則該問題稱為凸優(yōu)化。 注意這里不等式約束g(x)=0則要求g(x)為凹函數(shù)。 凸優(yōu)化的任一局部極值點(diǎn)也是全局極值點(diǎn)，局部最優(yōu)也是全局最優(yōu),等式約束,考慮一個(gè)簡單的問題目標(biāo)函數(shù),不考慮圓h(x)的限制時(shí)，f(x)要得到極小值，需要往f(x)的負(fù)梯度（下降最快的方向）方向走，如下左圖藍(lán)色箭頭。 如果考慮圓h(x)的限制，要得到極小值，需要沿著圓的切線方向走，如下右圖紅色粗箭頭。注意這里的方向不是h(x)的梯度，而是正交于h(x)的

3、梯度，h(x)梯度如下右圖的紅色細(xì)箭頭。 在極小值點(diǎn)，f(x)和h(x)的等高線是相切的,在關(guān)鍵的極小值點(diǎn)處，f(x)的負(fù)梯度和h(x)的梯度在同一直線上， 如下圖左下方critical point的藍(lán)色和紅色箭頭所示,特別注意：優(yōu)化問題是凸優(yōu)化的話，通過上圖兩個(gè)條件求得的解就是極小值點(diǎn)（而且是全局極?。２皇峭箖?yōu)化的話，這兩個(gè)條件只是極小值點(diǎn)的必要條件，還需要附加多一個(gè)正定的條件才能變成充要條件，如下圖所示,不等式約束,對(duì)于不等式約束g(x)=0和等式約束h(x)=0不一樣，h(x)=0可以在平面上畫出一條等高線，而 g(x)=0是一個(gè)區(qū)域，很多個(gè)等高線堆疊而成的一塊區(qū)域，我們把這塊區(qū)域稱為

4、可行域,極小值點(diǎn)落在可行域內(nèi)（不包含邊界,極小值點(diǎn)落在可行域外（包含邊界,對(duì)于f(x)而言要沿著f(x)的負(fù)梯度方向走，才能走到極小值點(diǎn)，如下圖的藍(lán)色箭頭。 這個(gè)時(shí)候g(x)的梯度往區(qū)域外發(fā)散，如下圖紅色箭頭。 顯然，走到極小值點(diǎn)的時(shí)候，g(x)的梯度和f(x)的負(fù)梯度同向。因?yàn)闃O小值點(diǎn)在邊界上，這個(gè)時(shí)候g(x)等于0,極小值點(diǎn)落在可行域內(nèi)（不包含邊界）：這個(gè)時(shí)候可行域的限制不起作用，相當(dāng)于沒有約束，直接f(x)的梯度等于0求解，這個(gè)時(shí)候g(x極小值點(diǎn))0（因?yàn)槁湓诳尚杏騼?nèi)）。 極小值點(diǎn)落在可行域外（包含邊界）：可行域的限制起作用，極小值點(diǎn)應(yīng)該落在可行域邊界上即g(x)=0，類似于等值約束，此

5、時(shí)有g(shù)(x)的梯度和f(x)的負(fù)梯度同向,總結(jié),總結(jié),對(duì)于不等式約束的優(yōu)化，需要滿足三個(gè)條件，滿足這三個(gè)條件的解x*可能的極小值點(diǎn)。 這三個(gè)條件就是著名的KKT條件，它整合了上面兩種情況的條件,優(yōu)化問題是凸優(yōu)化的話，KKT條件就是極小值點(diǎn)（而且是全局極?。┐嬖诘某湟獥l件。 不是凸優(yōu)化的話，KKT條件只是極小值點(diǎn)的必要條件，不是充分條件，KKT點(diǎn)是駐點(diǎn)，是可能的極值點(diǎn)。也就是說，就算求得的滿足KKT條件的點(diǎn)，也不一定是極小值點(diǎn)，只是說極小值點(diǎn)一定滿足KKT條件,特別注意,不是凸優(yōu)化的話，還需要附加多一個(gè)正定的條件才能變成充要條件，如下圖所示,推廣到多個(gè)等式和不對(duì)等式約束,總結(jié),對(duì)偶方法,大綱,間

6、隔與支持向量 對(duì)偶問題 核函數(shù) 軟間隔與正則化 支持向量回歸 核方法,對(duì)偶問題 拉格朗日乘子法,和,第三步：回代可得,解的稀疏性,最終模型： KKT條件,支持向量機(jī)解的稀疏性: 訓(xùn)練完成后, 大部分的訓(xùn)練樣本都不需保留, 最終模型僅與支持向量有關(guān). 重要性質(zhì)：模型訓(xùn)練完后，大部分的訓(xùn)練樣本都不需要 保留，最終模型僅僅與支持向量有關(guān),必有,或,對(duì)偶方法重新求解前面的問題,對(duì)偶方法重新求解前面的問題,第一步：轉(zhuǎn)化為對(duì)偶問題,第二步：代入約束條件,第三步：利用KKT條件，計(jì)算向量w,第四步：利用KKT條件，計(jì)算b,如果樣本變多，人工計(jì)算不現(xiàn)實(shí)，需要一種高效的計(jì)算算法,高效求解方法 SMO: sequ

7、ential minimal optimization,基本思路：不斷執(zhí)行如下兩個(gè)步驟直至收斂. 第一步：選取一對(duì)需更新的變量 和 . 第二步：固定 和 以外的參數(shù), 求解對(duì)偶問題更新 和 . 僅考慮 和 時(shí), 對(duì)偶問題的約束變?yōu)?偏移項(xiàng) ：通過支持向量來確定,用一個(gè)變量表示另一個(gè)變量, 回代入對(duì)偶問題可得一個(gè)單變量的二次規(guī)劃, 該問題具有閉式解,SMO 變量選擇原則,第一個(gè)變量是在KKT條件不滿足的中間選擇，直觀來看，KKT條件違背的程度越大，則變量更新后可能會(huì)使得目標(biāo)函數(shù)的增幅越大，從而選擇違背KKT條件程度越大的變量 第二個(gè)變量應(yīng)選擇使得目標(biāo)函數(shù)增長最快的變量；常用啟發(fā)式，也就是兩樣本的

8、間距最大,大綱,間隔與支持向量 對(duì)偶問題 核函數(shù) 軟間隔與正則化 支持向量回歸 核方法,線性不可分,Q:若不存在一個(gè)能正確劃分兩類樣本的超平面, 怎么辦? -A:將樣本從原始空間映射到一個(gè)更高維的特征空間, 使得樣本在這個(gè)特征空間內(nèi)線性可分,核支持向量機(jī),設(shè)樣本 映射后的向量為 , 劃分超平面為,原始問題,對(duì)偶問題,預(yù)測(cè),只以內(nèi)積的形式出現(xiàn),核函數(shù),基本想法：不顯式地設(shè)計(jì)核映射, 而是設(shè)計(jì)核函數(shù). Mercer定理(充分非必要)：只要一個(gè)對(duì)稱函數(shù)所對(duì)應(yīng)的核矩陣半正定, 則它就能作為核函數(shù)來使用,核函數(shù),基本想法：不顯式地設(shè)計(jì)核映射, 而是設(shè)計(jì)核函數(shù). Mercer定理(充分非必要)：只要一個(gè)對(duì)

9、稱函數(shù)所對(duì)應(yīng)的核矩陣半正定, 則它就能作為核函數(shù)來使用. 常用核函數(shù),核函數(shù)的注意事項(xiàng),核函數(shù)選擇成為svm的最大變數(shù) 經(jīng)驗(yàn)：文本數(shù)據(jù)使用線性核，情況不明使用高斯核 核函數(shù)的性質(zhì)： 1 核函數(shù)的線性組合仍為核函數(shù) 2 核函數(shù)的直積仍為核函數(shù) 3 設(shè) 為核函數(shù)，則對(duì)于任意函數(shù)g,大綱,間隔與支持向量 對(duì)偶問題 核函數(shù) 軟間隔與正則化 支持向量回歸 核方法,軟間隔,Q:現(xiàn)實(shí)中, 很難確定合適的核函數(shù)使得訓(xùn)練樣本在特征空間中線性可分; 同時(shí)一個(gè)線性可分的結(jié)果也很難斷定是否是有過擬合造成的. -A:引入”軟間隔”的概念, 允許支持向量機(jī)在一些樣本上不滿足約束,0,不滿足約束的樣本,0/1損失函數(shù),基本

10、想法：最大化間隔的同時(shí), 讓不滿足約束的樣本應(yīng)盡可能少.其中 是”0/1損失函數(shù)” 存在的問題：0/1損失函數(shù)非凸、非連續(xù), 不易優(yōu)化,替代損失,0,1,2,1,2,1,2,3,替代損失函數(shù)數(shù)學(xué)性質(zhì)較好, 一般是0/1損失函數(shù)的上界,軟間隔SVM,軟間隔支持向量機(jī),原始問題,軟間隔與松弛向量,超平面方程,0,軟間隔與松弛向量,超平面方程,0,軟間隔與松弛向量,超平面方程,0,軟間隔與松弛向量,超平面方程,0,軟間隔與松弛向量,超平面方程,0,軟間隔與松弛向量,超平面方程,0,求解軟間隔問題,構(gòu)造Lagrange 函數(shù),軟間隔支持向量機(jī),原始問題,對(duì)偶問題,根據(jù)KKT條件可推得最終模型僅與支持向

11、量有關(guān), 也即hinge損失函數(shù)依然保持了支持向量機(jī)解的稀疏性,軟間隔支持向量機(jī)KKT條件,KKT條件背后的結(jié)論,分類正確,支持向量,C-SVC 機(jī)的變形,C-SVC 機(jī)的等價(jià)變形,多余了,C-SVC 機(jī)的變形的對(duì)偶,軟間隔SVM,軟間隔支持向量機(jī)-稀疏性原因,正則化,支持向量機(jī)學(xué)習(xí)模型的更一般形式 通過替換上面兩個(gè)部分, 可以得到許多其他學(xué)習(xí)模型 對(duì)數(shù)幾率回歸(Logistic Regression) 最小絕對(duì)收縮選擇算子(LASSO),結(jié)構(gòu)風(fēng)險(xiǎn), 描述模型的某些性質(zhì),經(jīng)驗(yàn)風(fēng)險(xiǎn), 描述模型與訓(xùn)練數(shù)據(jù)的契合程度,正則化,正則化,大綱,間隔與支持向量 對(duì)偶問題 核函數(shù) 軟間隔與正則化 支持向量回

12、歸 核方法,支持向量回歸機(jī)-SVR,0,間隔帶,對(duì)于有限個(gè)樣本組成的訓(xùn)練集來說，一定存在一個(gè)帶狀區(qū)域包含所有的樣本點(diǎn)。并且這樣的帶狀區(qū)域有無窮多個(gè)，寬度最小的帶狀區(qū)域才是我們關(guān)心的,支持向量回歸,當(dāng)帶狀區(qū)域很大，所得的回歸模型不精確，此時(shí)允許模型輸出和實(shí)際輸出間存在 的偏差,0,間隔帶,支持向量回歸,損失函數(shù),落入中間 間隔帶的樣本不計(jì)算損失, 從而使得模型獲得稀疏性,0,最小二乘損失函數(shù),支持向量回歸損失函數(shù),支持向量回歸,形式化,原始問題,對(duì)偶問題,預(yù)測(cè),推導(dǎo)SVR,大綱,間隔與支持向量 對(duì)偶問題 核函數(shù) 軟間隔與正則化 支持向量回歸 核方法,表示定理,結(jié)論: 無論是支持向量機(jī)還是支持向量

13、回歸, 學(xué)得的模型總可以表示成核函數(shù)的線性組合. 更一般的結(jié)論(表示定理): 對(duì)于任意單調(diào)增函數(shù) 和任意非負(fù)損失函數(shù) , 優(yōu)化問題 的解總可以寫為,支持向量機(jī),支持向量回歸,核線性判別分析,通過表示定理可以得到很多線性模型的”核化”版本 核SVM 核LDA 核PCA 核LDA: 先將樣本映射到高維特征空間, 然后在此特征空間中做線性判別分析,Take Home Message,支持向量機(jī)的”最大間隔”思想 對(duì)偶問題及其解的稀疏性 通過向高維空間映射解決線性不可分的問題 引入”軟間隔”緩解特征空間中線性不可分的問題 將支持向量的思想應(yīng)用到回歸問題上得到支持向量回歸 將核方法推廣到其他學(xué)習(xí)模型,成熟的SVM軟件包,LIBSVMhttp:/www.