拉格朗日對偶問題與支持向量機(jī)學(xué)習(xí)筆記(2)

2023-02-27 15:42 作者:ZJU前校長-吳朝暉院士 0人讀過 | 我要投稿

本部分主要講解線性可分的SVM的思想與推導(dǎo)過程，以及非線性可分的情況下的SVM處理方法。

關(guān)于本部分使用的拉格朗日對偶模型，可以參考另一篇文章“拉格朗日對偶問題與支持向量機(jī)學(xué)習(xí)筆記(1)”。

本文參考了“https://blog.csdn.net/weixin_44378835/article/details/110732412?utm_source%20=%20app”這篇博文和其他一些博文，進(jìn)行了一定的縮減，在部分地方添加了自己的想法和更詳細(xì)的推導(dǎo)過程。

2?支持向量機(jī)（SVM）

2.1?SVM的基本思想

當(dāng)我們對線性可分的兩個(gè)類別進(jìn)行二分類時(shí)，往往可以得到無窮多個(gè)符合條件的超平面。我們希望從中選出“最好”的一個(gè)超平面，而評價(jià)好壞的標(biāo)準(zhǔn)就是“分類間隔”，也就是在不改變分類結(jié)果的前提下超平面可以進(jìn)行平移的范圍，也就是下圖中的 $d$ 。顯然，分類間隔應(yīng)當(dāng)越大越好，因?yàn)槲覀儾荒芘懦龢颖酒顜淼挠绊懀环诸愰g隔越大，未被我們采樣的潛在區(qū)域中的樣本被錯(cuò)誤分類的概率越小。

值得注意的是，分類間隔的大小取決于那些離決策邊界最近的點(diǎn)。因此，為了找到最合適的決策邊界，我們只需要關(guān)注少數(shù)距離邊界近的點(diǎn)，而這些少數(shù)點(diǎn)就是“支持向量”；這是有很大好處的，因?yàn)樵跇颖军c(diǎn)很多的時(shí)候這可以大大減少計(jì)算量。

基于上述討論，我們希望最大化決策邊界與支持向量之間的距離。

記支持向量 $x_s$ 與判別函數(shù) $G(x)%3Dw%5ETx%2Bw_0$ 距離為 $r$ ，則 $r%3D%20%5Cfrac%20%7B%7CG(x_s)%7C%7D%20%7B%7C%7Cw%7C%7C%7D%EF%BC%8Cd%3D2r%3D%5Cfrac%20%7B2%7CG(x_s)%7C%7D%20%7B%7C%7Cw%7C%7C%7D$ 。要最大化 $d$ ，可以固定 $%7CG(x_s)%7C$ 求最小的 $%7C%7Cw%7C%7C$ ，也可以固定 $%7C%7Cw%7C%7C$ 求最大的 $%7CG(x)%7C$ 。支持向量機(jī)算法選擇固定 $%7CG(x)%7C$ 求最小的 $%7C%7Cw%7C%7C$ 。

由于 $%7C%7Cw%7C%7C$ 本身不方便求最小值，轉(zhuǎn)而求 $%7B%5Cfrac%201%202%7C%7Cw%7C%7C%5E2%7D$ 的最小值（顯然 $%7B%5Cfrac%201%202%7C%7Cw%7C%7C%5E2%7D$ 隨著 $%7C%7Cw%7C%7C$ 單調(diào)遞增，且 $%7B%7C%7Cw%7C%7C%5E2%7D$ 可以寫成 $%7Bw%5ETw%7D$ 這種向量內(nèi)積的形式，相對而言更好求最小值；此外，由于之后要用到KKT條件， $%5Cfrac%201%202%7B%7C%7Cw%7C%7C%5E2%7D$ 求導(dǎo)后直接變 $w$ ，所以乘 $%5Cfrac%201%202$ ）

根據(jù)設(shè)定（固定 $%7CG(x_s)%7C$ 求最小的 $%7C%7Cw%7C%7C$ ），令 $%7CG(x_s)%7C%3D1$ ，則所有的樣本點(diǎn)的判別函數(shù)的絕對值都滿足 $%7CG(x)%7C%20%5Cgeq%201$ 。使用指示變量 $sgn(%C2%B7)$ 來指示 $G(x)$ 的符號： $G(x)$ 為正時(shí) $sgn(G(x))$ 等于1， $G(x)$ 為負(fù)時(shí) $sgn(G(x))$ 等于-1。

綜上，建立如下優(yōu)化模型來表示SVM算法(樣本點(diǎn)共l個(gè))：

? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? $%5Cdisplaystyle%7Bmin%20%5Cquad%20%5Cfrac%201%202%7B%7C%7Cw%7C%7C%5E2%7D%5C%5C%20s.t.%20%5Cquad%20sgn(G(x%5E%7B(1)%7D))(w%5ETx%5E%7B(1)%7D%2Bw_0)%20%5Cgeq%201%5C%5C%20%5Cquad%20sgn(G(x%5E%7B(2)%7D))(w%5ETx%5E%7B(2)%7D%2Bw_0)%20%5Cgeq%201%5C%5C%20...%5C%5C%20%5Cquad%20sgn(G(x%5E%7B(l)%7D))(w%5ETx%5E%7B(l)%7D%2Bw_0)%20%5Cgeq%201%5C%5C%7D$

根據(jù)內(nèi)積的定義， $%5Cfrac%201%202%7B%7C%7Cw%7C%7C%5E2%7D$ 是一個(gè)凸函數(shù)，因此上述優(yōu)化問題是一個(gè)凸優(yōu)化問題。回顧上文中提到的KKT條件，這個(gè)優(yōu)化問題的 strong duality成立（d* = p*)?；谏鲜隹紤]，我們接下來只需建立此問題的對偶問題，并找出滿足KKT條件的點(diǎn)，則滿足條件的點(diǎn)就是本問題的最優(yōu)解。

原問題的對偶問題為：

$max_%5Calpha%20min_%7Bw%EF%BC%8Cw_0%7DL(w%2Cw_0%2C%5Calpha)%20%3D%20%7B%5Cfrac%201%202%7Bw%5ETw%7D%7D%20-%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20%5Cbigg(sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)-1%20%5Cbigg)$

$L(w%2Cw_0%2C%5Calpha)$ 對 $w$ 求偏導(dǎo)： $%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w%7D%20%3D%20w%20-%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))x%5E%7B(i)%7D%3D0$

得到： $w%20%3D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))x%5E%7B(i)%7D%20%5Cquad%20%5Cquad(1)$

$L(w%2Cw_0%2C%5Calpha)$ 對 $w_0$ 求偏導(dǎo)： $%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w_0%7D%20%3D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0$

得到： $%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%20%5Cquad%20%5Cquad(2)$

將上述（1），（2）兩個(gè)式子代入 $L(w%2Cw_0%2C%5Calpha)$ 的表達(dá)式，就可以求出 $min_%7Bw%2Cw_0%7DL(w%2Cw_0%2C%5Calpha)$ ，(推導(dǎo)略，這字實(shí)在太難打了)

$%7Bmin_%7Bw%2Cw_0%7DL(w%2Cw_0%2C%5Calpha)%20%3D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))x%5E%7B(i)T%7Dx%5E%7B(j)%7D%7D$

因此，對偶問題可以寫成：

$max_%5Calpha%20%5Cbigg(%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%7B%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))x%5E%7B(i)T%7Dx%5E%7B(j)%7D%20%5Cbigg)%5C%5C%20s.t.%20%5Cquad%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%5C%5C%20%5Calpha%5E%7B(i)%7D%20%5Cgeq%200%20%2C%20%5Cforall%20i%20%5Cin%20%5C%7B1%2C2%2C...%2Cl%5C%7D%7D$

同時(shí)，由于 $L(w%2Cw_0%2C%5Calpha)$ 的最優(yōu)解需要滿足KKT條件，根據(jù)互補(bǔ)松弛性， $%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20%5Cbigg(sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)-1%20%5Cbigg)%3D0$ ，所以對于任意的 $i$ ，要么 $%5Calpha%5E%7B(i)%7D%3D0$ ，要么 $sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)%3D1$ ；當(dāng) $%5Calpha%5E%7B(i)%7D%3D0$ 時(shí)，根據(jù)（1）式，樣本 $i$ 對最優(yōu)的 $w$ 沒有幫助；當(dāng) $sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)%3D1$ 時(shí)，樣本 $i$ 的 $G(x%5E%7B(i)%7D)%3D(w%5ETx%5E%7B(i)%7D%2Bw_0)%3D1$ ，說明此樣本 $i$ 就是支持向量。

由簡化后的對偶模型求解出 $%5Calpha%5E%7B(i)%7D$ ，代入到式（1）中便獲得了最優(yōu)的 $w%3D%5Cdisplaystyle%5Csum%5E%7Bl_s%7D_%7Bs%3D1%7D%5Calpha%5E%7B(s)%7D%20sgn(G(x%5E%7B(s)%7D))x%5E%7B(s)%7D$ (僅依賴于支持向量)；再根據(jù)上面的方法找出支持向量，根據(jù) $w%5ETx%5E%7B(s)%7D%2Bw_0%3D1$ 即可求出 $w_0$ 。

