?PaperWeekly 原創 ·?作者｜王東偉

單位｜Cubiz

研究方向｜深度學習

本文介紹支持向量機（Support Vector Machine，SVM）。

在上一篇文章關于邏輯回歸的敘述中，我們提到了決策邊界（decision boundary），它實際上是分割 n 維數據點的一個超平面（hyperplane），比如 n=2 時決策邊界為直線，n=3 為平面，n=4 為三維“平面”（有三個維度的超平面）。一般來說，n 維空間的超平面有 n-1 個維度，并且可以把空間分割為兩個部分。

嚴格上，“分割空間”是仿射空間超平面的性質，其他空間類型則未必，更多的細節請參閱 Hyperplane. Wikipedia。

SVM 算法的目標，是找到一個超平面分割不同類別的數據點，并且使得數據點與超平面的最小距離最大。聽起來有些拗口，接下來我們以一個簡單的例子說明，如圖 1 所示，“x”表示正類樣本，“o”表示負類樣本。

顯然，圖 1.2 所示的決策邊界具有更大的“間隔”（margin），通常具有更穩定的分類性能。粗略地說，大間隔分類器對于未知樣本的分類準確率具有更大的均值和更小的方差，比如對于圖 1.1 的決策邊界，未知的正類樣本很大概率會“越過”邊界而被錯誤分類，而圖 1.2 的 決策邊界則給了未知樣本“更大的容錯空間”。

關于如何得到最大間隔的決策邊界，本文后半部分有較嚴格的數學推導，不過現在先以“提出假設、設定誤差函數、求極值點”的思路來理解 SVM 的原理。

對于上述二分類問題，SVM 算法的步驟如下：

假設：

誤差函數：

求 極值點：

其中 C 為常數，暫時無需理會。注意到，SVM 直接給出樣本的分類 y = 1 或者 y = -1，而邏輯回歸是給出 y = 1 的概率。其中：

等價于：

這也正是我們使用 {1, -1} 表示正負類的原因，可以讓 有更簡潔的表達。

支持向量機的幾何意義

接下來，我們將從幾何的角度理解支持向量機。

▲ 圖2

如圖 2， 是分割正負類樣本的直線。A 點為正類樣本（即），坐標為 ，AB 為垂線段， 為 A 到直線的距離。不難證明向量 垂直于直線。由于 ，并且 （因為 為單位向量），得到點 B 的坐標：

點 B 位于直線上，即：

整理得到：

同理，對于負類樣本可以得到：

進一步得到：

需要指出的是，以上推導基于樣本是線性可分的情況（即存在一條線性邊界可以完美區分兩類數據點），其他情況稍后探討。

回到誤差函數。我們把它分成兩部分：

觀察 表達式，對于正類樣本，如果我們希望 ，只需滿足，即 ；對于負類樣本同樣可以得到 時，。

注意到，對于任意一條以 100% 正確率分割正負類樣本的直線 ，等比縮放 和 仍然得到同一條直線，意味著我們可以任意調節 ，使得對于任意樣本都有 ，即 。因此，如果我們暫時忽略 ，僅僅讓 取得極小值，我們可以得到無數條符合條件的決策邊界。

▲ 圖3

圖 3 顯示了其中三條滿足 取極小值的決策邊界。

現在同時讓 取得極小值。注意到 ，即我們需要保持 的同時，讓 盡可能小。因為 表示數據點到直線的距離，事實上我們只需關注距離直線最近的點，令 ，則優化目標為（再次強調，僅對于線性可分的情況）：

我們來看幾個直觀的例子：

顯然，圖 4.3 的 值最大，意味著在保證 的條件下， 可以取得極小值，也就是誤差函數取得極小值，于是，最小化誤差函數將使我們得到一個最大間隔的決策邊界。事實上， 取得極小值將使得 ，并且圖 4.3 虛線上的點都滿足 ，這些點我們稱之為“支持向量”（support vectors）！

異常值處理

我們現在對 已經有了更多的了解， 的目的是盡可能區分正負類樣本，并且一旦能完全正確地分割樣本它就“滿足”了，因此對于線性可分的數據樣本，通常它將得到無數條決策邊界。同時優化 ，我們將從 得到的“候選邊界”中選擇一條“最佳邊界”（最大間距的決策邊界）。但是，假如 對所有“候選邊界”都不滿意怎么辦？

考慮圖 5 的樣本分布，如果我們再次忽略 ，僅讓 取得極小值，得到的“候選邊界”將位于一個狹窄的區域，圖 5 顯示了其中一條。

▲ 圖5

