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

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

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

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

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

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

本文目錄:

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

• 2、筆記：支持向量機(jī)

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

• 4、小球大間隔模型存在的對(duì)偶問(wèn)題

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

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

支持向量機(jī)分為三類：

（1）線性可分支持向量機(jī)，樣本線性可分，可通過(guò)硬間隔最大化訓(xùn)練一個(gè)分類器。

（2）線性支持向量機(jī)，樣本基本線性可分，可通過(guò)軟間隔最大化訓(xùn)練一個(gè)分類器。

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

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

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

軟間隔說(shuō)的是，不存在一個(gè)平面可以把樣本完全正確無(wú)誤的分開(kāi)，因此呢允許一些樣本被分錯(cuò)，怎么做呢就是加入松弛變量，因?yàn)橄Ｍ皱e(cuò)的樣本越小越好，因此松弛變量也有約束條件。加入松弛變量后，問(wèn)題就變?yōu)榫€性可分了，因?yàn)槭敲恳粋€(gè)樣本都線性可分，因此松弛變量是針對(duì)樣本的，每一個(gè)樣本都對(duì)應(yīng)一個(gè)不同的松弛變量。

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

這里啰嗦一句，誤分類點(diǎn)y*(wx+b)<0，所以加個(gè)負(fù)號(hào)在前邊。

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

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

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

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

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

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

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

這個(gè)寫(xiě)完下面得再補(bǔ)充

我們知道了支持向量的概念，那么支持向量機(jī)的目標(biāo)函數(shù)是要使這兩個(gè)支持向量之間的距離盡可能的遠(yuǎn)，因?yàn)檫@樣才能更好地把樣本點(diǎn)分開(kāi)，當(dāng)然支持向量也要滿足最基本的約束條件，那就是分類正確，還有就是其他點(diǎn)到分隔平面的距離要大于等于支持向量到分隔平面的距離。

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

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

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

把它帶回去原來(lái)的目標(biāo)函數(shù)中，整理一下。

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

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

放到這里就是：

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

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

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

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

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

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

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

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

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

核函數(shù)的種類：

這部分的核心在于SMO算法的編寫(xiě)。有待補(bǔ)充。

二、筆記：支持向量機(jī)

1、線性可分支持向量機(jī)

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

1.1、目標(biāo)函數(shù)

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

1.2 對(duì)偶理論求解目標(biāo)函數(shù)

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

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

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

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

此外，原問(wèn)題與對(duì)偶問(wèn)題滿足強(qiáng)對(duì)偶關(guān)系的充要條件是KKT條件：

1.3 對(duì)偶問(wèn)題的解

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

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

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

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

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

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

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

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

1.5支持向量

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

2、線性支持向量機(jī)

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

2.1 目標(biāo)函數(shù)

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

2.2對(duì)偶問(wèn)題的求解

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

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

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

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

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

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

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

2.4支持向量

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

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

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

3.1 核函數(shù)

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

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

2）常用核函數(shù)

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

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

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

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

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

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

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

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

3.2目標(biāo)函數(shù)

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

3.3 決策函數(shù)

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

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

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

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

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

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

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

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

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

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

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

則解決方法是消元法或者拉格朗日法。消元法比較簡(jiǎn)單不在贅述，這里主要講拉格朗日法，因?yàn)楹竺嫣岬降腒KT條件是對(duì)拉格朗日乘子法的一種泛化。

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

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

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

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

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

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

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

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

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

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

KKT條件是指在滿足一些有規(guī)則的條件下, 一個(gè)非線性規(guī)劃(Nonlinear Programming)問(wèn)題能有最優(yōu)化解法的一個(gè)必要和充分條件. 這是一個(gè)廣義化拉格朗日乘數(shù)的成果. 一般地, 一個(gè)最優(yōu)化數(shù)學(xué)模型的列標(biāo)準(zhǔn)形式參考開(kāi)頭的式子, 所謂 Karush-Kuhn-Tucker 最優(yōu)化條件，就是指上式的最優(yōu)點(diǎn)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。

