支持向量机

SVM（Support Vector Machine，支持向量机）是一种二类分类模型，目标是在特征空间上找到间隔最大化的超平面。

# 线性可分 SVM

# 线性可分与超平面

考虑一个二维平面，平面上有两种不同的数据（红点和蓝点）。如果可以用一条直线将这两类数据分开，那么称这些数据是线性可分的，这条直线就相当于一个超平面（Hyperplane）。

扩展到 $n$ 维空间后，给定一个二分类器数据集 $D = \{ (x_i, y_i) \}_{i=1}^n$，其中 $y_i \in \{ +1, -1 \}$，如果存在一个超平面 $w^T x + b = 0$ 将两类样本分开，且对于每个样本都有 $y_i (w^T x_i + b) > 0$，则称这两类样本是线性可分的。

# 最大间隔与支持向量

接下来的问题是如何确定这个超平面。从直观上而言，这个超平面应该以最大间隔把两类样本分开，因此我们需要寻找最大间隔超平面。

# 支持向量

我们定义 $\gamma$ 为所有样本到超平面的最短距离。如果 $\gamma$ 越大，则超平面对两个数据集的划分越稳定，不容易受噪声等因素影响。SVM 的目标是寻找一个超平面使得 $\gamma$ 最大，即下图中的实线。

这些离超平面最近的点（虚线上的点）被称为支持向量（support vector），可以看到实际上 SVM 的解只受支持向量的影响，与数据集中的其他点无关。

两条虚线之间的区域被称为间隔（margin），距离为 $2 \gamma$。

# 几何间隔

初中几何告诉我们，二维空间中的一点 $(m, n)$ 到直线 $Ax + By + C = 0$ 的距离公式是：

$$\frac{| Am + Bn + C |}{\sqrt{A^2 + B^2}}$$

扩展到 n 维空间后，样本 $x_i$ 到直线 $w^T x + b = 0$ 的距离为：

$$\frac{| w^T x_i + b |}{\| w \|} = \frac{y_i(w^T x_i + b)}{\| w \|}$$

其中 $\| w \|$ 是 $w$ 的 $\ell_2$ 范数，即 $\sqrt{w_1^2 + \dots + w_n^2}$。

# 优化问题

现在我们可以得到以下优化目标：

$$\begin{aligned} \max_{w,b} &\quad \gamma \\ \text{s.t.} &\quad \frac{y_i(w^T x_i + b)}{\| w \|} \geq \gamma \end{aligned}$$

由于同时缩放 $w \to kw$ 和 $b \to kb$ 不会改变样本到超平面的距离，我们可以限制 $\| w \| \cdot \gamma = 1$，则上式等价于：

$$\begin{aligned} \max_{w,b} &\quad \frac{1}{\| w \|} \\ \text{s.t.} &\quad y_i(w^T x_i + b) \geq 1 \end{aligned}$$

为了后面计算方便，再做一点转换：

$$\begin{aligned} \min_{w,b} &\quad \frac{1}{2} \| w \|^2 \\ \text{s.t.} &\quad 1 - y_i(w^T x_i + b) \leq 0 \end{aligned}$$

# 对偶问题

现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。由于这个问题的特殊结构，这里通过拉格朗日对偶性（Lagrange duality）将其转换为对偶问题（dual problem）进行求解，这样做的优点在于：

• 对偶问题更容易求解，减小计算复杂度
• 可以自然的引入核函数，从而推广到非线性分类问题

# 拉格朗日乘子法

我们面对的问题是不等式约束，令：

$$\begin{aligned} L(x, w, b, \lambda) &= \underbrace{f(x)}_{\text{要优化的函数}} + \sum_{i=1}^n \lambda_i \underbrace{g_i(x)}_{\text{约束条件}} \\ &= \frac{1}{2} \| w \|^2 + \sum_{i=1}^n \lambda_i \Big (1 - y_i(w^T x_i + b) \Big ) \end{aligned}$$

