svm5的演算法

『壹』 分類演算法 - SVM演算法

SVM的全稱是Support Vector Machine，即支持向量機，主要用於解決模式識別領域中的數據分類問題，屬於有監督學習演算法的一種。SVM要解決的問題可以用一個經典的二分類問題加以描述。如圖1所示，紅色和藍色的二維數據點顯然是可以被一條直線分開的，在模式識別領域稱為線性可分問題。然而將兩類數據點分開的直線顯然不止一條。圖2和3分別給出了A、B兩種不同的分類方案，其中黑色實線為分界線，術語稱為「決策面」。每個決策面對應了一個線性分類器。雖然在目前的數據上看，這兩個分類器的分類結果是一樣的，但如果考慮潛在的其他數據，則兩者的分類性能是有差別的。

之前在b站看到一個非常好的介紹！！十分推薦， 這是傳送門

按照我自己的理解，以二維數據為例，我們喂給模型已經分類好的數據，那麼假設有一線條可以將此部分數據正確劃分為2大部分，這樣可以形成2個等式，即橫線兩邊的數值歸類為1或者-1，一般情況下可以求出最大間隔即無數個解，因此需要一個限定條件求出最優的那條線條。限定方式為：無數個解形成一個解的范圍，距離邊緣相等的那條線條即是最優解。

有時候本來數據的確是可分的，也就是說可以用線性分類SVM的學習方法來求解，但是卻因為混入了異常點，導致不能線性可分，比如下圖，本來數據是可以按下面的實線來做超平面分離的，可以由於一個橙色和一個藍色的異常點導致我們沒法按照線性分類支持向量機方法來分類。

以上討論的都是在線性可分情況進行討論的，但是實際問題中給出的數據並不是都是線性可分的，比如有些數據可能是曲線的。

那麼這種非線性可分的數據是否就不能用SVM演算法來求解呢？答案是否定的。事實上，對於低維平面內不可分的數據，放在一個高維空間中去就有可能變得可分。以二維平面的數據為例，我們可以通過找到一個映射將二維平面的點放到三維平面之中。理論上任意的數據樣本都能夠找到一個合適的映射使得這些在低維空間不能劃分的樣本到高維空間中之後能夠線性可分。

當特徵變數非常多的時候，在高維空間中計算內積的運算量是非常龐大的。考慮到我們的目的並不是為找到這樣一個映射而是為了計算其在高維空間的內積，因此如果我們能夠找到計算高維空間下內積的公式，那麼就能夠避免這樣龐大的計算量，我們的問題也就解決了。實際上這就是我們要找的 核函數 ，即兩個向量在隱式映射後的空間中的內積。

（1）對於邊界清晰的分類問題效果好；
（2）對高維分類問題效果好；
（3）當維度高於樣本數的時候，SVM 較為有效；
（4）因為最終只使用訓練集中的支持向量，所以節約內存

（1）當數據量較大時，訓練時間會較長；
（2）當數據集的噪音過多時，表現不好；
（3）SVM 不直接提供結果的概率估計，它在計算時直接使用 5 倍交叉驗證。

（1）LR 與 SVM 都是分類演算法；
（2）LR 與 SVM 都是監督學習演算法；
（3）LR 與 SVM 都是判別模型；
（4）關於判別模型與生成模型的詳細概念與理解，筆者會在下篇博文給出，這里不詳述。
（5）如果不考慮核函數，LR 與 SVM 都是線性分類演算法，也就是說他們的分類決策面都是線性的

這里需要說明的是，LR 也是可以用核函數的，因在 LR 演算法里，每個樣本點都必須參與決策面的計算過程，也就是說，如果在 LR 里也運用核函數的原理，那麼每個樣本點都必須參與核計算，這帶來的計算復雜度是相當高的。所以在具體應用時，LR 很少運用核函數機制。

（1）損失函數不同；
（2）SVM 只考慮支持向量，而 LR 考慮全局（即遠離的點對邊界線的確定也起作用）；
（3）在解決非線性問題時，SVM 採用核函數的機制，而 LR 通常不採用核函數的方法；
（4）SVM 的損失函數就自帶正則（損失函數中的12||w||2項），這就是為什麼 SVM 是結構風險最小化演算法的原因，而 LR 必須另外在損失函數上添加正則項；
（5）LR是參數模型，SVM是非參數模型，本質不同。
（6）在訓練集較小時，SVM 較適用，而 LR 需要較多的樣本。

（1）LR 與線性回歸都是廣義的線性回歸；
（2）線性回歸模型的優化目標函數是最小二乘，而 LR 則是似然函數；
（3）線性回歸在整個實數域范圍內進行預測，敏感度一致，而分類范圍，需要在[0,1]。邏輯回歸就是一種減小預測范圍，將預測值限定為[0,1]間的一種回歸模型，因而對於這類問題來說，邏輯回歸的魯棒性比線性回歸的要好。
（4）邏輯回歸的模型本質上是一個線性回歸模型，邏輯回歸都是以線性回歸為理論支持的。但線性回歸模型無法做到 sigmoid 的非線性形式，sigmoid 可以輕松處理 0/1 分類問題。
（5）線性回歸主要做預測，LR 主要做分類（如二分類）；

『貳』 機器學習演算法中的SVM和聚類演算法

相信大家都知道，機器學習中有很多的演算法，我們在進行機器學習知識學習的時候一定會遇到過很多的演算法，而機器學習中的SVM演算法和聚類演算法都是比較重要的，我們在這篇文章中就重點給大家介紹一下這兩種演算法，希望這篇文章能夠幫助大家理解這兩種演算法。

機器學習演算法——SVM

提道機器學習演算法就不得不說一說SVM，這種演算法就是支持向量機，而支持向量機演算法是誕生於統計學習界，這也是機器學習中的經典演算法，而支持向量機演算法從某種意義上來說是邏輯回歸演算法的強化，這就是通過給予邏輯回歸演算法更嚴格的優化條件，支持向量機演算法可以獲得比邏輯回歸更好的分類界線。不過如果通過跟高斯核的結合，支持向量機可以表達出非常復雜的分類界線，從而達成很好的的分類效果。核事實上就是一種特殊的函數，最典型的特徵就是可以將低維的空間映射到高維的空間。