2.2?線性不可分時(shí)的 SVM

我們到目前為止討論的都是線性可分的支持向量機(jī)。這個(gè)模型有解的一個(gè)前提條件是樣本集是線性可分的。但實(shí)際上，很多問題的樣本集并不是線性可分的，例如下面這樣的樣本集。

那么，我們要如何去處理這種情況呢？在具體探討解決方案前，我們首先要明確一個(gè)問題，那就是造成樣本集線性不可分的原因是什么。

實(shí)際上，有兩種可能的原因會導(dǎo)致樣本集線性不可分：

異常點(diǎn)帶來的線性不可分：樣本集的總體是線性可分的，但是由于抽樣存在隨機(jī)噪聲，少數(shù)的異常樣本點(diǎn)較大地偏離了總體，使得不存在一個(gè)超平面能夠?qū)深悩颖具M(jìn)行分割。

問題本質(zhì)上的線性不可分。在這種情況下，樣本來自的總體就是線性不可分的，此時(shí)線性可分的SVM完全失效。

兩種情況下，我們采取的補(bǔ)救措施也有所不同。

2.2.1?異常點(diǎn)帶來的線性不可分——軟間隔支持向量機(jī)

線性可分的支持向量機(jī)無法求解異常點(diǎn)帶來的線性不可分，是因?yàn)樗丫嚯x分類間隔最近的點(diǎn)作為支持向量，從而異常點(diǎn)很可能會錯(cuò)誤地被認(rèn)為是支持向量，這導(dǎo)致了它無法容忍任何異常點(diǎn)。軟間隔支持向量機(jī)的思想是通過引入松弛變量的方法，使得離群的異常點(diǎn)不會成為支持向量，從而在一定程度上容忍異常點(diǎn)。

具體的做法就是同時(shí)引入松弛變量 $%5Cxi%5E%7B(l_i)%7D%20%5Cgeq%200$ 和懲罰系數(shù) $C%20%5Cgeq%200$ 。 $%5Cxi%5E%7B(l_i)%7D$ 的引入使得異常值點(diǎn)不會成為支持向量；但是 $%5Cxi%5E%7B(l_i)%7D$ 越大，則代價(jià)函數(shù)也越大，因?yàn)槲覀儾⒉幌ＭＰ统霈F(xiàn)過多的離群點(diǎn)和錯(cuò)誤分類。最理想的情況下，絕大多數(shù)支持向量外側(cè)的樣本(包括支持向量)，對應(yīng)的松弛變量都應(yīng)該是為0的。只有少數(shù)在支持向量內(nèi)側(cè)的異常點(diǎn)，才有一個(gè)盡可能小的松弛變量。

需要注意的是，懲罰系數(shù) $C$ 是預(yù)先給定的，而松弛變量 $%5Cxi%5E%7B(l_i)%7D$ 則是通過優(yōu)化獲得的，因?yàn)槲覀冊趦?yōu)化目標(biāo)函數(shù)之前并不知道哪些樣本點(diǎn) $i$ 會成為離群點(diǎn)。

上述軟間隔支持向量機(jī)優(yōu)化問題的求解過程與線性支持向量機(jī)完全相同。最后得到的最優(yōu)權(quán)向量?，仍然由一組支持向量 $x%5E%7B(s)%7D$ ?的線性組合所構(gòu)成。

2.2.2?問題本質(zhì)上的線性不可分——非線性支持向量機(jī)（核函數(shù)）

當(dāng)需要分類的總體本就不是線性可分的時(shí)候，使用軟間隔SVM也是無效的。

解決此類問題的方法是“廣義線性化”。廣義線性化就是將低維空間中的一個(gè)非線性分類問題往高維空間映射，從而轉(zhuǎn)化為一個(gè)線性分類問題。例如下面這個(gè)一維空間中的非線性判別問題，通過映射到二維空間，就變成了一個(gè)線性判別問題。

假設(shè)存在這樣一個(gè)從低維向高維的映射 $%5Cphi(%C2%B7)$ ，能夠?qū)⒌途S的中線性不可分的樣本 $x%5E%7B(i)%7D$ 映射為高維中線性可分的 $%5Cphi(x%5E%7B(i)%7D)$ 。注意到，盡管樣本的判別函數(shù)也需要進(jìn)行映射，但是因?yàn)?/span>樣本的類別標(biāo)簽沒有改變，所以判別函數(shù)的符號也沒有改變。根據(jù)上文中的結(jié)論，我們只需求解如下模型中的 $%5Calpha$ 即可：

