Support Vector Machines
SVM是本次課程中會介紹到的最后一種監(jiān)督機器學習算法.
Optimization Objective
如果將logistic regression的cost function去掉regularization和sum相關的東西,剩下的那部分(上圖中的Cost of example)可以看作是每個樣本貢獻的代價,該代價分為兩部分,左邊部分在y=1時貢獻代價,右邊部分在y=0時貢獻代價,繼續(xù)將sigmoid函數帶入Cost of example中我們可以分別繪制y=1和y=0時cost(z)的圖形.
Recall:對于logistic regression來說,在y=1時要讓代價最小那么要滿足,y=0時情況相反.
SVM的cost(z)相對于logistic regression更簡單,當y=1時,并且時,cost(z)=0,當時表現和logistic regression類似,只是是一個線性函數,當y=0時,并且時,cost(z)=0.對于SVM來說當y=1時,代價記作,當y=0時,記作.
SVM的代價函數和Logistic Regression的代價函數形式上略微有些不同:
- cost(z)不同
- 關注點不同,LR中通過對Regularization部分使用
來影響
最終取值.SVM中通過C來影響第一部分,假設我們將C設置為一個相當大的數字,那么cost function要想最小,就會得出以下結論:
SVM Decision Boundary
1.當y=1時,我們希望,這樣cost function的前半部分會最小(0)
2.當y=0時,我們希望,這樣cost function的前半部分會最小(0)
如果能找到
使用SVM的話,decision boundary很大程度上會是上圖中黑色的那一條,相比于另外兩條來說,黑色的decision boundary會盡可能離所有樣本的距離最遠(所以也更"安全"),這個距離被稱為margin,所以SVM也被稱為Large margin classifier.
SVM在C設置的非常大的時候很容易受特異值的干擾,如上圖中傾斜的那根decision boundary,此時需要調整C為一個略小的值.
The mathematics behind large margin classification
其中||u||是向量u的長度
p是v在u上投影的長度(正負取決于u,v的夾角)
為了簡單起見,假設我們只有3個參數,,,其中,在滿足y=1,z>=1;y=0,z<=-1時,代價函數可以看作是求的最小值.
z又可以看作,其中p是x在上投影的長度,如下圖:
假設我們隨意作一條decision boundary(綠色),如上圖左,可以證明是一條垂直于decision boundary的直線,在這種情況下p值很小,但是我們又希望
,那么cost function會使得
變大,導致整體代價變大.反觀上圖右,在這種情況下p值相對左圖較大,所以我們會得到一個相對較小的
,這樣一來整體代價會更小.所以在使用SVM計算出的decision boundary總會離樣本有足夠大的margin(只要C足夠大).
Kernel
之前使用Logistic Regression的時候我們會像右圖一樣設計hypothesis函數,但是在SVM中我們又更好的解決方案--Kernel
Kernel:對于給定的訓練樣本,使用landmark計算新的特征值f.
使用kernel之后,新的hypothesis將會變成
predict 1 when otherwise 0
f有很多種計算方式,下圖是Gaussian Kernel
上圖中的代表第一個landmark.由公式可知:
if :
if x far away from :
hypothesis如上圖所示,并且挑選了,假設現在有訓練樣本x(粉紅色)靠近,那么使用Gaussian Kernel計算得到,通過cost function假設我們求到并帶入hypothesis函數可知predict y=1
那么接下來的問題,landmark怎么選?Cost function長什么樣?
Landmarks
Given
choose
Cost function with kernels
SVM使用Kernel之后的代價函數與之前不同之處在于:
1.->
2.通過Kernel新生成的特征值數量和Training Set中樣本的個數是一致的,所以第二部分中的n(代表之前的特征值數量)需要寫成m.
SVM with Kernels
總結下SVM使用Kernel的過程
1.挑選landmarks(與Training Set一一對應)
2.對于每一個樣本計算對應的向量
,(對于一些kernel在計算前需要先做feature scaling)
其中
3.將帶入到cost function中計算得到
,hypothesis完成.
注意,因為新的特征值數量是m+1,所以通過cost function 求出的 向量的大小也是m+1
SVM with Kernels high variance or bias trading off
1.cost function 中的C如果越大,即
傾向于去滿足>=Threshold或者<=Threshold來使cost function中的第一部分減小,所以
會傾向變大,這樣會導致overfitting.反之如果C越小,則會導致underfitting.
2.對于Gaussian Kernel來說越大,
的變化趨于平穩(wěn),那么容易導致underfitting.反之如果
越小,
的變化則不那么平穩(wěn),這樣容易導致overfitting.
與
函數圖如下:
