寫在前面

有一個(gè)多月沒有更新博客了，整個(gè)三月份都在忙項(xiàng)目的事，忙著各種掃尾解決一些“歷史遺留問題”。終于到了清明節(jié)假期，可以寫一寫博客了。老實(shí)講，一共有好幾篇可以寫，不過想來想去還是先寫這篇SVM相關(guān)的吧！主要是再不寫估計(jì)算法的推導(dǎo)細(xì)節(jié)就快忘完了，其他的坑慢慢再填：（哭。

OK，言歸正傳，先簡單介紹一下什么是序列最小優(yōu)化算法（以下簡稱SMO算法）。SMO算法是一種解決二次優(yōu)化問題的算法，其最經(jīng)典的應(yīng)用就是在解決SVM問題上。SVM推導(dǎo)到最后，特別是使用了拉格朗日因子法求解之后便不難發(fā)現(xiàn)其最終等效為一個(gè)二次規(guī)劃問題。二次規(guī)劃問題有很多成熟的解法，在SMO算法出現(xiàn)之前這些解法就已經(jīng)應(yīng)用到了SVM問題的求解上。但是這些解法無論效果如何都有一個(gè)共同的缺點(diǎn)即是計(jì)算量太大，在小樣本的情況下尚堪使用，數(shù)據(jù)量一大就變得難以奏效。1996年，John Platt發(fā)布了一個(gè)稱為SMO的強(qiáng)大算法，用于訓(xùn)練SVM分類器。其基本思路就是一次迭代只優(yōu)化兩個(gè)變量而固定剩余的變量。直觀地講就是將一個(gè)大的優(yōu)化問題分解為若干個(gè)小的優(yōu)化問題，這些小的優(yōu)化問題往往是易于求解的。要想搞清楚SMO算法首先要簡要介紹一下SVM。

什么是SVM

SVM是Support Vector Machine（支持向量機(jī)）的英文縮寫，是上世紀(jì)九十年代興起的一種機(jī)器學(xué)習(xí)算法，在目前神經(jīng)網(wǎng)絡(luò)大行其道的情況下依然保持著生命力。有人說現(xiàn)在是神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)的時(shí)代了，AI從業(yè)者可以不用了解像SVM這樣的古董了。姑且不說SVM是否真的已經(jīng)沒有前途了，僅僅是SVM在數(shù)學(xué)上優(yōu)美的推導(dǎo)就值得后來者好好欣賞一番，這也是筆者迄今為止見過機(jī)器學(xué)習(xí)領(lǐng)域最優(yōu)美的數(shù)學(xué)推導(dǎo)。

和大多數(shù)二分類算法一樣，SVM算法也是致力于在正例和反例之間找出一個(gè)超平面來將它們區(qū)分開來，如下圖所示：

圖1

如圖所示，正例用“+”號(hào)表示，反例用“-”號(hào)表示。從圖中可以看出，正例和反例是線性可分的。學(xué)習(xí)器的目的就是要學(xué)出一條如圖所示的紅色超平面將正例和反例區(qū)分開來。這也是其他非SVM分類器的共同目標(biāo)，即：

而SVM與其它分類器所不同的是它引入了“支持向量”這一概念，反映到圖中也就是紅色的小點(diǎn)所代表的向量。（注：由于筆者作圖時(shí)采用的SVM是軟間隔的版本，因此支持向量不像是大多數(shù)教科書上采用硬間隔的SVM那樣）由SVM的優(yōu)化目標(biāo)我們可以知道：樣本空間中任意一個(gè)點(diǎn)x到該超平面的的距離可寫為：

假設(shè)超平面可以完全正確地將所有樣本分類，則對(duì)于任意一個(gè)樣本（xi，yi）來說都有如下性質(zhì)（注：樣本的標(biāo)簽用+1代表正例，-1代表反例）：

訓(xùn)練樣本中使上式成立的樣本稱為支持向量，兩個(gè)異類支持向量到超平面距離之和為：