於是問題來了，如何在二維平面劃分出一個圓形的分類界線？其實我們在二維平面可能會很困難，但是通過核可以將二維空間映射到三維空間，然後使用一個線性平面就可以達成類似效果。也就是說，二維平面劃分出的非線性分類界線可以等價於三維平面的線性分類界線。接著，我們可以通過在三維空間中進行簡單的線性劃分就可以達到在二維平面中的非線性劃分效果。而支持向量機是一種數學成分很濃的機器學習演算法。在演算法的核心步驟中，有一步證明，即將數據從低維映射到高維不會帶來最後計算復雜性的提升。於是，通過支持向量機演算法，既可以維持計算效率，又可以獲得非常好的分類效果。因此支持向量機在90年代後期一直占據著機器學習中最核心的地位，基本取代了神經網路演算法。

機器學習演算法——聚類演算法

說完了SVM，下面我們給大家介紹一下聚類演算法，前面的演算法中的一個顯著特徵就是我的訓練數據中包含了標簽，訓練出的模型可以對其他未知數據預測標簽。在下面的演算法中，訓練數據都是不含標簽的，而演算法的目的則是通過訓練，推測出這些數據的標簽。這類演算法有一個統稱，即無監督演算法。無監督演算法中最典型的代表就是聚類演算法。而聚類演算法中最典型的代表就是K-Means演算法。這一演算法被廣大朋友所應用。

現在，我們可以清楚認識到機器學習是一個綜合性很強的學科。在這篇文章中我們給大家介紹了很多關於機器學習中的支持向量機和聚類演算法的相關知識，通過這些知識我們不難發現機器學習中有很多有用的演算法，熟練掌握這些演算法是我們真正學會機器學習的必經之路。

『叄』 SVM演算法原理

一、決策面方程

以二維空間為例，二維空間中任意一條直線方程可以寫為

我們將其向量化，可以得到

設用向量w代表矩陣a1和a2，用向量x代表矩陣x1和x2，標量γ代表b，則方程可化表示為

從方程可知，一個n維空間的超平面在二維空間上的表現，可以是一條直線，或者一個曲線（二維空間中只能看到這個n維超平面穿過而無法看到其模樣）， 超平面方程即是我們的決策面方程

二、函數間隔和幾何間隔

在SVM監督學習中，我們規定標簽數據為+1和-1兩個值，這么做的目的， 可以計算出任意一個樣本點在超平面方程上的表現結果的符號，與標簽符號是否一致來判斷分類的正確性 ，為此我們可以引入函數間隔的概念

但是當我們成比例的縮放w和γ，函數間隔的值也將成比例的變化，可是超平面的位置並沒有發生任何變化，所以函數間隔並不是我們想要的分類間隔，為此，我們需要引入幾何間隔的概念

還是以二維空間出發，任意一點到直線的距離可以寫成

我們將其拓展到n維空間，直線方程即是我們的超平面方程，則n維空間中任何一點到超平面的距離可以寫成

為此，我們引入幾何間隔概念，其中||w||表示向量w的二范數

從幾何間隔可以看出，就算等比例縮放w和γ，由於除上了||w||使得幾何間隔的值不會改變，它只隨著超平面位置的變化而變化，因此， 我們要尋找的分類間隔是幾何間隔

三、不等式約束條件

SVM演算法的目的是找到一個將分類效果達到最合理化的超平面，這個超平面即是分類器 。而評估分類器的好壞的標准就是分類間隔的大小

我們定義分類間隔的距離為d，好的分類器應該讓所有樣本點到決策面的幾何間隔都大於等於d

化簡上式，不等式兩邊同時除以d可得

由於||w||和d都是標量，可定義

則上式可化簡為

在不等式兩邊同時乘以yi，即將兩個式子化簡為一個式子（這里體現了正是因為標簽數據為+1和-1，才方便將約束條件變成一個約束方程）

這個約束方程的意義 即是任何樣本點到超平面（分類器）的幾何間隔都大於等於分類間隔

四、SVM最優化模型的數學描述

評估分類器的優劣是分類間隔的大小，且對於任意樣本點都滿足約束方程

由約束方程可知，當樣本點落在支持向量邊界上有如下關系

則分類間隔d可以表示為支持向量點到超平面的幾何間隔

要讓任何樣本點都在d之外，即求分類間隔d的最大值，則目標函數可以寫成

為了方便在後續最優化處理中對目標函數的求導，我們將目標函數做等效變化

由目標函數是二次的，而約束條件是線性的，則 SVM的數學模型即是：不等式約束條件下的二次型函數優化 ，而求解這一類優化問題，接下來我們需要構造 拉格朗乘子函數

五、引入拉格朗函數

目標函數是求解在約束條件g(x)下的二次型函數f(x)的最小值，直觀上我們希望構造一個函數L(x)，使得L(x)在f(x)的可行解區域內的求出的值和f(x)求出的值完全一樣，而在f(x)的可行解區域外，L(x)的值又接近無窮大，這么做的目的，使得我們可以用一個函數L(x)來等效表示原問題的g(x)和f(x)

拉格朗函數的目的，就是將約束條件融合到目標函數中，構造一個新函數來表示目標函數，將有約束的優化問題轉化為無約束的優化問題

下面，我們構造拉格朗函數來表示目標函數

其中αi是拉格朗日乘子，每一個約束條件對應一個拉格朗日乘子，其中αi大於等於0

則原優化問題可以轉化為

討論如下條件(1)(2)：

(1) 當樣本點不滿足約束條件時，即說明在 可行解區域外

此時將αi置為正無窮大，那麼θ(w)顯然也是正無窮大

(2) 當樣本點滿足約束條件時，即說明在 可行解區域內

