-
支持向量機
鎖定
支持向量機(Support Vector Machine, SVM)是一類按監督學習(supervised learning)方式對數據進行二元分類的廣義線性分類器(generalized linear classifier),其決策邊界是對學習樣本求解的最大邊距超平面(maximum-margin hyperplane)
[1-3]
。
SVM使用鉸鏈損失函數(hinge loss)計算經驗風險(empirical risk)並在求解系統中加入了正則化項以優化結構風險(structural risk),是一個具有稀疏性和穩健性的分類器
[2]
。SVM可以通過核方法(kernel method)進行非線性分類,是常見的核學習(kernel learning)方法之一
[4]
。
- 中文名
- 支持向量機
- 外文名
- Support Vector Machine, SVM
- 類 型
- 機器學習算法
支持向量機歷史
SVM是由模式識別中廣義肖像算法(generalized portrait algorithm)發展而來的分類器
[8]
,其早期工作來自前蘇聯學者Vladimir N. Vapnik和Alexander Y. Lerner在1963年發表的研究
[9]
。1964年,Vapnik和Alexey Y. Chervonenkis對廣義肖像算法進行了進一步討論並建立了硬邊距的線性SVM
[7]
。此後在二十世紀70-80年代,隨着模式識別中最大邊距決策邊界的理論研究
[10]
、基於鬆弛變量(slack variable)的規劃問題求解技術的出現
[11]
,和VC維(Vapnik-Chervonenkis dimension, VC dimension)的提出
[12]
,SVM被逐步理論化併成為統計學習理論的一部分
[1]
。1992年,Bernhard E. Boser、Isabelle M. Guyon和Vapnik通過核方法得到了非線性SVM
[13]
。1995年,Corinna Cortes和Vapnik提出了軟邊距的非線性SVM並將其應用於手寫字符識別問題
[14]
,這份研究在發表後得到了關注和引用,為SVM在各領域的應用提供了參考。
支持向量機理論
支持向量機線性分類
在分類問題中給定輸入數據和學習目標:
,其中輸入數據的每個樣本都包含多個特徵並由此構成特徵空間(feature space):
,而學習目標為二元變量
表示負類(negative class)和正類(positive class)。
若輸入數據所在的特徵空間存在作為決策邊界(decision boundary)的超平面將學習目標按正類和負類分開,並使任意樣本的點到平面距離大於等於1
[2]
:
則稱該分類問題具有線性可分性,參數
分別為超平面的法向量和截距。
滿足該條件的決策邊界實際上構造了2個平行的超平面作為間隔邊界以判別樣本的分類:
在一個分類問題不具有線性可分性時,使用超平面作為決策邊界會帶來分類損失,即部分支持向量不再位於間隔邊界上,而是進入了間隔邊界內部,或落入決策邊界的錯誤一側。損失函數可以對分類損失進行量化,其按數學意義可以得到的形式是0-1損失函數:
經驗風險(empirical risk)與結構風險(structural risk)
參見:統計學習理論
支持向量機核方法
主條目:核方法
一些線性不可分的問題可能是非線性可分的,即特徵空間存在超曲面(hypersurface)將正類和負類分開。使用非線性函數可以將非線性可分問題從原始的特徵空間映射至更高維的希爾伯特空間(Hilbert space)
,從而轉化為線性可分問題,此時作為決策邊界的超平面表示如下
[2]
[3]
:
Mercer定理(Mercer's theorem)
常見的核函數
在構造核函數後,驗證其對輸入空間內的任意格拉姆矩陣為半正定矩陣是困難的,因此通常的選擇是使用現成的核函數
[3]
。以下給出一些核函數的例子,其中未做説明的參數均是該核函數的超參數(hyper-parameter)
[2]
:
名稱 | 解析式 |
---|---|
多項式核(polynomial kernel) | |
徑向基函數核(RBF kernel) | |
拉普拉斯核(Laplacian kernel) | |
Sigmoid核(Sigmoid kernel) |
當多項式核的階為1時,其被稱為線性核,對應的非線性分類器退化為線性分類器。RBF核也被稱為高斯核(Gaussian kernel),其對應的映射函數將樣本空間映射至無限維空間。核函數的線性組合和笛卡爾積也是核函數,此外對特徵空間內的函數
,
也是核函數
[2]
。
支持向量機算法
支持向量機標準算法
線性SVM(linear SVM)
1. 硬邊距(hard margin)
給定輸入數據和學習目標:
,硬邊界SVM是在線性可分問題中求解最大邊距超平面(maximum-margin hyperplane)的算法,約束條件是樣本點到決策邊界的距離大於等於1。硬邊界SVM可以轉化為一個等價的二次凸優化(quadratic convex optimization)問題進行求解
[3]
[2]
:
2. 軟邊距(soft margin)
在線性不可分問題中使用硬邊距SVM將產生分類誤差,因此可在最大化邊距的基礎上引入損失函數構造新的優化問題。SVM使用鉸鏈損失函數,沿用硬邊界SVM的優化問題形式,軟邊距SVM的優化問題有如下表示:
由上述KKT條件可知,對任意樣本
,總有
或
,對前者,該樣本不會對決策邊界
產生影響,對後者,該樣本滿足
意味其處於間隔邊界上(
)、間隔內部(
)或被錯誤分類(
),即該樣本是支持向量。由此可見,軟邊距SVM決策邊界的確定僅與支持向量有關,使用鉸鏈損失函數使得SVM具有稀疏性
[2]
。
非線性SVM(nonlinear SVM)
數值求解
1. 內點法(Interior Point Method, IPM)
以軟邊距SVM為例,IPM使用對數阻擋函數(logarithmic barrier function)將SVM的對偶問題由極大值問題轉化為極小值問題並將其優化目標和約束條件近似表示為如下形式
[18-19]
:
IPM在計算
時需要對N階矩陣求逆,在使用牛頓迭代法時也需要計算Hessian矩陣的逆,是一個內存開銷大且複雜度為
的算法,僅適用於少量學習樣本的情形
[19]
[20]
。一些研究通過低秩近似(low-rank approximation)和並行計算提出了更適用於大數據的IPM,並在SVM的實際學習中進行了應用和比較
[19]
[20]
[21]
。
2. 序列最小優化(Sequential Minimal Optimization, SMO)
SMO是一種座標下降法(coordinate descent),以迭代方式求解SVM的對偶問題,其設計是在每個迭代步選擇拉格朗日乘子中的兩個變量
並固定其它參數,將原優化問題化簡至1維子可行域(feasible subspace),此時約束條件有如下等價形式
[22]
:
- 初始所有化拉格朗日乘子;
- 識別一個不滿足KKT條件的乘子,並求解其二次規劃問題;
- 反覆執行上述步驟直到所有乘子滿足KKT條件或參數的更新量小於設定值。
可以證明,在二次凸優化問題中,SMO的每步迭代都嚴格地優化了SVM的對偶問題,且迭代會在有限步後收斂於全局極大值
[23]
。SMO算法的迭代速度與所選取乘子對KKT條件的偏離程度有關,因此SMO通常採用啓發式方法選取拉格朗日乘子
[24]
。
3. 隨機梯度下降(Stochastic Gradient Descent, SGD)
編程實現
這裏提供一個python 3環境下使用scikit-learn封裝模塊的SVM編程實現:
# 導入模塊 import numpy as np import matplotlib.pyplot as plt from sklearn import svm, datasets % matplotlib inline # 鳶尾花數據 iris = datasets.load_iris() X = iris.data[:, :2] # 為便於繪圖僅選擇2個特徵 y = iris.target # 測試樣本(繪製分類區域) xlist1 = np.linspace(X[:, 0].min(), X[:, 0].max(), 200) xlist2 = np.linspace(X[:, 1].min(), X[:, 1].max(), 200) XGrid1, XGrid2 = np.meshgrid(xlist1, xlist2) # 非線性SVM:RBF核,超參數為0.5,正則化係數為1,SMO迭代精度1e-5, 內存佔用1000MB svc = svm.SVC(kernel='rbf', C=1, gamma=0.5, tol=1e-5, cache_size=1000).fit(X, y) # 預測並繪製結果 Z = svc.predict(np.vstack([XGrid1.ravel(), XGrid2.ravel()]).T) Z = Z.reshape(XGrid1.shape) plt.contourf(XGrid1, XGrid2, Z, cmap=plt.cm.hsv) plt.contour(XGrid1, XGrid2, Z, colors=('k',)) plt.scatter(X[:, 0], X[:, 1], c=y, edgecolors='k', linewidth=1.5, cmap=plt.cm.hsv)
支持向量機改進算法
偏斜數據的改進算法
概率SVM(Platt's probabilistic outputs)
概率SVM可以視為Logistic迴歸和SVM的結合,SVM由決策邊界直接輸出樣本的分類,概率SVM則通過Sigmoid函數計算樣本屬於其類別的概率
[27]
。具體地,在計算標準SVM得到學習樣本的決策邊界後,概率SVM通過縮放和平移參數
對決策邊界進行線性變換,並使用極大似然估計(Maximum Liklihood Estimation, MLE)得到
的值,將樣本到線性變換後超平面的距離作為Sigmoid函數的輸入得到概率
[27]
。在通過標準SVM求解決策邊界後,概率SVM的改進可表示如下
[27]
:
多分類SVM(multiple class SVM)
標準SVM是基於二元分類問題設計的算法,無法直接處理多分類問題。利用標準SVM的計算流程有序地構建多個決策邊界以實現樣本的多分類,通常的實現為“一對多(one-against-all)”和“一對一(one-against-one)”
[29]
。一對多SVM對m個分類建立m個決策邊界,每個決策邊界判定一個分類對其餘所有分類的歸屬;一對一SVM是一種投票法(voting),其計算流程是對m個分類中的任意2個建立決策邊界,即共有
個決策邊界,樣本的類別按其對所有決策邊界的判別結果中得分最高的類別選取
[29]
。一對多SVM通過對標準SVM的優化問題進行修改可以實現一次迭代計算所有決策邊界
[29]
。
最小二乘SVM(Least Square SVM, LS-SVM)
LS-SVM是標準SVM的一種變體,兩者的差別是LS-SVM沒有使用鉸鏈損失函數,而是將其優化問題改寫為類似於嶺迴歸(ridge regression)的形式,對軟邊距SVM,LS-SVM的優化問題如下
[30]
:
結構化SVM(structured SVM)
結構化SVM是標準SVM在處理結構化預測(structured prediction)問題時所得到的推廣,給定樣本空間和標籤空間的結構化數據
和標籤空間內的距離函數
,其優化問題如下:
多核SVM(multiple kernel SVM)
多核SVM是多核學習(multiple kernel learning)在監督學習中的實現,是在標準的非線性SVM中將單個核函數替換為核函數族(kernel family)的改進算法。多核SVM的構建方法可以被歸納為以下5類
[36]
:
- 顯式規則(fixed rule):在不加入任何超參數的情形下使用核函數的性質,例如線性可加性構建核函數族。顯示規則構建的多核SVM可以直接使用標準SVM的方法進行求解。
- 啓發式方法(heuristic approach):使用包含參數的組合函數構建核函數族,參數按參與構建的單個核函數的核矩陣或分類表現確定。
- 優化方法(optimization approach):使用包含參數的組合函數構建核函數族,參數按核函數間的相似性或最小化結構風險或所得到的優化問題求解。
- 貝葉斯方法(Bayesian approach):使用包含參數的組合函數構建核函數族,參數被視為隨機變量並按貝葉斯推斷方法進行估計。
- 提升方法(Boosting approach):按迭代方式不斷在核函數族中加入核函數直到多核SVM的分類表現不再提升為止。
研究表明,從分類的準確性而言,多核SVM具有更高的靈活性,在總體上也優於使用其核函數族中某個單核計算的標準SVM,但非線性和依賴於樣本的核函數族構建方法不總是更優的。核函數族的構建通常依具體問題而定
[36]
。
支持向量機擴展算法
支持向量迴歸(Support Vector Regression, SVR)
將SVM由分類問題推廣至迴歸問題可以得到支持向量迴歸(Support Vector Regression, SVR),此時SVM的標準算法也被稱為支持向量分類(Support Vector Classification, SVC)
[2]
[37]
。SVC中的超平面決策邊界是SVR的迴歸模型:
。SVR具有稀疏性,若樣本點與迴歸模型足夠接近,即落入迴歸模型的間隔邊界內,則該樣本不計算損失,對應的損失函數被稱為ε-不敏感損失函數(ε-insensitive loss):
,其中
是決定間隔邊界寬度的超參數
[2]
。可知,不敏感損失函數與SVC使用的鉸鏈損失函數相似,在原點附近的部分取值被固定為0。類比軟邊距SVM,SVR是如下形式的二次凸優化問題
[37]
:
支持向量聚類(support vector clustering)
支持向量聚類是一類非參數的聚類算法,是SVM在聚類問題中的推廣。具體地,支持向量聚類首先使用核函數,通常是徑向基函數核,將樣本映射至高維空間,隨後使用SVDD(Support Vector Domain Description)算法得到一個閉合超曲面作為高維空間中樣本點富集區域的刻畫。最後,支持向量聚類將該曲面映射回原特徵空間 ,得到一系列閉合等值線,每個等值線內部的樣本會被賦予一個類別
[39]
。
支持向量聚類不要求預先給定聚類個數,研究表明,支持向量聚類在低維學習樣本的聚類中有穩定表現,高維樣本通過其它降維(dimensionality reduction)方法進行預處理後也可進行支持向量聚類
[39]
[40]
。
半監督SVM(Semi-Supervised SVM, S3VM)
S3VM是SVM在半監督學習中的應用,可以應用於少量標籤數據和大量無標籤數據組成的學習樣本。在不考慮未標記樣本時,SVM會求解最大邊距超平面,在考慮無標籤數據後,S3VM會依據低密度分隔(low density separation)假設求解能將兩類標籤樣本分開,且穿過無標籤數據低密度區域的劃分超平面。
支持向量機性質
穩健性與稀疏性:SVM的優化問題同時考慮了經驗風險和結構風險最小化,因此具有穩定性。從幾何觀點,SVM的穩定性體現在其構建超平面決策邊界時要求邊距最大,因此間隔邊界之間有充裕的空間包容測試樣本
[2]
。SVM使用鉸鏈損失函數作為代理損失,鉸鏈損失函數的取值特點使SVM具有稀疏性,即其決策邊界僅由支持向量決定,其餘的樣本點不參與經驗風險最小化
[2]
。在使用核方法的非線性學習中,SVM的穩健性和稀疏性在確保了可靠求解結果的同時降低了核矩陣的計算量和內存開銷。
與其它線性分類器的關係:SVM是一個廣義線性分類器,通過在SVM的算法框架下修改損失函數和優化問題可以得到其它類型的線性分類器,例如將SVM的損失函數替換為logistic損失函數就得到了接近於logistic迴歸的優化問題
[2]
。SVM和logistic迴歸是功能相近的分類器,二者的區別在於logistic迴歸的輸出具有概率意義,也容易擴展至多分類問題,而SVM的稀疏性和穩定性使其具有良好的泛化能力並在使用核方法時計算量更小
[44]
。
作為核方法的性質:SVM不是唯一可以使用核技巧的機器學習算法,logistic迴歸、嶺迴歸和線性判別分析(Linear DiscriminantAnalysis, LDA)也可通過核方法得到核logistic迴歸(kernel logistic regression)、核嶺迴歸(kernel ridge regression)和核線性判別分析(Kernelized LDA, KLDA)方法。因此SVM是廣義上核學習的實現之一
[4]
。
支持向量機應用
包含SVM的編程模塊
按引用次數,由台灣大學資訊工程研究所開發的LIBSVM是使用最廣的SVM工具
[28]
。LIBSVM包含標準SVM算法、概率輸出、支持向量迴歸、多分類SVM等功能,其源代碼由C編寫,並有JAVA、Python、R、MATLAB等語言的調用接口、基於CUDA的GPU加速和其它功能性組件,例如多核並行計算、模型交叉驗證等
[47-48]
。
基於Python開發的機器學習模塊scikit-learn提供預封裝的SVM工具,其設計參考了LIBSVM
[49]
。其它包含SVM的Python模塊有MDP
[50]
、MLPy
[51]
、PyMVPA
[52]
等。TensorFlow的高階API組件Estimators有提供SVM的封裝模型
[53]
。
- 參考資料
-
- 1. Vapnik, V..Statistical learning theory. 1998 (Vol. 3). .New York, NY:Wiley,1998:Chapter 10-11, pp.401-492
- 2. 周志華.機器學習.北京:清華大學出版社,2016:pp.121-139, 298-300
- 3. 李航.統計學習方法.北京:清華大學出版社,2012:第七章,pp.95-135
- 4. Hsieh, W.W..Machine learning methods in the environmental sciences: Neural networks and kernels:Cambridge university press,2009:Chapter 7, pp.157-169
- 5. Qin, J. and He, Z.S., 2005, August. A SVM face recognition method based on Gabor-featured key points. In Machine Learning and Cybernetics, 2005. Proceedings of 2005 International Conference on (Vol. 8, pp. 5144-5149). IEEE.
- 6. Sun, A., Lim, E.P. and Ng, W.K., 2002, November. Web classification using support vector machine. In Proceedings of the 4th international workshop on Web information and data management (pp. 96-99). ACM.
- 7. Vapnik, V. and Chervonenkis, A., 1964. A note on class of perceptron. Automation and Remote Control, 24.
- 8. Support Vector Machines - History .svms.org[引用日期2019-01-06]
- 9. Vapnik, V.N. and Lerner, A.Y., 1963. Recognition of patterns with help of generalized portraits. Avtomat. i Telemekh, 24(6), pp.774-780.
- 10. Cover, T.M., 1965. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions on electronic computers, (3), pp.326-334.
- 11. Smith, F.W., 1968. Pattern classifier design by linear programming. IEEE Transactions on Computers, 100(4), pp.367-372.
- 12. Vapnik, V.N. and Chervonenkis, A.Y., 2015. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity (pp. 11-30). Springer, Cham.
- 13. Boser, B.E., Guyon, I.M. and Vapnik, V.N., 1992, July. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory (pp. 144-152). ACM.
- 14. Cortes, C. and Vapnik, V., 1995. Support-vector networks. Machine learning, 20(3), pp.273-297.
- 15. Zhang, T., 2004. Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics, pp.56-85.
- 16. Tikhonov, A.N., 1943. On the stability of inverse problems. In Dokl. Akad. Nauk SSSR (Vol. 39, pp. 195-198).
- 17. Friedman, J., Hastie, T. and Tibshirani, R..The elements of statistical learning (Vol. 1, No. 10).New York, NY:Springer,2001:Chapter 12, pp.417-438
- 18. Gondzio, J., Using interior point methods for optimization in training very large scale Support Vector Machines .School of Mathematics, University of Edinburgh .2009[引用日期2019-01-02]
- 19. Woodsend, K., 2009. Using interior point methods for large-scale support vector machine training. Doctor of Philosophy Thesis. University of Edinburgh.
- 20. Fine, S. and Scheinberg, K., 2001. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2(Dec), pp.243-264.
- 21. Ferris, M.C. and Munson, T.S., 2002. Interior-point methods for massive support vector machines. SIAM Journal on Optimization, 13(3), pp.783-804.
- 22. Platt, J., 1998. Sequential minimal optimization: A fast algorithm for training support vector machines.
- 23. Osuna, E., Freund, R. and Girosi, F., 1997, September. An improved training algorithm for support vector machines. In Neural Networks for Signal Processing [1997] VII. Proceedings of the 1997 IEEE Workshop (pp. 276-285). IEEE.
- 24. Platt, J.C., 1999. 12 fast training of support vector machines using sequential minimal optimization. Advances in kernel methods, pp.185-208.
- 25. Bottou, L., 2010. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010 (pp. 177-186). Physica-Verlag HD.
- 26. Ben-Hur, A. and Weston, J., 2010. A user’s guide to support vector machines. In Data mining techniques for the life sciences (pp. 223-239). Humana Press.
- 27. Platt, J., 1999. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3), pp.61-74.
- 28. Chang, C.C. and Lin, C.J., 2011. LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3), p.27.
- 29. Hsu, C.W. and Lin, C.J., 2002. A comparison of methods for multiclass support vector machines. IEEE transactions on Neural Networks, 13(2), pp.415-425.
- 30. Suykens, J.A. and Vandewalle, J., 1999. Least squares support vector machine classifiers. Neural processing letters, 9(3), pp.293-300.
- 31. Chu, W., Ong, C.J. and Keerthi, S.S., 2002. A note on least squares support vector machines. Technical Report, CD-02–09.
- 32. Wang, H. and Hu, D., 2005, October. Comparison of SVM and LS-SVM for regression. In Neural Networks and Brain, 2005. ICNN&B'05. International Conference on (Vol. 1, pp. 279-283). IEEE.
- 33. Ye, J. and Xiong, T., 2007, March. Svm versus least squares svm. In Artificial Intelligence and Statistics (pp. 644-651).
- 34. Nguyen, L.M., Shimazu, A. and Phan, X.H., 2006, July. Semantic parsing with structured SVM ensemble classification models. In Proceedings of the COLING/ACL on Main conference poster sessions (pp. 619-626). Association for Computational Linguistics.
- 35. Guo, J., Chen, H., Sun, Z. and Lin, Y., 2004. A novel method for protein secondary structure prediction using dual‐layer SVM and profiles. PROTEINS: Structure, Function, and Bioinformatics, 54(4), pp.738-743.
- 36. Gönen, M. and Alpaydın, E., 2011. Multiple kernel learning algorithms. Journal of machine learning research, 12(Jul), pp.2211-2268.
- 37. Smola, A.J. and Schölkopf, B., 2004. A tutorial on support vector regression. Statistics and computing, 14(3), pp.199-222.
- 38. Support vector clustering - Asa Ben-Hur .Scholarpedia and Brain Corporation.2008-2-28[引用日期2019-04-18]
- 39. Ben-Hur, A., Horn, D., Siegelmann, H.T. and Vapnik, V., 2001. Support vector clustering. Journal of machine learning research, 2(Dec), pp.125-137.
- 40. Roberts, S.J., 1997. Parametric and non-parametric unsupervised cluster analysis. Pattern Recognition, 30(2), pp.261-272.
- 41. Bennett, K.P. and Demiriz, A., 1999. Semi-supervised support vector machines. In Advances in Neural Information processing systems (pp. 368-374).
- 42. Joachims, T., 1999, June. Transductive inference for text classification using support vector machines. In ICML (Vol. 99, pp. 200-209).
- 43. Li, Y.F., Kwok, J.T. and Zhou, Z.H., 2009, June. Semi-supervised learning using label mean. In Proceedings of the 26th Annual International Conference on Machine Learning (pp. 633-640). ACM.
- 44. Swersky, K., Support Vector Machines vs Logistic Regression. In CSC2515 .Department of Computer Science, University of Toronto.2014[引用日期2019-01-06]
- 45. Bahlmann, C., Haasdonk, B. and Burkhardt, H., 2002. Online handwriting recognition with support vector machines-a kernel approach. In Frontiers in handwriting recognition, 2002. proceedings. eighth international workshop on (pp. 49-54). IEEE.
- 46. Byvatov, E. and Schneider, G., 2003. Support vector machine applications in bioinformatics. Applied bioinformatics, 2(2), pp.67-77.
- 47. Chang, C.-C. and Lin, C.-J., LIBSVM -- A Library for Support Vector Machines .國立台灣大學,資訊工程研究所.2018[引用日期2019-01-06]
- 48. LIBSVM Tools .國立台灣大學,資訊工程研究所.2018-10-31[引用日期2019-01-06]
- 49. scikt-learn: Support Vector Machines .scikit-learn.org.2018[引用日期2019-01-06]
- 50. Modular Toolkit for Data Processing - Node List .MDP.2016-03-08[引用日期2019-01-06]
- 51. mlpy v3.4.0 documentation: Support Vector Machines (SVMs) .MLPy.2011[引用日期2019-01-06]
- 52. PyMVPA User Manual - mvpa2.clfs.svm .PyMVPA.2016[引用日期2019-01-06]
- 53. TensorFlow - tf.contrib.learn.SVM .TensorFlow.2018-11-20[引用日期2019-01-06]
- 收起