記錄記錄，好記性不如爛筆頭，本系列博客是我以后復(fù)習(xí)使用，所以沒有按照順序來寫。這一篇blog講SVM的兩個(gè)難題，一個(gè)是拉格朗日乘子，一個(gè)是KKT條件。

支持向量機(jī)SVM

支持向量機(jī)（SVM），全稱是support vector machine,簡(jiǎn)單來說，它是一種二類分類器，基本模型就是在特征空間上尋找間隔最大的線性分類器，基于這個(gè)模型我們更改核函數(shù)就可以把它應(yīng)用于非線性問題之中，首先我們看他的定義，什么是“在特征空間中尋找間隔最大的線性分類器”？首先我們應(yīng)該知道什么是線性分類器，詳情見上一篇博文，其中描述的logistic regression 便是我們的基礎(chǔ)，假設(shè)SVM是一個(gè)二分類器，那么顯而易見，我們需要將輸出結(jié)果轉(zhuǎn)換為兩種類別。下面舉一個(gè)簡(jiǎn)單的例子

二分類問題

圓圈與叉叉分別表示兩種不同的種類，顯而易見，我們可以通過logistic regression來擬合一條直線分類這兩種不同的類別，擬合之后他大概長(zhǎng)這個(gè)樣子。

logistic regression

因?yàn)閣*x+b輸出的是一個(gè)連續(xù)值，比如說0.8,1.5，需要將他同1,-1,0比較，上圖中最左邊那條虛線表示的是通過了最近的一個(gè)反例，同理最右邊那條虛線表示的是通過了最近的一個(gè)正例，這些被邊緣線通過的點(diǎn)被叫做支持向量，他們是最重要的，哪怕不要其他點(diǎn)。因?yàn)樗麄円?guī)定了正例以及反例的邊緣。

關(guān)于求解SVM時(shí)候的拉格朗日乘子以及KKT條件

我們?cè)僦匦驴匆槐殛P(guān)于SVM的定義，目的是取得間隔最大化的學(xué)習(xí)器，當(dāng)超平面距離數(shù)據(jù)點(diǎn)越遠(yuǎn)時(shí)候，分類的確信度也越大，為了讓確信度足夠高我們應(yīng)該讓所選擇的超平面最大化這個(gè)“間隔”值，兩個(gè)經(jīng)過異類支持向量點(diǎn)的超平面之間距離為2/||w||,就是我們需要最大化的間隔。如下圖所示

支持向量機(jī)

我們的超平面對(duì)數(shù)據(jù)進(jìn)行正常分類那么必定存在下面的不等式，對(duì)于正例y=+1，我們的超平面需要將他預(yù)測(cè)為>=1的情況，如果y=-1那么我們的超平面需要將他預(yù)測(cè)為<=-1。

這是很容易理解的，當(dāng)樣例為正例時(shí)我們應(yīng)該把他預(yù)測(cè)至少=1或者>1,反之也是成立的。那么問題現(xiàn)在就清楚了，我們應(yīng)該在他滿足正常分類的條件下，求得||w||的最小值，也就是我們想要最大化||w||^2

目標(biāo)函數(shù)與約束條件

上式中w,b是模型參數(shù)，現(xiàn)在我們面臨的是一個(gè)最優(yōu)化問題，怎么求解呢？這是一個(gè)凸優(yōu)化問題（y(x),h(x)是凸函數(shù)，并且h(x)為仿射函數(shù)），我們可以用現(xiàn)成的工具包來解，但是我們這里采用的是另一種解法，可以順勢(shì)引出核函數(shù)等。
這時(shí)候我們需要構(gòu)造一個(gè)拉格朗日函數(shù)，拉格朗日函數(shù)就是將約束條件分別和拉格朗日乘子相乘，然后再與目標(biāo)函數(shù)相加，這樣我們的關(guān)系式就可以用一個(gè)方程標(biāo)示出來了，但是我們面臨一個(gè)問題，就是約束條件可能是等式，也可能是不等式，我們要分開考慮兩種情況。

等式約束

考慮一個(gè)簡(jiǎn)單的問題目標(biāo)函數(shù)f(x) = x1 + x2，等式約束h(x)=x1^2 + x2^2 ?2，求解極小值點(diǎn)。f(x)在二維平面上畫出等高線（contour）就是一條條斜率相同的直線，h(x)=0在二維平面上畫出等高線就是一個(gè)圓，如下圖所示?？梢悦黠@的看出，在圓圈h(x)的限制下，直線f(x)的最小值為-2，在左下角直線x1+x2=2和圓的交點(diǎn)上。

我們從梯度方向考慮一下，如果不考慮限制條件的話，目標(biāo)函數(shù)將會(huì)向他梯度的反方向移動(dòng)，如下方深藍(lán)色箭頭。但是如果考慮限制的話我們只能取得圓圈上的值那么他只能向h(x)梯度正切方向移動(dòng)，(注意h(x)函數(shù)是那個(gè)圓，梯度是指向圓外的)，紅粗線表示目標(biāo)函數(shù)移動(dòng)方向，細(xì)紅線表示限制函數(shù)的梯度。