此時θ(w)的最小值就是原目標函數，於是綜上所述，引入拉格朗乘子函數後，可以得到新的目標函數

我們用p*表示優化目標函數後的最優解，且與最初的目標函數等價

觀察新的目標函數，如果直接求偏導數求解，那麼一上來將面對w和b兩個未知參數，而αi又是不等式約束，求解過程將非常復雜。換一個角度思考，如果將max和min的位置對調，變成如下新的目標函數

上式變化使用了 拉格朗日函數的對偶性，交換後的新問題即是原目標函數的對偶問題 ，我們用d*來表示對偶目標函數的最優解，可見d*的求導過程比p*相對容易，且d*<=p*，而當滿足下列條件時，d*= p*

因為目標函數本身已經是一個凸函數，而優化問題又是求解最小值，所以目標函數的最優化問題就是凸優化問題，則接下來就要重點討論KKT條件

六、KKT條件的描述

一個最優化模型能夠表示成下列標准形式

其中f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，m和n分別是等式約束和不等式約束的數量

KKT條件即是規定f(x)的 最優值 必須滿足以下(1)(2)(3)條件， 只有滿足KKT條件，目標函數的最優化問題依然可以用拉格朗日乘子法解決

很明顯，我們需要優化的目標函數屬於帶有不等式約束函數g(x)，所以條件二顯然滿足，下面我們來分析條件一和條件三的理論

七、目標函數的等高線與約束條件的最優值分析（條件一）

對於KKT條件一的分析，我們假設目標函數是f(x1,x2)的二元函數，它的圖像在三維空間里是一個曲面，准確的來說是一個凸曲面

其中g(x1,x2)是約束方程，要求目標函數f(x1,x2)的最小值，即轉化為 求g(x1,x2)=c這條曲線上的一點，使得f(x1,x2)取得最小值，換個比喻，就是在山上（目標函數曲面）尋找一條山路（約束條件曲線）的最低點

我們畫出目標函數的等高線，來分析目標函數最優值和約束條件的關系

對於研究目標函數z=f(x1,x2)，當z取不同的值，即將曲線z投影在(x1,x2)組成的空間中（這里指的是二維空間），也就是曲面的等高線，上圖中d1和d2即是兩條目標函數的等高線，可以看出，當約束函數g(x1,x2)與目標函數的等高線有共同的交點， 即證明這組值同時滿足在目標函數的可行域中，也符合約束條件的約束關系

如果等高線與g(x1,x2) 相交 ，則是一組目標函數的解，但是這個解一定不是最優解， 因為相交意味著肯定存在其它等高線在該條等高線的內部或者外部 ，可能會使得新的等高線與g(x1,x2)的交點更大或者更小，這就意味著只有當等高線與g(x1,x2) 相切 ，才可能得到最優解（切線可能多條）

所以最優解必須滿足： 目標函數的負梯度方向與約束函數的梯度方向一致

而上式恆成立的條件就是： 拉格朗日乘子α >= 0 ，且這個式子就是目標函數對各個參數求偏導數的結果，即KKT的第一個條件：目標函數對各個參數的導數為0

八、分類討論約束條件和拉格朗日乘子的組合（條件三）

對於KKT條件三，可以看出，因為所有的約束函數gi(x)<=0，所有的拉格朗日乘子αi>=0，要使得求和後結果為0，要麼某個約束函數gi(x)=0，要麼其對應的αi=0

從一個案例出發來分析KKT條件三的邏輯，假設目標函數和約束函數是

將不等式約束構造出拉格朗日函數，並分別對x1和x2求偏導數

而KKT的條件三要求最優解滿足 ∑α*g(x) = 0，在這個案例里α和g(x)只有一個，結合條件一，可以得到

根據之前的分析，最優值滿足條件三的話，要麼α=0，要麼g(x)=0

（i）：如果α=0，則x1=1，x2=-2，代入g(x1,x2) =10-1-10*(-2)=29>0，發現這組解違背了約束函數g(x)<0，則舍棄這組解

（ii）: 如果g(x1,x2)=0，則代入x1和x2的表達式到g(x)中，解出α=58/101>0，發現這組解不違背約束函數，則代入α解出x1=130/101，x2=88/101，則這組解有可能是最優解

綜上(i)(ii)討論，目標函數的最優值符合KKT條件三，也說明了 滿足強對偶條件的優化問題的最優值必須滿足KKT條件

九、求解對偶問題

上面分析了目標函數滿足凸優化和KKT條件，則問題轉化為求解原問題的對偶問題（即p*=d*）

根據對偶問題描述，先要求內側w和b關於L(w,b,α)的最小化值，即求L對w和b的偏導數

將w和b的偏導數帶入拉格朗函數化簡得

整理一下最終化簡結果為

從上述結果可以看出，樣本的x和y是已知的，此時的 L(w,b,α)函數只有一個變數，即αi

我們歸納一下現在的目標函數為

現在目標函數變成了如上形式，其中αi>=0，這里隱含著一個假設，即數據100%線性可分，但是現實生活中，數據往往是不會那麼規則的線性化，為此我們需要引入鬆弛變數

十、引入鬆弛變數

由於現實世界中的數據都是帶有噪音的，也就是數據可能出偏離其正常的位置很遠，而出現這種極端現象後往往會影響超平面的選擇，也許將無法構造出將數據徹底分開的超平面出來

所以對於處理這種情況， SVM需要允許（妥協）出某些噪音很大的數據點能夠偏離超平面，即允許其出現在超平面的錯誤的一側 ，為此我們引入鬆弛變數C，這樣我們的目標函數又變為

接下來為了研究討論αi的取值范圍，我們加上一個負號將目標函數等價轉化為

十一、討論拉格朗乘子的取值意義和其值域

回顧一下最初的約束條件為

設ui為該約束條件，可以歸納出αi關於約束函數的取值意義

