svm算法簡介解析ppt課件

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

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

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

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

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

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

7、,l （這里0指的是零向量） 定義,當(dāng)所有約束條件都滿足時有,對偶問題,一般有 ，但是在某些特定條件下（KKT），這兩個最優(yōu)化問題會取相同的值。 （經(jīng)證明，我們求解的目標(biāo)函數(shù)滿足條件KKT條件,1.首先固定，要讓L關(guān)于w和b最小化，我們分別對w,b偏導(dǎo)并令其等于零，得到 帶回 得到,凸二次規(guī)劃問題求解,問題轉(zhuǎn)換為： 由凸二次規(guī)劃的性質(zhì)能保證這樣最優(yōu)的向量a是存在的,凸二次規(guī)劃問題求解,2.求對的極大，即是關(guān)于對偶變量的優(yōu)化問題 （SMO優(yōu)化算法-序列最小最優(yōu)化算法） 然后根據(jù) 可求出最優(yōu)的w和b，即最優(yōu)超平面,一個簡單的例子,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的值，進而求得w和b的值,線性不可分情況下,情況1：樣本本質(zhì)上是非線性可分的 解決方法：核函數(shù),將分類函數(shù)變形得最終分類函數(shù)，為,根據(jù)線性可分情況下的結(jié)論,我們把橫軸上斷電a,b之間紅色部分里的所有點定為正類，兩邊黑色部分定為負(fù)類，不能找到一個線性函數(shù)將兩類正確分開,問題引入,但是能找到一條二次曲線將正負(fù)類分開，它的函數(shù)表達(dá)式可以寫為,問題只是它不是一個線性函數(shù)，但是，新建一個向量在z和a,在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)（只

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

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

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

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

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

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

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

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