本文轉(zhuǎn)自徐飛翔的“《SVM筆記系列之二》SVM的拉格朗日函數(shù)表示以及其對(duì)偶問(wèn)題”

版權(quán)聲明：本文為博主原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。

SVM的原問(wèn)題的拉格朗日乘數(shù)表示

我們?cè)谏弦黄┪?a href="http://www.e-ticket.cn/eestar/article-4996.html" target="_blank" rel="noopener">《SVM筆記系列1，SVM起源與目的》中，談到了SVM的原問(wèn)題，這里摘抄如下：

其滿足形式:

假設(shè)原問(wèn)題為，并且其最優(yōu)解為。這是一個(gè)有約束的最優(yōu)化問(wèn)題，我們利用廣義拉格朗日乘子法(具體移步《拉格朗日乘數(shù)法和KKT條件的直觀解釋》)，將其轉(zhuǎn)換為無(wú)約束的形式：

變形為：

我們將會(huì)得到原問(wèn)題的另一個(gè)表述為：

這里我覺(jué)得有必要解釋下為什么可以表述為 這種形式。假設(shè)我們有一個(gè)樣本點(diǎn)是不滿足原問(wèn)題的約束條件的，也就是說(shuō)，那么在這個(gè)環(huán)節(jié)就會(huì)使得從而使得 。如果是滿足約束條件的，那么為了求得最大值，因?yàn)?span>而且，所以就會(huì)使得。由此我們得知：

因此在滿足約束的情況下，

不滿足約束條件的樣本點(diǎn)則因?yàn)闊o(wú)法對(duì)正無(wú)窮求最小值而自然拋棄。這個(gè)時(shí)候，我們?cè)噲D去解中的我們會(huì)發(fā)現(xiàn)因?yàn)?span>對(duì)于是線性的，非凸的1，因此無(wú)法通過(guò)梯度的方法求得其最大值點(diǎn)，其最大值點(diǎn)應(yīng)該處于可行域邊界上，因此我們需要得到SVM的對(duì)偶問(wèn)題進(jìn)行求解。至此，我們得到了原問(wèn)題的最小最大表述：

SVM的對(duì)偶問(wèn)題

從上面的討論中，我們得知了SVM的原問(wèn)題的最小最大表達(dá)形式為：

設(shè)SVM的對(duì)偶問(wèn)題為，其最優(yōu)解為，可知道其為：

此時(shí)，我們得到了對(duì)偶問(wèn)題的最大最小表述，同樣的，我們?cè)噲D去求解中的，我們會(huì)發(fā)現(xiàn)由于對(duì)于W來(lái)說(shuō)是凸函數(shù)，因此可以通過(guò)梯度的方法求得其最小值點(diǎn)（即是其極小值點(diǎn)）。

求解，因?yàn)?span>是凸函數(shù)，我們對(duì)采用求梯度的方法求解其最小值（也是KKT條件中的，和：

得出：

將其代入，注意到,得：

整理為:

等價(jià)為求最小問(wèn)題:

根據(jù)Karush–Kuhn–Tucker(KKT)條件2,我們有：

前兩個(gè)式子我們已經(jīng)在求極值的時(shí)候利用了，得知:

并且其中至少有一個(gè)，對(duì)此有，代入剛才的 ，我們有

所以決策超平面為：

分類超平面為：

其中，我們可以觀察到超平面只是依賴于的樣本點(diǎn)，而其他樣本點(diǎn)對(duì)其沒(méi)有影響，所以這些樣本是對(duì)決策超平面起著決定性作用的，因此我們將對(duì)應(yīng)的樣本點(diǎn)集合稱為支持向量。同時(shí)，我們可以這樣理解當(dāng)時(shí)，我們有，這個(gè)恰恰是表明了支持向量的函數(shù)間隔都是1，恰好和我們之前的設(shè)定一致。

至此，我們得到了硬間隔線性支持向量機(jī)的數(shù)學(xué)表述形式，所謂硬間隔線性支持向量機(jī)，就是滿足我之前的假設(shè)

兩類樣本是線性可分的，總是存在一個(gè)超平面可以將其完美分割開(kāi)。

但是，在現(xiàn)實(shí)生活中的數(shù)據(jù)往往是或本身就是非線性可分但是近似線性可分的，或是線性可分但是具有噪聲的，以上兩種情況都會(huì)導(dǎo)致在現(xiàn)實(shí)應(yīng)用中，硬間隔線性支持向量機(jī)變得不再實(shí)用，因此我們將會(huì)在后續(xù)討論用以解決近似線性可分的軟間隔線性支持向量機(jī)和基于kernel的支持向量機(jī)，后者可以解決非線性可分的問(wèn)題。下圖表示了硬間隔線性支持向量機(jī)和軟間隔支持向量機(jī)之間的區(qū)別。

在下一篇中，我們緊接著現(xiàn)在的內(nèi)容，介紹序列最小最優(yōu)化算法（Sequential Minimal Optimization,SMO），用于求解，得到 以便于得到超平面的和b。我們將在其他文章中介紹軟間隔線性支持向量機(jī)，廣義拉格朗日乘數(shù)法，KKT條件和基于kernel的支持向量機(jī)。

這里我們要記住我們需要最優(yōu)化的目的式子，我們以后將會(huì)反復(fù)提到這個(gè)式子。

1.易證明。參考wikipedia的凸函數(shù)定義。 ??

2.事實(shí)上，如果的滿足KKT條件，那么在SVM這個(gè)問(wèn)題中， 和 和同時(shí)是原問(wèn)題和對(duì)偶問(wèn)題的解的充分必要條件是滿足KKT條件，具體見(jiàn)《統(tǒng)計(jì)學(xué)習(xí)方法》附錄和《拉格朗日乘數(shù)法和KKT條件的直觀解釋》。