四、小球大間隔模型存在的對(duì)偶問(wèn)題

軟間隔

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

因此，我們需要對(duì)分類器的標(biāo)準(zhǔn)稍稍放松，允許部分樣本出錯(cuò)。但是這就帶來(lái)了一個(gè)問(wèn)題，在硬間隔的場(chǎng)景當(dāng)中，間隔就等于距離分隔平面最近的支持向量到分隔平面的距離。那么，在允許出錯(cuò)的情況下，這個(gè)間隔又該怎么算呢？

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

ξ

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

這

個(gè)

限

制

條

件

，

我

們

將

它

變

成

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

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

ξ

i

，它一共有幾種情況。

𝜉=0

ξ

=

0

，表示樣本能夠正確分類

0<𝜉<1

0

<

ξ

<

1

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

𝜉=1

ξ

=

1

，表示樣本在分割平面上

𝜉≥1

ξ

≥

1

，表示樣本異常

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

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

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是一個(gè)常數(shù)，可以理解成懲罰參數(shù)。我們希望||𝜔||2

|

|

ω

|

|

2

盡量小，也希望∑𝜉𝑖

∑

ξ

i

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

從形式上來(lái)看模型的學(xué)習(xí)目標(biāo)函數(shù)和之前的硬間隔差別并不大，只是多了一個(gè)變量而已。這也是我們希望的，在改動(dòng)盡量小的前提下讓模型支持分隔錯(cuò)誤的情況。

模型推導(dǎo)

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

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

f

(

x

)

=

min

ω

,

b

,

ξ

1

2

|

|

ω

|

|

2

+

C

∑

i

=

1

m

ξ

i

第二個(gè)是不等式約束，拉格朗日乘子法當(dāng)中限定不等式必須都是小于等于0的形式，所以我們要將原式中的式子做一個(gè)簡(jiǎn)單的轉(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

)

我們寫(xiě)出廣義拉格朗日函數(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

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

min

ω

,

b

,

ξ

max

α

≥

0

,

β

≥

0

L

(

ω

,

b

,

ξ

,

α

,

β

)

。

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

對(duì)偶問(wèn)題

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

max

α

≥

0

,

β

≥

0

min

ω

,

b

,

ξ

L

(

ω

,

b

,

ξ

,

α

,

β

)

，這個(gè)對(duì)偶問(wèn)題要成立需要滿足KKT條件。

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

∂

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

我們把這三個(gè)式子帶入對(duì)偶函數(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

，所以最后我們可以把式子化簡(jiǎn)成：

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

將原始化簡(jiǎn)了之后，我們?cè)倩剡^(guò)頭來(lái)看KKT條件。KKT條件單獨(dú)理解看起來(lái)有點(diǎn)亂，其實(shí)我們可以分成三個(gè)部分，分別是原始問(wèn)題可行：

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

1−

ξ

i

−

y

i

(

ω

T

x

i

+b)≤0 −

ξ

i

≤0

對(duì)偶問(wèn)題可行：

𝛼𝑖≥0𝛽𝑖=𝐶−𝛼𝑖

α

i

≥0

β

i

=C−

α

i

以及松弛可行：

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

α

i

(1−ξ−

y

i

(

ω

T

x

i

+b))=0

β

i

ξ

i

=0

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

α

i

(

1

−

ξ

−

y

i

(

ω

T

x

i

+

b

)

)

=

0

。

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

α

i

=

0

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

如果𝛼𝑖=0

α

i

=

0

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

y

i

(

ω

T

x

i

+

b

)

−

1

≥

0

，樣本分類正確，不會(huì)對(duì)模型產(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

，如果此時(shí)𝜉≤1

ξ

≤

1

，那么樣本被正確分類，否則樣本被錯(cuò)誤分類

經(jīng)過(guò)了化簡(jiǎn)之后，式子當(dāng)中只剩下了變量𝛼

α

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

α

，這個(gè)𝛼

α

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

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

推薦閱讀：

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

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

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

vin是啥（車輛vin是啥）

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