【機器學習 林軒田】筆記Ep2 機器學習技法(一) SVM: Dual SVM
前篇筆記
大綱
來源： 台大資訊系教授林軒田機器學習技法 Video6~9
Motivation of Dual SVM
在前一篇筆記中，我們介紹了Linear SVM，其核心目標是找到能夠有效分離資料的「最胖」分類邊界（margin），並透過二次規劃解出這條邊界，
我們也在最後留下”Large-margin hyperplanes + Feature transform” 這樣的伏筆準備今天一探究境。
資料千千萬萬種，而且大多數都是線性不可分，對於非線性問題，我們通常透過Feature transform（特徵轉換）將原始空間的資料映射到高維空間，然後在高維空間中應用Linear SVM。
這樣用意結合兩樣好處
- Large-margin 有助於降低 VC Dimension，進一步限制模型複雜度，又可以加強泛化能力
- 特徵轉換則增加模型的表現力，降低訓練誤差 Ein
一切聽起來都如此美妙…
然而，做特徵轉換會帶來計算挑戰。當資料被映射到高維空間後，其維度從 d增加到dhat+1
隨著維度增長，求解二次規劃問題變得更加困難，甚至在dhat無限大的情況下幾乎無法處理。
所以我們需要另一種方法，使得 SVM 的求解過程不再依賴於dhat ，而僅與樣本數量N有關，這就是Dual SVM的核心動機。
找到目標後，就來試著建模看看吧！
其實在數學上我們有一種破解方法，就是將目前SVM問題轉成對偶(dual)問題，
- 原始 SVM 的二次規劃問題涉及 dhat + 1 個變數和 N 個限制條件。
- 對偶 SVM 則將變數數量轉化為 N，限制條件增加到 N + 1
這樣可以有效地減少對 dhat的依賴：
回顧時間：
在機器學習基石課程中，介紹Regularization時，透過在最小化 Ein 的過程中添加限制條件 w^T w ≤C。我們的求解方法是引入拉格朗日因子 λ，將有條件的最小化問題轉換為無條件的最小化問題
最終可以得到 w 的最佳解：
在正則化問題中，λ是已知的量（使用者事先決定），求解過程相對簡單。然而，在Dual SVM問題中，我們也可以引入 λ，將有限制式問題轉換為無限制式問題。
不同的是，這裡的λ 是未知參數，且其數量為 N，需要透過演算法來求解。
接下來就要引入拉格朗日因子α來將有限制最佳化問題轉成無限制式最佳化問題。
（ Regulation時使用λ，但這邊因為學術圈習慣改成叫α（alpha）。）
這邊直接看圖片，左邊是原本的問題，右邊將α與移項後的限制式做線性組合，一起納進了原目標式中。
新的函數我們稱它為拉格朗日函數，包含三個參數(b, w, α)
而新的SVM問題考慮了拉格朗日函數，轉變成：
什麼鬼，怎麼突然變這樣！
我們來分析一下為什麼會變成最小化問題中包含一個最大化問題：
首先我們假設α_n ≥ 0，並搞清楚最終要得到的還是
現在聚焦於
則對於可能的(b, w)組合：
考慮以上狀況後，取Max實際上就是想辦法得到我們要的 1/2 w^Tw，最外層的min則是會在 1/2 w^Tw與無窮大之間選，
想當然爾最終會得到 1/2 w^Tw，成功達成目的！
Lagrange Dual SVM
現在我們有最新的目標：
其實還是不會解，但我們發現一個性質，
如果我們將拉格朗日因子都固定下來，可以形成以下不等式：
右項再加上取Max，不等式仍然成立：
做到這邊，其實默默地將min, MAX調換過來，也默默地完成了原問題的Lagrange Dual問題。
不等式右邊稱為我們原SVM問題的lower bound，你可能會問，
解決lower bound不等於解決原問題啊？
但是呢，我們可以去觀察原問題（左側）是否滿足三個條件：
- 凸函數（convex）
- 有解（feasible）
- 限制式是線性的（linear constraints）
如果滿足，則這個不等式滿足「強對偶條件」，可以將原本弱對偶關係（≤ or ≥）轉變成強對偶關係（=）
那顯然是有的！有了強對偶性的支持，我們就可以將目標聚焦在解右邊的式子了。
所以我們來化簡一下右邊的式子：
看到求一個函數的最小值不自覺就會利用梯度為零的方式，那我們也來處理看看梯度為零，先展開函數：
- 首先考慮拉格朗日函數對於參數b梯度為零：
事實上，我們可以把這個限制條件加進去前面Max中，則拉格朗日函數可以再簡化成
- 再來，考慮拉格朗日函數對於參數w梯度為零：
得到
同樣可以把這個限制條件加進去前面Max中，則拉格朗日函數發現神奇的變化
經過一番努力後，我們得到最終化簡
在這最後的關卡，我們要如何解開這個問題，就要配合KKT Condition，
KKT Condition是強對偶性成立時，存在最優解的必要條件，需要滿足：
- primal feasible
- dual feasible
- dual-inner optimal
- primal-inner optimal
有了KKT的支持，我們就可以來求最佳解了！
Solving Dual SVM using KKT
經過辛苦的簡化後，我們得到：
看到Max就知道要再轉成min（符號改變，為習慣解法），然後把並且將我們剛剛求導得到的限制式列出來，其中：
轉成這樣很顯然的，這是一個QP問題，有N個變量，限制式有N+1個
然後就根據上一篇筆記的流程，找出Q，p，A，c
右圖是回顧之前的QP轉換，會發現這次的Q矩陣（由q_nm組成）變得很「醜」，大部分不是0，稱之為dense
這邊先為dense埋下一個伏筆，然後來看看怎麼處理目前的Q
會發現當N很大的時候，例如N等於十萬，我們的dense Q矩陣計算量會變很大，並且空間也會佔滿N²，所以對於Dual SVM的Q還有一套方法論可以做簡化，這邊不會再贅述如何簡化。
簡單來說，這次找的二次規劃工具要包含可以簡化Dense Q矩陣的才比較好。
接下來交給二次規劃工具，我們求到了最終的α_n，接著利用之前的條件，就可以反推出(w, b)
現在可以來解釋為什麼稱作”SV”M了
接下來來剖析一下Dual SVM的意義是什麼。
Messages behind Dual SVM
先澄清觀念，並不是所有落在boundary上的點都稱為SV，儘管他們在幾何上也看似在「支撐」，有嚴格遵守α_n > 0並且落在boundary上的點才可以稱作SV，其餘α_n= 0的點稱為candidates
為什麼α_n > 0才有資格稱作SV呢？
因為在我們最後要求(w,b)的公式中，只有α_n > 0才可以求得出不為0之(w,b)，
搞笑一點來講，candidate依附在boundary上面，但其實一點力都沒支撐，是薪水小偷。
回到SVM意義上來說，其實就表示我們的樣本裡面有一些boundary的「決定性樣本」Support Vector 與「其他樣本」not-SV，not-SV對我們計算boundry沒有影響，所以我們不需要他們。
而SVM就可以幫助我們找到那些Support Vector
接著來看看從不同角度思考的模型們
比較SVM與PLA：
我們可以觀察到，SVM 是由large margin上所有的SV所決定的，而 PLA 是由當前分類錯誤的所有樣本所決定的，
無論是 SVM 還是 PLA，都可以表示為原始資料 y_nz_n 的線性組合形式，這樣的轉換可以等價(represented)於對原始資料做計算。
從白話文講就是
- SVM透過學習很重要的點來學會分類
- PLA透過學習錯誤的點來學會分類
故事有完美的結局了嗎，還早呢！
記得前面埋的小伏筆dense嗎？
- Primal Hard-Margin SVM 有 dhat + 1 個參數，以及 N 個限制條件。當 dhat + 1很大時，求解問題會變得困難。
所以我們費了大番工夫轉成Dual形式，得到
- Dual Hard-Margin SVM 則有 N 個參數，以及 N + 1 個限制條件。
但是！儘管我們參數量減少了，還是在計算過程中面臨到dense Q矩陣的問題，
當 N 很大時，我們好像又沒輒了！
那Dual這些過程是在做白工嗎，並不是的，馬上我們就會結合Kernel來達成我們最後真正的目標，
讓SVM計算上擺脫對 dhat （或者說N）的依賴
章節回顧
- Motivation of Dual SVM：從Linear SVM轉變成Dual SVM問題，並引入拉格朗日因子形成拉格朗日函數
- Lagrange Dual SVM：推導出對偶問題以及發現滿足強對偶性與KKT condition
- Solving Dual SVM：利用KKT解決Lagrange Dual SVM問題
- Messages behind Dual SVM：SVM的意義以及還沒被解決的問題
下篇筆記
題外話murmur：Medium不支援latex數學式真的太痛苦了，要是有解方的朋友們也可以私訊我！
