kkt條件推導(dǎo)（kkt條件推導(dǎo)的一定收斂嗎）

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關(guān)于kkt條件推導(dǎo)的問題，以下是小編對此問題的歸納整理，讓我們一起來看看吧。

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

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

官網(wǎng)：https://ai.de1919.com。

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

本文目錄:

• 1、支持向量機—從推導(dǎo)到python手寫

• 2、筆記：支持向量機

• 3、最優(yōu)化問題求解方法

• 4、小球大間隔模型存在的對偶問題

一、支持向量機—從推導(dǎo)到python手寫

筆者比較懶能截圖的地方都截圖了。

支持向量機分為三類：

（1）線性可分支持向量機，樣本線性可分，可通過硬間隔最大化訓練一個分類器。

（2）線性支持向量機，樣本基本線性可分，可通過軟間隔最大化訓練一個分類器。

（3）非線性支持向量機，樣本線性不可分，可通過核函數(shù)和軟間隔最大化訓練一個分類器。

上面最不好理解的恐怕就是硬間隔和軟間隔了，

說白了硬間隔就是說存在這么一個平面，可以把樣本完全正確無誤的分開，當然這是一種極理想的情況，現(xiàn)實中不存在，所以就有了軟間隔。

軟間隔說的是，不存在一個平面可以把樣本完全正確無誤的分開，因此呢允許一些樣本被分錯，怎么做呢就是加入松弛變量，因為希望分錯的樣本越小越好，因此松弛變量也有約束條件。加入松弛變量后，問題就變?yōu)榫€性可分了，因為是每一個樣本都線性可分，因此松弛變量是針對樣本的，每一個樣本都對應(yīng)一個不同的松弛變量。

其實感知機說白了就是找到一條直線把樣本點分開，就是上方都是一類，下方是另一類。當然完全分開是好事，往往是不能完全分開的，因此就存在一個損失函數(shù)，就是誤分類點到這個平面的距離最短：

這里啰嗦一句，誤分類點y*(wx+b)<0，所以加個負號在前邊。

一般情況下||w||都是可以縮放，那么我們把它縮放到1，最后的目標函數(shù)就變成了

間隔就是距離，我們假設(shè)分離超平面為 ，那么樣本點到這個平面的距離可以記為 。我們都知道通過感知機劃分的點，超平面上方的點 ，下方的點 ，然后通過判斷 的值與y的符號是否一致來判斷分類是否正確。根據(jù)這個思路函數(shù)間隔定義為：

支持向量的定義來源于幾何間隔，幾何間隔最直接的解釋是離分隔超平面最近點的距離，其他任何點到平面的距離都大于這個值，所以幾何間隔就是支持向量。然后呢同樣道理，w和b是可以縮放的，所以定義支持向量滿足如下條件：

再通俗一點說，支持向量是一些點，這些點到分隔平面的距離最近，為了便于表示，把他們進行一下縮放計算，讓他們滿足了wx+b=+-1.

核函數(shù)是支持向量機的核心概念之一，它存在的目的就是將維度轉(zhuǎn)換之后的計算簡化，達到減少計算量的目的。我們都知道支持向量機求的是間距最大化，通常情況下我們求得的alpha都等于0，因此支持向量決定了間距最大化程度。

核函數(shù)的形式是這樣的

其中x(i)和x(j)都是向量，他們兩個相乘就是向量內(nèi)積，相乘得到一個數(shù)。剛才說了目標函數(shù)一般只和支持向量有關(guān)，因此在做核函數(shù)計算之前，實際就是選擇的支持向量進行計算。

這個寫完下面得再補充

我們知道了支持向量的概念，那么支持向量機的目標函數(shù)是要使這兩個支持向量之間的距離盡可能的遠，因為這樣才能更好地把樣本點分開，當然支持向量也要滿足最基本的約束條件，那就是分類正確，還有就是其他點到分隔平面的距離要大于等于支持向量到分隔平面的距離。

這種凸優(yōu)化問題都可以通過拉格朗日算子進行優(yōu)化，就是把約束條件通過拉格朗日系數(shù)放到目標函數(shù)上。這部分基礎(chǔ)知識，就是拉格朗日算法可以將等式約束和不等式約束都加到目標函數(shù)上，完成求解問題的轉(zhuǎn)換，但是要滿足一些約束條件，也就是我們后邊要說的kkt條件。

