作者：石川

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

1 引言

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

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

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

2 初識(shí) SVM

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

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

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

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

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

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

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

3 線性超平面

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

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

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

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

4 分類問(wèn)題

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

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

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

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

5 最大間隔超平面

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

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

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

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

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

6 支持向量分類器

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

、

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

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

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

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

7 支持向量機(jī)

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

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

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

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

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

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

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

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

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

對(duì)于前面那個(gè)線性分類器無(wú)能為力的例子，在使用了適當(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é)語(yǔ)

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

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