svm算法簡(jiǎn)介解析ppt課件

1、svm(supported vector machine,概念： 支持向量機(jī)是Corinna Cortes和Vapnik等于1995年首先提出的，其基本原理是（以二維數(shù)據(jù)為例）：如果訓(xùn)練數(shù)據(jù)是分布在二維平面上的點(diǎn)，它們按照其分類聚集在不同的區(qū)域?；诜诸愡吔绲姆诸愃惴ǖ哪繕?biāo)是，通過(guò)訓(xùn)練，找到這些分類之間的邊界。對(duì)于多維數(shù)據(jù)（如N維），可以將它們視為N維空間中的點(diǎn)，而分類邊界就是N維空間中的面，稱為超面（超面比N維空間少一維）。線性分類器使用超平面類型的邊界，非線性分類器使用超曲面。 數(shù)據(jù)：線性可分&線性不可分,線性可分 線性不可分 情況1：樣本本質(zhì)上是非線性可分的 解決方法：核函數(shù) 情況2：本

2、質(zhì)上線性，非線性由噪音導(dǎo)致 強(qiáng)制使用非線性函數(shù)，會(huì)導(dǎo)致過(guò)擬合 解決方法：軟間隔,兩種情況,線性可分,定義： 對(duì)于來(lái)自兩類的一組模式 ,如果能用一個(gè)線性判別函數(shù)正確分類,則稱他們是線性可分的,線性不可分,線性可分情況,我們?cè)鯓硬拍苋〉靡粋€(gè)最優(yōu)的劃分直線f(x)呢,最大距離Maximum Marginal,從概率的角度上來(lái)說(shuō)，就是使得置信度最小的點(diǎn)置信度最大 從實(shí)踐的角度來(lái)說(shuō)，這樣的效果非常好 從誤差的角度，誤分次數(shù) （其中， 是樣本集合到分類面的間隔，R是空間中一個(gè)能完全包含樣本數(shù)據(jù)的球的半徑）誤分次數(shù)一定程度上代表分類器的誤差，間隔越大的解，它的誤差上界越小,函數(shù)間隔,定義函數(shù)間隔為： 接著，

3、我們定義超平面（w,b）關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔為超平面（w,b）關(guān)于T中所有樣本點(diǎn)（xi,yi）的函數(shù)間隔最小值，其中，x是特征，y是結(jié)果標(biāo)簽，i表示第i個(gè)樣本，有,定義函數(shù)間隔的原因,一般而言，一個(gè)點(diǎn)距離超平面的遠(yuǎn)近可以表示為分類預(yù)測(cè)的確信或準(zhǔn)確程度。在超平面 確定的情況下， 能夠相對(duì)的表示點(diǎn)X到超平面的遠(yuǎn)近，而 的符號(hào)與類標(biāo)記y的符號(hào)是否一致表示分類是否正確，所以，可以用量 的正負(fù)性來(lái)判定或表示分類的正確性和確信度，于是引出函數(shù)間隔概念,函數(shù)間隔的局限性,上述定義的函數(shù)間隔雖然可以表示分類預(yù)測(cè)的正確性和確信度，但在選擇分類超平面時(shí)，只有函數(shù)間隔還遠(yuǎn)遠(yuǎn)不夠，因?yàn)槿绻杀壤母淖僿和b，如

4、將他們改變?yōu)?w和2b，雖然此時(shí)超平面沒(méi)有改變，但函數(shù)間隔的值卻發(fā)生改變。我們可以對(duì)法向量w加些約束條件，使其表面看起來(lái)規(guī)范化，如此，我們引入了真正意義點(diǎn)到超平面的距離-幾何間隔,幾何間隔,在函數(shù)間隔 的基礎(chǔ)上，對(duì)w和b進(jìn)行歸一化，即為幾何間隔： 這時(shí)如果成比例的改變w和b，幾何間隔的值不會(huì)發(fā)生改變,因?yàn)閣x+b=0，為了方便，我們可以按任意比例縮放w和b，而不會(huì)改變結(jié)果。我們可以添加這樣的約束條件 ，這意味著可以先求出w和b的解，之后重新縮放這些參數(shù)，就可以輕易地滿足這個(gè)條件,最大間隔分類器的定義,由于函數(shù)間隔的缺陷，不適合用來(lái)最大化一個(gè)量，因?yàn)樵诔矫婀潭ㄒ院?，我們可以等比例地縮放w好b的