αi只有滿足上述3種情況，才能求出最優解，所以 當αi與約束條件ui沖突的時候，需要更新這些αi ，這也就是滿足目標函數的第一個約束限制，即0<=αi<=C

而同時目標函數還受到第二個約束條件的限制，即

所以不能只更新一個αi因子，需要同時再次更新第二個αj因子，也就是 α因子總是成對的更新（αi對總是和αj配對），一增一減，此消彼長，才能保證加權和為0的約束 ，同時這也就是下面提及SMO演算法的思想和多元函數化簡為二元函數，在從二元函數化簡為一元函數的難點

根據這個約束和α因子需要成對更新，假設我們選取的兩個拉格朗乘子為α1和α2，則更新之前是old，更新之後是new，且更新前後需要滿足和為0的約束

兩個因子同時更新顯然非常困難，所以需要先求出第一個αj的解，再用αj的解去表示更新第二個αi的解 ，後文的SMO演算法會闡述這一點。因此需要先確定αj的取值范圍，假設L和H分別為它的下界和上界，結合目標函數的約束限制來綜合討論L和H的取值關系

（i）：當y1和y2異號時，可以得到

移項可得a2 = a1 - A，此時α的取值范圍如下圖所示

所以此時α的上下界H和L為

（ii）：當y1和y2同號時，可以得到

移項可得a2 = -a1 + A，此時α的取值范圍如下圖所示

所以此時α的上下界H和L為

綜上(i)(ii)的討論，通過y1和y2的異號或者同號，可以推導出α更新後的上下界分別為

這個公式顯得非常的重要，它將α因子限制在有效的矩形范圍內，在SMO演算法中，當我們更新完α後，由於α可能會被更新得很大或很小，因此需要經過裁剪來保證α的在約束條件內

12、SMO演算法的思想

回顧之前第九，第十，第十一步的分析，目標函數為

目標函數只包含n個變數α的 多元函數 ，且帶有兩個約束條件，我們的 目的是求出目標函數的最小值，即找到一組α的組合，使得目標函數取得最小值

由第十一步的分析，我們需要不斷更新這n個α因子，通過迭代來逼近函數達到最小值，但是如果一次性更新n個參數，將會有n!種組合，那麼時間復雜度將會非常高，為此我們首先想到 坐標上升（下降）法

來通過一個例子來說明坐標上升法的思路

可知案例中要求一個三元函數的最大值， 演算法的思想是每次迭代時只更新一個維度，通過多次迭代直到收斂來優化函數的最值 ，求出三個變數的偏導數推出其關系

通過迭代即就可以求出其最值

SMO演算法借鑒了坐標上升（下降）法的思想來優化α因子組合，但是由於目標函數的第二個約束條件有加權和為0的限制，導致每次迭代時候不能只更新一個因子αi，必須同時更新與之配對的另一個因子αj，此消彼長才能保證加權和為0（第十一步中已提及）

所以SMO演算法思想是將原始問題中，求解n個參數的二次規劃問題，分解成了多個子二次規劃問題來分別求解，每一個子問題只需要求解2個參數，即將多元函數推導為二元函數，再將二元函數推導為一元函數

13、多元函數推導為二元函數

目標函數是關於α的N元函數，通過SMO的演算法思想，假設每次迭代更新，選取一對α1和α2的組合，其餘的乘子不變， 首先需要將α1和α2從目標函數中分離出來 ，也就是將多元函數推導為二元函數

從N元函數中分離出α1和α2因子

由於上式推導結果過於復雜，我們定義2個表達式來表示上式常量部分，用來簡化上式

又由於單獨存下的常數項對以後的求導沒有貢獻，所以我們提出單獨的常數項定義為Constant

帶入vi和Constant表達式，則結果化簡為

至此，我們將 多元函數推導為含有α1和α2變數的二元函數 ，接下來將這個二元函數推導為一元函數

14、二元函數推導為一元函數

我們需要推導出α1和α2的關系，然後用α2來表示α1帶入二元函數，就可以推導出關於α2的一元函數了

由目標函數的第二個約束條件

同理根據SMO演算法思想，從約束條件中分離出α1和α2

將等式兩邊同時乘以y1，可推導出α1和α2的關系

同理，我們定義兩個表達式r和s來表示上式的常量部分，用來簡化上式關系

帶入r和s後，α1和α2的關系推導為

下面將α1帶入我們的二元函數中，可得

至此， 我們將二元函數推導為只含有一個變數α2的一元函數 ，接下來終於可以對目標函數求導了

15、求解一元函數的偏導數，推導出第一個拉格朗乘子的遞推關系

我們對一元函數求α2的偏導數為0

帶入s=y1*y2和y2*y2=1，整理上式可求出α2

『肆』 SVM演算法-推導

第一部分：從幾何意義到數學表達

第三部分：SMO
求解第二部分最後推導出的最小化問題，每次固定兩個lambda，由於有最後一個條件限制：lambdai*yi + lambdaj yj = const，labmdai可以用lambdaj表達出來，最小化函數是一個拋物線，開口朝上，求導，令導數為0，獲得沒有限制的最優化問題，由於lambdai >= 0（第1個限制條件），做一個clipping，獲得在限制條件下的lambdai最優解，然後也能求得lambdaj，就完成了一次lambdai和lambdaj的更新迭代。
一般取最違反KKT條件的lambdai和lambdaj來做更新。

svm軟間隔

svm的核函數選擇

一般選擇高斯核函數，線性核函數是高斯核函數的一個特例；在特定的參數下，sigmoid核函數和高斯核函數具有類似的作用；相比於多項式核函數，高斯核函數的參數更少，更好調，當然，如果能把多項式核函數的參數調好，有可能會獲得更好的效果。對於特徵數量非常大的情況，會更傾向於使用線性核函數。

為什麼要轉化為對偶問題?

高斯核函數無限維的理解

『伍』 svm演算法是什麼

SVM(Support Vector Machine)中文名為支持向量機，是常見的一種判別方法。

