支持向量机

2019-01-28 本文已影响1人千与千与

支持向量机

线性可分支持向量机与硬间隔最大化
线性支持向量机与软间隔最大化
非线性支持向量机与核函数
序列最小最优化算法

支持向量机（support vector machines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。

支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case）、线性支持向量机（linear support vector machine）及非线性支持向量机（non-linear support vector machine）。

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

当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。

通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。

线性可分支持向量机与硬间隔最大化

假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧氏空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以，输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。
学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程 $\omega\cdot x+b＝0$ ，它由法向量 $\omega$ 和截距 $b$ 决定，可用 $(\omega,b)$ 来表示。分离超平面将特征空间划分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧为负类。
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面 $\omega \cdot x+b＝0$ 确定的情况下， $\mid \omega \cdot x+b \mid$ 能够相对地表示点 $x$ 距离超平面的远近。而 $\omega \cdot x+b$ 的符号与类标记 $y$ 的符号是否一致能够表示分类是否正确。所以可用量 $y(\omega \cdot x+b)$ 来表示分类的正确性及确信度，这就是函数间隔（functional margin）的概念。
对于给定的训练数据集 $T$ 和超平面 $(\omega,b)$ ，定义超平面 $(\omega,b)$ 关于样本点 $(x_i,y_i)$ 的函数间隔为
$\hat{\gamma}_i = y_i(\omega \cdot x_i + b)$
定义超平面 $(\omega,b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(\omega,b)$ 关于 $T$ 中所有样本点 $(x_i,y_i)$ 的函数间隔之最小值，即
$\hat{\gamma} = min_{i=1,2,...,N} \ \hat{\gamma}_i$
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变 $\omega$ 和 $b$ ，例如将它们改为 $2\omega$ 和 $2b$ ，超平面并没有改变，但函数间隔却成为原来的 2 倍。这一事实启示我们，可以对分离超平面的法向量 $\omega$ 加某些约束，如规范化， $\mid \mid \omega \mid \mid ＝ 1$ ，使得间隔是确定的。这时函数间隔成为几何间隔（geometric margin）。
对于给定的训练数据集 $T$ 和超平面 $(\omega,b)$ ，定义超平面 $(\omega,b)$ 关于样本点 $(x_i,y_i)$ 的几何间隔为
$\gamma_i = y_i(\frac{\omega}{\mid \mid \omega \mid \mid} \cdot x_i + \frac{b}{\mid \mid \omega \mid \mid})$
定义超平面 $(\omega,b)$ 关于训练数据集 $T$ 的几何间隔为超平面 $(\omega,b)$ 关于 $T$ 中所有样本点 $(x_i,y_i)$ 的几何间隔之最小值，即
$\gamma = min_{i=1,2,...,N} \ \gamma_i$
如果 $\mid \mid \omega \mid \mid＝1$ ，那么函数间隔和几何间隔相等。如果超平面参数 $\omega$ 和 $b$ 成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。这里的间隔最大化又称为硬间隔最大化。
间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。
最大间隔分离超平面可以表示为下面的约束最优化问题
$\begin{array} \ max_{\omega, b} & \gamma \\ s.t. & y_i(\frac{\omega}{\mid \mid \omega \mid \mid} \cdot x_i + \frac{b}{\mid \mid \omega \mid \mid}) \ge \gamma, \ \ \ \ \ i=1,2,...,N \end{array}$
即我们希望最大化超平面 $(\omega,b)$ 关于训练数据集的几何间隔·，约束条件表示的是超平面 $(\omega,b)$ 关于每个训练样本点的几何间隔至少是 $\gamma$ 。
考虑几何间隔和函数间隔的关系，可将这个问题改写为
$\begin{array} \ max_{\omega,b} & \frac{\hat{\gamma}}{\mid\mid \omega \mid\mid} \\ s.t. & y_i(\omega\cdot x_i + b) \ge \hat{\gamma}, \ \ \ \ \ i=1,2,...,N \end{array}$
函数间隔 $\hat{\gamma}$ 的取值并不影响最优化问题的解。事实上，假设将 $\omega$ 和 $b$ 按比例改变为 $\lambda \omega$ 和 $\lambda b$ ，这时函数间隔成为 $\lambda \hat{\gamma}$ 。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生一个等价的最优化问题。这样，就可以取 $\hat{\gamma}＝1$ 。将 $\hat{\gamma}＝1$ 代入上面的最优化问题，注意到最大化 $\frac{1}{\mid\mid \omega \mid\mid}$ 和最小化 $\frac{1}{2}\mid\mid \omega \mid\mid^2$ 是等价的，于是就得到下面的线性可分支持向量机学习的最优化问题
$\begin{array} \ min_{\omega, b} & \frac{1}{2}\mid\mid \omega \mid\mid^2 \\ s.t. & y_i(\omega\cdot x_i + b) - 1 \ge 0, \ \ \ \ \ i=1,2,...,N \end{array}$
这是一个凸二次规划问题（convex quadratic programming）。求解 $\omega^*$ ， $b^*$ ，就可以得到最大间隔分离超平面 $\omega^* \cdot x+b^*＝0$ 及分类决策函数 $f(x)＝sign(\omega^* \cdot x+b^*)$ ，即线性可分支持向量机模型。
线性可分训练数据集的最大间隔分离超平面是存在且唯一的。
证明： 以上可知最大间隔分离超平面可以表示为下面的约束最优化问题
$\begin{array} \ min_{\omega, b} & \frac{1}{2}\mid\mid \omega \mid\mid^2 \ \ \ \ \ (式1)\\ s.t. & y_i(\omega\cdot x_i + b) - 1 \ge 0, \ \ \ \ \ i=1,2,...,N \ \ \ \ \ (式2) \end{array}$

1>>存在性证明：
由于训练数据集线性可分，所以式1~式2 最优化问题一定存在可行解。又由于目标函数有下界，所以最优化问题必有解，记作 $(\omega^*, b^*)$ 。由于训练数据集中既有正类点又有负类点，所以 $(\omega, b) = (0, b)$ 不是最优化的可行解，因而最优解 $(\omega^*, b^*)$ 必满足 $\omega^* \neq 0$ 。由此得知分离超平面的存在性。

2>> 唯一性证明：
首先证明 $\omega^*$ 的唯一性。假设式1~式2 存在两个最优解 $(\omega_1^*, b_1^*)$ 和 $(\omega_2^*, b_2^*)$ ，显然 $\mid \mid \omega_1^* \mid \mid = \mid\mid \omega_2^* \mid\mid = c$ ，其中 $c$ 是一个常数。令 $\omega = \frac{\omega_1^* + \omega_2^*}{2}, b = \frac{b_1^*, b_2^*}{2}$ ，易知 $(\omega, b)$ 是式1~式2 的可行解。从而有
$\mid\mid \omega \mid\mid \le \frac{ \mid\mid \omega_1^* \mid\mid + \mid\mid \omega_2^* \mid\mid}{2} = c$
上式表明，如果 $\mid\mid \omega \mid\mid$ 小于 $\frac{ \mid\mid \omega_1^* \mid\mid + \mid\mid \omega_2^* \mid\mid}{2}$ ，由最优化目标函数式1 可知， $(\omega, b)$ 才是最优解，与假设矛盾，因此考虑 $\mid\mid \omega \mid\mid$ 等于 $\frac{ \mid\mid \omega_1^* \mid\mid + \mid\mid \omega_2^* \mid\mid}{2}$ 的情况，易知 $\omega_1^* = \omega_2^*$ ，由此可以把两个最优解 $(\omega_1^*, b_1^*)$ 和 $(\omega_2^*, b_2^*)$ 分别写成 $(\omega^*, b_1^*)$ 和 $(\omega^*, b_2^*)$ 。
再证 $b_1^*=b_2^*$ 。设 $x_1^\prime$ 和 $x_2^\prime$ 是集合 $\{x_i\mid y_i = +1\}$ 分别对应于 $(\omega^*, b_1^*)$ 和 $(\omega^*, b_2^*)$ 使得问题的不等式等号成立的点， $x_1^{\prime\prime}$ 和 $x_2^{\prime\prime}$ 是集合 $\{x_i\mid y_i = -1\}$ 分别对应于 $(\omega^*, b_1^*)$ 和 $(\omega^*, b_2^*)$ 使得问题的不等式等号成立的点，则由 $b_1^* = -\frac{1}{2}(\omega^*\cdot x_1^\prime + \omega^*\cdot x_1^{\prime\prime})$ ， $b_2^* = -\frac{1}{2}(\omega^*\cdot x_2^\prime + \omega^*\cdot x_2^{\prime\prime})$ 得
$b_1^* - b_2^* = -\frac{1}{2}[(\omega^* \cdot(x_1^\prime - x_2^\prime)) + \omega^* \cdot(x_1^{\prime\prime} - x_2^{\prime\prime})) ]$
又因为
$\omega^* \cdot x_2^\prime + b_1^* \ge 1 = \omega^* \cdot x_1^\prime + b_1^* \\ \omega^* \cdot x_1^\prime + b_2^* \ge 1 = \omega^* \cdot x_2^\prime + b_2^* \\$
所以 $\omega^* \cdot (x_1^\prime - x_2^\prime) = 0$ ，同理有 $\omega^* \cdot (x_1^{\prime\prime} - x_2^{\prime\prime}) = 0$ 。
因此 $b_1^* = b_2^*$ 。
由 $\omega_1^* = \omega_2^*$ 和 $b_1^* = b_2^*$ 可知，两个最优解 $(\omega_1^*, b_1^*)$ 和 $(\omega_2^*, b_2^*)$ 是相同的，解的唯一性得证。
在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。 支持向量是使约束条件式等号成立的点，即 $y_i(\omega\cdot x_i + b) - 1 = 0$ ，如下图中点 $H_1$ 和点 $H_2$ 就是支持向量。

