正文

kkt點求解（kkt點怎么求）

發(fā)布時間：2023-04-07 17:14:45 稿源：創(chuàng)意嶺閱讀： 142

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關于kkt點求解的問題，以下是小編對此問題的歸納整理，讓我們一起來看看吧。

開始之前先推薦一個非常厲害的Ai人工智能工具，一鍵生成原創(chuàng)文章、方案、文案、工作計劃、工作報告、論文、代碼、作文、做題和對話答疑等等

只需要輸入關鍵詞，就能返回你想要的內容，越精準，寫出的就越詳細，有微信小程序端、在線網頁版、PC客戶端

官網：https://ai.de1919.com。

創(chuàng)意嶺作為行業(yè)內優(yōu)秀的企業(yè)，服務客戶遍布全球各地，如需了解SEO相關業(yè)務請撥打電話175-8598-2043，或添加微信：1454722008

本文目錄:

1、SVM算法原理
2、請問各位大俠如何做二次凸規(guī)劃的求解
3、支持向量機(SVM)基本原理
4、支持向量機（SVM）

kkt點求解（kkt點怎么求）

一、SVM算法原理

一、決策面方程

以二維空間為例，二維空間中任意一條直線方程可以寫為

我們將其向量化，可以得到

設用向量w代表矩陣a1和a2，用向量x代表矩陣x1和x2，標量γ代表b，則方程可化表示為

從方程可知，一個n維空間的超平面在二維空間上的表現，可以是一條直線，或者一個曲線（二維空間中只能看到這個n維超平面穿過而無法看到其模樣），超平面方程即是我們的決策面方程

二、函數間隔和幾何間隔

在SVM監(jiān)督學習中，我們規(guī)定標簽數據為+1和-1兩個值，這么做的目的，可以計算出任意一個樣本點在超平面方程上的表現結果的符號，與標簽符號是否一致來判斷分類的正確性，為此我們可以引入函數間隔的概念

但是當我們成比例的縮放w和γ，函數間隔的值也將成比例的變化，可是超平面的位置并沒有發(fā)生任何變化，所以函數間隔并不是我們想要的分類間隔，為此，我們需要引入幾何間隔的概念

還是以二維空間出發(fā)，任意一點到直線的距離可以寫成

我們將其拓展到n維空間，直線方程即是我們的超平面方程，則n維空間中任何一點到超平面的距離可以寫成

為此，我們引入幾何間隔概念，其中||w||表示向量w的二范數

從幾何間隔可以看出，就算等比例縮放w和γ，由于除上了||w||使得幾何間隔的值不會改變，它只隨著超平面位置的變化而變化，因此，我們要尋找的分類間隔是幾何間隔

三、不等式約束條件

SVM算法的目的是找到一個將分類效果達到最合理化的超平面，這個超平面即是分類器。而評估分類器的好壞的標準就是分類間隔的大小

我們定義分類間隔的距離為d，好的分類器應該讓所有樣本點到決策面的幾何間隔都大于等于d

化簡上式，不等式兩邊同時除以d可得

由于||w||和d都是標量，可定義

則上式可化簡為

在不等式兩邊同時乘以yi，即將兩個式子化簡為一個式子（這里體現了正是因為標簽數據為+1和-1，才方便將約束條件變成一個約束方程）

這個約束方程的意義即是任何樣本點到超平面（分類器）的幾何間隔都大于等于分類間隔

四、SVM最優(yōu)化模型的數學描述

評估分類器的優(yōu)劣是分類間隔的大小，且對于任意樣本點都滿足約束方程

由約束方程可知，當樣本點落在支持向量邊界上有如下關系

則分類間隔d可以表示為支持向量點到超平面的幾何間隔

要讓任何樣本點都在d之外，即求分類間隔d的最大值，則目標函數可以寫成

為了方便在后續(xù)最優(yōu)化處理中對目標函數的求導，我們將目標函數做等效變化

由目標函數是二次的，而約束條件是線性的，則 SVM的數學模型即是：不等式約束條件下的二次型函數優(yōu)化，而求解這一類優(yōu)化問題，接下來我們需要構造拉格朗乘子函數

五、引入拉格朗函數

目標函數是求解在約束條件g(x)下的二次型函數f(x)的最小值，直觀上我們希望構造一個函數L(x)，使得L(x)在f(x)的可行解區(qū)域內的求出的值和f(x)求出的值完全一樣，而在f(x)的可行解區(qū)域外，L(x)的值又接近無窮大，這么做的目的，使得我們可以用一個函數L(x)來等效表示原問題的g(x)和f(x)

拉格朗函數的目的，就是將約束條件融合到目標函數中，構造一個新函數來表示目標函數，將有約束的優(yōu)化問題轉化為無約束的優(yōu)化問題

下面，我們構造拉格朗函數來表示目標函數

其中αi是拉格朗日乘子，每一個約束條件對應一個拉格朗日乘子，其中αi大于等于0

則原優(yōu)化問題可以轉化為

討論如下條件(1)(2)：

(1) 當樣本點不滿足約束條件時，即說明在可行解區(qū)域外

此時將αi置為正無窮大，那么θ(w)顯然也是正無窮大

(2) 當樣本點滿足約束條件時，即說明在可行解區(qū)域內

此時θ(w)的最小值就是原目標函數，于是綜上所述，引入拉格朗乘子函數后，可以得到新的目標函數

我們用p*表示優(yōu)化目標函數后的最優(yōu)解，且與最初的目標函數等價

觀察新的目標函數，如果直接求偏導數求解，那么一上來將面對w和b兩個未知參數，而αi又是不等式約束，求解過程將非常復雜。換一個角度思考，如果將max和min的位置對調，變成如下新的目標函數