支持向量機（Support Vector Machine, SVM）是一類按監督學習（supervised learning）方式對數據進行二元分類的廣義線性分類器（generalized linear classifier），其決策邊界是對學習樣本求解的最大邊距超平面（maximum-margin hyperplane）。

數值求解特點：

SVM的求解可以使用二次凸優化問題的數值方法，例如內點法和序列最小優化演算法，在擁有充足學習樣本時也可使用隨機梯度下降。

在二次凸優化問題中，SMO的每步迭代都嚴格地優化了SVM的對偶問題，且迭代會在有限步後收斂於全局極大值。SMO演算法的迭代速度與所選取乘子對KKT條件的偏離程度有關，因此SMO通常採用啟發式方法選取拉格朗日乘子。

在每次迭代時，SGD首先判定約束條件，若該樣本不滿足約束條件，則SGD按學習速率最小化結構風險；若該樣本滿足約束條件，為SVM的支持向量，則SGD根據正則化系數平衡經驗風險和結構風險，即SGD的迭代保持了SVM的稀疏性。

『陸』 svm演算法是什麼

支持向量機（英語：support vector machine，常簡稱為SVM，又名支持向量網路）是在分類與回歸分析中分析數據的監督式學習模型與相關的學習演算法。

SVM使用鉸鏈損失函數（hinge loss）計算經驗風險（empirical risk）並在求解系統中加入了正則化項以優化結構風險（structural risk），是一個具有稀疏性和穩健性的分類器。

SVM可以通過核方法（kernel method）進行非線性分類，是常見的核學習（kernel learning）方法之一 。

SVM被提出於1964年，在二十世紀90年代後得到快速發展並衍生出一系列改進和擴展演算法，在人像識別、文本分類等模式識別（pattern recognition）問題中有得到應用。

動機

H1不能把類別分開。H2可以，但只有很小的間隔。H3以最大間隔將它們分開。

將數據進行分類是機器學習中的一項常見任務。 假設某些給定的數據點各自屬於兩個類之一，而目標是確定新數據點將在哪個類中。對於支持向量機來說，數據點被視為p維向量，而我們想知道是否可以用 (p-1)維超平面來分開這些點。

這就是所謂的線性分類器。可能有許多超平面可以把數據分類。最佳超平面的一個合理選擇是以最大間隔把兩個類分開的超平面。

因此，我們要選擇能夠讓到每邊最近的數據點的距離最大化的超平面。如果存在這樣的超平面，則稱為最大間隔超平面，而其定義的線性分類器被稱為最大間隔分類器，或者叫做最佳穩定性感知器。

應用

1、用於文本和超文本的分類，在歸納和直推方法中都可以顯著減少所需要的有類標的樣本數。

2、用於圖像分類。實驗結果顯示：在經過三到四輪相關反饋之後，比起傳統的查詢優化方案，支持向量機能夠獲取明顯更高的搜索准確度。這同樣也適用於圖像分割系統，比如使用Vapnik所建議的使用特權方法的修改版本SVM的那些圖像分割系統。

3、用於手寫字體識別。

4、用於醫學中分類蛋白質，超過90%的化合物能夠被正確分類。基於支持向量機權重的置換測試已被建議作為一種機制，用於解釋的支持向量機模型。

支持向量機權重也被用來解釋過去的SVM模型。為識別模型用於進行預測的特徵而對支持向量機模型做出事後解釋是在生物科學中具有特殊意義的相對較新的研究領域。

以上內容參考網路-支持向量機

『柒』 支持向量機（SVM）常見問題

SVM是一種二分類模型。它的基本模型是在特徵空間中尋找間隔最大化的分離超平面的線性分類器。（間隔最大化是它的獨特之處），通過該超平面實現對未知樣本集的分類。

意義：原始樣本空間中可能不存在這樣可以將樣本正確分為兩類的超平面，但是我們知道如果原始空間的維數是有限的，也就是說屬性數是有限的，則一定存在一個高維特徵空間能夠將樣本劃分。SVM通過核函數將輸入空間映射到高維特徵空間，最終在高維特徵空間中構造出最優分離超平面，從而把平面上本身無法線性可分的數據分開。核函數的真正意義是做到了沒有真正映射到高維空間卻達到了映射的作用，即減少了大量的映射計算。

選擇：

利用專家先驗知識選定核函數，例如已經知道問題是線性可分的，就可以使用線性核，不必選用非線性核。

如果特徵的數量大到和樣本數量差不多，則選用線性核函數SVM或LR。

如果特徵的數量小，樣本的數量正常，則選用高斯核函數SVM。

如果特徵的數量小，樣本數量很多，由於求解最優化問題的時候，目標函數涉及兩兩樣本計算內積，使用高斯核明顯計算量會大於線性核，所以手動添加一些特徵，使得線性可分，然後可以用LR或者線性核的SVM；

利用交叉驗證，試用不同的核函數，誤差最小的即為效果最好的核函數。

混合核函數方法，將不同的核函數結合起來。

當訓練數據線性可分時，存在無窮個分離超平面可以將兩類數據正確分開。感知機或神經網路等利用誤分類最小策略，求得分離超平面，不過此時的解有無窮多個。線性可分支持向量機利用間隔最大化求得最優分離超平面，這時，解是唯一的。另一方面，此時的分隔超平面所產生的分類結果是最魯棒的，對未知實例的泛化能力最強。

增、刪非支持向量樣本對模型沒有影響;

支持向量樣本集具有一定的魯棒性;

有些成功的應用中,SVM 方法對核的選取不敏感

雜訊數量太多

雜訊以新的分布形式出現，與原先樣本集的雜訊分布表現的相當不同。此時雜訊也有大概率落在最大分類間隔中間，從而成為支持向量，大大影響模型。

所以我們常說的魯棒性其實是主要是體現在對Outlier（異常點、離群點）上。

