SVM原理與應(yīng)用培訓(xùn)

SVM原理與應(yīng)用HITSCIR-TMGroupzkli-李澤魁大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包2大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包3SVM背景支持向量機(jī)supportvectormachineSVM4為什么要用SVM(個(gè)人觀點(diǎn))分類(lèi)效果好上手快N種語(yǔ)言的N個(gè)Toolkit理論基礎(chǔ)完備婦孺皆知的好模型找工作需要它(利益相關(guān)：面試狗一只)應(yīng)用與原理5SVM發(fā)展歷史重要理論基礎(chǔ)160年代，Vapnik和Chervonenkis提出VC維理論重要理論基礎(chǔ)21982年，Vapnik提出結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論支持向量機(jī)(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中6作者之一簡(jiǎn)介Vapnik《StatisticalLearningTheory》作者書(shū)中詳細(xì)的論證了統(tǒng)計(jì)機(jī)器學(xué)習(xí)之所以區(qū)別于傳統(tǒng)機(jī)器學(xué)習(xí)的本質(zhì)，就在于統(tǒng)計(jì)機(jī)器學(xué)習(xí)能夠精確的給出學(xué)習(xí)效果，能夠解答需要的樣本數(shù)等等一系列問(wèn)題。7SVM理論基礎(chǔ)1（比較八股）統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論(StatisticalLearningTheory或SLT)是研究有限樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論(Vapnik-ChervonenkisDimension)

反映了函數(shù)集的學(xué)習(xí)能力，VC維越大則學(xué)習(xí)機(jī)器越復(fù)雜8SVM理論基礎(chǔ)2（比較八股）結(jié)構(gòu)風(fēng)險(xiǎn)最小化機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近。這個(gè)與問(wèn)題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)。結(jié)構(gòu)化風(fēng)險(xiǎn)=經(jīng)驗(yàn)風(fēng)險(xiǎn)+置信風(fēng)險(xiǎn)經(jīng)驗(yàn)風(fēng)險(xiǎn)=

分類(lèi)器在給定樣本上的誤差置信風(fēng)險(xiǎn)=分類(lèi)器在未知文本上分類(lèi)的結(jié)果的誤差，代表了我們?cè)诙啻蟪潭壬峡梢孕湃畏诸?lèi)器在未知文本上分類(lèi)的結(jié)果。（無(wú)法準(zhǔn)確估值，給出估計(jì)的區(qū)間）9SVM理論基礎(chǔ)2（比較八股）結(jié)構(gòu)化風(fēng)險(xiǎn)=經(jīng)驗(yàn)風(fēng)險(xiǎn)+置信風(fēng)險(xiǎn)置信風(fēng)險(xiǎn)因素：樣本數(shù)量，給定的樣本數(shù)量越大，學(xué)習(xí)結(jié)果越有可能正確，此時(shí)置信風(fēng)險(xiǎn)越??；分類(lèi)函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險(xiǎn)會(huì)變大。泛化誤差界的公式*R(w)≤Remp(w)+Ф(n/h)公式中R(w)就是真實(shí)風(fēng)險(xiǎn)，Remp(w)就是經(jīng)驗(yàn)風(fēng)險(xiǎn)，Ф(n/h)就是置信風(fēng)險(xiǎn)。統(tǒng)計(jì)學(xué)習(xí)的目標(biāo)從經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化變?yōu)榱藢で蠼?jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的和最小，即結(jié)構(gòu)風(fēng)險(xiǎn)最小。10SVM理論基礎(chǔ)（小結(jié)）統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論SVM關(guān)注的是VC維結(jié)構(gòu)風(fēng)險(xiǎn)最小化R(w)≤Remp(w)+Ф(n/h)11SVM特性小樣本與問(wèn)題的復(fù)雜度比起來(lái)，SVM算法要求的樣本數(shù)是相對(duì)比較少的非線性SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過(guò)松弛變量和核函數(shù)技術(shù)來(lái)實(shí)現(xiàn)高維模式識(shí)別例如文本的向量表示，幾萬(wàn)維，反例:KNN12大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包13線性分類(lèi)器問(wèn)題的引入X和O是兩類(lèi)樣本中間的直線就是一個(gè)分類(lèi)函數(shù)，它可以將兩類(lèi)樣本完全分開(kāi)。14線性函數(shù)？在一維空間里就是一個(gè)點(diǎn)在二維空間里就是一條直線在三維空間里就是一個(gè)平面……如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱(chēng)——超平面(HyperPlane)15線性函數(shù)

