kkt點(diǎn)求解（kkt點(diǎn)怎么求）

大家好！今天讓創(chuàng)意嶺的小編來(lái)大家介紹下關(guān)于kkt點(diǎn)求解的問(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、SVM算法原理

• 2、請(qǐng)問(wèn)各位大俠如何做二次凸規(guī)劃的求解

• 3、支持向量機(jī)(SVM)基本原理

• 4、支持向量機(jī)（SVM）

一、SVM算法原理

一、決策面方程

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

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

設(shè)用向量w代表矩陣a1和a2，用向量x代表矩陣x1和x2，標(biāo)量γ代表b，則方程可化表示為

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

二、函數(shù)間隔和幾何間隔

在SVM監(jiān)督學(xué)習(xí)中，我們規(guī)定標(biāo)簽數(shù)據(jù)為+1和-1兩個(gè)值，這么做的目的， 可以計(jì)算出任意一個(gè)樣本點(diǎn)在超平面方程上的表現(xiàn)結(jié)果的符號(hào)，與標(biāo)簽符號(hào)是否一致來(lái)判斷分類的正確性 ，為此我們可以引入函數(shù)間隔的概念

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

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

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

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

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

三、不等式約束條件

SVM算法的目的是找到一個(gè)將分類效果達(dá)到最合理化的超平面，這個(gè)超平面即是分類器 。而評(píng)估分類器的好壞的標(biāo)準(zhǔn)就是分類間隔的大小

我們定義分類間隔的距離為d，好的分類器應(yīng)該讓所有樣本點(diǎn)到?jīng)Q策面的幾何間隔都大于等于d

化簡(jiǎn)上式，不等式兩邊同時(shí)除以d可得

由于||w||和d都是標(biāo)量，可定義

則上式可化簡(jiǎn)為

在不等式兩邊同時(shí)乘以yi，即將兩個(gè)式子化簡(jiǎn)為一個(gè)式子（這里體現(xiàn)了正是因?yàn)闃?biāo)簽數(shù)據(jù)為+1和-1，才方便將約束條件變成一個(gè)約束方程）

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

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

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

由約束方程可知，當(dāng)樣本點(diǎn)落在支持向量邊界上有如下關(guān)系

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

要讓任何樣本點(diǎn)都在d之外，即求分類間隔d的最大值，則目標(biāo)函數(shù)可以寫(xiě)成

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

由目標(biāo)函數(shù)是二次的，而約束條件是線性的，則 SVM的數(shù)學(xué)模型即是：不等式約束條件下的二次型函數(shù)優(yōu)化 ，而求解這一類優(yōu)化問(wèn)題，接下來(lái)我們需要構(gòu)造 拉格朗乘子函數(shù)

五、引入拉格朗函數(shù)

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

拉格朗函數(shù)的目的，就是將約束條件融合到目標(biāo)函數(shù)中，構(gòu)造一個(gè)新函數(shù)來(lái)表示目標(biāo)函數(shù)，將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題

下面，我們構(gòu)造拉格朗函數(shù)來(lái)表示目標(biāo)函數(shù)

其中αi是拉格朗日乘子，每一個(gè)約束條件對(duì)應(yīng)一個(gè)拉格朗日乘子，其中αi大于等于0

則原優(yōu)化問(wèn)題可以轉(zhuǎn)化為

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

(1) 當(dāng)樣本點(diǎn)不滿足約束條件時(shí)，即說(shuō)明在 可行解區(qū)域外

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

(2) 當(dāng)樣本點(diǎn)滿足約束條件時(shí)，即說(shuō)明在 可行解區(qū)域內(nèi)

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

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

觀察新的目標(biāo)函數(shù)，如果直接求偏導(dǎo)數(shù)求解，那么一上來(lái)將面對(duì)w和b兩個(gè)未知參數(shù)，而αi又是不等式約束，求解過(guò)程將非常復(fù)雜。換一個(gè)角度思考，如果將max和min的位置對(duì)調(diào)，變成如下新的目標(biāo)函數(shù)

上式變化使用了 拉格朗日函數(shù)的對(duì)偶性，交換后的新問(wèn)題即是原目標(biāo)函數(shù)的對(duì)偶問(wèn)題 ，我們用d*來(lái)表示對(duì)偶目標(biāo)函數(shù)的最優(yōu)解，可見(jiàn)d*的求導(dǎo)過(guò)程比p*相對(duì)容易，且d*<=p*，而當(dāng)滿足下列條件時(shí)，d*= p*

