支持向量機SVM總結之拉格朗日對偶問題

05-01

前一章節最後得到了SVM的優化目標函數：

現在我們就需要想方設法去解這個函數優化問題。

凸優化

我們的函數優化問題是一個凸優化問題，什麼叫凸優化，我下面只是簡單得講一下，不過多深入。

解釋一下「凸」。在一段數據區間內[x1,x2]，任意的數據點都可以用 $heta X_{1}+(1- heta)X_{2}$ 表示，其中 $0leq hetaleq1$ ，這段區間稱為convex set。一個函數如果其變數域是convex set，且任意其變數域中的 $x eq y$ 都滿足： $f( heta x + (1- heta)y)leq heta f(x)+(1- heta)f(y)$ ,其中 $0leq hetaleq1$ ，則說明這個函數式嚴格凸的。二次函數曲線在實數域上是典型的一個凸的函數。

凸優化問題就是去尋找凸函數的極值。一般在沒有任何約束條件下，求函數極值一般是求偏導，然後令偏導為0，求得參數的值。這是最簡單的情況。但是我們的SVM優化目標函數是有不等式約束條件的。之前在隱馬爾可夫模型總結時，遇到過有等式約束的條件下，求函數的極值問題，使用的是拉格朗日乘子法。這個方法的具體內涵可以見quora上的經典回答。

https://www.quora.com/What-is-the-meaning-of-the-value-of-a-Lagrange-multiplier-when-doing-optimization/answer/Balaji-Pitchai-Kannu?

www.quora.com

等式約束條件下的優化問題已經知道方法了，但是我們的SVM中的優化函數是帶不等式約束條件的，這個怎麼求？這裡我讀了幾篇博客包括淺談最優化問題的KKT條件，關於SVM數學細節邏輯的個人理解（二）：從基本形式轉化為對偶問題 - xxrxxr - 博客園，給出了詳細的介紹，下面我先介紹一下對偶問題，然後結合上述博客，詳細說明對偶問題的KKT條件是如何推導出來的。

對偶問題

考慮同時帶等式約束和不等式約束的優化問題：

我們使用通用的拉格朗日乘子法，得到拉格朗日多項式：

其中， $alpha_{i}$ 是對應於 $g_{i}(w)leq0$ 的拉格朗日乘子， $eta_{i}$ 是對應於 $h_{i}(w)=0$ 的拉格朗日乘子。我們定義原始的優化目標：

這裡， $alpha_{i}$ 是非負的，這個目標就是最大化我們的拉格朗日多項式，將上述式子進行展開得到：

從上式可以得到，若我們的參數w不滿足 $g_{i}(w)leq0$ ，此時因為 $alpha_{i}$ 是非負的，那麼取 $alpha_{i}$ 為正數可以讓中間的項永遠大於0，因此 $heta_{p}(w) ightarrowinfty$ ;若參數w不滿足 $h_{i}(w)=0$ ，那麼讓 $eta_{i} ightarrowinfty$ ,使得 $heta_{p}(w) ightarrowinfty$ 。相反，若參數w滿足所有的原始約束條件，那麼此時可以得到， $sum_{i=1}^{l}{eta_{i}h_{i}(w)}=0$ ， $sum_{i=1}^{k}{alpha_{i}g_{i}(w)}leq0$ ，要使 $heta_{p}(w)$ 最大，那麼就有： $heta_{p}(w)=f(w)$ 。因此原始優化目標可以寫成：

因此我們S原來的找極小值的優化問題也可以寫成：

此時為了敘述方便，定義 $p^{*}=min_{w} heta_{p}(w)$ 表示我們需要求的最優目標值，這個通常叫做原始問題，表示原始的優化目標。

而往往對應於原始問題，我們能夠轉化為相應的對偶問題。對偶問題可以理解為在研究目標函數在約束條件下的極大值問題時，通常都存在與之匹配的求極小值的問題。因此上面的例子中，對應的對偶問題形式如下：

相當於是把原始問題中的max和min的位置進行了對調。有一個顯而易見的結論，即對一個序列先找極小值，然後在所有極小值中找到一個最大值a；對一個序列先找極大值，然後在所有極大值中找到一個最小值b。 $aleq b$ 是明顯成立的。因此有：

為何要研究對偶問題？我自己的理解是對偶問題比原始問題更容易解，容易在哪裡？可以看到對偶問題外層的優化目標參數是拉格朗日參數，然後通過求得的拉格朗日參數，間接得到我們最終要求的超平面的參數w。而原始問題外層的優化目標參數直接是w，無法直接去優化得到這個參數（因為還存在著其他未知的拉格朗日參數）

那麼什麼時候對偶問題能夠等價於原始問題呢？由於上式為 $d^*leq p^*$ ，兩個問題要等價，相當於要使 $d^*=p^*$ 。因此有數學家提出了一些理論來讓兩種問題等價。假設當前函數f以及 $g_{i}$ 都是凸的，且 $h_{i}$ 是仿射的（理解為帶截距的線性函數），同時存在w，使得 $g_{i}(w)<0$ 對所有i都成立。此時必然存在參數解 $w^*,alpha^*,eta^*$ （第一個是原始問題的解，後兩個是對偶問題的解）,使得 $d^*=p^*=L(w^*,alpha^*,eta^*)$ 。 $w^*,alpha^*,eta^*$ 必須要滿足這樣一個條件，叫Karush-Kuhn-Tucker（KKT）條件：