上式變化使用了拉格朗日函數的對偶性，交換后的新問題即是原目標函數的對偶問題，我們用d*來表示對偶目標函數的最優(yōu)解，可見d*的求導過程比p*相對容易，且d*<=p*，而當滿足下列條件時，d*= p*

因為目標函數本身已經是一個凸函數，而優(yōu)化問題又是求解最小值，所以目標函數的最優(yōu)化問題就是凸優(yōu)化問題，則接下來就要重點討論KKT條件

六、KKT條件的描述

一個最優(yōu)化模型能夠表示成下列標準形式

其中f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，m和n分別是等式約束和不等式約束的數量

KKT條件即是規(guī)定f(x)的最優(yōu)值必須滿足以下(1)(2)(3)條件，只有滿足KKT條件，目標函數的最優(yōu)化問題依然可以用拉格朗日乘子法解決

很明顯，我們需要優(yōu)化的目標函數屬于帶有不等式約束函數g(x)，所以條件二顯然滿足，下面我們來分析條件一和條件三的理論

七、目標函數的等高線與約束條件的最優(yōu)值分析（條件一）

對于KKT條件一的分析，我們假設目標函數是f(x1,x2)的二元函數，它的圖像在三維空間里是一個曲面，準確的來說是一個凸曲面

其中g(x1,x2)是約束方程，要求目標函數f(x1,x2)的最小值，即轉化為求g(x1,x2)=c這條曲線上的一點，使得f(x1,x2)取得最小值，換個比喻，就是在山上（目標函數曲面）尋找一條山路（約束條件曲線）的最低點

我們畫出目標函數的等高線，來分析目標函數最優(yōu)值和約束條件的關系

對于研究目標函數z=f(x1,x2)，當z取不同的值，即將曲線z投影在(x1,x2)組成的空間中（這里指的是二維空間），也就是曲面的等高線，上圖中d1和d2即是兩條目標函數的等高線，可以看出，當約束函數g(x1,x2)與目標函數的等高線有共同的交點，即證明這組值同時滿足在目標函數的可行域中，也符合約束條件的約束關系

如果等高線與g(x1,x2) 相交，則是一組目標函數的解，但是這個解一定不是最優(yōu)解，因為相交意味著肯定存在其它等高線在該條等高線的內部或者外部，可能會使得新的等高線與g(x1,x2)的交點更大或者更小，這就意味著只有當等高線與g(x1,x2) 相切，才可能得到最優(yōu)解（切線可能多條）

所以最優(yōu)解必須滿足：目標函數的負梯度方向與約束函數的梯度方向一致

而上式恒成立的條件就是：拉格朗日乘子α >= 0 ，且這個式子就是目標函數對各個參數求偏導數的結果，即KKT的第一個條件：目標函數對各個參數的導數為0

八、分類討論約束條件和拉格朗日乘子的組合（條件三）

對于KKT條件三，可以看出，因為所有的約束函數gi(x)<=0，所有的拉格朗日乘子αi>=0，要使得求和后結果為0，要么某個約束函數gi(x)=0，要么其對應的αi=0

從一個案例出發(fā)來分析KKT條件三的邏輯，假設目標函數和約束函數是

將不等式約束構造出拉格朗日函數，并分別對x1和x2求偏導數

而KKT的條件三要求最優(yōu)解滿足 ∑α*g(x) = 0，在這個案例里α和g(x)只有一個，結合條件一，可以得到

根據之前的分析，最優(yōu)值滿足條件三的話，要么α=0，要么g(x)=0

（i）：如果α=0，則x1=1，x2=-2，代入g(x1,x2) =10-1-10*(-2)=29>0，發(fā)現這組解違背了約束函數g(x)<0，則舍棄這組解

（ii）: 如果g(x1,x2)=0，則代入x1和x2的表達式到g(x)中，解出α=58/101>0，發(fā)現這組解不違背約束函數，則代入α解出x1=130/101，x2=88/101，則這組解有可能是最優(yōu)解

綜上(i)(ii)討論，目標函數的最優(yōu)值符合KKT條件三，也說明了滿足強對偶條件的優(yōu)化問題的最優(yōu)值必須滿足KKT條件

九、求解對偶問題

上面分析了目標函數滿足凸優(yōu)化和KKT條件，則問題轉化為求解原問題的對偶問題（即p*=d*）

根據對偶問題描述，先要求內側w和b關于L(w,b,α)的最小化值，即求L對w和b的偏導數

將w和b的偏導數帶入拉格朗函數化簡得

整理一下最終化簡結果為

從上述結果可以看出，樣本的x和y是已知的，此時的 L(w,b,α)函數只有一個變量，即αi

我們歸納一下現在的目標函數為

現在目標函數變成了如上形式，其中αi>=0，這里隱含著一個假設，即數據100%線性可分，但是現實生活中，數據往往是不會那么規(guī)則的線性化，為此我們需要引入松弛變量

十、引入松弛變量

由于現實世界中的數據都是帶有噪音的，也就是數據可能出偏離其正常的位置很遠，而出現這種極端現象后往往會影響超平面的選擇，也許將無法構造出將數據徹底分開的超平面出來

所以對于處理這種情況， SVM需要允許（妥協）出某些噪音很大的數據點能夠偏離超平面，即允許其出現在超平面的錯誤的一側，為此我們引入松弛變量C，這樣我們的目標函數又變?yōu)?/p>

接下來為了研究討論αi的取值范圍，我們加上一個負號將目標函數等價轉化為

十一、討論拉格朗乘子的取值意義和其值域

回顧一下最初的約束條件為