我們可以發(fā)現(xiàn)，在關(guān)鍵的極小值處，我們的目標(biāo)函數(shù)和限制條件的梯度是在一條直線上的，可能是同向的也可能是反向的，在極小值點(diǎn)有如下情況

在最小值時(shí)候梯度共線

梯度關(guān)系

也就是說，我們對(duì)于f(x)以及h(x)來說當(dāng)滿足上面的式子時(shí)候，就是目標(biāo)函數(shù)和限制條件在同一條直線時(shí)候，并且此時(shí)的h(x)=0（因?yàn)槭窃趫A上）時(shí)候解得的x就是我們需要的極值點(diǎn)，為了做到上面這個(gè)條件，我們構(gòu)造一個(gè)拉格朗日函數(shù)，對(duì)函數(shù)令偏導(dǎo)數(shù)為0求解，這時(shí)候恰好等價(jià)于“滿足上面那個(gè)式子，并且h(x)=0”，那么此時(shí)我們求解出來的x就是我們所需要的極值點(diǎn)，和就是拉格朗日乘子法。

上面我們提到的求||w||^2的最小值，限制條件是要求正確分類那些點(diǎn)，那么就可以轉(zhuǎn)換成拉格朗日函數(shù)來求解。

拉格朗日函數(shù)

其中第二張圖片中的x就是我們需要求解的變量，也就是上面問題中的w，接下來我們就需要該函數(shù)分別對(duì)x和拉格朗日乘子分別求偏導(dǎo)數(shù)等于0，對(duì)x求偏導(dǎo)為0表示滿足梯度在一條直線，對(duì)拉格朗日乘子求偏導(dǎo)為0表示h(x)=0，這樣求解出來的x就是極值點(diǎn)。

不等式約束

在不等式約束中有兩種情況我們需要討論，這里需要注意以下，很多blog上面都沒有寫清楚為什么g(x)<0情況下約束條件是不起作用的，參閱了另外一篇博客時(shí)候發(fā)現(xiàn)了解釋，最后寫出參考的blog網(wǎng)址，在不等式約束g(x)<0情況下，我們將極值點(diǎn)情況分為兩類，這是一種分類思想，將極值點(diǎn)分為在約束域中以及約束域外，首先我們來看極值點(diǎn)在約束域內(nèi)的話是什么情況。

極值點(diǎn)在約束域內(nèi)

考慮目標(biāo)函數(shù)f(x)=x1²+x2²，不等值約束g(x)=x1²+x2²?1，顯然f(x)的極小值為原點(diǎn)(0,0)，落在可行域內(nèi)?？尚杏蛞栽c(diǎn)為圓心，半徑為1。

極值點(diǎn)在內(nèi)

極值點(diǎn)在約束域外

考慮目標(biāo)函數(shù)f(x)=(x1?1.1)²+(x2+1.1)² ，不等值約束g(x)=x1²+x2²?1，顯然f(x)的極小值為原點(diǎn)(1.1, -1.1)，落在可行域外。可行域以原點(diǎn)為圓心，半徑為1。這種情況下我們的約束條件是有效的，因?yàn)闃O值點(diǎn)在約束域外，所以我們的取值不能取到全局的極值點(diǎn)，只能取到在約束域上的極小值。

極值點(diǎn)在外

我們可以總結(jié)一下不等式情況下有什么特點(diǎn)，我們可以發(fā)現(xiàn)，不管是極值點(diǎn)在約束域內(nèi)亦或者是在約束域外，我們都會(huì)有這個(gè)關(guān)系

當(dāng)極值點(diǎn)在約束域內(nèi)的時(shí)候因?yàn)榧s束條件是沒用的，所以我們應(yīng)該讓拉格朗日乘子等于0，如果極值點(diǎn)在約束域之外的時(shí)候存在g(x)=0。

KKT條件

上面哪個(gè)關(guān)系式子是我們將目標(biāo)函數(shù)轉(zhuǎn)換成為拉格朗日函數(shù)之后的一個(gè)限制條件，并且我們知道在不等式的兩種情況下拉格朗日乘子都是>0的，同樣的這也是拉格朗日函數(shù)的一個(gè)限制條件。如果在凸優(yōu)化問題中這兩個(gè)條件都滿足那么我們求出來的極值點(diǎn)就是全局最小的極值點(diǎn)，如果不是凸優(yōu)化問題那么上述條件只是必要條件不是充分條件，我們求解出來的可能不是全局極值點(diǎn)也可能是駐點(diǎn)。而我們上述的條件就是KKT條件

KKT條件

上述所有就是我們?cè)谇蠼釹VM時(shí)候需要考慮的兩個(gè)難點(diǎn)，過了這道坎之后SVM大概也完成了不到一半吧，后面還有一個(gè)SMO算法以及關(guān)于核函數(shù)的問題，任重而道遠(yuǎn)哦~