Support Vector Machines
SVM是本次课程中会介绍到的最后一种监督机器学习算法.
Optimization Objective
如果将logistic regression的cost function去掉regularization和sum相关的东西,剩下的那部分(上图中的Cost of example)可以看作是每个样本贡献的代价,该代价分为两部分,左边部分在y=1时贡献代价,右边部分在y=0时贡献代价,继续将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来说越大,
的变化趋于平稳,那么容易导致underfitting.反之如果
越小,
的变化则不那么平稳,这样容易导致overfitting.
与
函数图如下:
