SVM的简单推导

2019-04-03 本文已影响202人 super_zhang

线性判别函数

给定若干n维度空间的样本点 $x^{(1)},\cdots,x^{(m)}$ ，我们希望使用超平面将不同类别的点划分开来。如下图，考虑两类的情况，我们需要一个超平面将两类数据划分开，其由 $g(x)$ 确定，称 $g(x)$ 为线性判别函数。

划分超平面

$g(x)$ 的表达式如下
$g(x)=w^Tx+b$

间隔最大化

几何间隔是指某个样本 $x^{(i)}$ 到分类界面 $g(x)=0$ 的距离
$\gamma_i=\frac{|w^Tx^{(i)}+b|}{\|w\|}.$
定义样本集与分类界面之间的几何间隔为，样本集中所有样本与分类界面之间几何间隔的最小值。

而SVM的目标是找到一个可以正确划分样本点，且与样本集几何间隔最大的超平面。如下图，称距离最优分类界面最近的这些训练样本为支持向量（support vector）。

支持向量

可以看出，最优分类界面完全由支持向量决定。设支持向量 $X_s$ ，那么可以直接通过最大化间隔，求得 $w$ 和 $b$ 。
$\max_{w,b,x\in X_s} \frac{|w^Tx+b|}{\|w\|}$
但是支持向量正是通过最优分类界面得到的，所以这样通过支持向量求最优分界面的方法时行不通的。

目标函数

记样本 $x^{(i)}$ 的类别标记为 $y^{(i)}$ ，那么 $y^{(i)}\cdot g(x^{(i)})>0$ 意味着分类界面正确划分了样本 $x^{(i)}$ 。不妨通过 $y^{(i)}\cdot g(x^{(i)})\geq 1$ 表示样本 $x^{(i)}$ 离分类界面保持一定的距离，这个距离等于
$\gamma_i = \frac{|w^Tx^{(i)}+b|}{\|w\|} \geq \frac{1}{\|w\|}.$
这时，最大化几何间隔，等价于
$\min_{w,b} \frac{1}{2}\|w\|^2.$
按照这个思路，我们可以定义如下目标函数
$\begin{align} &\min_{w,b} \frac{1}{2}\|w\|^2,\\ &{\rm s.t.}\ \ \ \ y^{(i)}\cdot \left(w^Tx^{(i)}+b\right)\geq 1, i=1,2,\cdots,m. \end{align}$

Kuhn-Tucker构造法

上面的目标函数是一个有约束最优化问题，我们首先需要将其转化为一个无约束最优问题。

使用拉格朗日乘子法，可以得到相应的拉格朗日函数
$L(w,b,\alpha)=\frac{1}{2}\|w\|^2+\sum_{i=1}^m\alpha_i\left(1-y^{(i)}\cdot\left(w^Tx^{(i)}-b\right)\right), \alpha_i\geq 0.$
分别对参数 $w,b$ 求偏导：
$\begin{align} &\frac{\partial L(w,b,\alpha)}{\partial w}=w-\sum_{i=1}^m \alpha _iy^{(i)} x^{(i)},\\ &\frac{\partial L(w,b,\alpha)}{\partial b}=\sum_{i=1}^m \alpha_i y^{(i)}. \end{align}$
令偏导为零，得
$\begin{align} &w=\sum_{i=1}^m \alpha_iy^{(i)}x^{(i)},\\ &\sum_{i=1}^m \alpha_i y^{(i)}=0. \end{align}$
将上面第一个式子带入到拉格朗日函数中得
$L(\alpha)=\sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_i y^{(i)} y^{(j)}{x^{(i)}}^Tx^{(j)}.$
因此原问题的对偶问题是
$\begin{align} \max_\alpha\ &L(\alpha)\\ {\rm s.t.}\ \ &\sum_{i=1}^m \alpha_i y^{(i)}=0,\\ &\alpha_i\geq 0,i=1,2,\cdots,m. \end{align}$
这是一个二次规划问题。但是该问题的计算规模正比于训练样本数，这会在实际任务中造成很大的开销。为了解决这个问题，人们提出了许多高效的算法，具有代表性的是SMO。这里不进行介绍。

假设通过解对偶问题得到了 $\alpha_i$ ，那么可通过下式得到权向量 $w$
$w=\sum_{i=1}^m \alpha_iy^{(i)}x^{(i)}.$
而对于支持向量中的样本 $x_s$ ，有
$y_s\cdot (w^Tx_s+b)=1$
那么那些样本点是支持向量呢？那些满足 $\alpha_i>0$ 的样本 $x^{(i)}$ 。这里不进行具体的推导。

松弛变量

当训练样本是线性不可分时，目标函数是无解的。这时，可以通过引入松弛变量，对某些对样本妥协，也就是允许某些样本被分错。

具体来说，改写目标函数
$\begin{align} \min_{w,b,\xi_i}\ &\frac{1}{2}\|w\|^2+C\sum_{i=1}^m \xi_i,\\ {\rm s.t.}\ \ &y^{(i)}\cdot \left(w^Tx^{(i)}+b\right)\geq 1-\xi_i,\\ & \xi_i\geq 0, i=1,2,\cdots,m. \end{align}$
其中， $C(C>0)$ 为惩罚参数，需要人工设置。C值越大对误分类的惩罚越大。

对上述目标函数使用拉格朗日乘子法得到
$\begin{align} L(w,b,\alpha,\xi,\mu)=&\frac{1}{2}\|w\|^2+C\sum_{i=1}^m\xi_i\\ & +\sum_{i=1}^m\alpha_i\left(1-\xi_i -y^{(i)}(w^Tx^{(i)}+b) \right)-\sum_{i=1} ^m\mu_i\xi_i, \end{align}$
其中， $\alpha_i\geq 0,\mu_i\geq 0$ 是拉格朗日乘子。令 $L(w,b,\alpha,\xi,\mu)$ 对 $w,b,\xi_i$ 的偏导为零，并代入到拉格朗日函数中可得原问题的对偶问题
$\begin{align} \max_\alpha\ & \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}{x^{(i)}}^Tx^{(i)}\\ {\rm s.t.}\ \ & \sum_{i=1}^m\alpha_iy^{(i)}=0,\\ & 0\leq \alpha_i\leq C, i=1,2,\cdots,m. \end{align}$

核函数

核函数的思想类似于神经网络中的激活函数。

有时，通过函数 $\phi(\cdot)$ 将样本从原始空间映射到一个更高维的特征空间，SVM可以找到更加合适的划分超平面。比如
$\Phi:(x_1,x_2)^T\rightarrow (x_1^2,\sqrt 2x_1x_2,x_2^2)^T.$
这时候划分判别函数变为
$g(x)=w^T\phi(x)+b.$
定义核函数为
${\cal K}(x^{(i)},x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)}).$
在SVM求解的过程中，使用 ${\cal K}(x^{(i)},x^{(j)})$ 替代 $\phi(x^{(i)})^T\phi(x^{(j)})$ ，可大大减少计算量。常用核函数有，高斯核、多项式核、Sigmoid核等。

题外话

SVM作为机器学习中一个著名的算法，还有许多变体，如半监督SVM、单类SVM等。

单类SVM: SVDD