1、線性不可分SVM王成（副教授）計算機科學與技術學院1.廣義線性判別函數x1x2 對圖示的兩類分布，可以用一個4次多項式決策函數對其分類。這是一個兩維函數 做特征空間變換，令 則有 可將一個在低維空間很復雜的決策面，變換成一個高維空間的線性函數： 稱之為廣義線性判別函數。即 在變換后的空間中是線性的，在原空間是非線性的。 一般來說，對于任意高次判別函數 ，都可以通過適當的變換變成廣義線性判別函數 ，利用線性判別函數的簡單性來解決復雜問題。 但是，這種變換帶來一個很嚴重的問題： 維數大大增加，例中2維變成15維 維數增加導致所需樣本數呈指數增加。目錄線性不可分問題核函數松弛變量多輸入多輸出支持向量

2、機回歸算法支持向量機實現研究現狀數據線性不可分的情況 解決的一個途徑(支持向量機算法)是用“超曲面”代替“超平面”,找一個能夠正確分類所有觀測樣本的的“最大間隔超曲面”。紅點 x2+y2-4y=0綠點x2+y2-4y=-3映射形式為：()=例：二維線性不可分映射到三維后線性可分 在用線性學習器學習一個非線性關系，需要選擇一個非線性特征集，并且將數據寫成新的表達形式，等價于：用一個固定的非線性映射，將數據映射到特征空間，在特征空間中使用線性學習器。因此，考慮的假設集是這種類型的函數：這里：X-F是從輸入空間到某個特征空間的映射1.首先使用一個非線性映射將數據變換到一個特征空間F2.然后在特征空間

3、使用線性學習器分類。低維非線性到高維線性這意味著建立非線性學習器分為如下幾步：如何處理線性不可分數據目錄線性不可分問題核函數松弛變量支持向量機實現研究現狀核函數對于非線性的情況，SVM 的處理方法是選擇一個核函數 (,) ，通過將數據映射到高維空間，來解決在原始空間中線性不可分的問題。 核函數通過把數據映射到高維空間來增加第一節所述的線性學習器的能力，使得線性學習器對偶空間的表達方式讓分類操作更具靈活性和可操作性。因為訓練樣例一般是不會獨立出現的，它們總是以成對樣例的內積形式出現，而用對偶形式表示學習器的優勢在為在該表示中可調參數的個數不依賴輸入屬性的個數，通過使用恰當的核函數來替代內積，可以

4、隱式得將非線性的訓練數據映射到高維空間，而不增加可調參數的個數(當然，前提是核函數能夠計算對應著兩個輸入特征向量的內積)。 基本概念 低維非線性到高維線性在我們遇到核函數之前，如果用原始的方法，那么在用線性學習器學習一個非線性關系，需要選擇一個非線性特征集，并且將數據寫成新的表達形式，這等價于應用一個固定的非線性映射，將數據映射到特征空間，在特征空間中使用線性學習器，因此，考慮的假設集是這種類型的函數： 這里：X-F是從輸入空間到某個特征空間的映射，這意味著建立非線性學習器分為兩步：1.首先使用一個非線性映射將數據變換到一個特征空間F，2.然后在特征空間使用線性學習器分類。13在上文我提到過對

5、偶形式，而這個對偶形式就是線性學習器的一個重要性質，這意味著假設可以表達為訓練點的線性組合，因此決策規則可以用測試點和訓練點的內積來表示：對一個函數k，滿足所有的x，z都有k(x,z)=,這里的(x)為從X到內積特征空間F的映射，則稱k為核函數。求解i, i=1,2,n進行分類回顧：核函數的引入在求解分類函數和利用分類函數進行分類時，都涉及到“高維特征向量求內積”。若映射到的高維空間維數太高甚至是無窮維時，存在“維數災難”。若存在這么一個函數 (.,.),滿足：也就是說，我們要求的高維空間中向量內積運算，可以直接在低維空間進行運算求得，兩者的值相等，這樣就避免直接在高維空間求向量積可能帶來的維

6、數災難問題。那么分類函數相應為當特征空間維數很高或為無窮維時，直接計算高維空間中的內積是非常困難的，因此需要另外的方法。那么巧妙地將高維空間中的求內積運算轉化為低維空間中的運算，避免“維數災難”。核函數的引入16核函數能簡化映射空間中的內積運算，在我們的 SVM 里需要計算的地方數據向量總是以內積的形式出現的。對比剛才我們上面寫出來的式子，現在我們的分類函數為：其中 由如下dual問題計算而得：避開了直接在高維空間中進行計算，而結果卻是等價的！核函數的引入 因此，只要找到適當的核函數，就可以實現某個線性變換后的線性分類。 尋優函數為： 分類函數為：支持向量機的基本思想： 通過非線性變換將輸入空

