支持向量机

1. 简介

支持向量机（Support Vector Machines，SVM）是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。支持机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题。

支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机、线性支持向量机以及非线性支持向量机。

当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器， 即线性可分支持向量机，又称硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

2. 线性可分支持向量机

假设给定一个特征空间上的训练数据集

$$T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$$

其中，$x_i \in \mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y} = \{+1, -1\}, i = 1, 2, \cdots, N$。$x_i$ 为第 $i$ 个特征向量，也称为实例，$y_i$ 为 $x_i$ 的类标记。当 $y_i = +1$ 时，称 $x_i$ 为正例；当 $y_i = -1$ 时，称 $x_i$ 为负例。$(x_i, y_i)$ 称为样本点。再假设训练数据集是线性可分的。

学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程 $w \cdot x + b= 0$。一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。**感知机利用误差分类最小的策略，求得分离超平面，此时的解有无穷多个；线性可分支持向量机利用间隔最大化求最优分离超平面，此时解是唯一的。**支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

• 定义：给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规化问题学习得到的分离超平面为

  $$w^{*} \cdot x + b^{*} = 0$$

  以及相应的分类决策函数

  $$f(x) = \mathrm{sign}(w^{*} \cdot x + b^{*})$$

  称为线性可分支持向量机。

• 函数间隔：对于给定的训练数据集 $T$ 和超平面 $(w, b)$，定义超平面 $(w, b)$ 关于样本点 $(x_i, y_i)$ 的函数间隔为

  $$\hat{\gamma}_i = y_i (w \cdot x_i + b)$$

  定义超平面 $(w, b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(w, b)$ 关于 $T$ 中所有样本点 $(x_i, y_i)$ 的函数间隔之最小值，即

  $$\hat{\gamma} = \min_{i=1,\cdots,N} \hat{\gamma}_i$$

• 几何间隔：几何间隔是对函数间隔的规范化，其定义为

  $$\gamma_i = y_i \left(\frac{w}{\lVert w \rVert } \cdot x_i + \frac{b}{\lVert w \rVert}\right)$$

  定义超平面 $(w, b)$ 关于训练数据集 $T$ 的几何间隔为超平面 $(w, b)$ 关于 $T$ 中所有样本点 $(x_i, y_i)$ 的函数间隔之最小值，即

  $$\gamma = \min_{i=1,\cdots,N} \gamma_i$$

• 间隔最大化：求解最大间隔分离超平面问题，具体可以表示为下面的约束最优化问题：

  $$\begin{aligned} \max_{w,b} & \quad \gamma \\ \mathrm{s.t.} & \quad y_i \left( \frac{w}{\lVert w \rVert} \cdot x_i + \frac{b}{\lVert w \rVert} \right) \geq \gamma, i = 1, 2, \cdots, N \end{aligned}$$

  对上述问题进行简化，可以得到等价的下述最优化问题：

  $$\begin{aligned} \min_{w, b} &\quad \frac{1}{2}\lVert w \rVert^2 \\ \mathrm{s.t.} &\quad y_i(w \cdot x_i + b) - 1 \geq 0, i = 1, 2, \cdots, N \end{aligned}$$

  最大间隔法

  输入：线性可分训练数据集 $T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中，$x_i \in \mathcal{X} = \mathbb{R}^n$，$y_i \in \mathcal{Y} = \{-1, +1\}, i = 1, 2, \cdots, N$；

  输出：最大间隔分离超平面和分类决策函数。

  1. 构造并求解约束最优化问题：

     $$\begin{aligned} \min_{w,b} &\quad \frac{1}{2} \lVert w \rVert^2 \\ \mathrm{s.t.} &\quad y_i(w \cdot x_i + b) - 1 \geq 0, i = 1, 2, \cdots, N \end{aligned}$$

     求得最优解 $w^*, b^*$。

  2. 由此得到分离超平面：

     $$w^* \cdot x + b^* = 0$$

     分类决策函数：

     $$f(x) = \mathrm{sign}(w^* \cdot x + b^*)$$

  对偶算法

  输入：线性可分训练数据集 $T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中，$x_i \in \mathcal{X} = \mathbb{R}^n$，$y_i \in \mathcal{Y} = \{-1, +1\}, i = 1, 2, \cdots, N$；

  输出：最大间隔分离超平面和分类决策函数。

  1. 构造并求解约束最优化问题：

     $$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ \mathrm{s.t.} &\quad \sum_{i=1}^N \alpha_i y_i = 0 \\ &\quad \alpha_i \geq 0, i = 1,2,\cdots,N \end{aligned}$$

     求得最优解 $\alpha^* = (\alpha_1^*, \alpha_2^*, \cdots, \alpha_N^*)^T$。

  2. 计算

     $$w^* = \sum_{i=1}^N \alpha_i^* y_i x_i \\ b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i (x_i \cdot x_j)$$

  3. 求得分离超平面

     $$w^* \cdot x + b^* = 0$$

     分类决策函数

     $$f(x) = \mathrm{sign}(w^* \cdot x + b^*)$$

• 定理（最大间隔分离超平面的存在唯一性）：若训练数据集 $T$ 线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

• 支持向量：在线线性可分情况下，训练数据集的样本点中与「分离超平面」距离最近的样本点的实例称为「支持向量」。支持向量是使以下约束等号成立的点：

  $$y_i(w \cdot x_i + b) - 1 = 0$$

  在决定分离超平面时，只有支持向量起作用，而其它实例点并不起作用。

3. 线性支持向量机

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束并不能都成立。要将它扩展到线性不可分问题上，就需要修改硬间隔最大化，使其成为软间隔最大化。

• 线性不可分意味着某些样本点 $(x_i, y_i)$ 不能满足函数间隔大于等于 $1$ 的约束条件。可以对每个样本点 $(x_i, y_i)$ 引进一个松弛变量 $\xi_i \geq 0$，使函数间隔加上松弛变量大于等于 $1$。即约束条件变为

  $$y_i (w \cdot x_i + b) \geq 1 - \xi_i$$

  同时，对每个松弛变量 $\xi_i$，支付一个代价 $\xi_i$。目标函数由原来的 $\frac{1}{2} \lVert w \rVert^2$ 变成

  $$\frac{1}{2} \lVert w \rVert^2 + C\sum_{i=1}^N \xi_i$$

  其中，$C > 0$ 称为惩罚参数，一般由应用问题决定。$C$ 值大时对误分类的惩罚增大，$C$ 值小时对误分类的惩罚减小。最小化新目标函数的含义为：使 $\frac{1}{2} \lVert w \rVert^2$ 尽量小即间隔尽量大，同时使误差分类点的个数尽量小。

线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题：

$$\begin{aligned} \min_{w,b,\xi} &\quad \frac{1}{2} \lVert w \rVert^2 + C \sum_{i=1}^N \xi_i \\ \mathrm{s.t.} &\quad y_i(w \cdot x_i + b) \geq 1 - \xi_i, i = 1, 2, \cdots, N \\ &\quad \xi_i \geq 0, i = 1, 2, \cdots, N \end{aligned}$$

该问题是一个凸二次规化问题，因此关于 $(w, b, \xi)$ 的解是存在的。可以证明 $w$ 的解是唯一的，但 $b$ 的解可能不唯一，而是存在一个区间。

• 线性支持向量机：对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大化问题，得到的分离超平面为

  $$w^* \cdot x + b^* = 0$$

  以及相应的分类决策函数

  $$f(x) = \mathrm{sign}(w^* \cdot x + b^*)$$

  线性支持向量机学习算法

  输入：线性可分训练数据集 $T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中，$x_i \in \mathcal{X} = \mathbb{R}^n$，$y_i \in \mathcal{Y} = \{-1, +1\}, i = 1, 2, \cdots, N$；

  输出：分离超平面和分类决策函数。

  1. 选择惩罚参数 $C > 0$，构造并求解凸二次规划问题

     $$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ \mathrm{s.t.} &\quad \sum_{i=1}^N \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq C, i = 1, 2, \cdots, N \end{aligned}$$

     求得最优解 $\alpha^* = (\alpha_1^*, \alpha_2^*, \cdots, \alpha_N^*)^T$。

  2. 计算

     $$w^* = \sum_{i=1}^N \alpha_i^* y_i x_i \\ b^* = y_j - \sum_{i=1}^N y_i \alpha_i^* (x_i \cdot x_j)$$

  3. 求得分离超平面

     $$w^* \cdot x + b^* = 0$$

     分类决策函数

     $$f(x) = \mathrm{sign}(w^* \cdot x + b^*)$$

• 支持向量：在线性不可分的情况下，将上述问题的解 $\alpha^* = (\alpha_1^*, \alpha_2^*, \cdots, \alpha_N^*)^T$ 中对应于 $\alpha_i^* > 0$ 的样本点 $(x_i, y_i)$ 的实例 $x_i$ 称为软间隔的支持向量。若 $\alpha_i^* < C$，则 $\xi_i = 0$，支持向量 $x_i$ 恰好落在间隔边界上；若 $\alpha_i^* = C, 0 < \xi_i < 1$，则分类正确，$x_i$ 在间隔边界与分离超平面之间；若 $\alpha_i^* = C, \xi_i = 1$，则 $x_i$ 在分离超平面上；若 $\alpha_i^* = C, \xi_i > 1$，则 $x_i$ 位于分离超平面误分一侧。

• 合页损失函数：线性支持向量机学习还有另外一种解释，即最小化以下目标函数：

  $$\sum_{i=1}^N [1 - y_i(w \cdot x_i + b)]_+ + \lambda \lVert w \rVert^2$$

  其中，第一项是经验损失函数/经验风险，函数

  $$L(y(w \cdot x + b)) = [1 - y(w \cdot x + b)]_+$$

  称为合页损失函数，下标「+」表示以下取正值的函数

  $$[z]_+ = \begin{cases} z & z > 0 \\ 0 & z \leq 0 \end{cases}$$

  第二项是系数为 $\lambda$ 的 $w$ 的 $L_2$ 范数，是正则化项。

  定理：线性支持向量机原始最优化问题等价于以下最优化问题：

  $$\min_{w,b} \quad \sum_{i=1}^N [1 - y_i(w \cdot x_i + b)]_+ + \lambda \lVert w \rVert^2$$

4. 非线性支持向量机

对于解线性分类问题，线性分类支持向量机是一种非常有效的方法。但有时分类问题是非线性的，此时就需要使用非线性支持向量机，其主要特点是利用核技巧。

4.1 核技巧

非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。一般采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题来求解原来的非线性问题。用线性分类方法求解非线性分类问题分为两步：

• 首先使用一个变换将原空间的数据映射到新空间；
• 然后在新空间里用线性分类学习方法从训练数据中学习分类模型。

「核技巧」便属于这样的方法。核函数的定义如下：

• 定义（核函数）：设 $\mathcal{X}$ 是输入空间（欧氏空间 $\mathbb{R}^n$ 的子集或离散集合），又设 $\mathcal{H}$ 为特征空间（希尔伯特空间），如果存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射

  $$\phi(x): \mathcal{X} \rightarrow \mathcal{H}$$

  使得对所有 $x, z \in \mathcal{X}$，函数 $K(x, z)$ 满中条件

  $$K(x, z) = \phi(x) \cdot \phi(z)$$

  则称 $K(x, z)$ 为核函数，$\phi(x)$ 为映射函数，$[\cdot]$ 为内积。

核技巧的想法是，在学习和预测中只定义核函数 $K(x, z)$，而不显示地定义映射函数 $\phi$。通常，直接计算 $K(x, z)$ 比较容易，而通过 $\phi(x)$ 和 $\phi(z)$ 计算 $K(x, z)$ 并不容易。

仔细观察可以注意到，在线性支持向量机的对偶问题中，无论是目标函数还是决策函数，都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中，内积 $x_i \cdot x_j$ 可以用核函数 $K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)$ 来代替。此时对偶问题的目标函数成为