圖 5 中的 H 點為異常值（outlier）。顯然，我們希望決策邊界可以盡可能抵御異常值的干擾，回到最優的位置。事實上， 的加入將有效處理異常值問題，我們看它是怎么做到的。

假設 H 點為樣本 ， 表示為：

圖 6.1 的決策邊界將使 ，即 取極小值，但是由于最小距離 非常小，最小化整體誤差將使得 很大，即 增大；反之，圖 6.2 的決策邊界則使得 減小，從而 減小，與此同時， 增大將使得 增大。因此，同時優化 將得到一條介于兩者之間的決策邊界。一種具體的情況是，如果樣本很多，那么 對 的影響很小，異常值將幾乎被忽略，這正是我們希望的結果。

上述 對異常值處理的“效果”，我們通常稱之為“正則化”（regularization），它可以避免模型“過擬合”（overfitting），相對的概念還有“欠擬合”（underfitting），后續文章將繼續探討。

現在我們可以說明常數 C 的作用，讓我們再看一眼完整的誤差函數：

假設 C 取一個很大的值，比如 1000000，則后半部分 產生的影響將很小（或者說 ) 的影響很大），于是也就無法起到正則化的作用，會導致過擬合；反之 C 取值很小，則容易欠擬合。

此外，帶有正則化項（即）的 ，我們通常稱之為目標函數（objective function）而不是誤差函數（loss function），并且更通用的符號表示是 ，不過本文暫時采用誤差函數的表達。

非線性SVM

考慮以下正負類樣本，如何找到決策邊界？

▲ 圖7

我們目前所了解的 SVM 只能擬合線性邊界，非線性邊界需要對模型做一些“改裝”。

具體操作非常簡單。假設樣本特征數量為 n，數據樣本數量為 m，對于任意特定的數據樣本 ，可以得到 與所有數據樣本 的“相似度”（similarity）：

也就是說，對于每一個樣本 （n 維），我們都可以得到相應的 （m 維）。

即為核函數（kernel function），通常我們采用高斯核（Gaussian kernel）：

對于不采用核函數的 SVM，我們通常說它用了線性核（linear kernel）。

通過將 替換為 ，我們可以得到核函數版本的 SVM 模型和誤差函數：

關于極值點求解及核函數

為了說明極值點求解及核函數的原理，我們需要做一些看起來有些嚇人的數學推導，由于篇幅有限，我將對一些關鍵的數學原理做簡要說明，更詳細的推導可參考斯坦福 CS 課程的資料 CS229 Lecture Notes. Andrew Ng. Spring Stanford University. 2020。

之前我們得到了一個優化問題：

其中：

容易得到，上述優化問題等價于：

注意到，我們還沒有考慮正則化，比如圖 6.2 所示的邊界是不被允許的，因為 H 點不滿足 的約束條件（而 ）。

因此，考慮到正則化和非線性可分的情況，我們將優化問題調整為：

現在你可以驗證，假設 H 點對應?，對于合適的?，圖 6.2 所示的邊界將被允許，但是 H 點將帶來 （類比 ）的誤差值提升作為“懲罰”。事實上，上述優化問題等價于優化 SVM 的誤差函數 。

以上為帶約束的優化問題（constrained optimization problems）。其中一個解決思路是，找到優化問題 D，使得由 D 得到的解，可以得到原問題 P 的解。P 和 D 分別稱為 primal problem 和 dual problem（以下翻譯為原始問題和對偶問題）。關于 Duality 的嚴格定義，請參考 Duality(optimization). Wikipedia。

通常我們使用拉格朗日對偶（Lagrange duality）來求解。

對于一般化的帶約束的優化問題 ，

求解步驟如下：

找到該優化問題的替代問題 （跟 有相同的解）；

得到對偶問題 ；

求解 得到 的解。

定義拉格朗日函數如下：

考慮以下函數：

給定一個 值，如果 滿足約束 ，可以得到：

如果 不滿足約束，可以得到 （讀者可自行驗證）。

即：

因此我們得到以下優化問題 ：

容易驗證 與 有相同的解。

進一步，得到對偶問題 ：

注意到，對偶問題的約束僅有 ，且 ，因此更容易求解。

可以證明：

以下用一個簡單的例子說明上述不等式。假如 在 上處處連續，，。固定 ，則對于任意 ，都有 ，即 ；固定 ，則對于任意 ，都有 ，即 ，因此，。在滿足一定條件下，，比如馬鞍形函數。

現在我們的目標是找到 使得 ，而 是否存在涉及兩個條件：Slater's condition 和 Karush–Kuhn–Tucker conditions（以下簡稱斯萊特條件和 KTT 條件）。

斯萊特條件。對于以下優化問題：

當 和 為凸函數（convex），并且存在 使得：

則其滿足強對偶性（strong duality）。

