Support Vector Machines

SVM是本次课程中会介绍到的最后一种监督机器学习算法.

Optimization Objective

SVM cost1(z) and cost0(z)
如果将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 Cost Function

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)
  如果能找到满足以上两点,那么cost function就只剩第二部分了.

SVM Decision Boundary 2

使用SVM的话,decision boundary很大程度上会是上图中黑色的那一条,相比于另外两条来说,黑色的decision boundary会尽可能离所有样本的距离最远(所以也更"安全"),这个距离被称为margin,所以SVM也被称为Large margin classifier.

outliers

SVM在C设置的非常大的时候很容易受特异值的干扰,如上图中倾斜的那根decision boundary,此时需要调整C为一个略小的值.

The mathematics behind large margin classification

Vector inner product

其中||u||是向量u的长度
p是v在u上投影的长度(正负取决于u,v的夹角)
SVM Decision Boundary
为了简单起见,假设我们只有3个参数,,,其中,在满足y=1,z>=1;y=0,z<=-1时,代价函数可以看作是求的最小值.
z又可以看作,其中p是x在上投影的长度,如下图:
SVM Decision Boundary

假设我们随意作一条decision boundary(绿色),如上图左,可以证明是一条垂直于decision boundary的直线,在这种情况下p值很小,但是我们又希望,那么cost function会使得变大,导致整体代价变大.反观上图右,在这种情况下p值相对左图较大,所以我们会得到一个相对较小的,这样一来整体代价会更小.所以在使用SVM计算出的decision boundary总会离样本有足够大的margin(只要C足够大).

Why the theta is perpendicular to the decision boundary

Kernel

Non-linear Decision Boundary
之前使用Logistic Regression的时候我们会像右图一样设计hypothesis函数,但是在SVM中我们又更好的解决方案--Kernel
Kernel:对于给定的训练样本,使用landmark计算新的特征值f.
使用kernel之后,新的hypothesis将会变成
predict 1 when otherwise 0
f有很多种计算方式,下图是Gaussian Kernel
Gaussian Kernel
上图中的代表第一个landmark.由公式可知:
if :
if x far away from :
Predict by using Kernel
hypothesis如上图所示,并且挑选了,假设现在有训练样本x(粉红色)靠近,那么使用Gaussian Kernel计算得到,通过cost function假设我们求到并带入hypothesis函数可知predict y=1
那么接下来的问题,landmark怎么选?Cost function长什么样?

Landmarks

Given
choose

Cost function with kernels

Cost function
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.
与函数图如下:

Example