支持向量机 (SVM) 深入理解——机器学习经典分类算法

/ Machine Learning / 没有评论 / 383浏览

SVM 最早是由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出

目前的版本 (soft margin) 是由 Corinna Cortes 和 Vapnik 在 1993 年提出,并在 1995 年发表

在深度学习(2012)出现之前,SVM被认为机器学习中近十几年来最成功,表现最好的算法

线性可分支持向量机

考虑一个二分类问题,假设输入空间与特征空间为两个不同的空间。

这两个空间一一对应,并将输入空间中的输入,映射为特征空间中的特征向量。

假设给定一个特征空间上的训练集 T = { $(x_1, y_1),(x_2, y_2),...,(x_n, y_n)$ }

$x_i \in \mathcal{X} = R^n, \quad i = 1,2,...n$
$y_i \in \mathcal{Y} = {+1, -1}$,当 $x_i$ 为正例时, $y_i$ 为 +1,当 $x_i$ 为负例时,$y_i$ 为 -1

函数间隔

对于一个超平面

$$w^Tx +b = 0$$

$|w^Tx + b|$ 的大小能够相对地表示点 $x$ 距离超平面的远近。

为了去掉 $|w^Tx + b|$ 的绝对值符号,可在其前乘以 $y$,因为 $w^Tx + b$ 的符号与类标记 $y$ 的符号是否一致能够表示分类是否正确,即 $y(w \cdot x +b)$ 表示分类的正确性确信度

定义: 超平面 $(w^T, b)$ 关于样本点 $(x_{i}, y_{i})$ 的 函数间隔

$$\hat{\lambda_i} = y_i \cdot (w^T x_i + b)$$

超平面 $(w^T, b)$ 关于训练数据集 T 的函数间隔 为超平面 $(w^T, b)$ 关于 T 中的所有样本点 $(x_{i}, y_{i})$ 的 函数间隔 最小值

$$\hat{\lambda} = \min_{i = 1,2,...,N} \hat{\lambda_i}$$

函数间隔可以表示分类预测的正确性确信度
一个点距离分离超平面的远近可以表示分类预测的确信程度

几何间隔

函数间隔存在的问题:当我们成比例地改变 $w^T$,$b$, 超平面并没改变, 但函数间隔却成为了原来的2倍。

解决函数间隔的问题:对分离超平面的法向量 $w$ 加约束 $\parallel w \parallel$ = 1。这就是几何间隔的思想。

对于一个超平面 $w^Tx +b = 0$,点 $(x,y)$ 到超平面 $(w^T, b)$ 的距离为

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

$\parallel w \parallel$ 为 $w$ 的 $L_2$ 范数

当样本点 $(x_{i}, y_{i})$ 被超平面正确分类时,点 $(x,y)$ 到超平面 $(w^T, b)$ 的距离为

$$d = \frac{y \cdot (w^Tx + b)}{\parallel w \parallel}$$

硬间隔最大化

目标函数

$$\underset{w^T,b}{\mathrm{\arg \max}} \left \{ \frac{\min \limits_{i} \left [ y_i \cdot (w^Tx + b) \right ]}{\parallel w \parallel} \right \}$$

令 $\min \limits_{i} \left [ y_i \cdot (w^Tx + b) \right ] = \gamma, \qquad \gamma > 0$

函数间隔 $\gamma$ 的取值并不影响最优化问题。事实上,将 $w$ 和 $b$ 按比例改为 $\lambda w$ 和 $\lambda b$,这时函数间隔变为 $\lambda \gamma$。 它产生了一个等价的最有化问题,既然这样,可令 $\gamma = 1$

那么间隔最大化可表示为

$$\underset{w^T,b}{\mathrm{\arg \max}} \frac{1}{\parallel w \parallel} $$

对于机器学习的问题,要求解的都是凸函数,要求凸函数的极大值非常难求,但求极小值非常简单

