Week 7 notes: Support Vector Machines

2017-08-30

• notes
• machine learning

---

Introduction

No notes.

Large Margin Classification

Optimization Objective

Support Vector Machine

Learn complex non-linear function.

---

Figure 1. Relation between Logistic Regression and SVM Source: Coursera Machine Learning course

---

Large Margin Intuition

SVM Decision Boundary

Consider a case where we set constant C to be a very large value, when minimizing the optimization objective, we are going to be highly motivated to choose a value, so that the first term is equal to 0. So what would it take to make this first term equal to 0.

---

Figure 2. SVM optimization objective Source: Coursera Machine Learning course

---

When the first term is equal to 0, we need to minimize $\frac{1}{2}\sum_{i=1}^{n} \theta_{i} ^{2}$ (ignored θ₀).

Linear separable case

The obtained decision boundary when minimizing the optimization objective will have the margin as large as possible (hence the name Large Margin Intuition).

This means SVM will choose the black decision boundary instead of the pink and green one:

---

Figure 3. Large margin classifier Source: Coursera Machine Learning course

---

Mathematics Behind Large Margin Intuition

Vector Inner Product

$$u^{T}v = p\left \|u\right \|$$

p = length of projection of v onto u. p can be positive or negative.

---

Figure 4. Vector Inner Product Source: Coursera Machine Learning course

---

SVM Decision Boundary

We can rewrite the optimization objective of SVM as follow: $\min_{\theta}\frac{1}{2}\sum_{j=1}^{n}\theta_{j}^{2} = \frac{1}{2}\left \| \theta \right \|^{2}$

s.t.

$$p^{(i)}\left \| \theta \right \| \geq 1 ~~~ if ~~ y^{(i)}=1$$ $$p^{(i)}\left \| \theta \right \| \lt -1 ~~~ if ~~ y^{(i)}=0$$

where p⁽ⁱ⁾ is the projection of x^(u) onto the vector θ.

Simplification: θ₀ = 0.

According to the illustration below, with the minimal value of the magnitude of θ, the absolute value of p will large as much as possible (hence the large margin).

---

Figure 5. When the magnitude of θ is minimal, the margin is large Source: Coursera Machine Learning course

---

More intuitive illustration:

---

Figure 5. The margin line Source: Coursera Machine Learning course

---

Kernels

It’s a technique.

Kernels I

Kernels II

« Bài tập gom cụm sử dụng thuật toán K-Means Week 8 notes: Unsupervised Learning »