機器學習技法 Lecture 2

Dual Support Vector Machine
講解如何將SVM轉換成對偶形式,用另一種方式解決。


對偶支撐向量機的目的是想要消除feature transform導致參數過多的不利之處。其中用的方法是將數學式一直轉換,雖然變成另一個樣子,可是卻是解一樣的問題。主要的方法是用lagrange multiplier,把條件變成要求的目標。
真的很神奇,我小小的腦袋絕對想不出這種推導…


化簡SVM的constraints

在一開始老師就提到,要將SVM轉成Dual SVM會用到很難的數學(關於最佳化),但影片不會細談,而是使用結果。

SVM有N個constraints,代表會用到N個lagrange multipiers。加了之後變成

接下來,很神奇的,把SVM的目標式轉換成「外面min裡面max」的式子(如下)。其中min是本來就有的,神奇的是max,藉由max可以讓這個目標式算出來的東西跟原本一模一樣!因為如果b w違反了(y_n (w^T z_n + b) >= 1 ),那max裡的值會放到無限大(lagrange multipliers 都非負),絕對不可能是min。

再來,又是很神奇的,把max和min互換。原本的關係應該是小於等於(weak duality),但QP最佳化的研究說,只要滿足以下條件,兩者就相等(strong duality):

  • convex primal(凸)
  • feasible primal(原來的函數有解,找的到w b)
  • linear constraints (QP本來就是線性條件)

因此,我們又可以把問題改成

到這邊算是踏出一大步了,w b的限制不見了,跑到min max了。


用偏微分把w b再提出來

新的對偶目標式的w b限制不見了,但其實是跑到min。如果w b滿足min的話,那麼對它們偏微分就要等於零。這個條件可以當作限制(dual inner)提出來,使目標式又變得簡單,甚至整個式子只剩lagrange multipliers。


KKT Optimality Conditions

要算出上面式子必須滿足4個條件(必要條件):

  • primal feasible: (y_n(w^Tz_n+b)>=1) (SVM的條件)
  • dual feasible: 阿法n>=0 (對偶SVM的條件)(懶得查阿法的打法…)
  • dual-inner optimal: 就是上面式子max下面的constraints (要滿足對偶SVM最佳解的條件)
  • primal-inner optimal: complementary slackness (a_n(1-y_n(w^Tz_n+b))=0) (a是阿法,滿足SVM最佳解的條件,前面有解釋)

對目前SVM的問題來講也是充份條件。


QP計算alpha

到這邊其實已經進行的差不多了。把剩下的式子再整理一下,就可以用QP算了。
值得一提的是,有專門為SVM設計的QP solver,至於怎麼做的不清楚。

用QP解出阿法後,要怎麼求w b呢?

  • w很簡單,從上面的constraints就知道w是(a_ny_nz_n)的總和,直接算就好。
  • b就比較神奇一點。從complementary slackness的條件,當a不是0時,代表另外一邊一定是0,就可以算出(b=y_n-w^Tz_n)。

神奇的物理意義

當初一個a代表一個資料點給的constraint,因為complementary slackness,如果a不等於0的話,就代表(y_n(w^Tz_n+b)=1)。還記得在SVM裡,這不就是離平面最近的點啊嘛?也就是說,只要是a不等於0對應到的資料點,就是support vector!

而(w = a_ny_nz_n),也就是說,w只需要在意a不等於0的資料點就好了!呼應SVM所說的,只要support vector就可以決定平面了。(這裡指的平面是hyper plane)

老師還把SVM跟PLA做了比較,PLA從錯誤的點學習,SVM找出重要的支撐向量學習。兩者有近似的意義。


Are we done yet?

這章節的目的是要把feature transform造成的複雜度降下來,這章節用了好多力氣把SVM換成dual SVM,看似好像達到目標了,可是feature transform完的複雜度其實跑到QP問題裡的矩陣大小了。下一章節就是要講如何再從dual SVM解決矩陣大小的問題!

總覺得技法的難度跟基石比難了不少,好在老師真的很用心在設計課程,一步一步的帶領學生,讓我們了解每一章節的意義。