這里說的缺失數據是指缺失某些特徵數據，向量數據不完整。SVM沒有處理缺失值的策略（決策樹有）。而SVM希望樣本在特徵空間中線性可分，若存在缺失值它們在該特徵維度很難正確的分類（例如SVM要度量距離(distance measurement)，高斯核，那麼缺失值處理不當就會導致效果很差），所以特徵空間的好壞對SVM的性能很重要。缺失特徵數據將影響訓練結果的好壞。

SVM的空間消耗主要是在存儲訓練樣本和核矩陣，由於SVM是藉助二次規劃來求解支持向量，而求解二次規劃將涉及m階矩陣的計算（m為樣本的個數），當m數目很大時該矩陣的存儲和計算將耗費大量的內存和運算時間。如果數據量很大，SVM的訓練時間就會比較長，所以SVM在大數據的使用中比較受限。

過擬合是什麼就不再解釋了。SVM其實是一個自帶L2正則項的分類器。SVM防止過擬合的主要技巧就在於調整軟間隔鬆弛變數的懲罰因子C。C越大表明越不能容忍錯分，當無窮大時則退化為硬間隔分類器。合適的C大小可以照顧到整體數據而不是被一個Outlier給帶偏整個判決平面。至於C大小的具體調參通常可以採用交叉驗證來獲得。每個鬆弛變數對應的懲罰因子可以不一樣。

一般情況下，低偏差，高方差，即遇到過擬合時，減小C；高偏差，低方差，即遇到欠擬合時，增大C。

樣本偏斜是指數據集中正負類樣本數量不均，比如正類樣本有10000個，負類樣本只有100個，這就可能使得超平面被「推向」負類（因為負類數量少，分布得不夠廣），影響結果的准確性。

對於樣本偏斜（樣本不平衡）的情況，在各種機器學習方法中，我們有針對樣本的通用處理辦法：如上（下）采樣，數據合成，加權等。

僅在SVM中，我們可以通過為正負類樣本設置不同的懲罰因子來解決樣本偏斜的問題。具體做法是為負類設置大一點的懲罰因子，因為負類本來就少，不能再分錯了，然後正負類的懲罰因子遵循一定的比例，比如正負類數量比為100：1，則懲罰因子的比例直接就定為1:100，具體值要通過實驗確定。

優點：

非線性映射是SVM方法的理論基礎,SVM利用內積核函數代替向高維空間的非線性映射；

對特徵空間劃分的最優超平面是SVM的目標,最大化分類邊際的思想是SVM方法的核心；

支持向量是SVM的訓練結果,在SVM分類決策中起決定作用的是支持向量；

SVM 的最終決策函數只由少數的支持向量所確定,計算的復雜性取決於支持向量的數目,而不是樣本空間的維數,這在某種意義上避免了「維數災難」。

小樣本集上分類效果通常比較好。

少數支持向量決定了最終結果,這不但可以幫助我們抓住關鍵樣本、「剔除」大量冗餘樣本,而且註定了該方法不但演算法簡單,而且具有較好的「魯棒」性。這種「魯棒」性主要體現在:

①增、刪非支持向量樣本對模型沒有影響;

②支持向量樣本集具有一定的魯棒性;

③有些成功的應用中,SVM 方法對核的選取不敏感

SVM 是一種有堅實理論基礎的新穎的小樣本學習方法。它基本上不涉及概率測度及大數定律等,因此不同於現有的統計方法。從本質上看,它避開了從歸納到演繹的傳統過程,實現了高效的從訓練樣本到預報樣本的「轉導推理」,大大簡化了通常的分類和回歸等問題。

缺點：

SVM演算法對大規模訓練樣本難以實施。由於SVM是藉助二次規劃來求解支持向量，而求解二次規劃將涉及m階矩陣的計算（m為樣本的個數），當m數目很大時該矩陣的存儲和計算將耗費大量的機器內存和運算時間（上面有講）。

用SVM解決多分類問題存在困難。傳統的SVM就是解決二分類問題的，上面有介紹不少解決多分類問題的SVM技巧，不過各種方法都一定程度上的缺陷。

對缺失值敏感，核函數的選擇與調參比較復雜。

答：使用ROC曲線。Roc曲線下的面積，介於0.1和1之間。AUC值是一個概率值，當你隨機挑選一個正樣本以及負樣本，當前的分類演算法根據計算得到的Score值將這個正樣本排在負樣本前面的概率就是AUC值，AUC值越大，當前分類演算法越有可能將正樣本排在負樣本前面。Auc作為數值可以直觀的評價分類器的好壞，值越大越好，隨機情況大概是0.5，所以一般不錯的分類器AUC至少要大於0.5。

選擇ROC和ROC下曲線面積是因為分類問題經常會碰到正負樣本不均衡的問題，此時准確率和召回率不能有效評價分類器的性能，而ROC曲線有個很好的特性：當測試集中的正負樣本的分布變換的時候，ROC曲線能夠保持不變。

答：大值特徵會掩蓋小值特徵（內積計算）。高斯核會計算向量間的距離，也會產生同樣的問題；多項式核會引起數值問題。影響求解的速度。數據規范化後，會丟失一些信息。預測的時候，也要進行規范化

答：1）訓練速度：線性核只需要調節懲罰因子一個參數，所以速度快；多項式核參數多，難調;徑向基核函數還需要調節γ,需要計算e的冪，所以訓練速度變慢。【調參一般使用交叉驗證，所以速度會慢】

2）訓練結果：線性核的得到的權重w可以反映出特徵的重要性，從而進行特徵選擇；多項式核的結果更加直觀，解釋性強;徑向基核得到權重是無法解釋的。