因?yàn)槟繕?biāo)函數(shù)本身已經(jīng)是一個(gè)凸函數(shù)，而優(yōu)化問(wèn)題又是求解最小值，所以目標(biāo)函數(shù)的最優(yōu)化問(wèn)題就是凸優(yōu)化問(wèn)題，則接下來(lái)就要重點(diǎn)討論KKT條件

六、KKT條件的描述

一個(gè)最優(yōu)化模型能夠表示成下列標(biāo)準(zhǔn)形式

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

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

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

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

對(duì)于KKT條件一的分析，我們假設(shè)目標(biāo)函數(shù)是f(x1,x2)的二元函數(shù)，它的圖像在三維空間里是一個(gè)曲面，準(zhǔn)確的來(lái)說(shuō)是一個(gè)凸曲面

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

我們畫(huà)出目標(biāo)函數(shù)的等高線，來(lái)分析目標(biāo)函數(shù)最優(yōu)值和約束條件的關(guān)系

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

如果等高線與g(x1,x2) 相交 ，則是一組目標(biāo)函數(shù)的解，但是這個(gè)解一定不是最優(yōu)解， 因?yàn)橄嘟灰馕吨隙ù嬖谄渌雀呔€在該條等高線的內(nèi)部或者外部 ，可能會(huì)使得新的等高線與g(x1,x2)的交點(diǎn)更大或者更小，這就意味著只有當(dāng)?shù)雀呔€與g(x1,x2) 相切 ，才可能得到最優(yōu)解（切線可能多條）

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

而上式恒成立的條件就是： 拉格朗日乘子α >= 0 ，且這個(gè)式子就是目標(biāo)函數(shù)對(duì)各個(gè)參數(shù)求偏導(dǎo)數(shù)的結(jié)果，即KKT的第一個(gè)條件：目標(biāo)函數(shù)對(duì)各個(gè)參數(shù)的導(dǎo)數(shù)為0

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

對(duì)于KKT條件三，可以看出，因?yàn)樗械募s束函數(shù)gi(x)<=0，所有的拉格朗日乘子αi>=0，要使得求和后結(jié)果為0，要么某個(gè)約束函數(shù)gi(x)=0，要么其對(duì)應(yīng)的αi=0

從一個(gè)案例出發(fā)來(lái)分析KKT條件三的邏輯，假設(shè)目標(biāo)函數(shù)和約束函數(shù)是

將不等式約束構(gòu)造出拉格朗日函數(shù)，并分別對(duì)x1和x2求偏導(dǎo)數(shù)

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

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

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

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

綜上(i)(ii)討論，目標(biāo)函數(shù)的最優(yōu)值符合KKT條件三，也說(shuō)明了 滿足強(qiáng)對(duì)偶條件的優(yōu)化問(wèn)題的最優(yōu)值必須滿足KKT條件

九、求解對(duì)偶問(wèn)題

上面分析了目標(biāo)函數(shù)滿足凸優(yōu)化和KKT條件，則問(wèn)題轉(zhuǎn)化為求解原問(wèn)題的對(duì)偶問(wèn)題（即p*=d*）

根據(jù)對(duì)偶問(wèn)題描述，先要求內(nèi)側(cè)w和b關(guān)于L(w,b,α)的最小化值，即求L對(duì)w和b的偏導(dǎo)數(shù)

將w和b的偏導(dǎo)數(shù)帶入拉格朗函數(shù)化簡(jiǎn)得

整理一下最終化簡(jiǎn)結(jié)果為

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

我們歸納一下現(xiàn)在的目標(biāo)函數(shù)為

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

十、引入松弛變量

由于現(xiàn)實(shí)世界中的數(shù)據(jù)都是帶有噪音的，也就是數(shù)據(jù)可能出偏離其正常的位置很遠(yuǎn)，而出現(xiàn)這種極端現(xiàn)象后往往會(huì)影響超平面的選擇，也許將無(wú)法構(gòu)造出將數(shù)據(jù)徹底分開(kāi)的超平面出來(lái)

所以對(duì)于處理這種情況， SVM需要允許（妥協(xié)）出某些噪音很大的數(shù)據(jù)點(diǎn)能夠偏離超平面，即允許其出現(xiàn)在超平面的錯(cuò)誤的一側(cè) ，為此我們引入松弛變量C，這樣我們的目標(biāo)函數(shù)又變?yōu)?/p>

接下來(lái)為了研究討論αi的取值范圍，我們加上一個(gè)負(fù)號(hào)將目標(biāo)函數(shù)等價(jià)轉(zhuǎn)化為

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

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

設(shè)ui為該約束條件，可以歸納出αi關(guān)于約束函數(shù)的取值意義

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

而同時(shí)目標(biāo)函數(shù)還受到第二個(gè)約束條件的限制，即

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

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

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