這里有個細節(jié)就是轉(zhuǎn)換時候的加減號問題，這個和目標函數(shù)還有約束的正負號有關(guān)。一般這么理解，就是求最小化問題時候，如果約束是大于0的，那么拉個朗日算子可以減到這一部分，這樣一來目標函數(shù)只能越來越小，最優(yōu)解就是約束為0的時候，這個時候和沒有約束的等價，再求最小就是原問題了。

這里是最小化問題，直接減掉這部分約束，然后后半部分永遠大于等于0所以這個式子的值是要小于原來目標函數(shù)值的。我們知道當x滿足原問題的約束條件的時候，最大化L就等于那個原目標函數(shù)。所以我們可以把這個問題轉(zhuǎn)化為：

把它帶回去原來的目標函數(shù)中，整理一下。

這個時候只要求最優(yōu)的α，就可以求出w和b了。我們上邊做了那么一堆轉(zhuǎn)換，這個過程要滿足一個叫做kkt條件的東西，其實這個東西就是把一堆約束條件整理到一起。

（1）原有問題的可行性，即h(x )=0,g(x )<0

放到這里就是：

SMO算法的核心思想是求出最優(yōu)化的α，然后根據(jù)之前推導(dǎo)得到的w,b,α之間的關(guān)系計算得到w和b，最后的計算公式是：

現(xiàn)在的問題就是怎么求α了。

SMO算法總共分兩部分，一部分是求解兩個α的二次規(guī)劃算法，另一部分是選擇兩個α的啟發(fā)式算法。

先說這個選擇α的啟發(fā)式算法部分：大神可以證明優(yōu)先優(yōu)化違反kkt條件的α可以最快獲得最優(yōu)解，至于咋證明的，就先不看了。

在講支持向量機的求解算法時候，直接給出了核函數(shù)K，那么怎么去理解核函數(shù)呢。核函數(shù)的作用是解決樣本點在高維空間的內(nèi)積運算問題，怎么理解呢，通常的分類問題都是有很多個特征的，然后為了達到現(xiàn)線性可分，又會從低維映射到高維，樣本量再一多計算量非常大，因此先通過函數(shù)進行一個轉(zhuǎn)換，減少乘法的計算量。

要理解核函數(shù)，先理解內(nèi)積運算，內(nèi)積運算實際是兩個向量，對應(yīng)位置相乘加和，比如我有x1 = [v1,v2], x2=[w1,w2]，那么x1和x2的內(nèi)積計算方法就是：v1w1+v2w2。

如果上面那種情況線性不可分，需要到高維進行映射，讓數(shù)據(jù)變得線性可分，然后數(shù)據(jù)變?yōu)槲寰S的，即v1 ^2+v2 2+v1+v2+v1v2，然后再進行一次內(nèi)積計算，數(shù)據(jù)變?yōu)? 。

稍作變換，可以變?yōu)? ，形式展開和上邊那個長式子差不多，然后其實可以映射內(nèi)積相乘的情況，所以可以進行核函數(shù)的變化。

問題在于，當你需要顯式的寫出來映射形式的時候，在維度很高的時候，需要計算的量太大，比如x1有三個維度，再進行映射就有19維度了，計算很復(fù)雜。如果用核函數(shù)，還是在原來低維度進行運算，既有相似的效果（映射到高維），又低運算量，這就是核函數(shù)的作用了。

核函數(shù)的種類：

這部分的核心在于SMO算法的編寫。有待補充。

二、筆記：支持向量機

1、線性可分支持向量機

線性可分支持向量機是指在訓練數(shù)據(jù)集線性可分的情況下，尋找一條幾何間隔最大化的直線（也稱硬間隔最大化），將正樣本和負樣本完全分開。

1.1、目標函數(shù)

設(shè)有數(shù)據(jù)集D{(x(1),y(1))，(x(2),y(2))，(x(3),y(3))...(x(m),y(m))}含有m個樣本，其中x∈Rn，y∈(-1,+1)。(x為n維向量)，分割樣本的直線方程為y=ω.x+b（ω∈Rn屬于n維向量），目標函數(shù)為：

1.2 對偶理論求解目標函數(shù)

