人工智能大作業(yè)21

1、.：.；研討報(bào)告題 目 支持向量機(jī)學(xué)習(xí)報(bào)告 學(xué) 號(hào) 學(xué) 生 支持向量機(jī)學(xué)習(xí)報(bào)告支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)實(shí)際的VC 維實(shí)際和構(gòu)造風(fēng)險(xiǎn)最小原理根底上的，根據(jù)有限的樣本信息在模型的復(fù)雜性即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度和學(xué)習(xí)才干即無錯(cuò)誤地識(shí)別恣意樣本的才干之間尋求最正確折衷，以期獲得最好的推行才干。支持向量機(jī)SVM(Support Vector Machine)是AT&TBell實(shí)驗(yàn)室的VVapnik提出的針對(duì)分類和回歸問題的統(tǒng)計(jì)學(xué)習(xí)實(shí)際。由于SVM方法具有許多優(yōu)點(diǎn)和有出路的實(shí)驗(yàn)性能，該技術(shù)已成為機(jī)器學(xué)習(xí)研討領(lǐng)域中的熱點(diǎn)，并獲得很理想的效果，如人臉識(shí)別、手寫體數(shù)字識(shí)別和網(wǎng)頁(yè)分類等。1原理及方法SVM

2、根據(jù)問題的復(fù)雜性可以分為線性可分SVM和非線性可分SVM，其根本原理如下：在進(jìn)展文本分類的時(shí)候，每一個(gè)樣本由一個(gè)向量就是那些文本特征所組成的向量和一個(gè)標(biāo)志標(biāo)示出這個(gè)樣本屬于哪個(gè)類別組成。如下： Di=(xi,yi) xi就是文本向量維數(shù)很高，yi就是分類標(biāo)志。 在二元的線性分類中，這個(gè)表示分類的標(biāo)志只需兩個(gè)值，1和-1用來表示屬于還是不屬于這個(gè)類。有了這種表示法，可以定義一個(gè)樣本點(diǎn)到某個(gè)超平面的間隔： yi(wxi+b)假設(shè)某個(gè)樣本屬于該類別的話，那么wxi+b0由于我們所選的g(x)=wx+b就經(jīng)過大于0還是小于0來判別分類，而yi也大于0；假設(shè)不屬于該類別的話，那么wxi+b 核函數(shù)矩陣K

3、是對(duì)稱半正定的。這個(gè)條件也是充分的，由Mercer定理來表達(dá)。Mercer定理：假設(shè)函數(shù)K是上的映射也就是從兩個(gè)n維向量映射到實(shí)數(shù)域。那么假設(shè)K是一個(gè)有效核函數(shù)也稱為Mercer核函數(shù)，那么當(dāng)且僅當(dāng)對(duì)于訓(xùn)練樣例，其相應(yīng)的核函數(shù)矩陣是對(duì)稱半正定的。Mercer定理闡明為了證明K是有效的核函數(shù)，那么不用去尋覓，而只需求在訓(xùn)練集上求出各個(gè)，然后判別矩陣K能否是半正定運(yùn)用左上角主子式大于等于零等方法即可。把一個(gè)本來線性不可分的文本分類問題，經(jīng)過映射到高維空間而變成了線性可分的。就像以下圖這樣： 圓形和方形的點(diǎn)各有成千上萬個(gè)。如今想象我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一篇文章，映射到高維空間以后

4、當(dāng)然，也運(yùn)用了一樣的核函數(shù)，也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的：就是圖中黃色那個(gè)點(diǎn)，它是方形的，因此它是負(fù)類的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使得本來線性可分的問題變成了線性不可分的。這樣類似的問題僅有少數(shù)點(diǎn)線性不可分叫做“近似線性可分的問題。 但這種對(duì)噪聲的容錯(cuò)性是人的思想帶來的。由于本來的優(yōu)化問題的表達(dá)式中，確實(shí)要思索一切的樣本點(diǎn)，在此根底上尋覓正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是間隔 ，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問題無解。這種解法其實(shí)也叫做“硬間隔分類法，由于他硬性的要求一切樣本點(diǎn)都滿足和分類平面間的間隔 必需大于某個(gè)值。 仿照人的思緒，允許一些點(diǎn)到分