上式被稱為“間隔”。SVM的優(yōu)化目標(biāo)是為了找到這樣一個(gè)劃分超平面，該超平面能使間隔最大化，則SVM的優(yōu)化目標(biāo)可以表示為如下形式：

這就是SVM的基本數(shù)學(xué)表達(dá)，接下來就要對(duì)SVM問題進(jìn)行求解。從上面的數(shù)學(xué)形式可以看出這是一個(gè)優(yōu)化問題，可以使用拉格朗日乘子法求解其對(duì)偶問題。由于本文不是專門介紹SVM的，因此忽略掉具體的推導(dǎo)，直接給出SVM的對(duì)偶問題表達(dá)：

由于采用了拉格朗日乘子法，因此該對(duì)偶問題還有一個(gè)KKT條件約束，即要求：

以上，就是SVM的一些相關(guān)介紹。需要特別說明的是，以上的推導(dǎo)都是建立在“硬間隔”的基礎(chǔ)上，“硬間隔”要求樣本集中每一個(gè)樣本都滿足約束條件。在現(xiàn)實(shí)中往往很難確定合適的核函數(shù)使得訓(xùn)練樣本在特征空間中是線性可分的，緩解該問題的一個(gè)辦法是允許支持向量機(jī)在一些樣本上出錯(cuò)，為此引入“軟間隔”的概念。具體來說，“硬間隔”要求所有參與訓(xùn)練的樣本都必須滿足SVM的約束條件，而“軟間隔”允許有部分樣本不滿足這樣的約束。由于本文不是專門論述SVM的，因此就不展開講“軟間隔”所帶來的一些新的問題，只說一下“軟間隔”條件下新的優(yōu)化目標(biāo)：

KKT條件為：

其中，C為容忍度因子，可以理解為SVM對(duì)“軟間隔”的支持度。若C為無窮大，則所有的訓(xùn)練樣本均必須滿足SVM的約束條件，C值越小就允許越多的樣本不滿足約束條件。

SMO算法思想

通過觀察SVM的優(yōu)化目標(biāo)我們可以發(fā)現(xiàn)其最終的目的是要計(jì)算出一組最優(yōu)的alpha和常數(shù)項(xiàng)b的值。SMO算法的中心思想就是每次選出兩個(gè)alpha進(jìn)行優(yōu)化（之所以是兩個(gè)是因?yàn)閍lpha的約束條件決定了其與標(biāo)簽乘積的累加等于0，因此必須一次同時(shí)優(yōu)化兩個(gè)，否則就會(huì)破壞約束條件），然后固定其他的alpha值。重復(fù)此過程，直到達(dá)到某個(gè)終止條件程序退出并得到我們需要的優(yōu)化結(jié)果。接下來，就具體推導(dǎo)一下SMO算法的細(xì)節(jié)。

算法數(shù)學(xué)推導(dǎo)

由于SVM中有核函數(shù)的概念，因此我們用Kij來表示在核函數(shù)K下向量i和向量j的計(jì)算值?，F(xiàn)在假定我們已經(jīng)選出alpha1和alpha2兩個(gè)待優(yōu)化項(xiàng)，然后將原優(yōu)化目標(biāo)函數(shù)展開為與alpha1和alpha2有關(guān)的部分和無關(guān)的部分：

其中c是與alpha1和alpha2無關(guān)的部分，在本次優(yōu)化中當(dāng)做常數(shù)項(xiàng)處理。由SVM優(yōu)化目標(biāo)函數(shù)的約束條件：

可以得到：

將優(yōu)化目標(biāo)中所有的alpha1都替換為用alpha2表示的形式，得到如下式子：

此時(shí)，優(yōu)化目標(biāo)中僅含有alpha2一個(gè)待優(yōu)化變量了，我們現(xiàn)在將待優(yōu)化函數(shù)對(duì)alpha2求偏導(dǎo)得到如下結(jié)果：

已知：

將以上三個(gè)條件帶入偏導(dǎo)式子中，得到如下結(jié)果：

化簡后得：

記：

若n<=0則退出本次優(yōu)化，若n>0則可得到alpha2的更新公式：

