支持向量機(jī)入門第1頁，共32頁，2023年，2月20日，星期五內(nèi)容SVM的理論基礎(chǔ)線性判別函數(shù)和判別面最優(yōu)分類面支持向量機(jī)LIBSVM簡介實(shí)驗(yàn)第2頁，共32頁，2023年，2月20日，星期五SVM的理論基礎(chǔ)傳統(tǒng)的統(tǒng)計(jì)模式識別方法只有在樣本趨向無窮大時，其性能才有理論的保證。統(tǒng)計(jì)學(xué)習(xí)理論（STL）研究有限樣本情況下的機(jī)器學(xué)習(xí)問題。SVM的理論基礎(chǔ)就是統(tǒng)計(jì)學(xué)習(xí)理論。傳統(tǒng)的統(tǒng)計(jì)模式識別方法在進(jìn)行機(jī)器學(xué)習(xí)時，強(qiáng)調(diào)經(jīng)驗(yàn)風(fēng)險最小化。而單純的經(jīng)驗(yàn)風(fēng)險最小化會產(chǎn)生“過學(xué)習(xí)問題”，其推廣能力較差。推廣能力是指:將學(xué)習(xí)機(jī)器(即預(yù)測函數(shù),或稱學(xué)習(xí)函數(shù)、學(xué)習(xí)模型)對未來輸出進(jìn)行正確預(yù)測的能力。

第3頁，共32頁，2023年，2月20日，星期五SVM的理論基礎(chǔ)

“過學(xué)習(xí)問題”：某些情況下，當(dāng)訓(xùn)練誤差過小反而會導(dǎo)致推廣能力的下降。例如：對一組訓(xùn)練樣本(x,y),x分布在實(shí)數(shù)范圍內(nèi)，y取值在[0，1]之間。無論這些樣本是由什么模型產(chǎn)生的，我們總可以用y=sin(w*x)去擬合，使得訓(xùn)練誤差為0.第4頁，共32頁，2023年，2月20日，星期五SVM的理論基礎(chǔ)根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險由經(jīng)驗(yàn)風(fēng)險值和置信范圍值兩部分組成。而基于經(jīng)驗(yàn)風(fēng)險最小化準(zhǔn)則的學(xué)習(xí)方法只強(qiáng)調(diào)了訓(xùn)練樣本的經(jīng)驗(yàn)風(fēng)險最小誤差，沒有最小化置信范圍值，因此其推廣能力較差。Vapnik與1995年提出的支持向量機(jī)（SupportVectorMachine,SVM）以訓(xùn)練誤差作為優(yōu)化問題的約束條件，以置信范圍值最小化作為優(yōu)化目標(biāo)，即SVM是一種基于結(jié)構(gòu)風(fēng)險最小化準(zhǔn)則的學(xué)習(xí)方法，其推廣能力明顯優(yōu)于一些傳統(tǒng)的學(xué)習(xí)方法。第5頁，共32頁，2023年，2月20日，星期五SVM的理論基礎(chǔ)由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問題的求解，因此SVM的解是全局唯一的最優(yōu)解SVM在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中.第6頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面一個線性判別函數(shù)(discriminantfunction)是指由x的各個分量的線性組合而成的函數(shù)

兩類情況:對于兩類問題的決策規(guī)則為如果g(x)>=0，則判定x屬于C1，如果g(x)<0，則判定x屬于C2第7頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面方程g(x)=0定義了一個判定面，它把歸類于C1的點(diǎn)與歸類于C2的點(diǎn)分開來。當(dāng)g(x)是線性函數(shù)時，這個平面被稱為“超平面”(hyperplane)。當(dāng)x1和x2都在判定面上時，這表明w和超平面上任意向量正交，并稱w為超平面的法向量。超平面第8頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面

判別函數(shù)g(x)是特征空間中某點(diǎn)x到超平面的距離的一種代數(shù)度量.第9頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面廣義線性判別函數(shù)

在一維空間中，沒有任何一個線性函數(shù)能解決下述劃分問題（黑紅各代表一類數(shù)據(jù)），可見線性判別函數(shù)有一定的局限性。第10頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面廣義線性判別函數(shù)如果建立一個二次判別函數(shù)g(x)=(x-a)(x-b)，則可以很好的解決上述分類問題。決策規(guī)則仍是：如果g(x)>=0，則判定x屬于C1，如果g(x)<0，則判定x屬于C2。第11頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面第12頁，共32頁，2023年，2月20日，星期五線性判別函數(shù)和判別面廣義線性判別函數(shù)第13頁，共32頁，2023年，2月20日，星期五最優(yōu)分類面SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來的,基本思想可用下圖的兩維情況說明.圖中,方形點(diǎn)和圓形點(diǎn)代表兩類樣本,H為分類線,H1,H2分別為過各類中離分類線最近的樣本且平行于分類線的直線,它們之間的距離叫做分類間隔(margin)。

所謂最優(yōu)分類線就是要求分類線不但能將兩類正確分開(訓(xùn)練錯誤率為0),而且使分類間隔最大.推廣到高維空間，最優(yōu)分類線就變?yōu)樽顑?yōu)分類面。

第14頁，共32頁，2023年，2月20日，星期五最優(yōu)分類面