（i）：當(dāng)y1和y2異號(hào)時(shí)，可以得到

移項(xiàng)可得a2 = a1 - A，此時(shí)α的取值范圍如下圖所示

所以此時(shí)α的上下界H和L為

（ii）：當(dāng)y1和y2同號(hào)時(shí)，可以得到

移項(xiàng)可得a2 = -a1 + A，此時(shí)α的取值范圍如下圖所示

所以此時(shí)α的上下界H和L為

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

這個(gè)公式顯得非常的重要，它將α因子限制在有效的矩形范圍內(nèi)，在SMO算法中，當(dāng)我們更新完α后，由于α可能會(huì)被更新得很大或很小，因此需要經(jīng)過(guò)裁剪來(lái)保證α的在約束條件內(nèi)

12、SMO算法的思想

回顧之前第九，第十，第十一步的分析，目標(biāo)函數(shù)為

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

由第十一步的分析，我們需要不斷更新這n個(gè)α因子，通過(guò)迭代來(lái)逼近函數(shù)達(dá)到最小值，但是如果一次性更新n個(gè)參數(shù)，將會(huì)有n!種組合，那么時(shí)間復(fù)雜度將會(huì)非常高，為此我們首先想到 坐標(biāo)上升（下降）法

來(lái)通過(guò)一個(gè)例子來(lái)說(shuō)明坐標(biāo)上升法的思路

可知案例中要求一個(gè)三元函數(shù)的最大值， 算法的思想是每次迭代時(shí)只更新一個(gè)維度，通過(guò)多次迭代直到收斂來(lái)優(yōu)化函數(shù)的最值 ，求出三個(gè)變量的偏導(dǎo)數(shù)推出其關(guān)系

通過(guò)迭代即就可以求出其最值

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

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

13、多元函數(shù)推導(dǎo)為二元函數(shù)

目標(biāo)函數(shù)是關(guān)于α的N元函數(shù)，通過(guò)SMO的算法思想，假設(shè)每次迭代更新，選取一對(duì)α1和α2的組合，其余的乘子不變， 首先需要將α1和α2從目標(biāo)函數(shù)中分離出來(lái) ，也就是將多元函數(shù)推導(dǎo)為二元函數(shù)

從N元函數(shù)中分離出α1和α2因子

由于上式推導(dǎo)結(jié)果過(guò)于復(fù)雜，我們定義2個(gè)表達(dá)式來(lái)表示上式常量部分，用來(lái)簡(jiǎn)化上式

又由于單獨(dú)存下的常數(shù)項(xiàng)對(duì)以后的求導(dǎo)沒(méi)有貢獻(xiàn)，所以我們提出單獨(dú)的常數(shù)項(xiàng)定義為Constant

帶入vi和Constant表達(dá)式，則結(jié)果化簡(jiǎn)為

至此，我們將 多元函數(shù)推導(dǎo)為含有α1和α2變量的二元函數(shù) ，接下來(lái)將這個(gè)二元函數(shù)推導(dǎo)為一元函數(shù)

14、二元函數(shù)推導(dǎo)為一元函數(shù)

我們需要推導(dǎo)出α1和α2的關(guān)系，然后用α2來(lái)表示α1帶入二元函數(shù)，就可以推導(dǎo)出關(guān)于α2的一元函數(shù)了

由目標(biāo)函數(shù)的第二個(gè)約束條件

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

將等式兩邊同時(shí)乘以y1，可推導(dǎo)出α1和α2的關(guān)系

同理，我們定義兩個(gè)表達(dá)式r和s來(lái)表示上式的常量部分，用來(lái)簡(jiǎn)化上式關(guān)系

帶入r和s后，α1和α2的關(guān)系推導(dǎo)為

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

至此， 我們將二元函數(shù)推導(dǎo)為只含有一個(gè)變量α2的一元函數(shù) ，接下來(lái)終于可以對(duì)目標(biāo)函數(shù)求導(dǎo)了

15、求解一元函數(shù)的偏導(dǎo)數(shù)，推導(dǎo)出第一個(gè)拉格朗乘子的遞推關(guān)系

我們對(duì)一元函數(shù)求α2的偏導(dǎo)數(shù)為0

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

二、請(qǐng)問(wèn)各位大俠如何做二次凸規(guī)劃的求解

二次規(guī)劃（Quadratic programming），在運(yùn)籌學(xué)當(dāng)中，是一種特殊類型的最佳化問(wèn)題。

[編輯] 簡(jiǎn)介二次規(guī)劃問(wèn)題可以以下形式來(lái)描述：

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

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

Ex = d