1）1.1中的問題稱為函數(shù)優(yōu)化的原問題，構(gòu)造廣義拉格朗日函數(shù)L(ω,b,α): 其中，α為拉格朗日乘子，數(shù)學上可以證明，構(gòu)造的拉格朗日函數(shù)的最小最大問題(先對α求最大值，再對ω,b求最小值）與原問題等價，即min _ω,b max _α L(ω,b,α)與原問題等價。

2）容易證明，min _ω,b max _α L(ω,b,α)與其對偶問題max _α min _ω,b L(ω,b,α)滿足以下關(guān)系：

上式被成為弱對偶關(guān)系

3）如果原問題是一個凸二次規(guī)劃問題，則滿足強對偶關(guān)系，即：

此外，原問題與對偶問題滿足強對偶關(guān)系的充要條件是KKT條件：

1.3 對偶問題的解

由強對偶關(guān)系，可以將求原問題轉(zhuǎn)化為求對偶問題，通過KKT條件，可以得到將對偶問題的優(yōu)化問題最終轉(zhuǎn)化為：

該問題為凸二次規(guī)劃問題，可以利用一些優(yōu)化算法進行求解，比如SMO算法等。

1.4分類超平面和決策函數(shù)

由1.3求得最優(yōu)解α ^* 后，可分別得到ω ^* 和b ^* 。

選擇α ^* 中的一個正分量α ^* _j >0，可得b ^* ：

分離超平面為：y=ω ^* .x+b ^*

決策函數(shù)為f(x)=sign(ω ^* .x+b ^* )

線性可分支持向量機求得的超平面唯一。

1.5支持向量

只有那些拉格朗日乘子α不為0對應(yīng)的點才對最終的決策函數(shù)有貢獻，這些點均位于分割邊界上，被稱為支持向量。

2、線性支持向量機

對于訓練集出現(xiàn)某些異常點，導(dǎo)致無法線性可分，線性支持向量機目的在于尋找一條直線，在剔除這些異常點后，使大部分訓練數(shù)據(jù)是線性可分的，實現(xiàn)軟間隔最大化。

2.1 目標函數(shù)

其中，參數(shù)C用來對誤分類進行懲罰，C越大，對誤分類容忍度越??；ζ表示松弛因子。

2.2對偶問題的求解

最終轉(zhuǎn)化為對偶問題的優(yōu)化為：

2.3分類超平面和決策函數(shù)

由1.3求得最優(yōu)解α ^* 后，可分別得到ω ^* 和b ^* 。

選擇α ^* 中的一個正分量0<α ^* _j <C，可得b ^* ,注意，此時求得的b值不唯一：

分離超平面為：y=ω ^* .x+b ^*

決策函數(shù)為f(x)=sign(ω ^* .x+b ^* )

注意，線性支持向量機求得的超平面不唯一。

2.4支持向量

支持向量由在函數(shù)間隔邊界上的點、超平面與間隔邊界上的點、位于超平面上的點和誤分類點組成。

3、非線性支持向量機與核函數(shù)

非線性支持向量機用來解決線性不可分數(shù)據(jù)集的分類問題?，F(xiàn)實中存在一些數(shù)據(jù)集，在現(xiàn)有特征維度下完全線性不可分（與只存在一些異常點不同，使用軟間隔最大化的線性支持向量及也不能解決），非線性支持向量機通過核函數(shù)，將低維數(shù)據(jù)集通過映射函數(shù)轉(zhuǎn)換為高維數(shù)據(jù)，這些高維數(shù)據(jù)是線性可分的。

3.1 核函數(shù)

1）設(shè)X是輸入空間，H為特征空間，如果存在映射函數(shù)φ(x)使在輸入空間X的數(shù)據(jù)映射到特征空間H中，使得對于輸入空間X中的任意x,z∈X，都有：

則稱K(x,z)為核函數(shù)。

2）常用核函數(shù)

（1）多項式核函數(shù)

其中，p為多項式次數(shù)。

（2）高斯核函數(shù)

對應(yīng)的支持向量機為高斯徑向基函數(shù)分類器。

高斯核函數(shù)中的參數(shù)δ較大時，導(dǎo)致高偏差，低方差；

δ參數(shù)較小時，導(dǎo)致低偏差，高方差。

（3）字符串核函數(shù)

定義在字符串上的核函數(shù)

3.2目標函數(shù)

目標函數(shù)轉(zhuǎn)化為對偶問題的求解，并應(yīng)用核函數(shù)后，可以轉(zhuǎn)化為：

3.3 決策函數(shù)

在3.2求得α值后，不必通過映射函數(shù)φ(x)求參數(shù)ω，而是通過核函數(shù)求得決策函數(shù)：

將數(shù)據(jù)從低維空間通過映射函數(shù)映射到高維空間，當做優(yōu)化計算時，不必顯式求得映射函數(shù)，而是通過核函數(shù)在低維空間做計算，這種方式稱為為核技巧。

注意：吳恩達機器學習課程中，稱高斯核函數(shù)K(x _i ,x)為樣本x與參考點x _i (i=1,2,...m)的相似度函數(shù)。對于容量為m訓練數(shù)據(jù)集，選擇這m個數(shù)據(jù)作為參考點，將樣本x與參考點x _i 的高斯核函數(shù)(相似度函數(shù))構(gòu)建新的特征f _i ，最終的決策函數(shù)可以表示為：

其中，θ ₀ 對應(yīng)著公式3.3中的b ^* ，θ _i 對應(yīng)著α _i ^* y _i ，f _i 對應(yīng)著K(x _i ,x)。

三、最優(yōu)化問題求解方法

在求解最優(yōu)化問題中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件是兩種最常用的方法。在有等式約束時使用拉格朗日乘子法，在有不等約束時使用KKT條件。

我們這里提到的最優(yōu)化問題通常是指對于給定的某一函數(shù)，求其在指定作用域上的全局最小值(因為最小值與最大值可以很容易轉(zhuǎn)化，即最大值問題可以轉(zhuǎn)化成最小值問題)。提到KKT條件一般會附帶的提一下拉格朗日乘子。對學過高等數(shù)學的人來說比較拉格朗日乘子應(yīng)該會有些印象。二者均是求解最優(yōu)化問題的方法，不同之處在于應(yīng)用的情形不同。

一般情況下，最優(yōu)化問題會碰到一下三種情況：

這是最簡單的情況，解決方法通常是函數(shù)對變量求導(dǎo)，令求導(dǎo)函數(shù)等于0的點可能是極值點。將結(jié)果帶回原函數(shù)進行驗證即可。

設(shè)目標函數(shù)為f(x)，約束條件為h_k(x)，形如:

s.t. 表示subject to ，“受限于”的意思，l表示有l(wèi)個約束條件。

則解決方法是消元法或者拉格朗日法。消元法比較簡單不在贅述，這里主要講拉格朗日法，因為后面提到的KKT條件是對拉格朗日乘子法的一種泛化。

作為一種優(yōu)化算法，拉格朗日乘子法主要用于解決約束優(yōu)化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個變量和k個約束條件的約束優(yōu)化問題轉(zhuǎn)化為含有（n+k）個變量的無約束優(yōu)化問題。拉格朗日乘子背后的數(shù)學意義是其為約束方程梯度線性組合中每個向量的系數(shù)。

如何將一個含有n個變量和k個約束條件的約束優(yōu)化問題轉(zhuǎn)化為含有（n+k）個變量的無約束優(yōu)化問題？拉格朗日乘數(shù)法從數(shù)學意義入手，通過引入拉格朗日乘子建立極值條件，對n個變量分別求偏導(dǎo)對應(yīng)了n個方程，然后加上k個約束條件（對應(yīng)k個拉格朗日乘子）一起構(gòu)成包含了（n+k）變量的（n+k）個方程的方程組問題，這樣就能根據(jù)求方程組的方法對其進行求解。

首先定義拉格朗日函數(shù)F(x)：

然后解變量的偏導(dǎo)方程：

我們上述討論的問題均為等式約束優(yōu)化問題，但等式約束并不足以描述人們面臨的問題，不等式約束比等式約束更為常見，大部分實際問題的約束都是不超過多少時間，不超過多少人力，不超過多少成本等等。所以有幾個科學家拓展了拉格朗日乘數(shù)法，增加了KKT條件之后便可以用拉格朗日乘數(shù)法來求解不等式約束的優(yōu)化問題了。

設(shè)目標函數(shù)f(x)，不等式約束為g(x)，有的教程還會添加上等式約束條件h(x)。此時的約束優(yōu)化問題描述如下：

則我們定義不等式約束下的拉格朗日函數(shù)L，則L表達式為：

其中f(x)是原目標函數(shù)，hj(x)是第j個等式約束條件，λj是對應(yīng)的約束系數(shù)，gk是不等式約束，uk是對應(yīng)的約束系數(shù)。

常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標函數(shù)全部寫為一個式子L(a, b, x)= f(x) + a g(x)+b h(x)，

首先，我們先介紹一下什么是KKT條件。

KKT條件是指在滿足一些有規(guī)則的條件下, 一個非線性規(guī)劃(Nonlinear Programming)問題能有最優(yōu)化解法的一個必要和充分條件. 這是一個廣義化拉格朗日乘數(shù)的成果. 一般地, 一個最優(yōu)化數(shù)學模型的列標準形式參考開頭的式子, 所謂 Karush-Kuhn-Tucker 最優(yōu)化條件，就是指上式的最優(yōu)點x∗必須滿足下面的條件:

1). 約束條件滿足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q