函数 $L(x, w, b, \lambda)$ 为广义拉格朗日函数（将约束条件融合到目标函数里去，从而只用一个函数表达式来表达问题），$\lambda \geq 0$ 为拉格朗日乘子。

按照拉格朗日乘子法的思路，可以用 $L(x, w, b, \lambda)$ 对 $x$ 和 $\lambda$ 求偏导得到鞍点：

$$\begin{cases} \frac{\partial L}{\partial x_i} &i = 1, 2, \dots, n \\ \frac{\partial L}{\partial \lambda_k} &k = 1, 2, \dots, l \end{cases}$$

再根据问题本身的具体情况检验出极值点。但这里共有 $n+l$ 个优化变量，如果全部求偏导工作量太大，所以考虑将原问题转化成其对偶问题进行求解。

# 极小极大问题

定义一个函数：

$$\theta_P(x) = \max_{\lambda_i \geq 0} L(x, w, b, \lambda)$$

容易得到：

• 假设第 $i$ 个约束条件没有被满足，即 $g_i(x) > 0$，则可以使 $\lambda_i \to + \infty$，从而 $\theta_P(x) = + \infty$
• 假设所有约束条件都满足了，则可以使 $\lambda_i \to 0$，从而 $\theta_P(x) = \frac{1}{2} \| w \|^2$

所以极小化问题：

$$\min_{w,b} \theta_P(x) = \min_{w,b} \max_{\lambda_i \geq 0} L(x, w, b, \lambda)$$

与原始最优化问题等价，即有相同的解（因为当趋向无穷时，问题无解，所以必须满足约束条件）。上式称为广义拉格朗日函数的极小极大问题，也是我们们要优化的原始问题。

# 强对偶性

如果直接求解上述优化问题，需要考虑 $\min$ 的 $w$ 和 $b$，但这里我们可以通过强对偶转换把 $w$ 和 $b$ 化简掉，减小计算复杂度。

原始问题的对偶问题为：

$$\max_{\lambda_i \geq 0} \min_{w,b} L(x, w, b, \lambda)$$

如果原始问题与对偶问题都有最优解，容易推出：

$$\underbrace{\max_{\lambda_i \geq 0} \min_{w,b} L(x, w, b, \lambda)}_{\text{对偶问题}} \leq \underbrace{\min_{w,b} \max_{\lambda_i \geq 0} L(x, w, b, \lambda)}_{\text{原始问题}} \\[1pt]$$

这个性质叫弱对偶性（weak duality），对于所有优化问题都成立，即使原始问题非凸。但如果我们希望将原始问题转换为对偶问题求解，就要求它们必须满足强对偶性（strong duality）：

$$\max_{\lambda_i \geq 0} \min_{w,b} L(x, w, b, \lambda) = \min_{w,b} \max_{\lambda_i \geq 0} L(x, w, b, \lambda)$$

在满足以下两个条件的时候，可以进行强对偶转换：

• Slater 条件：当主问题为凸优化问题, 即 $f$ 和 $g_i$ 为凸函数，$h_j$ 为仿射函数（$h_j(x) = 0$，SVM 里没有这个约束），且可行域中至少有一点使不等式约束严格成立时，对偶问题等价于主问题。

  证明过程可以参考 Convex Optimization 5.3.2 节。

  Slater 条件是强对偶成立的充分条件（强对偶成立的一种情况，并不是唯一的情况），确保了鞍点的存在。

  显然，$f(x) = \frac{1}{2} \| w \|^2$ 和 $g_i(x) = 1 - y_i(w^T x_i + b)$ 都是凸函数，所以 SVM 满足 Slater 条件。

• KKT 条件：取极值的充分条件，确保鞍点一定是最优解；当原问题是凸优化问题时，KKT 条件是取极值的充要条件。它要求原问题在最优值处必须满足：

  • 拉格朗日乘子非负：$\lambda_i \geq 0$
  • 约束条件满足：$g_i(x) < 0 \rArr 1 - y_i(w^T x_i + b) \leq 0$
  • 互补松弛 (complementary slackness)：$\lambda_i g_i(x) = 0$

  KKT 条件的细节可以看这里。

