機器學習技法 Lecture 6

Support Vector Regression


使用Kernel的Ridge Regression

回顧一下ridge regression,其實就是單純的linear regression加上squared error的regularizor。

要怎麼把kernel的概念加進去呢?
我們回想一下,kernel之所以能用,是因為w可以被z表示,上一章講解LogReg的時候已知,L2-regularized的linear model中,最佳的w一定可以被z表示,所以其實不難。

這裡我們讓z的線性組合係數由beta代表。化簡目標式會得到

然後求beta的方式很簡單,沒有條件的最佳化問題就用梯度=0去解,最後求得beta。

beta公式如下,我們可以確定反矩陣一定存在,因為K必須是半正定才是合法kernel。到這裡,我們就成功地將kernel加入ridge regression了。。

最後來比較一下linear和kernel的差別,重點在於複雜度,kernel因為要求反矩陣,所以複雜度會是資料量的立方。


Tube Regression (Support Vector Regression)

如果用kernel ridge regression做classification的話,會發現w的線性組合beta多數不是零,也就是dense,這讓prediction變得複雜,而 tube regression就是為了讓beta變sparse

Tube regression跟SVM很像(其實就是參考來的),只要在margin(以下由epsilon表示)內的點就不算犯錯。因此我們必須重新定義目標式,這會讓regression的線變成像是一個水管(tube),目標式長這樣。

然後我們真的就一直模仿SVM的過程,為了把max這個非線性的運算換掉,我們加入了ksi代表犯錯的程度(就是soft SVM)。最後式子變成以下,是個QP問題,有2N+1+d(tilt)個變數,2N+2N個constraints。這是primal的問題,再來就是把它變dual(好熟悉)。

目前有個小疑問,為什麼可以用regression直接做classification?Regression不是要追求的不是一條可以通過所有點的線嗎?而不是要把點分開。


解dual問題

這個跟SVM的時候很像,老師要我們自己好好解解看,我是沒有解啦(反正我猜作業一定有)。把新學到的叫做support vector regression(SVR),拿來跟SVM相比,下面是兩者dual+kernel解出來的樣子,最後可以用QP算出來。

我們可以觀察一下beta哪裡變sparse了。當z的係數等於0時,代表兩個ksi都等於0,也就是該點位在tube裡面。因此,support vector就是那些在tube外面的點

這裡算是有解答我前面的小疑惑,SVR的SV是離線太遠的點,剛好跟SVM相反,離線越遠越好,這反應了兩者在求的東西本來就不同。


大團圓

終於介紹完了這些類似的model,其中linear的部分,上面兩個比較少用,因為他們下方的model可以表現得比他們好。下面三個是在LIBLINEAR裡實作的

再來是nonlinear model,一樣的,下面的三個model會比上面兩個好用,他們就是LIBSVM實作的model。

下面來個大團圓。橫軸跟縱軸都有關係呀。