支持向量机

在详细讲解支持向量机相关概念的推导前，我们先详细讲讲一些重要的数学方法。

1. 拉格朗日乘数法

拉格朗日乘数法适用于下面的问题：

\min_{x_1,\dots,x_n} f(x_1, \dots, x_n) \quad \text{s.t.}\; g(x_1, \dots,x_n)=0

拉格朗日乘数法基于下面的定理：在取到最值的地方， $f(x_1, \dots, x_n)$ 和 $g(x_1, \dots, x_n)$ 的梯度是平行的。

$proof:$ 我们考虑点 $p$ 的方向向量 $v$ 。由于我们沿着约束条件 $g(x)=0$ 移动，移动方向满足：

\nabla g(x) \cdot v = 0

在取得最值的地方，此时的 $p$ 是 $f$ 在约束条件下的极值点，有：

\nabla f(x) \cdot v = 0

于是易得此时 $\nabla f(x)$ 与 $\nabla g(x)$ 平行。

有了这个定理，我们就可以令 $\nabla f(x) = \lambda \nabla g(x)$ ，并构造出如下的拉格朗日函数：

L(x_1, \dots, x_n, \lambda) = f(x_1, \dots, x_n) - \lambda g(x_1, \dots, x_n)

这样，我们就把一个有约束的优化问题，转化成了一个对 $L$ 的无约束的优化问题。我们只需要求 $L$ 对所有参数的偏导数：

\begin{aligned} \frac{\partial L}{\partial x_1}=0 &\Rightarrow \frac{\partial f}{\partial x_1}-\lambda\frac{\partial g}{\partial x_1}=0\\[4pt] \frac{\partial L}{\partial x_2}=0 &\Rightarrow \frac{\partial f}{\partial x_2}-\lambda\frac{\partial g}{\partial x_2}=0\\[4pt] &\vdots\\[4pt] \frac{\partial L}{\partial x_n}=0 &\Rightarrow \frac{\partial f}{\partial x_n}-\lambda\frac{\partial g}{\partial x_n}=0\\[6pt] \frac{\partial L}{\partial \lambda}=0 &\Rightarrow -\,g(x,y)=0 \Rightarrow g(x,y)=0 \end{aligned}

就可以得到约束条件下 $f$ 的最值了。

2. KKT 条件

KKT 条件 (Karush-Kuhn-Tucker Conditions) 是对拉格朗日方法的加强，它适用于求解如下问题（为了方便，这里只使用单参数）:

\min_{x} f(x) \quad \text{s.t.}\; g(x)\le0

KKT 条件规定，一个解是最优解，当且仅当它满足下面的条件：

平稳性： $\nabla f(x) - \lambda \nabla g(x) = 0$
原始可行性： $g(x) \le 0$
对偶可行性： $\lambda \ge 0$
互补松弛性： $\lambda g(x)=0$

其中互补松弛性是 KKT 条件的核心，它同时解决了下面两种情况：

约束无效：极值点在 $g(x)$ 约束区域内部，此时只需要 $\nabla f(x)=0$ 。
约束有效：极值点在 $g(x)$ 约束区域边界上或者外面，此时问题退化成拉格朗日乘数问题，即 $\nabla f(x) - \lambda g(x)=0$ 。

3. 拉格朗日对偶

假设我们正在解决下面这个原始问题：

\begin{aligned} \min_{x}\;& f(x) \\[6pt] \text{s.t.}\;& g_i(x) \le 0, \quad i=1,\dots,k \\[6pt] & h_j(x) = 0, \quad j=1,\dots,m \end{aligned}

直接求解这个问题可能有很大难度，于是我们先构造它的拉格朗日函数：

L(x, \alpha, \mu) = f(x) + \sum_{i=1}^k \alpha_i g_i(x) + \sum_{j=1}^m \mu_j h_j(x)

由 KKT 条件的对偶可行性，我们需要 $\alpha_i \ge 0$ 。

我们定义函数 $θ_P(x)$ ：

\theta_P(x) = \max_{\alpha, \mu; \alpha_i \ge 0} L(x, \alpha, \mu)

这个函数看起来很复杂，但它的行为很有趣：

如果 $x$ 违反了任何约束 (如某个 $g_i(x) > 0$ 或者 $h_j(x) \neq 0$ )：我们可以让对应的 $α_i$ 或 $μ_j$ 趋向于无穷大，从而使得 $L$ 也趋向于无穷大。因此 $θ_P(x) = ∞$ 。
如果 $x$ 满足了所有约束，此时 $g_i(x) \le 0，h_j(x) = 0$ 。为了最大化 $L$ ，因为 $αᵢ \ge 0$ ，所以 $αᵢgᵢ(x)$ 这一项最大也只能是 0（当 $αᵢ=0$ 或 $gᵢ(x)=0$ 时）。而 $μⱼhⱼ(x)$ 这一项永远是0。因此 $θ_P(x) = f(x)$ 。

所以，我们最初的那个带约束的 $\min f(x)$ 问题，就等价于下面这个不带约束的问题：

\min_x \theta_P(x) = \min_x \max_{\alpha, \mu; \alpha_i \ge 0} L(x, \alpha, \mu)