# 对偶问题求解

总结一下，我们要优化的是：

$$\max_{\lambda_i \geq 0} \min_{w,b} \left [ \frac{1}{2} \| w \|^2 + \sum_{i=1}^n \lambda_i \Big (1 - y_i(w^T x_i + b) \Big ) \right ]$$

# 极小化

先固定 $\lambda$，让 $L$ 关于 $w$ 和 $b$ 最小化，所以使 $w, b$ 的偏导等于零：

$$\begin{gather} \frac{\partial L}{\partial w} = w - \sum_{i=1}^n \lambda_i x_i y_i = 0 \rArr w = \sum_{i=1}^n \lambda_i x_i y_i \\ \frac{\partial L}{\partial b} = \sum_{i=1}^n \lambda_i y_i = 0 \end{gather}$$

把上述结果代回函数中：

$$\min_{w,b} L(x, w, b, \lambda) = \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j$$

证明

$$\begin{aligned} L(x, w, b, \lambda) &= \frac{1}{2} \| w \|^2 + \sum_{i=1}^n \lambda_i \Big (1 - y_i(w^T x_i + b) \Big ) \\ &= \frac{1}{2} w^T w - \sum_{i=1}^n \lambda_i y_i w^T x_i - \underbrace{\sum_{i=1}^n \lambda_i y_i b}_{\text{代入} (2)} + \sum_{i=1}^n \lambda_i \\ &= \frac{1}{2} w^T \underbrace{\sum_{i=1}^n \lambda_i x_i y_i}_{\text{代入} (1)} - w^T \sum_{i=1}^n \lambda_i y_i x_i + \sum_{i=1}^n \lambda_i \\ &= - \frac{1}{2} w^T \sum_{i=1}^n \lambda_i x_i y_i + \sum_{i=1}^n \lambda_i \\ &= - \frac{1}{2} \left (\sum_{i=1}^n \lambda_i x_i y_i \right )^T \sum_{i=1}^n \lambda_i x_i y_i + \sum_{i=1}^n \lambda_i \\ &= - \frac{1}{2} \underbrace{\sum_{i=1}^n \lambda_i y_i (x_i)^T}_{\lambda_i, y_i \text{ 都是实数，转置后与自身一样}} \sum_{i=1}^n \lambda_i y_i x_i + \sum_{i=1}^n \lambda_i \\ &= \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j \\ \end{aligned}$$

可以看到 $w, b$ 已经被化简掉了，只要求出 $\lambda$ 就可以了。

原问题的复杂度是与样本维度（即 $w$ 的维度）相关的，而转换成对偶问题后，复杂度就与样本维度无关，而只与样本数量有关了。在求解非线性问题时，会涉及到用核函数升维，升维后的样本维度往往远大于样本数量，这时在对偶问题下求解计算复杂度会小很多。

# 极大化（SMO）

现在要让 $L$ 关于 $\lambda$ 最大化，即：

$$\begin{aligned} \max_{\lambda_i \geq 0} &\quad \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j \\ \text{s.t.} &\quad \sum_{i=1}^n \lambda_i y_i = 0 \end{aligned}$$

把上式转换为求解极小：

$$\begin{aligned} \min_{\lambda_i \geq 0} &\quad \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j - \sum_{i=1}^n \lambda_i \\ \text{s.t.} &\quad \sum_{i=1}^n \lambda_i y_i = 0 \end{aligned}$$

这个优化问题属于二次规划问题，可以用 SMO（序列最小优化算法，Sequential Minimal Optimization) 算法求解，其核心思想是：每次只优化一个参数，固定其他参数，仅求当前这个优化参数的极值。