分類(lèi)問(wèn)題例如我們有一個(gè)線性函數(shù)g(x)=wx+b我們可以取閾值為0，這樣當(dāng)有一個(gè)樣本xi需要判別的時(shí)候，我們就看g(xi)的值。若g(xi)>0，就判別為類(lèi)別O若g(xi)<0，則判別為類(lèi)別XTipsw、x、b均可以是向量中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個(gè)函數(shù)叫做分類(lèi)面16分類(lèi)面的決定分離超平面不是唯一上面的N直線都可以對(duì)點(diǎn)正確分類(lèi)分離超平面存在一個(gè)最好的17分類(lèi)面的“好壞”量化一個(gè)很直觀的感受是，讓“離直線最近的點(diǎn)，距離直線盡可能地遠(yuǎn)”就是分割的間隙越大越好，把兩個(gè)類(lèi)別的點(diǎn)分得越開(kāi)越好18“分類(lèi)間隔”的引入文本分類(lèi)分類(lèi)時(shí)樣本格式label（標(biāo)示出這個(gè)樣本屬于哪個(gè)類(lèi)別）feature（文本特征所組成的向量）假設(shè)label=±1，我們就可以定義一個(gè)樣本點(diǎn)到某個(gè)超平面的間隔為(這是定義)δi=yi(wxi+b)19^分類(lèi)間隔δi=yi(wxi+b)yi(wxi+b)總大于0的，而且它的值等于|wxi+b|如果某個(gè)樣本屬于該類(lèi)別的話，wxi+b>0，而yi也大于0反之，wxi+b<0，而yi也小于0現(xiàn)在把w和b進(jìn)行一下歸一化，即用w/||w||和b/||w||分別代替原來(lái)的w和b，那么間隔就可以寫(xiě)成20^分類(lèi)間隔

幾何間隔解析幾何中點(diǎn)xi到直線g(x)=0的距離公式推廣一下，是到超平面g(x)=0的距離，g(x)=0就是上節(jié)中提到的分類(lèi)超平面||w||是什么符號(hào)？||w||叫做向量w的范數(shù)，向量長(zhǎng)度其實(shí)指的是它的2-范數(shù)用歸一化的w和b代替原值之后的間隔有一個(gè)專(zhuān)門(mén)的名稱(chēng)，叫做幾何間隔21量化問(wèn)題之“支持向量”被紅色和藍(lán)色的線圈出來(lái)的點(diǎn)就是所謂的支持向量(supportvector)22量化問(wèn)題之“最大化間隔”MaximumMarginal原則ClassifierBoundary就是f(x)，紅色和藍(lán)色的線（plusplane與minusplane）就是supportvector所在的面，紅色、藍(lán)色線之間的間隔就是我們要最大化的分類(lèi)間的間隔。23量化問(wèn)題之“最大化間隔”MaximumMargin原則幾何間隔24幾何間隔的現(xiàn)實(shí)含義H是分類(lèi)面，而H1和H2是平行于H，且過(guò)離H最近的兩類(lèi)樣本的直線，H1與H，H2與H之間的距離就是幾何間隔25幾何間隔的存在意義幾何間隔與樣本的誤分次數(shù)間存在關(guān)系其中的δ是樣本集合到分類(lèi)面的間隔，R=max||xi||

