SVM原理與應用課件

原理與應用大綱背景線性分類非線性分類松弛變量多元分類應用工具包2大綱背景線性分類非線性分類松弛變量多元分類應用工具包3背景支持向量機

4為什么要用(個人觀點)分類效果好上手快種語言的個理論基礎完備婦孺皆知的好模型找工作需要它(利益相關：面試狗一只)應用與原理5發(fā)展歷史重要理論基礎年代，和提出維理論重要理論基礎年，提出結構風險最小化理論支持向量機()是和于年首先提出的它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到函數擬合等其他機器學習問題中6作者之一簡介《》作者書中詳細的論證了統(tǒng)計機器學習之所以區(qū)別于傳統(tǒng)機器學習的本質，就在于統(tǒng)計機器學習能夠精確的給出學習效果，能夠解答需要的樣本數等等一系列問題。7理論基礎（比較八股）統(tǒng)計學習理論的維理論(或)是研究有限樣本情況下機器學習規(guī)律的理論()反映了函數集的學習能力，維越大則學習機器越復雜8理論基礎（比較八股）結構風險最小化機器學習本質上就是一種對問題真實模型的逼近。這個與問題真實解之間的誤差，就叫做風險。結構化風險經驗風險置信風險經驗風險

分類器在給定樣本上的誤差置信風險分類器在未知文本上分類的結果的誤差，代表了我們在多大程度上可以信任分類器在未知文本上分類的結果。（無法準確估值，給出估計的區(qū)間）9理論基礎（比較八股）結構化風險經驗風險置信風險置信風險因素：樣本數量，給定的樣本數量越大，學習結果越有可能正確，此時置信風險越小；分類函數的維，顯然維越大，推廣能力越差，置信風險會變大。泛化誤差界的公式*()≤()Ф()公式中()就是真實風險，()就是經驗風險，Ф()就是置信風險。統(tǒng)計學習的目標從經驗風險最小化變?yōu)榱藢で蠼涷烇L險與置信風險的和最小，即結構風險最小。10理論基礎（小結）統(tǒng)計學習理論的維理論關注的是維結構風險最小化()≤()Ф()11特性小樣本與問題的復雜度比起來，算法要求的樣本數是相對比較少的非線性擅長應付樣本數據線性不可分的情況，主要通過松弛變量和核函數技術來實現(xiàn)高維模式識別例如文本的向量表示，幾萬維，反例:12大綱背景線性分類非線性分類松弛變量多元分類應用工具包13線性分類器問題的引入和是兩類樣本中間的直線就是一個分類函數，它可以將兩類樣本完全分開。14線性函數？在一維空間里就是一個點在二維空間里就是一條直線在三維空間里就是一個平面……如果不關注空間的維數，這種線性函數還有一個統(tǒng)一的名稱——超平面()15線性函數分類問題例如我們有一個線性函數()我們可以取閾值為，這樣當有一個樣本需要判別的時候，我們就看()的值。若()>，就判別為類別若()<，則判別為類別、、均可以是向量中間那條直線的表達式是()，即，我們也把這個函數叫做分類面16分類面的決定分離超平面不是唯一上面的直線都可以對點正確分類分離超平面存在一個最好的17分類面的“好壞”量化一個很直觀的感受是，讓“離直線最近的點，距離直線盡可能地遠”就是分割的間隙越大越好，把兩個類別的點分得越開越好18“分類間隔”的引入文本分類分類時樣本格式（標示出這個樣本屬于哪個類別）（文本特征所組成的向量）假設±，我們就可以定義一個樣本點到某個超平面的間隔為(這是定義)δ()19^分類間隔δ()()總大于的，而且它的值等于如果某個樣本屬于該類別的話，>，而也大于反之，<，而也小于現(xiàn)在把和進行一下歸一化，即用和分別代替原來的和，那么間隔就可以寫成20^分類間隔幾何間隔解析幾何中點到直線()的距離公式推廣一下，是到超平面()的距離，()就是上節(jié)中提到的分類超平面是什么符號？叫做向量的范數，向量長度其實指的是它的范數用歸一化的和代替原值之后的間隔有一個專門的名稱，叫做幾何間隔21量化問題之“支持向量”被紅色和藍色的線圈出來的點就是所謂的支持向量()22量化問題之“最大化間隔”原則就是()，紅色和藍色的線（與）就是所在的面，紅色、藍色線之間的間隔就是我們要最大化的分類間的間隔。23量化問題之“最大化間隔”原則幾何間隔24幾何間隔的現(xiàn)實含義是分類面，而和是平行于，且過離最近的兩類樣本的直線，與，與之間的距離就是幾何間隔25幾何間隔的存在意義幾何間隔與樣本的誤分次數間存在關系其中的δ是樣本集合到分類面的間隔，

