本周主要學習SVM
一、 内容概要
- Large Margin Classification
- Optimization Objective（優化Objective（損失函數））
- Large Margin Intuition（大邊距的直覺了解）
- Mathematics Behind Large Magin Classification（最大間距分類器背後的數學推導）
- Kernels
- Kernels 1
- Kernels 2
- SVMs in Practice
- Using An SVM
二、重點&難點
1. Large Margin Classification
1) Optimization Objective（優化Objective（損失函數））
- 回顧一下邏輯回歸模型
\[h_θ(x) = \frac{1}{1+e^{-θ^Tx}}
\]
\[J(θ)=\frac{1}{m} [\sum_{i=1}^{m} y^{(i)}( -logh_θ(x^{(i)})) + (1-y^{(i)})(-log(1-h_θ(x^{(i)}) ) ] + \frac{λ}{2m}\sum_{j=1}^{n}θ_j^2
在SVM中對cost function作如下等效變化（即将log函數替換成折線）
-
折線化變形
替換後cost function變為
\[J(θ)=\frac{1}{m} [\sum_{i=1}^{m} y^{(i)}Cost_1(θ^Tx^{(i)}) + (1-y^{(i)})Cost_0(θ^Tx^{(i)}) ] + \frac{λ}{2m}\sum_{j=1}^{n}θ_j^2
Cost的下标分别表示y所對應的值。
-
去m變形
另外我們知道為了得到最優化的一組θ，我們需要通過求\(min J(θ)\)進而得出一組解，是以上式中的m可以約掉，因為m是常數，是以對于求最小值沒有影響，是以cost function可以進一步變形為：
\[J(θ)= [\sum_{i=1}^{m} y^{(i)}Cost_1(θ^Tx^{(i)}) + (1-y^{(i)})Cost_0(θ^Tx^{(i)}) ] + \frac{λ}{2}\sum_{j=1}^{n}θ_j^2
-
乘以C變形
繼續變形前我們可以假設上式左邊為訓練資料集項(Training data set term),記為A，右側為正則項，記為λB，是以有\(J(θ) = A+λB\)。
按照上面所說，此時在等式兩側乘以一個數不會影響最終的結果，假設乘以一個C（\(C=\frac{1}{λ}\)），是以有\(J(θ)=CA+B\)
此時有
\[J(θ)= C[\sum_{i=1}^{m} y^{(i)}Cost_1(θ^Tx^{(i)}) + (1-y^{(i)})Cost_0(θ^Tx^{(i)}) ] + \frac{1}{2}\sum_{j=1}^{n}θ_j^2
2) Large Margin Intuition（大邊距的直覺了解）
上面将普通邏輯回歸中的log函數變形後得到的曲線如下：
差別：
If y=1, we want \(θ^Tx≥1\) (not just ≥0)
If y=0, we want \(θ^Tx≤-1\) (not just ≤0)
和引入正則項同理，當C取非常大的值時，我們希望如下藍色圈住的部分接近于0，即使得A=0
但是要如何使A=0呢？參考上面的折線圖，我們可以知道要使得A=0，則需要滿足：
- 當y=1,則\(θ^Tx≥1\)
- 當y=0,則\(θ^Tx≤-1\)
此時即等價于
3) Mathematics Behind Large Magin Classification
在推導公式之前需要回顧一下向量内積的概念。
已知SVM的優化目标是：
\[min\frac{1}{2}\sum_{j=1}^nθ_j^2 且滿足
\[當y=1時,theta^Tx^{(i)}≥1
\[當y=0時,theta^Tx^{(i)}≤-1
為了友善了解，令\(θ_0=0\)，特征數n=2，則有
\[min\frac{1}{2}\sum_{j=1}^nθ_j^2 = \frac{1}{2}(θ_1^2+θ_2^2)=\frac{1}{2}\sqrt{(θ_1^2+θ_2^2)}^2=\frac{1}{2}||θ||^2
其中，||θ||為向量θ的長度或稱為θ的範數。
如果将\(θ^Tx(i)\)看成是經過原點(因為θ0=0) 的兩個向量相乘，如下圖：
則\(θ^Tx^{(i)}\)等價于向量\(x^{(i)}\)在向量θ上的投影\(p^{(i)}\)與θ的範數||θ||相乘，即
\[θ^Tx^{(i)} = p^{(i)}||θ|| = θ_1x_1^{(1)}+θ_2x_1^{(2)}
故SVM優化目标變為
\[min\frac{1}{2}||θ||^2 且滿足
\[當y=1時,p^{(i)}||θ||≥1
\[當y=0時,p^{(i)}||θ||≤-1
直覺的了解\(p^{(i)}||θ||\)的意義。
假設theta0=0,下面展示了一個小間距決策邊界的例子。（綠色為決策邊界）
-
首先解釋一下為什麼θ向量會垂直于決策邊界。
因為θ的斜率是\(\frac{θ_2}{θ_1}\),決策邊界表達式為\(θ^Tx=0\),即\(θ_1x_1+θ_2x_2=0\),斜率為\(\frac{θ_2}{θ_1}\)，是以θ向量會垂直于決策邊界。
-
看第一個例子(x1)
假如決策邊界最開始如下圖
将\(x^1\)投影到θ向量，得到\(p^1\)，可以看到\(p^1\)值很小。SVM的優化目标是\(min\frac{1}{2}||θ||^2\)，但是還需要滿足\(|p^{(i)}||θ|||≥1\)，而又因為\(p^1\)值很小，是以||θ||值就需要較大才行，顯然這與優化目标背道而馳，是以還有優化的空間。
x2 同理，不再贅述。
- 優化後的例子
此時\(p^1\)值明顯增大，||θ||變小，達到優化目的。
2. Kernels
1) Kernels 1
之前課程中已經提到過通過使用多項式來解決非線性拟合問題，如下圖所示
-
引入核函數
在SVM中我們引入核函數來解決這個問題。
假設\(h_θ(x) = θ_0+θ_1f_1+θ_2f_2+……\)，然後随機人為的選取幾個向量\(l^{(i)}\)作為标記（landmarks），為友善說明選取三個：
同時定義核函數（核函數很多種，這裡使用的是高斯核函數Gaussion Kernels）為
\[f_i = similarity(x^{(i)}, l^{(i)}) = e^{(-\frac{||x^{(i)}-l^{(i)}||^2}{2δ^2})}
這裡的核函數\(f_i\)可以了解成相似度，即點x與标記點l如果很相近則預判為1，反之為0.
由高斯核函數的表達式也可以很好的了解：
\[若x^{(i)}≈l^{(i)},則f_i≈1
\[若x^{(i)}與l^{(i)}相距較遠,則f_i≈0
另外高斯核函數中有一個參數\(δ^2\)，它對于結果的影響如下面幾個圖所示
可知\(δ^2\)越小，圖像越窄，下降的速度也就越快。
- 核函數計算示例
首先還是假設選取三個landmarks，并且分類的方法是：
\[若θ_0+θ_1f_1+θ_2f_2+……≥0，預測為1，反之為0
假設θ向量已知為\(θ_0=-0.5,θ_1=1,θ_2=1,θ_3=0\)
下面看第一個點的分類情況：
此時\(x≈l^{(1)}，故f_1=1\)，同理因為遠離其餘兩個landmarks，是以\(f_2=0,f_3=0\)。
是以帶入計算公式有
\[h_θ(x) = θ_0+θ_1f_1+θ_2f_2+θ_3f_3=-0.5+1*1+1*0+0*0=0.5≥0
故該點y=1
繼續看下圖新添的兩個x坐标點
和如上同樣的分析後可以知道，綠色的點有y=1，青色的點是y=0
按照上面的計算方法，在計算了大量點後可以得到如下的邊界
2) Kernels 2
-
優化目标
上面的landmarks都是人工選取的幾個點而已，但是真實計算時會計算很多點。另外因為引入了核函數，是以SVM優化目标變為：
\[minJ(θ)=min C[\sum_{i=1}^{m} y^{(i)}Cost_1(θ^Tf^{(i)}) + (1-y^{(i)})Cost_0(θ^Tf^{(i)}) ] + \frac{1}{2}\sum_{j=1}^{n}θ_j^2
注意原來cost函數中的x變成了f。
另外上式中右邊的正則項可以變成\(\sum_{j=1}^{n}θ_j^2=θ^Tθ\)，還可以繼續變形
\(\sum_{j=1}^{n}θ_j^2=θ^Tθ=θ^TMθ\)，其中矩陣M取決于你所使用的核函數。
需要注意，上述那些SVM的計算技巧應用到别的算法，如邏輯回歸中，會變得非常慢，是以一般不将核函數以及标記點等方法用在邏輯回歸中。
- 參數影響
1.C
前面提到過的\(C=\frac{1}{λ}\),C對bias和variance的影響如下：
C太大，相當于λ太小，會産生高方差，低偏差；
C太小，相當于λ太大，會産生高偏差，低方差。
2.\(δ^2\)
\(δ^2\)大，則特征\(f_i\)變化較緩慢，可能會産生高偏差，低方差；
\(δ^2\)小，則特征\(f_i\)變化不平滑，可能會産生高方差，低偏差。
3. SVMs in Practice
1) Using An SVM
SVM和邏輯回歸的選擇問題
什麼時候該用邏輯回歸？什麼時候該用SVM？
①如果n相對于m來說很大，則應該使用邏輯回歸或者線性核函數（無核）的SVM。
m較小時，使用線性分類器效果就挺不錯了，并且也沒有足夠的資料去拟合出複雜的非線性分類器。
②如果n很小，m中等大小，則應該使用高斯核函數SVM。
③如果n很小，m很大，則高斯核函數的SVM運作會很慢。這時候應該建立更多的特征變量，然後再使用邏輯回歸或者線性核函數（無核）的SVM。
對于以上這些情況，神經網絡很可能做得很好，但是訓練會比較慢。實際上SVM的優化問題是一種凸優化問題，好的SVM優化軟體包總是能找到全局最小值或者是接近全局最小的值。