注意到 $H_1$ 和 $H_2$ 平行，并且没有实例点落在它们中间。在 $H_1$ 与 $H_2$ 之间形成一条长带，分离超平面与它们平行且位于它们中央。长带的宽度，即 $H_1$ 与 $H_2$ 之间的距离称为间隔（margin）。间隔依赖于分离超平面的法向量 $\omega$ ，等于 $\frac{2}{\mid\mid \omega \mid\mid}$ 。 $H_1$ 和 $H_2$ 称为间隔边界。
在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解；但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用，所以将这种分类模型称为支持向量机。支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。
为了求解线性可分支持向量机的最优化问题式1~式2，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，就是线性可分支持向量机的对偶算法（dual algorithm）。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。
构建拉格朗日函数。为此，对每一个不等式引进拉格朗日乘子 $\alpha_i \ge 0, i=1,2,...,N$ ，定义拉格朗日函数：
$L(\omega, b, \alpha) = \frac{1}{2}\mid \mid \omega \mid\mid^2 - \sum_{i=1}^N \alpha_iy_i(\omega \cdot x_i + b) + \sum_{i=1}^N \alpha_i$
其中， $\alpha = (\alpha_1, \alpha_2,...,\alpha_N)^T$ 为拉格朗日乘子向量。
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
$max_\alpha \ min_{\omega, b} \ L(\omega, b, \alpha)$
1>> 求 $min_{\omega, b}\ L(\omega, b, \alpha)$
将拉格朗日函数 $L(\omega, b, \alpha)$ 分别对 $\omega, b$ 求偏导并令其等于 0
$\nabla_\omega L(\omega, b, \alpha) = \omega - \sum_{i=1}^N \alpha_i y_i x_i = 0 \\ \nabla_b L(\omega, b, \alpha) = -\sum_{i=1}^N \alpha_i y_i = 0$
得
$\omega = \sum_{i=1}^N \alpha_i y_i x_i \\ \sum_{i=1}^N \alpha_i y_i = 0$
将以上公式代入拉格朗日函数中，得
$\begin{array} \ L(\omega, b, \alpha) & = & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j) \cdot x_i + b) + \sum_{i=1}^N \alpha_i \\ & = & -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i \end{array}$
即
$min_{\omega, b} \ L(\omega, b, \alpha) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i$