2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇為梯度算子;

3). λj≠0且不等式約束條件滿足μi≥0,μigi(x∗)=0,i=1,2,…,p。

四、小球大間隔模型存在的對偶問題

軟間隔

在上文當中我們說了，在實際的場景當中，數(shù)據(jù)不可能是百分百線性可分的，即使真的能硬生生地找到這樣的一個分隔平面區(qū)分開樣本，那么也很有可能陷入過擬合當中，也是不值得追求的。

因此，我們需要對分類器的標準稍稍放松，允許部分樣本出錯。但是這就帶來了一個問題，在硬間隔的場景當中，間隔就等于距離分隔平面最近的支持向量到分隔平面的距離。那么，在允許出錯的情況下，這個間隔又該怎么算呢？

為了解決這個問題，我們需要對原本的公式進行變形，引入一個新的變量叫做松弛變量。松弛變量我們用希臘字母𝜉

ξ

來表示，這個松弛變量允許我們適當放松$y_i(\omega^T x_i + b) \ge 1 這個限制條件，我們將它變成

這

個

限

制

條

件

，

我

們

將

它

變

成

y_i(\omega^T x_i + b) \ge 1-\xi_i $。

也就是說對于每一條樣本我們都會有一個對應(yīng)的松弛變量𝜉𝑖

ξ

i

，它一共有幾種情況。

𝜉=0

ξ

=

0

，表示樣本能夠正確分類

0<𝜉<1

0

<

ξ

<

1

，表示樣本在分割平面和支持向量之間

𝜉=1

ξ

=

1

，表示樣本在分割平面上

𝜉≥1

ξ

≥

1

，表示樣本異常

我們可以結(jié)合下面這張圖來理解一下，會容易一些：

松弛變量雖然可以讓我們表示那些被錯誤分類的樣本，但是我們當然不希望它隨意松弛，這樣模型的效果就不能保證了。所以我們把它加入損失函數(shù)當中，希望在松弛得盡量少的前提下保證模型盡可能劃分正確。這樣我們可以重寫模型的學習條件：

min12||𝜔||2+𝐶∑𝑖=1𝑚𝜉𝑖𝑠.𝑡.𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≥1−𝜉𝑖,𝜉𝑖≥0,𝑖=1,2,3…,𝑛𝑖=1,2,3…,𝑛

min

1

2

|

|

ω

|

|

2

+C

∑

i

=

1

m

ξ

i

s.t.

y

i

(

ω

T

x

i

+b)≥1−

ξ

i

, i=1,2,3…,n

ξ

i

≥0, i=1,2,3…,n

這里的C是一個常數(shù)，可以理解成懲罰參數(shù)。我們希望||𝜔||2

|

|

ω

|

|

2

盡量小，也希望∑𝜉𝑖

∑

ξ

i

盡量小，這個參數(shù)C就是用來協(xié)調(diào)兩者的。C越大代表我們對模型的分類要求越嚴格，越不希望出現(xiàn)錯誤分類的情況，C越小代表我們對松弛變量的要求越低。

從形式上來看模型的學習目標函數(shù)和之前的硬間隔差別并不大，只是多了一個變量而已。這也是我們希望的，在改動盡量小的前提下讓模型支持分隔錯誤的情況。

模型推導(dǎo)

對于上面的式子我們同樣使用拉格朗日公式進行化簡，將它轉(zhuǎn)化成沒有約束的問題。