5、類平面的間隔 不滿足原先的要求。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一樣，因此用間隔而不是幾何間隔來衡量有利于我們表達(dá)方式的簡(jiǎn)約。我們?cè)葘?duì)樣本點(diǎn)的要求是： 意思是說離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。假設(shè)要引入容錯(cuò)性，就給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許由于松弛變量是非負(fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)這些點(diǎn)也叫離群點(diǎn)，意味著我們放棄了對(duì)這些點(diǎn)的準(zhǔn)確分類，而這對(duì)我們的分類器來說是種損失。但是放棄這些點(diǎn)也帶來了益處，那就是使分類面不用向這些點(diǎn)的方向挪動(dòng)，因此可以得到更大的幾何間隔在低維空間看來，分類邊境也更平滑。顯然我們必需權(quán)衡這種損失和益

6、處。益處很明顯，我們得到的分類間隔越大，益處就越多?；叵胛覀?cè)嫉挠查g隔分類對(duì)應(yīng)的優(yōu)化問題：|w|2就是目的函數(shù)當(dāng)然系數(shù)可有可無，希望它越小越好，因此損失就必然是一個(gè)能使之變大的量能使它變小就不叫損失了，我們本來就希望目的函數(shù)值越小越好。那如何來衡量損失， 其中l(wèi)都是樣本的數(shù)目。把損失參與到目的函數(shù)里的時(shí)候，就需求一個(gè)懲罰因子cost，也就是libSVM的諸多參數(shù)中的C，原來的優(yōu)化問題就變成了下面這樣：一是并非一切的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)踐上只需“離群點(diǎn)才有，一切沒離群的點(diǎn)松弛變量都等于0對(duì)負(fù)類來說，離群點(diǎn)就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點(diǎn)，對(duì)正類來說，就是跑到H1左側(cè)的那

7、些正樣本點(diǎn)。 二是松弛變量的值實(shí)踐上標(biāo)示出了對(duì)應(yīng)的點(diǎn)究竟離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。 三是懲罰因子C決議了注重離群點(diǎn)帶來的損失的程度，顯然當(dāng)一切離群點(diǎn)的松弛變量的和一定時(shí)，定的C越大，對(duì)目的函數(shù)的損失也越大，此時(shí)就暗示著不情愿放棄這些離群點(diǎn)，最極端的情況是把C定為無限大，這樣只需稍有一個(gè)點(diǎn)離群，目的函數(shù)的值馬上變成無限大，問題變成無解，這就退化成了硬間隔問題。 四是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問題在解的時(shí)候，C是一個(gè)必需事先指定的值，指定這個(gè)值以后，解一下，得到一個(gè)分類器，然后用測(cè)試數(shù)據(jù)看看結(jié)果怎樣樣，假設(shè)不夠好，換一個(gè)C的值，再解一次優(yōu)化問題，得到另一個(gè)分類器，再看看效果，如此就是一個(gè)

8、參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C不斷是定值。 從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時(shí)看看間隔有多大，又有多少點(diǎn)離群，把目的函數(shù)的值算一算，再換一組三條直線他可以看到，分類的直線位置假設(shè)挪動(dòng)了，有些原來離群的點(diǎn)會(huì)變得不再離群，而有的本來不離群的點(diǎn)會(huì)變成離群點(diǎn)，再把目的函數(shù)的值算一算，如此往復(fù)迭代，直到最終找到目的函數(shù)最小時(shí)的w。 松弛變量也就是處理線性不可分問題的方法，核函數(shù)的引入也是為理處理線性不可分的問題。其實(shí)兩者還有些不同。以文本分類為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞郑瑹o論怎樣找分類平面，總會(huì)