2>> 求 $min_{\omega, b} \ L(\omega, b, \alpha)$ 对 $\alpha$ 的极大，即是对偶问题
$\begin{array} \ max_\alpha & -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N\alpha_iy_i = 0 \\ & \alpha_i \ge 0, \ \ \ \ \ \ i=1,2,...,N \end{array}$
将上式得目标函数由求极大转换成求极小，就得到下面与之等价的对偶最优化问题：
$\begin{array} \ min_\alpha & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N\alpha_iy_i = 0 \\ & \alpha_i \ge 0, \ \ \ \ \ \ i=1,2,...,N \end{array}$
对线性可分训练数据集，假设对偶最优化问题对 $\alpha$ 的解为 $\alpha^*=(\alpha_1^*, \alpha_2^*,...,\alpha_N^*)^T$ ，可以由 $\alpha^*$ 求得原始最优化问题对 $(\omega, b)$ 的解 $\omega^*, b^*$
设 $\alpha^*=(\alpha_1^*, \alpha_2^*,...,\alpha_N^*)^T$ 是以上对偶问题的解，则存在下标 $j$ ，使得 $\alpha_j^* \gt 0$ 并可按下式求得原始最优化问题的解 $\omega^*, b^*$ ：
$\omega^* = \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)$
证明： 由 $\omega^*,b^*,\alpha^*$ 是原始问题和对偶问题的解，满足 KKT 条件，可得
$\begin{array} \nabla_\omega L(\omega^*,b^*,\alpha^*) = \omega^* - \sum_{i=1}^N \alpha_i^* y_i x_i = 0\\ \nabla_b L(\omega^*,b^*,\alpha^*) = -\sum_{i=1}^N \alpha_i^* y_i = 0 \\ \alpha_i^*(y_i(\omega^* \cdot x_i + b^*) - 1) = 0, \ \ \ \ \ i=1,2,...,N \\ yi(\omega^* \cdot x_i + b^*) - 1 \ge 0, \ \ \ \ \ i=1,2,...,N \\ a_i^* \ge 0, \ \ \ \ \ i=1,2,...,N \\ \end{array}$
由此得
$\omega^* = \sum_{i=1}^N \alpha_i^* y_i x_i \\$
其中至少有一个 $a_j^* \gt 0$ （用反证法，假设 $\alpha^*＝0$ ，可得 $\omega^*＝0$ ，而 $\omega^*＝0$ 不是原始最优化问题的解，产生矛盾），对此 $j$ 有
$y_j(\omega^* \cdot x_j + b^*) - 1 = 0$
将 $\omega^* = \sum_{i=1}^N \alpha_i^* y_i x_i \\$ 代入此式，且 $y_j^2=1$ ，可得
$b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i(x_i \cdot x_j)$
由此定理可知，分离超平面可以写成
$\sum_{i=1}^N \alpha_i^*y_i(x\cdot x_i) + b^* = 0$
分类决策函数可以写成
$f(x) = sign(\sum_{i=1}^N \alpha_i^*y_i(x\cdot x_i) + b^*)$
这就是数，分类决策函数只依赖于输入 $x$ 和训练样本输入的内积。 分类决策函数称为线性可分支持向量机的对偶形式。这种求得分离超平面及分类决策函数的算法，称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。
在线性可分支持向量机中，以上推导可知， $\omega^*$ 和 $b^*$ 只依赖于训练数据中对应于 $\alpha_i^*>0$ 的样本点 $(x_i, y_i)$ ，而其他样本点对 $\omega^*$ 和 $b^*$ 没有影响。我们将训练数据中对应于 $\alpha_i^*>0$ 的实例点 $x_i \in R^n$ 称为支持向量。

线性支持向量机与软间隔最大化

