Margin

所有在decision boundary上的点都符合 $w^T x + b = 0$.

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.

根据前面定义,首先可以有

这个解法中,$|w|=1$限制了functional margin和geometric margin相等,所以可以认为geometric margin至少为$\gamma$。 因此解决这个问题就相当于找$(w,b)$,并且有最大的geometric margin(根据training set中的数据)。 但发现$|w|=1$会把这个问题变得复杂,因为non-convex。 所以将问题进行转换。

这里是说functional margin至少为$\hat \gamma$。 进一步进行转换。 我们引入scaling constraint:$(w,b)$的functional margin的必须为1。 因为对于functional margin,将$w$和$b$乘以一个系数,functional margin也会乘以相同的倍数,也就是scaling constraint。 由此,问题变成了

至此,这个问题变成了Quadratic Programming (QP) problem。

Lagarange Duality

这里插入讲一下拉格朗日乘子和对偶问题。

Primal Problem

任意问题都可以转换成如下形式

为了解决这个问题,我们定义generalized Lagrangian

而式子当中的$\alpha_i$和$\beta_i$就是Lagrange multipliers,拉格朗日乘子。 考虑这个数值

根据简单的推导,可以得到如下

因此,$\theta_P$可以取得任何符合primal constraints的$w$对应的数值。因此,如果我们考虑如下的最小化问题

这个问题就变得和我们一开始设定的primal problem一样。 我们不妨设$p^* = \min_w \theta_P(w)$为解。

Dual Problem

下面先考虑另外一个问题。

然后就可以展示dual problem

这和primal problem几乎一样,除了将min和max的顺序颠倒了一下。 我们定义dual problem的最优解为$d^* = \max_{\alpha, \beta} \min_w \mathcal{L}(w, \alpha, \beta)$。

primal problem和dual problem的联系如下

只有符合Karush-Kuhn-Tucker (KKT) condition的时候,中间的等号才会成立。 假设一定存在$w^, \alpha^, \beta^$,其中$w^$是primal的解,而$\alpha^, \beta^$是dual的解,并且$d^* = p^* = \mathcal{L}(w^, \alpha^, \beta^*)$。 并且还符合如下的KKT condition:

Conclusion: Apply Dual to SVM

总结一下在SVM的设定中,代入Lagarange Duality的解法。

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] $.

注意,$w^T x + b$中的$w,b$都是Lagarange定义中的$w$。 所以代入KKT的第一个条件,我们有

所以可以把$w=\sum_{i=1}^m \alpha_i y_i x_i$和$\sum_{i=1}^m \alpha_i y_i = 0$重新代回到Lagrangian,就有

Kernel

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

基于此,在包含m个data points的training set上,我们定义Kernel matrix

可以证明Kernel matrix是半正定对称矩阵。 由此引入Mercer定理。

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})$

Regularization and Non-separable Case