首先，我們確定幾個值。第一個是我們要優(yōu)化的目標：𝑓(𝑥)=min𝜔,𝑏,𝜉12||𝜔||2+𝐶∑𝑚𝑖=1𝜉𝑖

f

(

x

)

=

min

ω

,

b

,

ξ

1

2

|

|

ω

|

|

2

+

C

∑

i

=

1

m

ξ

i

第二個是不等式約束，拉格朗日乘子法當中限定不等式必須都是小于等于0的形式，所以我們要將原式中的式子做一個簡單的轉(zhuǎn)化：

𝑔(𝑥)=1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≤0ℎ(𝑥)=−𝜉𝑖≤0

g(x)=1−

ξ

i

−

y

i

(

ω

T

x

i

+b)≤0 h(x)=−

ξ

i

≤0

最后是引入拉格朗日乘子: 𝛼=(𝛼1,𝛼2,⋯,𝛼𝑚),𝛽=(𝛽1,𝛽2,⋯,𝛽𝑚)

α

=

(

α

1

,

α

2

,

⋯

,

α

m

)

,

β

=

(

β

1

,

β

2

,

⋯

,

β

m

)

我們寫出廣義拉格朗日函數(shù)：𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)=12||𝜔||2+𝐶∑𝑚𝑖=1𝜉𝑖,+∑𝑚𝑖=1𝛼𝑖(1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))−∑𝑚𝑖=1𝛽𝑖𝜉𝑖

L

(

ω

,

b

,

ξ

,

α

,

β

)

=

1

2

|

|

ω

|

|

2

+

C

∑

i

=

1

m

ξ

i

,

+

∑

i

=

1

m

α

i

(

1

−

ξ

i

−

y

i

(

ω

T

x

i

+

b

)

)

−

∑

i

=

1

m

β

i

ξ

i

我們要求的是這個函數(shù)的最值，也就是min𝜔,𝑏,𝜉max𝛼≥0,𝛽≥0𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)

min

ω

,

b

,

ξ

max

α

≥

0

,

β

≥

0

L

(

ω

,

b

,

ξ

,

α

,

β

)

。

在處理硬間隔的時候，我們講過對偶問題，對于軟間隔也是一樣。我們求L函數(shù)的對偶函數(shù)的極值。

對偶問題

原函數(shù)的對偶問題是max𝛼≥0,𝛽≥0min𝜔,𝑏,𝜉𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)

max

α

≥

0

,

β

≥

0

min

ω

,

b

,

ξ

L

(

ω

,

b

,

ξ

,

α

,

β

)

，這個對偶問題要成立需要滿足KKT條件。

我們先把這個KKT條件放一放，先來看一下對偶問題當中的內(nèi)部的極小值。這個極小值沒有任何約束條件，所以我們可以放心大膽地通過求導(dǎo)來來計算極值。這個同樣是高中數(shù)學的內(nèi)容，我們分別計算∂𝐿∂𝜔

∂

L

∂

ω

，∂𝐿∂𝑏

∂

L

∂

b

和∂𝐿∂𝜉

∂

L

∂

ξ

。

求導(dǎo)之后，我們可以得到：

∂𝐿∂𝜔=0∂𝐿∂𝑏=0∂𝐿∂𝜉=0→𝜔=∑𝑖=1𝑚𝛼𝑖𝑦𝑖𝑥𝑖→∑𝑖=1𝑚𝛼𝑖𝑦𝑖=0→𝛽𝑖=𝐶−𝛼𝑖

∂

L

∂

ω

=0 →ω=

∑

i

=

1

m

α

i

y

i

x

i

∂

L

∂

b

=0 →

∑

i

=

1

m

α

i

y

i

=0

∂

L

∂

ξ

=0 →

β

i

=C−

α

i

我們把這三個式子帶入對偶函數(shù)可以得到：

𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)=12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗+𝐶∑𝑖=1𝑚𝜉𝑖+∑𝑖=1𝑚𝛼𝑖(1−𝜉𝑖)−∑𝑖=1𝑚(𝐶−𝛼𝑖)𝜉𝑖=∑𝑖=1𝑚𝛼𝑖−12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗

L(ω,b,ξ,α,β) =

1

2

∑

i

=

1

m

∑

j

=

1

m

α

i

α