9、有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果依然是不可分的，但比原始空間里的要更加接近線性可分的形狀就是到達(dá)了近似線性可分的形狀，此時(shí)再用松弛變量處置那些少數(shù)“冥頑不化的離群點(diǎn)，更加簡(jiǎn)單有效。 對(duì)比復(fù)雜的推導(dǎo)過程，SVM的思想確實(shí)簡(jiǎn)單。是在樣本中去找分隔線，為了評(píng)判哪條分界限更好，引入了幾何間隔最大化的目的。之后處理目的函數(shù)的最優(yōu)化問題。在處理最優(yōu)化的過程中，發(fā)現(xiàn)了w可以由特征向量?jī)?nèi)積來表示，進(jìn)而發(fā)現(xiàn)了核函數(shù)，僅需求調(diào)整核函數(shù)就可以將特征進(jìn)展低維到高維的變換，在低維上進(jìn)展計(jì)算，本質(zhì)結(jié)果表如今高維上。由于并不是一切的樣本都可分，為了保證SVM的通用性，進(jìn)展了軟間隔的處置，導(dǎo)致的結(jié)果就

10、是將優(yōu)化問題變得更加復(fù)雜，然而驚奇的是松弛變量沒有出如今最后的目的函數(shù)中。最后的優(yōu)化求解問題，也被拉格朗日對(duì)偶和SMO算法化解，使SVM趨向于完美。SVM有如下主要幾個(gè)特點(diǎn)：(1)非線性映射是SVM方法的實(shí)際根底,SVM利用內(nèi)積核函數(shù)替代向高維空間的非線性映射；(2)對(duì)特征空間劃分的最優(yōu)超平面是SVM的目的,最大化分類邊沿的思想是SVM方法的中心；(3)支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決議作用的是支持向量。(4)SVM 是一種有堅(jiān)實(shí)實(shí)際根底的新穎的小樣本學(xué)習(xí)方法。它根本上不涉及概率測(cè)度及大數(shù)定律等,因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看,它避開了從歸納到演繹的傳統(tǒng)過程,實(shí)現(xiàn)了高效

11、的從訓(xùn)練樣本到預(yù)告樣本的“轉(zhuǎn)導(dǎo)推理,大大簡(jiǎn)化了通常的分類和回歸等問題。(5)SVM 的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上防止了“維數(shù)災(zāi)難。(6)少數(shù)支持向量決議了最終結(jié)果,這不但可以協(xié)助 我們抓住關(guān)鍵樣本、“剔除大量冗余樣本,而且注定了該方法不但算法簡(jiǎn)單,而且具有較好的“魯棒性。這種“魯棒性主要表達(dá)在:增、刪非支持向量樣本對(duì)模型沒有影響;支持向量樣本集具有一定的魯棒性;有些勝利的運(yùn)用中,SVM 方法對(duì)核的選取不敏感兩個(gè)缺乏：(1) SVM算法對(duì)大規(guī)模訓(xùn)練樣本難以實(shí)施由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將

12、涉及m階矩陣的計(jì)算m為樣本的個(gè)數(shù)，當(dāng)m數(shù)目很大時(shí)該矩陣的存儲(chǔ)和計(jì)算將耗費(fèi)大量的機(jī)器內(nèi)存和運(yùn)算時(shí)間。針對(duì)以上問題的主要改良有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、張學(xué)工的CSVM以及O.L.Mangasarian等的SOR算法(2) 用SVM處理多分類問題存在困難經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，而在數(shù)據(jù)發(fā)掘的實(shí)踐運(yùn)用中，普通要處理多類的分類問題?？梢越?jīng)過多個(gè)二類支持向量機(jī)的組合來處理。主要有一對(duì)多組合方式、一對(duì)一組合方式和SVM決策樹；再就是經(jīng)過構(gòu)造多個(gè)分類器的組合來處理。主要原理是抑制SVM固有的缺陷，結(jié)合其他算法的優(yōu)勢(shì)，

13、處理多類問題的分類精度。如：與粗集實(shí)際結(jié)合，構(gòu)成一種優(yōu)勢(shì)互補(bǔ)的多類問題的組合分類器。2實(shí)驗(yàn)及分析2.1libsvm自帶例子1用heart_scale測(cè)試調(diào)整c，分類準(zhǔn)確率會(huì)變化，但是，變?yōu)?00%，我以為能夠是測(cè)試數(shù)據(jù)和訓(xùn)練數(shù)據(jù)是一樣的數(shù)據(jù)集引起的。2不同的參數(shù)tt 核函數(shù)類型：核函數(shù)設(shè)置類型(默許2)0 線性：uv1 多項(xiàng)式：(r*uv + coef0)degree2 RBF函數(shù)：exp(-r|u-v|2)3 sigmoid：tanh(r*uv + coef0)不同的核函數(shù)對(duì)分類準(zhǔn)確率的影響。對(duì)于heart_scale不同的核函數(shù)對(duì)分類準(zhǔn)確率的影響不大,rbf 核函數(shù)的性能最好。3調(diào)整c和g

