從零推導支持向量機 (SVM)

　　2019-02-07 22:31計算機/Mac/科技

　　AI 科技評論按，本文作者張皓，目前為南京大學計算機系機器學習與數據挖掘所（LAMDA）碩士生，研究方向為計算機視覺和機器學習，特別是視覺識別和深度學習。

　　個人主頁：http://lamda.nju.edu.cn/zhangh/。該文是其為雷鋒網 AI 科技評論提供的獨家供稿，未經許可禁止轉載。

　　摘要

　　支持向量機 (SVM) 是一個非常經典且高效的分類模型。但是，支持向量機中涉及許多複雜的數學推導，並需要比較強的凸優化基礎，使得有些初學者雖下大量時間和精力研讀，但仍一頭霧水，最終對其望而卻步。本文旨在從零構建支持向量機，涵蓋從思想到形式化，再簡化，最後實現的完整過程，並展現其完整思想脈絡和所有公式推導細節。本文力圖做到邏輯清晰而刪繁就簡，避免引入不必要的概念、記號等。此外，本文並不需要讀者有凸優化的基礎，以減輕讀者的負擔。對於用到的優化技術，在文中均有介紹。

　　儘管現在深度學習十分流行，了解支持向量機的原理，對想法的形式化、簡化，及一步步使模型更一般化的過程，及其具體實現仍然有其研究價值。另一方面，支持向量機仍有其一席之地。相比深度神經網路，支持向量機特別擅長於特徵維數多於樣本數的情況，而小樣本學習至今仍是深度學習的一大難題。

　　1. 線性二分類模型

　　給定一組數據，其中，二分類任務的目標是希望從數據中學得一個假設函數 h: R → {−1,1}，使得 h(xi) =yi，即

　　

　　用一個更簡潔的形式表示是

　　更進一步，線性二分類模型認為假設函數的形式是基於對特徵 xi 的線性組合，即

　　

　　定理 1. 線性二分類模型的目標是找到一組合適的參數 (w, b)，使得

　　即，線性二分類模型希望在特徵空間找到一個劃分超平面，將屬於不同標記的樣本分開。

　　證明.

　　

　　2. 線性支持向量機

　　線性支持向量機 (SVM) [4]也是一種線性二分類模型，也需要找到滿足定理 1 約束的劃分超平面，即 (w, b)。由於能將樣本分開的超平面可能有很多，SVM 進一步希望找到離各樣本都比較遠的劃分超平面。

　　當面對對樣本的隨機擾動時，離各樣本都比較遠的劃分超平面對擾動的容忍能力比較強，即不容易因為樣 本的隨機擾動使樣本穿越到劃分超平面的另外一側而產生分類錯誤。因此，這樣的劃分超平面對樣本比較穩健，不容易過擬合。另一方面，離各樣本都比較遠的劃分超平面不僅可以把正負樣本分開，還可以以比較大的確信度將所有樣本分開，包括難分的樣本，即離劃分超平面近的樣本。

　　2.1 間隔

　　在支持向量機中，我們用間隔 (margin) 刻畫劃分超平面與樣本之間的距離。在引入間隔之前，我們需要 先知道如何計算空間中點到平面的距離。

　　

　　定義 1 (間隔 γ ). 間隔表示距離劃分超平面最近的樣本到劃分超平面距離的兩倍，即

　　也就是說，間隔表示劃分超平面到屬於不同標記的最近樣本的距離之和。

　　定理 3. 線性支持向量機的目標是找到一組合適的參數(w, b)，使得

　　

　　即，線性支持向量機希望在特徵空間找到一個劃分超平面，將屬於不同標記的樣本分開，並且該劃分超平面距離各樣本最遠。

　　證明. 帶入間隔定義即得。

　　2.2 線性支持向量機基本型

　　定理 3 描述的優化問題十分複雜，難以處理。為了能在現實中應用，我們希望能對其做一些簡化，使其變 為可以求解的、經典的凸二次規劃 (QP) 問題。