設ui為該約束條件，可以歸納出αi關于約束函數的取值意義

αi只有滿足上述3種情況，才能求出最優(yōu)解，所以當αi與約束條件ui沖突的時候，需要更新這些αi ，這也就是滿足目標函數的第一個約束限制，即0<=αi<=C

而同時目標函數還受到第二個約束條件的限制，即

所以不能只更新一個αi因子，需要同時再次更新第二個αj因子，也就是 α因子總是成對的更新（αi對總是和αj配對），一增一減，此消彼長，才能保證加權和為0的約束，同時這也就是下面提及SMO算法的思想和多元函數化簡為二元函數，在從二元函數化簡為一元函數的難點

根據這個約束和α因子需要成對更新，假設我們選取的兩個拉格朗乘子為α1和α2，則更新之前是old，更新之后是new，且更新前后需要滿足和為0的約束

兩個因子同時更新顯然非常困難，所以需要先求出第一個αj的解，再用αj的解去表示更新第二個αi的解，后文的SMO算法會闡述這一點。因此需要先確定αj的取值范圍，假設L和H分別為它的下界和上界，結合目標函數的約束限制來綜合討論L和H的取值關系

（i）：當y1和y2異號時，可以得到

移項可得a2 = a1 - A，此時α的取值范圍如下圖所示

所以此時α的上下界H和L為

（ii）：當y1和y2同號時，可以得到

移項可得a2 = -a1 + A，此時α的取值范圍如下圖所示

所以此時α的上下界H和L為

綜上(i)(ii)的討論，通過y1和y2的異號或者同號，可以推導出α更新后的上下界分別為

這個公式顯得非常的重要，它將α因子限制在有效的矩形范圍內，在SMO算法中，當我們更新完α后，由于α可能會被更新得很大或很小，因此需要經過裁剪來保證α的在約束條件內

12、SMO算法的思想

回顧之前第九，第十，第十一步的分析，目標函數為

目標函數只包含n個變量α的多元函數，且?guī)в袃蓚€約束條件，我們的目的是求出目標函數的最小值，即找到一組α的組合，使得目標函數取得最小值

由第十一步的分析，我們需要不斷更新這n個α因子，通過迭代來逼近函數達到最小值，但是如果一次性更新n個參數，將會有n!種組合，那么時間復雜度將會非常高，為此我們首先想到坐標上升（下降）法

來通過一個例子來說明坐標上升法的思路

可知案例中要求一個三元函數的最大值，算法的思想是每次迭代時只更新一個維度，通過多次迭代直到收斂來優(yōu)化函數的最值，求出三個變量的偏導數推出其關系

通過迭代即就可以求出其最值

SMO算法借鑒了坐標上升（下降）法的思想來優(yōu)化α因子組合，但是由于目標函數的第二個約束條件有加權和為0的限制，導致每次迭代時候不能只更新一個因子αi，必須同時更新與之配對的另一個因子αj，此消彼長才能保證加權和為0（第十一步中已提及）

所以SMO算法思想是將原始問題中，求解n個參數的二次規(guī)劃問題，分解成了多個子二次規(guī)劃問題來分別求解，每一個子問題只需要求解2個參數，即將多元函數推導為二元函數，再將二元函數推導為一元函數

13、多元函數推導為二元函數

目標函數是關于α的N元函數，通過SMO的算法思想，假設每次迭代更新，選取一對α1和α2的組合，其余的乘子不變，首先需要將α1和α2從目標函數中分離出來，也就是將多元函數推導為二元函數

從N元函數中分離出α1和α2因子

由于上式推導結果過于復雜，我們定義2個表達式來表示上式常量部分，用來簡化上式

又由于單獨存下的常數項對以后的求導沒有貢獻，所以我們提出單獨的常數項定義為Constant

帶入vi和Constant表達式，則結果化簡為

至此，我們將多元函數推導為含有α1和α2變量的二元函數，接下來將這個二元函數推導為一元函數

14、二元函數推導為一元函數

我們需要推導出α1和α2的關系，然后用α2來表示α1帶入二元函數，就可以推導出關于α2的一元函數了

由目標函數的第二個約束條件

同理根據SMO算法思想，從約束條件中分離出α1和α2

將等式兩邊同時乘以y1，可推導出α1和α2的關系

同理，我們定義兩個表達式r和s來表示上式的常量部分，用來簡化上式關系

帶入r和s后，α1和α2的關系推導為

下面將α1帶入我們的二元函數中，可得

至此，我們將二元函數推導為只含有一個變量α2的一元函數，接下來終于可以對目標函數求導了

15、求解一元函數的偏導數，推導出第一個拉格朗乘子的遞推關系

我們對一元函數求α2的偏導數為0

帶入s=y1*y2和y2*y2=1，整理上式可求出α2

二、請問各位大俠如何做二次凸規(guī)劃的求解

二次規(guī)劃（Quadratic programming），在運籌學當中，是一種特殊類型的最佳化問題。

[編輯] 簡介二次規(guī)劃問題可以以下形式來描述：

f(x) = (1 / 2)xTQx + cTx

受到一個或更多如下型式的限制條件：

Ex = d

vT 是 v 的轉置。

如果Q是半正定矩陣，那么f(x)是一個凸函數。如果有至少一個向量x滿足約束而且f(x)在可行域有下界，二次規(guī)劃問題就有一個全局最小值x。如果Q是正定矩陣，那么全局最小值就是唯一的。如果Q=0，二次規(guī)劃問題就變成線性規(guī)劃問題。

根據優(yōu)化理論，一個點x 成為全局最小值的必要條件是滿足 Karush-Kuhn-Tucker(KKT)條件。當f(x)是凸函數時，KKT條件也是充分條件。

