支援向量機(SVM)的值得玩味的一些要點
一. 引語
作為感知機(perceptron)的重要發展,在早期的機器學習領域,SVM絕對算的上是一個巨大的飛躍,相比於支援perceptron的無腦迭代(即不知道是否一定收斂)以及結果的隨機性(即收斂結果的隨機性),SVM以其精巧的設計和優良的模型特性使得它在問世之後便立即成為及其學習界的寵兒。
不管是從模型的設計出發,還是從模型的求解以及模型的改進,SVM都算的上是機器學習模型的一個楷模,接下來我將從幾個方面談一下我的體會,淺析一下SVM的數學之美。
二. 簡約有效的建模思想
繼承於perceptron,SVM的根本出發點在於找到一個合適的分類面,將正反兩類樣本劃分開來,而且分類面也是簡單的線性分類面。
可以說,相比於perceptron,SVM在最初的設計出發點僅僅是為了克服我們上面指出的perceptron的其中一點缺陷,也就是結果的隨機性,它試圖不僅僅要得到一個可行的結果,更重要的事,這個結果還必須具備有優良的特性,這個優良的特性,用SVM的觀點來看,也是十分簡潔的約束,那就是找到一個分類面,讓這個分類面距離正負樣本點都足夠遠,也就是最大間隔,這是十分直觀的。
三. 簡單的模型構建
得到了優化目標,那麼就要找到對於優化目標的數學描述,這個其實也不是很難。
函式間距和幾何間距用的基本上都是初中的知識,我個人覺得即使是初中生也會比較容易地得到優化目標的數學模型。
然後就是老套路,如果直接進行優化,那就是雅可比一步到位法或者是梯度下降迭代法,牛人就用牛頓法或者擬牛頓法。
但是這個問題是帶約束的問題,那麼我們就要請出拉格朗日大仙,將之轉化為無約束的問題,也就是拉格朗日函式:
$$L(w,b,\alpha ) = {1 \over 2}{\left\| w \right\|^2} - \sum\limits_{i = 1}^N {{\alpha _i}({y_i}(wx + b) - 1} )$$
四. 巧妙的模型的求解——拉格朗日對偶性
我們大可以直接去求上面的模型,但是可能會大費周章,考慮將求解過程進行拆解。
首先,我們考慮原問題的一個等價問題,也就是:
$$\mathop {\min }\limits_{w,b} \mathop {\max }\limits_\alpha L(\alpha ,w,b)$$
進一步,得到對偶問題,也就是它的下界:
$$\mathop {\max }\limits_\alpha \mathop {\min }\limits_{w,b} L(\alpha ,w,b)$$
五. 為什麼說對偶化會簡化運算
我們試著直接去求原問題的解析解,那麼可能是及其複雜的(反正我是沒啥好辦法)
但是按照最優化的一般套路,我們在無法求得一個問題的最優解的時候,往往試圖尋找它的一個下界,如果這個下界恰好還是一個下確界,那麼問題就轉化為子問題的最值問題,我們顯然有:
$$\mathop {\min }\limits_{w,b} L(\alpha ,w,b) \le L(\alpha ,w,b) \le \mathop {\max }\limits_\alpha L(\alpha ,w,b)$$
從而我們可以通過求解對偶問題的最值問題來求解原問題。
六. 對偶問題與原問題的關係
剛才我們講,對偶問題是原問題的一個下界,但是我們也許更關心的是:對偶問題到底是一個平凡下界還是一個確下界?
這個問題要涉及到原問題的凸性。
我們知道,由於對偶之後的求解目標可以看作原問題的一個漸進下確界,對偶目標一定是凸性的 。
但是問題就出在原問題不一定是凸的,我們可以說針對這個特定問題(二次規劃型問題)是成立的,但是卻不一定時時如此。
但是我們可以有一個結論,那就是如果原問題是凸的,那麼我們可以求得最優解,但是如果原問題本身就不是凸的,那麼我們也不能保證轉化之後的凸優化可以幫助我們求得最優解。
七. SVM的改進——我們的優化目標竟然是最小化方差?
我們注意到,在前面的SVM討論中,我們一直有一個前提,那就是所有的模式都被正確的分類,否則不論原問題的對偶轉化便無法完成。
我們試著讓模型進行一點擴充套件,針對近似線性可分的情況也有較好的適應性,因此我們引入了一個鬆弛變數$\xi $。
但是,我其實不太care這個鬆弛變數$\xi $的引入對原問題到底有多大的影響,我注意到一個神奇的現象,那就是如果我們審視此時優化目標:
$${1 \over 2}{\left\| w \right\|^2} + C\sum\limits_{i = 1}^N {\xi i} $$
如果從一般機器學習模型角度來看的話,那麼前一項相當於是正則項,對模型複雜度進行懲罰;而後一項則是經驗損失項,而C就是調和引數。
如果我們回頭看,我們就會發現,我們在沒有考慮錯誤分類時的優化目標竟然是最小化方差
該怎麼理解這一點呢?個人認為可以這樣解釋:
如果我們不考慮模型會錯分模式,那麼經驗損失為0,在這個前提下我們的最優面就是得到一個儘可能平滑的分類面,這也與直觀相符合。