SVM入门笔记

2019-03-20 本文已影响0人 zealscott

本文不是一篇正式的tutorial，只是帮助回忆和理解SVM推导的笔记。此文章会长期更新。

分类问题

SVM（support vector machine）是一种著名的分类算法。我们学过Logistic回归，但它只能处理简单的线性分类。在现实生活中，很多问题的属性不能简单的用线性分类完成，或者说线性分类的效果不好，这时候我们就要想其他办法。

超平面

我们可以想象这样一个方程：

$w^Tx + b = 0$

若这里的 $x$ 是二维向量，那么就是我们熟悉的平面方程。若大于二维，则是一个超平面，在SVM中，这个超平面也被称为决策面。

我们的目标就是想找到这样一个决策面，使得样本点能够较好的分布在超平面两侧，这就达到了我们分类的目的。

分类间隔

很显然，对于样本点来说，这样的决策面肯定不止一个。那么，如何来度量我们分类好坏的标准呢？

在SVM中，我们使用分类间隔来度量，所谓分类间隔，是指保证决策面方向不变且不会错分样本的情况下移动决策面，会在原来的决策面两侧找到两个极限位置（越过则会产生错分现象）。因此，这两条平行线（面）之间的垂直距离就是这个决策面对应的分类间隔。

不同方向的最优决策面通常是不同的，那个具有最大间隔的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为支持向量。

根据我们学习过的平面距离可以得到：

$d = \frac {|w^T + b|}{||w||}$

我们首先考虑一个决策面是否能够将所有样本都正确分类的约束。我们可以为每个样本点 $x_i$ 加上一个类别标签 $y_i = \{-1,1\}$ ，假如我们的决策面方程能够完全正确的对所有样本点进行分类，则可以得到：