3）適應的數據：線性核：樣本數量遠小於特徵數量(n<<m）【此時不需要映射到高維】，或者樣本數量與特徵數量都很大【此時主要考慮訓練速度】；徑向基核：樣本數量遠大於特徵數量(n>>m)

答：如果σ選得很大的話，高次特徵上的權重實際上衰減得非常快，使用泰勒展開就可以發現，當很大的時候，泰勒展開的高次項的系數會變小得很快，所以實際上相當於一個低維的子空間；

如果σ選得很小，則可以將任意的數據映射為線性可分——當然，這並不一定是好事，因為隨之而來的可能是非常嚴重的過擬合問題，因為此時泰勒展開式中有效的項將變得非常多，甚至無窮多，那麼就相當於映射到了一個無窮維的空間，任意數據都將變得線性可分。

相同

第一，LR和SVM都是分類演算法。

第二，如果不考慮核函數，LR和SVM都是線性分類演算法，也就是說他們的分類決策面都是線性的。

第三，LR和SVM都是監督學習演算法。

第四，LR和SVM都是判別模型。

第五，LR和SVM都有很好的數學理論支撐。

不同

第一，loss function不同。

第二，支持向量機只考慮局部的邊界線附近的點，而邏輯回歸考慮全局（遠離的點對邊界線的確定也起作用）。

第三，在解決非線性問題時，支持向量機採用核函數的機制，而LR通常不採用核函數的方法。在計算決策面時，SVM演算法里只有少數幾個代表支持向量的樣本參與了計算，也就是只有少數幾個樣本需要參與核計算（即kernal machine解的系數是稀疏的）。然而，LR演算法里，每個樣本點都必須參與決策面的計算過程，也就是說，假設我們在LR里也運用核函數的原理，那麼每個樣本點都必須參與核計算，這帶來的計算復雜度是相當高的。所以，在具體應用時，LR很少運用核函數機制。​

第四，​線性SVM依賴數據表達的距離測度，所以需要對數據先做normalization，LR不受其影響。一個計算概率，一個計算距離！​

第五，SVM的損失函數就自帶正則！！！（損失函數中的1/2||w||^2項），這就是為什麼SVM是結構風險最小化演算法的原因！！！而LR必須另外在損失函數上添加正則項！！！所謂結構風險最小化，意思就是在訓練誤差和模型復雜度之間尋求平衡，防止過擬合，從而達到真實誤差的最小化。未達到結構風險最小化的目的，最常用的方法就是添加正則項，SVM的目標函數里居然自帶正則項！！！再看一下上面提到過的SVM目標函數：

我們再來看看，所謂out lier，是怎麼產生的，無非有兩種情況，一種就是這個樣本的標簽y搞錯了，一種就是沒搞錯，但這個樣本是一個個例，不具備統計特性。

不論對於哪一種情況，svm會在f將這個out lier預測的比較正確時，就停止，不會一直優化對out lier的預測，因為沒有什麼太大意義了。而lr則不同，它會繼續要求f對這個out lier的預測進行優化，並且永不停止，顯然，這樣的優化很可能會削弱f的泛化性能，因為沒有必要死磕out lier 。

答案就是SVM！！！

『捌』 簡述svm演算法的原理

svm演算法是在數據中找出最優間隔平面，如果數據線性不可分，那麼可以使用核函數

『玖』 支持向量機（SVM）

        支持向量機（support vector machine），故一般簡稱SVM，通俗來講，它是一種二分類模型，其基本模型定義為特徵空間上的間隔最大的線性分類器，這族分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。SVM在很多諸如文本分類，圖像分類，生物序列分析和生物數據挖掘，手寫字元識別等領域有很多的應用。

        支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。

        假設給定一些分屬於兩類的2維點，這些點可以通過直線分割， 我們要找到一條最優的分割線，如何來界定一個超平面是不是最優的呢?

        如圖：

        在上面的圖中，a和b都可以作為分類超平面，但最優超平面只有一個，最優分類平面使間隔最大化。 那是不是某條直線比其他的更加合適呢? 我們可以憑直覺來定義一條評價直線好壞的標准:

        距離樣本太近的直線不是最優的，因為這樣的直線對雜訊敏感度高，泛化性較差。 因此我們的目標是找到一條直線（圖中的最優超平面），離所有點的距離最遠。 由此， SVM演算法的實質是找出一個能夠將某個值最大化的超平面，這個值就是超平面離所有訓練樣本的最小距離。這個最小距離用SVM術語來說叫做間隔(margin) 。

        描述：給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：

        例如：現在有一個二維平面，平面上有兩種不同的數據，分別用圈和叉表示。由於這些數據是線性可分的，所以可以用一條直線將這兩類數據分開，這條直線就相當於一個超平面，超平面一邊的數據點所對應的y全是-1 ，另一邊所對應的y全是1。

        我們令分類函數為：

        當f(x) 等於0的時候，x便是位於超平面上的點，而f(x)大於0的點對應 y=1 的數據點，f(x)小於0的點對應y=-1的點，如下圖所示：

        一個點距離超平面的遠近可以表示分類預測的確信或准確程度，如何確定這個超平面呢？從直觀上而言，這個超平面應該是最適合分開兩類數據的直線。而判定「最適合」的標准就是這條直線離直線兩邊的數據的間隔最大。所以，得尋找有著最大間隔的超平面。

補充知識點： 點到平面的距離

        支持向量機學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面.。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個(等價於感知機)，但是幾何間隔最大的分離超平面是唯一的。這里的間隔最大化又稱為硬間隔最大化。

        間隔最大化的直觀解釋是:對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點(離超平面最近的點)也有足夠大的確信度將它們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。

      按照我們前面的分析，對一個數據點進行分類， 當它的margin越大的時候，分類的confidence越大。 對於一個包含n個點的數據集，我們可以很自然地定義它的margin為所有這n個點的margin值中最小的那個。於是，為了使得分類的confidence高，我們希望所選擇的超平面hyper plane能夠最大化這個margin值。讓所選擇的超平面能夠最大化這個「間隔」值，這個間隔就是下圖中的Gap的一半：

為什麼用幾何間隔求最大的分離超平面而不用函數間隔？

例題：

我們構造了約束最優化問題，就是下面這個：

        此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。

補充知識點： 拉格朗日乘子法學習

                     拉格朗日KKT條件

                     KKT條件介紹

                     拉格朗日對偶

         通過給每一個約束條件加上一個拉格朗日乘子（Lagrange multiplier）α，定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）：

 求解這個式子的過程需要拉格朗日對偶性的相關知識。

例題：

         接下來談談線性不可分的情況，因為 線性可分這種假設實在是太有局限性 了。下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區域，每個區域只包含一種顏色的點。

         要想在這種情況下的分類器，有兩種方式， 一種是用曲線 去將其完全分開，曲線就是一種 非線性 的情況，跟之後將談到的 核函數 有一定的關系：

         另外一種還是用直線，不過不用去保證可分性 ，就是包容那些分錯的情況，不過我們得加入懲罰函數，使得點分錯的情況越合理越好。其實在很多時候，不是在訓練的時候分類函數越完美越好，因為訓練函數中有些數據本來就是雜訊，可能就是在人工加上分類標簽的時候加錯了，如果我們在訓練（學習）的時候把這些錯誤的點學習到了，那麼模型在下次碰到這些錯誤情況的時候就難免出錯了。這種學習的時候學到了「雜訊」的過程就是一個過擬合（over-fitting），這在機器學習中是一個大忌。

我們可以為分錯的點加上一點懲罰，對一個分錯的點的 懲罰函數 就是 這個點到其正確位置的距離：

        對於線性不可分的情況，我們可以用核函數讓空間從原本的線性空間變成一個更高維的空間 ， 在這個高維的線性空間下，再用一個超平面進行劃分 。 這兒舉個例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的：

        上圖是一個線性不可分的圖，當我們把這兩個類似於橢圓形的點映射到一個高維空間後，映射函數為：

        用這個函數可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)，並且對映射後的坐標加以旋轉之後就可以得到一個線性可分的點集了。

        形象說明：例如世界上本來沒有兩個完全一樣的物體，對於所有的兩個物體，我們可以通過增加維度來讓他們最終有所區別，比如說兩本書，從(顏色，內容)兩個維度來說，可能是一樣的，我們可以加上作者這個維度，是在不行我們還可以加入頁碼，可以加入擁有者，可以加入購買地點，可以加入筆記內容等等。當維度增加到無限維的時候，一定可以讓任意的兩個物體可分了。

