對(duì)偶支持向量機(jī)DSVM

1

Motivation of Dual SVM

首先，我們回顧一下，對(duì)于非線性SVM，我們通?？梢允褂梅蔷€性變換將變量從x域轉(zhuǎn)換到z域中。然后，在z域中，根據(jù)上一節(jié)課的內(nèi)容，使用線性SVM解決問題即可。上一節(jié)課我們說過，使用SVM得到large-margin，減少了有效的VC Dimension，限制了模型復(fù)雜度；另一方面，使用特征轉(zhuǎn)換，目的是讓模型更復(fù)雜，減小Ein。

所以說，非線性SVM是把這兩者目的結(jié)合起來，平衡這兩者的關(guān)系。那么，特征轉(zhuǎn)換下，求解QP問題在z域中的維度設(shè)為d^+1，如果模型越復(fù)雜，則d^+1越大，相應(yīng)求解這個(gè)QP問題也變得很困難。當(dāng)d^無限大的時(shí)候，問題將會(huì)變得難以求解，那么有沒有什么辦法可以解決這個(gè)問題呢？一種方法就是使SVM的求解過程不依賴d^，這就是我們本節(jié)課所要討論的主要內(nèi)容。

比較一下，我們上一節(jié)課所講的Original SVM二次規(guī)劃問題的變量個(gè)數(shù)是d^+1，有N個(gè)限制條件；而本節(jié)課，我們把問題轉(zhuǎn)化為對(duì)偶問題（’Equivalent’ SVM），同樣是二次規(guī)劃，只不過變量個(gè)數(shù)變成N個(gè)，有N+1個(gè)限制條件。這種對(duì)偶SVM的好處就是問題只跟N有關(guān)，與d^無關(guān)，這樣就不存在上文提到的當(dāng)d^無限大時(shí)難以求解的情況。

如何把問題轉(zhuǎn)化為對(duì)偶問題（’Equivalent’ SVM），其中的數(shù)學(xué)推導(dǎo)非常復(fù)雜，本文不做詳細(xì)數(shù)學(xué)論證，但是會(huì)從概念和原理上進(jìn)行簡(jiǎn)單的推導(dǎo)。

所以，在regularization問題中，λ是已知常量，求解過程變得容易。那么，對(duì)于dual SVM問題，同樣可以引入λ，將條件問題轉(zhuǎn)換為非條件問題，只不過λ是未知參數(shù)，且個(gè)數(shù)是N，需要對(duì)其進(jìn)行求解。

這個(gè)函數(shù)右邊第一項(xiàng)是SVM的目標(biāo)，第二項(xiàng)是SVM的條件和拉格朗日因子αn的乘積。我們把這個(gè)函數(shù)稱為拉格朗日函數(shù)，其中包含三個(gè)參數(shù)：b，w，αn。

下面，我們利用拉格朗日函數(shù)，把SVM構(gòu)造成一個(gè)非條件問題：

2

Lagrange Dual SVM

現(xiàn)在，我們已經(jīng)將SVM問題轉(zhuǎn)化為與拉格朗日因子αn有關(guān)的最大最小值形式。已知αn≥0，那么對(duì)于任何固定的α′，且αn′≥0，一定有如下不等式成立：

對(duì)上述不等式右邊取最大值，不等式同樣成立：

上述不等式表明，我們對(duì)SVM的min和max做了對(duì)調(diào)，滿足這樣的關(guān)系，這叫做Lagrange dual problem。不等式右邊是SVM問題的下界，我們接下來的目的就是求出這個(gè)下界。

已知≥是一種弱對(duì)偶關(guān)系，在二次規(guī)劃QP問題中，如果滿足以下三個(gè)條件：

• 函數(shù)是凸的（convex primal）
• 函數(shù)有解（feasible primal）
• 條件是線性的（linear constraints）

那么，上述不等式關(guān)系就變成強(qiáng)對(duì)偶關(guān)系，≥變成=，即一定存在滿足條件的解(b,w,α)，使等式左邊和右邊都成立，SVM的解就轉(zhuǎn)化為右邊的形式。

