0
| 本文作者： AI科技評(píng)論 | 編輯：汪思穎 | 2019-02-07 21:54 |
雷鋒網(wǎng) AI 科技評(píng)論按，本文作者張皓，目前為南京大學(xué)計(jì)算機(jī)系機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘所（LAMDA）碩士生，研究方向?yàn)橛?jì)算機(jī)視覺(jué)和機(jī)器學(xué)習(xí)，特別是視覺(jué)識(shí)別和深度學(xué)習(xí)。
個(gè)人主頁(yè)：http://lamda.nju.edu.cn/zhangh/。該文為其給雷鋒網(wǎng) AI 科技評(píng)論的獨(dú)家供稿，未經(jīng)許可禁止轉(zhuǎn)載。
摘要
支持向量機(jī) (SVM) 是一個(gè)非常經(jīng)典且高效的分類(lèi)模型。但是，支持向量機(jī)中涉及許多復(fù)雜的數(shù)學(xué)推導(dǎo)，并需要比較強(qiáng)的凸優(yōu)化基礎(chǔ)，使得有些初學(xué)者雖下大量時(shí)間和精力研讀，但仍一頭霧水，最終對(duì)其望而卻步。本文旨在從零構(gòu)建支持向量機(jī)，涵蓋從思想到形式化，再簡(jiǎn)化，最后實(shí)現(xiàn)的完整過(guò)程，并展現(xiàn)其完整思想脈絡(luò)和所有公式推導(dǎo)細(xì)節(jié)。本文力圖做到邏輯清晰而刪繁就簡(jiǎn)，避免引入不必要的概念、記號(hào)等。此外，本文并不需要讀者有凸優(yōu)化的基礎(chǔ)，以減輕讀者的負(fù)擔(dān)。對(duì)于用到的優(yōu)化技術(shù)，在文中均有介紹。
盡管現(xiàn)在深度學(xué)習(xí)十分流行，了解支持向量機(jī)的原理，對(duì)想法的形式化、簡(jiǎn)化，及一步步使模型更一般化的過(guò)程，及其具體實(shí)現(xiàn)仍然有其研究?jī)r(jià)值。另一方面，支持向量機(jī)仍有其一席之地。相比深度神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)特別擅長(zhǎng)于特征維數(shù)多于樣本數(shù)的情況，而小樣本學(xué)習(xí)至今仍是深度學(xué)習(xí)的一大難題。
1. 線性二分類(lèi)模型
給定一組數(shù)據(jù)
，其中
，二分類(lèi)任務(wù)的目標(biāo)是希望從數(shù)據(jù)中學(xué)得一個(gè)假設(shè)函數(shù) h: R → {?1,1}，使得 h(xi) =yi，即
用一個(gè)更簡(jiǎn)潔的形式表示是
更進(jìn)一步，線性二分類(lèi)模型認(rèn)為假設(shè)函數(shù)的形式是基于對(duì)特征 xi 的線性組合，即
定理 1. 線性二分類(lèi)模型的目標(biāo)是找到一組合適的參數(shù) (w, b)，使得
即，線性二分類(lèi)模型希望在特征空間找到一個(gè)劃分超平面，將屬于不同標(biāo)記的樣本分開(kāi)。
證明.
2. 線性支持向量機(jī)
線性支持向量機(jī) (SVM) [4]也是一種線性二分類(lèi)模型，也需要找到滿(mǎn)足定理 1 約束的劃分超平面，即 (w, b)。由于能將樣本分開(kāi)的超平面可能有很多，SVM 進(jìn)一步希望找到離各樣本都比較遠(yuǎn)的劃分超平面。
當(dāng)面對(duì)對(duì)樣本的隨機(jī)擾動(dòng)時(shí)，離各樣本都比較遠(yuǎn)的劃分超平面對(duì)擾動(dòng)的容忍能力比較強(qiáng)，即不容易因?yàn)闃? 本的隨機(jī)擾動(dòng)使樣本穿越到劃分超平面的另外一側(cè)而產(chǎn)生分類(lèi)錯(cuò)誤。因此，這樣的劃分超平面對(duì)樣本比較穩(wěn)健，不容易過(guò)擬合。另一方面，離各樣本都比較遠(yuǎn)的劃分超平面不僅可以把正負(fù)樣本分開(kāi)，還可以以比較大的確信度將所有樣本分開(kāi)，包括難分的樣本，即離劃分超平面近的樣本。
2.1 間隔
在支持向量機(jī)中，我們用間隔 (margin) 刻畫(huà)劃分超平面與樣本之間的距離。在引入間隔之前，我們需要 先知道如何計(jì)算空間中點(diǎn)到平面的距離。
定義 1 (間隔 γ ). 間隔表示距離劃分超平面最近的樣本到劃分超平面距離的兩倍，即
也就是說(shuō)，間隔表示劃分超平面到屬于不同標(biāo)記的最近樣本的距離之和。
定理 3. 線性支持向量機(jī)的目標(biāo)是找到一組合適的參數(shù)(w, b)，使得
即，線性支持向量機(jī)希望在特征空間找到一個(gè)劃分超平面，將屬于不同標(biāo)記的樣本分開(kāi)，并且該劃分超平面距離各樣本最遠(yuǎn)。
證明. 帶入間隔定義即得。
2.2 線性支持向量機(jī)基本型
定理 3 描述的優(yōu)化問(wèn)題十分復(fù)雜，難以處理。為了能在現(xiàn)實(shí)中應(yīng)用，我們希望能對(duì)其做一些簡(jiǎn)化，使其變 為可以求解的、經(jīng)典的凸二次規(guī)劃 (QP) 問(wèn)題。
定義 2 (凸二次規(guī)劃). 凸二次規(guī)劃的優(yōu)化問(wèn)題是指目標(biāo)函數(shù)是凸二次函數(shù)，約束是線性約束的一類(lèi)優(yōu)化問(wèn)題。
由于對(duì) (w, b) 的放縮不影響解，為了簡(jiǎn)化優(yōu)化問(wèn)題，我們約束 (w, b) 使得
推論 6. 線性支持向量機(jī)基本型中描述的優(yōu)化問(wèn)題屬于二次規(guī)劃問(wèn)題，包括 d + 1 個(gè)優(yōu)化變量，m 項(xiàng)約束。
證明. 令
代入公式 10 即得。
3. 對(duì)偶問(wèn)題
現(xiàn)在，我們可以通過(guò)調(diào)用現(xiàn)成的凸二次規(guī)劃軟件包來(lái)求解定理 5 描述的優(yōu)化問(wèn)題。不過(guò)，通過(guò)借助拉格朗
日 (Lagrange) 函數(shù)和對(duì)偶 (dual) 問(wèn)題，我們可以將問(wèn)題更加簡(jiǎn)化。
3.1 拉格朗日函數(shù)與對(duì)偶形式
構(gòu)造拉格朗日函數(shù)是求解帶約束優(yōu)化問(wèn)題的重要方法。
證明.
推論 8 (KKT 條件). 公式 21 描述的優(yōu)化問(wèn)題在最優(yōu)值處必須滿(mǎn)足如下條件。
證明. 由引理 7 可知，u 必須滿(mǎn)足約束，即主問(wèn)題可行。對(duì)偶問(wèn)題可行是公式 21 描述的優(yōu)化問(wèn)題的約束項(xiàng)。αigi(u) = 0 是在主問(wèn)題和對(duì)偶問(wèn)題都可行的條件下的最大值。
定義 4 (對(duì)偶問(wèn)題). 定義公式 19 描述的優(yōu)化問(wèn)題的對(duì)偶問(wèn)題為
引理 10 (Slater 條件). 當(dāng)主問(wèn)題為凸優(yōu)化問(wèn)題，即 f 和 gi 為凸函數(shù)，hj 為仿射函數(shù)，且可行域中至少有一點(diǎn)使不等式約束嚴(yán)格成立時(shí)，對(duì)偶問(wèn)題等價(jià)于原問(wèn)題。
證明. 此證明已超出本文范圍，感興趣的讀者可參考 [2]。
3.2 線性支持向量機(jī)對(duì)偶型
線性支持向量機(jī)的拉格朗日函數(shù)為
證明. 因?yàn)楣?26 內(nèi)層對(duì) (w,b) 的優(yōu)化屬于無(wú)約束優(yōu)化問(wèn)題，我們可以通過(guò)令偏導(dǎo)等于零的方法得到 (w,b)的最優(yōu)值。
將其代入公式 26，消去 (w, b)，即得。
推論 13. 線性支持向量機(jī)對(duì)偶型中描述的優(yōu)化問(wèn)題屬于二次規(guī)劃問(wèn)題，包括 m 個(gè)優(yōu)化變量，m + 2 項(xiàng)約束。
證明. 令
代入公式 10 即得。其中，ei 是第 i 位置元素為 1，其余位置元素為 0 的單位向量。我們需要通過(guò)兩個(gè)不等式約束
和
來(lái)得到一個(gè)等式約束。
3.3 支持向量
定理 14 (線性支持向量機(jī)的 KKT 條件). 線性支持向量機(jī)的 KKT 條件如下。
代入引理 8 即得。
定義 5 (支持向量). 對(duì)偶變量 αi > 0 對(duì)應(yīng)的樣本。
引理 15. 線性支持向量機(jī)中，支持向量是距離劃分超平面最近的樣本，落在最大間隔邊界上。
定理 16. 支持向量機(jī)的參數(shù) (w, b) 僅由支持向量決定，與其他樣本無(wú)關(guān)。
證明. 由于對(duì)偶變量 αi > 0 對(duì)應(yīng)的樣本是支持向量，
其中 SV 代表所有支持向量的集合，b 可以由互補(bǔ)松弛算出。對(duì)于某一支持向量 xs 及其標(biāo)記 ys，由于
實(shí)踐中，為了得到對(duì) b 更穩(wěn)健的估計(jì)，通常使用對(duì)所有支持向量求解得到 b 的平均值。
推論 17. 線性支持向量機(jī)的假設(shè)函數(shù)可表示為
證明. 代入公式 35 即得。
4. 核函數(shù)
至此，我們都是假設(shè)訓(xùn)練樣本是線性可分的。即，存在一個(gè)劃分超平面能將屬于不同標(biāo)記的訓(xùn)練樣本分開(kāi)。但在很多任務(wù)中，這樣的劃分超平面是不存在的。支持向量機(jī)通過(guò)核技巧 (kernel trick) 來(lái)解決樣本不是線性可分的情況 [1]。
4.1 非線性可分問(wèn)題
既然在原始的特征空間
不是線性可分的，支持向量機(jī)希望通過(guò)一個(gè)映射
，使得數(shù)據(jù)在新的空間
是線性可分的。
引理 18. 當(dāng) d 有限時(shí)，一定存在
，使得樣本在空間中線性可分.
證明. 此證明已超出本文范圍，感興趣的讀者可參考計(jì)算學(xué)習(xí)理論中打散 (shatter) 的相應(yīng)部分 [16]。
令 φ(x) 代表將樣本 x 映射到中的特征向量，參數(shù) w 的維數(shù)也要相應(yīng)變?yōu)?img alt="從零推導(dǎo)支持向量機(jī) (SVM)" src="https://static.leiphone.com/uploads/new/images/20190207/5c5c3064dee3d.png?imageView2/2/w/740"/>維，則支持向量機(jī)的基本型和對(duì)偶型相應(yīng)變?yōu)椋?/p>
其中，基本型對(duì)應(yīng)于
+ 1 個(gè)優(yōu)化變量，m 項(xiàng)約束的二次規(guī)劃問(wèn)題；對(duì)偶型對(duì)應(yīng)于 m 個(gè)優(yōu)化變量，m + 2 項(xiàng)約束的二次規(guī)劃問(wèn)題。
4.2 核技巧
注意到，在支持向量機(jī)的對(duì)偶型中，被映射到高維的特征向量總是以成對(duì)內(nèi)積的形式存在，即
如果先計(jì)算特征在空間的映射，再計(jì)算內(nèi)積，復(fù)雜度是
。當(dāng)特征被映射到非常高維的空間，甚至是無(wú)窮維空間時(shí)，這將會(huì)是沉重的存儲(chǔ)和計(jì)算負(fù)擔(dān)。
核技巧旨在將特征映射和內(nèi)積這兩步運(yùn)算壓縮為一步, 并且使復(fù)雜度由降為
。即，核技巧希望構(gòu)造一個(gè)核函數(shù) κ(xi,xj)，使得
，并且 κ(xi,xj) 的計(jì)算復(fù)雜度是。
4.3 核函數(shù)選擇
通過(guò)向高維空間映射及核技巧，我們可以高效地解決樣本非線性可分問(wèn)題。但面對(duì)一個(gè)現(xiàn)實(shí)任務(wù)，我們很 難知道應(yīng)該具體向什么樣的高維空間映射，即應(yīng)該選什么樣的核函數(shù)，而核函數(shù)選擇的適合與否直接決定整體的性能。
表 1 列出了幾種常用的核函數(shù)。通常，當(dāng)特征維數(shù) d 超過(guò)樣本數(shù) m 時(shí) (文本分類(lèi)問(wèn)題通常是這種情況)，使用線性核；當(dāng)特征維數(shù) d 比較小，樣本數(shù) m 中等時(shí)，使用 RBF 核；當(dāng)特征維數(shù) d 比較小，樣本數(shù) m 特別大時(shí)，支持向量機(jī)性能通常不如深度神經(jīng)網(wǎng)絡(luò)。
除此之外，用戶(hù)還可以根據(jù)需要自定義核函數(shù)，但需要滿(mǎn)足 Mercer 條件 [5]。
反之亦然。
新的核函數(shù)還可以通過(guò)現(xiàn)有核函數(shù)的組合得到，使用多個(gè)核函數(shù)的凸組合是多核學(xué)習(xí) [9] 的研究?jī)?nèi)容。
4.4 核方法
上述核技巧不僅使用于支持向量機(jī)，還適用于一大類(lèi)問(wèn)題。
即 Φα 比 w 有更小的目標(biāo)函數(shù)值，說(shuō)明 w 不是最優(yōu)解，與假設(shè)矛盾。因此，最優(yōu)解必定是樣本的線性組合。
此外，原版表示定理適用于任意單調(diào)遞增正則項(xiàng) Ω(w)。此證明已超出本文范圍，感興趣的讀者可參考 [13]。
表示定理對(duì)損失函數(shù)形式?jīng)]有限制，這意味著對(duì)許多優(yōu)化問(wèn)題，最優(yōu)解都可以寫(xiě)成樣本的線性組合。更進(jìn)
一步，
將可以寫(xiě)成核函數(shù)的線性組合
通過(guò)核函數(shù)，我們可以將線性模型擴(kuò)展成非線性模型。這啟發(fā)了一系列基于核函數(shù)的學(xué)習(xí)方法，統(tǒng)稱(chēng)為核方法 [8]。
5. 軟間隔
不管直接在原特征空間，還是在映射的高維空間，我們都假設(shè)樣本是線性可分的。雖然理論上我們總能找 到一個(gè)高維映射使數(shù)據(jù)線性可分，但在實(shí)際任務(wù)中，尋找到這樣一個(gè)合適的核函數(shù)通常很難。此外，由于數(shù)據(jù)中通常有噪聲存在，一味追求數(shù)據(jù)線性可分可能會(huì)使模型陷入過(guò)擬合的泥沼。因此，我們放寬對(duì)樣本的要求，即允許有少量樣本分類(lèi)錯(cuò)誤。
5.1 軟間隔支持向量機(jī)基本型
我們希望在優(yōu)化間隔的同時(shí)，允許分類(lèi)錯(cuò)誤的樣本出現(xiàn)，但這類(lèi)樣本應(yīng)盡可能少：
其中，
是指示函數(shù)，C 是個(gè)可調(diào)節(jié)參數(shù)，用于權(quán)衡優(yōu)化間隔和少量分類(lèi)錯(cuò)誤樣本這兩個(gè)目標(biāo)。但是，指示函數(shù)不連續(xù)，更不是凸函數(shù)，使得優(yōu)化問(wèn)題不再是二次規(guī)劃問(wèn)題。所以我們需要對(duì)其進(jìn)行簡(jiǎn)化。
公式 60 難以實(shí)際應(yīng)用的原因在于指示函數(shù)只有兩個(gè)離散取值 0/1，對(duì)應(yīng)樣本分類(lèi)正確/錯(cuò)誤。為了能使優(yōu) 化問(wèn)題繼續(xù)保持為二次規(guī)劃問(wèn)題，我們需要引入一個(gè)取值為連續(xù)值的變量，刻畫(huà)樣本滿(mǎn)足約束的程度。我們引入松弛變量 (slack variable) ξi，用于度量樣本違背約束的程度。當(dāng)樣本違背約束的程度越大，松弛變量值越大。即，
其中，C 是個(gè)可調(diào)節(jié)參數(shù)，用于權(quán)衡優(yōu)化間隔和少量樣本違背大間隔約束這兩個(gè)目標(biāo)。當(dāng) C 比較大時(shí)，我們希望更多的樣本滿(mǎn)足大間隔約束；當(dāng) C 比較小時(shí)，我們?cè)试S有一些樣本不滿(mǎn)足大間隔約束。
5.2 軟間隔支持向量機(jī)對(duì)偶型
定理 25 (軟間隔支持向量機(jī)對(duì)偶型). 軟間隔支持向量機(jī)的對(duì)偶問(wèn)題等價(jià)于找到一組合適的 α，使得
因?yàn)閮?nèi)層對(duì) (w, b, ξ) 的優(yōu)化屬于無(wú)約束優(yōu)化問(wèn)題，我們可以通過(guò)令偏導(dǎo)等于零的方法得到 (w, b, ξ) 的最優(yōu)值。
推論 26. 軟間隔支持向量機(jī)對(duì)偶型中描述的優(yōu)化問(wèn)題屬于二次規(guī)劃問(wèn)題，包括 m 個(gè)優(yōu)化變量，2m+2 項(xiàng)約束。
5.3 軟間隔支持向量機(jī)的支持向量
定理 27 (軟間隔支持向量機(jī)的 KKT 條件). 軟間隔支持向量機(jī)的 KKT 條件如下.
引理 28. 軟間隔支持向量機(jī)中，支持向量落在最大間隔邊界，內(nèi)部，或被錯(cuò)誤分類(lèi)的樣本。
定理 29. 支持向量機(jī)的參數(shù) (w, b) 僅由支持向量決定，與其他樣本無(wú)關(guān)。
證明. 和線性支持向量機(jī)證明方式相同。
5.4 鉸鏈損失
引理 30. 公式 61 等價(jià)為
其中，第一項(xiàng)稱(chēng)為經(jīng)驗(yàn)風(fēng)險(xiǎn)，度量了模型對(duì)訓(xùn)練數(shù)據(jù)的擬合程度；第二項(xiàng)稱(chēng)為結(jié)構(gòu)風(fēng)險(xiǎn)，也稱(chēng)為正則化項(xiàng)，度量了模型自身的復(fù)雜度。正則化項(xiàng)削減了假設(shè)空間，從而降低過(guò)擬合風(fēng)險(xiǎn)。λ 是個(gè)可調(diào)節(jié)的超參數(shù)，用于權(quán)衡經(jīng)驗(yàn)風(fēng)險(xiǎn)和結(jié)構(gòu)風(fēng)險(xiǎn)。
6. 優(yōu)化方法
6.1 SMO
如果直接用經(jīng)典的二次規(guī)劃軟件包求解支持向量機(jī)對(duì)偶型，由于
的存儲(chǔ)開(kāi)銷(xiāo)是
，當(dāng)訓(xùn)練樣本很多時(shí)，這將是一個(gè)很大的存儲(chǔ)和計(jì)算開(kāi)銷(xiāo)。序列最小化 (SMO) [10]是一個(gè)利用支持
向量機(jī)自身特性高效的優(yōu)化算法。SMO 的基本思路是坐標(biāo)下降。
定義 7 (坐標(biāo)下降). 通過(guò)循環(huán)使用不同坐標(biāo)方向，每次固定其他元素，只沿一個(gè)坐標(biāo)方向進(jìn)行優(yōu)化，以達(dá)到目標(biāo)函數(shù)的局部最小，見(jiàn)算法 1.
我們希望在支持向量機(jī)中的對(duì)偶型中，每次固定除
αi 外的其他變量，之后求在 αi 方向上的極值。但由于
約束
，當(dāng)其他變量固定時(shí)，αi 也隨著確定。這樣，我們無(wú)法在不違背約束的前提下對(duì) αi 進(jìn)行優(yōu)化。因此，SMO 每步同時(shí)選擇兩個(gè)變量 αi 和 αj 進(jìn)行優(yōu)化，并固定其他參數(shù)，以保證不違背約束。
定理 32 (SMO 每步的優(yōu)化目標(biāo)). SMO 每步的優(yōu)化目標(biāo)為
推論 33. SMO 每步的優(yōu)化目標(biāo)可等價(jià)為對(duì) αi 的單變量二次規(guī)劃問(wèn)題。
證明. 由于
，我們可以將其代入 SMO
每步的優(yōu)化目標(biāo)，以消去變量 αj。此時(shí)，優(yōu)化目標(biāo)函數(shù)是對(duì)于 αi 的二次函數(shù)，約束是一個(gè)取值區(qū)間 L ≤ αi ≤
H。之后根據(jù)目標(biāo)函數(shù)頂點(diǎn)與區(qū)間 [L, H] 的位置關(guān)系，可以得到 αi 的最優(yōu)值。理論上講，每步優(yōu)化時(shí) αi 和 αj 可以任意選擇，但實(shí)踐中通常取 αi 為違背 KKT 條件最大的變量，而 αj取對(duì)應(yīng)樣本與 αi 對(duì)應(yīng)樣本之間間隔最大的變量。對(duì)
SMO 算法收斂性的測(cè)試可以用過(guò)檢測(cè)是否滿(mǎn)足 KKT
條件得到。
6.2 Pegasos
我們也可以直接在原問(wèn)題對(duì)支持向量機(jī)進(jìn)行優(yōu)化，尤其是使用線性核函數(shù)時(shí)，我們有很高效的優(yōu)化算法，如 Pegasos [14]。Pegasos 使用基于梯度的方法在線性支持向量機(jī)基本型
進(jìn)行優(yōu)化，見(jiàn)算法 2。
6.3 近似算法
當(dāng)使用非線性核函數(shù)下的支持向量機(jī)時(shí)，由于核矩陣
，所以時(shí)間復(fù)雜度一定是
，因此，有許多學(xué)者致力于研究一些快速的近似算法。例如，CVM [15]基于近似最小包圍球算法，Nystr?m 方法[18]通過(guò)從 K 采樣出一些列來(lái)得到 K
的低秩近似，隨機(jī)傅里葉特征[12]構(gòu)造了向低維空間的隨機(jī)映射。本章介紹了許多優(yōu)化算法，實(shí)際上現(xiàn)在已有許多開(kāi)源軟件包對(duì)這些算法有很好的實(shí)現(xiàn)，目前比較著名的有
LibLinear[7] 和 LibSVM[3]，分別適用于線性和非線性核函數(shù)。
7. 支持向量機(jī)的其他變體
ProbSVM. 對(duì)數(shù)幾率回歸可以估計(jì)出樣本屬于正類(lèi)的概率，而支持向量機(jī)只能判斷樣本屬于正類(lèi)或負(fù)類(lèi)，無(wú)法得到概率。ProbSVM[11]先訓(xùn)練一個(gè)支持向量機(jī)，得到參數(shù) (w, b)。再令
，將
當(dāng)做新的訓(xùn)練數(shù)據(jù)訓(xùn)練一個(gè)對(duì)數(shù)幾率回歸模型，得到參數(shù)
。因此，ProbSVM
的假設(shè)函數(shù)為
對(duì)數(shù)幾率回歸模型可以認(rèn)為是對(duì)訓(xùn)練得到的支持向量機(jī)的微調(diào)，包括尺度 (對(duì)應(yīng) θ1) 和平移 (對(duì)應(yīng) θ0)。通常 θ1 > 0，θ0 ≈ 0。
多分類(lèi)支持向量機(jī). 支持向量機(jī)也可以擴(kuò)展到多分類(lèi)問(wèn)題中. 對(duì)于 K 分類(lèi)問(wèn)題，多分類(lèi)支持向量機(jī) [17] 有 K
組參數(shù)
，并希望模型對(duì)于屬于正確標(biāo)記的結(jié)果以 1 的間隔高于其他類(lèi)的結(jié)
果，形式化如下
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] 周志華. 機(jī)器學(xué)習(xí). 清華大學(xué)出版社, 2016. 9
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。
