SVM(Support Vector Machine概荷,支持向量機(jī))是最經(jīng)典的分類算法食茎,本文主要整理(為了應(yīng)付考試)SVM的推導(dǎo)方式融涣,不包含SMO算法求解最后的約束。
借鑒博客:
https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html
https://www.cnblogs.com/90zeng/p/Lagrange_duality.html
一般的崩瓤,SVM就是一個(gè)分類器,只是相對于傳統(tǒng)的線性分類器踩官,它添加了一個(gè)支持向量的概念却桶。這樣相對于傳統(tǒng)分類器可能存在的多個(gè)解,SVM由于約束的存在一般只有單解蔗牡,并且表現(xiàn)更好颖系。
從圖片上解釋,對于一組數(shù)據(jù)辩越,傳統(tǒng)的線性分類器使用一條直線將數(shù)據(jù)分類嘁扼,而SVM在使用直線的同時(shí)要求數(shù)據(jù)點(diǎn)距離這條直線的最小距離最大,也就是說分類器和數(shù)據(jù)之間要有足夠大的“間隔”黔攒。這樣做的好處是很明顯的趁啸,越大的“間隔”代表了更大的轉(zhuǎn)圜空間,在得到新的數(shù)據(jù)之后更容易將其正確分類亏钩。
而SVM的工作就是求解這個(gè)最大間隔莲绰,也就是最優(yōu)化問題。對于線性可分的數(shù)據(jù)姑丑,可以直接套用線性規(guī)劃的知識(shí)進(jìn)行推導(dǎo)蛤签,但如果數(shù)據(jù)線性不可分,就需要核函數(shù)進(jìn)行數(shù)據(jù)升維栅哀,進(jìn)行超平面分類震肮。
下面是具體的建模推導(dǎo)過程:
一·決策面方程
我們現(xiàn)在二維場景下考慮分類方程留拾,所以決策面也就是決策線戳晌。
考慮在二維場景下,我們描述一條直線的方法是:
簡單替換痴柔,將替換為
沦偎,將
替換為
,簡單獲得以下公式:
=>
將上述公式轉(zhuǎn)換為向量形式:
也就是
這個(gè)式子的幾何意義是原式子的法向量豪嚎。而如果我們將上述式子推廣到高維空間搔驼,就是我們需要的決策面方程。也就是:
二·分類間隔方程
在獲取決策面方程之后舌涨,我們需要獲知決策面方程中的和
的具體值,而求解這個(gè)值的核心就是靠分類間隔方程所施加的約束條件扔字。
首先我們需要副系以下間隔的含義囊嘉,在SVM中,“間隔”指的是分類器距離樣本點(diǎn)的最小距離革为,我們需要找一個(gè)使這個(gè)最小距離最大的分類器作為我們的最優(yōu)解扭粱。因此我們的約束條件是很好想到的,高中學(xué)過的距離公式:
而在超平面上篷角,只需要簡單的推廣以上公式焊刹,結(jié)合我們之前獲得的決策面方程,
我們不難得到虐块,在我們所得到的直線(超平面上),某個(gè)樣本與其的距離是:
?
分母是指的二范數(shù)嘉蕾,也就是平方和求導(dǎo)贺奠。這樣我們的問題就轉(zhuǎn)化為,求最大的
错忱,其中
儡率,也就是求
。
三·約束條件
獲取了上述分類間隔方程以清,但是這個(gè)方程只是來評判我們的分類器是否是好的儿普,我們并不能確定
(1)分類器是否能正確分類
(2)如何選擇正確的支持向量點(diǎn)
這兩個(gè)問題是限制我們隨意計(jì)算的限制條件,在SVM中掷倔,以下列方式處理這些限制條件眉孩。
首先仍然只考慮線性可分的二分類情況,在這種情況下只有兩類數(shù)據(jù)勒葱,我們對這兩類數(shù)據(jù)分別賦值為1和-1浪汪,也就是:
分類還是很直觀的,事實(shí)上我們在有監(jiān)督學(xué)習(xí)里面基本也這么賦值凛虽。這樣賦值之后死遭,假設(shè)我們所得到的分類器可以正確分類兩類數(shù)據(jù),那么我們的分類器可以得出什么結(jié)果凯旋?不難得到以下形式:
如果我們嚴(yán)格一點(diǎn)(或者說運(yùn)氣很好)呀潭,我們得到的分類器是SVM的最優(yōu)解钉迷,那么根據(jù)上面的距離公式,我們可以簡化得到:
其中:
? ??
分母都是標(biāo)量蜗侈,所以除以并不影響原式子的幾何含義篷牌,也就是法向量。那么我們事實(shí)上拿掉這個(gè)
也不會(huì)影響最后的結(jié)果踏幻。最后對以上式子進(jìn)行整理,即可獲得一個(gè)不等式:
這里的與上文中的
在數(shù)值上不同戳杀,但是在幾何意義上是一樣的该面。
四·優(yōu)化問題描述
在三中,我們考慮了如果我們的分類器可以正確分類信卡,我們的公式要如何進(jìn)行約束隔缀,那么現(xiàn)在我們需要解決第二個(gè)問題了,如果選取支持向量點(diǎn)傍菇?
這個(gè)問題比較好考慮猾瘸,支持向量點(diǎn)有一個(gè)特征,那就是對于一個(gè)支持向量點(diǎn),必然有
那么在我們預(yù)先定義好的距離公式中丢习,我們發(fā)現(xiàn)帶入上式子的結(jié)果牵触,有
那么我們對的最大值約束就變化為對
的最小值約束,也就是求解
五·求解準(zhǔn)備
在得到上述式子之后咐低,我們發(fā)現(xiàn)這是一個(gè)帶有不等式約束的規(guī)劃問題揽思,為了解決這種問題,我們一般采用構(gòu)造拉格朗日函數(shù)的方法见擦,使用對偶性解決問題钉汗。
5.1·拉格朗日函數(shù)
首先,我們先要從宏觀的視野上了解一下拉格朗日對偶問題出現(xiàn)的原因和背景鲤屡。
我們知道我們要求解的是最小化問題损痰,所以一個(gè)直觀的想法是如果我能夠構(gòu)造一個(gè)函數(shù),使得該函數(shù)在可行解區(qū)域內(nèi)與原目標(biāo)函數(shù)完全一致酒来,而在可行解區(qū)域外的數(shù)值非常大卢未,甚至是無窮大,那么這個(gè)沒有約束條件的新目標(biāo)函數(shù)的優(yōu)化問題就與原來有約束條件的原始目標(biāo)函數(shù)的優(yōu)化問題是等價(jià)的問題役首。
這就是使用拉格朗日方程的目的尝丐,它將約束條件放到目標(biāo)函數(shù)中,從而將有約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題衡奥。
隨后爹袁,人們又發(fā)現(xiàn),使用拉格朗日獲得的函數(shù)矮固,使用求導(dǎo)的方法求解依然困難失息。進(jìn)而譬淳,需要對問題再進(jìn)行一次轉(zhuǎn)換,即使用一個(gè)數(shù)學(xué)技巧:拉格朗日對偶盹兢。
所以邻梆,顯而易見的是,我們在拉格朗日優(yōu)化我們的問題這個(gè)道路上绎秒,需要進(jìn)行下面二個(gè)步驟:
將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)
使用拉格朗日對偶性浦妄,將不易求解的優(yōu)化問題轉(zhuǎn)化為易求解的優(yōu)化
下面,進(jìn)行第一步:將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)
先寫下原始式子:
我們首先將其變形见芹,將其變?yōu)槿缦赂袷剑?/p>
其中被稱為拉格朗日乘子剂娄,當(dāng)然雖然名字很嚇唬人,事實(shí)上它是我們隨意引入的一個(gè)參數(shù)玄呛。這個(gè)參數(shù)是用來構(gòu)造等價(jià)問題的阅懦。
我們令。
也就是當(dāng)前這個(gè)方程和無關(guān)徘铝,當(dāng)某個(gè)點(diǎn)
不在可行解區(qū)域中耳胎,也就是
,我們將
設(shè)置為無窮大,顯然此時(shí)
也是無窮大的惕它。而當(dāng)該點(diǎn)在可行域區(qū)域內(nèi)怕午,
,那么
的結(jié)果顯然是
(因?yàn)楹蟀氩糠直厝淮笥诘扔?怠缸,那么為了保證最大诗轻,當(dāng)然是等于0)。這樣揭北,
就可以轉(zhuǎn)化為:
顯然在可行域內(nèi),是一個(gè)凸函數(shù)搔体,是必然有極小值的恨樟,因此問題被轉(zhuǎn)化為求此函數(shù)的最小值,也就是:
這個(gè)式子事實(shí)上也不好求疚俱,因?yàn)閮?nèi)層的仍然帶有不等式的限制條件劝术,因此我們要使用拉格朗日對偶方法將其轉(zhuǎn)化為易求的對偶形式。
5.2 拉格朗日對偶及其證明
拉格朗日對偶的定義如下:
以我們剛剛獲得的式子為例呆奕,我們先針對
作為未知數(shù)構(gòu)造一個(gè)函數(shù):
考慮其極大化养晋,也就是
這個(gè)問題就是原始問題的對偶問題了。假設(shè)我們使
則可以證明
證明方式:對于任意的梁钾,有
不難推論绳泉,當(dāng)時(shí),此時(shí)
均為最優(yōu)解姆泻。
那么如何使得上述相等情況成立呢零酪?這就需要滿足KKT條件冒嫡。
5.3·KKT條件
KKT條件的全稱是Karush-Kuhn-Tucker條件,KKT條件是說最優(yōu)值條件必須滿足以下條件:
條件一:經(jīng)過拉格朗日函數(shù)處理之后的新目標(biāo)函數(shù)L(w,b,α)對x求導(dǎo)為零:
條件二:h(x) = 0四苇;
條件三:α*g(x) = 0孝凌;
我們的式子已經(jīng)滿足此條件,具體的嘛……反正我也不懂月腋,先記下來以后補(bǔ)= =
六·最終結(jié)果
已知
首先固定,針對內(nèi)層最小化求導(dǎo)蟀架,可以得到:
帶入原式:
此時(shí)只有一個(gè)參數(shù),
然后我們計(jì)算外層的最大化罗售,
現(xiàn)在我們的優(yōu)化問題變成了如上的形式辜窑。對于這個(gè)問題,我們有更高效的優(yōu)化算法寨躁,即序列最小優(yōu)化(SMO)算法。我們通過這個(gè)優(yōu)化算法能得到α牙勘,再根據(jù)α职恳,我們就可以求解出w和b,進(jìn)而求得我們最初的目的:找到超平面方面,即"決策平面"放钦。
七·非線性與核函數(shù)
前面六個(gè)部分都是建立在數(shù)據(jù)線性可分的情況之下,而當(dāng)數(shù)據(jù)不可分時(shí)恭金,我們需要使用一些方法將其升維操禀,使其在高維空間成為可分的。
總體而言横腿,經(jīng)過SMO計(jì)算出之后颓屑,可以得到最后的方程:
使用內(nèi)積表示它:
如果數(shù)據(jù)是不可分的,我們使用一個(gè)非線性映射(不管這個(gè)映射是什么樣的耿焊,事實(shí)上往往不知道這是什么映射揪惦,映射獲得的結(jié)果也可能無法計(jì)算)將數(shù)據(jù)映射到高維空間,使其在高維空間可分罗侯,則上式可以改寫為:
其中是一個(gè)映射器腋,它表示輸入空間到特征空間的映射。
這種映射結(jié)果钩杰,牽扯到高維空間的內(nèi)積運(yùn)算纫塌,而高維空間維度越高我們需要的計(jì)算量就越大,有時(shí)候甚至是無限維的讲弄,導(dǎo)致不能直接計(jì)算措左。因此我們定義了一個(gè)核函數(shù)(kernel function),其本質(zhì)是在輸入空間的一個(gè)函數(shù)垂睬,我們?nèi)绻梢允沟?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Ckappa(x_i%2C%20x)%3D%3C%5Cphi(x_i)%2C%5Cphi(x)%3E" alt="\kappa(x_i, x)=<\phi(x_i),\phi(x)>" mathimg="1">媳荒,那么計(jì)算就可以局限在輸入空間的低緯度抗悍,減少計(jì)算資源的消耗。
所以直接就給出一個(gè)定義:核是一個(gè)函數(shù)k钳枕,對所有x,z∈X缴渊,滿足k(x,z)=<?(xi),?(x)>,這里?(·)是從原始輸入空間X到內(nèi)積空間F的映射鱼炒。
在實(shí)際使用中衔沼,有多種比較常見的核函數(shù)形式(所以核函數(shù)實(shí)際上都是一種近似):