Machine Learning 06 - Support Vector Machine

正在学习Stanford吴恩达的机器学习课程，常做笔记，以便复习巩固。
鄙人才疏学浅，如有错漏与想法，还请多包涵，指点迷津。

6.1 Large Margin Classification

6.1.1 Optimizaiton objective

Here we intorduce the last supervised algorithm : Support Vector Machine.

Hypothesis :

Cost function :

where cost1$cos{t}_1$ is the cost when y=1$y=1$ and cost0$cos{t}_0$ is the cost when y=0$y=0$. An intuitive explanation is below :

Decision boundary :

SVM will find a line that has the largest margin between the data. And the regularized term C$C$ is intuitively show below :

6.1.2 Concept of kernels

In this part, in order to fit Non-linear decision boundary, we will adapt the hypothesis function to

(1) Polynomial

It can fit dataset very well, but we don’t know which features to add and it is very computationally expensive.

(2) Gaussian Kernel
First, choose some landmarks l(i)( i=1,2,⋯)$l^{(i)}(i=1,2,\cdots )$

Second, define fi( i=1,2,⋯)$f_i(i=1,2,\cdots )$, such as Gaussian Kernel :

It mesures the similarity of two points :

• If x≈l(i):fi≈1$x\approx l^{(i)}:f_i\approx 1$,
• If x$x$ is far from l(i)$l^{(i)}$ : fi≈0$f_i\approx 0$.

And the σ$\sigma$ just like a scale of the distance of two points :

Finally, what it perdicet (for example) is :

6.1.3 SVM with kernels

(1) Choose landmarks

Given (x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))$(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots ,(x^{(m)},y^{(m)})$ ,and choose l(1)=x(1),l(2)=x(2),⋯,l(m)=x(m)$l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},\cdots ,l^{(m)}=x^{(m)}$ .

(2) Define kernels

We define f$f$ as Gaussian Kernel :

(3) Training

Use minimization algorirhm to solve it.

(4) Evaluation

• Large C$C$:Lower bias, higher variance.
• Small C$C$:Higher bias, lower variance.
• Large σ2${\sigma }^2$: Higher bias, lower variance. (f$f$ is more “smooth”)
• Small σ2${\sigma }^2$: Lower bias, higher variance.

(5) Note

• Perform feature scaling before using the Gaussian Kernel .
• Not all similarity functions make valid kernals. (Need to satisfy “Mercer Theorem” to make sure SVM packages run correctly)
• Other kernels : Polynomial kernel, String kernel, …
• Muti-class classification : one-vs-all method.
• If n≫m$n\gg m$, use logistic regression or SVM without kernel; if n$n$ is samll, m$m$ is intermediate, use SVM with kernel; if m≫n$m\gg n$, create more features, and turn to case one. Neural network likely to work well for most of these things.