當二次規(guī)劃問題只有等式約束時，二次規(guī)劃可以用線性方程求解。否則的話，常用的二次規(guī)劃解法有：內點法(interior point)、active set和共軛梯度法等。凸集二次規(guī)劃問題是凸優(yōu)化問題的一個特例。

[編輯] 對偶每個二次規(guī)劃問題的對偶問題也是二次規(guī)劃問題。我們以正定矩陣Q為例：

L(x,λ) = (1 / 2)xTQx + λT(Ax ? b) + cTx

對偶問題g(λ)，可定義為

我們可用 : 得到L的極小

x * = ? Q ? 1(ATλ + c),

對偶函數：

g(λ) = ? (1 / 2)λTAQ ? 1ATλ ? cTQ ? 1ATλ ? bTλ

對偶問題為：

maximize : ? (1 / 2)λTAQ ? 1ATλ ? (ctQ ? 1AT + bT)λ

subject to :

計算復雜性當Q正定時，用橢圓法可在多項式時間內解二次規(guī)劃問題。當Q負定時，二次規(guī)劃問題是NP困難的(NP-Hard)。即使Q 存在一個負特征值時，二次規(guī)劃問題就是NP困難的。

三、支持向量機(SVM)基本原理

看了很多關于SVM的博客，但是常常只能保存書簽之后看，有時候有的博客就突然沒了，這里就作為搬運工總結一下之后自己看吧。主要內容來自于：

支持向量機通俗導論（理解SVM的三層境界）

線性回歸

給定數據集 , 其中, ,線性回歸試圖學習到一個線性模型,盡可能地輸出正確標記.

如果我們要用線性回歸算法來解決一個分類問題,(對于分類,y 取值為 0 或者 1),但如果你使用的是線性回歸,那么假設函數的輸出值可能遠大于 1,或者遠小于 0,就算所有訓練樣本的標簽 y 都是 0 或 1但是如果算法得到的值遠大于 1 或者遠小于 0 的話,就會感覺很奇怪。所以我們在接下來的要研究的算法就叫做邏輯回歸算法,這個算法的性質是:它的輸出值永遠在 0 到 1 之間。

所以邏輯回歸就是一個分類算法,這個算法的輸出值永遠在 0 到 1 之間.

我們先看二分類的LR,具體做法是:利用sigmoid 函數,將每一個點的回歸值映射到0,1之間.sigmoid函數特性如下:

如圖所示,令 , 當 z > 0 , z 越大, sigmoid 返回值越接近1(但永遠不會超過1). 反之,當z < 0時,z 越小, sigmoid 返回值越接近0(但永遠不會小于0).

支持向量機 ，因其英文名為support vector machine，故一般簡稱SVM，通俗來講，它是一種二類分類模型，其基本模型定義為 特征空間 上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規(guī)劃問題的求解。

線性分類器

給定一些數據點，它們分別屬于兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：

logistic回歸目的是從特征學習出一個0/1分類模型，而這個模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數）將自變量映射到(0,1)上，映射后的值被認為是屬于y=1的概率。

假設函數:

其中x是n維特征向量，函數g就是logistic函數。

圖像為：

在超平面w x+b=0確定的情況下，|w x+b|能夠表示點x到距離超平面的遠近，而通過觀察w x+b的符號與類標記y的符號是否一致可判斷分類是否正確，所以，可以用(y (w*x+b))的正負性來判定或表示分類的正確性。于此，我們便引出了函數間隔（functional margin）的概念。

定義函數間隔（用表示）為

而超平面(w，b)關于T中所有樣本點(xi，yi)的函數間隔最小值（其中，x是特征，y是結果標簽，i表示第i個樣本），便為超平面(w, b)關于訓練數據集T的函數間隔：

但這樣定義的函數間隔有問題，即如果成比例的改變w和b（如將它們改成2w和2b），則函數間隔的值f(x)卻變成了原來的2倍（雖然此時超平面沒有改變），所以只有函數間隔還遠遠不夠。

事實上，我們可以對法向量w加些約束條件，從而引出真正定義點到超平面的距離--幾何間隔（geometrical margin）的概念。

假定對于一個點 x ，令其垂直投影到超平面上的對應點為 x0 ，w 是垂直于超平面的一個向量，為樣本x到超平面的距離，如下圖所示：

根據平面幾何知識，有

其中||w||為w的二階范數（范數是一個類似于模的表示長度的概念），是單位向量（一個向量除以它的模稱之為單位向量）。

又由于x0 是超平面上的點，滿足 f(x0)=0，代入超平面的方程 ,可得，即

隨即讓此式的兩邊同時乘以，再根據和，即可算出：

為了得到的絕對值，令乘上對應的類別 y，即可得出幾何間隔（用表示）的定義：

從上述函數間隔和幾何間隔的定義可以看出：幾何間隔就是函數間隔除以||w||，而且函數間隔y (wx+b) = y f(x)實際上就是|f(x)|，只是人為定義的一個間隔度量，而幾何間隔|f(x)|/||w||才是直觀上的點到超平面的距離。

對一個數據點進行分類，當超平面離數據點的“間隔”越大，分類的確信度（confidence）也越大。所以，為了使得分類的確信度盡量高，需要讓所選擇的超平面能夠最大化這個“間隔”值。這個間隔就是下圖中的Gap的一半。