vT 是 v 的轉(zhuǎn)置。

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

根據(jù)優(yōu)化理論，一個(gè)點(diǎn)x 成為全局最小值的必要條件是滿足 Karush-Kuhn-Tucker(KKT)條件。當(dāng)f(x)是凸函數(shù)時(shí)，KKT條件也是充分條件。

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

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

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

對(duì)偶問(wèn)題g(λ)，可定義為

我們可用 : 得到L的極小

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

對(duì)偶函數(shù)：

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

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

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

subject to :

計(jì)算復(fù)雜性當(dāng)Q正定時(shí)，用橢圓法可在多項(xiàng)式時(shí)間內(nèi)解二次規(guī)劃問(wèn)題。當(dāng)Q負(fù)定時(shí)，二次規(guī)劃問(wèn)題是NP困難的(NP-Hard)。即使Q 存在一個(gè)負(fù)特征值時(shí)，二次規(guī)劃問(wèn)題就是NP困難的。

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

看了很多關(guān)于SVM的博客，但是常常只能保存書(shū)簽之后看，有時(shí)候有的博客就突然沒(méi)了，這里就作為搬運(yùn)工總結(jié)一下之后自己看吧。主要內(nèi)容來(lái)自于：

支持向量機(jī)通俗導(dǎo)論（理解SVM的三層境界）

線性回歸

給定數(shù)據(jù)集 , 其中, ,線性回歸試圖學(xué)習(xí)到一個(gè)線性模型,盡可能地輸出正確標(biāo)記.

如果我們要用線性回歸算法來(lái)解決一個(gè)分類問(wèn)題,(對(duì)于分類,y 取值為 0 或者 1),但如果你使用的是線性回歸,那么假設(shè)函數(shù)的輸出值可能遠(yuǎn)大于 1,或者遠(yuǎn)小于 0,就算所有訓(xùn)練樣本的標(biāo)簽 y 都是 0 或 1但是如果算法得到的值遠(yuǎn)大于 1 或者遠(yuǎn)小于 0 的話,就會(huì)感覺(jué)很奇怪。所以我們?cè)诮酉聛?lái)的要研究的算法就叫做邏輯回歸算法,這個(gè)算法的性質(zhì)是:它的輸出值永遠(yuǎn)在 0 到 1 之間。

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

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

如圖所示,令 , 當(dāng) z > 0 , z 越大, sigmoid 返回值越接近1(但永遠(yuǎn)不會(huì)超過(guò)1). 反之,當(dāng)z < 0時(shí),z 越小, sigmoid 返回值越接近0(但永遠(yuǎn)不會(huì)小于0).

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

線性分類器

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

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

假設(shè)函數(shù):

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

圖像為：

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

定義函數(shù)間隔 （用表示）為

而超平面(w，b)關(guān)于T中所有樣本點(diǎn)(xi，yi)的函數(shù)間隔最小值（其中，x是特征，y是結(jié)果標(biāo)簽，i表示第i個(gè)樣本），便為超平面(w, b)關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔：

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

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

假定對(duì)于一個(gè)點(diǎn) x ，令其垂直投影到超平面上的對(duì)應(yīng)點(diǎn)為 x0 ，w 是垂直于超平面的一個(gè)向量， 為樣本x到超平面的距離，如下圖所示：

根據(jù)平面幾何知識(shí)，有

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

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

隨即讓此式 的兩邊同時(shí)乘以 ，再根據(jù) 和 ，即可算出 ：

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

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

對(duì)一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行分類，當(dāng)超平面離數(shù)據(jù)點(diǎn)的“間隔”越大，分類的確信度（confidence）也越大。所以，為了使得分類的確信度盡量高，需要讓所選擇的超平面能夠最大化這個(gè)“間隔”值。這個(gè)間隔就是下圖中的Gap的一半。

通過(guò)由前面的分析可知：函數(shù)間隔不適合用來(lái)最大化間隔值，因?yàn)樵诔矫婀潭ㄒ院?，可以等比例地縮放w的長(zhǎng)度和b的值，這樣可以使得 的值任意大，亦即函數(shù)間隔 可以在超平面保持不變的情況下被取得任意大。但幾何間隔因?yàn)槌狭? ，使得在縮放w和b的時(shí)候幾何間隔的值 是不會(huì)改變的，它只隨著超平面的變動(dòng)而變動(dòng)，因此，這是更加合適的一個(gè)間隔。換言之，這里要找的最大間隔分類超平面中的“間隔”指的是幾何間隔。

于是最大間隔分類器（maximum margin classifier）的目標(biāo)函數(shù)可以定義為