此時(shí)，我們已經(jīng)得到了alpha2的更新公式。不過我們此時(shí)還需要考慮alpha2的取值范圍問題。因?yàn)閍lpha2的取值范圍應(yīng)該是在0到C之間，但是在這里并不能簡單地把取值范圍限定在0至C之間，因?yàn)閍lpha2的取值不僅僅與其本身的范圍有關(guān)，也與alpha1，y1和y2有關(guān)。設(shè)alpha1*y1+alpha2*y2=k，畫出其約束，在這里要分兩種情況，即y1是否等于y2。我們?cè)谶@里先來考慮y1!=y2的情況：在這種情況下alpha1-alpha2=k：

圖2

可以看出此時(shí)alpha2的取值范圍為：

當(dāng)y1=y2時(shí)，alpha1+alpha2=k：

圖3

可以看出此時(shí)alpha2的取值范圍為：

以上，可以總結(jié)出alpha2的取值上下界的規(guī)律：

故可得到alpha2的取值范圍：

由alpha_old1y1+alpha_old2y2=alpha_new1y1+alpha_new2y2可得alpha1的更新公式：

接下來，需要確定常數(shù)b的更新公式，在這里首先需要根據(jù)“軟間隔”下SVM優(yōu)化目標(biāo)函數(shù)的KKT條件推導(dǎo)出新的KKT條件，得到結(jié)果如下：

由于現(xiàn)在alpha的取值范圍已經(jīng)限定在0至C之間，也就是上面KKT條件的第三種情況。接下來我們將第三種KKT條件推廣到任意核函數(shù)的情境下：

由此我們可以得到常數(shù)b的更新公式：

其中Ei是SVM的預(yù)測誤差，計(jì)算式為：

以上，筆者就已經(jīng)把SMO算法的大部分細(xì)節(jié)推導(dǎo)出來了。接下來，我們可以根據(jù)這些推導(dǎo)對(duì)SMO算法進(jìn)行實(shí)現(xiàn)，并且用我們的算法訓(xùn)練一個(gè)SVM分類器。

SMO的算法實(shí)現(xiàn)

SMO算法的實(shí)現(xiàn)還是比較復(fù)雜的，有很多細(xì)節(jié)，我們不用一一關(guān)注，只用抓住其中兩個(gè)特別重要的點(diǎn)就行了：1、如何選取每次迭代的alpha對(duì)；2、如何確定SVM優(yōu)化程序的退出條件。筆者將就這兩個(gè)主要問題進(jìn)行論述。首先關(guān)注第一個(gè)問題：如何選取alpha對(duì)。

我們可以簡化一下第一個(gè)問題：假定現(xiàn)在已經(jīng)選取了第一個(gè)待優(yōu)化的alpha，如何選取另一個(gè)alpha？在SMO算法中為了讓迭代次數(shù)盡量少，收斂速度盡量快，算法要求我們選取的兩個(gè)alpha有盡可能大的“差異”。在算法的實(shí)現(xiàn)中我們用預(yù)測的誤差值來表征一個(gè)alpha的效果。那么兩個(gè)aplha盡可能不同反映在算法上就是兩個(gè)alpha所對(duì)應(yīng)的預(yù)測誤差值之差的絕對(duì)值最大，該思想用代碼表現(xiàn)出來如下圖所示：

圖4

上面的代碼反映出了這樣一種思想：首先傳入第一個(gè)alpha所對(duì)應(yīng)的索引值“i”，然后搜索誤差列表eCache，在其中找到與“i”所對(duì)應(yīng)的誤差值相差絕對(duì)值最大的那個(gè)索引值“j”，則另一個(gè)alpha的索引值就定為“j”。若誤差值列表eCache還沒有初始化則從所有的索引值中隨機(jī)選取一個(gè)索引值作為另一個(gè)alpha的索引值。