通過由前面的分析可知：函數間隔不適合用來最大化間隔值，因為在超平面固定以后，可以等比例地縮放w的長度和b的值，這樣可以使得的值任意大，亦即函數間隔可以在超平面保持不變的情況下被取得任意大。但幾何間隔因為除上了，使得在縮放w和b的時候幾何間隔的值是不會改變的，它只隨著超平面的變動而變動，因此，這是更加合適的一個間隔。換言之，這里要找的最大間隔分類超平面中的“間隔”指的是幾何間隔。

于是最大間隔分類器（maximum margin classifier）的目標函數可以定義為

同時需滿足一些條件，根據間隔的定義，有

回顧下幾何間隔的定義，可知：如果令函數間隔等于1（之所以令等于1，是為了方便推導和優(yōu)化，且這樣做對目標函數的優(yōu)化沒有影響），則有 = 1 / ||w||且，從而上述目標函數轉化成了：

相當于在相應的約束條件下，最大化這個1/||w||值，而1/||w||便是幾何間隔。

據了解，

由于這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變量 (dual variable) 的優(yōu)化問題，即通過求解與原問題等價的對偶問題（dual problem）得到原始問題的最優(yōu)解，這就是線性可分條件下支持向量機的對偶算法，這樣做的優(yōu)點在于：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。

那什么是拉格朗日對偶性呢？簡單來講，通過給每一個約束條件加上一個拉格朗日乘子 ,（Lagrange multiplier），定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）

然后令：

容易驗證，當某個約束條件不滿足時，例如，那么顯然有（只要令即可）。而當所有約束條件都滿足時，則最優(yōu)值為，亦即最初要最小化的量。

因此，在要求約束條件得到滿足的情況下最小化，實際上等價于直接最小化（當然，這里也有約束條件，就是 ≥0,i=1,…,n），因為如果約束條件沒有得到滿足，會等于無窮大，自然不會是我們所要求的最小值。

具體寫出來，目標函數變成了：

這里用表示這個問題的最優(yōu)值，且和最初的問題是等價的。如果直接求解，那么一上來便得面對w和b兩個參數，而又是不等式約束，這個求解過程不好做。不妨把最小和最大的位置交換一下，變成：

交換以后的新問題是原始問題的對偶問題，這個新問題的最優(yōu)值用來表示。而且有 ≤ ，在滿足某些條件的情況下，這兩者相等，這個時候就可以通過求解對偶問題來間接地求解原始問題。

換言之，之所以從minmax 的原始問題，轉化為maxmin 的對偶問題，一者因為是的近似解，二者，轉化為對偶問題后，更容易求解。

下面可以先求L 對w、b的極小，再求L對的極大。

KKT條件

≤ 在滿足某些條件的情況下，兩者等價，這所謂的“滿足某些條件”就是要滿足KKT條件。

要讓兩者等價需滿足strong duality （強對偶），而后有學者在強對偶下提出了KKT條件，且KKT條件的成立要滿足constraint qualifications，而constraint qualifications之一就是Slater條件。所謂Slater 條件，即指：凸優(yōu)化問題，如果存在一個點x，使得所有等式約束都成立，并且所有不等式約束都嚴格成立（即取嚴格不等號，而非等號），則滿足Slater 條件。對于此處，Slater 條件成立，所以 ≤ 可以取等號。

一般地，一個最優(yōu)化數學模型能夠表示成下列標準形式：

其中，f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，p和q分別為等式約束和不等式約束的數量。

KKT條件的意義：它是一個非線性規(guī)劃（Nonlinear Programming）問題能有最優(yōu)化解法的必要和充分條件。

而KKT條件就是指上面最優(yōu)化數學模型的標準形式中的最小點 x* 必須滿足下面的條件：

我們這里的問題是滿足 KKT 條件的（首先已經滿足Slater條件，再者f和gi也都是可微的，即L對w和b都可導），因此現在我們便轉化為求解第二個問題。

也就是說，原始問題通過滿足KKT條件，已經轉化成了對偶問題。而求解這個對偶學習問題，分為3個步驟：首先要讓L(w，b，a) 關于 w 和 b 最小化，然后求對的極大，最后利用SMO算法求解對偶問題中的拉格朗日乘子。

對偶問題求解的3個步驟

將以上結果代入之前的L：

得到：

具體推導過程是比較復雜的，如下所示：

最后，得到：

“倒數第4步”推導到“倒數第3步”使用了線性代數的轉置運算，由于ai和yi都是實數，因此轉置后與自身一樣。“倒數第3步”推導到“倒數第2步”使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運算法則。最后一步是上一步的順序調整。

從上面的最后一個式子，我們可以看出，此時的拉格朗日函數只包含了一個變量，那就是（求出了便能求出w，和b，由此可見，則核心問題：分類函數也就可以輕而易舉的求出來了）。

上述式子要解決的是在參數上求最大值W的問題，至于和都是已知數。要了解這個SMO算法是如何推導的，請?zhí)较挛牡?.5節(jié)、SMO算法。

總結

讓我們再來看看上述推導過程中得到的一些有趣的形式。首先就是關于我們的 hyper plane ，對于一個數據點 x 進行分類，實際上是通過把 x 帶入到算出結果然后根據其正負號來進行類別劃分的。而前面的推導中我們得到:

因此分類函數為：

這里的形式的有趣之處在于，對于新點 x的預測，只需要計算它與訓練數據點的內積即可（表示向量內積），這一點至關重要，是之后使用 Kernel 進行非線性推廣的基本前提。此外，所謂 Supporting Vector 也在這里顯示出來——事實上，所有非Supporting Vector 所對應的系數都是等于零的，因此對于新點的內積計算實際上只要針對少量的“支持向量”而不是所有的訓練數據即可。