线性不可分意味着某些样本点 $(x_i,y_i)$ 不能满足函数间隔大于等于 1 的约束条件。为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\xi_i \ge 0$ ，使函数间隔加上松弛变量大于等于 1。这样，约束条件变为
$y_i(\omega \cdot x_i + b) \ge 1- \xi_i$
同时，对每一个松弛变量 $\xi_i$ ，支付一个代价 $\xi_i$ 。目标函数由原来的 $\frac{1}{2}\mid\mid \omega \mid\mid^2$ 变成
$\frac{1}{2} \mid\mid \omega\mid\mid^2 + C\sum_{i=1}^N\xi_i$
这里， $C \gt 0$ 称为惩罚参数，一般由应用问题决定， $C$ 值大时对误分类的惩罚增大， $C$ 值小时对误分类的惩罚减小。最小化目标函数包含两层含义：使 $\frac{1}{2}\mid\mid \omega\mid\mid^2$ 尽量小即间隔尽量大，同时使误分类点的个数尽量小， $C$ 是调和二者的系数。相应于硬间隔最大化，它称为软间隔最大化。
线性不可分的线性支持向量机的学习问题变成如下凸二次规划（convex quadratic programming）问题（原始问题）：
$\begin{array} \ min_{\omega, b, \xi} & \frac{1}{2} \mid\mid \omega\mid\mid^2 + C\sum_{i=1}^N\xi_i \\ s.t. & y_i(\omega \cdot x_i + b) \ge 1- \xi_i, \ \ \ \ \ i=1,2,...,N \\ & \xi_i \ge 0, \ \ \ \ \ i=1,2,...,N \end{array}$
原始问题是一个凸二次规划问题，因而关于 $(\omega,b,\xi)$ 的解是存在的。可以证明 $\omega$ 的解是唯一的，但 $b$ 的解不唯一， $b$ 的解存在于一个区间。
对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大化问题，得到的分离超平面为
$\omega^* \cdot x + b^* = 0$
以及相应的分类决策函数
$f(x) = sign(\omega^* \cdot x + b^* )$
称为线性支持向量机。
原始问题的对偶问题是
$\begin{array} \ min_\alpha & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^N\alpha_i \\ s.t. & \sum_{i=1}^N\alpha_iy_i = 0 \\ & 0\le \alpha_i \le C, \ \ \ \ \ i=1,2,...,N \end{array}$
证明：
原始最优化问题的拉格朗日函数是
$L(\omega, b,\xi, \alpha, \mu) = \frac{1}{2} \mid\mid \omega\mid\mid^2 + C\sum_{i=1}^N\xi_i - \sum_{i=1}^N \alpha_i(y_i(\omega \cdot x_i + b) - 1 + \xi_i) - \sum_{i=1}^N \mu_i\xi_i$
其中 $\alpha_i \ge 0$ ， $\mu_i \ge 0$ 。
对偶问题是拉格朗日函数的极大极小问题。首先求 $L(\omega, b,\xi, \alpha, \mu)$ 对 $\omega, b, \xi$ 的极小，由
$\begin{array} \ \nabla_\omega L(\omega, b,\xi, \alpha, \mu) = \omega - \sum_{i=1}^N\alpha_iy_ix_i = 0 \\ \nabla_b L(\omega, b,\xi, \alpha, \mu) = - \sum_{i=1}^N\alpha_iy_i = 0 \\ \nabla_{\xi_i} L(\omega, b,\xi, \alpha, \mu) = C - \alpha_i - \mu_i = 0 \\ \end{array}$
得
$\begin{array} \ \omega = \sum_{i=1}^N \alpha_iy_ix_i \\ \sum_{i=1}^N \alpha_iy_i = 0 \\ C - \alpha_i - \mu_i = 0 \end{array}$
代入拉格朗日函数，得
$\begin{array} \ min_{\omega, b , \xi} & L(\omega, b,\xi, \alpha, \mu) = - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^N\alpha_i \\ \end{array}$
再对 $min_{\omega, b , \xi} \ \ L(\omega, b,\xi, \alpha, \mu)$ 求 $\alpha$ 的极大，即得对偶问题：
$\begin{array} \ max_\alpha & - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^N\alpha_i \\ s.t. & \sum_{i=1}^N \alpha_iy_i = 0 \\ & C - \alpha_i - \mu_i = 0 \\ & \alpha_i \ge 0 \\ & \mu_i \ge 0, \ \ \ \ \ i=1,2,...,N \end{array}$
将以上对偶最优化问题进行变换，得到需要证明的对偶问题，得证。
设 $\alpha^* = (\alpha_1^*, \alpha_2^*,...,\alpha_N^*)^T$ 是对偶问题的一个解，若存在 $\alpha_j^*$ ， $0\lt a_j^*\lt C$ ，则原始问题的解 $\omega^*, b^*$ 可按下式求得：
$\begin{array} \ \omega^* = \sum_{i=1}^N\alpha_i^*y_ix_i \\ b^* = y_i - \sum_{i=1}^Ny_i\alpha_i^*(x_i \cdot x_j) \end{array}$
证明：
原始问题是凸二次规划问题，其解满足KKT条件。即得
$\begin{array} \ \nabla_\omega L(\omega^*, b,^*\xi^*, \alpha^*, \mu^*) = \omega^* - \sum_{i=1}^N\alpha_i^*y_ix_i = 0 \\ \nabla_b L(\omega^*, b,^*\xi^*, \alpha^*, \mu^*) = - \sum_{i=1}^N\alpha_i^*y_i = 0 \\ \nabla_{\xi_i} L(\omega^*, b,^*\xi^*, \alpha^*, \mu^*) = C - \alpha_i^* - \mu_i^* = 0 \\ \alpha_i^*(y_i(\omega^* + b^*) -1 + \xi_i^*) = 0 \\ \mu_i^*\xi_i^* = 0 \\ y_i(\omega^* + b^*) -1 + \xi_i^* \ge 0 \\ \xi_i^* \ge 0 \\ \alpha_i^* \ge 0 \\ \mu_i^* \ge 0, \ \ \ \ \ i=1,2,...,N \\ \end{array}$
可知， $\omega^* = \sum_{i=1}^N\alpha_i^*y_ix_i$ 成立。若存在 $0 \lt a_j^* \lt C$ ,可知 $\mu_i^* \gt 0$ ，可知 $\xi_i^* = 0$ ，可知 $y_i(\omega^* + b^*) -1 = 0$ ，再由 $y_i^2 = 1$ ，可得 $b^* = y_i - \sum_{i=1}^Ny_i\alpha_i^*(x_i \cdot x_j)$ ，得证。
对任一适合条件 $0<\alpha_j^*<C$ 的，都可求出 $b^*$ 。可见原始问题对 $b$ 的解并不唯一，所以实际计算时可以取在所有符合条件的样本点上的平均值。
在线性不可分的情况下，将对偶问题的解 $\alpha^* = (\alpha_1^*, \alpha_2^*,...,\alpha_N^*)^T$ 中对应于 $\alpha_i \gt 0$ 的样本点 $(x_i,y_i)$ 的实例 $x_i$ 称为支持向量（软间隔的支持向量）。如下图所示，分离超平面由实线表示，间隔边界由虚线表示，正例点由“○”表示，负例点由“×”表示。图中还标出了实例 $x_i$ 到间隔边界的距离 $\frac{\xi_i}{\mid\mid \omega \mid\mid}$ 。