同時(shí)需滿足一些條件，根據(jù)間隔的定義，有

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

相當(dāng)于在相應(yīng)的約束條件 下，最大化這個(gè)1/||w||值，而1/||w||便是幾何間隔。

據(jù)了解，

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

那什么是拉格朗日對(duì)偶性呢？簡(jiǎn)單來(lái)講，通過(guò)給每一個(gè)約束條件加上一個(gè)拉格朗日乘子 ,（Lagrange multiplier），定義拉格朗日函數(shù)（通過(guò)拉格朗日函數(shù)將約束條件融合到目標(biāo)函數(shù)里去，從而只用一個(gè)函數(shù)表達(dá)式便能清楚的表達(dá)出我們的問(wèn)題）

然后令：

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

因此，在要求約束條件得到滿足的情況下最小化 ，實(shí)際上等價(jià)于直接最小化 （當(dāng)然，這里也有約束條件，就是 ≥0,i=1,…,n） ，因?yàn)槿绻s束條件沒(méi)有得到滿足， 會(huì)等于無(wú)窮大，自然不會(huì)是我們所要求的最小值。

具體寫(xiě)出來(lái)，目標(biāo)函數(shù)變成了：

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

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

換言之，之所以從minmax 的原始問(wèn)題，轉(zhuǎn)化為maxmin 的對(duì)偶問(wèn)題，一者因?yàn)? 是 的近似解，二者，轉(zhuǎn)化為對(duì)偶問(wèn)題后，更容易求解。

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

KKT條件

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

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

一般地，一個(gè)最優(yōu)化數(shù)學(xué)模型能夠表示成下列標(biāo)準(zhǔn)形式：

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

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

而KKT條件就是指上面最優(yōu)化數(shù)學(xué)模型的標(biāo)準(zhǔn)形式中的最小點(diǎn) x* 必須滿足下面的條件：

我們這里的問(wèn)題是滿足 KKT 條件的（首先已經(jīng)滿足Slater條件，再者f和gi也都是可微的，即L對(duì)w和b都可導(dǎo)），因此現(xiàn)在我們便轉(zhuǎn)化為求解第二個(gè)問(wèn)題。

也就是說(shuō)，原始問(wèn)題通過(guò)滿足KKT條件，已經(jīng)轉(zhuǎn)化成了對(duì)偶問(wèn)題。而求解這個(gè)對(duì)偶學(xué)習(xí)問(wèn)題，分為3個(gè)步驟：首先要讓L(w，b，a) 關(guān)于 w 和 b 最小化，然后求對(duì) 的極大，最后利用SMO算法求解對(duì)偶問(wèn)題中的拉格朗日乘子。

對(duì)偶問(wèn)題求解的3個(gè)步驟

將以上結(jié)果代入之前的L：

得到：

具體推導(dǎo)過(guò)程是比較復(fù)雜的，如下所示：

最后，得到：

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

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

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

總結(jié)

讓我們?cè)賮?lái)看看上述推導(dǎo)過(guò)程中得到的一些有趣的形式。首先就是關(guān)于我們的 hyper plane ，對(duì)于一個(gè)數(shù)據(jù)點(diǎn) x 進(jìn)行分類，實(shí)際上是通過(guò)把 x 帶入到 算出結(jié)果然后根據(jù)其正負(fù)號(hào)來(lái)進(jìn)行類別劃分的。而前面的推導(dǎo)中我們得到:

因此分類函數(shù)為：

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

為什么非支持向量對(duì)應(yīng)的 等于零呢？直觀上來(lái)理解的話，就是這些“后方”的點(diǎn)——正如我們之前分析過(guò)的一樣，對(duì)超平面是沒(méi)有影響的，由于分類完全有超平面決定，所以這些無(wú)關(guān)的點(diǎn)并不會(huì)參與分類問(wèn)題的計(jì)算，因而也就不會(huì)產(chǎn)生任何影響了。

回憶一下我們通過(guò) Lagrange multiplier得到的目標(biāo)函數(shù)：

注意到如果 xi 是支持向量的話，上式中紅顏色的部分是等于 0 的（因?yàn)橹С窒蛄康?functional margin 等于 1 ），而對(duì)于非支持向量來(lái)說(shuō)，functional margin 會(huì)大于 1 ，因此紅顏色部分是大于零的，而 又是非負(fù)的，為了滿足最大化， 必須等于 0 。這也就是這些非Supporting Vector 的點(diǎn)的局限性。

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

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

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