5、值，這樣可以使得 的值任意打，亦即函數(shù)間隔可以在超平面不變的情況下被取得任意大。 而幾何間隔則沒(méi)有這個(gè)問(wèn)題，因?yàn)槌?這個(gè)分母，所以縮放w和b的時(shí)候幾何間隔不會(huì)隨之改變，它只隨超平面的變動(dòng)而變動(dòng)，因此更加適合用其來(lái)定義最大距離,因此，我們的最大間隔分類的目標(biāo)函數(shù)可以定義為： 事實(shí)證明這個(gè)約束是一個(gè)非凸性約束，我們需要避免，所以我們需要改變優(yōu)化問(wèn)題的表述方式,添加約束條件， 這是一個(gè)隱含的縮放約束，因?yàn)榧僭O(shè)你已經(jīng)解出了w和b，并且發(fā)現(xiàn)最差情形的函數(shù)間隔是10或者其他值，這樣，通過(guò)對(duì)w和b除以10或者其他值，我們可以將函數(shù)間隔變?yōu)?,此時(shí)，優(yōu)化問(wèn)題的表達(dá)式為： 我們的優(yōu)化問(wèn)題轉(zhuǎn)變成了一個(gè)凸優(yōu)化問(wèn)題

6、,目標(biāo)函數(shù)是二次的，約束條件是線性的，所以這是一個(gè)凸二次規(guī)劃問(wèn)題，所以一定會(huì)存在全局的最優(yōu)解，這個(gè)問(wèn)題可以用現(xiàn)成的QP（quadratic programming）優(yōu)化包或者二次程序軟件進(jìn)行求解。 此外，由于這個(gè)問(wèn)題的特殊結(jié)構(gòu)，還可以通過(guò)拉格朗日對(duì)偶性變換到對(duì)偶變量的優(yōu)化問(wèn)題，即通過(guò)與原問(wèn)題等價(jià)的對(duì)偶問(wèn)題得到原始問(wèn)題的最優(yōu)解，這就是線性可分條件下支持向量機(jī)的對(duì)偶算法，這樣做的優(yōu)點(diǎn)在于：一者對(duì)偶問(wèn)題往往更容易求解，二者可以自然的引入核函數(shù)，進(jìn)而推廣到非線性分類問(wèn)題,最優(yōu)問(wèn)題的求解,拉格朗日乘數(shù)法的擴(kuò)展形式,minf(w) s.t. gi(w)0 i=1,2,.,k hi(w)=0 i=1,2,.

7、,l （這里0指的是零向量） 定義,當(dāng)所有約束條件都滿足時(shí)有,對(duì)偶問(wèn)題,一般有 ，但是在某些特定條件下（KKT），這兩個(gè)最優(yōu)化問(wèn)題會(huì)取相同的值。 （經(jīng)證明，我們求解的目標(biāo)函數(shù)滿足條件KKT條件,1.首先固定，要讓L關(guān)于w和b最小化，我們分別對(duì)w,b偏導(dǎo)并令其等于零，得到 帶回 得到,凸二次規(guī)劃問(wèn)題求解,問(wèn)題轉(zhuǎn)換為： 由凸二次規(guī)劃的性質(zhì)能保證這樣最優(yōu)的向量a是存在的,凸二次規(guī)劃問(wèn)題求解,2.求對(duì)的極大，即是關(guān)于對(duì)偶變量的優(yōu)化問(wèn)題 （SMO優(yōu)化算法-序列最小最優(yōu)化算法） 然后根據(jù) 可求出最優(yōu)的w和b，即最優(yōu)超平面,一個(gè)簡(jiǎn)單的例子,x1 =(0, 0), y1 = +1 x2 =(1, 0), y2

8、 = +1 x3 =(2, 0), y3 = -1 x4 =(0, 2), y4 = -1,可調(diào)用Matlab中的二次規(guī)劃程序，求得1, 2, 3, 4的值，進(jìn)而求得w和b的值,線性不可分情況下,情況1：樣本本質(zhì)上是非線性可分的 解決方法：核函數(shù),將分類函數(shù)變形得最終分類函數(shù)，為,根據(jù)線性可分情況下的結(jié)論,我們把橫軸上斷電a,b之間紅色部分里的所有點(diǎn)定為正類，兩邊黑色部分定為負(fù)類，不能找到一個(gè)線性函數(shù)將兩類正確分開(kāi),問(wèn)題引入,但是能找到一條二次曲線將正負(fù)類分開(kāi)，它的函數(shù)表達(dá)式可以寫(xiě)為,問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，新建一個(gè)向量在z和a,在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)（只