　　定義 2 (凸二次規劃). 凸二次規劃的優化問題是指目標函數是凸二次函數，約束是線性約束的一類優化問題。

　　

　　由於對 (w, b) 的放縮不影響解，為了簡化優化問題，我們約束 (w, b) 使得

　　

　　

　　推論 6. 線性支持向量機基本型中描述的優化問題屬於二次規劃問題，包括 d + 1 個優化變數，m 項約束。

　　證明. 令

　　

　　代入公式 10 即得。

　　3. 對偶問題

　　現在，我們可以通過調用現成的凸二次規劃軟體包來求解定理 5 描述的優化問題。不過，通過藉助拉格朗 日 (Lagrange) 函數和對偶 (dual) 問題，我們可以將問題更加簡化。

　　3.1 拉格朗日函數與對偶形式

　　構造拉格朗日函數是求解帶約束優化問題的重要方法。

　　

　　證明.

　　

　　推論 8 (KKT 條件). 公式 21 描述的優化問題在最優值處必須滿足如下條件。

　　

　　證明. 由引理 7 可知，u 必須滿足約束，即主問題可行。對偶問題可行是公式 21 描述的優化問題的約束項。αigi(u) = 0 是在主問題和對偶問題都可行的條件下的最大值。

　　定義 4 (對偶問題). 定義公式 19 描述的優化問題的對偶問題為

　　

　　引理 10 (Slater 條件). 當主問題為凸優化問題，即 f 和 gi 為凸函數，hj 為仿射函數，且可行域中至少有一點使不等式約束嚴格成立時，對偶問題等價於原問題。

　　證明. 此證明已超出本文範圍，感興趣的讀者可參考 [2]。

　　

　　3.2 線性支持向量機對偶型

　　線性支持向量機的拉格朗日函數為

　　

　　證明. 因為公式 26 內層對 (w,b) 的優化屬於無約束優化問題，我們可以通過令偏導等於零的方法得到 (w,b)的最優值。

　　

　　將其代入公式 26，消去 (w, b)，即得。

　　推論 13. 線性支持向量機對偶型中描述的優化問題屬於二次規劃問題，包括 m 個優化變數，m + 2 項約束。

　　證明. 令

　　

　　代入公式 10 即得。其中，ei 是第 i 位置元素為 1，其餘位置元素為 0 的單位向量。我們需要通過兩個不等式約束和來得到一個等式約束。

　　3.3 支持向量

　　定理 14 (線性支持向量機的 KKT 條件). 線性支持向量機的 KKT 條件如下。

　　

　　代入引理 8 即得。

　　定義 5 (支持向量). 對偶變數 αi > 0 對應的樣本。

　　引理 15. 線性支持向量機中，支持向量是距離劃分超平面最近的樣本，落在最大間隔邊界上。

　　

　　定理 16. 支持向量機的參數 (w, b) 僅由支持向量決定，與其他樣本無關。

　　證明. 由於對偶變數 αi > 0 對應的樣本是支持向量，

　　

　　其中 SV 代表所有支持向量的集合，b 可以由互補鬆弛算出。對於某一支持向量 xs 及其標記 ys，由於

　　

　　實踐中，為了得到對 b 更穩健的估計，通常使用對所有支持向量求解得到 b 的平均值。

　　推論 17. 線性支持向量機的假設函數可表示為

　　證明. 代入公式 35 即得。

　　4. 核函數

　　至此，我們都是假設訓練樣本是線性可分的。即，存在一個劃分超平面能將屬於不同標記的訓練樣本分開。但在很多任務中，這樣的劃分超平面是不存在的。支持向量機通過核技巧 (kernel trick) 來解決樣本不是線性可分的情況 [1]。

　　4.1 非線性可分問題

　　既然在原始的特徵空間不是線性可分的，支持向量機希望通過一個映射，使得數據在新的空間是線性可分的。