i=1,...,n，即R是所有樣本中向量長(zhǎng)度最長(zhǎng)的值（也就是說(shuō)代表樣本的分布有多么廣）誤分次數(shù)一定程度上代表分類(lèi)器的誤差。（證明略）誤分次數(shù)的上界由幾何間隔決定（樣本已知的時(shí)候）26MaximumMargin為了使分類(lèi)面更合適為了減少誤分次數(shù)最大化幾何間隔27minimize||w||是否讓W(xué)=0，目標(biāo)函數(shù)就最小了呢？=。=式子有還有一些限制條件，完整的寫(xiě)下來(lái)，應(yīng)該是這樣的求最小值的問(wèn)題就是一個(gè)優(yōu)化問(wèn)題，一個(gè)帶約束的二次規(guī)劃(quadraticprogramming,QP)問(wèn)題，是一個(gè)凸問(wèn)題凸二次規(guī)劃區(qū)別于一般意義上的規(guī)劃問(wèn)題，它有解而且是全局最優(yōu)的解，而且可以找到28如何解二次規(guī)劃問(wèn)題等式約束，是求極值、拉格朗日轉(zhuǎn)化等方法轉(zhuǎn)化為無(wú)約束問(wèn)題不等式約束的問(wèn)題怎么辦？方法一：用現(xiàn)成的QP(QuadraticProgramming)優(yōu)化包進(jìn)行求解(效率低)方法二：求解與原問(wèn)題等價(jià)的對(duì)偶問(wèn)題(dualproblem)得到原始問(wèn)題的最優(yōu)解(更易求解、可以推廣到核函數(shù))拉格朗日乘子法拉格朗日對(duì)偶性KKT理論支撐29求解步驟轉(zhuǎn)化為對(duì)偶問(wèn)題對(duì)偶轉(zhuǎn)化&KKT條件求解wb極小化拉格朗日乘子極值求解α極大化用SMO算法求解α乘子301、對(duì)偶問(wèn)題的轉(zhuǎn)化給每一個(gè)約束條件加上一個(gè)拉格朗日乘子（Lagrangemultiplier），定義拉格朗日函數(shù)根據(jù)對(duì)偶算法與KKT條件約束，這個(gè)問(wèn)題可以從轉(zhuǎn)化為其中p*和d*等價(jià)條件就是KKT條件*312、wb的極小化那么問(wèn)題轉(zhuǎn)化為先固定α，求wb的最小值將以上結(jié)果代入之前的L，得到只含α的優(yōu)化結(jié)果323、α的極大化優(yōu)化問(wèn)題接上一步處理結(jié)果如果求出了α*，那么w和b就可以隨之求解最終得出分離超平面和分類(lèi)決策函數(shù)。那么有什么好方法求α呢？333、利用SMO算法求解對(duì)偶問(wèn)題中的拉格朗日乘子α優(yōu)化問(wèn)題接上一步處理結(jié)果上述式子要解決的是在參數(shù)αi上求最大值的問(wèn)題，至于xy都是已知數(shù)SMO算法(略)34

表達(dá)式的感性分析(番外篇)線性函數(shù)表達(dá)式為g(x)=<w,x>+b樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合w=α1x1+α2x2+…+αnxn同時(shí)w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類(lèi)別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。因此用下面這個(gè)式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

35分類(lèi)函數(shù)的預(yù)測(cè)將w的表達(dá)式帶入分類(lèi)函數(shù)后對(duì)于新點(diǎn)x的預(yù)測(cè)，只需要計(jì)算它與訓(xùn)練數(shù)據(jù)點(diǎn)的內(nèi)積即可（表示向量?jī)?nèi)積）所有非SupportingVector所對(duì)應(yīng)的系數(shù)都αi是等于零的，因此對(duì)于新點(diǎn)的內(nèi)積計(jì)算實(shí)際上只要針對(duì)少量的“支持向量”而不是所有的訓(xùn)練數(shù)據(jù)即可。36大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包37非線性分類(lèi)——問(wèn)題的引入我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類(lèi)，兩邊的黑色部分里的點(diǎn)定為負(fù)類(lèi)。試問(wèn)能找到一個(gè)線性函數(shù)把兩類(lèi)正確分開(kāi)么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。38非線性分類(lèi)——問(wèn)題的引入顯然通過(guò)點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類(lèi)別39非線性分類(lèi)——問(wèn)題的引入這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫(xiě)為：它不是一個(gè)線性函數(shù)，但是，我們可以新建一個(gè)向量y和a：這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>40非線性分類(lèi)——問(wèn)題的引入原先問(wèn)題是：轉(zhuǎn)化后的問(wèn)題：

