作者：石川

摘要：這篇文章深入淺出的為你講解監(jiān)督分類算法的一大利器：支持向量機(jī)。

1 引言

支持向量機(jī)（support vector machines，SVM）是我最早接觸的監(jiān)督分類算法之一。早在 MIT 修統(tǒng)計學(xué)的時候，我用它做過一個舊金山灣區(qū)上班族通勤模式的分類研究，但當(dāng)時只是很粗淺的認(rèn)識。后來由于工作的關(guān)系又非常系統(tǒng)的學(xué)習(xí)了一下，這其中包括認(rèn)真學(xué)習(xí)了斯坦福 Andrew Ng（吳恩達(dá)）的機(jī)器學(xué)習(xí)課（吳講的真的非常好，深入淺出），參閱了大量的關(guān)于 SVM 的理論和實(shí)際應(yīng)用的文獻(xiàn)，以及和美國的一些機(jī)器學(xué)習(xí)領(lǐng)域?qū)＜医粨Q想法，這些使我在判斷是否要采用 SVM 解決量化投資中的問題時逐漸變得游刃有余。

對于監(jiān)督分類算法的表現(xiàn)，業(yè)界常用大概 10 種不同的指標(biāo)來評判，包括 Accuracy，LIFT，F(xiàn)-Score，ROC，Precision / Recall Break-Even Point，Root Mean Squared Error 等。無論以哪種準(zhǔn)確性的評價指標(biāo)來看，SVM 的效果都不輸于人工神經(jīng)網(wǎng)絡(luò) ANN 或者高級的集合算法如隨機(jī)森林。SVM 的另一個特點(diǎn)是其自身可以在一定程度上防止過擬合，這對于其在量化投資上的應(yīng)用格外重要。這是因?yàn)槿魏稳斯ぶ悄芩惴ㄓ行У那疤崾牵?strong style="box-sizing: border-box;">歷史樣本和未來樣本是來自同一個（未知）的整體，滿足同分布。只有這樣，基于歷史樣本學(xué)習(xí)出來的規(guī)律才會在未來繼續(xù)有效。但是對于金融數(shù)據(jù)來說，這個假設(shè)在很多問題上無法滿足。因此，如果機(jī)器學(xué)習(xí)算法在歷史數(shù)據(jù)上過擬合的話，那么基本可以肯定這個模型對未來的數(shù)據(jù)毫無作用。

鑒于我對 SVM 的鐘愛，我很早以前就打算寫一篇介紹它的短文，作為對知識的一個梳理。不過后來，我讀了一篇來自 quantstart.com 的文章，名為 Support Vector Machines: A Guide for Beginners。作者并沒有使用大量的數(shù)學(xué)公式，而是用精煉的語言和恰如其分的圖例對 SVM 的基本原理進(jìn)行了闡述。平心而論，讓我自己憋幾天也不一定能寫的比人家更清晰和生動，因此今天不如就索性把這篇文章大致翻譯過來，作為對 SVM 的一個介紹。我會跳過一些不影響理解的文字、對原文的結(jié)構(gòu)做一些改動，并在一些地方加入自己的理解。對那些閱讀英語比閱讀中文更舒服的小伙伴，也不妨看看原文。

2 初識 SVM

支持向量機(jī)解決的是監(jiān)督的二元分類問題（supervised binary classification）：

垃圾郵件識別就是這么一個例子：一個郵件要么屬于垃圾郵件，要么屬于非垃圾郵件。對于一封新郵件，我們希望機(jī)器學(xué)習(xí)算法自動對它分類。為此，我們首先通過人工對大量的歷史郵件進(jìn)行?spam?或?non-spam?標(biāo)識，然后用這些標(biāo)識后的歷史郵件對機(jī)器學(xué)習(xí)算法進(jìn)行訓(xùn)練。

在處理這類分類問題時，SVM 的作用對象是樣本的特征空間（feature space），它是一個有限維度的向量空間，每個維度對應(yīng)著樣本的一個特征，而這些特征組合起來可以很好的描述被分類的樣本。比如在上面的垃圾郵件識別例子中，一些可以有效辨別 spam 和 non-spam 郵件的詞匯就構(gòu)成了特征空間。