软间隔的支持向量 $x_i$ 或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。若 $\alpha_i^* \lt C$ ，则 $\xi_i＝0$ ，支持向量 $x_i$ 恰好落在间隔边界上；若 $\alpha_i^*＝C$ ， $0 \lt \xi_i \lt 1$ ，则分类正确， $x_i$ 在间隔边界与分离超平面之间；若 $\alpha_i^*＝C$ ， $\xi_i＝1$ ，则xi在分离超平面上；若 $\alpha_i^*＝C$ ， $\xi_i>1$ ，则 $x_i$ 位于分离超平面误分一侧。

线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：
$\sum_{i=1}^N[1-y_i(\omega \cdot x_i + b)]_+ + \lambda \mid\mid \omega \mid\mid^2$
目标函数的第一项是经验损失或经验风险，函数
$L(y(\omega\cdot x + b)) = [1- y(\omega\cdot x + b)]_+$
称为合页损失函数（hinge loss function）。下标“＋”表示以下取正值的函数。
$[z]_+ = \begin{cases} z, \ \ \ \ \ z \gt 0 \\ 0, \ \ \ \ \ z \le 0 \end{cases}$
这就是说，当样本点 $(x_i,y_i)$ 被正确分类且函数间隔（确信度） $y_i(\omega \cdot x_i+b)$ 大于 1 时，损失是 0，否则损失是 $1-y_i(\omega \cdot x_i+b)$ ，注意到在上图中的实例点 $x_4$ 被正确分类，但损失不是 0。目标函数的第二项是系数为 $\lambda$ 的 $\omega$ 的 L2 范数，是正则化项。

线性支持向量机原始最优化问题：
$\begin{array} \ min_{\omega, b, \xi} & \frac{1}{2}\mid\mid \omega \mid\mid^2 + C\sum_{i=1}^N\xi_i \\ s.t. & y_i(\omega\cdot x_i + b) \ge 1 - \xi_i，\ \ \ \ \ i = 1,2,...,N \\ & \xi_i \ge 0, \ \ \ \ \ i = 1,2,...,N \end{array}$
等价于最优化问题
$\begin{array} \ min_{\omega, b} & \sum_{i=1}^N[1-y_i(\omega \cdot x_i + b)]_+ + \lambda \mid\mid \omega \mid\mid^2 \end{array}$
证明：
令 $1-y_i(\omega\cdot x_i + b)=\frac{1}{2}\xi_i$ ， $\xi_i \ge 0$ ，则 $y_i(\omega\cdot x_i + b)=1-\frac{1}{2}\xi_i\ge 1-\xi_i$ ，于是 $\omega, b, \xi$ 满足约束条件。由 $\xi_i \ge 0$ 可知， $[1-y_i(\omega\cdot x_i + b)]_+=[\frac{1}{2}\xi_i]_+=\frac{1}{2}\xi_i$ ，所以最优化问题可写成
$\begin{array} \ min_{\omega, b} & \sum_{i=1}^N\frac{1}{2}\xi_i + \lambda\mid\mid \omega \mid\mid^2 \end{array}$
取 $\lambda = \frac{1}{4C}$ ，则
$\begin{array} \ min_{\omega, b} & \frac{1}{2C}(C\sum_{i=1}^N\xi_i + \frac{1}{2}\mid\mid \omega \mid\mid^2) \end{array}$
与原始最优化问题目标函数等价。

非线性支持向量机与核函数