　　引理 18. 當 d 有限時，一定存在，使得樣本在空間中線性可分.

　　證明. 此證明已超出本文範圍，感興趣的讀者可參考計算學習理論中打散 (shatter) 的相應部分 [16]。

　　令 φ(x) 代表將樣本 x 映射到中的特徵向量，參數 w 的維數也要相應變為維，則支持向量機的基本型和對偶型相應變為：

　　

　　其中，基本型對應於+ 1 個優化變數，m 項約束的二次規劃問題；對偶型對應於 m 個優化變數，m + 2 項約束的二次規劃問題。

　　4.2 核技巧

　　注意到，在支持向量機的對偶型中，被映射到高維的特徵向量總是以成對內積的形式存在，即

　　如果先計算特徵在空間的映射，再計算內積，複雜度是。當特徵被映射到非常高維的空間，甚至是無窮維空間時，這將會是沉重的存儲和計算負擔。

　　核技巧旨在將特徵映射和內積這兩步運算壓縮為一步, 並且使複雜度由降為。即，核技巧希望構造一個核函數 κ(xi,xj)，使得，並且 κ(xi,xj) 的計算複雜度是。

　　

　　4.3 核函數選擇

　　通過向高維空間映射及核技巧，我們可以高效地解決樣本非線性可分問題。但面對一個現實任務，我們很 難知道應該具體向什麼樣的高維空間映射，即應該選什麼樣的核函數，而核函數選擇的適合與否直接決定整體的性能。

　　表 1 列出了幾種常用的核函數。通常，當特徵維數 d 超過樣本數 m 時 (文本分類問題通常是這種情況)，使用線性核；當特徵維數 d 比較小，樣本數 m 中等時，使用 RBF 核；當特徵維數 d 比較小，樣本數 m 特別大時，支持向量機性能通常不如深度神經網路。

　　除此之外，用戶還可以根據需要自定義核函數，但需要滿足 Mercer 條件 [5]。

　　

　　反之亦然。

　　新的核函數還可以通過現有核函數的組合得到，使用多個核函數的凸組合是多核學習 [9] 的研究內容。

　　

　　4.4 核方法

　　上述核技巧不僅使用於支持向量機，還適用於一大類問題。

　　

　　即 Φα 比 w 有更小的目標函數值，說明 w 不是最優解，與假設矛盾。因此，最優解必定是樣本的線性組合。

　　此外，原版表示定理適用於任意單調遞增正則項 Ω(w)。此證明已超出本文範圍，感興趣的讀者可參考 [13]。

　　表示定理對損失函數形式沒有限制，這意味著對許多優化問題，最優解都可以寫成樣本的線性組合。更進 一步，將可以寫成核函數的線性組合

　　通過核函數，我們可以將線性模型擴展成非線性模型。這啟發了一系列基於核函數的學習方法，統稱為核方法 [8]。

　　5. 軟間隔

　　不管直接在原特徵空間，還是在映射的高維空間，我們都假設樣本是線性可分的。雖然理論上我們總能找 到一個高維映射使數據線性可分，但在實際任務中，尋找到這樣一個合適的核函數通常很難。此外，由於數據中通常有雜訊存在，一味追求數據線性可分可能會使模型陷入過擬合的泥沼。因此，我們放寬對樣本的要求，即允許有少量樣本分類錯誤。

　　

　　5.1 軟間隔支持向量機基本型

　　我們希望在優化間隔的同時，允許分類錯誤的樣本出現，但這類樣本應儘可能少：

　　

　　其中，是指示函數，C 是個可調節參數，用於權衡優化間隔和少量分類錯誤樣本這兩個目標。但是，指示函數不連續，更不是凸函數，使得優化問題不再是二次規劃問題。所以我們需要對其進行簡化。