而在我們遇到核函數(shù)之前，如果用原始的方法，那么在用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性關(guān)系，需要選擇一個(gè)非線性特征集，并且將數(shù)據(jù)寫(xiě)成新的表達(dá)形式，這等價(jià)于應(yīng)用一個(gè)固定的非線性映射，將數(shù)據(jù)映射到特征空間，在特征空間中使用線性學(xué)習(xí)器，因此，考慮的假設(shè)集是這種類型的函數(shù)：

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

首先使用一個(gè)非線性映射將數(shù)據(jù)變換到一個(gè)特征空間F，

然后在特征空間使用線性學(xué)習(xí)器分類。

而由于對(duì)偶形式就是線性學(xué)習(xí)器的一個(gè)重要性質(zhì)，這意味著假設(shè)可以表達(dá)為訓(xùn)練點(diǎn)的線性組合，因此決策規(guī)則可以用測(cè)試點(diǎn)和訓(xùn)練點(diǎn)的內(nèi)積來(lái)表示：

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

核是一個(gè)函數(shù)K，對(duì)所有x，z，滿足 ，這里φ是從X到內(nèi)積特征空間F的映射。

來(lái)看個(gè)核函數(shù)的例子。如下圖所示的兩類數(shù)據(jù)，分別分布為兩個(gè)圓圈的形狀，這樣的數(shù)據(jù)本身就是線性不可分的，此時(shí)咱們?cè)撊绾伟堰@兩類數(shù)據(jù)分開(kāi)呢(下文將會(huì)有一個(gè)相應(yīng)的三維空間圖)？

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

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

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

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

因此我只需要把它映射到 ，這樣一個(gè)三維空間中即可，下圖即是映射之后的結(jié)果，將坐標(biāo)軸經(jīng)過(guò)適當(dāng)?shù)男D(zhuǎn)，就可以很明顯地看出，數(shù)據(jù)是可以通過(guò)一個(gè)平面來(lái)分開(kāi)的

核函數(shù)相當(dāng)于把原來(lái)的分類函數(shù)：

映射成：

而其中的 可以通過(guò)求解如下 dual 問(wèn)題而得到的：

這樣一來(lái)問(wèn)題就解決了嗎？似乎是的：拿到非線性數(shù)據(jù)，就找一個(gè)映射

四、支持向量機(jī)（SVM）

參考Jerrylead 和 july-支持向量機(jī)通俗導(dǎo)論

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

中間那條線是θ T x=0，logistic回歸強(qiáng)調(diào) 所有點(diǎn) 盡可能地遠(yuǎn)離中間那條線。學(xué)習(xí)出的結(jié)果也就中間那條線。

但是：

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

我想這就是支持向量機(jī)的思路和logistic回歸的不同點(diǎn)：

支持向量機(jī)考慮局部（不關(guān)心已經(jīng)確定遠(yuǎn)離的點(diǎn)），

邏輯回歸一個(gè)考慮全局（已經(jīng)遠(yuǎn)離的點(diǎn)可能通過(guò)調(diào)整中間線使其能夠更加遠(yuǎn)離，但是也可能使一部分點(diǎn)靠近中間線來(lái)?yè)Q取另外一部分點(diǎn)更加遠(yuǎn)離中間線。）

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

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

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

所以， 函數(shù)間隔越大，說(shuō)明分類正確的置信度越大。函數(shù)間隔越小 ，比如上圖c點(diǎn)，說(shuō)明越不能確定c點(diǎn)屬于哪一類。

可以為 別的值，只是為了方便。這一點(diǎn)在參考的第二個(gè)博客上也已經(jīng)說(shuō)明了。

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

定義函數(shù)間隔如下：

也就是，這個(gè)樣本點(diǎn)x與超平面之間的間隔（但是現(xiàn)在有些不準(zhǔn)確，所以有下面的幾何間隔）。

此時(shí)，若根據(jù)SVM的思想，最大化這個(gè)間隔，就能提高分類正確的確信度了嗎？

答案是否定的，因?yàn)?，如果成比例的改變w 和b（如將它們改成2w 和2b），則函數(shù)間隔的值f(x) 卻變成了原來(lái)的2 倍（ 雖然函數(shù)值增大了，達(dá)到了目標(biāo)，但是此時(shí)超平面沒(méi)有改變 ），所以只有函數(shù)間隔還遠(yuǎn)遠(yuǎn)不夠。

我們真正關(guān)心的，其實(shí)是“幾何上”的點(diǎn)到平面的距離，于是可以用幾何知識(shí)推理出來(lái)的幾何間隔。 而不是一開(kāi)始人們想當(dāng)然定義的函數(shù)間隔。

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

又因?yàn)閤 0 是超平面w T x + b=0上的點(diǎn)，利用向量之間的運(yùn)算