，即是所有樣本中向量長度最長的值（也就是說代表樣本的分布有多么廣）誤分次數一定程度上代表分類器的誤差。（證明略）誤分次數的上界由幾何間隔決定（樣本已知的時候）26

為了使分類面更合適為了減少誤分次數最大化幾何間隔27

是否讓，目標函數就最小了呢？。式子有還有一些限制條件，完整的寫下來，應該是這樣的求最小值的問題就是一個優(yōu)化問題，一個帶約束的二次規(guī)劃(,)問題，是一個凸問題凸二次規(guī)劃區(qū)別于一般意義上的規(guī)劃問題，它有解而且是全局最優(yōu)的解，而且可以找到28如何解二次規(guī)劃問題等式約束，是求極值、拉格朗日轉化等方法轉化為無約束問題不等式約束的問題怎么辦？方法一：用現(xiàn)成的()優(yōu)化包進行求解(效率低)方法二：求解與原問題等價的對偶問題()得到原始問題的最優(yōu)解(更易求解、可以推廣到核函數)拉格朗日乘子法拉格朗日對偶性理論支撐29求解步驟轉化為對偶問題對偶轉化條件求解極小化拉格朗日乘子極值求解α極大化用算法求解α乘子30、對偶問題的轉化給每一個約束條件加上一個拉格朗日乘子（），定義拉格朗日函數根據對偶算法與條件約束，這個問題可以從轉化為其中*和*等價條件就是條件*31、的極小化那么問題轉化為先固定α，求的最小值將以上結果代入之前的，得到只含α的優(yōu)化結果32、α的極大化優(yōu)化問題接上一步處理結果如果求出了α*，那么和就可以隨之求解最終得出分離超平面和分類決策函數。那么有什么好方法求α呢？33、利用算法求解對偶問題中的拉格朗日乘子α優(yōu)化問題接上一步處理結果上述式子要解決的是在參數α上求最大值的問題，至于都是已知數算法(略)34表達式的感性分析(番外篇)線性函數表達式為()<>樣本確定了，用數學的語言描述，就是可以表示為樣本的某種組合αα…α同時不僅跟樣本點的位置有關，還跟樣本的類別有關（也就是和樣本的“標簽”有關）。因此用下面這個式子表示才算完整：αα…α

35分類函數的預測將的表達式帶入分類函數后對于新點的預測，只需要計算它與訓練數據點的內積即可（表示向量內積）所有非所對應的系數都α是等于零的，因此對于新點的內積計算實際上只要針對少量的“支持向量”而不是所有的訓練數據即可。36大綱背景線性分類非線性分類松弛變量多元分類應用工具包37非線性分類——問題的引入我們把橫軸上端點和之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數把兩類正確分開么？不能，因為二維空間里的線性函數就是指直線，顯然找不到符合條件的直線。38非線性分類——問題的引入顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別39非線性分類——問題的引入這條曲線就是我們熟知的二次曲線，它的函數表達式可以寫為：它不是一個線性函數，但是，我們可以新建一個向量和：這樣()就可以轉化為()<>40非線性分類——問題的引入原先問題是：轉化后的問題：