j

y

i

y

j

x

i

T

x

j

+C

∑

i

=

1

m

ξ

i

+

∑

i

=

1

m

α

i

(1−

ξ

i

)−

∑

i

=

1

m

(C−

α

i

)

ξ

i

=

∑

i

=

1

m

α

i

−

1

2

∑

i

=

1

m

∑

j

=

1

m

α

i

α

j

y

i

y

j

x

i

T

x

j

由于𝛽𝑖≥0

β

i

≥

0

，所以我們可以得到0≤𝛼𝑖≤𝐶

0

≤

α

i

≤

C

，所以最后我們可以把式子化簡成：

max𝛼∑𝑖=1𝑚𝛼𝑖−12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗𝑠.𝑡.∑𝑚𝑖=1𝛼𝑖𝑦𝑖=00≤𝛼𝑖≤𝐶,𝑖=1,2,3…,𝑚

max

α

∑

i

=

1

m

α

i

−

1

2

∑

i

=

1

m

∑

j

=

1

m

α

i

α

j

y

i

y

j

x

i

T

x

j

s.t.

∑

i

=

1

m

α

i

y

i

=0 0≤

α

i

≤C, i=1,2,3…,m

將原始化簡了之后，我們再回過頭來看KKT條件。KKT條件單獨理解看起來有點亂，其實我們可以分成三個部分，分別是原始問題可行：

1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≤0−𝜉𝑖≤0

1−

ξ

i

−

y

i

(

ω

T

x

i

+b)≤0 −

ξ

i

≤0

對偶問題可行：

𝛼𝑖≥0𝛽𝑖=𝐶−𝛼𝑖

α

i

≥0

β

i

=C−

α

i

以及松弛可行：

𝛼𝑖(1−𝜉−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))=0𝛽𝑖𝜉𝑖=0

α

i

(1−ξ−

y

i

(

ω

T

x

i

+b))=0

β

i

ξ

i

=0

我們觀察一下倒數(shù)第二個條件：𝛼𝑖(1−𝜉−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))=0

α

i

(

1

−

ξ

−

y

i

(

ω

T

x

i

+

b

)

)

=

0

。

這是兩個式子相乘并且等于0，無非兩種情況，要么𝛼𝑖=0

α

i

=

0

，要么后面那串等于0。我們分情況討論。

如果𝛼𝑖=0

α

i

=

0

，那么𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)−1≥0

y

i

(

ω

T

x

i

+

b

)

−

1

≥

0

，樣本分類正確，不會對模型產(chǎn)生影響。

如果𝛼𝑖>0

α

i

>

0

，那么𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)=1−𝜉𝑖

y

i

(

ω

T

x

i

+

b

)

=

1

−

ξ

i

，則樣本是支持向量。由于𝐶=𝛼𝑖+𝛽𝑖

C

=

α

i

+

β

i

，并且𝛽𝑖𝜉𝑖=0

β

i

ξ

i

=

0

。我們又可以分情況：

𝛼𝑖<𝐶

α

i

<

C

，那么𝛽𝑖>0

β

i

>

0

，所以𝜉𝑖=0

ξ

i

=

0

，那么樣本在邊界上

如果𝛼𝑖=𝐶

α

i

=

C

，那么𝛽𝑖=0

β

i

=

0

，如果此時𝜉≤1

ξ

≤

1

，那么樣本被正確分類，否則樣本被錯誤分類

經(jīng)過了化簡之后，式子當中只剩下了變量𝛼

α

，我們要做的就是找到滿足約束條件并且使得式子取極值時的𝛼

α

，這個𝛼

α

要怎么求呢？我們這里先放一放，將在下一篇文章當中詳解講解。

以上就是關(guān)于kkt條件推導(dǎo)相關(guān)問題的回答。希望能幫到你，如有更多相關(guān)問題，您也可以聯(lián)系我們的客服進行咨詢，客服也會為您講解更多精彩的知識和內(nèi)容。

推薦閱讀：

kkt充分條件（充分條件怎么推）

kkt二階最優(yōu)條件（二階最優(yōu)化條件）

kkt條件推導(dǎo)（kkt條件推導(dǎo)的一定收斂嗎）

vin是啥（車輛vin是啥）

園林景觀設(shè)計中的工程人員（園林景觀設(shè)計中的工程人員是什么）