$$W(\alpha) = \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i$$

同样，分类决策函数中的内积也可以用核函数代替，而分类决策函数式成为

$$\begin{aligned} f(x) & = \mathrm{sign}\left( \sum_{i=1}^{N_s} a_i^* y_i \phi(x_i) \cdot \phi(x) + b^* \right) \\ & = \mathrm{sign}\left( \sum_{i=1}^{N_s} \alpha_i^* y_i K(x_i, x) + b^* \right) \end{aligned}$$

这等价于经过映射函数 $\phi$ 将原来的输入空间变换到一个新的特征空间，将输入空间中的内积 $x_i \cdot x_j$ 变换为特征空间中的内积 $\phi(x_i) \cdot \phi(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时，学习到的含有核函数的支持向量机也是非线性分类模型。

4.2 正定核

已知映射函数 $\phi$，可以通过 $\phi(x)$ 和 $\phi(z)$ 的内积求得核函数 $K(x, z)$。如何能不用构造映射 $\phi(x)$ 直接判断一个给定的函数 $K(x, z)$ 是不是核函数？或者说函数 $K(x, z)$ 需要满足什么条件才能成为核函数。

假设 $K(x, z)$ 是定义在 $\mathcal{X} \times \mathcal{X}$ 上的对称函数，并且对任意的 $x_1, x_2, \cdots, x_m \in \mathcal{X}$，$K(x, z)$ 关于 $x_1, x_2, \cdots, x_m$ 的 Gram 矩阵是半正定的。可以依据函数 $K(x, z)$ 构成一个希尔伯特空间，其步骤是：首先定义映射 $\phi$ 并构成向量空间 $\mathcal{S}$；然后在 $\mathcal{S}$ 上定义内积构成内积空间；最后将 $\mathcal{S}$ 完备化构成希尔伯特空间。

1. 定义映射，构成向量空间 $\mathcal{S}$：先定义映射 $\phi: x \rightarrow K(\cdot, x)$，根据这一映射，对任意 $x_i \in \mathcal{X}, \alpha_i \in \mathbb{R}, i = 1, 2, \cdots, m$，定义线性组合

   $$f(\cdot) = \sum_{i=1}^m \alpha_i K(\cdot, x_i)$$

   考虑由线性组合为元素的集合 $\mathcal{S}$。由于集合 $\mathcal{S}$ 对加法和数乘运算是封闭的，所以 $\mathcal{S}$ 构成一个向量空间。

2. 在 $\mathcal{S}$ 上定义内积，使其成为内积空间：在 $\mathcal{S}$ 上定义一个运算 $*$，对任意 $f, g \in \mathcal{S}$，有

   $$f(\cdot) = \sum_{i=1}^m \alpha_i K(\cdot, x_i) \\ g(\cdot) = \sum_{j=1}^l \beta_j K(\cdot, z_j)$$

   定义运算

   $$f \cdot g = \sum_{i=1}^m \sum_{j=1}^l \alpha_i \beta_j K(x_i, z_j)$$

3. 将内积空间 $\mathcal{S}$ 完备化为希尔伯特空间：根据定义的内积运算，可以得到范数

   $$\lVert f \rVert = \sqrt{f \cdot f}$$

   因此，$\mathcal{S}$ 是一个赋范空间。根据泛函分析理论，对于不完备的赋范空间 $\mathcal{S}$，一定可以使之完备化，得到完备的赋范空间 $\mathcal{H}$，即希尔伯特空间。

• 定理（正定核的充要条件）：设 $K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ 是对称函数，则 $K(x, z)$ 为正定核函数的充要条件是对任意 $x_i \in \mathcal{X}, i = 1, 2, \cdots, m$，$K(x, z)$ 对应的 Gram 矩阵

  $$K = [K(x_i, x_j)]_{m \times m}$$

  是半正定矩阵。

• 定义（正定核的等价定义）：设 $\mathcal{X} \subset \mathbb{R}^n$，$K(x, z)$ 是定义在 $\mathcal{X} \times \mathcal{X}$ 上的对称函数，如果对任意 $x_i \in \mathcal{X}, i = 1, 2, \cdots, m$，$K(x, z)$ 对应的 Gram 矩阵

  $$K = [K(x_i, x_j)]_{m \times m}$$

  是半正定矩阵，则称 $K(x, z)$ 是正定核。

4.3 常用核函数

1. 多项式核函数：

   $$K(x, z) = (x \cdot z + 1)^p$$

   对应的支持向量机是一个 $p$ 次多项式分类器。在此情形下，分类决策函数成为

   $$f(x) = \mathrm{sign}\left( \sum_{i=1}^{N_s} a_i^* y_i (x_i \cdot x + 1)^p + b^* \right)$$

2. 高斯核函数：

   $$K(x, z) = \exp{\left( -\frac{\lVert x - z \rVert^2}{2\sigma^2} \right)}$$

   对应的支持向量机是高斯径向基函数分类器。在此情形下，分类决策函数成为

   $$f(x) = \mathrm{sign}\left( \sum_{i=1}^{N_s} a_i^* y_i \exp{\left( - \frac{\lVert x - x_i \rVert^2}{2\sigma^2} \right)} + b^* \right)$$

3. 字符串核函数：考虑一个有限字符表 $\Sigma$，字符串 $s$ 是从 $\Sigma$ 中取出的有限个字符的序列，包括空字符串。字符串 $s$ 的长度用 $\lvert s \rvert$ 表示，它的元素记作 $s(1)s(2) \cdots s(\lvert s \rvert)$。两个字符串 $s$ 和 $t$ 的连接记作 $st$。所有长度为 $n$ 的字符串的集合记作 $\Sigma^n$，所有字符串的集合记作 $\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n$。考虑字符串 $s$ 的子串 $u$，给定一个指标序列 $i = (i_1, i_2, \cdots, i_{\lvert u \rvert}), 1 \leq i_1 < i_2 \cdots < i_{\lvert u \rvert} \leq \lvert s \rvert$，$s$ 的子串定义为 $u = s(i) = s(i_1)s(i_2) \cdots s(i_{\lvert u \rvert})$，其长度记作 $l(i) = i_{\lvert u \rvert} - i_1 + 1$。如果 $i$ 是连续的，则 $l(i) = \lvert u \rvert$；否则 $l(i) \gt \lvert u \rvert$。假设 $\mathcal{S}$ 是长度大于或等于 $n$ 的字符串的集合，$s$ 是 $\mathcal{S}$ 的元素。现在建立字符串集合 $\mathcal{S}$ 到特征空间 $\mathcal{H}_n = \mathbb{R}^{\Sigma^n}$ 的映射 $\phi_n(s)$。$\mathbb{R}^{\Sigma^n}$ 表示定义在 $\Sigma^n$ 上的实数空间，其每一维对应一个字符串 $u \in \Sigma^n$，映射 $\phi_n(s)$ 将字符串 $s$ 对应于空间 $\mathbb{R}^{\Sigma^n}$ 的一个向量，其在 $u$ 维上的取值为

   $$[\phi_n(s)]_u = \sum_{i:s(i) = u} \lambda^{l(i)}$$

   其中，$0 < \lambda \leq 1$ 是一个衰减参数，$l(i)$ 表示字符串 $i$ 的长度，求和在 $s$ 中所有与 $u$ 相同的子串上进行。

   两个字符串 $s$ 和 $t$ 上的字符串核函数是基于映射 $\phi_n$ 的特征空间中的内积：

   $$\begin{aligned} k_n(s, t) &= \sum_{u \in \Sigma^n} [\phi_n(s)]_u [\phi_n(t)]_u \\ &= \sum_{u \in \Sigma^n} \sum_{(i,j):s(i) = t(j) = u} \lambda^{l(i)} \lambda^{l(j)} \end{aligned}$$

   字符串核函数 $k_n(s, t)$ 给出了字符串 $s$ 和 $t$ 中长度等于 $n$ 的所有子串组成的特征向量的余弦相似度。直观上，两个字符串相同的子串越多，它们就越相似，字符串核函数的值就越大。字符串核函数可以由动态规划快速地计算。

4.4 非线性支持向量分类机

• 定义（非线性支持向量机）：从非线性分类训练集，通过核函数与软间隔最大化/凸二次规划，学习得到的分类决策函数

  $$f(x) = \mathrm{sign} \left( \sum_{i=1}^N \alpha_i^* y_i K(x, x_i) + b^* \right)$$

  称为非线性支持向量机，$K(x, z)$ 是正定核函数。

非线性支持向量机学习算法

输入：线性可分训练数据集 $T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中，$x_i \in \mathcal{X} = \mathbb{R}^n$，$y_i \in \mathcal{Y} = \{-1, +1\}, i = 1, 2, \cdots, N$；

输出：分类决策函数。

1. 选取适当的核函数 $K(x, z)$ 和适当的参数 $C$，构造并求解最优化问题

   $$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ \mathrm{s.t.} &\quad \sum_{i=1}^N \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq C, i = 1, 2, \cdots, N \end{aligned}$$

   求得最优解 $\alpha^* = (\alpha_1^*, \alpha_2^*, \cdots, \alpha_N^*)^T$。

2. 计算

   $$b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i K(x_i, x_j)$$

3. 构造决策函数

   $$f(x) = \mathrm{sign}\left( \sum_{i=1}^N \alpha_i^* y_i K(x, x_i) + b^* \right)$$

当 $K(x, z)$ 是正定核函数时，上述问题是凸二次规划问题，解是存在的。

5. 序列最小最优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题，这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致于无法使用。序列最小最优化算法（Sequential Minimal Optimization，SMO）是一种能高效地实现支持向量机学习的算法。SMO 算法要解如下凸二次规划的对偶问题：

$$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ \mathrm{s.t.} &\quad \sum_{i=1}^N \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq C, i = 1, 2, \cdots, N \end{aligned}$$

在这个问题中，变量是拉格朗日乘子，一个变量 $\alpha_i$ 对应于一个样本点 $(x_i, y_i)$，变量的总数等于训练样本容量 $N$。SMO 算法是一种启发式算法，其基本思路是：如果所有变量都满足此最优化问题的 KKT 条件，那么这个最优化问题的解就得到了。因为 KKT 条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规化问题关于这两个变量的解应该更接近原始规划问题的解，因为这会使得原始规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反 KKT 条件最严重的那一个，另一个由约束条件自动确定。如此，SMO 算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。

整个 SMO 算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。

注意，子问题的两个变量中只有一个是自由变量。假设 $\alpha_1, \alpha_2$ 为两个变量，$\alpha_3, \alpha_4, \cdots, \alpha_N$ 固定，那么由等式约束可知：

$$\alpha_1 = -y_1 \sum_{i=2}^N \alpha_i y_i$$

如果 $\alpha_2$ 确定，那么 $\alpha_1$ 也随之确实。所以子问题中同时更新两个变量。

5.1 两变量二次规划

不失一般性，假设选择的两个变量是 $\alpha_1, \alpha_2$，其他变量 $\alpha_i (i = 3, 4, \cdots, N)$ 是固定的。于是 SMO 的最优化问题的子问题可以写成：

$$\begin{aligned} \min_{\alpha_1, \alpha_2} &\quad W(\alpha_1, \alpha_2) = \frac{1}{2} K_{11} \alpha_1^2 + \frac{1}{2} K_{22} \alpha_2^2 + y_1 y_2 K_{12} \alpha_1 \alpha_2 - \\ &\qquad (\alpha_1 + \alpha_2) + y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i2} \\ \mathrm{s.t.} &\quad \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^N y_i \alpha_i = \xi \\ &\quad 0 \leq \alpha_i \leq C, i = 1, 2 \end{aligned}$$