為了對新的樣本分類，SVM 算法會根據(jù)歷史數(shù)據(jù)在特征空間內(nèi)構(gòu)建一個超平面（hyperplane）；它將特征空間線性分割為兩個部分，對應(yīng)著分類問題的兩類，分別位于超平面的兩側(cè)。構(gòu)建超平面的過程就是模型訓(xùn)練過程。對于一個給定的新樣本，根據(jù)它的特征值，它會被放在超平面兩側(cè)中的某一側(cè)，這便完成了分類。不難看出，SVM 是一個非概率的線性分類器。這是因?yàn)?SVM 模型回答的是非此即彼的問題，新樣本會被確定的分到兩類中的某一類。

在數(shù)學(xué)上表達(dá)上，每一個歷史樣本點(diǎn)由一個 (x, y) 元組表示，其中粗體的?x?是特征向量，即?x?= (x_1, …, x_p)，其中每一個 x_j?代表樣本的一個特征，而 y 代表該樣本的已知分類（通常用 +1 和 -1 表示兩個不同的類）。SVM 會根據(jù)這些給定的歷史數(shù)據(jù)來訓(xùn)練算法的參數(shù)，找到最優(yōu)的線性超平面。理想情況下，這個超平面可以將兩類樣本點(diǎn)完美的分開（即沒有錯分的情況）。對于給定的訓(xùn)練數(shù)據(jù)，可以將它們完美分開的超平面很可能不是唯一的，比如一個超平面稍微旋轉(zhuǎn)一個角度便得到一個仍然能夠完美分割的超平面。在眾多的能夠?qū)崿F(xiàn)分類的超平面中，只有一個是最優(yōu)的。我們會在下文介紹這個“最優(yōu)”的定義。

在實(shí)際應(yīng)用中，很多數(shù)據(jù)并非是線性可分的。SVM 的強(qiáng)大之處在于它不僅僅局限于是一個高維空間的線性分類器。它通過非線性的核函數(shù)（kernel functions）把原始的特征空間映射到更高維的特征空間（可以是無限維的），在高維空間中再將這些樣本點(diǎn)線性分割。高維空間的線性分割對應(yīng)著原始特征空間的非線性分割，因此在原始特征空間中生成了非線性的決策邊界。此外，這么做并不以增加計算機(jī)的計算負(fù)擔(dān)為代價。因此 SVM 相當(dāng)高效。

下面，我們會解釋如何找到最優(yōu)的線性超平面?；谒鲎畲箝g隔分類器（maximal margin classifier）的概念。通過實(shí)例，我們會發(fā)現(xiàn)最大間隔分類器有時無法滿足實(shí)際問題，這是因?yàn)椴煌愋偷臉颖军c(diǎn)錯綜的交織在一起，讓它們無法被完美分割。為了解決這個問題，我們必須允許分類器故意的錯誤劃分一些點(diǎn)，從而得到對整體樣本總體分類效果的最優(yōu)，這便引出了支持向量分類器（support vector classifier）。最后，我們介紹核函數(shù)的概念。支持向量分類器結(jié)合核函數(shù)便得到了支持向量機(jī)。最后，我們總結(jié)?SVM 的優(yōu)缺點(diǎn)。

3 線性超平面

線性超平面是 SVM 的核心。對于一個 p 維空間，超平面是一個 p-1 維的物體，它將這個 p 維空間一分為二。下圖分別是 2 維和 3 維特征空間中超平面的例子。在 2 維特征空間中，超平面就是一條 1 維的直線，在 3 維特征空間中，超平面是一個 2 維的平面。（注意，我們并不要求超平面一定要通過特征空間的原點(diǎn)。）

對于一個 p 維的特征空間?x?= (x_1, …, x_p)，我們可以通過下面這個式子來定義一個超平面：

如果用向量和內(nèi)積來表達(dá)，這個式子變?yōu)?b?x?+ b_0?= 0。任何滿足這個式子的向量?x?都落在這個 p-1 維超平面上。該超平面將 p 維特征空間分為兩個區(qū)域，如下圖所示（示意圖，假設(shè) p = 2，兩個顏色代表特征空間中兩個不同的區(qū)域）：

如果一個向量?x?滿足?b?x?+ b_0?> 0，則它會落在超平面上方的區(qū)域；如果一個向量?x?滿足?b?x?+ b_0?< 0，則它會落在超平面下方的區(qū)域。通過判斷?b?x?+ b_0?的符號，就可以對?x?分類。

4 分類問題