再令上式乘上對(duì)應(yīng)的類別y，即可得出幾何間隔

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

接下來(lái)就是我們的目標(biāo)：尋找一個(gè)超平面， 使得離超平面比較近的點(diǎn)能有更大的間距。 也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。也就是找到最大的幾何間隔。

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

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

最大化幾何間隔

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

用函數(shù)間隔表示幾何間隔

于是得到了這個(gè)式子：

然而這個(gè)時(shí)候目標(biāo)函數(shù)不是凸函數(shù)，約束條件也不是線性的，沒(méi)法直接代入優(yōu)化軟件里計(jì)算。我們還要改寫(xiě)。前面說(shuō)到 同時(shí)擴(kuò)大w和b對(duì)結(jié)果沒(méi)有影響 ，因此，我們將全局的函數(shù)間隔值定義為1。于是，上述的函數(shù)轉(zhuǎn)變成了

由于求1/||w||的最大值，相當(dāng)于求||w||²的最小值，因此結(jié)果為：

因?yàn)楝F(xiàn)在的 目標(biāo)函數(shù)是二次的，約束條件是線性的，所以它是一個(gè)凸二次規(guī)劃問(wèn)題 。這個(gè)問(wèn)題可以用現(xiàn)成的QP (Quadratic Programming) 5優(yōu)化包進(jìn)行求解。一言以蔽之：在一定的約束條件下，目標(biāo)最優(yōu)，損失最小。

根據(jù)前面幾個(gè)文章的話，SVM作為判別模型，它的的模型，就是 w T x i + b 。參數(shù)就是w和b。學(xué)習(xí)完參數(shù)以后，新來(lái)的樣例作為x i ，得到結(jié)果大于1，說(shuō)明在超平面上面，所以是正例。反之亦然。

根據(jù)SVM的思想，SVM的初步目標(biāo)函數(shù)，就是所有樣例的幾何間隔盡可能的大

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

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

從上可以看出 ，就同時(shí)擴(kuò)大w和b就相當(dāng)于等式兩邊同時(shí)除以函數(shù)間隔 γ，而新的w和b仍然是舊的wb的函數(shù)，所以最大化仍然可以進(jìn)行。

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

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

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

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

引入對(duì)偶的優(yōu)點(diǎn)：

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

這種極值問(wèn)題怎么求

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

但是，出現(xiàn)問(wèn)題了，此時(shí)加入的約束條件g已經(jīng)不再等于0了，所以，此時(shí)可以調(diào)整算子alpha變成很大很大的 值，使結(jié)果負(fù)無(wú)窮， 這顯然是不合理的。

所以，我們需要 排除在滿足條件下，也會(huì)無(wú)解的情況。

因此，我們定義下面的函數(shù)

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

所以，當(dāng)g和h不滿足約束時(shí)，總可以調(diào)整α i 和β i 來(lái)使thetap具最大值為正無(wú)窮。

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

于是函數(shù)等價(jià)于這樣

于是原來(lái)的極值問(wèn)題min f(w) 就等價(jià)于求min θ p 了，

即：

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

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

但是，又出現(xiàn)了新的問(wèn)題，也就是，如果直接求解，首先面對(duì)的就是兩個(gè)參數(shù)（最里面的是max，這個(gè)max問(wèn)題有兩個(gè)參數(shù)），而且alpha也是不等式約束，再在w上求最小值，這個(gè)過(guò)程并不容易做。那么應(yīng)該怎么辦呢？

在最優(yōu)化課程里，當(dāng)遇到不好解的優(yōu)化問(wèn)題時(shí)，可以轉(zhuǎn)化為原問(wèn)題的對(duì)偶問(wèn)題試試。

此處，d代表對(duì)偶。D--dual

我們定義函數(shù)

θ D 將問(wèn)題轉(zhuǎn)化為先求L(ω,α,b)關(guān)于 ω 的最小值（此時(shí)α和β是固定值），之后再求θ D 的最大值。 上來(lái)面對(duì)的是一個(gè)參數(shù)，相對(duì)簡(jiǎn)單些。

相對(duì)于原問(wèn)題，更換了min和max的順序，得到了它的對(duì)偶問(wèn)題。

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

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

對(duì)偶問(wèn)題已經(jīng)表示出來(lái)了，這個(gè)對(duì)偶問(wèn)題也相對(duì)原問(wèn)題好求，那么，這兩個(gè)問(wèn)題等價(jià)嗎？或者說(shuō)，對(duì)偶問(wèn)題的解是不是原問(wèn)題的解呢？

需要用KKT條件來(lái)判斷了。

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

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

對(duì)于一般化的拉格朗日公式：

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