在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)原來(lái)在二維空間中一個(gè)線性不可分的問(wèn)題，映射到四維空間后，變成了線性可分的。解決線性不可分問(wèn)題的基本思路——向高維空間轉(zhuǎn)化(這種特征變換稱(chēng)作特征映射(featuremapping))，使其變得線性可分。41核函數(shù)——例子引入我們文本分類(lèi)問(wèn)題的原始空間是1000維的，在這個(gè)維度上問(wèn)題是線性不可分的。現(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)式中的w’和x’都是2000維的向量，只不過(guò)w’是定值，而x’是變量現(xiàn)在我們的輸入，是一個(gè)1000維的向量x，分類(lèi)的過(guò)程是先把x變換為2000維的向量x’，然后求這個(gè)變換后的向量x’與向量w’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類(lèi)結(jié)果。42核函數(shù)——例子引入我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來(lái)了，分類(lèi)結(jié)果就算出來(lái)了。是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>？如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后：這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了43假設(shè)映射函數(shù)是我們要將映射為那么定義核函數(shù)（Kernel）為如果要實(shí)現(xiàn)該節(jié)開(kāi)頭的效果，只需先計(jì)算，然后計(jì)算

即可，然而這種計(jì)算方式是非常低效的。比如最初的特征是n維的，我們將其映射到n^2維，然后再計(jì)算，這樣需要O(n^2)的時(shí)間。那么我們能不能想辦法減少計(jì)算時(shí)間呢?核函數(shù)——形式化定義44核函數(shù)這樣的K(w,x)確實(shí)存在。它被稱(chēng)作核函數(shù)(kernel)，而且還不止一個(gè)事實(shí)上，只要是滿足了Mercer條件*的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過(guò)某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。45核函數(shù)——例子1假設(shè)x和z都是n維的展開(kāi)后，得我們可以只計(jì)算原始特征x和z內(nèi)積的平方，時(shí)間復(fù)雜度是O(n)，就等價(jià)與計(jì)算映射后特征的內(nèi)積。也就是說(shuō)我們不需要花時(shí)間O(n^2)了46核函數(shù)——例子2核函數(shù)對(duì)應(yīng)的映射函數(shù)（n=3時(shí)）是47核函數(shù)舉例1——高斯核如果x和z很相近(

)，那么核函數(shù)值為1，如果x和z相差很大()，那么核函數(shù)值約等于0。由于這個(gè)函數(shù)類(lèi)似于高斯分布，因此稱(chēng)為高斯核函數(shù)，也叫做徑向基函數(shù)(RadialBasisFunction簡(jiǎn)稱(chēng)RBF)。它能夠把原始特征映射到無(wú)窮維。48核函數(shù)舉例1——高斯核49核函數(shù)舉例2——sigmoid核既然高斯核函數(shù)能夠比較x和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。50核函數(shù)舉例3——多項(xiàng)式核剛才我們舉的例子是這里多項(xiàng)式核的一個(gè)特例（R=0，d=2）。雖然比較麻煩，而且沒(méi)有必要，不過(guò)這個(gè)核所對(duì)應(yīng)的映射實(shí)際上是可以寫(xiě)出來(lái)的。51核函數(shù)舉例4——線性核這實(shí)際上就是原始空間中的內(nèi)積。這個(gè)核存在的主要目的是使得“映射后空間中的問(wèn)題”和“映射前空間中的問(wèn)題”兩者在形式上統(tǒng)一起來(lái)52核函數(shù)小結(jié)我們會(huì)經(jīng)常遇到線性不可分的樣例，此時(shí)，我們的常用做法是把樣例特征映射到高維空間中去如果凡是遇到線性不可分的樣例，一律映射到高維空間，那么這個(gè)維度大小是會(huì)高到可怕的核函數(shù)就隆重登場(chǎng)了，核函數(shù)的價(jià)值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)絕就絕在它事先在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類(lèi)效果表現(xiàn)在了高維上，也就如上文所說(shuō)的避免了直接在高維空間中的復(fù)雜計(jì)算53核函數(shù)分類(lèi)效果圖籬笆部署問(wèn)題54核函數(shù)還有什么值得我們注意的既然有很多的核函數(shù)，針對(duì)具體問(wèn)題該怎么選擇？對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則如果使用核函數(shù)向高維空間映射后，問(wèn)題仍然是線性不可分的，那怎么辦？松弛變量55大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包56問(wèn)題的引入現(xiàn)在我們已經(jīng)把一個(gè)本來(lái)線性不可分的文本分類(lèi)問(wèn)題，通過(guò)映射到高維空間而變成了線性可分的57問(wèn)題的引入圓形和方形的點(diǎn)各有成千上萬(wàn)個(gè)，現(xiàn)在想象我們有另一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的：58近似線性可分問(wèn)題就是圖中黃色那個(gè)點(diǎn)，它是方形的，因而它是負(fù)類(lèi)的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使得原本線性可分的問(wèn)題變成了線性不可分的。這樣類(lèi)似的問(wèn)題（僅有少數(shù)點(diǎn)線性不可分）叫做“近似線性可分”的問(wèn)題。59Outlier的處理分析有一萬(wàn)個(gè)點(diǎn)都符合某種規(guī)律（因而線性可分），有一個(gè)點(diǎn)不符合，那這一個(gè)點(diǎn)是否就代表了分類(lèi)規(guī)則中我們沒(méi)有考慮到的方面呢更有可能的是，這個(gè)樣本點(diǎn)壓根就是錯(cuò)誤，是噪聲，是提供訓(xùn)練集的同學(xué)人工分類(lèi)時(shí)一打瞌睡錯(cuò)放進(jìn)去的。所以我們會(huì)簡(jiǎn)單的忽略這個(gè)樣本點(diǎn)，仍然使用原來(lái)的分類(lèi)器，其效果絲毫不受影響。60硬間隔分類(lèi)問(wèn)題由于我們?cè)镜膬?yōu)化問(wèn)題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)（不能忽略某一個(gè)，因?yàn)槌绦蛩趺粗涝摵雎阅囊粋€(gè)呢？），在此基礎(chǔ)上尋找正負(fù)類(lèi)之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問(wèn)題無(wú)解。這種解法其實(shí)也叫做“硬間隔”分類(lèi)法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類(lèi)平面間的距離必須大于某個(gè)值。61如何評(píng)價(jià)硬間隔分類(lèi)硬間隔的分類(lèi)法其結(jié)果容易受少數(shù)點(diǎn)的控制，這是很危險(xiǎn)的解決方法：允許一些點(diǎn)到分類(lèi)平面的距離不滿足原先的要求62松弛變量的引入意思是說(shuō)離分類(lèi)面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯(cuò)性，就給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小63松弛變量值的確定當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)（這些點(diǎn)也叫離群點(diǎn)），意味著我們放棄了對(duì)這些點(diǎn)的精確分類(lèi)，而這對(duì)我們的分類(lèi)器來(lái)說(shuō)是種損失但是放棄這些點(diǎn)也帶來(lái)了好處，那就是使分類(lèi)面不必向這些點(diǎn)的方向移動(dòng)，因而可以得到更大的幾何間隔（在低維空間看來(lái)，分類(lèi)邊界也更平滑）64松弛變量vs優(yōu)化問(wèn)題我們?cè)嫉挠查g隔分類(lèi)對(duì)應(yīng)的優(yōu)化問(wèn)題我們要把松弛變量加入到優(yōu)化問(wèn)題中，即將損失越小越好65軟間隔分類(lèi)器如果是，則為二階軟間隔分類(lèi)器如果是，則為一階軟間隔分類(lèi)器66懲罰因子C懲罰因子C把損失加入到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子（cost，也就是N中工具包中的參數(shù)C）67松弛變量&懲罰因子的幾點(diǎn)說(shuō)明并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)際上只有“離群點(diǎn)”才有，沒(méi)離群的點(diǎn)松弛變量都等于0松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)懲罰因子C決定了你有多重視離群點(diǎn)帶來(lái)的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時(shí)，你定的C越大，對(duì)目標(biāo)函數(shù)的損失也越大懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問(wèn)題在解的時(shí)候，C是一個(gè)事先指定的值68核函數(shù)vs松弛變量相同點(diǎn)：都是解決線性不可分問(wèn)題的不同點(diǎn)：在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞?，無(wú)論你怎么找分類(lèi)平面，總會(huì)有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)達(dá)到了近似線性可分的狀態(tài)后，此時(shí)再用松弛變量處理那些少數(shù)“冥頑不化”的離群點(diǎn)69C的運(yùn)用：數(shù)據(jù)集偏斜(unbalanced)它指的是參與分類(lèi)的兩個(gè)類(lèi)別（也可以指多個(gè)類(lèi)別）樣本數(shù)量差異很大。比如說(shuō)正類(lèi)有10000個(gè)樣本，而負(fù)類(lèi)只給了100個(gè)70數(shù)據(jù)集偏斜(unbalanced)方形的點(diǎn)是負(fù)類(lèi)。H，H1，H2是根據(jù)給的樣本算出來(lái)的分類(lèi)面兩個(gè)灰色點(diǎn)有提供的話，那算出來(lái)的分類(lèi)面應(yīng)該是H’，H2’和H1負(fù)類(lèi)給的樣本點(diǎn)越多，就越容易出現(xiàn)在灰色點(diǎn)附近的點(diǎn)，我們算出的結(jié)果也就越接近于真實(shí)的分類(lèi)面。71unbalanced問(wèn)題的解決方法(1)懲罰因子，那就是給樣本數(shù)量少的負(fù)類(lèi)更大的懲罰因子，表示我們重視這部分樣本72unbalanced問(wèn)題的解決方法(2)不一定是樣本少，還可能是分布不夠廣“政治類(lèi)”vs“體育類(lèi)”文本分類(lèi)，體育類(lèi)集中在“籃球”領(lǐng)域比如可以算算他們?cè)诳臻g中占據(jù)了多大的體積，例如給負(fù)類(lèi)找一個(gè)超球，它可以包含所有負(fù)類(lèi)的樣本，再給正類(lèi)找一個(gè)，比比兩個(gè)球的半徑，就可以大致確定分布的情況但是有些領(lǐng)域分布的確不夠廣，比如“高考作文”vs“C語(yǔ)言類(lèi)”73unbalanced問(wèn)題的解決方法簡(jiǎn)單的就是美的Libsvm在解決偏斜問(wèn)題的時(shí)候用的是方案一，樣本數(shù)量的比C的初始值根據(jù)參數(shù)調(diào)優(yōu)計(jì)算出來(lái)咱們先假定說(shuō)C+是5這么大，C-就可以定為500這么大（10000：100=100：1）74大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包75多元分類(lèi)SVM是一種典型的兩類(lèi)分類(lèi)器，即它只回答屬于正類(lèi)還是負(fù)類(lèi)的問(wèn)題而現(xiàn)實(shí)中要解決的問(wèn)題，往往是多類(lèi)的問(wèn)題如何由兩類(lèi)分類(lèi)器得到多類(lèi)分類(lèi)器，就是一個(gè)值得研究的問(wèn)題76方案一：一次求解N個(gè)分類(lèi)面一次性考慮所有樣本，并求解一個(gè)多目標(biāo)函數(shù)的優(yōu)化問(wèn)題，一次性得到多個(gè)分類(lèi)面可惜這種算法還基本停留在紙面上，因?yàn)橐淮涡郧蠼獾姆椒ㄓ?jì)算量實(shí)在太大，大到無(wú)法實(shí)用的地步77方案二：一類(lèi)對(duì)其余一類(lèi)對(duì)余類(lèi)法(Oneversusrest，OVR)構(gòu)造類(lèi)別數(shù)k個(gè)的二元分類(lèi)器訓(xùn)練時(shí)第i個(gè)分類(lèi)機(jī)取訓(xùn)練集中第i類(lèi)為正類(lèi)，其余類(lèi)別點(diǎn)為負(fù)類(lèi)判別時(shí)，輸入信號(hào)分別經(jīng)過(guò)k個(gè)分類(lèi)器輸出優(yōu)點(diǎn)每個(gè)優(yōu)化問(wèn)題的規(guī)模比較小，而且分類(lèi)的時(shí)候速度很快缺點(diǎn)分類(lèi)重疊&不可分類(lèi)&人為的數(shù)據(jù)偏斜78方案三：一對(duì)一該方法在每?jī)深?lèi)問(wèn)訓(xùn)練一個(gè)分類(lèi)器，因此對(duì)于一個(gè)k類(lèi)問(wèn)題，將有k(k-1)/2個(gè)分類(lèi)器優(yōu)點(diǎn)避免了數(shù)據(jù)偏斜訓(xùn)練階段（也就是算出這些分類(lèi)器的分類(lèi)平面時(shí)）所用的總時(shí)間卻比“OVR”方法少很多投票時(shí)也會(huì)有分類(lèi)重疊的現(xiàn)象，但不會(huì)有不可分類(lèi)現(xiàn)象缺點(diǎn)類(lèi)別數(shù)為5的時(shí)候，我們調(diào)用了10個(gè)分類(lèi)器，類(lèi)別數(shù)如果是1000，要調(diào)用的分類(lèi)器數(shù)目會(huì)上升至約500,000個(gè)（但是時(shí)間上可能OVO還是比OVR少，因?yàn)榭紤]的樣本數(shù)少）79方案四：DAG方法(有向無(wú)環(huán)圖)DAG-SVMs是針對(duì)OVO存在誤分現(xiàn)象提出的這種方法的k(k-1)/2個(gè)分類(lèi)器，構(gòu)成一個(gè)有向無(wú)環(huán)圖。該有向無(wú)環(huán)圖中含有k(k-1)/2個(gè)內(nèi)部節(jié)點(diǎn)和k個(gè)葉結(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)二類(lèi)分類(lèi)器80方案四：DAG方法(有向無(wú)環(huán)圖)優(yōu)點(diǎn)簡(jiǎn)單易行，只需要使用k-1個(gè)決策函數(shù)即可得出結(jié)果，較“一對(duì)一"方法提高了測(cè)試速度，而且不存在誤分、拒分區(qū)域由于其特殊的結(jié)構(gòu)，故有一定的容錯(cuò)性，分類(lèi)精度較一般的二叉樹(shù)方法高缺點(diǎn)誤差積累81方案四：DAG方法(有向無(wú)環(huán)圖)DAG的錯(cuò)誤累積錯(cuò)誤累積在一對(duì)其余和一對(duì)一方法中也都存在，DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論證明而一對(duì)其余和一對(duì)一方法中，盡管每一個(gè)兩類(lèi)分類(lèi)器的泛化誤差限是知道的，但是合起來(lái)做多類(lèi)分類(lèi)的時(shí)候，誤差上界是多少DAG方法根節(jié)點(diǎn)的選取我們就總?cè)≡趦深?lèi)分類(lèi)中正確率最高的那個(gè)分類(lèi)器作根節(jié)點(diǎn)置信度最大的路徑82其他方案：決策樹(shù)、ECOC決策樹(shù)方法糾錯(cuò)輸出編碼法(ECOC)K*L維編碼矩陣類(lèi)別判定用漢明距離83大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包84SVM的應(yīng)用文本分類(lèi)(下頁(yè)詳談)圖像處理圖像過(guò)濾、圖片分類(lèi)與檢索生物信息技術(shù)蛋白質(zhì)分類(lèi)語(yǔ)音識(shí)別人臉檢測(cè)、指紋識(shí)別手寫(xiě)字體識(shí)別網(wǎng)絡(luò)入侵檢測(cè)、口令認(rèn)證、網(wǎng)頁(yè)分類(lèi)……85SVM的文本分類(lèi)應(yīng)用例:Topic分類(lèi)14萬(wàn)條微信數(shù)據(jù)，33個(gè)類(lèi)別。3000條測(cè)試數(shù)據(jù)，其余數(shù)據(jù)為訓(xùn)練數(shù)據(jù)。Emotion分類(lèi)8000句微博，3個(gè)類(lèi)別。2000句測(cè)試數(shù)據(jù)，其余數(shù)據(jù)訓(xùn)練。省略恢復(fù)“小明買(mǎi)了蘋(píng)果，很甜?！?6大綱背景線性分類(lèi)非線性分類(lèi)松弛變量多元分類(lèi)應(yīng)用工具包87SVM工具包LibsvmLiblinear

