# Margin

## Functional Margin

$\hat \gamma_i = y_i (w^T x_i + b)$

## Geometric Margin

$\gamma_i = y_i (\frac{w^T}{||w||} x_i + \frac{b}{||w||})$

When $|| w ||=1$, the two margins are the same.

# Linearly Separable

Goal: find a decision margin that maximizes the geometric margin.

# Lagarange Duality

## Dual Problem

primal problem和dual problem的联系如下

## Conclusion: Apply Dual to SVM

Given

Define Lagrangian to be $\mathcal{L}(w, b, \alpha) = \frac{1}{2} |w|^2 - \sum_{i=1}^{m} \alpha_i[y_i (w^T x_i + b) - 1]$.

# Kernel

feature map定义为 $\varphi$。 给定某个$\varphi$的时候，我们可以定义Kernel

Theorem (Mercer). Let $K: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ be given. Then for $K$ to be a valid (Mercer) kernel, it is necessary and sufficient that for any ${ x_1, …, x_m }, m < \inf$, the corresponding kernel matrix is symmetric positive semi-definite.

## Feature Space

A feature map is a map $\varphi : X \to F$, where F is a Hilbert space which we will call the feature space. Every feature map can naturally define a RKHS by means of the definition of a positive definite function.

## Reproducing Kernel Hilbert Space

Metric Space

Def: A metric space is a pair $(M,d)$ where M is a set, and $d:M^2 \to \mathbb{R}$ which s.t.

• $d(x,y) > 0$
• $d(x,y) = d(y,x)$
• $d(a,b) \le d(a,c) + d(c,b)$

## Some examples

• Bilinear Kernels: $K(x, y) = \langle x, y \rangle$,就是原始空间中的内积
• Polynomial Kernels: $K(x, y) = (\alpha \langle x, y \rangle + 1)^d$
• Radial basis function Kernels (RBF):
• Gaussian Kernel: $K(x,y) = \exp(-\frac{|| x-y ||}{2 \sigma^2})$
• Laplacian Kernel: $K(x,y) = \exp(-\frac{|| x-y ||}{\sigma^2})$