其中，$K_{i, j} = K(x_i, x_j), i,j = 1, 2, \cdots, N$，$\xi$ 是常数。

5.2 SMO 算法

输入：训练数据集 $T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中，$x_i \in \mathcal{X} = \mathbb{R}^n$，$y_i \in \mathcal{Y} = \{-1, +1\}, i = 1, 2, \cdots, N$，精度 $\varepsilon$；

输出：近似解 $\hat{\alpha}$。

1. 取初值 $\alpha^{(0)} = 0$，令 $k = 0$；

2. 选取优化变量 $\alpha_1^{(k)}, \alpha_2^{(k)}$，解析求解两个变量的最优化问题，求得最优解 $\alpha_1^{(k+1)}, \alpha_2^{(k+1)}$，更新 $\alpha$ 为 $\alpha^{(k+1)}$。

3. 若在精度 $\varepsilon$ 范围内满足停机条件：

   $$\sum_{i=1}^N \alpha_i y_i = 0, 0 \leq \alpha_i \leq C, i = 1, 2, \cdots, N \\ y_i \cdot g(x_i) \begin{cases} \geq 1 & \{x_i | \alpha_i = 0\} \\ = 1 & \{x_i | 0 < \alpha_i < C\} \\ \leq 1 & \{x_i | \alpha_i = C\} \end{cases}$$

   其中，

   $$g(x_i) = \sum_{j=1}^N \alpha_j y_j K(x_j, x_i) + b$$