这被称为原始问题的min-max形式。

我们试着把 $\min$ 和 $\max$ 交换一下：

\max_{\alpha, \mu; \alpha_i \ge 0} \min_x L(x, \alpha, \mu)

这个问题就被称为拉格朗日对偶问题 (The Dual Problem)，其中 $θ_D(α, μ) = \min_x L(x, α, μ)$ 被称为对偶函数。

于是，我们有了下面两个问题：

原始问题 (P): $p^\star = \min \max L$
对偶问题 (D): $d^\star = \max \min L$

这两个问题具有如下关系：

弱对偶性 (Weak Duality)：这个性质永远成立。即对偶问题的解永远小于等于原始问题的解： $d^\star \le p^\star$ 。
强对偶性 (Strong Duality)：在某些良好的条件下（如原始问题是凸优化问题，并且满足一些约束规范，如Slater条件），等号会成立： $d^\star = p^\star$ $d^{⋆} = p^{⋆}$ 。
- SVM正好满足这些良好的条件！

4. 对原有优化式子的计算

有了这些数学上的准备后，我们开始引入核函数。

$a.$ 对偶问题转化

我们使用 KKT 条件对我们原有的优化式子：

\begin{aligned} \min_{w}\;& \frac{1}{2} \|w\|^2 + C\sum_{i=1}^N \xi_i\\[6pt] \text{s.t.}\;& \xi_i \ge 0,\quad y_i\big(w X_i + \beta) \ge 1-\xi_i,\quad i=1,\dots,N \end{aligned}

转换成如下的拉格朗日表达式：

L_P = \frac{1}{2} \|w\|^2 + C\sum_{i=1}^N \xi_i - \sum_{i=1}^N \alpha_i\big[\,y_i(w \cdot X_i + \beta) - (1-\xi_i)\,\big] - \sum_{i=1}^N \mu_i\,\xi_i

这里为了后面求偏导让系数都为1，写成了 $\frac{1}{2} \|w\|^2$ 。

根据拉格朗日对偶构造，我们先求解 $\min$ 。分别求偏导得：

\frac{\partial L_P}{\partial w}=0 \Rightarrow w - \sum_{i=1}^N \alpha_i y_i X_i = 0 \tag{1}

\frac{\partial L_P}{\partial \beta}=0 \Rightarrow \sum_{i=1}^N \alpha_iy_i=0 \tag{2}

\frac{\partial L_P}{\partial \xi_i}=0 \Rightarrow C-\alpha_i-\mu_i = 0 \tag{3}

\alpha_i\big[\,y_i(w X_i + \beta) - (1-\xi_i)\,\big] = 0 \tag{4}

由 $(1)$ 得 $w = \sum_{i=1}^N \alpha_i y_i X_i$ ，带入 $L_P$ 中：

\begin{aligned} L_P &= -\frac{1}{2}\|w\|^2 + C\sum_{i=1}^N \xi_i + \sum_{i=1}^N \alpha_i(1-\xi_i) - \sum_{i=1}^N \mu_i\,\xi_i \\[6pt] &= -\frac{1}{2}\|w\|^2 + \sum_{i=1}^N \alpha_i + \sum_{i=1}^N \big(C-\alpha_i-\mu_i\big)\,\xi_i \end{aligned}

由 $(3)$ ：

L_P=-\frac{1}{2}\| w \|^2 + \sum_{i=1}^N \alpha_i

由 $\|w\|^2=w\cdot w^T$ 以及 $(1)$ 得：

L_P= \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (X_i \cdot X_j)

这个式子就是我们最终的对偶式。于是我们的优化问题变成了：

\max _\alpha L_P(\alpha)

$b.$ 对对偶式的分析

现在我们详细地分析一下我们得到的对偶式：

L_P= \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (X_i \cdot X_j)

我们在原始问题中求解的 $w\cdot X + \beta$ 无法分开线性不可分的数据。而在对偶式中，我们发现数据点并不是单独出现、而是以点积形式出现的。这个特性启示我们可以用一个更为强大的核函数来替换这个简单的点积。通过选用不同的核函数（如高斯核、多项式核），我们能做到一件神奇的事情：在计算上不做改变，但效果上等同于将数据映射到了一个更高维甚至无限维的空间中，然后在这个高维空间里进行线性划分。

（关于核函数，我在 Data Science 的 “机器学习基础” 笔记中已经有详细的讲解，这里略过）

在原始问题中，我们需要优化权重向量。看着这个 $w$ ，我们很难直观地知道这个式子到底是由哪些训练样本决定的。而在对偶问题中，我们求解的是 $α$ 向量。求解完毕后，根据 KKT 条件，大部分没有超出间隔的点对应的 $\alpha_i$ 都为0，只有少数 $α_i$ 大于 0。这些 $\alpha_i \lt 0$ 的点就是支持向量。公式 $w = \sum_{i=1}^N \alpha_i y_i X_i$ 也指明整个模型也仅仅是由这些向量构建而成的。
原始问题的变量数量是 $d + n + 1$ ，而对偶问题的变量数量是 $n$ ，当原始问题的特征数量巨大时，我们可以转而优化这个对偶问题。