非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。
设原空间为 $X\subset R^2$ ， $x=(x^{(1)},x^{(2)})^T \in X$ ，新空间为 $Z \subset R^2$ ， $z=(z^{(1)}, z^{(2)})^T \in Z$ ，定义从原空间到新空间的变换（映射）：
$z = \emptyset(x) = ((x^{(1)})^2, (x^{(2)})^2)^T$
经过变换 $z=\emptyset(x)$ ，原空间 $X\subset R^2$ 变换为新空间 $Z \subset R^2$ ，原空间中的点相应地变换为新空间中的点。假设原空间的椭圆
$\omega_1(x^{(1)})^2 + \omega_2(x^{(2)})^2 + b = 0$
变换为新空间的直线
$\omega_1z^{(1)} + \omega_2z^{(2)} + b = 0$
在变换后的新空间里，直线 $\omega_1z^{(1)} + \omega_2z^{(2)} + b = 0$ 可以将变换后的正负实例点正确分开。这样，原空间的非线性可分问题就变成了新空间的线性可分问题。
用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。
设 $X$ 是输入空间（欧氏空间 $R^n$ 的子集或离散集合），又设 $H$ 为特征空间（希尔伯特空间），如果存在一个从 $X$ 到 $H$ 的映射
$\emptyset(x): X\rightarrow H$
使得对所有 $x,z \in X$ ，函数 $K(x,z)$ 满足条件
$K(x,z) = \emptyset(x) \cdot \emptyset(z)$
则称 $K(x,z)$ 为核函数， $\emptyset(x)$ 为映射函数。
核技巧的想法是，在学习与预测中只定义核函数 $K(x,z)$ ，而不显式地定义映射函数 $\emptyset$ 。通常，直接计算 $K(x,z)$ 比较容易，而通过 $\emptyset(x)$ 和 $\emptyset(z)$ 计算 $K(x,z)$ 并不容易。注意， $\emptyset$ 是输入空间 $R^n$ 到特征空间 $H$ 的映射，特征空间 $H$ 一般是高维的，甚至是无穷维的。可以看到，对于给定的核 $K(x,z)$ ，特征空间 $H$ 和映射函数 $\emptyset$ 的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。
在核函数 $K(x,z)$ 给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。
例如：在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中的内积 $x_i\cdot x_j$ 可以用核函数 $K(x_i，x_j)＝\emptyset(x_i)\cdot \emptyset(x_j)$ 来代替。此时对偶问题的目标函数成为
$W(\alpha) = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^N\alpha_i$
同样，分类决策函数中的内积也可以用核函数代替，而分类决策函数成为
$f(x) = sign(\sum_{i=1}^{N_s}\alpha_i^*y_i \emptyset(x_i)\emptyset(x) + b^*) = sign(\sum_{i=1}^{N_s}\alpha_i^*y_i K(x_i,x) + b^*)$
这等价于经过映射函数 $\emptyset$ 将原来的输入空间变换到一个新的特征空间，将输入空间中的内积 $x_i\cdot x_j$ 变换为特征空间中的内积 $\emptyset(x_i)\cdot \emptyset(x_j)$ ，在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。
通常所说的核函数就是正定核函数（positive definite kernel function）。
正定核太难理解，等知识完备后，再来回顾
设 $K: X\times X \rightarrow R$ 是对称函数，则 $K(x,z)$ 为正定核函数的充要条件是对任意 $x_i \in X$ ， $i=1,2,...,m$ ， $K(x,z)$ 对应的 Gram 矩阵：
$K = [K(x_i, x_j)]_{m \times m}$
是半正定矩阵，此时则称 $K(x,z)$ 是正定核。
多项式核函数
$K(x,z) = (x\cdot z + 1)^ p$
对应的支持向量机是一个 $p$ 次多项式分类器。在此情行下，分类决策函数成为
$f(x) = sign(\sum_{i=1}^{N_s}\alpha_i^*y_i (x_i \cdot x + 1)^p + b^*)$
高斯核函数
$K(x,z) = exp(-\frac{\mid\mid x - z \mid\mid^2}{2\sigma^2})$
对应的支持向量机是高斯径向基函数（radial basis function）分类器。在此情形下，分类决策函数成为
$f(x) = sign(\sum_{i=1}^{N_s}\alpha_i^*y_i exp(-\frac{\mid\mid x - z \mid\mid^2}{2\sigma^2}) + b^*)$
字符串核函数（跳过）
将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数。
非线性支持向量机学习算法
输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i \in X = R^n$ ， $y_i \in Y = \{-1, +1\}$ ， $i=1,2,...,N$ ；
输出：分类决策函数。

1>> 选取适当的核函数 $K(x, z)$ 和适当的参数 $C$ ，构造并求解最优化问题
$\begin{array} \ min_\alpha & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i, x_j) - \sum_{i=1}^N\alpha_i \\ s.t. & \sum_{i=1}^N\alpha_iy_i = 0 \\ & 0 \le \alpha_i \le C, \ \ \ \ \ i=1,2,...,N \end{array}$
求得最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$ 。
2>> 选择 $\alpha^*$ 的一个正分量 $0 \lt \alpha_j^* \lt C$ ，计算
$b^* = y_j -\sum_{i=1}^N\alpha^*y_iK(x_i , x_j)$
3>> 构造决策函数
$f(x) = sign(\sum_{i=1}^N\alpha_i^*y_i K(x_i,x) + b^*)$
当 $K(x,z)$ 是正定核函数时，以上问题是凸二次规划问题，解是存在的。

序列最小最优化算法

序列最小最优化算法简称 SMO 算法，SMO 算法要解如下凸二次规划问题的对偶问题：
$\begin{array} \ min_\alpha & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i, x_j) - \sum_{i=1}^N\alpha_i \\ s.t. & \sum_{i=1}^N\alpha_iy_i = 0 \\ & 0 \le \alpha_i \le C, \ \ \ \ \ i=1,2,...,N \end{array}$
在这个问题中，变量是拉格朗日乘子，一个变量 $\alpha_i$ 对应于一个样本点 $(x_i,y_i)$ ；变量的总数等于训练样本容量 $N$ 。
SMO 算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的 KKT 条件（Karush-Kuhn-Tucker conditions），那么这个最优化问题的解就得到了。因为 KKT 条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反 KKT 条件最严重的那一个，另一个由约束条件自动确定。如此， SMO 算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
注意，子问题的两个变量中只有一个是自由变量。假设 $\alpha_1$ ， $\alpha_2$ 为两个变量， $\alpha_3,\alpha_4,…,\alpha_N$ 固定，那么由等式约束 $\sum_{i=1}^N\alpha_iy_i = 0$ 可知
$\alpha_1 = -y_1 \sum_{i=2}^N\alpha_iy_i$
如果 $\alpha_2$ 确定，那么 $\alpha_1$ 也随之确定。所以子问题中同时更新两个变量。
假设选择两个变量是 $\alpha_1, \alpha_2$ ，其他变量 $\alpha_i(i=3,4,...,N)$ 是固定的。于是 SMO 的最优化问题的子问题可以写成：
$\begin{array} \ min_{\alpha_1,\alpha_2} & W(\alpha_1, \alpha_2) = \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2}K_{22}\alpha_2^2 + y_iy_2K_{12}\alpha_1\alpha_2-(\alpha_1 + \alpha_2) + y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1} + y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2} \\ s.t. & \alpha_1y_1 + \alpha_2y_2 = -\sum_{i=3}^Ny_i\alpha_i = \xi \ \ \ \ \ \ (1)\\ & 0 \le \alpha_i \le C, \ \ \ \ \ i=1,2, \ \ \ \ \ (2) \end{array}$
其中， $K_{ij} = K(x_i, x_j), \ \ i,j = 1,2,...,N$ ， $\xi$ 是常数，式中省略了不含 $\alpha_i, \alpha_j$ 的常数项。
由于只有两个变量 $(\alpha_1, \alpha_2)$ ，约束可以用二维空间中的图形表示

