ML-對偶(Duality)問題 KKT 條件

對偶(Duality)問題 KKT 條件

Primal => Dual

現實中我們遇到的原優化問題, 寫為标準型的話是這樣的.

\(min _w f(w) \\ s.t. \\ g_i(w) <=0 \\ h_i(w) = 0\)

即要求的是在w滿足限制條件下, 且使得f(w)取得最小值的 w 的值.

那我們通常的做法是通過引入拉格朗日函數:

\(L(w, \alpha, \beta) = f(w) + \sum _{i=1}^{k} \alpha_i g_i(w) + \sum _{i=1}^{t} \beta_i h_i(w)\)

其中\(\alpha, \beta\) 都大于等于0, 稱為拉格朗日算子. 至于為什麼能這樣做, 參考"對偶問題初識"的筆記裡我有推導, 更詳盡的可以翻翻高數, 關于帶限制條件下求函數極值的部分, 分别從幾何和分析的兩個角度有推導(核心就是偏導數,梯度向量(法向量)平行), 這裡就過了,不想牽扯太多.

現在來考慮一個max 的函數:

\(\theta_p(w) = max _{\alpha, \beta} L(w, \alpha, \beta)\) 即針對 \(\alpha, \beta\)要對L(w) 取最大.

對于給定的w, 如果對于原問題 f(w)中沒有對w進行限制, 則可得出\(\theta_p(w)\)的是無窮大的.

\(\theta_p(w) = [f(w) + \sum _{i=1}^{k} \alpha_i g_i(w) + \sum _{i=1}^{t} \beta_i h_i(w)] = \infty\)

如過 w 滿足primal 的限制, 則\(\theta_p(w) = f(w)\), 這裡的"=",應該表示"最優化問題等價"不是數值上等于,感覺. 這裡有一點繞, 其實想表達的是這樣的思想:

欲對關于\(w,\alpha, \beta\)的函數\(L(w,\alpha, \beta) 取min\)時的優化問題, 轉為先對 \(\alpha, \beta\) 優化取max, 再優化 w

用數學的形式來表達這樣的思想即:

\(min_w \ [\theta_p (w)] =min_w \ [max_{\alpha, \beta} \ L(w, \alpha, \beta)]\)

再定義: \(\theta_D(\alpha, \beta) = min_w \ L(w, \alpha, \beta)\)

• \(\theta _p(w)\) 是針對 \(\alpha, \beta\) 的max最優化
• \(\theta_D(\alpha, \beta)\) 是針對 w 的min最優化

也就是将dual 的問題可定義為:

\(max_{\alpha, \beta} \ [\theta_D(\alpha, \beta)] = max_{\alpha, \beta \ min_w \ [L(w, \alpha, \beta)]}\)

對于原始及其對偶問題, 我們假設

• p* 為primal 問題 \(min_w \ \theta_p(w)\)
• d* 為其 dual 問題 \(max_{\alpha, \beta} \ \theta_D(\alpha, \beta)\)

必然有:

$p^* = min_w [max_{\alpha, \beta} \ L(w, \alpha, \beta)] >= max_{\alpha, \beta} \ [min_w \ L(w, \alpha, \beta)]= d* $

關于 p* >= d* 在"對偶問題初識"的筆記中有過證明, 根據限制條件及定義證明的

有一種這樣的感覺: 對一個多元函數有: "min max" >= "max min", 多個參數哈.

KKT

關于primal 和 dual 的一個最為重要的結論, 莫過于p* >= d* (用限制定義證明)

\(minmize \ f_0(x) \\ s.t. \\ f_i(x) <=0, i=1,2,..m \\ h_j(x) = 0, j = 1,2...p\)

在凸優化及對偶的初識中, 我們知道, 如果 p = d*, 則稱為強對偶, 當函數為convex, 一般會成立. 同樣, 如果已經函數是convex. 如果滿足: \(\exists \ x', f_i(x') <0, h_j(x')=0\)強對偶*的哦.

我們進一步還推導了 complementary slackness 條件

即如果 p*=d * 必然要有 \(\lambda^* f_i(x) = 0\)

這裡先引入結論, p*=d * ** 隻有在KKT條件下才會滿足**

KKT

• 是以3個科學家名字命名的: Karush-Kuhn-Tucke
• 廣義化的拉格朗日數數乘的擴充

SVM算是KKT的一個最典型的應用了. 假設 f, g 都是convex函數\(f(w) = w^Tw\)的限制條件, 滿足\(h_i(w), g_i(w)\) 都是 \(a_i^Tw+b\) 的線性形式, 同時假設存在w使得\(g_i(w)<=0 恒成立\). 則一定存在\(a_i^*, \beta^*, w^*\) 滿足Karush-Kuhn-Tucker(KKT)條件,而 [ \(a_i^*, \beta^*, w^*\)] 也正好是 **p*=d ***的解, KKT條件即:

\(\frac {\partial } {\partial w_i} L(w^*,a_i^*, \beta^*)= 0\)

\(\frac {\partial } {\partial \beta_i} L(w^*, a_i^*, \beta^*)= 0\)

\(\alpha_i^*g_i(w^*) = 0\) (很關鍵的 complementary 條件哦, 已認證定義證明)

\(g_i(w^*)<=0\)

\(a^* >= 0\)

why KKT?

不難發現在很多問題求解, 我們大多能轉為dual的問題, 然而如果不能滿足KKT條件, dual的問題可能不能簡化primal問題的求解, KKT我自己平時也基本不會用到, 不過在SVM中卻被巧妙地用到了, 就是有一條關鍵性質:

\(\alpha_i^*g_i(w^*) = 0\)

使得SVM在求解參數的時候, 簡化了大量的運算量, 進而找到那些支援向量就搞定了, 其他地方, 歐文感覺也沒太用到, 不過運籌學方面,應該會有涉及一點, 我也不管, 就像了解一波KKT和推導SMV, 裝逼一波, 然後應用上做一個自信的調參俠,僅此而已, 下一波就推導SVM.