$$\underset{w^T,b}{\mathrm{\arg \max}} \frac{1}{\parallel w \parallel} \Rightarrow \underset{w^T,b}{\mathrm{\arg \min}} \parallel w \parallel \Rightarrow \underset{w^T,b}{\mathrm{\arg \min}} \parallel w \parallel ^2 \Rightarrow \underset{w^T,b}{\mathrm{\arg \min}} \frac{1}{2} \parallel w \parallel ^2$$

于是,目标函数是在 $y_i \cdot (w^Tx + b) \ge 1$ 的条件下,求 $\underset{w^T,b}{\mathrm{\arg \min}} \frac{1}{2} \parallel w \parallel ^2$

拉格朗日乘子法

标准格式

$$ \left \{\begin{matrix} min &\qquad f(x) \\ s.t. &\qquad g_i(x) \le 0 \end{matrix}\right. $$

于是

$$L(w^T, b, \alpha) = \frac{1}{2} \parallel w \parallel ^2 + \sum_{i=1}^{n} \alpha_i \cdot \left [1 - y_i(w^Tx_i + b) \right ] \tag{1}$$

对偶问题

$$\min_{w^T,b} \max_\alpha L(w^T, b, \alpha) \to \max_\alpha \min_{w^T,b}L(w^T, b, \alpha)$$

最大值里面的最小值 > 最小值里面的最大值

推导过程

$$\frac{\partial L}{\partial w} = w - \sum_{i = 1}^{n} \alpha_iy_ix_i = 0 \Longrightarrow w = \sum_{i = 1}^{n} \alpha_iy_ix_i$$

$$\frac{\partial L}{\partial b} = \sum_{i=0}^{n}\alpha_iy_i = 0$$

带入(1)式

$$ \begin{aligned} L(w, b, \alpha) &= \frac{1}{2}w^Tw + \sum_{i=1}^{n}\alpha_i - w^T\sum_{i=1}^{n}\alpha_iy_ix_i - b\sum_{i=1}^{n}\alpha_iy_i \\ &=\frac{1}{2} (\sum_{i = 1}^{n} \alpha_iy_ix_i)^T(\sum_{i = 1}^{n} \alpha_iy_ix_i) + \sum_{i=1}^{n}\alpha_i - (\sum_{i = 1}^{n} \alpha_iy_ix_i)^T(\sum_{i=1}^{n}\alpha_iy_ix_i) - b\sum_{i=1}^{n}\alpha_iy_i \\ &=\sum_{i=1}^{n}\alpha_i -\frac{1}{2} (\sum_{i = 1}^{n} \alpha_iy_ix_i)^T(\sum_{i = 1}^{n} \alpha_iy_ix_i) \\ &=\sum_{i=1}^{n}\alpha_i -\frac{1}{2} \sum_{i = 1, j =1}^{n} \alpha_i\alpha_jy_iy_jx_i^Tx_j \end{aligned} $$

所以

$$\min_{w,b} L(w,b,\alpha) = \sum_{i=1}^{n}\alpha_i -\frac{1}{2} \sum_{i = 1, j =1}^{n} \alpha_i\alpha_jy_iy_jx_i^Tx_j$$

然后上式对 $\alpha$ 求最大值

$$L(\alpha) = \sum_{i=1}^{n}\alpha_i -\frac{1}{2} \sum_{i = 1, j =1}^{n} \alpha_i\alpha_jy_iy_jx_i^Tx_j$$

条件

$$ \left \{\begin{matrix} \sum_{i=1}^{n}\alpha_iy_i &= 0 \\ \alpha_i &\ge 0 \end{matrix}\right. $$

求最大值比较困难,可以转化为求相反数的最小值, 即

$$L^{'}(\alpha) = \frac{1}{2} \sum_{i = 1, j =1}^{n} \alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{n}\alpha_i$$

求导后可以得到 $\alpha$ 的值,进而可得到 $w$、$b$ 的值,从而求得超平面。

软间隔最大化

松弛因子

通常情况下,训练数据中有一些离群点。线性不可分意味着某些样本点不能满足函数间隔 $\ge$ 1。

为了解决这个问题,可以对每个样本点引入一个松弛变量 $\xi_i \ge 0$,使函数间隔加上松弛变量 $\ge$ 1, 即

$$y_i(w^Tx_i + b) \ge 1 - \xi_i$$

目标函数

$$\underset{w^T,b}{\mathrm{\arg \min}} \frac{1}{2} \parallel w \parallel^2 + C \sum_{i=1}^{n}\xi_i$$

$C \rightarrow \infty$ 时,严格不能容忍错误
$C \rightarrow 0$ 时, 可以容忍更大的错误

条件:

$$ \left \{\begin{matrix} \sum_{i=1}^{n}\alpha_iy_i &= 0 \\ \alpha_i &\ge 0 \\ \mu_i &\ge 0 \\ C - \alpha_i - \mu_i &= 0 \\ \alpha_i &\le C \end{matrix}\right. $$

拉格朗日乘子

$$L(w,b,\xi,\alpha,\mu) = \frac{1}{2} \parallel w \parallel^2 + + C \sum_{i=1}^{n}\xi_i + \sum_{i=1}^{n}\alpha_i \left [ 1 - \xi_i - y_i(w^Tx_i + b)\right ] + \sum_{i=1}^{n}\mu_i(0 - \xi_i)$$

对 $w, b, \xi$ 求偏导后可以得到

$$w = \sum_{i=1}^{n} \alpha_iy_ix_i$$

$$\sum_{i=1}^{n}\alpha_iy_i = 0$$

$$C - \alpha_i - \mu_i = 0$$

带入原式得

$$L(\alpha) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j$$

同样求 $L(\alpha)$ 相反数的最小值

$$L^{'}(\alpha) = \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{n}\alpha_i$$

条件:

$$ \left \{\begin{matrix} \sum_{i=1}^{n}\alpha_iy_i &= 0 \\ \alpha_i &\ge 0 \\ \alpha_i &\le C \end{matrix}\right. $$

核函数

数据集在空间中对应的向量往往不可被一个超平面区分开,对于低纬不可分的问题,可将其转化到高维上.

两个步骤来解决:

线性 SVM 中转化为最优化问题时求解的公式计算都是以内积 (dot product) 的形式出现的 $\Phi(x_i)\Phi(x_j)$

其中 $\Phi(x)$ 是把训练集中的向量点转化到高维的非线性映射函数

因为内积的算法复杂度非常大,所以我们利用核函数来取代计算非线性映射函数的内积,即

$$K(X_i, X_j) = \Phi(x_i)\Phi(x_j)$$

核函数原理

已知两个向量

$$x = (x_1, x_2, x_3),\quad y = (y_1, y_2, y_3)$$

定义方程:

$$f(x) = (x_1x_1, x_1x_2, x_1x_3, x_2x_1, x_2x_2, x_2x_3, x_3x_1, x_3x_2, x_3x_3)$$

$$K(x, y ) = (x \cdot y)^2$$

举个例子,假设x = (1, 2, 3), y = (4, 5, 6),则

$f(x) = (1, 2, 3, 2, 4, 6, 3, 6, 9)$

$f(y) = (16, 20, 24, 20, 25, 36, 24, 30, 36)$

$f(x) \cdot f(y) = 16 + 40 + 72 + 40 + 100+ 180 + 72 + 180 + 324 = 1024$

$K(x, y) = (4 + 10 + 18 ) ^2 = 32^2 = 1024$

同样的结果,使用kernel方法计算容易很多

H 度多项式核函数

polynomial kernel of degree h

$$K(X_i, X_j) = (X_i \cdot X_j + 1)^h$$

高斯径向基核函数

Gaussian radial basis function kernel

$$K(X_i,X_j) = exp \left [ -\frac{\parallel X_i - X_j \parallel^2}{2\delta^2} \right ]$$

S 型核函数

Sigmoid function kernel

$$K(X_i,X_j) = tanh(kX_i \cdot X_j - \delta)$$

总结

支持向量机特点