為什么非支持向量對應的等于零呢？直觀上來理解的話，就是這些“后方”的點——正如我們之前分析過的一樣，對超平面是沒有影響的，由于分類完全有超平面決定，所以這些無關的點并不會參與分類問題的計算，因而也就不會產生任何影響了。

回憶一下我們通過 Lagrange multiplier得到的目標函數：

注意到如果 xi 是支持向量的話，上式中紅顏色的部分是等于 0 的（因為支持向量的 functional margin 等于 1 ），而對于非支持向量來說，functional margin 會大于 1 ，因此紅顏色部分是大于零的，而又是非負的，為了滿足最大化，必須等于 0 。這也就是這些非Supporting Vector 的點的局限性。

至此，我們便得到了一個maximum margin hyper plane classifier，這就是所謂的支持向量機（Support Vector Machine）。當然，到目前為止，我們的 SVM 還比較弱，只能處理線性的情況，不過，在得到了對偶dual 形式之后，通過 Kernel 推廣到非線性的情況就變成了一件非常容易的事情了(通過求解對偶問題得到最優(yōu)解，這就是線性可分條件下支持向量機的對偶算法，這樣做的優(yōu)點在于：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題”)。

事實上，大部分時候數據并不是線性可分的，這個時候滿足這樣條件的超平面就根本不存在。在上文中，我們已經了解到了SVM處理線性可分的情況，那對于非線性的數據SVM咋處理呢？對于非線性的情況，SVM 的處理方法是選擇一個核函數 κ(⋅,⋅) ，通過將數據映射到高維空間，來解決在原始空間中線性不可分的問題。

具體來說，在線性不可分的情況下，支持向量機首先在低維空間中完成計算，然后通過核函數將輸入空間映射到高維特征空間，最終在高維特征空間中構造出最優(yōu)分離超平面，從而把平面上本身不好分的非線性數據分開。如圖所示，一堆數據在二維空間無法劃分，從而映射到三維空間里劃分：

而在我們遇到核函數之前，如果用原始的方法，那么在用線性學習器學習一個非線性關系，需要選擇一個非線性特征集，并且將數據寫成新的表達形式，這等價于應用一個固定的非線性映射，將數據映射到特征空間，在特征空間中使用線性學習器，因此，考慮的假設集是這種類型的函數：

這里ϕ：X->F是從輸入空間到某個特征空間的映射，這意味著建立非線性學習器分為兩步：

首先使用一個非線性映射將數據變換到一個特征空間F，

然后在特征空間使用線性學習器分類。

而由于對偶形式就是線性學習器的一個重要性質，這意味著假設可以表達為訓練點的線性組合，因此決策規(guī)則可以用測試點和訓練點的內積來表示：

如果有一種方式可以在特征空間中直接計算內積〈φ(xi · φ(x)〉，就像在原始輸入點的函數中一樣，就有可能將兩個步驟融合到一起建立一個非線性的學習器，這樣直接計算法的方法稱為核函數方法：

核是一個函數K，對所有x，z，滿足，這里φ是從X到內積特征空間F的映射。

來看個核函數的例子。如下圖所示的兩類數據，分別分布為兩個圓圈的形狀，這樣的數據本身就是線性不可分的，此時咱們該如何把這兩類數據分開呢(下文將會有一個相應的三維空間圖)？

事實上，上圖所述的這個數據集，是用兩個半徑不同的圓圈加上了少量的噪音生成得到的，所以，一個理想的分界應該是一個“圓圈”而不是一條線（超平面）。如果用和來表示這個二維平面的兩個坐標的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：

注意上面的形式，如果我們構造另外一個五維的空間，其中五個坐標的值分別為，那么顯然，上面的方程在新的坐標系下可以寫作：

關于新的坐標，這正是一個 hyper plane 的方程！也就是說，如果我們做一個映射，將按照上面的規(guī)則映射為，那么在新的空間中原來的數據將變成線性可分的，從而使用之前我們推導的線性分類算法就可以進行處理了。這正是 Kernel 方法處理非線性問題的基本思想。

再進一步描述 Kernel 的細節(jié)之前，不妨再來看看上述例子在映射過后的直觀形態(tài)。當然，你我可能無法把 5 維空間畫出來，不過由于我這里生成數據的時候用了特殊的情形，所以這里的超平面實際的方程是這個樣子的（圓心在軸上的一個正圓）

因此我只需要把它映射到，這樣一個三維空間中即可，下圖即是映射之后的結果，將坐標軸經過適當的旋轉，就可以很明顯地看出，數據是可以通過一個平面來分開的

核函數相當于把原來的分類函數：

映射成：

而其中的可以通過求解如下 dual 問題而得到的：

這樣一來問題就解決了嗎？似乎是的：拿到非線性數據，就找一個映射

四、支持向量機（SVM）

參考Jerrylead 和 july-支持向量機通俗導論

再回憶一下邏輯回歸：Logistic回歸目的是從特征學習出一個0/1分類模型，而 這個模型是將特征的線性組合作為自變量 ，由于自變量的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數） 將自變量映射到(0,1)上，映射后的值被認為是屬于y=1的概率 。

中間那條線是θ T x=0，logistic回歸強調 所有點 盡可能地遠離中間那條線。學習出的結果也就中間那條線。

但是：

考慮上面3個點A、B和C。從圖中我們可以確定A是×類別的， 然而C我們是不太確定的 ，B還算能夠確定。這樣我們可以得出結論， 我們更應該關心靠近中間分割線的點，讓他們盡可能地遠離中間線，而不是在所有點上達到最優(yōu)（引出了下面的函數間隔與幾何間隔） 。

我想這就是支持向量機的思路和logistic回歸的不同點：

支持向量機考慮局部（不關心已經確定遠離的點），

邏輯回歸一個考慮全局（已經遠離的點可能通過調整中間線使其能夠更加遠離，但是也可能使一部分點靠近中間線來換取另外一部分點更加遠離中間線。）

上面已經知道，θ T x=0是分類的線，在svm中，只考慮局部，只考慮θ T x的正負問題，而不用關心g（z）。因此，在這里，用w T x+b代替θ T x，并 對g(z)做一個簡化 ，將其簡單映射到類別標簽y=1和y=-1上。

這里的y取值為1和-1（在svm中，只考慮局部，只考慮θ T x的正負問題），是為了方便定義：在分類正確的情況下，函數間隔（確信度）的大小

比如，在分類正確的情況下，y等于1，wx+b應該為正數越大，則情況越好，是正例的確定度就越大。就如上圖的A點。y等于-1，wx+b應該為負數越大，則情況越好是負例的確信度就越大。

所以， 函數間隔越大，說明分類正確的置信度越大。函數間隔越小，比如上圖c點，說明越不能確定c點屬于哪一類。

可以為別的值，只是為了方便。這一點在參考的第二個博客上也已經說明了。

由上面解釋，已知可以用y(wT x + b) 的正負性來判定（或表示）分類的正確性。

定義函數間隔如下：

也就是，這個樣本點x與超平面之間的間隔（但是現在有些不準確，所以有下面的幾何間隔）。

此時，若根據SVM的思想，最大化這個間隔，就能提高分類正確的確信度了嗎？

答案是否定的，因為，如果成比例的改變w 和b（如將它們改成2w 和2b），則函數間隔的值f(x) 卻變成了原來的2 倍（ 雖然函數值增大了，達到了目標，但是此時超平面沒有改變 ），所以只有函數間隔還遠遠不夠。

我們真正關心的，其實是“幾何上”的點到平面的距離，于是可以用幾何知識推理出來的幾何間隔。 而不是一開始人們想當然定義的函數間隔。

事實上，我們可以對法向量w 加些約束條件（ 這就是調優(yōu)問題的思考了 )，從而引出真正定義點到超平面的距離——幾何間隔（geometrical margin）的概念。