那么第一個(gè)alpha如何選取呢？這個(gè)問題與另外兩個(gè)問題是相關(guān)的：第一個(gè)問題是選取的alpha值是否違反KKT條件，如果該alpha值違反了KKT條件則該alpha是不能夠作為優(yōu)化對(duì)象的；第二個(gè)問題與SMO優(yōu)化算法的優(yōu)化終止條件有關(guān)，通常SMO算法會(huì)在一個(gè)死循環(huán)中反復(fù)執(zhí)行兩個(gè)過程，第一個(gè)過程是遍歷所有的alpha值，每掃描到一個(gè)alpha就將其作為alpha對(duì)的第一個(gè)值傳入內(nèi)循環(huán)，同時(shí)根據(jù)上一段提出的選取準(zhǔn)則選擇另一個(gè)alpha。遍歷完一次alpha值之后若alpha值被優(yōu)化器改變的次數(shù)不為0則本次循環(huán)結(jié)束同時(shí)修改一些標(biāo)志量然后進(jìn)入下一次循環(huán)。下一次循環(huán)執(zhí)行第二個(gè)過程：遍歷alpha值列表中所有不為0的值，每掃描到一個(gè)不為0的alpha值之后就將其傳入內(nèi)循環(huán)，然后執(zhí)行和上面相同的過程。重復(fù)執(zhí)行上述過程，最終，當(dāng)某次循環(huán)遍歷優(yōu)化所有alpha列表后卻沒有一個(gè)alpha值被優(yōu)化器改變則程序認(rèn)為優(yōu)化任務(wù)完成了，程序退出。代碼如下：

圖5

以上，就是SMO算法在實(shí)現(xiàn)時(shí)的一些細(xì)節(jié)。完整的SMO實(shí)現(xiàn)還是比較復(fù)雜的，有很多的小細(xì)節(jié)需要注意，在這里就不一一論述了。如果讀者想了解更多可以訪問我的git倉庫，上面有我的詳細(xì)代碼，倉庫地址在文章的末尾給出。

后記

SVM算法其實(shí)筆者很早就用過，最早是大學(xué)時(shí)用來做垃圾郵件的分類，但那個(gè)時(shí)候一直是在調(diào)用算法包，對(duì)SVM算法的種種細(xì)節(jié)不是很了解。今年寒假的時(shí)候數(shù)據(jù)挖掘這門課剛好有一個(gè)大作業(yè)用到了這個(gè)算法，這才算好好了解了一下這種算法實(shí)現(xiàn)的內(nèi)部細(xì)節(jié)，自己用python好好實(shí)現(xiàn)了一下。

自從上了研究生以后就一直在了解學(xué)習(xí)機(jī)器學(xué)習(xí)的種種算法，真心感覺這個(gè)領(lǐng)域非常有意思，對(duì)數(shù)學(xué)的要求很高。雖然自己學(xué)習(xí)的算法現(xiàn)在還是停留在像支持向量機(jī)，隨機(jī)森林，決策樹，邏輯回歸這些經(jīng)典的算法上，可以說進(jìn)步緩慢，但是我還是很有信心，總是要先把基礎(chǔ)打好嘛！嗯~目前為止這些經(jīng)典的算法幾乎都快被我掃清了，數(shù)據(jù)挖掘領(lǐng)域的十大算法自己已經(jīng)差不多實(shí)現(xiàn)了六七個(gè)，接下來想想看就該進(jìn)入概率圖模型，馬爾科夫隨機(jī)場，神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)什么的了，剛好這學(xué)期有一門神經(jīng)網(wǎng)絡(luò)的課。估計(jì)這篇文章就是傳統(tǒng)機(jī)器學(xué)習(xí)算法的最后一篇博客了，以后再寫就應(yīng)該是神經(jīng)網(wǎng)絡(luò)和分布式系統(tǒng)方面的了，什么TensorFlow，什么CNN，RNN都寫一寫。哈哈！請(qǐng)大家關(guān)注我的github，我會(huì)在上面把我自己的機(jī)器學(xué)習(xí)筆記代碼都實(shí)時(shí)公開的，博客也會(huì)有時(shí)間就寫。

https://github.com/yhswjtuILMARE/Machine-Learning-Study-Notes

2018年4月8日