不等式约束 $(1)$ 使得 $(\alpha_1, \alpha_2)$ 在盒子 $[0,C]\times [0,C]$ 内，等式约束 $(2)$ 使得 $(\alpha_1, \alpha_2)$ 在平行于盒子的对角线的直线上。因此要求的是目标函数在一条平行于对角线的线段上的最优值。这使得两个变量的最优化问题成为实质上的单变量的最优化问题，不妨考虑为变量 $\alpha_2$ 的最优化问题。
假设最优化问题的初始可行解是 $\alpha_1^{old}, \alpha_2^{old}$ ，最优解为 $\alpha_1^{new}, \alpha_2^{new}$ ，并且假定在沿着约束方向未经剪辑时 $\alpha_2$ 的最优解 $\alpha_2^{new,unc}$ ，未经剪辑的最优解即未考虑约束约束条件时的最优解。

由于 $\alpha_2^{new}$ 需满足不等式约束 $(2)$ ，所以最优值 $\alpha_2^{new}$ 的取值范围必须满足条件
$L \le \alpha_2^{new} \le H$
其中， $L$ 与 $H$ 是 $\alpha_2^{new}$ 所在对角线段端点的界。如果 $y_1 \neq y_2$ ，则
$L = max(0, \alpha_2^{old} - \alpha_1^{old}) \\ H = min(C, C + \alpha_2^{old} - \alpha_1^{old})$
如果 $y_1 = y_2$ ，则
$L = max(0, \alpha_2^{old} + \alpha_1^{old} - C) \\ H = min(C, C + \alpha_2^{old} + \alpha_1^{old})$
下面，首页求沿着约束方向未经剪辑即未考虑不等式约束时 $\alpha_2$ 的最优解 $\alpha_2^{new,unc}$ ；然后再求剪辑后的 $\alpha_2$ 的解 $\alpha_2^{new}$ 。记
$g(x) = \sum_{i=1}^N \alpha_iy_iK(x_i, x) + b$
令
$E_i = g(x_i) - y_i = (\sum_{j=1}^N \alpha_jy_jK(x_j, x_i) + b) - y_i, \ \ \ \ \ i = 1,2$
当 $i=1,2$ 时， $E_i$ 为函数 $g(x)$ 对输入 $x_i$ 的预测值与真实输出 $y_i$ 之差。
定义最优化问题沿着约束方向未经剪辑时得解是
$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}$
其中，
$\eta = K_{11} + K_{22} - 2K_{12} = \mid\mid \emptyset(x_1) -\emptyset(x_2)\mid\mid^2$
$\emptyset(x)$ 是输入空间到特征空间的映射。
经剪辑后的 $\alpha_2$ 的解是
$\alpha_2^{new} = \begin{cases} H, \ \ \ \ \ \alpha_2^{new,unc} \gt H \\ \alpha_2^{new,unc}, \ \ \ \ \ L \le \alpha_2^{new,unc} \le H \\ L, \ \ \ \ \ \alpha_2^{new,unc} \lt L \end{cases}$
由 $\alpha_2^{new}$ 求得 $\alpha_1^{new}$ 是
$\alpha_1^{new} = \alpha_1^{old} + y_1y_2(\alpha_2^{old} - \alpha_2^{new})$
证明：
引进记号
$v_i = \sum_{j=3}^N\alpha_jy_jK(x_i,x_j) = g(x_i) - \sum_{j=1}^2\alpha_jy_jK(x_i,x_j) - b, \ \ \ \ \ i = 1,2$
目标函数可以写成
$W(\alpha_1, \alpha_2) = \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2}K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 - (\alpha_1 + \alpha_2) + y_1v_1\alpha_1 + y_2v_2\alpha_2$
由于 $\alpha_1y_1 = \xi -\alpha_2y_2$ 及 $y_i^2=1$ ，可将 $\alpha_1$ 表示为
$\alpha_1 = (\xi - y_2\alpha_2)y_1$
代入上述目标函数，得到的只是 $\alpha_2$ 的函数的目标函数
$W(\alpha_2) = \frac{1}{2}K_{11}(\xi - \alpha_2y_2)^2 + \frac{1}{2}K_{22}\alpha_2^2 + y_2K_{12}(\xi-\alpha_2y_2)\alpha_2 - (\xi - \alpha_2y_2)y_1 - \alpha_2 + v_1(\xi - \alpha_2y_2) + y_2v_2\alpha_2$
对 $\alpha_2$ 求导
$\frac{\partial W}{\partial \alpha_2} = K_{11}\alpha_2 + K_{22}\alpha_2 - 2K_{12}\alpha_2 - K_{11}\xi y_2 + K_{12}\xi y_2 + y_1y_2 - 1 - v_1y_2 + y_2v_2$
令其为 0，得
$\begin{array} \ (K_{11} + K_{22} - 2K_{12}) \alpha_2 & = & y_2(y_2 - y_1 + \xi K_{11} - \xi K_{12} + v_1 - v_2) \\ & = & y_2[y_2 -y_1 + \xi K_{11} - \xi K_{12} + (g(x_1) - \sum_{j=1}^2y_j\alpha_jK_{1j} - b) - (g(x_2) - \sum_{j=1}^2y_j\alpha_jK_{2j} - b) \end{array}$
将 $\xi = \alpha_1^{old}y_1 + \alpha_2^{old}y_2$ 代入，得到
$\begin{array} \ (K_{11} + K_{22} - 2K_{12}) \alpha_2^{new,unc} & = & y_2((K_{11} + K_{22} -2K_{12})\alpha_2^{old}y_2 + y_2 -y_1 + g(x_1) - g(x_2)) \\ & = & (K_{11} + K_{22} -2K_{12})\alpha_2^{old} + y_2(E_1 - E_2) \end{array}$
将 $\eta = K_{11} + K_{22} - 2K_{12}$ 代入，于是得到
$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}$
要使其满足不等式约束必须将其限制在区间 $[L，H]$ 内，从而得到 $\alpha_2^{new}$ 的表达式。由等式约束，得到 $\alpha_1^{new}$ 的表达式。于是得到最优问题的解 $(\alpha_1^{new}, \alpha_2^{new})$ 。

