深入理解SVM，軟間隔與對偶問題
今天是機器學習專題的第33篇文章，我們繼續來聊聊SVM模型。
在上一篇文章當中我們推到了SVM模型在線性可分的問題中的公式推導，我們最後得到的結論是一個帶有不等式的二次項：
&\min_{\omega , b} \frac{1}{2}||\omega||^2\\
s.t.& \quad y_i(\omega^Tx + b) \ge 1, &i=1,2,3\ldots,m\\
\end{align*}\right.\]
想要了解具體推導過程的同學，可以參考我的上一篇文章：
其實上一篇的文章當中遺留了一個問題，就是我們希望得到\(||\omega||\)最小，為什麼不直接求\(||\omega||\)最小，而非要求\(||\omega||^2\)最小呢？原因就在它的解法上，因為我們要將它轉化成一個凸二次規劃問題（Quadratic Programming）。QP問題也是計算科學當中一個很重要的領域，也是比較困難的領域，因為需要對電腦以及數學都有很深的造詣。
我個人感覺和實際的機器學習以及工程結合不是非常緊密，目前主要在SVM模型的原理推導上用到，所以我們可以只需要把SVM用到的公式原理理解就可以了。
求解過程
QP問題其實有專門的QP計算包可以求它的極值，我也曾經用過，但這並不是唯一的解法，並且這種解法有一個很大的缺點在於沒辦法套用核函數。所以我們一般不使用QP規劃的方法來求解。
我們觀察一下原式，很自然的會有一種感覺，就是那些不等式很煩人。我們希望消除掉這些不等式，也有辦法，就是通過使用拉格朗日乘子法來將有約束的優化目標轉化成無約束的優化函數。
我們來看下拉格朗日乘子法的使用過程，給定一個不等式約束問題：
&\min_{x} f(x)\\ s.t.& g_i(x) \le 0, i=1, 2, \cdots, k\\
&h_j(x) = 0, j=1, 2, \cdots, m\\ & \end{align*}\right.\]
對於這個看起來很複雜的方程組，我們引入一個廣義朗格朗日函數，將它改寫成這樣：
\]
這個式子相比於上面的方程組看起來要簡單一些，但是它有什麼用呢？我們簡單分析一下，會發現\(L \le f(x)\)。因為\(\alpha_i \ge 0\)，並且\(g_i(x) \le 0\)。所以兩者相加，\(L \le f(x)\)，當\(\alpha_i = 0\)時L可以取到最大值，這時\(L = f(x)\)。所以我們要求的是\(\max L(x, \alpha, \beta)\)。
又由於我們要求的目標是\(f(x)\)的極小值，我們最終的目標是\(\min_{x} \max_{\alpha_i \ge 0} L(x, \alpha, \beta)\)。
對偶問題
接下來我們就要討論著名的對偶問題了，所謂的對偶問題，實質上是將一個帶有兩個不等式的方程的不等式進行調換順序。把\(\min \max L\)轉變成\(\max \min L\)，但問題是不等號的位置顯然是有講究的，不可以隨意調換順序，所以我們需要證明這樣調換成立的。
為了方便起見，我們把原問題寫成\(\theta_P(x)=\min_x \max_{\alpha, \beta}L(x, \alpha, \beta)\)，我們再定義一個關於\(\alpha\)和\(\beta\)有關的方程：\(\theta_D(\alpha, \beta) = \min_{x}L(x, \alpha, \beta)\)。這個方程等式的右邊是拉格朗日函數的最小化，因為x確定了之後，方程的結果就只和\(\alpha\)以及\(\beta\)相關，所以它是一個關於\(\alpha\)和\(\beta\)的函數。
我們對這個函數求極大值：
\]
不知道這個式子看起來是不是覺得有些眼熟，因為它和我們剛才推導得出來的原問題非常相似，只是不等號的位置不同。我們為什麼要列出這兩個式子呢？當然不是為了好玩的，主要是為了想要得到這樣一條不等式：
\]
我們用拉格朗日方程做過度，就可以很容易證明這個式子：
\]
我們想要用對偶問題代替原問題，就需要上面這個不等號取等。對於拉格朗日方程取等的條件，數學家們已經有了嚴謹的證明，只需要滿足Karush-Kuhn-Tucker條件（簡稱KTT條件）。KTT的條件推導也是一個挺複雜的過程，我們不做深入研究， 只需要知道它的存在就可以了。
KTT條件有這麼幾條，看起來多其實並不複雜。
\]
\]
\]
\]
\]
\]
\]
我們對照KTT條件，求解\(\theta_P(x)\)的極小值，這個就是高中數學的部分了。我們首先對原式進行化簡：
L(x, \omega, b) &= \frac{1}{2}||\omega||^2 + \sum_{i=1}^m\alpha_i(1 – y_i(\omega^T x_i + b))\\
&= \frac{1}{2}||\omega||^2 + \sum_{i=1}^m (\alpha_i – \alpha_i y_i \omega^Tx_i – \alpha_i y_ib) \\
&= \frac{1}{2}||\omega||^2 + \sum_{i=1}^m \alpha_i – \sum_{i=1}^m \alpha_i y_i\omega^Tx_i – \sum{i=1}^m \alpha_i y_ib
\end{aligned}
\]
再對\(\omega\)和\(b\)進行求導：
\]
\]
我們通過求導得出了\(\omega\)和\(\alpha\)之間的關係，也就是說只要我們確定了\(\alpha\)也就確定了\(\omega\)，另外我們可以神奇地發現上面的式子當中已經沒有了b，說明b已經被我們消去了。我們把上面求導得到的取極值時的\(\omega\)和\(b\)代入原式，消去\(\omega\)和\(b\)，可以得到：
\min_{\omega, b} L(x, \omega, b) &= \frac{1}{2}\omega^T\omega + \sum_{i=1}^m \alpha_i – \sum_{i=1}^m \alpha_iy_i\omega^Tx_i – \sum_{i=1}^m \alpha_iy_i b \\
&= -\frac{1}{2}\omega^T\sum_{i=1}^m \alpha_iy_i x_i + \sum_{i=1}^m \alpha_i – b\sum_{i=1}^m \alpha_iy_i \\
& = -\frac{1}{2}\omega^T\sum_{i=1}^m \alpha_iy_i x_i + \sum_{i=1}^m \alpha_i \\
& = \sum_{i=1}^m \alpha_i – \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j
\end{aligned}
\]
我們觀察一下是這個式子，會發現x和y都是固定的值由樣本確定，唯一的變數就只有\(\alpha\)了。我們要求的是上式的極大值，唯一的變數是\(\alpha\)，求出了\(\alpha\)就可以推導得到對應的\(\omega\)和b。
那麼這個\(\alpha\)怎麼求呢？相關的內容我們放到下一篇文章。
今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支援吧（關注、轉發、點贊）。