在郵件識別的例子中，假設(shè)我們有 n 個歷史郵件，每一封都被標(biāo)識為 spam（+1）或者 non-spam（-1）。每一封郵件中都有一些詞被選為關(guān)鍵詞。所有這 n 封郵件中不重復(fù)的關(guān)鍵詞就組成了我們的特征。假設(shè)不重復(fù)的關(guān)鍵詞一共有 p 個。

如果將上面這個問題用數(shù)學(xué)語言轉(zhuǎn)化為分類問題，則我們有 n 個訓(xùn)練樣本，每一個樣本都是一個 p 維的特征向量?x_i。此外，每一個訓(xùn)練樣本都有一個已知的分類 y_i（例如 spam 或者 non-spam）。因此，我們有 n 對訓(xùn)練樣本 (x_i, y_i)。分類器將通過學(xué)習(xí)這些訓(xùn)練樣本來優(yōu)化自身的參數(shù)，得到最終的分類模型。我們使用測試樣本來檢查分類器的分類效果。

讓我們來看一個簡化的例子?？紤] 2 維特征空間并假設(shè)訓(xùn)練樣本都是完美可分的（如下圖所示）。圖中，紅色和藍(lán)色代表了兩類不同的樣本點(diǎn)。三天虛線表示三個不同的超平面；它們都可以將這些點(diǎn)完美分開。

在這個例子中，這三條線都可以將特征空間一分為二。然而，我們?nèi)绾未_定哪條線才是最優(yōu)的呢？直觀上說，無論是（1）還是（3），都離某些紅色和藍(lán)色的樣本點(diǎn)太近了，給我們的感覺是這兩條線僅是“將將”把這些點(diǎn)分開；而位于中間的（2）號虛線離任何紅色的和藍(lán)色的點(diǎn)都比較遠(yuǎn)，給我們的感覺是它非常清晰地將這些點(diǎn)區(qū)分開了。因此，如果從這三條里面選的話，（2）號虛線應(yīng)該是最好的選擇。在數(shù)學(xué)上，上述直觀感受被精確的翻譯為數(shù)學(xué)優(yōu)化方程，即最大間隔超平面。

5 最大間隔超平面

在上一節(jié)中，我們看到能夠?qū)崿F(xiàn)分類的超平面可能不唯一。在這種情況下我們需要找到最優(yōu)的。對于一個給定的超平面，我們可以計算每個樣本點(diǎn)到該平面的距離，這些距離中最小的一個就是這個超平面的間隔距離（margin）。因此，對于每一個超平面我們可以計算出它的?margin。所有可行的超平面中，margin 最大的那個就是我們要找的最優(yōu)超平面，即最大間隔超平面（maximal margin hyperplane）。使用該超平面進(jìn)行分類的分類器就稱為最大間隔分類器。

考慮下面這個 2 維特征空間示意圖。圖中有紅色和藍(lán)色兩類樣本點(diǎn)。黑色的實(shí)線就是最大間隔超平面。在這個例子中，A，B，C 三個點(diǎn)到該超平面的距離相等。注意，這些點(diǎn)非常特別，這是因?yàn)槌矫娴膮?shù)完全由這三個點(diǎn)確定。該超平面和任何其他的點(diǎn)無關(guān)。如果改變其他點(diǎn)的位置，只要其他點(diǎn)不落入虛線上或者虛線內(nèi)，那么超平面的參數(shù)都不會改變。A，B，C 這三個點(diǎn)被稱為支持向量（support vectors）。最大間隔超平面非常依賴支持向量的位置（這很明顯是個缺點(diǎn)，我們會在后面解決）。

在數(shù)學(xué)上，求解最大間隔超平面參數(shù)相當(dāng)于求解下面這個最優(yōu)化問題：

這個優(yōu)化問題雖然看起來復(fù)雜，但是它非常容易求解，不過關(guān)于它的求解過程不在本文的討論范圍內(nèi)。需要強(qiáng)調(diào)的是，上面的假想例子假設(shè)兩類樣本點(diǎn)是可以完美的被分開的。而在在實(shí)際問題中，這樣的情況幾乎是不存在的?？紤]下面的例子，紅藍(lán)兩類樣本點(diǎn)糾結(jié)在一起，我們無法找到一個超平面將它們完美的分開。