Svm_perfLibShortText……88Libsvm簡(jiǎn)介L(zhǎng)ibSVM是林智仁(Chih-JenLin)教授開(kāi)發(fā)可以很方便的對(duì)數(shù)據(jù)做分類(lèi)或回歸程序小，運(yùn)用靈活，輸入?yún)?shù)少，并且是開(kāi)源的，易于擴(kuò)展，因此成為目前國(guó)內(nèi)應(yīng)用最多的SVM的庫(kù)Thecurrentrelease(Version3.20,November2014)

89Libsvm工具包工具包組成JavaMatlabPythonsvm-toy(一個(gè)可視化的工具,用來(lái)展示訓(xùn)練數(shù)據(jù)和分類(lèi)界面,里面是源碼,其編譯后的程序在windows文件夾下)Tools(四個(gè)python文件,用來(lái)數(shù)據(jù)集抽樣(subset),參數(shù)優(yōu)選(grid),集成測(cè)試(easy),數(shù)據(jù)檢查(checkdata))Windows(包含libSVM四個(gè)exe程序包)其他.c.h源碼90Libsvm工具包常用命令Svmtrain

svmtrain[options]training_set_file[model_file]Svmpredictsvmpredict[options]test_filemodel_fileoutput_fileSvmscalesvmscale[options]filename91Libsvm模型文件X.model92Libsvm源碼數(shù)據(jù)結(jié)構(gòu)舉例SVMnodeSVMmodel93Libsvm源碼數(shù)據(jù)結(jié)構(gòu)舉例SVMproblemsvm_train調(diào)用的svm_group_class94LiblinearLiblinear線性分類(lèi)器主要為大規(guī)模數(shù)據(jù)的線性模型設(shè)計(jì)由于采用線性核,所以不需要計(jì)算kernelvalue,速度更快缺點(diǎn)就是太吃?xún)?nèi)存了。10G的數(shù)據(jù)量需要接近50G的內(nèi)存，數(shù)據(jù)量再大就沒(méi)法做了

95什么時(shí)候用Liblinear當(dāng)你面對(duì)海量的數(shù)據(jù)時(shí)，這里的海量通常是百萬(wàn)級(jí)別以上海量數(shù)據(jù)分為兩個(gè)層次：樣本數(shù)量和特征的數(shù)量。使用線性和非線性映射訓(xùn)練模型得到相近的效果對(duì)模型訓(xùn)練的時(shí)間效率要