核函數定義：

核技巧在支持向量機中的應用：

常用核函數：

非線性支持向量機學習演算法：

        支持向量機的學習問題可以形式化為求解凸二次規劃問題。這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以致無法使用。所以，如何高效地實現支持向量機學習就成為一一個重要的問題。目前人們已提出許多快速實現演算法.本節講述其中的序列最小最優化(sequential minimal optimization, SMO)演算法。

        上述問題是要求解N個參數(α1,α2,α3,...,αN)，其他參數均為已知，序列最小最優化演算法(SMO)可以高效的求解上述SVM問題，它把原始求解N個參數二次規劃問題分解成很多個子二次規劃問題分別求解，每個子問題只需要求解2個參數，方法類似於坐標上升，節省時間成本和降低了內存需求。每次啟發式選擇兩個變數進行優化，不斷循環，直到達到函數最優值。

        整個SMO演算法包括兩部分，求解兩個變數的 二次規劃 問題和選擇這兩個變數的 啟發式 方法。

 上面求得的(α1)new和(α2)new是在η>0的情況下求得的：

        當時為了推導公式我們直接默認它是大於0了，現在我們需要重新審視這一項（η）。這一項是原來關於的二次項的系數。我們可以分下面三種情況討論：

（1）當η>0時 ：這個二次函數開口向上，所以要求這個二次函數的最小值，如果說極值點不在計算出的可行域的范圍內，就要根據這個極值點和可行域邊界值的關系來得到取最小值的地方：

①如果這個極值點在可行域左邊，那麼我們可以得到這個可行域內二次函數一定在單增，所以此時L應該是那個取最小值的地方。就如大括弧的第三種情況。

②如果這個極值點在可行域右邊，那麼此時可行域內一定單減，所以此時H就是那個取最小值的地方，就是大括弧里的第一種情況。

（2）當η=0時： 這個二次函數就變成了一個一次函數，那麼不管這個一次函數的單調性怎樣，最小值一定是在邊界處取到。所以到時候計算可行域的兩個邊界的值，看哪個小就用哪個。

（3）當η<0時: 這個二次函數開口向下，那麼此時怎麼得到取最小值的點呢？很容易就能想到：最小值也是在可行域的邊界處取到。很容易理解，此時開口向下，當極值點在區間內時，最小值只能在端點處取，因為極值點處是最大的。而當極值點在區間外時，區間內一定是單調的，此時最小值也只能在端點處取。通過計算比較邊界處的目標函數值，哪個小取哪個。

通過以上判斷求出(α2)new以後，再根據公式求出(α1)new，然後帶入目標函數（1）中。即如下過程：

        上述分析是在從N個變數中已經選出兩個變數進行優化的方法，下面分析如何高效地選擇兩個變數進行優化，使得目標函數下降的最快。

『拾』 svm演算法是什麼

SVM演算法中文翻譯為支持向量機，它的英文全稱是Support Vector Machine。

之所以叫作支持向量機，是因為該演算法最終訓練出來的模型，由一些支持向量決定。所謂的支持向量，也就是能夠決定最終模型的向量。SVM演算法最初是用來解決二分類問題的，而在這個基礎上進行擴展，也能夠處理多分類問題以及回歸問題。

SVM演算法的歷史

早在1963 年，著名的前蘇聯統計學家弗拉基米爾·瓦普尼克在讀博士期間，就和他的同事阿列克謝·切爾沃寧基斯共同提出了支持向量機的概念。

但由於當時的國際環境影響，他們用俄文發表的論文，並沒有受到國際學術界的關注。直到 20 世紀 90 年代，瓦普尼克隨著移民潮來到美國，而後又發表了SVM 理論。此後，SVM 演算法才受到應有的重視。如今，SVM 演算法被稱為最好的監督學習演算法之一。