又因為x 0 是超平面w T x + b=0上的點，利用向量之間的運算

再令上式乘上對應的類別y，即可得出幾何間隔

從上述函數間隔和幾何間隔的定義可以看出：幾何間隔就是函數間隔除以∥w∥，而 函數間隔實際上就是，只是人為定義的一個間隔度量，而幾何間隔才是直觀上的點到超平面的距離。

接下來就是我們的目標：尋找一個超平面， 使得離超平面比較近的點能有更大的間距。 也就是我們不考慮所有的點都必須遠離超平面，我們關心求得的超平面能夠讓所有點中離它最近的點具有最大間距。也就是找到最大的幾何間隔。

由上一小節(jié)可以知道，我們這里要找的最大間隔分類超平面中的“間隔”指的是幾何間隔。

上面兩個式子的意思是（ 注意，函數間距上面是折線，幾何間距上面是波浪線 ）：

最大化幾何間隔

約束條件是，每個樣例的函數間隔都要大于全局的那一個函數間隔（也就是所有訓練集里的最小的那個）

用函數間隔表示幾何間隔

于是得到了這個式子：

然而這個時候目標函數不是凸函數，約束條件也不是線性的，沒法直接代入優(yōu)化軟件里計算。我們還要改寫。前面說到 同時擴大w和b對結果沒有影響 ，因此，我們將全局的函數間隔值定義為1。于是，上述的函數轉變成了

由于求1/||w||的最大值，相當于求||w||²的最小值，因此結果為：

因為現在的 目標函數是二次的，約束條件是線性的，所以它是一個凸二次規(guī)劃問題 。這個問題可以用現成的QP (Quadratic Programming) 5優(yōu)化包進行求解。一言以蔽之：在一定的約束條件下，目標最優(yōu)，損失最小。

根據前面幾個文章的話，SVM作為判別模型，它的的模型，就是 w T x i + b 。參數就是w和b。學習完參數以后，新來的樣例作為x i ，得到結果大于1，說明在超平面上面，所以是正例。反之亦然。

根據SVM的思想，SVM的初步目標函數，就是所有樣例的幾何間隔盡可能的大

至此，得到了SVM的目標函數，算是初步解決了SVM的這個問題，用優(yōu)化包求解得到wb，即可得到具有最大幾何間距的超平面，提高分類每個點的確信度，分類目標完成。

接下來介紹的是手工求解w和b的方法了，一種更優(yōu)的求解方法。

從上可以看出，就同時擴大w和b就相當于等式兩邊同時除以函數間隔 γ，而新的w和b仍然是舊的wb的函數，所以最大化仍然可以進行。

效果等價于，令函數間隔γ=1，綜上所述，零γ=1是合理的，而且也方便了原優(yōu)化問題的計算 。

由拉格朗日對偶（線性可分條件下SVM的對偶算法）引入核函數（非線性可分條件下SVM的算法）

上一篇說到，得到了 如下的線性可分的SVM的目標函數 ，可以利用優(yōu)化包進行求解。

此外，由于這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變量(dual variable) 的優(yōu)化問題，即通過求解與原問題等價的對偶問題（dual problem）得到原始問題的最優(yōu)解，這就是線性可分條件下支持向量機的對偶算法。

引入對偶的優(yōu)點：

因為 引入拉格朗日算子可以求出極值。 （參考最優(yōu)化方法的解釋）

這種極值問題怎么求

首先，同樣定義拉格朗日公式，希望可以利用拉格朗日算子法求得最優(yōu)解，得到：