在任意維度的空間中，這種形式的函數都是一個線性函數原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的。解決線性不可分問題的基本思路——向高維空間轉化(這種特征變換稱作特征映射())，使其變得線性可分。41核函數——例子引入我們文本分類問題的原始空間是維的，在這個維度上問題是線性不可分的?，F(xiàn)在我們有一個維空間里的線性函數式中的’和’都是維的向量，只不過’是定值，而’是變量現(xiàn)在我們的輸入，是一個維的向量，分類的過程是先把變換為維的向量’，然后求這個變換后的向量’與向量’的內積，再把這個內積的值和相加，就得到了結果，看結果大于閾值還是小于閾值就得到了分類結果。42核函數——例子引入我們其實只關心那個高維空間里內積的值，那個值算出來了，分類結果就算出來了。是否能有這樣一種函數(),他接受低維空間的輸入值，卻能算出高維空間的內積值<’’>？如果有這樣的函數，那么當給了一個低維空間的輸入以后：這兩個函數的計算結果就完全一樣，我們也就用不著費力找那個映射關系，直接拿低維的輸入往()里面代就可以了43假設映射函數是我們要將映射為那么定義核函數（）為如果要實現(xiàn)該節(jié)開頭的效果，只需先計算，然后計算即可，然而這種計算方式是非常低效的。比如最初的特征是維的，我們將其映射到^維，然后再計算，這樣需要(^)的時間。那么我們能不能想辦法減少計算時間呢?核函數——形式化定義44核函數這樣的()確實存在。它被稱作核函數()，而且還不止一個事實上，只要是滿足了條件*的函數，都可以作為核函數。核函數的基本作用就是接受兩個低維空間里的向量，能夠計算出經過某個變換后在高維空間里的向量內積值。45核函數——例子假設和都是維的展開后，得我們可以只計算原始特征和內積的平方，時間復雜度是()，就等價與計算映射后特征的內積。也就是說我們不需要花時間(^)了46核函數——例子核函數對應的映射函數（時）是47核函數舉例——高斯核如果和很相近()，那么核函數值為，如果和相差很大()，那么核函數值約等于。由于這個函數類似于高斯分布，因此稱為高斯核函數，也叫做徑向基函數(簡稱)。它能夠把原始特征映射到無窮維。48核函數舉例——高斯核49核函數舉例——核既然高斯核函數能夠比較和的相似度，并映射到到，回想回歸，函數可以，因此還有核函數等等。50核函數舉例——多項式核剛才我們舉的例子是這里多項式核的一個特例（，）。雖然比較麻煩，而且沒有必要，不過這個核所對應的映射實際上是可以寫出來的。51核函數舉例——線性核這實際上就是原始空間中的內積。這個核存在的主要目的是使得“映射后空間中的問題”和“映射前空間中的問題”兩者在形式上統(tǒng)一起來52核函數小結我們會經常遇到線性不可分的樣例，此時，我們的常用做法是把樣例特征映射到高維空間中去如果凡是遇到線性不可分的樣例，一律映射到高維空間，那么這個維度大小是會高到可怕的核函數就隆重登場了，核函數的價值在于它雖然也是講特征進行從低維到高維的轉換，但核函數絕就絕在它事先在低維上進行計算，而將實質上的分類效果表現(xiàn)在了高維上，也就如上文所說的避免了直接在高維空間中的復雜計算53核函數分類效果圖籬笆部署問題54核函數還有什么值得我們注意的既然有很多的核函數，針對具體問題該怎么選擇？對核函數的選擇，現(xiàn)在還缺乏指導原則如果使用核函數向高維空間映射后，問題仍然是線性不可分的，那怎么辦？松弛變量55大綱背景線性分類非線性分類松弛變量多元分類應用工具包56問題的引入現(xiàn)在我們已經把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的57問題的引入圓形和方形的點各有成千上萬個，現(xiàn)在想象我們有另一個樣本點，但是這個樣本的位置是這樣的：58近似線性可分問題就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數點線性不可分）叫做“近似線性可分”的問題。59的處理分析有一萬個點都符合某種規(guī)律（因而線性可分），有一個點不符合，那這一個點是否就代表了分類規(guī)則中我們沒有考慮到的方面呢更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓練集的同學人工分類時一打瞌睡錯放進去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。60硬間隔分類問題由于我們原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點（不能忽略某一個，因為程序它怎么知道該忽略哪一個呢？），在此基礎上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。61如何評價硬間隔分類硬間隔的分類法其結果容易受少數點的控制，這是很危險的解決方法：允許一些點到分類平面的距離不滿足原先的要求62松弛變量的引入意思是說離分類面最近的樣本點函數間隔也要比大。如果要引入容錯性，就給這個硬性的閾值加一個松弛變量，即允許因為松弛變量是非負的，因此最終的結果是要求間隔可以比小63松弛變量值的確定當某些點出現(xiàn)這種間隔比小的情況時（這些點也叫離群點），意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）64松弛變量優(yōu)化問題我們原始的硬間隔分類對應的優(yōu)化問題我們要把松弛變量加入到優(yōu)化問題中，即將損失越小越好65軟間隔分類器如果是，則為二階軟間隔分類器如果是，則為一階軟間隔分類器66懲罰因子懲罰因子把損失加入到目標函數里的時候，就需要一個懲罰因子（，也就是中工具包中的參數）67松弛變量懲罰因子的幾點說明并非所有的樣本點都有一個松弛變量與其對應。實際上只有“離群點”才有，沒離群的點松弛變量都等于松弛變量的值實際上標示出了對應的點到底離群有多遠，值越大，點就越遠懲罰因子決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，你定的越大，對目標函數的損失也越大懲罰因子不是一個變量，整個優(yōu)化問題在解的時候，是一個事先指定的值68核函數松弛變量相同點：都是解決線性不可分問題的不同點：在原始的低維空間中，樣本相當的不可分，無論你怎么找分類平面，總會有大量的離群點，此時用核函數向高維空間映射一下，雖然結果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)達到了近似線性可分的狀態(tài)后，此時再用松弛變量處理那些少數“冥頑不化”的離群點69的運用：數據集偏斜()它指的是參與分類的兩個類別（也可以指多個類別）樣本數量差異很大。比如說正類有個樣本，而負類只給了個70數據集偏斜()方形的點是負類。，，是根據給的樣本算出來的分類面兩個灰色點有提供的話，那算出來的分類面應該是’，’和負類給的樣本點越多，就越容易出現(xiàn)在灰色點附近的點，我們算出的結果也就越接近于真實的分類面。71問題的解決方法()懲罰因子，那就是給樣本數量少的負類更大的懲罰因子，表示我們重視這部分樣本72問題的解決方法()不一定是樣本少，還可能是分布不夠廣“政治類”“體育類”文本分類，體育類集中在“籃球”領域比如可以算算他們在空間中占據了多大的體積，例如給負類找一個超球，它可以包含所有負類的樣本，再給正類找一個，比比兩個球的半徑，就可以大致確定分布的情況但是有些領域分布的確不夠廣，比如“高考作文”“語言類”73問題的解決方法簡單的就是美的在解決偏斜問題的時候用的是方案一，樣本數量的比的初始值根據參數調優(yōu)計算出來咱們先假定說是這么大，就可以定為這么大（：：）74大綱背景線性分類非線性分類松弛變量多元分類應用工具包75多元分類是一種典型的兩類分類器，即它只回答屬于正類還是負類的問題而現(xiàn)實中要解決的問題，往往是多類的問題如何由兩類分類器得到多類分類器，就是一個值得研究的問題76方案一：一次求解個分類面一次性考慮所有樣本，并求解一個多目標函數的優(yōu)化問題，一次性得到多個分類面可惜這種算法還基本停留在紙面上，因為一次性求解的方法計算量實在太大，大到無法實用的地步77方案二：一類對其余一類對余類法(，)構造類別數個的二元分類器訓練時第個分類機取訓練集中第類為正類，其余類別點為負類判別時，輸入信號分別經過個分類器輸出優(yōu)點每個優(yōu)化問題的規(guī)模比較小，而且分類的時候速度很快缺點分類重疊不可分類人為的數據偏斜78方案三：一對一該方法在每兩類問訓練一個分類器，因此對于一個類問題，將有()個分類器優(yōu)點避免了數據偏斜訓練階段（也就是算出這些分類器的分類平面時）所用的總時間卻比“”方法少很多投票時也會有分類重疊的現(xiàn)象，但不會有不可分類現(xiàn)象缺點類別數為的時候，我們調用了個分類器，類別數如果是，要調用的分類器數目會上升至約個（但是時間上可能還是比少，因為考慮的樣本數少）79方案四：方法(有向無環(huán)圖)是針對存在誤分現(xiàn)象提出的這種方法的()個分類器，構成一個有向無環(huán)圖。該有向無環(huán)圖中含有()個內部節(jié)點和個葉結點，每個節(jié)點對應一個二類分類器80方案四：方法(有向無環(huán)圖)優(yōu)點簡單易行，只需要使用個決策函數即可得出結果，較“一對一"方法提高了測試速度，而且不存在誤分、拒分區(qū)域由于其特殊的結構，故有一定的容錯性，分類精度較一般的二叉樹方法高缺點誤差積累81方案四：方法(有向無環(huán)圖)的錯誤累積錯誤累積在一對其余和一對一方法中也都存在，方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論證明而一對其余和一對一方法中，盡管每一個兩類分類器的泛化誤差限是知道的，但是合起來做多類分類的時候，誤差上界是多少方法根節(jié)點的選取我們就總取在兩類分類中正確率最高的那個分類器作根節(jié)點置信度最大的路徑82其他方案：決策樹、決策樹方法糾錯輸出編碼法()*維編碼矩陣類別判定用漢明距離83大綱背景線性分類非線性分類松弛變量多元分類應用工具包84的應用文本分類(下頁詳談)圖像處理圖像過濾、圖片分類與檢索生物信息技術蛋白質分類語音識別人臉檢測、指紋識別手寫字體識別網絡入侵檢測、口令認證、網頁分類……85的文本分類應用例:分類萬條微信數據，個類別。條測試數據，其余數據為訓練數據。分類句微博，個類別。句測試數據，其余數據訓練。省略恢復“小明買了蘋果，很甜。”86大綱背景線性分類非線性分類松弛變量多元分類應用工具包87工具包

……88簡介是林智仁()教授開發(fā)可以很方便的對數據做分類或回歸程序小，運用靈活，輸入參數少，并且是開源的，易于擴展，因此成為目前國內應用最多的的庫(,)

89工具包工具包組成(一個可視化的工具,用來展示訓練數據和分類界面,里面是源碼,其編譯后的程序在文件夾下)(四個文件,用來數據集抽樣(),參數優(yōu)選(),集成測試(),數據檢查())(包含四個程序包)其他源碼