記錄記錄，好記性不如爛筆頭膏燃，本系列博客是我以后復習使用，所以沒有按照順序來寫何什。這一篇blog講SVM的兩個難題组哩，一個是拉格朗日乘子，一個是KKT條件。

支持向量機SVM

支持向量機（SVM）伶贰，全稱是support vector machine,簡單來說蛛砰，它是一種二類分類器，基本模型就是在特征空間上尋找間隔最大的線性分類器黍衙，基于這個模型我們更改核函數就可以把它應用于非線性問題之中泥畅，首先我們看他的定義，什么是“在特征空間中尋找間隔最大的線性分類器”琅翻？首先我們應該知道什么是線性分類器位仁，詳情見上一篇博文，其中描述的logistic regression 便是我們的基礎方椎，假設SVM是一個二分類器聂抢，那么顯而易見，我們需要將輸出結果轉換為兩種類別棠众。下面舉一個簡單的例子

二分類問題

圓圈與叉叉分別表示兩種不同的種類琳疏，顯而易見，我們可以通過logistic regression來擬合一條直線分類這兩種不同的類別闸拿，擬合之后他大概長這個樣子空盼。

logistic regression

因為w*x+b輸出的是一個連續(xù)值，比如說0.8,1.5新荤，需要將他同1,-1,0比較我注，上圖中最左邊那條虛線表示的是通過了最近的一個反例，同理最右邊那條虛線表示的是通過了最近的一個正例迟隅，這些被邊緣線通過的點被叫做支持向量但骨，他們是最重要的，哪怕不要其他點智袭。因為他們規(guī)定了正例以及反例的邊緣奔缠。

關于求解SVM時候的拉格朗日乘子以及KKT條件

我們再重新看一遍關于SVM的定義，目的是取得間隔最大化的學習器吼野，當超平面距離數據點越遠時候校哎，分類的確信度也越大，為了讓確信度足夠高我們應該讓所選擇的超平面最大化這個“間隔”值瞳步，兩個經過異類支持向量點的超平面之間距離為2/||w||,就是我們需要最大化的間隔闷哆。如下圖所示

支持向量機

我們的超平面對數據進行正常分類那么必定存在下面的不等式，對于正例y=+1单起，我們的超平面需要將他預測為>=1的情況抱怔，如果y=-1那么我們的超平面需要將他預測為<=-1。

這是很容易理解的嘀倒，當樣例為正例時我們應該把他預測至少=1或者>1,反之也是成立的屈留。那么問題現在就清楚了局冰，我們應該在他滿足正常分類的條件下，求得||w||的最小值灌危，也就是我們想要最大化||w||^2

目標函數與約束條件

上式中w,b是模型參數康二，現在我們面臨的是一個最優(yōu)化問題，怎么求解呢勇蝙？這是一個凸優(yōu)化問題（y(x),h(x)是凸函數沫勿，并且h(x)為仿射函數），我們可以用現成的工具包來解味混，但是我們這里采用的是另一種解法藕帜，可以順勢引出核函數等。
這時候我們需要構造一個拉格朗日函數惜傲，拉格朗日函數就是將約束條件分別和拉格朗日乘子相乘洽故，然后再與目標函數相加，這樣我們的關系式就可以用一個方程標示出來了盗誊，但是我們面臨一個問題时甚，就是約束條件可能是等式，也可能是不等式哈踱，我們要分開考慮兩種情況荒适。

等式約束

考慮一個簡單的問題目標函數f(x) = x1 + x2，等式約束h(x)=x1^2 + x2^2 ?2开镣，求解極小值點刀诬。f(x)在二維平面上畫出等高線（contour）就是一條條斜率相同的直線，h(x)=0在二維平面上畫出等高線就是一個圓邪财，如下圖所示陕壹。可以明顯的看出树埠，在圓圈h(x)的限制下糠馆，直線f(x)的最小值為-2，在左下角直線x1+x2=2和圓的交點上怎憋。

我們從梯度方向考慮一下又碌，如果不考慮限制條件的話，目標函數將會向他梯度的反方向移動绊袋，如下方深藍色箭頭毕匀。但是如果考慮限制的話我們只能取得圓圈上的值那么他只能向h(x)梯度正切方向移動，(注意h(x)函數是那個圓癌别，梯度是指向圓外的)皂岔，紅粗線表示目標函數移動方向，細紅線表示限制函數的梯度规个。

我們可以發(fā)現凤薛，在關鍵的極小值處姓建，我們的目標函數和限制條件的梯度是在一條直線上的诞仓，可能是同向的也可能是反向的缤苫，在極小值點有如下情況

在最小值時候梯度共線

梯度關系

也就是說，我們對于f(x)以及h(x)來說當滿足上面的式子時候墅拭，就是目標函數和限制條件在同一條直線時候活玲，并且此時的h(x)=0（因為是在圓上）時候解得的x就是我們需要的極值點，為了做到上面這個條件谍婉，我們構造一個拉格朗日函數舒憾，對函數令偏導數為0求解，這時候恰好等價于“滿足上面那個式子穗熬，并且h(x)=0”镀迂，那么此時我們求解出來的x就是我們所需要的極值點，和就是拉格朗日乘子法唤蔗。

上面我們提到的求||w||^2的最小值探遵，限制條件是要求正確分類那些點，那么就可以轉換成拉格朗日函數來求解妓柜。

拉格朗日函數

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

不等式約束

在不等式約束中有兩種情況我們需要討論掘殴，這里需要注意以下，很多blog上面都沒有寫清楚為什么g(x)<0情況下約束條件是不起作用的粟誓，參閱了另外一篇博客時候發(fā)現了解釋杯巨，最后寫出參考的blog網址，在不等式約束g(x)<0情況下努酸，我們將極值點情況分為兩類服爷，這是一種分類思想，將極值點分為在約束域中以及約束域外获诈，首先我們來看極值點在約束域內的話是什么情況仍源。

極值點在約束域內

考慮目標函數f(x)=x1²+x2²，不等值約束g(x)=x1²+x2²?1舔涎，顯然f(x)的極小值為原點(0,0)笼踩，落在可行域內⊥鱿樱可行域以原點為圓心嚎于，半徑為1掘而。

極值點在內

極值點在約束域外

考慮目標函數f(x)=(x1?1.1)²+(x2+1.1)² 止潘，不等值約束g(x)=x1²+x2²?1，顯然f(x)的極小值為原點(1.1, -1.1)辫诅，落在可行域外凭戴。可行域以原點為圓心炕矮，半徑為1么夫。這種情況下我們的約束條件是有效的，因為極值點在約束域外吧享，所以我們的取值不能取到全局的極值點魏割，只能取到在約束域上的極小值。

極值點在外

我們可以總結一下不等式情況下有什么特點操灿，我們可以發(fā)現锯仪，不管是極值點在約束域內亦或者是在約束域外，我們都會有這個關系

當極值點在約束域內的時候因為約束條件是沒用的趾盐，所以我們應該讓拉格朗日乘子等于0庶喜，如果極值點在約束域之外的時候存在g(x)=0。

KKT條件

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

KKT條件

上述所有就是我們在求解SVM時候需要考慮的兩個難點丹锹，過了這道坎之后SVM大概也完成了不到一半吧稀颁，后面還有一個SMO算法以及關于核函數的問題芬失，任重而道遠哦~