$%7Bmax_%5Calpha%20%5Cbigg(%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D)%20%5Cbigg)%5C%5Cs.t.%20%5Cquad%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%5C%5C%5Calpha%5E%7B(i)%7D%20%5Cgeq%200%20%2C%20%5Cforall%20i%20%5Cin%20%5C%7B1%2C2%2C...%2Cl%5C%7D%7D$

然而，一方面，我們并不知道一個(gè)普適的方法來為所有的線性不可分總體尋找從低維向高維的映射 $%5Cphi(%C2%B7)$ ，我們甚至不知道 $%5Cphi(%C2%B7)$ 的維數(shù)應(yīng)該是多少；另一方面，將低維特征映射到高維后模型計(jì)算量會指數(shù)型增長，帶來計(jì)算上的困難。因此上述方法雖然看似很美好，但實(shí)際上是不可行的。但是，人們想出了一種方法，使得我們不用真的將所有向量從低維映射到高維，但仍能從一定程度上求解上述問題，這個(gè)方法就是核函數(shù)。

觀察上面的這個(gè)優(yōu)化目標(biāo)，我們可以發(fā)現(xiàn)映射前與映射后的優(yōu)化目標(biāo)的唯一區(qū)別就在于將 $x%5E%7B(i)T%7Dx%5E%7B(j)%7D$ 變成了 $%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D$ 。也就是說，如果我們能夠找到一個(gè)函數(shù) $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3D%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D)$ ，那么其實(shí)不用真的找到 $%5Cphi(%C2%B7)$ ，也不用真的進(jìn)行映射，我們只要用 $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)$ 替換上式中的 $%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D)$ 并進(jìn)行求解如下的優(yōu)化問題，就能獲得所需要的 $%5Calpha$ ：

$%7Bmax_%5Calpha%20%5Cbigg(%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%20%5Cbigg)%5C%5Cs.t.%20%5Cquad%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%5C%5C%5Calpha%5E%7B(i)%7D%20%5Cgeq%200%20%2C%20%5Cforall%20i%20%5Cin%20%5C%7B1%2C2%2C...%2Cl%5C%7D%7D$

盡管核函數(shù)與 $%5Cphi(%C2%B7)$ 一樣，在實(shí)際上無論是形式還是參數(shù)都沒有確定的選擇方法，只能依靠經(jīng)驗(yàn)進(jìn)行嘗試，但是核函數(shù)法仍然為我們帶來了兩個(gè)好處：

使用核函數(shù)并沒有增加變量的維數(shù)，避免了由維數(shù)增加帶來的求解困難。
相比于完全幾乎完全沒有規(guī)律的 $%5Cphi(%C2%B7)$ ，有幾種特定形式的核函數(shù)被驗(yàn)證為是有效并且被廣泛使用，便于我們進(jìn)行嘗試。

常用的核函數(shù)有以下這些：

線性核函數(shù)： $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3Dx%5E%7B(i)T%7Dx%5E%7B(j)%7D$ ，形式簡單，計(jì)算量小。
多項(xiàng)式核函數(shù)： $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3D(%5Cgamma%20x%5E%7B(i)T%7D%2B%5Czeta)%5EQ$ ?，其中 $%5Cgamma%20%2C%5Czeta%2CQ$ 均可自由指定。其中γ對內(nèi)積進(jìn)行縮放，ζ進(jìn)行加減上的調(diào)整，Q用于控制次數(shù)。
高斯核函數(shù)： $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3D%5Cdisplaystyle%7Bexp(%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C2%7D%7B2%5Csigma%5E2%7D)%7D$
······

3?結(jié)語

雖然現(xiàn)在SVM已經(jīng)被“研究爛了”，目前也有很多完成度很高，效果很好的工具包，不過學(xué)習(xí)它的底層原理感覺還是很有必要的。

之后可能也會繼續(xù)發(fā)一些學(xué)習(xí)方面的專欄，希望這個(gè)學(xué)期別像上個(gè)學(xué)期一樣擺爛了。

最后再吐槽一下b站專欄的功能：以前寫點(diǎn)短專欄還好，現(xiàn)在稍微寫長點(diǎn)就發(fā)現(xiàn)真的太不方便了，不支持的格式也多，排版出來的效果也是稀碎。。。。

標(biāo)簽：SVM 支持向量機(jī)核函數(shù)