SMO 算法在每个子问题中选择两个变量优化，其中至少一个变量是违反 KKT 条件的。
SMO 称选择第 1 个变量的过程为外层循环。外层循环在训练样本中选取违反 KKT 条件最严重的样本点，并将其对应的变量作为第 1 个变量。具体地，检验训练样本点 $(x_i，y_i)$ 是否满足 KKT 条件，即
$\alpha_i = 0 \Leftrightarrow y_ig(x_i) \ge 1 \\ 0 \lt \alpha_i \lt C \Leftrightarrow y_ig(x_i) = 1 \\ a_i = C \Leftrightarrow y_ig(x_i) \le 1$
其中， $g(x_i) = \sum_{j=1}^N\alpha_jy_jK(x_j,x_i) + b$
该检验是在 $\varepsilon$ 范围内进行的。在检验过程中，外层循环首先遍历所有满足条件 $0<\alpha_i<C$ 的样本点，即在间隔边界上的支持向量点，检验它们是否满足 KKT 条件。如果这些样本点都满足 KKT 条件，那么遍历整个训练集，检验它们是否满足 KKT 条件。
SMO 称选择第 2 个变量的过程为内层循环。假设在外层循环中已经找到第 1 个变量 $\alpha_1$ ，现在要在内层循环中找第 2 个变量 $\alpha_2$ 。第 2 个变量选择的标准是希望能使 $\alpha_2$ 有足够大的变化。

由上述笔记可知， $\alpha_2^{new}$ 是依赖于 $\mid E_1 - E_2 \mid$ 的，为了加快计算速度，一种简单的做法是选择 $\alpha_2$ ，使其对应的 $\mid E_1 - E_2 \mid$ 最大。因为 $\alpha_1$ 已定， $E_1$ 也确定了。如果 $E_1$ 是正的，那么选择最小的 $E_i$ 作为 $E_2$ ；如果 $E_1$ 是负的，那么选择最大的 $E_i$ 作为 $E_2$ 。为了节省计算时间，将所有 $E_i$ 值保存在一个列表中。

在特殊情况下，如果内层循环通过以上方法选择的 $\alpha_2$ 不能使目标函数有足够的下降，那么采用以下启发式规则继续选择 $\alpha_2$ 。遍历在间隔边界上的支持向量点，依次将其对应的变量作为 $\alpha_2$ 试用，直到目标函数有足够的下降。若找不到合适的 $\alpha_2$ ，那么遍历训练数据集；若仍找不到合适的 $\alpha_2$ ，则放弃第 1 个 $\alpha_1$ ，再通过外层循环寻求另外的 $\alpha_1$ 。
在每次完成两个变量优化后，都要重新计算阈值 $b$ 。当 $0 \lt \alpha_1^{new} \lt C$ 时，由 $KKT$ 条件可知
$\sum_{i=1}^N \alpha_iy_iK_{i1} + b = y_i$
于是
$b_1^{new} = y_1 - \sum_{i=3}^N\alpha_iy_iK_{i1} - \alpha_1^{new}y_1K_{11} - \alpha_2^{new}y_2K_{21}$
由 $E_1$ 的定义式有
$E_1 = \sum_{i=3}^N\alpha_iy_iK_{i1} + \alpha_1^{old}y_iK_{11} + \alpha_2^{old}y_2K_{21} + b^{old} -y_1$
可得
$y_1 - \sum_{i=3}^N\alpha_iy_iK_{i1} = -E_1 + \alpha_1^{old}y_1K_{11} + \alpha_2^{old}y_2K_{21} + b^{old}$
代入 $b_1^{new}$ 公式得
$b_1^{new} = -E_1 - y_1K_{11}(\alpha_1^{new} - \alpha_1^{old}) -y_2K_{21}(\alpha_2^{new} - \alpha_2^{old}) + b^{old}$
同样，如果 $0 \lt \alpha_2^{new} \lt C$ ，那么
$b_2^{new} = -E_2 - y_1K_{12}(\alpha_1^{new} - \alpha_1^{old}) -y_2K_{22}(\alpha_2^{new} - \alpha_2^{old}) + b^{old}$
如果 $\alpha_1^{new}, \alpha_2^{new}$ 同时满足条件 $0 \lt \alpha_1^{new} \lt C , \ \ i=1,2$ ,那么 $b_1^{new} = b_2^{new}$ 。如果 $\alpha_1^{new},\alpha_2^{new}$ 是 $0$ 或者 $C$ ，那么 $b_{new}$ 和 $b_2^{new}$ 以及它们之间的数都是符合 KKT 条件的阈值，这时选择它们的中点作为 $b^{new}$ 。

在每次完成两个变量的优化之后，还必须更新对应的 $E_i$ 值，并将它们保存在列表中。 $E_i$ 值的更新要用到 $b^{new}$ 值，以及所有支持向量对应的 $\alpha_j$ ：
$E_i^{new} = \sum_Sy_j\alpha_jK(x_i,x_j) + b^{new} - y_i$
其中， $S$ 是所有支持向量 $x_j$ 的集合。

支持向量机

线性可分支持向量机与硬间隔最大化

线性支持向量机与软间隔最大化

非线性支持向量机与核函数

序列最小最优化算法

猜你喜欢

热点阅读