7、間變換到一個高維空間，然后在這個變換空間中求最優分界面，實現分類。這種非線性變換是通過定義適當的內積函數，用內積運算實現的。（不必真的進行這種非線性變換）支持向量機核函數：如何處理非線性數據01某種試驗方法的名稱這種方法的特點如果用 X1 和 X2 來表示這個二維平面的兩個坐標的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：如果我們構造另外一個五維空間，其中五個坐標為 則有：如果我們做一個映射 :R2R5 ，將 X 按照上面的規則映射為 Z ，那么在新的空間中原來的數據將變成線性可分的，從而使用之前我們推導的線性分類算法就可以進行處理了。這正是 Kernel

8、 方法處理非線性問題的基本思想。例子.設兩個向量 和 ，而 即是到前面說的五維空間的映射，因此映射過后的內積為：而這個式子與下面這個是等價的 ： 一個是映射到高維空間中，然后再根據內積的公式進行計算；而另一個則直接在原來的低維空間中進行計算，而不需要顯式地寫出映射后的結果。 我們把這里的計算兩個向量在隱式映射過后的空間中的內積的函數叫做核函數 (Kernel Function) 20核函數能簡化映射空間中的內積運算，在我們的 SVM 里需要計算的地方數據向量總是以內積的形式出現的。對比剛才我們上面寫出來的式子，現在我們的分類函數為： 其中 由如下 dual 問題計算而得：這樣一來計算的問題就算

9、解決了，避開了直接在高維空間中進行計算，而結果卻是等價的！ 是高維或無窮維度空間中的向量積運算核函數K（ .，.）是直接在低維度空間中進行計算，兩者計算結果相等按照前面的思路，處理線性不可分數據步驟為:首先尋找一個映射函數將數據映射到高維空間，(在高維空間中數據可能變得線性可分)在高維空間中應用SVM分析求解過程中引入核函數。得到分類函數但實際上，尋找使變得線性可分的映射函數很難。尋找與映射函數對應的核函數更難。核函數的實際應用問題上：理論上核函數的使用下：實際中核函數的使用高維空間中的最優分類面非線性問題通過非線性變換將它轉化為某個高維空間中的線性問題，在這個高維空間中尋找最優分類面。分類函

10、數只涉及到訓練樣本之間的內積運算 ,因此,在高維空間中只需進行內積運算,這種內積運算可通過定義在原空間中的函數來實現, 甚至不必知道變換的形式。SLT指出,根據Hibert-Schmidt原理,只要一種運算滿足Mercer條件,就可以作為內積使用。Mercer條件問題：什么樣的函數能作為核函數？ 2.3支持向量機2數據線性不可分的情況對偶優化問題（D）: 求解對偶問題的最優解后,支持向量機的決策函數為： 在最優分類面中采用適當的內積函數就可以實現某一非線性變換后的線性分類,而計算復雜度卻沒有增加。非線性支持向量機 核函數分類不同的內積核函數將形成不同的算法,目前,在SVM理論研究與實際應用中,

11、最常使用的有以下四類核函數:（1）線性核函數：（2）多項式核函數： , q是自然數。此時得到的支持向量機是一個q階多項式分類器。（3）Gauss徑向基核函數: 。得到的支持向量機是一種徑向基函數分類器。（4）Sigmoid核函數： a和t是常數，tanh是Sigmoid函數。常用的核函數RBF核函數如何選擇核函數，有哪些指導原則？映射到高維空間就一定線性可分嗎？如果高維空間仍然線性不可分，那該怎么辦？核函數的選擇，沒有明確的原則，一般根據具體問題，采用試探的方式。核函數隱藏著一個到高維的映射，可能使得數據在高維變得線性可分，但并不不能保證映射到高維空間后一定線性可分。若仍然線性不可分，引入松弛

12、變量、懲罰系數，放松約束，雖然仍然不能保證對訓練數據線性可分，但它會根據我們給出的懲罰因子找到代價最小的分類器。機器學習-周志華著 上有這樣一句話：“幸運的是，如果原始空間是有限維，即屬性有限，那么一定存在一個高緯度特征空間使樣本可分。” 但是沒有給出證明或參考文獻。兩個問題回答高維空間中的最優分類面非線性問題通過非線性變換將它轉化為某個高維空間中的線性問題，在這個高維空間中尋找最優分類面。分類函數只涉及到訓練樣本之間的內積運算。因此,在高維空間中只需進行內積運算,這種內積運算可通過定義在原空間中的函數來實現, 甚至不必知道變換的形式。 在最優分類面中采用適當的內積函數就可以實現某一非線性變換

