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)$ 表示分类的正确性及确信度

• 当 $y(w \cdot x +b) > 0$ 时，表示分类正确
• 当 $y(w \cdot x +b) < 0$ 时，表示分类错误

定义： 超平面 $(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)$$

总结

支持向量机特点

• 训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。
• SVM 不太容易产生 overfitting
• SVM 训练出来的模型完全依赖于支持向量 (Support Vectors)
• 一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易被泛化。