9、不過(guò)其中的a,z是多維向量），因此，自變量z的次數(shù)不大于1。經(jīng)過(guò)映射，判別函數(shù)為,原來(lái)在二維空間中一個(gè)線性不可分的問(wèn)題，映射到四維空間后，變成了線性可分的。因此，這也形成了我們最初想解決線性不可分問(wèn)題的基本思路-向高維空間轉(zhuǎn)化，使其變得線性可分。 而轉(zhuǎn)化的關(guān)鍵的部分在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個(gè)映射沒(méi)有系統(tǒng)的方法，此外，在數(shù)據(jù)維度較大時(shí)，計(jì)算困難（我們對(duì)一個(gè)二維空間做映射，選擇的新空間是原始空間的所有一階和二階的組合，得到了五個(gè)維度；如果原始空間是三維，那么我們會(huì)得到 19 維的新空間，這個(gè)數(shù)目是呈爆炸性增長(zhǎng)的，這給 的計(jì)算帶來(lái)了非常大的困難，而且如果遇到無(wú)窮維的情況，就根本

10、無(wú)從計(jì)算了,如果有一種方式可以在特征空間中直接計(jì)算內(nèi)積(xi ） (x)，就像在原始輸入點(diǎn)的函數(shù)中一樣，就有可能將兩個(gè)步驟融合到一起建立一個(gè)非線性的學(xué)習(xí)器，這樣直接計(jì)算法的方法稱為核函數(shù)方法，于是，核函數(shù)便橫空出世了。 核函數(shù)：對(duì)所有x,z屬于X，滿足 這里 是從X到內(nèi)積特征空間F的映射,分類函數(shù)為,優(yōu)化問(wèn)題的表達(dá)式,常見(jiàn)核函數(shù),多項(xiàng)式核 線性核 高斯徑向基函數(shù)核 Sigmoid核,對(duì)于核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則。各種實(shí)驗(yàn)的觀察結(jié)果表明，某些問(wèn)題用某些核函數(shù)效果很好，用另一些很差，但一般來(lái)講，徑向基核函數(shù)是不會(huì)出現(xiàn)太大偏差的一種，首選。 如果使用核函數(shù)向高維空間映射后，問(wèn)題仍然是線性不可

11、分的，怎么辦,情況2：本質(zhì)上線性，非線性由噪音導(dǎo)致 強(qiáng)制使用非線性函數(shù)，會(huì)導(dǎo)致過(guò)擬合 解決方法：軟間隔,想象我們有另一個(gè)訓(xùn)練集，它是方形的（負(fù)類），這單獨(dú)的一個(gè)樣本使得原本線性可分的問(wèn)題變成了線性不可分的。這樣類似的問(wèn)題（僅有少數(shù)點(diǎn)線性不可分）。叫做“近線性可分”問(wèn)題,我們會(huì)覺(jué)得，這個(gè)點(diǎn)可能是錯(cuò)誤的，是噪聲。所以我們會(huì)簡(jiǎn)單的忽略這個(gè)樣本點(diǎn)，仍然使用原來(lái)的分類器，其效果絲毫不受影響。 但這種對(duì)噪聲的容錯(cuò)性是人的思維帶來(lái)的，我們的程序沒(méi)有，在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表距離，是非負(fù)的，像這種情況會(huì)使得整個(gè)問(wèn)題無(wú)解。這種解法其實(shí)也叫做“硬間隔”分類法，因?yàn)樗残缘囊笏?/p>

12、樣本點(diǎn)都滿足和分類平面間的距離大于某個(gè)值。 由上面的例子可以看出，硬間隔分類法其結(jié)果容易受少數(shù)點(diǎn)的控制,解決方法,允許一些點(diǎn)到分類平面的距離不滿足原先的要求。原先對(duì)樣本點(diǎn)的要求是（意思是說(shuō)離分類面最近的樣本點(diǎn)函數(shù)間隔要比1大）： 如果引入容錯(cuò)性，就給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許,因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)（這些點(diǎn)叫離群點(diǎn)），意味著我們放棄了對(duì)這些點(diǎn)的精確分類，而這對(duì)我們的分類器來(lái)說(shuō)是種損失。但是放棄這些點(diǎn)也帶來(lái)了好處，那就是使分類面不必向這些點(diǎn)的方向移動(dòng)，因而可以得到更大的間隔,如何衡量損失,把損失加入到目標(biāo)函數(shù)里