但因为有约束条件 $\sum_{i=1}^n \lambda_i y_i = 0$，没法一次只变动一个参数，所以这里一次优化两个参数。只有两个变量的二次规划问题存在解析解。

选择两个需要更新的参数 $\lambda_i, \lambda_j$，那么 SMO 这一步的优化目标为：

$$\begin{gather} \begin{split} \min_{\lambda_i \geq 0} \quad & \frac{1}{2} (\lambda_i^2 y_i^2 x_i^T x_i + \lambda_j^2 y_j^2 x_j^T x_j) + \lambda_i \lambda_j y_i y_j x_i^T x_j - (\lambda_i + \lambda_j) \\ &+ \lambda_i y_i \sum_{k \not = i, j} \lambda_k y_k x_i^T x_k + \lambda_j y_j \sum_{k \not = i, j} \lambda_k y_k x_j^T x_k \end{split} \\ \text{s.t.} \quad \lambda_i y_i + \lambda_j y_j = c \end{gather}$$

其中 $c = - \sum_{k \not = i, j} \lambda_k y_k$。可以由 $(4)$ 得到 $\lambda_j = \frac{c - \lambda_i y_i}{y_j}$，由此可以消去 $\lambda_j$，这时目标问题就被转换为了只有一个约束条件 $\lambda_i$ 的最优化问题。

SMO 的具体流程就直接去看《统计学习方法》7.4 节吧，或者这里也总结了一下，咕咕咕。

# 求 w 和 b

现在已经通过 SMO 求得了最优解 $\lambda^*$，现在需要算出 $w$ 和 $b$。

由公式 $(1)$ 可以求得 $w$。

证明

由 KKT 条件可以得到：

$$\lambda_i (1 - y_i(w^T x_i + b)) = 0$$

所以当 $\lambda_i > 0$ 时：

$$1 - y_i(w^T x_i + b) = 0 \rArr y_i(w^T x_i + b) = 1$$

所以样本 $x_i$ 是支持向量。

所以根据 $\lambda_i > 0$ 随便找个支持向量 $x_s$，然后带入 $y_s(w^T x_s + b) = 1$ 求出 $b$ 即可：

$$\begin{gathered} y_s(w^T x_s + b) = 1 \\ \rArr y_s^2(w^T x_s + b) = y_s \\ \rArr w^T x_s + b = y_s \\ \rArr b = y_s - w^T x_s \end{gathered}$$

考虑到鲁棒性，可以用支持向量的均值来算 $b$：

$$b = \frac{1}{|S|} \sum_{s \in S} (y_s - w^T x_s)$$

其中 $S$ 是所有支持向量的集合。然后最大间隔超平面 $w^T + b = 0$ 就算出来了。

---

之前我们从直觉上得出了 SVM 的参数只受支持向量的影响，与其他样本无关这个结论。现在我们可以从数学上证明一下这个结论：

也就是说我们只需要保存支持向量以供预测。

# 软间隔

到目前为止的推导都是基于数据线性可分的假设下进行的，这个假设下的间隔叫硬间隔（hard margin）。但这个假设可能不成立：

虽然理论上我们总能找到一个高维映射（核函数）使数据线性可分，但在实际应用中，寻找这样一个合适的核函数可能会很难。同时由于数据中通常有噪声存在，一味追求数据线性可分可能会使模型过拟合。所以我们引入了软间隔（soft margin），允许部分样本分类错误（上图中的小红点和小蓝点），即不满足约束条件 $1 - y_i(w^T x_i + b) \leq 0$。

为了度量这个间隔软到何种程度，我们为每个样本引入一个松弛变量（slack variable）$\xi_i \geq 0$：

$$1 - y_i(w^T x_i + b) - \xi_i \leq 0$$

并且我们希望分类错误的样本要尽可能少。所以现在优化目标变成了：