在這種情況下，我們怎么辦呢？解決的思路是放松我們的要求，即我們不要求所有的訓(xùn)練樣本都被正確的分類，由此引出軟間隔（soft margin）和支持向量分類器（support vector classifier）的概念。

6 支持向量分類器

引出軟間隔和支持向量分類器的概念有兩個動機(jī)。第一個動機(jī)是最大間隔分類器非常依賴支持向量的位置，這使得它對新的訓(xùn)練樣本非常敏感。考慮下面這個例子，右圖中僅僅因?yàn)樵黾恿艘粋€訓(xùn)練樣本而它恰好是支持向量，前后得到的超平面完全不同。很顯然，左圖中的超平面對所有點(diǎn)的整體分類效果更好，而右圖中因?yàn)橐粋€新樣本的加入，造成了模型的過擬合。

、

第二個動機(jī)就是上一節(jié)最后提到的，實(shí)際問題中，訓(xùn)練樣本幾乎無法被完美分開。為了解決這兩種情況，我們允許一部分樣本點(diǎn)被錯誤的分類，并以此為代價追求分類器的魯棒性以及分類器在全局所有樣本點(diǎn)上分類效果的整體最優(yōu)。一個支持向量分類器允許一些樣本點(diǎn)出現(xiàn)在最大間隔線之內(nèi)甚至是超平面錯誤的一側(cè)。下圖左圖中，A、B 兩點(diǎn)雖然沒有被分錯類，但它們出現(xiàn)在了最大間隔邊界（虛線）之內(nèi)；下圖右圖中，C 和 D 兩點(diǎn)則出現(xiàn)在超平面錯誤的一側(cè)。然而付出這些代價所換取的都是中間這條整體分類效果非常好的超平面（黑色實(shí)線）。

在數(shù)學(xué)上，引入 soft margin 后，優(yōu)化問題變?yōu)槿缦滦问剑?/p>

其中，對于每一個訓(xùn)練樣本點(diǎn)?i，定義了一個非負(fù)的松弛系數(shù)?e_i，它的取值表示該點(diǎn)是否滿足最大間隔。e_i?等于?0?則表示該點(diǎn)滿足最大間隔；如果?e_i?在?0?和?1?之間，說明這個樣本點(diǎn)在最大間隔邊界之內(nèi)但仍然分類正確；如果?e_i?大于?1?這說明該點(diǎn)被分到了超平面的錯誤一側(cè)。系數(shù) C 表示我們允許 soft margin?的程度。C 越小意味著我們越不允許出現(xiàn)不滿足最大間隔的情況。從直觀上說，C 的取值決定了最多有多少個訓(xùn)練樣本點(diǎn)可以被分類錯誤。下面的例子說明，對于不同的 C 的取值，得到的超平面也會有很大差異。

一個分類器的誤差由它的偏差和方差共同決定。在選取 C 時，我們必須權(quán)衡這兩者。一個很小的 C 往往意味著模型有很低的偏差但是很高的方差（因?yàn)樾碌臉颖军c(diǎn)會很容易改變超平面的參數(shù)）；一個很大的 C 通常意味著模型有很高的偏差（無法充分利用數(shù)據(jù)、找到有效的支持向量）和較低的方差。在實(shí)際應(yīng)用中，C 的取值可以通過交叉驗(yàn)證來確定。

7 支持向量機(jī)

支持向量分類器是一個很好的線性分類器（在允許錯誤樣本分類的前提下，找到對整體最優(yōu)的超平面）。然而對于有的問題，數(shù)據(jù)本身的特性決定了線性分類器無論如何也不可能取得很好的效果?？紤]下面這個例子。

如果僅使用線性的支持向量分類器，則只能得到上圖中黑色實(shí)線表示的超平面。它的分類效果是非常差的。這時，我們就需要對這個分類器進(jìn)行非線性的變換，這就是支持向量機(jī)。

這里變換的核心是對特征空間進(jìn)行非線性的變換。比如，對于 p 個特征 x_1, …, x_p，我們可以通過平方把它們變換到 2p 維的特征空間，即 x_1, (x_1)^2, …, x_p, (x_p)^2。然后在 2p 空間內(nèi)尋找線性的超平面進(jìn)行分類。雖然超平面在 2p 維度是線性的，但是由于它是原始特征的二次函數(shù)，因此從原始特征空間來看，我們實(shí)際上得到了一個非線性的分類器。