$f(x)=\left\{\begin{aligned}w^Tx_i + b >0 \space for \space y_i = 1 \\w^Tx_i + b <0 \space for \space y_i = -1\end{aligned}\right.$

如果我们要求再高一点，假设决策面正好处于间隔区域的中轴线上，并且相应的支持向量对应的样本点到决策面的距离为d，那么公式可以进一步写成：

$f(x)=\left\{\begin{aligned}(w^Tx_i + b )/||w||\ge d \space \forall y_i = 1 \\ (w^Tx_i + b )/||w||\le -d \space \forall y_i = -1\end{aligned}\right.$

对公式重写（两边同时除以d）：

$f(x)=\left\{\begin{aligned}w_d^Tx_i + b_d >1 \space for \space y_i = 1 \\w_d^Tx_i + b_d <1 \space for \space y_i = -1\end{aligned}\right. \quad w_d = \frac{w}{||w||d},b_d = \frac {b}{||w||d}$

由于 $w_d$ 与 $w$ 并没有本质差别，因此不再做区分，我们的目标是想要在正确分类的情况下使得分类间隔最大化，即 $max \{d\}$ ，也等价于 $min \{ \frac {1}{2} ||w||^2\}$ 。

因此，我们得到我们问题的总描述：

$\min \frac {1}{2} ||w||^2$

$s.t. \quad y_i(w^Tx_i +b)\ge1,i=1,...,n$

margins

Functional margins
- $\gamma^{(i)} = y^{(i)}(w^Tx + b)$
- 这个函数可以用来衡量confident和correct
- 如果分类正确，那么该函数始终是正数，且离决策边界越远，值越大，也就越confident
- 如果分类错误，那么该函数是负数
- 因此，我们的目标是找到最小的margin，也就是 $\gamma = \min \gamma^{(i)}$
Geometric margins
- Functional margins有一个很大的问题在于，如果我等比例的scale $w,b$ ，那么该值就一定会增大。但此时对于margin来说并没有提升，因此无法直接用来衡量。
- 我们新定义一个Geometric margins，可以认为是一个相对的大小：
  - $\gamma^{(i)} = y^{(i)}(\frac{w}{||w||}^Tx + \frac{b}{||w||})$
- 我们的目标不变:
  - $\gamma = \min \gamma^{(i)}$
- 很容易证明，这时候无论 $w,b$ 如何 scale，都不会影响margins了。（类似于normalization）

Optimal margin classifier

我们的目标是最大化margins，因此可以将原问题写为：

$\max \frac{\gamma}{||w||}$

$s.t. y^{(i)}(w^Tx^{(i)} + b) \ge \gamma$

但这依然不容易求解，联想到，我们已经使得无论 $w,b$ 如何 scale，都不会影响最终的值，因此，总是可以使 $w,b$ 满足 $\gamma = 1$ ，因此，我们的目标函数可以写为 $\max \frac{1}{||w||}$ 。注意到，最大化 $\frac{1}{||w||}$ 和最小化 $||w||^2$ 是一回事情（更容易求导），因此，我们将原问题转为了凸优化问题：

$\min \frac {1}{2} ||w||^2$

$s.t. \quad y_i(w^Tx_i +b)\ge1,i=1,...,n$

线性可分情况

拉格朗日函数

这是一个有约束条件的极值问题，因此可使用拉格朗日函数表达：

$L(w,b,a) =\frac {1}{2} ||w||^2 - \sum\limits _{i=1}^n \alpha_i(y_i(w^Tx_i +b)-1)$

我们令 $\alpha_i \ge 0，\theta(w) = {max}_{a_i \ge 0} L(w,b,a)$ 。容易验证：当某个约束条件不满足时，例如 $y_i(w^Tx_i +b)<1$ ，则有 $\theta(w) = \infty$ （只要令 $\alpha _i = \infty$ 而当所有约束都满足时，则有 $\theta(w) = \frac {1}{2} ||w||^2$ ，即为最初要最小化的量。

这样，我们就使用拉格朗日函数将所有约束条件集中到一个函数中，目标函数变成了：

$\min\limits_{w,b}\theta(w) = \min\limits_{w,b} \max\limits_{\alpha_i\ge 0}L(w,b,a) = p^*$

这里用 $p^*$ 表示这个问题的最优解，且与最初的问题是等价的，但如果直接面对这个函数，有 $w,b$ 两个参数，并且 $\alpha$ 还是不等式约束，不好求解。那么我们可以转化为对偶问题：

$\max\limits_{\alpha_i\ge 0}\min\limits_{w,b} L(w,b,a) = d^*$

这个新问题的最优解表示为 $d^\star$ ，且有 $d^{\star} \le p^{\star}$ ,在某些情况下这两者相等，因此可以求解对偶问题来间接求解原始问题。

KKT条件

由于对偶问题和原始问题有 $d^{\star} \le p^{\star}$ 的关系，但我们更希望取等号，这样我们就可以利用对偶问题来求得原问题的最优解。

而满足这种条件的约束称为KKT条件。

首先重新定义一下凸优化问题：

$\min f(w)$

$s.t. \quad g_i(w) \le 0$

$h_i(w) = 0$

拉格朗日函数可以表示为： $L(w,\alpha,\beta) = f(w) + \sum \alpha_i g_i(w) + \sum \beta_i h(w)$

KKT条件可以表示为：

$\frac{\partial}{\partial w_i}L(w^*,\alpha^*,\beta^*) = 0$

$\frac{\partial}{\partial \beta_i}L(w^*,\alpha^*,\beta^*) = 0$

$\alpha_i^* g_i^*(w^*) = 0$

$g_i(w^*) \le 0$

$\alpha^* \ge 0$

其中第三个条件被称为dual complementarity condition，也就是说，只有在 $g_i^{\star}(w^{\star}) = 0$ 时 $\alpha \ne 0$ ，也就是真正作为support vector，在后面的SMO中会有帮助。

对偶问题求解

我们需要求解的方程为：

$\max\limits_{\alpha_i\ge 0}\min\limits_{w,b} L(w,b,a) = d^*$

首先固定 $\alpha$ ，对 $w,b$ 求导数：

$\frac{\partial L }{\partial w} = 0 \Rightarrow w =\sum\limits_{i=1}^{n}a_iy_ix_i$

$\frac{\partial L }{\partial wb} = 0 \Rightarrow\sum\limits_{i=1}^{n}a_iy_i = 0$

将上面的结果带到 $L(w,b,a)$ 中可得：

$\begin{equation}\begin{split} L(w,b,a)&=\frac {1}{2} ||w||^2 - \sum\limits _{i=1}^n \alpha_i(y_i(w^Tx_i +b)-1) \\& =\frac {1}{2} ||w||^2 - \sum\limits_{i=1}^n a_iy_iw^Tx_i - \sum\limits_{i=1}^n a_iy_ib + \sum\limits_{i=1}^n a_i \\& =-\frac {1}{2} \sum\limits_{i,j = 1}^n a_ia_jy_iy_jx^T_ix_j + \sum\limits _{i= 1}^n a_i \end{split}\end{equation}$

这样，我们的目标函数就变为：

$\max\limits_{\alpha} \sum\limits _{i= 1}^n a_i-\frac {1}{2} \sum\limits_{i,j = 1}^n a_ia_jy_iy_jx^T_ix_j$

$s.t. \quad a_i\ge0,i=1,..., and \sum\limits_{i=1}^{n}a_iy_i = 0$

这样，我们的目标就变成了求 $\alpha$ ，从而可以求出：

$w =\sum\limits_{i=1}^{n}a_iy_ix_i$

$b = - \frac {\max _{i:y_i = -1} w^Tx + \min_{i:y_i = 1}w^Tx _i}{2}$

求 $\alpha$ 比直接求 $w,b$ 简单多了，其中SMO算法是目前最常用的，我们之后再说。

我们目前的分类函数为 $f(x) = w^Tx+b$ ，带入：

$\begin{equation}\begin{split} f(x) &= (\sum \alpha_iy_ix_i)^Tx +b \\& = \sum \alpha _iy_i(x_ix) +b \end{split}\end{equation}$

注意，这里的 $(x_ix)$ 表示向量乘积，因此，对于新点 $x$ ，只需要计算它与训练数据点的内积即可。这一点在之后的kernel函数中也会使用。

线性不可分情况

核函数

将attributes -> feature 的过程定义为feature mapping，例如，因此，我们想从feature中进行学习，而不是原始的attributes。而注意到，我们对样本的预测只与内积有关，因此可以定义Kernel：
- 这样，在原始算法中的所有内积都用Kernel代替，这样就实现了从feature中学习
这里最值得注意的是，为什么我们不直接学习feature的表示，而要学习kernel呢？
- 因为kernel的计算代价可能远远小于提取feature
- 例如，如果 $K(x,z) = (x^Tz +c)^d$ ，则对应于 $C_{n+d}^n$ 个feature space，而对于计算kernel来说，复杂度只有 $O(n)$
- 这种kernel的思想并不仅仅适用于SVM，只要有内积的形式，都可以使用，可以大大减少feature空间的维度
直觉来说，如果 $\phi(x)$ 和 $\phi(z)$ 越相近，则我们希望得到的 $K(x,z)$ 越大，反之越小
例如Gaussian kernel：
- correspond to an infinite dimensional feature mapping

正则化&不可分

当我们用 $\phi$ 将数据映射到高维特征空间，并不能提高线性可分的likelihood。同时，如果样本中存在outlier，会大大影响我们分类的效果和margin的大小。
因此，我们希望模型能够对outlier不敏感，加上正则项(正则化）：
- $\min_{\gamma,w,b} \frac{1}{2}||w||^2 + C\sum\limits_{i=1}^m\varepsilon_i$
- $s.t\quad y^{(i)}(w^Tx^{(i)} + b) \ge 1- \varepsilon_i$
- $\varepsilon_i \ge 0$
这样，我们的拉格朗日问题就变为：
- $L(w,b,\varepsilon,\alpha,r) = \frac{1}{2} w^Tw + C\sum\limits_{i=1}^m\varepsilon _i - \sum\limits_{i=1}^m\alpha_i[y^{(i)}(x^Tw + b - 1 +\varepsilon_i)] - \sum\limits_{i=1}^m r_i \varepsilon_i$
通过同样的方法，可以得到拉格朗日对偶问题为：
- $\max\limits_{\alpha} \sum\limits _{i= 1}^n a_i-\frac {1}{2} \sum\limits_{i,j = 1}^n a_ia_jy_iy_j(x^{(i)}_i,x^{(j)})$
- $s.t. \quad 0\le \alpha \le C$
- $\sum\limits_{i=1}^m \alpha_i y^{(i)} = 0$
根据KKT条件，我们可以得到
- $\alpha_i = 0 \quad \Rightarrow\quad y^{(i)}(w^Tx^{(i)} + b) \ge 1$
- $\alpha_i = C \quad \Rightarrow\quad y^{(i)}(w^Tx^{(i)} + b) \le 1$
- $0<\alpha_i < C \quad \Rightarrow\quad y^{(i)}(w^Tx^{(i)} + b) = 1$