滿足強對偶性的優化問題，其原始問題和對偶問題的最優解對應的目標函數值相等，即 。

對于如 所示形式的優化問題，KTT 條件如下：

對于 所示形式的優化問題，如果其滿足強對偶性（比如滿足斯萊特條件），以及相應的拉格朗日函數 關于 為嚴格凸函數，那么可以證明：

(1) 如果存在 是對偶問題的解，則 是原始問題的解；

(2) 和 分別為原始問題和對偶問題的解 滿足 KTT 條件。

結論（1）告訴我們，可以通過求解對偶問題得到原始問題的解。結論（2）則提供了極值點的判斷依據。注意到 KKT 條件（2），它意味著當 時，，這將讓 SVM 的優化結果得到少數的“支持向量”，下文將進一步說明。

我們可以對結論（1）作簡單證明。

對于滿足強對偶性的問題，令 和 分別為原始問題和對偶問題的解，可以得到：

即：

也就是說， 是 的極小值點，如果 是嚴格凸函數，則極小值點是唯一的。

以上，容易得到結論（1）。

現在，回到 SVM 的優化問題：

把上述約束條件轉化為 的形式，注意到該優化問題有 2m 個 的約束，并且沒有 的約束，我們可以得到拉格朗日函數：

于是，得到對偶問題：

對于 ，我們需要固定，令偏導數為零：

由以上方程可以得到 關于 的表達式，代入 ，可以得到對偶問題的最終表達式：

其中， 表示內積。求解上述問題可以采用基于梯度的迭代算法，并用 KTT 條件判斷目標函數值是否收斂。SMO 是目前比較流行且高效的 SVM 優化算法，詳情請參閱 SMO 的論文 Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. John C. Platt. Microsoft Research. 1998。

現在，假設我們得到了對偶問題的極值點 ，在推導對偶問題表達式的過程，注意到：

可以得到決策邊界的另一種表達式：

事實上，最終得到的 只有一小部分非零，這些非零的 對應的 就是支持向量。因此，我們的預測模型只需要計算 與少數支持向量的內積。

核函數

假如我們需要對樣本進行特征組合，得到更高維的樣本，比如進行如下特征映射：

注意到前文得到的對偶優化問題和預測模型都可以表示為 的函數，我們只需將 替換為 。一般地， 為特征映射，我們定義核函數為：

以特征數量 n=3 為例，考慮以下核函數：

可以看到上述核函數隱性地把 ,映射到高維向量 ，因此我們無需分別計算 ，這將減小計算復雜度，比如上述例子從 減小為 。

一個常用的核函數是：

我們稱之為 RBF 核（Radial basis function kernel）或高斯核（Gaussian kernel）。通過泰勒展開可以得到 σ=1 的 RBF：

可以看到 RBF 實際上將 x 映射到無限維空間。

從另一個角度看待核函數。容易發現，RBF 的取值跟 的距離成負相關，值域為 ，當 時取最大值 ，因此 RBF 也可以視為 的相似度（similarity）表示。

關于 σ 的作用。從相似度的角度理解核函數的作用，可以發現我們實際上通過計算輸入 與所有訓練樣本的相似度來確定它的所屬分類，最終我們會發現只需用到其中的部分訓練樣本就可以判斷 的分類，這是支持向量的另一個理解角度。σ 是高斯函數的標準差，它決定了訓練樣本的影響范圍，比如當 σ 很小時，由于影響范圍極小，導致我們幾乎需要用所有訓練樣本來確定 的分類，因此得到的支持向量的數量會很大。因此，太小的 σ 值會導致過擬合，太大會導致欠擬合。

在一些機器學習的工具庫中，RBF 通常表示為：

即 σ ，因此有：

大的 或小的 σ，容易導致過擬合，即低偏差、高方差；小的 或大的 σ，容易導致欠擬合，即高偏差、低方差。

參考文獻

[1] CS229 Lecture Notes. Andrew Ng. Stanford University. Spring 2020.

[2] Karush-Kuhn-Tucker conditions. Geoff Gordon. CMU.?

[3] Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. John C. Platt. Microsoft Research. 1998.

[4] The Simplified SMO Algorithm. Stanford University. 2009.

[5]Duality(optimization). Wikipedia.?

[6] Hyperplane. Wikipedia.?

[7] Karush–Kuhn–Tucker conditions. Wikipedia.?

[8] Support Vector Machine. Wikipedia?

[9] Lagrange multiplier, Wikipedia.?

[10] Radial basis function kernel. Wikipedia.?

[11] Slater's condition. Wikipedia?

更多閱讀

#投 稿?通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

?????投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的一文详解支持向量机（SVM）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。