　　公式 60 難以實際應用的原因在於指示函數只有兩個離散取值 0/1，對應樣本分類正確/錯誤。為了能使優 化問題繼續保持為二次規劃問題，我們需要引入一個取值為連續值的變數，刻畫樣本滿足約束的程度。我們引入鬆弛變數 (slack variable) ξi，用於度量樣本違背約束的程度。當樣本違背約束的程度越大，鬆弛變數值越大。即，

　　

　　其中，C 是個可調節參數，用於權衡優化間隔和少量樣本違背大間隔約束這兩個目標。當 C 比較大時，我們希望更多的樣本滿足大間隔約束；當 C 比較小時，我們允許有一些樣本不滿足大間隔約束。

　　

　　5.2 軟間隔支持向量機對偶型

　　定理 25 (軟間隔支持向量機對偶型). 軟間隔支持向量機的對偶問題等價於找到一組合適的 α，使得

　　

　　

　　因為內層對 (w, b, ξ) 的優化屬於無約束優化問題，我們可以通過令偏導等於零的方法得到 (w, b, ξ) 的最優值。

　　

　　推論 26. 軟間隔支持向量機對偶型中描述的優化問題屬於二次規劃問題，包括 m 個優化變數，2m+2 項約束。

　　

　　5.3 軟間隔支持向量機的支持向量

　　定理 27 (軟間隔支持向量機的 KKT 條件). 軟間隔支持向量機的 KKT 條件如下.

　　

　　引理 28. 軟間隔支持向量機中，支持向量落在最大間隔邊界，內部，或被錯誤分類的樣本。

　　

　　定理 29. 支持向量機的參數 (w, b) 僅由支持向量決定，與其他樣本無關。

　　證明. 和線性支持向量機證明方式相同。

　　5.4 鉸鏈損失

　　引理 30. 公式 61 等價為

　　

　　

　　其中，第一項稱為經驗風險，度量了模型對訓練數據的擬合程度；第二項稱為結構風險，也稱為正則化項，度量了模型自身的複雜度。正則化項削減了假設空間，從而降低過擬合風險。λ 是個可調節的超參數，用於權衡經驗風險和結構風險。

　　

　　

　　6. 優化方法

　　6.1 SMO

　　如果直接用經典的二次規劃軟體包求解支持向量機對偶型，由於的存儲開銷是，當訓練樣本很多時，這將是一個很大的存儲和計算開銷。序列最小化 (SMO) [10]是一個利用支持 向量機自身特性高效的優化演演算法。SMO 的基本思路是坐標下降。

　　

　　定義 7 (坐標下降). 通過循環使用不同坐標方向，每次固定其他元素，只沿一個坐標方向進行優化，以達到目標函數的局部最小，見演演算法 1.

　　我們希望在支持向量機中的對偶型中，每次固定除 αi 外的其他變數，之後求在 αi 方向上的極值。但由於 約束，當其他變數固定時，αi 也隨著確定。這樣，我們無法在不違背約束的前提下對 αi 進行優化。因此，SMO 每步同時選擇兩個變數 αi 和 αj 進行優化，並固定其他參數，以保證不違背約束。

　　

　　定理 32 (SMO 每步的優化目標). SMO 每步的優化目標為

　　

　　推論 33. SMO 每步的優化目標可等價為對 αi 的單變數二次規劃問題。

　　證明. 由於，我們可以將其代入 SMO 每步的優化目標，以消去變數 αj。此時，優化目標函數是對於 αi 的二次函數，約束是一個取值區間 L ≤ αi ≤ H。之後根據目標函數頂點與區間 [L, H] 的位置關係，可以得到 αi 的最優值。理論上講，每步優化時 αi 和 αj 可以任意選擇，但實踐中通常取 αi 為違背 KKT 條件最大的變數，而 αj取對應樣本與 αi 對應樣本之間間隔最大的變數。對 SMO 演演算法收斂性的測試可以用過檢測是否滿足 KKT 條件得到。