設(shè)線性可分的樣本集:D維空間中的線性判別函數(shù):

這樣分類間隔就等于,因此要求分類間隔最大,就要求最大.而要求分類面對所有樣本正確分類,就是要求滿足

第15頁，共32頁，2023年，2月20日，星期五最優(yōu)分類面求最優(yōu)分類面(最大間隔法)已知：求解：目標(biāo)：最優(yōu)分類面這是一個二次凸規(guī)劃問題，由于目標(biāo)函數(shù)和約束條件都是凸的，根據(jù)最優(yōu)化理論，這一問題存在唯一全局最小解．原問題第16頁，共32頁，2023年，2月20日，星期五最優(yōu)分類面凸集和凸函數(shù)凸函數(shù)的極小：若問題有局部解，則這個局部解是整體解．

第17頁，共32頁，2023年，2月20日，星期五最優(yōu)分類面首先建立Lagrange函數(shù)

最終可得到對偶問題第18頁，共32頁，2023年，2月20日，星期五最優(yōu)分類面線性不可分的情況下，可以條件中增加一個松弛項(xiàng)成為已知：求解：目標(biāo)：最優(yōu)分類面折衷考慮最少錯分樣本和最大分類間隔，就得到廣義最優(yōu)分類面，其中，C>0是一個常數(shù)，它控制對錯分樣本懲罰的程度。第19頁，共32頁，2023年，2月20日，星期五支持向量機(jī)上節(jié)所得到的最優(yōu)分類函數(shù)為：該式只包含待分類樣本與訓(xùn)練樣本中的支持向量的內(nèi)積運(yùn)算，可見,要解決一個特征空間中的最優(yōu)線性分類問題,我們只需要知道這個空間中的內(nèi)積運(yùn)算即可。

對非線性問題,可以通過非線性變換轉(zhuǎn)化為某個高維空間中的線性問題,在變換空間求最優(yōu)分類面.這種變換可能比較復(fù)雜,因此這種思路在一般情況下不易實(shí)現(xiàn).第20頁，共32頁，2023年，2月20日，星期五支持向量機(jī)核:第21頁，共32頁，2023年，2月20日，星期五支持向量機(jī)第22頁，共32頁，2023年，2月20日，星期五支持向量機(jī)核函數(shù)的選擇第23頁，共32頁，2023年，2月20日，星期五支持向量機(jī)SVM方法的特點(diǎn)①

非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射;②

對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊界的思想是SVM方法的核心;③

支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定作用的是支持向量。

SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法。它基本上不涉及概率測度及大數(shù)定律等,因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看,它避開了從歸納到演繹的傳統(tǒng)過程,實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報樣本的“轉(zhuǎn)導(dǎo)推理”(transductiveinference),大大簡化了通常的分類和回歸等問題。第24頁，共32頁，2023年，2月20日，星期五支持向量機(jī)SVM方法的特點(diǎn)SVM的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上避免了“維數(shù)災(zāi)難”。

少數(shù)支持向量決定了最終結(jié)果,這不但可以幫助我們抓住關(guān)鍵樣本、“剔除”大量冗余樣本,而且注定了該方法不但算法簡單,而且具有較好的“魯棒”性。這種“魯棒”性主要體現(xiàn)在:①增、刪非支持向量樣本對模型沒有影響;②支持向量樣本集具有一定的魯棒性;③有些成功的應(yīng)用中,SVM方法對核的選取不敏感。第25頁，共32頁，2023年，2月20日，星期五支持向量機(jī)SVM本質(zhì)上是兩類分類器.常用的SVM多值分類器構(gòu)造方法有:

第26頁，共32頁，2023年，2月20日，星期五LIBSVM簡介

LIBSVM是臺灣大學(xué)林智仁(LinChih-Jen)副教授等開發(fā)設(shè)計(jì)的一個簡單、易于使用和快速有效的SVM模式識別與回歸的軟件包，他不但提供了編譯好的可在Windows系列系統(tǒng)的執(zhí)行文件，還提供了源代碼，方便改進(jìn)、修改以及在其它操作系統(tǒng)上應(yīng)用；該軟件還有一個特點(diǎn)，就是對SVM所涉及的參數(shù)調(diào)節(jié)相對比較少，提供了很多的默認(rèn)參數(shù)，利用這些默認(rèn)參數(shù)就可以解決很多問題.第27頁，共32頁，2023年，2月20日，星期五支持向量機(jī)第28頁，共32頁，2023年，2月20日，星期五支持向量機(jī)前面介紹的C-SVM,有兩個相互矛盾的目標(biāo):最大化間隔和最小化訓(xùn)練錯誤.其中的常數(shù)C起著調(diào)和這兩個目標(biāo)的作用.定性地講,C值有著明確的含義:選取大的C值,意味著更強(qiáng)調(diào)最小化訓(xùn)練錯誤.但定量地講,C值本身并沒有確切的意義,所以C值的選取比較困難.為此,人們提出了這個改進(jìn)的方法.1、間隔錯誤樣本的個數(shù)所占總樣本數(shù)的份額的上界;2、支持向量的個數(shù)所占總樣本點(diǎn)數(shù)的份額的下界.第29頁，共32頁，2023年，2月20日，星