13、的時(shí)候，就需要一個(gè)懲罰因子C，原來(lái)的優(yōu)化問(wèn)題變?yōu)?注意,并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)，實(shí)際上只有離群點(diǎn)才有。 松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群多遠(yuǎn)，值越大，點(diǎn)越遠(yuǎn)。 懲罰因子決定了你有多重視離群點(diǎn)帶來(lái)的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時(shí)，你定的C越大，對(duì)目標(biāo)函數(shù)的損失也越大，此時(shí)就暗示著你非常不愿意放棄這些離群點(diǎn)，最極端的情況是你把C定為無(wú)限大，這樣只要稍有一個(gè)點(diǎn)離群，目標(biāo)函數(shù)的值馬上變成無(wú)限大，馬上讓問(wèn)題變成無(wú)解，這就退化成了硬間隔問(wèn)題,注意,懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問(wèn)題在解的時(shí)候，C是一個(gè)你必須事先指定的值，指定這個(gè)值以后，解一下，得到一個(gè)分類器，然后

14、用測(cè)試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個(gè)C的值，再解一次優(yōu)化問(wèn)題，得到另一個(gè)分類器，再看看效果，如此就是一個(gè)參數(shù)尋優(yōu)的過(guò)程，但這和優(yōu)化問(wèn)題本身不是一回事，優(yōu)化問(wèn)題在求解的過(guò)程中，C一直是定值。 盡管加入了松弛變量，但是優(yōu)化問(wèn)題的求解過(guò)程與硬間隔問(wèn)題求解過(guò)程無(wú)異,用之前的方法將限制條件加入到目標(biāo)函數(shù)中，得到新的拉格朗日函數(shù)， 分析方法和前面一樣，讓L對(duì)w,b,最小化 將w帶回目標(biāo)函數(shù)并化簡(jiǎn)得到,不過(guò)，由于我們得到 而又有 （作為拉格朗日乘數(shù)法的條件），因此有 優(yōu)化表達(dá)式變?yōu)?和之前的結(jié)果對(duì)比一下，可以看到唯一的區(qū)別就是多了一個(gè)上限C,而核函數(shù)化的非線性形式也是一樣的，只要把 換成k即可,加入

15、松弛變量的優(yōu)化問(wèn)題求解過(guò)程,先試著確定一下w，也就是確定圖中的三條直線，看看間隔有多大，有多少離群點(diǎn)，算出目標(biāo)函數(shù)。然后換一組三條直線，再把目標(biāo)函數(shù)的值算一下，如此迭代，直到找到目標(biāo)函數(shù)最小時(shí)的w,特例-偏斜問(wèn)題,樣本的偏斜，也叫數(shù)據(jù)集偏斜，它是指參與分類的兩個(gè)類別（也可以指多個(gè)類別）樣本數(shù)量差異很大，比如說(shuō)正類有10000個(gè)樣本，而負(fù)類只有100個(gè)，如圖,方形的點(diǎn)是負(fù)類，H,H1，H2是根據(jù)給的樣本算出來(lái)的分類面，由于負(fù)類的樣本很少很少，所以有一些本來(lái)是負(fù)類的樣本沒(méi)有提供，比如圖中兩個(gè)灰色的方形點(diǎn)，如果這兩個(gè)點(diǎn)提供的話，那么算出來(lái)的分類面應(yīng)該是H”，H2”,H1，實(shí)際上負(fù)類給的樣本點(diǎn)越多，越

16、容易出現(xiàn)在灰色點(diǎn)附近的點(diǎn)，我們算出的結(jié)果也就越接近于真實(shí)的分類面，但現(xiàn)在由于出現(xiàn)偏斜的現(xiàn)象，使得數(shù)量多的正類可以把分類面向負(fù)類方向“推”，因而影響了結(jié)果的準(zhǔn)確性,解決方法,給樣本量少的負(fù)類更大的懲罰因子，表示我們重視這部分樣本（本來(lái)樣本就少，所以拋棄的應(yīng)該少），因此我們的目標(biāo)函數(shù)中因松弛變量而損失的部分變成了,樣本的偏斜不僅由于數(shù)量，還由樣本分布的廣度決定。說(shuō)一個(gè)具體的例子，給政治類和體育類的文章做分類，政治類的文章多，而體育類只提供幾篇關(guān)于籃球的文章，這時(shí)分類會(huì)明顯偏向于政治類，如果要給體育類增加樣本，但增加的樣本仍然全都是籃球的，那即使體育類文章在數(shù)量上可以達(dá)到與政治類一樣多，但過(guò)于集中了，結(jié)果仍偏向政治類,所以，給C+和C-確定比例更好的方法可以是衡量他們