$$\begin{aligned} \min_{w,b} &\quad \frac{1}{2} \| w \|^2 + C \sum_{i=1}^n \xi_i \\ \text{s.t.} &\quad 1 - y_i(w^T x_i + b) - \xi_i \leq 0, \xi_i \geq 0 \end{aligned}$$

其中 $C$ 是一个大于 0 的常数，可以理解为错误样本的惩罚程度。特殊情况，当 $C$ 无穷大时，$\xi$ 就会无穷小，相当于线性可分 SVM。

# 拉格朗日函数

这样拉格朗日函数就变为了：

$$L(x, w, b, \lambda, \xi) = \frac{1}{2} \| w \|^2 + C \sum_{i=1}^n \xi_i + \sum_{i=1}^n \lambda_i \Big (1 - \xi_i - y_i(w^T x_i + b) \Big ) - \sum_{i=1}^n \mu_i \xi_i$$

其中 $\lambda_i \geq 0, \mu_i \geq 0$ 为拉格朗日乘子。

# 强对偶性

通过强对偶性把优化问题转换为：

$$\max_{\lambda_i \geq 0, \mu_i \geq 0} \min_{w, b, \xi} L(x, w, b, \lambda, \xi)$$

# 对偶问题求解

跟线性 SVM 一样，先固定 $\lambda, \mu$，让 $L$ 关于 $w, b, \xi_i$ 最小化，即使 $w, b, \xi_i$ 的偏导为零：

$$\begin{gathered} \frac{\partial L}{\partial w} = w - \sum_{i=1}^n \lambda_i x_i y_i = 0 \rArr w = \sum_{i=1}^n \lambda_i x_i y_i \\ \frac{\partial L}{\partial b} = \sum_{i=1}^n \lambda_i y_i = 0 \\ \frac{\partial L}{\partial \xi_i} = C - \lambda_i - \mu_i = 0 \rArr \lambda_i + \mu_i = C \\ \end{gathered}$$

把上面的式子代入拉格朗日函数得到：

$$\min_{w, b, \xi} L(x, w, b, \lambda, \xi) = \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j$$

可以看到 $\mu$ 被化简掉了，所以只需要最大化 $\lambda$ 就好。转换成求解极小：

$$\begin{aligned} \min_{\lambda_i \geq 0} &\quad \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j - \sum_{i=1}^n \lambda_i \\ \text{s.t.} &\quad \sum_{i=1}^n \lambda_i y_i = 0, \lambda_i + \mu_i = C \end{aligned}$$

因为 $\mu_i \geq 0$，所以 $\lambda_i = C - \mu_i < C$，于是 $\mu_i$ 被消去了，所以上式现在写做：

$$\begin{aligned} \min_{\lambda_i \geq 0} &\quad \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j x_i^T x_j - \sum_{i=1}^n \lambda_i \\ \text{s.t.} &\quad \sum_{i=1}^n \lambda_i y_i = 0, \lambda_i < C \end{aligned}$$

可以看到这个式子相比硬间隔的版本只是多了一个约束条件 $\lambda_i < C$。然后用 SMO 算法得到最优解 $\lambda^*$ 即可。

再然后用和硬间隔一样的方法求出 $w$ 和 $b$，从而求出超平面就行。

# Hinge Loss

SVM 的优化目标还有另外一种理解，即最小化 Hingle Loss：

$$L = \sum_{i=1}^n \max(1 - y_i(w^T x_i + b), 0) + \lambda \| w \|^2$$

其中第一项是经验风险，第二项是正则项。它的意思是 $y_i(w^T x_i + b) > 1$ 时损失为 0，否则损失为 $1 - y_i(w^T x_i + b)$。相比感知机的损失函数 $\max(y_i(w^T x_i + b), 0)$ 来说，hinge loss 不仅要分类正确，而且置信度还要足够高（间隔最大化），损失才为 0，更加严格。

Hingle Loss 的函数图像为：

因为长得像本打开的书，所以中文名叫合页损失。它的零区域对应的是不是支持向量的普通样本，从而所有的普通样本都不参与最终超平面的决定。

