SVM, Kernel, and Reproducing Kernel Hilbert Space
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.
根据前面定义，首先可以有
\[\begin{aligned} \max & & \gamma \\ s.t. & & y_i (w^T x_i + b) \ge \gamma, & & i=1,...,m\\ & & \|w\| = 1 \end{aligned}\]这个解法中，$|w|=1$限制了functional margin和geometric margin相等，所以可以认为geometric margin至少为$\gamma$。 因此解决这个问题就相当于找$(w,b)$，并且有最大的geometric margin（根据training set中的数据）。 但发现$|w|=1$会把这个问题变得复杂，因为non-convex。 所以将问题进行转换。
\[\begin{aligned} \max & & \frac{\hat \gamma}{\|w\|} \\ s.t. & & y_i (w^T x_i + b) \ge \hat \gamma, & & i=1,...,m \end{aligned}\]这里是说functional margin至少为$\hat \gamma$。 进一步进行转换。 我们引入scaling constraint：$(w,b)$的functional margin的必须为1。 因为对于functional margin，将$w$和$b$乘以一个系数，functional margin也会乘以相同的倍数，也就是scaling constraint。 由此，问题变成了
\[\begin{aligned} \min & & \frac{\|w\|}{2} \\ s.t. & & y_i (w^T x_i + b) \ge 1, & & i=1,...,m \end{aligned}\]至此，这个问题变成了Quadratic Programming (QP) problem。
Lagarange Duality
这里插入讲一下拉格朗日乘子和对偶问题。
Primal Problem
任意问题都可以转换成如下形式
\[\begin{aligned} \min_w & & f(w)\\ s.t. & & g_i(w) \le 0, & & i=1,...,k\\ & & h_i(w) = 0 & & i=1,...,l \end{aligned}\]为了解决这个问题，我们定义generalized Lagrangian \(\mathcal{L}(w, \alpha, \beta) = f(w) + \sum_{i=1}^k \alpha_i g_i(w) + \sum_{i=1}^l \beta_i h_i(w)\)
而式子当中的$\alpha_i$和$\beta_i$就是Lagrange multipliers，拉格朗日乘子。 考虑这个数值 \(\theta_P (w) = max_{\alpha, \beta} \mathcal{L}(w, \alpha, \beta)\)
根据简单的推导，可以得到如下
\[\begin{eqnarray} \theta_P(w) = \begin{cases} f(w), & \text{if $w$ s.t. primal constraints}\\ \inf, & \text{otherwise} \end{cases} \end{eqnarray}\]因此，$\theta_P$可以取得任何符合primal constraints的$w$对应的数值。因此，如果我们考虑如下的最小化问题
\[\min_w \theta_P(w) = \min_w \max_{\alpha, \beta} \mathcal{L}(w, \alpha, \beta)\]这个问题就变得和我们一开始设定的primal problem一样。 我们不妨设$p^* = \min_w \theta_P(w)$为解。
Dual Problem
下面先考虑另外一个问题。
\[\theta_D(\alpha, \beta) = min_w \mathcal{L}(w, \alpha, \beta)\]然后就可以展示dual problem
\[max_{\alpha, \beta} \theta_D(\alpha, \beta) = \max_{\alpha, \beta} \min_w \mathcal{L}(w, \alpha, \beta)\]这和primal problem几乎一样，除了将min和max的顺序颠倒了一下。 我们定义dual problem的最优解为$d^* = \max_{\alpha, \beta} \min_w \mathcal{L}(w, \alpha, \beta)$。
primal problem和dual problem的联系如下
\[d^* = \max_{\alpha, \beta} \min_w \mathcal{L}(w, \alpha, \beta) \le \min_w \max_{\alpha, \beta} \mathcal{L}(w, \alpha, \beta) = p^*\]只有符合Karush-Kuhn-Tucker (KKT) condition的时候，中间的等号才会成立。 假设一定存在$w^, \alpha^, \beta^$，其中$w^$是primal的解，而$\alpha^, \beta^$是dual的解，并且$d^* = p^* = \mathcal{L}(w^, \alpha^, \beta^*)$。 并且还符合如下的KKT condition:
\[\begin{aligned} \frac{\partial}{\partial w_i} \mathcal{L} (w^*, \alpha^*, \beta^*) = 0, && i=1,...,n\\ \frac{\partial}{\partial \beta_i} \mathcal{L} (w^*, \alpha^*, \beta^*) = 0, && i=1,...,l\\ \alpha_i^* g_i(w^*) = 0, && i=1,...,k\\ g_i(w^*) = 0, && i=1,...,k\\ \alpha_i^* = 0, && i=1,...,k \end{aligned}\]Conclusion: Apply Dual to SVM
总结一下在SVM的设定中，代入Lagarange Duality的解法。
Given
\[\begin{aligned} \min_w && \frac{1}{2} \|w\|^2 \\ s.t.&& 1 - y_i (w^T x_i + b) \le 0 && i=1,...,m \end{aligned}\]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的第一个条件，我们有
\[\begin{aligned} \frac{\partial}{\partial w} \mathcal{L} (w,b,\alpha) & = w - \sum_{i=1}^m \alpha_i y_i x_i = 0\\ \frac{\partial}{\partial b} \mathcal{L} (w,b,\alpha) & = \sum_{i=1}^m \alpha_i y_i = 0 \end{aligned}\]所以可以把$w=\sum_{i=1}^m \alpha_i y_i x_i$和$\sum_{i=1}^m \alpha_i y_i = 0$重新代回到Lagrangian，就有
\[\mathcal{L}(w,b,\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \langle x_i, x_j \rangle\]Kernel
feature map定义为 $\varphi$。 给定某个$\varphi$的时候，我们可以定义Kernel
\[K(x,z) = \varphi(x)^T \varphi(z)\]基于此，在包含m个data points的training set上，我们定义Kernel matrix
\[K_{ij} = K(x_i, x_j)\]可以证明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})$