4. 取 $\hat{\alpha} = \alpha^{(k+1)}$。

SMO 算法在每个子问题中选择两个变量优化，其中至少一个变量违反 KKT 条件。

• SMO 选择第一个变量的过程为外层循环。外层循环在训练样本中选取违反 KKT 条件最严重的样本点，并将其对应的变量作为第一个变量。

• SMO 选择第二个变量的过程为内层循环。假设外层循环已经找到第一个变量 $\alpha_1$，内层循环则是去选择第二个变量 $\alpha_2$，并使 $\alpha_2$ 有足够大的变化。

• 在每次完成两个变量的优化后，需要重新计算阈值 $b$ 和差值 $E_i$。

  $$E_1 = \sum_{i=3}^N \alpha_i y_i K_{i1} + \alpha_1^{old} y_1 K_{11} + \alpha_2^{old} y_2 K_{21} + b^{old} - y_1 \\ E_1 = \sum_{i=3}^N \alpha_i y_i K_{i1} + \alpha_2^{old} y_2 K_{22} + \alpha_1^{old} y_1 K_{12} + b^{old} - y_2 \\ b_1^{new} = - E_1 - y_1 K_{11}(\alpha_1^{new} - \alpha_1^{old}) - y_2 K_{21}(\alpha_2^{new} - \alpha_2^{old}) + b^{old} \\ b_2^{new} = - E_2 - y_1 K_{12}(\alpha_1^{new} - \alpha_1^{old}) - y_2 K_{22} (\alpha_2^{new} - \alpha_2^{old}) + b^{old}$$

  如果 $\alpha_1^{new}, \alpha_2^{new}$ 同时满足条件 $0 < \alpha_i^{new} < C, i = 1, 2$，那么 $b_1^{new} = b_2^{new}$。如果 $\alpha_1^{new}, \alpha_2^{new}$ 是 $0$ 或者 $C$，那么 $b_1^{new}$ 和 $b_2^{new}$ 以及它们之间的数都是符合 KKT 条件的阈值，这时选择它们的中点作为 $b^{new}$。在每次完成两个变量的优化后，还必须更新对应的 $E_i$ 值，并将它们保存在列表中。$E_i$ 值的更新要用到 $b^{new}$ 值，以及所有支持向量对应的 $\alpha_j$：

  $$E_i^{new} = \sum_{S} y_j \alpha_j K(x_i, x_j) + b^{new} - y_i$$

  其中，$S$ 是所有支持向量 $x_j$ 的集合。

附录

• 《统计学习方法》by 李航