Introduction

支持向量機（Support Vector Machine，SVM）是定義在特征空間中的最大間隔線性分類器，對于非線性可分的數(shù)據(jù)，SVM引入核方法（kernel trick）使它實質(zhì)上成為非線性分類器。SVM 有兩種解釋

• 求解間隔最大的分類平面，這種情況可以轉(zhuǎn)化為一個求解凸二次規(guī)劃的問題，一般轉(zhuǎn)換為對偶問題求解；
• Hinge Loss，通過經(jīng)驗風(fēng)險最小化，采取 Hinge Loss 來求得損失函數(shù)，最終對損失函數(shù)求極值即可。

本文主要講解的是二次規(guī)劃轉(zhuǎn)對偶求解的方式，Hinge Loss解釋參考支持向量機之Hinge Loss 解釋，下面步入正題，首先引入線性可分的概念。

線性可分

超平面一般會寫成，表明w,x都為列向量。

最大化幾何間隔提出目標函數(shù)

一般來說，訓(xùn)練樣本距離分類超平面的遠近可以表示分類預(yù)測的確信程度，下圖中點 C 的類別為 -1 確信程度要明顯高于點 A 。

該確信程度可以用樣本到超平面的距離來表示，該距離便是常說的幾何距離（點到直線的距離）。樣本點??到分類平面?的幾何距離如下所示：?

分子要取絕對值(距離為正值)，分母為?L2?范數(shù)：,訓(xùn)練樣例中若,則對應(yīng)的標簽為,反之，若,則有,所以將幾何間隔寫作如下形式：

合并一下就是這個東西。

函數(shù)間隔：

且整個數(shù)據(jù)集的函數(shù)間隔為：

這里之所以引入函數(shù)間隔，是因為其是可以自由縮放大小的，比如對于分類超平面?,若左右同時擴大??倍，?，分類平面不會發(fā)生任何改變，但是對于點? 的函數(shù)間隔為：

在函數(shù)間隔也擴大了??倍的情況下，分類超平面沒與幾何間隔（超平面沒變，點沒變，幾何間隔當(dāng)然不變）卻沒變。

所以并不會對我們的優(yōu)化函數(shù)產(chǎn)生一絲影響，因為優(yōu)化目標是最大化幾何間隔的，也就是說縮放分類超平面參數(shù)不會對最終的結(jié)果產(chǎn)生影響，進一步可將幾何間隔化成含有函數(shù)間隔的形式：

由于函數(shù)間隔不受scale的影響，我們指定,則有，即

最終我們得到目標函數(shù)

Algorithm 1.1

綜上，提煉出線性可分情況下 SVM 的學(xué)習(xí)算法，算法1.1：

線性可分 SVM 中到分類超平面的距離為 ?，因為之前我們在不影響結(jié)果的情況下，人為設(shè)定最小函數(shù)間隔，也就是說離超平面最近的點函數(shù)間隔為 1，這些點也就是之后要提到的支持向量support vector。

---

接下來主要講解如何求解算法1.1中的不等式約束二次規(guī)劃問題，二次規(guī)劃是一個凸優(yōu)化問題，求解該問題需要許多最優(yōu)化算法的知識，之前寫過三篇文章，算是 SVM 的基礎(chǔ)，只要這兩篇搞懂，SVM 就是浮云，本節(jié)許多結(jié)論不去細說。均來自之前的博文。

---

拉格朗日乘子法、KKT條件、對偶變換

現(xiàn)在回到之前的優(yōu)化目標，也即原始問題：

這里把不等式約束優(yōu)化寫成了常見的? 的形式，接下來首先構(gòu)造拉格朗日函數(shù)（無約束問題）：

有下式成立：

這個證明在前一篇對偶理論中有講到，稍微再提一嘴，，如果滿足不等式約束則必定有，即只有當(dāng)?shù)臅r候才會不等于0，其它時候都為0，為取到函數(shù)最大。如果了，那么就會取到正無窮大，此時函數(shù)無解，符合題意。

目標函數(shù)化為:

轉(zhuǎn)化為對偶問題：

在SVM中引入對偶的好處為：

• 對偶問題必為凸優(yōu)化問題.；
• 對偶問題是原始問題的下界，當(dāng)滿足一定條件，兩者等價；
• 引入對偶問題之后，可以自然而然的引入核函數(shù)。

滿足KKT條件(這里沒有等式約束)：

故原問題與對偶問題具有強對偶性。原問題的最優(yōu)解與對偶問題的最優(yōu)解相同。

求解KKT條件1有：

將結(jié)果代入對偶函數(shù)中有：

現(xiàn)在大功告成，只要求解對偶問題得到? ，然后根據(jù) KKT 條件得到? ,就可以完美的解得原始問題的最優(yōu)解了，經(jīng)過以上幾步，便得到了最終的線性可分支持向量機學(xué)習(xí)算法，算法1.2：

Algorithm 1.2

---

但Data Mining的書上寫的是先將KKT條件與聯(lián)立，然后采用優(yōu)化算法求解。SMO算法還沒了解過，這兩種方式應(yīng)該都大同小異吧。

---

這里順便明確給出支持向量的定義：根據(jù)KKT條件：

的樣本點即為間隔邊界上的支持向量，且；

對于非支持向量，即，一定有。

至此，關(guān)于線性可分情況下的二分類 SVM 全部推到完成，但是有一個問題：當(dāng)數(shù)據(jù)中存在一些異常值（outlier），去除這些 outlier 后數(shù)據(jù)是線性可分的，這種情況下要引入關(guān)于異常值的處理。

下一篇會講基本線性可分的SVM。

?

參考文章：

支持向量機SVM

總結(jié)

以上是生活随笔為你收集整理的【机器学习】SVM线性可分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。