13、后的線性分類, 而計算復雜度卻沒有增加。SLT指出,根據Hibert-Schmidt原理,只要一種運算滿足Mercer條件,就可以作為內積使用。目錄線性不可分問題核函數松弛變量多輸入多輸出支持向量機回歸算法支持向量機實現研究現狀引入松弛變量33現在去考慮映射到高維也不可分的情況，原來的約束條件是其中c是一個參數為常量，是需要優化的變量之一。現在考慮到映射到高維不可分，約束條件變為：其中稱為松弛變量，對應數據點x可以偏離的函數間隔的量，即將限制或約束條件加入到目標函數中，得到新的拉格朗日函數：這里的和都是拉格朗日乘子34然后將其看作是變量w和b的函數，分別對其求偏導，然后帶入公式中，求帶入后公式

14、的極大值我們會發現，沒有了參數 ，與之前的模型唯一不同是在于 又多了小于等于C的條件。而和函數化的非線性形式也是一樣的，只要把換成K(Xi,Xj)即可。目錄線性不可分問題核函數松弛變量多輸入多輸出支持向量機回歸算法支持向量機實現研究現狀多輸入多輸出支持向量機回歸算法 支持向量機是從線性可分情況下的最優分類面發展而來的。支持向量機形式上類似于一個神經網絡，輸出是中間節點的線性組合，每個中間節點對應于一個支持向量，其結構如圖1所示。支持向量機線性回歸（1）支持向量機線性回歸支持向量機線性回歸支持向量機線性回歸支持向量機線性回歸由此推出支持向量機線性回歸支持向量機線性回歸支持向量機線性回歸支持向量機

15、線性回歸支持向量機線性回歸支持向量機非線性回歸支持向量機非線性回歸(14)支持向量機非線性回歸SVM優點總結 SVM發展到現在經久不衰（十大經典機器學習和數據挖掘算法之一），反思一下SVM為何如此強大：首先模型選擇非常好，提出了最大距離分類面和KKT對偶化是分不開的，轉化為對偶問題不但運算效率高，而且很自然的擴展到存在松弛的線性可分、通過核函數轉為高維線性可分對偶問題的目標函數模型只是將輸入空間內積轉化為對應映射空間（更高維）的內積，而且由于核函數還使得運算過程在低維進行。不需要估計數據點的分布、概率密度函數這之類的先驗知識（如貝葉斯分類器等），推廣能力強！目錄線性不可分問題核函數松弛變量支持

16、向量機實現研究現狀支持向量機實現SVMlight - 2.private:/usr/local/binsvm_learn, svm_classifybsvm - 2.private:/usr/local/binsvm-train, svm-classify, svm-scalelibsvm - 2.private:/usr/local/binsvm-train, svm-predict, svm-scale, svm-toymySVMMATLAB svm toolbox支持向量機實現目錄線性不可分問題核函數松弛變量支持向量機實現研究現狀研究現狀應用研究支持向量機研究支持向量機算法研究應用研究S

17、VM的應用主要于模式識別領域貝爾實驗室對美國郵政手寫數字庫進行的實驗分類器錯誤率人工表現2.5%決策樹C4.516.2%最好的兩層神經網絡5.9%SVM4.0%SVM與神經網絡（NN）的對比SVM的理論基礎比NN更堅實，更像一門嚴謹的“科學”（三要素：問題的表示、問題的解決、證明）SVM 嚴格的數學推理NN 強烈依賴于工程技巧推廣能力取決于“經驗風險值”和“置信范圍值”，NN不能控制兩者中的任何一個。NN設計者用高超的工程技巧彌補了數學上的缺陷設計特殊的結構，利用啟發式算法，有時能得到出人意料的好結果。“我們必須從一開始就澄清一個觀點，就是如果某事不是科學，它并不一定不好。比如說，愛情就不是科

18、學。因此，如果我們說某事不是科學，并不是說它有什么不對，而只是說它不是科學。” by R. Feynman from The Feynman Lectures on Physics, Addison-Wesley同理，與SVM相比，NN不像一門科學，更像一門工程技巧，但并不意味著它就一定不好！主要應用領域手寫數字識別語音識別人臉識別文本分類支持向量機研究如何針對不同的問題選擇不同的核函數仍然是一個懸而未決的問題。標準的SVM對噪聲是不具有魯棒性的,如何選擇合適的目標函數以實現魯棒性是至關重要的。支持向量機算法研究支持向量機的本質是解一個二次規劃問題,雖然有一些經典（如對偶方法、內點算法等）,但

19、當訓練集規模很大時,這些算法面臨著維數災難問題。為此,人們提出了許多針對大規模數據集的SVM訓練算法。支持向量機算法研究（續1）思路1：分解子問題塊算法SMO算法(Sequential Minimal Optimization)思路2：序列優化思路3：近鄰SVM支持向量機算法研究（續2）訓練SVM的絕大多數算法都是針對分類問題,只有一小部分算法考慮了回歸函數的估計問題。提高算法效率、降低復雜度。支持向量機算法研究（續3）SVM增量學習算法的研究超球面SVM算法研究One-class SVM算法SVM多值分類器算法One-against-the-rest（一對多方法）One-against-one（一對一方法）Multi-class Objective Functions（多類SVM）Decision Directed A