# 核函数

前面讨论的硬间隔和软间隔都是假设训练样本的线性可分或至少大部分线性可分，但很多时候样本不是线性可分的（左图）：

这是就需要用到核函数（kernel function）将原空间的样本映射到一个更高维甚至无穷维（比如高斯核）的空间（右图），让样本点在高维空间线性可分，然后再学习出一个最大间隔超平面。

一个定理是：

那么设原空间为 $\mathcal{X} \in \Reals^d$，新空间为 $\mathcal{Z} \in \Reals^{\tilde{d}}$，从原空间到新空间的映射为 $\phi: \mathcal{X} \to \mathcal{Z}$。我们把函数 $K(x, z) = \phi(x) \cdot \phi(z)$ 叫做核函数。

现在新空间中的超平面可以写为 $w^T \phi(x) + b = 0$，非线性 SVM 的对偶问题变为：

$$\begin{aligned} \min_{\lambda_i \geq 0} &\quad \frac{1}{2} \sum_{i=1,j=1}^n \lambda_i \lambda_j y_i y_j K(x_i, x_j) - \sum_{i=1}^n \lambda_i \\ \text{s.t.} &\quad \sum_{i=1}^n \lambda_i y_i = 0, \lambda_i < C \end{aligned}$$

可以看到实际上我们只定义了核函数 $K$，而并没有显示地定义映射函数 $\phi$，因为通常来说直接计算 $K(x, z)$ 比较容易，而通过 $\phi(x)$ 和 $\phi(y)$ 来计算 $K(x, z)$ 则并不容易。也就是说核函数并没有把特征映射到高维空间，而是找到了一种直接在低位空间对高维空间中的向量做点积运算的简便方法。

# 常用核函数

常用的核函数 $K(x_i, x_j)$ 有：

名称	形式	优点	缺点
线性核	$x_i^T x_j$	高效；不容易过拟合	无法解决非线性可分问题
多项式核	$(\beta x_i^T x_j + \theta)^p$	比线性核更一般，$p$ 直接描述了被映射空间的复杂度	参数多，当 $p$ 很大时会导致计算不稳定
高斯核（RBF）	$\exp \left (- \frac{\| x_i - x_j \|^2}{2 \sigma^2} \right )$	只有一个参数，没有计算不稳定的问题	计算慢；$\sigma$ 是超参，所以需要调参；过拟合风险大

# 正定核

如果要自定义核函数，则需要满足 Mercer 条件：

# 优缺点

优点：

• 有严格的数学理论支持，可解释性强
• 能找出对任务至关重要的关键样本（支持向量）
• 参数只依赖少量的支持向量，无需依赖全体样本
• 计算的复杂性取决于样本的数量，而不是样本的维数，避免了“维数灾难”，可以有效解决高维特征的分类和回归问题
• 使用核函数后可以应对线性不可分问题
• 样本数量中等偏小时，同样有较好的效果

缺点：

• 在特征维度远大于样本个数时表现一般
• 在样本数量很多时训练时间会很长：SMO 算法每次都需要挑选一对参数，因此时间复杂度为 $O(n^2)$，其中 $n$ 为训练样本的数量
• 非线性问题的核函数没有选择标准
• 采用核函数时，如果需要存储核矩阵，则空间复杂度为 $O(n^2)$
• 因为参数只依赖少量的支持向量，所以对缺失数据敏感
• 模型的预测时间与支持向量的个数成正比，所以当支持向量的数量较大时，预测时间复杂度较高

# 参考

• 统计学习方法. 李航.
• 【机器学习】支持向量机 SVM（非常详细）
• 支持向量机通俗导论（理解SVM的三层境界）
• 拉格朗日对偶性
• 支持向量机（SVM）必备知识(KKT、Slater、对偶）
• Convex Optimization. Stephen Boyd and Lieven Vandenberghe. 2004.
• 支持向量机（SVM）—— SMO 算法