那什么是核函數(shù)呢？在求解超平面參數(shù)的最優(yōu)化問題中，最優(yōu)參數(shù)的取值僅僅依賴于訓(xùn)練樣本特征向量之間的內(nèi)積。假設(shè)兩個樣本點(diǎn)的特征向量為?x?和?z，則它們的內(nèi)積為?x?z（或者 (x^T)z）。假設(shè)特征空間的非線性映射為 phi，因此在映射后我們的樣本特征向量變?yōu)?phi(x) 和 phi(z)。在這個新的特征空間求解超平面時，我們需要使用的實(shí)際上是 phi(x)?phi(z)。對于這個映射，我們定義它對應(yīng)的核函數(shù)為：K(x,?z) = phi(x)?phi(z)。

因此，在優(yōu)化問題的求解中，我們只要把?x?z?都替換為 K(x,?z) 就相當(dāng)于是在 phi 這個映射下的特征空間內(nèi)求解超平面。當(dāng)我們知道映射 phi 的形式后，可以通過分別計算 phi(x) 和 phi(z)，然后再求它們的內(nèi)積得到 K(x,?z)。然而，這對于計算機(jī)來說是非常低效的。假如原始特征空間的維度為 p，而我們把它映射到維度為 p^2 的特征空間，則 SVM 算法的計算量就由 O(p) 變成了 O(p^2)。如果 p 很大的話（在很多實(shí)際問題中，p 是非常大的），這么做會大大的損害 SVM 的效率。

對此，核函數(shù)的優(yōu)勢是，對于很多應(yīng)用中常見的特征空間映射 phi 函數(shù)，核函數(shù)?K(x,?z)?存在一個非常方便計算的解析式。通過計算這個解析式，我們便可以繞過計算 phi(x) 和 phi(z)，而直接得到 K(x,?z) 的取值。然后我們只需要將 K(x,?z) 的值帶到最優(yōu)化參數(shù)的解中，便可得到最優(yōu)的超平面。這大大的降低了 SVM 的計算時間，使其成為高維空間分類的利器。

讓我們來看一個例子，考慮下面這個核函數(shù)（它又稱作多項(xiàng)式核）：

它的計算量只有 O(p)。當(dāng) p = 3 時，它對應(yīng)的映射 phi 卻是下面這個 13 維空間：

僅僅通過計算核函數(shù)的表達(dá)式就相當(dāng)于巧妙的進(jìn)行了從 3 維到 13 維空間的非線性映射，這是多么美妙！SVM的核心就是通過使用核函數(shù)（某一個給定的非線性方程），將原始的特征空間變換為更高維的特征空間。常見的核函數(shù)除了上面這個多項(xiàng)式核外，還有徑向基（高斯）核。它的表達(dá)式如下，這里不再贅述。

對于前面那個線性分類器無能為力的例子，在使用了適當(dāng)?shù)暮撕瘮?shù)后，我們可以在原始特征空間得到非線性的分類邊界（下面左圖使用了多項(xiàng)式核，右圖使用了高斯核）。顯然，它們的分類效果比線性分類器的效果要好很多，這是因?yàn)樗鼈兂浞掷昧擞?xùn)練數(shù)據(jù)的非線性特征。

8 SVM 的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

缺點(diǎn)：

9 結(jié)語

SVM 算是監(jiān)督分類算法的一個利器。它原理清晰、計算高效、易在高維空間處理非線性關(guān)系。但是，和任何一個機(jī)器學(xué)習(xí)算法一樣，最難的不是使用一個算法，而是真正明白我們要解決的問題。如果問題的本質(zhì)需要非線性分類邊界，而我們使用了線性的核函數(shù)，那結(jié)果可想而知。反過來也是一樣。在今后的討論中，我們還會進(jìn)一步從實(shí)戰(zhàn)的角度介紹如何有效的使用 SVM。

免責(zé)聲明：入市有風(fēng)險，投資需謹(jǐn)慎。在任何情況下，本文的內(nèi)容、信息及數(shù)據(jù)或所表述的意見并不構(gòu)成對任何人的投資建議。在任何情況下，本文作者及所屬機(jī)構(gòu)不對任何人因使用本文的任何內(nèi)容所引致的任何損失負(fù)任何責(zé)任。除特別說明外，文中圖表均直接或間接來自于相應(yīng)論文，僅為介紹之用，版權(quán)歸原作者和期刊所有。