經(jīng)過推導(dǎo)，SVM對(duì)偶問題的解已經(jīng)轉(zhuǎn)化為無條件形式：

其中，上式括號(hào)里面的是對(duì)拉格朗日函數(shù)L(b,w,α)計(jì)算最小值。那么根據(jù)梯度下降算法思想：最小值位置滿足梯度為零。首先，令L(b,w,α)對(duì)參數(shù)b的梯度為零：

這樣，SVM表達(dá)式消去了b，問題化簡(jiǎn)了一些。然后，再根據(jù)最小值思想，令L(b,w,α)對(duì)參數(shù)w的梯度為零：

即得到：

這樣，SVM表達(dá)式消去了w，問題更加簡(jiǎn)化了。這時(shí)候的條件有3個(gè)：

總結(jié)一下，SVM最佳化形式轉(zhuǎn)化為只與αn有關(guān)：

其中，滿足最佳化的條件稱之為Karush-Kuhn-Tucker(KKT)：

在下一部分中，我們將利用KKT條件來計(jì)算最優(yōu)化問題中的α，進(jìn)而得到b和w。

3

Solving Dual SVM

上面我們已經(jīng)得到了dual SVM的簡(jiǎn)化版了，接下來，我們繼續(xù)對(duì)它進(jìn)行一些優(yōu)化。首先，將max問題轉(zhuǎn)化為min問題，再做一些條件整理和推導(dǎo)，得到：

顯然，這是一個(gè)convex的QP問題，且有N個(gè)變量αn，限制條件有N+1個(gè)。則根據(jù)上一節(jié)課講的QP解法，找到Q，p，A，c對(duì)應(yīng)的值，用軟件工具包進(jìn)行求解即可。

4

Messages behind Dual SVM

回憶一下，上一節(jié)課中，我們把位于分類線邊界上的點(diǎn)稱為support vector（candidates）。本節(jié)課前面介紹了αn>0的點(diǎn)一定落在分類線邊界上，這些點(diǎn)稱之為support vector（注意沒有candidates）。也就是說分類線上的點(diǎn)不一定都是支持向量，但是滿足αn>0的點(diǎn)，一定是支持向量。

SV只由αn>0的點(diǎn)決定，根據(jù)上一部分推導(dǎo)的w和b的計(jì)算公式，我們發(fā)現(xiàn)，w和b僅由SV即αn>0的點(diǎn)決定，簡(jiǎn)化了計(jì)算量。這跟我們上一節(jié)課介紹的分類線只由“胖”邊界上的點(diǎn)所決定是一個(gè)道理。也就是說，樣本點(diǎn)可以分成兩類：一類是support vectors，通過support vectors可以求得fattest hyperplane；另一類不是support vectors，對(duì)我們求得fattest hyperplane沒有影響。

回過頭來，我們來比較一下SVM和PLA的w公式：

總結(jié)一下，本節(jié)課和上節(jié)課主要介紹了兩種形式的SVM，一種是Primal Hard-Margin SVM，另一種是Dual Hard_Margin SVM。Primal Hard-Margin SVM有d^+1個(gè)參數(shù)，有N個(gè)限制條件。當(dāng)d^+1很大時(shí)，求解困難。而Dual Hard_Margin SVM有N個(gè)參數(shù)，有N+1個(gè)限制條件。當(dāng)數(shù)據(jù)量N很大時(shí)，也同樣會(huì)增大計(jì)算難度。兩種形式都能得到w和b，求得fattest hyperplane。通常情況下，如果N不是很大，一般使用Dual SVM來解決問題。

5

Summary

本節(jié)課主要介紹了SVM的另一種形式：Dual SVM。我們這樣做的出發(fā)點(diǎn)是為了移除計(jì)算過程對(duì)d^的依賴。Dual SVM的推導(dǎo)過程是通過引入拉格朗日因子α，將SVM轉(zhuǎn)化為新的非條件形式。然后，利用QP，得到最佳解的拉格朗日因子α。再通過KKT條件，計(jì)算得到對(duì)應(yīng)的w和b。最終求得fattest hyperplane。