NTU ML14 notes

Hard margin dual problem 就是用 Lagrange 把前面的不等式轉換。 我們從這邊開始：

Subject to:

以下轉換並說明 minimize 這個問題是等價的：

1. 給定的 $w, b$ 有 $1-y_i(w^Tx_i+b) > 0$，也就是有限制被違反， $\max_{\alpha\ge 0} \cdots = \infty$。
2. 給定的 $w, b$ 全部 $1-y_i(w^Tx_i+b) \le 0$， $\max_{\alpha\ge 0} \cdots$ 有限。

也就是說不符合條件的 $w, b$ 被自動拿掉了，我們把條件藏起來了，重點是我們現在不再有對 $w, b$ 的限制。

Lagrange 告訴我們：在我們的情況 (QP) 下可以這樣交換

左邊的問題就是我們原先的問題，右邊的問題就是 dual problem， 因為現在不再有對 $w, b$ 的限制所以內層變得很好解。

從這個式子開始

對 $b$ 微分

對 $w$ 微分

整理得到

也就是說加入這些條件不會影響結果：

把那些條件代入

再把 $w$ 的限制代入

很神奇地，$L(w,b,\alpha)$ 和 $w, b$ 無關，因此我們可以拿掉 $w, b$ 的限制。

這就是推導出的 dual problem 的形式。這個問題現在只跟 $\alpha$ 有關，此外，對於求 $\alpha$ 的那些限制可以用用來解 $w, b$

解完這個問題後，KKT condition 告訴我們 dual problem 得到的解會符合這些條件（在 SVM 的情況為下充要條件）：

• 滿足原來 primal problem $y_i(w^Tx_i+b) \ge 1$，這是廢話 (primal feasible)
• 滿足 dual problem $\alpha \ge 0$，這是轉成 dual 時要求的，也是廢話 (dual feasible)
• $0 = \sum_{i=1}^N \alpha_i y_i$ 跟 $w = \sum_{i=1}^N \alpha_i y_i x_i$，這是我們微分算出來的 (dual-inner optimal)
• $\alpha_i (1-y_i(w^Tx_i+b)) = 0$ (primal-inner, complimentary slackness)，這是在 primal peoblem 中得到的結論。

補充說明，KKT 是三個數學家的名字開頭，提出了這個理論，並且跟 KKE 無關。