14、以找到最優(yōu)的c和g使分類正確率最高調(diào)整c和g得到c=1和g=0.03125，分類正確率最高。2.2wine數(shù)據(jù)集實(shí)驗(yàn)1測(cè)試wine數(shù)據(jù)標(biāo)簽有三類，各選取一半作為測(cè)試集，一半為訓(xùn)練集。準(zhǔn)確率并不好。 2不同的參數(shù)tt 核函數(shù)類型：核函數(shù)設(shè)置類型(默許2)0 線性：uv1 多項(xiàng)式：(r*uv + coef0)degree2 RBF函數(shù)：exp(-r|u-v|2)3 sigmoid：tanh(r*uv + coef0)不同的核函數(shù)對(duì)分類準(zhǔn)確率的影響。多項(xiàng)式和sigmoid函數(shù)的訓(xùn)練結(jié)果最差。3調(diào)整c和g以找到最優(yōu)的c和g使分類正確率最高。調(diào)整c和g得到c=64和g=0.00097，分類正確率最高。3

15、圖形化3結(jié)論及改良SVM有如下主要幾個(gè)特點(diǎn)： (1)非線性映射是SVM方法的實(shí)際根底,SVM用內(nèi)積核函數(shù)替代向高維空間的非線性映射；(2)對(duì)特征空間劃分的最優(yōu)超平面是SVM的目的,最大化分類間隔是SVM方法的中心； (3)支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決議作用 (4)SVM 是一種有堅(jiān)實(shí)實(shí)際根底的小樣本學(xué)習(xí)方法。它根本上不涉及概率測(cè)度及大數(shù)定律等,因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看,它避開了從歸納到演繹的傳統(tǒng)過程,實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)告樣本的“轉(zhuǎn)導(dǎo)推理,大大簡(jiǎn)化了通常的分類和回歸等問題； (5)SVM 的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量

16、的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上防止了“維數(shù)災(zāi)難。 (6)少數(shù)支持向量決議了最終結(jié)果,這不但可以協(xié)助 我們抓住關(guān)鍵樣本、“剔除大量冗余樣本,而且注定了該方法不但算法簡(jiǎn)單,而且具有較好的“魯棒性。SVM缺乏： (1) 訓(xùn)練好SVM分類器后,得到的支持向量被用來構(gòu)成決策分類面。對(duì)于大規(guī)容貌本集問題,SVM訓(xùn)練得到的支持向量數(shù)目很大,那么進(jìn)展分類決策時(shí)的計(jì)算代價(jià)很大。(2) 用SVM處理多分類問題存在困難，經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，要處理多類的分類問題。可以經(jīng)過多個(gè)二類支持向量機(jī)的組合來處理。要針對(duì)不同的問題選擇不同的核函數(shù)。規(guī)范的SVM對(duì)噪聲是不具有魯棒性的,如何選擇適宜的目的函數(shù)以實(shí)現(xiàn)魯棒性是至關(guān)重要的。要根據(jù)詳細(xì)問題選擇適宜的核函數(shù)及懲罰因子，多次實(shí)驗(yàn)選擇最好的結(jié)果。一個(gè)好的分類器固然重要,但前期的數(shù)據(jù)預(yù)處置亦很重要。當(dāng)數(shù)據(jù)預(yù)處置的好的話,特征提取的好的話,分類器的影響不會(huì)占很大比重。SVM算法參數(shù)選擇能夠是憑仗閱歷、實(shí)驗(yàn)對(duì)比、大范圍的搜索或者利用軟件包提供的交互檢驗(yàn)功能進(jìn)展尋優(yōu)。參考文獻(xiàn)1Chih-Jen Lin Department of Computer Science National Taiwan UniversityA Practical Guide to Support Vector Classification2Chih-