　　6.2 Pegasos

　　我們也可以直接在原問題對支持向量機進行優化，尤其是使用線性核函數時，我們有很高效的優化演演算法，如 Pegasos [14]。Pegasos 使用基於梯度的方法在線性支持向量機基本型

　　進行優化，見演演算法 2。

　　

　　6.3 近似演演算法

　　當使用非線性核函數下的支持向量機時，由於核矩陣，所以時間複雜度一定是，因此，有許多學者致力於研究一些快速的近似演演算法。例如，CVM [15]基於近似最小包圍球演演算法，Nyström 方法[18]通過從 K 採樣出一些列來得到 K 的低秩近似，隨機傅里葉特徵[12]構造了向低維空間的隨機映射。本章介紹了許多優化演演算法，實際上現在已有許多開源軟體包對這些演演算法有很好的實現，目前比較著名的有 LibLinear[7] 和 LibSVM[3]，分別適用於線性和非線性核函數。

　　7. 支持向量機的其他變體

　　ProbSVM. 對數幾率回歸可以估計出樣本屬於正類的概率，而支持向量機只能判斷樣本屬於正類或負類，無法得到概率。ProbSVM[11]先訓練一個支持向量機，得到參數 (w, b)。再令，將當做新的訓練數據訓練一個對數幾率回歸模型，得到參數。因此，ProbSVM 的假設函數為

　　對數幾率回歸模型可以認為是對訓練得到的支持向量機的微調，包括尺度 (對應 θ1) 和平移 (對應 θ0)。通常 θ1 > 0，θ0 ≈ 0。

　　多分類支持向量機. 支持向量機也可以擴展到多分類問題中. 對於 K 分類問題，多分類支持向量機 [17] 有 K 組參數，並希望模型對於屬於正確標記的結果以 1 的間隔高於其他類的結 果，形式化如下

　　

　　

　　References

　　[1] B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Annual Workshop on Computational Learning Theory, pages 144–152, 1992. 5

　　[2] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004. 4

　　[3] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27, 2011. 10

　　[4] C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273–297, 1995. 1 [5] N. Cristianini and J. Shawe-Taylor. An introduction to support vector machines and other kernel-based learning methods. Cambridge University Press, 2000. 6

　　[6] H. Drucker, C. J. Burges, L. Kaufman, A. J. Smola, and V. Vapnik. Support vector regression machines. In Advances in Neural Information Processing Systems, pages 155–161, 1997. 10

　　[7] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9(8):1871–1874, 2008. 10

　　[8] T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learning. The Annals of Statistics, pages 1171–1220, 2008. 6

　　[9] G. R. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5(1):27–72, 2004. 6 [10] J. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Micriosoft Research, 1998. 9

　　[11] J. Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in Large Margin Classifiers, 10(3):61–74, 1999. 10

　　[12] A. Rahimi and B. Recht. Random features for largescale kernel machines. In Advances in Neural Information Processing Systems, pages 1177–1184, 2008. 10

　　[13] B. Scholkopf and A. J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001. 6

　　[14] S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: Primal estimated sub-gradient solver for SVM. Mathematical Programming, 127(1):3–30, 2011. 9

　　[15] I. W. Tsang, J. T. Kwok, and P.-M. Cheung. Core vector machines: Fast SVM training on very large data sets. Journal of Machine Learning Research, 6(4):363– 392, 2005. 10

　　[16] V. Vapnik. The nature of statistical learning theory. Springer Science & Business Media, 2013. 5

　　[17] J. Weston, C. Watkins, et al. Support vector machines for multi-class pattern recognition. In Proceedings of the European Symposium on Artificial Neural Networks, volume 99, pages 219–224, 1999. 10

　　[18] C. K. Williams and M. Seeger. Using the nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems, pages 682–688, 2001. 10

　　[19] 周志華. 機器學習. 清華大學出版社, 2016. 9