但是，出現問題了，此時加入的約束條件g已經不再等于0了，所以，此時可以調整算子alpha變成很大很大的值，使結果負無窮， 這顯然是不合理的。

所以，我們需要 排除在滿足條件下，也會無解的情況。

因此，我們定義下面的函數

要看這個函數有什么優(yōu)點，就要看看這個函數相比于L(ω,α,b)有什么變化： 加了max，加了α I 大于等于零。

所以，當g和h不滿足約束時，總可以調整α i 和β i 來使thetap具最大值為正無窮。

只有當g和h滿足約束時，此時g<0，我們可以調整α i 和β i （使α i 等于0，β i 任意），得到最大值，即θ p =f(w)。

于是函數等價于這樣

于是原來的極值問題min f(w) 就等價于求min θ p 了，

即：

也就是說，最小化 θ p ，就是為了得到最小的 f(w)，而能有f(w)就說明了滿足約束條件。所以這個等價于原來的極值問題。

至此， 相比于拉格朗日公式L(ω,α,b)，現在即加入了拉格朗日算子，又排除了純粹的拉格朗日公式中出現無窮的情況。

但是，又出現了新的問題，也就是，如果直接求解，首先面對的就是兩個參數（最里面的是max，這個max問題有兩個參數），而且alpha也是不等式約束，再在w上求最小值，這個過程并不容易做。那么應該怎么辦呢？

在最優(yōu)化課程里，當遇到不好解的優(yōu)化問題時，可以轉化為原問題的對偶問題試試。

此處，d代表對偶。D--dual

我們定義函數

θ D 將問題轉化為先求L(ω,α,b)關于 ω 的最小值（此時α和β是固定值），之后再求θ D 的最大值。 上來面對的是一個參數，相對簡單些。

相對于原問題，更換了min和max的順序，得到了它的對偶問題。

--------------------------------------------------------------------------------------------------------------

一般的更換順序的結果是MaxMin(X) <= MinMax(X)。也就是，此時有

對偶問題已經表示出來了，這個對偶問題也相對原問題好求，那么，這兩個問題等價嗎？或者說，對偶問題的解是不是原問題的解呢？

需要用KKT條件來判斷了。

對于拉格朗日算子的深入理解可以看看《最優(yōu)化方法》，講義的最后一頁。

含有不等式約束的問題，常常 用KKT條件求得候選最優(yōu)解

對于一般化的拉格朗日公式：

最優(yōu)值 w 必須滿足以下三個條件：

----------1、L對 w 求導為零

----------2、h(w)=0

----------3、α i g i =0 ，i = 1，...，k

注意此時

第三個條件表明了KKT的思想：極值會在可行域邊界取得。 ----解釋：

-----對于一個特定的自變量w1，當自變量w1在 第 i 個 可行域邊界（g i (w1)=0）時，說明此時這個約束是起到了作用的。 這個約束是w1被g i 約束了。此時只能到g i 的平面上（即邊界），再多就出界了。。。 而對于最優(yōu)解來說，就是f(w)達到最優(yōu)，所以L中，除了f(w)部分，其余應該都等于0，所以此時α>0(或許等于零也可以？疑問）

----而此時，w1在其他的約束條件g 非i 下，有g 非i (w1)<0），說明W1可以隨意些，說明此時這個約束并沒有起到作用，但是作為最優(yōu)解，為了 除了f(w)部分，其余應該都等于0 ，所以其系數α應該等于零。

----------------------------------------------------------------------------------------

注意：這個是傳統(tǒng)最優(yōu)化問題的一般式，這個問題有k個不等式約束方程，所有的點都要滿足這k個不等式約束。 。假設有一百個樣本點，只有有三個極值N1，N2，N3，那么說明其余97個點帶入這k個方程中去都會小于零。另外對于這三個極值點，可能會有g i (N1) = 0,除了第i個g以外，g(N1)都小于0 。然后對于極值N2，g j (N2)=0，除了第j個約束以外，其余的g(N2)都小于0。

而本節(jié)一開始討論的問題，只有一個約束方程（因為參數只有w和b）即：y（w T x+b）>=1，所有的點（一共m個）都要滿足這個約束方程。 而關于為什么非支持向量的系數alpha會等于零呢？也就是相當于前面的，k=1（有k個約束條件）的情況下，m個樣本點中，非支持向量的約束g<0，為了最優(yōu)解，除了f(w)應該都等于零，所以alpha應該等于零。

另外可以參考這段話：

即，若d* = p* <==> x * 滿足KKT條件

由上面那句話可以知道，

折騰這么長時間，也就是為了說明，已經知道原問題

是凸優(yōu)化問題，所以，只要對偶問題的自變量w滿足了KKT條件，那么它就是對偶問題的最優(yōu)解w * ，同時也是原問題的最優(yōu)解了。

所以，由上可知，只要解出了2.1.3中的問題的參數w和b，也就是原問題的解了。

重新回到SVM的優(yōu)化問題（其中每個約束式實際就是一個訓練樣本）：

我們將約束條件改寫為拉格朗日的形式：

由KKT條件可知，只有當函數間隔是1（g=0）的時候，α i >0。此時，這個樣例 w i 在約束平面上受到約束。對于其它的不在線上的樣例點（g<0），極值不會在其范圍內去的，所以這些樣例點前面的系數α i =0.

實線是最大間隔超平面，假設×號的是正例，圓圈的是負例。在虛線上的點就是函數間隔是1的點，他們前面的系數α i >0， 這三個點被稱作支持向量。

由上面問題，構造拉格朗日函數如下（沒有等式約束，所以沒有β）：

————————————————————————————————