機器學習技法 Lecture 4

Soft-Margin Support Vector Machine
能夠犯錯的SVM。


前幾章講的SVM都不能犯錯,稱為Hard-Margin SVM。這大部分的資料是不存在可以完美分開的平面的。因此,我們需要一個能夠容忍錯誤的hypothesis。(原本以為從hard變soft會很麻煩,沒想到其實蠻簡單的。)


加入「到邊界距離」的觀念

首先,把「錯誤」加入要minimize的式子:C是控制「錯誤容忍度」的係數,C愈大,容忍度愈低。而原本SVM的constraints只需要「對的點」滿足就好。

上面的式子有個壞處,它變成不能微分,也就無法用QP解。怎麼辦呢?我們觀察到,犯錯的點也有分錯大錯小。因此,比較好的minimize目標應該是整體的錯誤程度,我們用新的符號表式,念作ksi。(到後面會發現神奇的物理意義,我自己覺得神奇啦)現在,我們已經把式子改成可容忍錯誤,ksi代表的就是該資料點的margin violation。


改成dual的形式

這裡就跟對偶SVM那章很像,加入lagrange multipliers以消除constraints。
在第2章,接下來的步驟是對w b取偏微分,但這裡我們先對ksi取偏微分,可以得到alpha和beta跟C的關係,而且ksi還能從消掉。

再來就是dual inner problem,跟第2章一樣,對w b偏微,得到一模一樣的條件。最後變成下面的式子,可以發現唯一的差別在於,alpha會被C限制這就是一個QP問題了,只是constraints變多,有2N+1個。


加入kernel

沒什麼難度,跟第三章一樣。


計算b

用QP算出alpha後,我們就能輕易的算出w,但是b就不一樣了。之前的SVM是用complementary slackness算出來的,soft-margin也是一樣的概念,但多了一點變化。這裡有兩個找出b的可能:

  • alpha > 0,代表support vector
  • alpha < C,代表free support vector

找到free SV就能算出b(如果沒有的話,只能找出b的上下限)。


Soft SVM的幾何意義

C愈大,代表愈不能容忍錯誤,所以會愈複雜。下圖是用了gaussian kernel的SVM,可以看出當C太大時,仍然會overfit。

資料點可以依alpha beta ksi,在空間中(幾何意義)分成三類:

  • 非SV:alpha=0,ksi=0。這種點沒有犯錯,也不在邊界上。
  • free SV:0<alpha<C,ksi=0。這種點是SV,且在邊界上。
  • bounded SV:alpha=C,ksi=犯錯的大小。這種點就是違反邊界的點。

怎麼選擇model?

將Gaussian kernel加上C後,可以降低overfit,但也因為參數變成C跟gamma,要調整的難度也變高。怎麼選擇呢?就是用cross validation

這裡有一個特別的上下限關係,leave one out cross validation的error一定會小於SV的比例:證明的概念在於:
如果拿掉的拿點不是SV,那麼對於model一點影響也沒有,而且那個點一定不會犯錯。
如果拿掉的點是SV,model可能就變了,而那個點可能本來就是犯錯的點,model變了依然可能犯錯。
所以整體犯錯的比例會小於等於SV的比例。

因此,我們除了用cross validation選擇model外,也可以用SV的數量來檢查。然而,這只是一個上下限的關係,並不一定能夠選出一個最好的model。


小總結

其實加上犯錯容忍度比想像中的簡單,不同的地方也沒有很多:

  • 在原本hard的alpha加上一個上限
  • 從alpha推回b的方法
  • 資料點相對平面關係的種類(bounde SV、free SV、non SV)