----------1、L對(duì) w 求導(dǎo)為零

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

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

注意此時(shí)

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

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

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

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

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

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

另外可以參考這段話：

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

由上面那句話可以知道，

折騰這么長(zhǎng)時(shí)間，也就是為了說(shuō)明，已經(jīng)知道原問(wèn)題

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

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

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

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

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

實(shí)線是最大間隔超平面，假設(shè)×號(hào)的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間隔是1的點(diǎn)，他們前面的系數(shù)α i >0， 這三個(gè)點(diǎn)被稱作 支持向量。

由上面問(wèn)題，構(gòu)造拉格朗日函數(shù)如下（沒(méi)有等式約束，所以沒(méi)有β）：

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

下面我們按照對(duì)偶問(wèn)題的求解步驟來(lái)一步步進(jìn)行，由2.1.3可知，對(duì)偶問(wèn)題的形式為：

首先求解L的最小值（最里面的先求），此時(shí)αi是固定的，L的最小值只與w和b有關(guān)。對(duì)w和b分別求偏導(dǎo)數(shù)。

得到

將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）， 即里面的min L已經(jīng)求出，接下來(lái)就是求max了

代入后，化簡(jiǎn)過(guò)程如下：

最后得到

由于最后一項(xiàng)是0，因此簡(jiǎn)化為

這里，上式中左右邊的向量?jī)?nèi)積，用方括號(hào)表示。

到這一步，拉格朗日函數(shù)只包含了一個(gè)變量α i 。接著進(jìn)行下一步 ，最大化的過(guò)程，求得α i 。

假設(shè)求得了α i 就能根據(jù)求導(dǎo)得到的結(jié)果

求得w，然后就能得到b。

b 就是 距離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。 （其實(shí)，由前面的那個(gè)x和圈的圖，可以認(rèn)為b就是截距，這個(gè)截距b等于上下兩條虛線的截距的平均值。）

注意，這里的w，b，alpha都是 向量，都是m維的向量

至于這里的α怎么求得，即上面的最大化問(wèn)題怎么求解，將留給下一篇中的SMO算法來(lái)闡明。

也就是說(shuō)，手動(dòng)解的話，還是需要利用SMO算法，求得α才行。

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

這里考慮另外一個(gè)問(wèn)題，由于前面求解中得到

用α i 代替w帶入判別模型w T x+b，得到：

也就是說(shuō)， 利用判別模型對(duì)新來(lái)樣本進(jìn)行判別時(shí) ，以前新來(lái)的要分類的樣本首先根據(jù)w和b做一次線性運(yùn)算，然后看求的結(jié)果是大于1還是小于1來(lái)判斷正例還是負(fù)例。大于1，說(shuō)明在超平面的上面，說(shuō)明是正例。同理，小于1說(shuō)明在超平面的下面，說(shuō)明是負(fù)例。

約束條件是wx+b-1小于等于零，所以判斷就是wx+b與1進(jìn)行大小比較

現(xiàn)在有了alpha，不需要求出w （那b呢，b怎么求呢，前面已經(jīng)解釋，b是由離超平面最近的間隔和負(fù)的函數(shù)間隔相等。。。得到的。所以，將新來(lái)的樣本與訓(xùn)練數(shù)據(jù)中 支持向量 做內(nèi)積以后，再確定最大的正數(shù)函數(shù)間隔以及最小的負(fù)數(shù)函數(shù)間隔，即可。）

就沖上面這段話，支持向量的系數(shù)alpha，也不能等于0。

另外，那有人會(huì)說(shuō)，與前面所有的樣本都做運(yùn)算是不是太耗時(shí)了？其實(shí)不然，我們從KKT條件中得到，只有支持向量的α i >0 （不等于零）其他情況α i 是等于零的。 比如，像前面那個(gè)x和圈的圖，新來(lái)的樣本只需要和三個(gè)支持向量做運(yùn)算即可 。

由此可以看到，求出α i 以后，只需要利用支持向量，就可以來(lái)判斷新來(lái)的樣例是正例還是負(fù)例了。也許這也是是為什么叫支持向量機(jī)吧。

上面這個(gè)公式，為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。

下面，先把沒(méi)求得的alpha放一放，趁著剛剛得到的這個(gè)公式的熱乎勁，再去看看核函數(shù)。

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

推薦閱讀：

hokkien翻譯（hockey 翻譯）

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

最優(yōu)化kkt條件（kkt條件例題）

景觀設(shè)計(jì)主題有哪些（景觀設(shè)計(jì)主題有哪些內(nèi)容）_1

鋼木門(mén)十大名牌排行榜（鋼木門(mén)十大名牌排行榜最新）