svm理論與實驗之5: 線性分類器的求解

徐海蛟博士 Teaching.

一個求最小值的問題就是一個優化問題（也叫尋優問題，更文绉绉的叫法是規劃——Programming），它同樣由兩部分組成，目标函數和限制條件，可以用下面的式子表示：

　　（式1）

　　限制條件用函數c來表示，就是constrain的意思啦。你可以看出一共有p+q個限制條件，其中p個是不等式限制，q個等式限制。

　　關于這個式子可以這樣來了解：式中的x是自變量，但不限定它的維數必須為1（是你解決的問題空間維數，對我們的文本分類來說，那可是成千上萬啊）。要求f(x)在哪一點上取得最小值（反倒不太關心這個最小值到底是多少，關鍵是哪一點），但不是在整個空間裡找，而是在限制條件所劃定的一個有限的空間裡找，這個有限的空間就是優化理論裡所說的可行域。注意可行域中的每一個點都要求滿足所有p+q個條件，而不是滿足其中一條或幾條就可以（切記，要滿足每個限制），同時可行域邊界上的點有一個額外好的特性，它們可以使不等式限制取得等号！而邊界内的點不行。

　　這對一般的優化問題可能提供不了什麼幫助，但對我們的 SVM來說，邊界上的點有其特殊意義，實際上是它們唯一的決定了分類超平面，這些點（想象他們就是以前的圖中恰好落在H1和H2上的點，在文本分類問題中，每一個點代表一個文檔，因而這個點本身也是一個向量）就被稱為支援向量。

　　關于可行域還有個概念不得不提，那就是凸集，凸集是指有這麼一個點的集合，其中任取兩個點連一條直線，這條線上的點仍然在這個集合内部，是以說“凸”是很形象的（一個反例是，二維平面上，一個月牙形的區域就不是凸集，你随便就可以找到兩個點違反了剛才的規定）。

　　回頭再來看我們線性分類器問題的描述，可以看出更多的東西。

　　（式2）

　　在這個問題中，自變量就是w，而目标函數是w的二次函數，所有的限制條件都是w的線性函數（哎，千萬不要把xi當成變量，它代表樣本，是已知的），這種規劃問題有個很有名氣的稱呼——二次規劃（Quadratic Programming，QP），而且可以更進一步的說，由于它的可行域是一個凸集，是以它是一個凸二次規劃。

　　一下子提了這麼多術語，實在不是為了讓大家以後能向别人炫耀博士學識的淵博，這其實是我們繼續下去的一個重要前提，因為在動手求一個問題的解之前（好吧，我承認，是計算機求解……），我們必須先問自己：這個問題是不是有解？如果有解，是否能找到？

　　對于一般意義上的規劃問題，兩個問題的答案都是不一定：不一定有解、即使有解也不一定找得到求得出來！但是，但是，凸二次規劃讓人喜歡的地方就在于：它有解（教科書裡面為了嚴謹，常常加限定成分，說它有全局最優解，由于我們想找的本來就是全局最優的解），而且可以找到！（當然，依據你使用的算法不同，找到這個解的速度，行話叫收斂速度，會有所不同）

　　對比（式2）和（式1）還可以發現，我們的線性分類器問題隻有不等式限制，是以形式上看似乎比一般意義上的規劃問題要簡單，但解起來卻并非如此。

　　因為我們實際上并不知道該怎麼解一個帶限制的優化問題。如果你仔細回憶一下念大學時候的高等數學的知識，會記得我們可以輕松的解一個不帶任何限制的優化問題（實際上就是當年背得爛熟的函數求極值嘛，求導再找0點呗，誰不會啊？笑^_^），

我們甚至還會解一個隻帶等式限制的優化問題，也是背得爛熟的，求條件極值，記得麼：通過添加拉格朗日乘子，構造拉格朗日函數，來把這個問題轉化為無限制的優化問題雲雲（如果你一時沒想通，我提醒一下，構造出的拉格朗日函數就是轉化之後的問題形式，它顯然沒有帶任何條件）。

　　學生問：如果隻帶等式限制的問題可以轉化為無限制的問題而得以求解，那麼可不可以把帶不等式限制的問題向隻帶等式限制的問題轉化一下而得以求解呢？

　　可以，實際上我們也正是這麼做的。下一節就來說說如何做這個轉化，一旦轉化完成，求解對任何學過高等數學的人來說，都是小菜一碟。