支持向量机

支持向量机乃至线性分类器都起源于 $logistic$ 回归， $logistic$ 回归目的是从特征学习出一个 $0/1$ 分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用 $logistic$ 函数（或称作 $sigmoid$ 函数）将自变量映射到 $0/1$ 上，映射后的值被认为是属于 $y=1$ 的概率。

硬边距支持向量机

函数间隔与几何间隔

一般来说，一个点距离分类超平面的远近可以表示分类预测的确信程度，在超平面 $w·x+b=0$ 确定的情况下，$|w·x + b|$ 能够 相对 的表示点 $x$ 距离超平面的远近，而 $w·x + b$ 的符号与类别标记 $y$ 的符号一致就表示分类正确。

函数间隔

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

$$ \hat \gamma_i = y_i(w·x_i+b) $$

为了使函数间隔最大（更大的信心确定该例是正例还是反例），当 $y_i\gt0$ 时，$(w·x_i+b)$ 应该是个大正数，反之是个大负数。因此 函数间隔代表了我们认为特征是正例还是反例的确信度 。

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

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

继续考虑 $(w,b)$ ，如果同时加大 $w$ 和 $b$，比如在 $(w·x_i+b)$ 前面乘个系数比如 $2$，那么所有点的函数间隔都会增大二倍，这个对求解问题来说不应该有影响，因为我们要求解的超平面是 $(w·x_i+b)=0$。这样，我们为了限制 $w$ 和 $b$，可能需要加入归一化条件，因为求解的目标是确定唯一的 $w$ 和 $b$，而不是多组线性相关的向量。

几何间隔

假设我们有了 $B$ 点所在的 $(wx_i+b)=0$ 的分割面，$A$ 到该面的距离可以用 $\gamma_i$ 表示，假设 $B$ 就是 $A$ 在分割面上的投影，我们知道 $BA$ 的方向为 $w$，单位向量为 $\frac w {||w||}$，记 $\gamma_i = |AB|$，根据点到直线的距离公式：

$$ \gamma_i = \frac {w· x_i+b} {||w||} = \frac w {||w||}·x_i + \frac b {||w||} $$

换一种更一般的写法：

$$ \gamma_i = y_i \left(\frac w {||w||}·x_i + \frac b {||w||}\right) $$

上式就是几何间隔的形式，显然，函数间隔和集合间隔满足：

$$ \gamma = \frac {\hat \gamma} {||w||} $$

当 $||w||=1$ 时，几何间隔和函数间隔相等，所以当 $w$ 和 $b$ 成比例变化时，超平面外的点函数函数间隔也会成比例变化，而几何间隔不变。

支持向量机间隔最大化

间隔最大化的直观解释就是：对训练数据集找到 几何间隔 最大的超平面意味着以充分大的确信度意味着对训练数据进行分类，考虑求一个几何间隔最大的分类超平面：

$$ \max_{w, b} \gamma

\\ s.t. \;\; y_i \left(\frac w {||w||}·x_i + \frac b {||w||}\right) \ge \gamma，i=1,2,…N $$

其中 $\gamma$ 训练集中几何间隔的最小值，即支持向量对应的几何间隔。

考虑几何间隔和函数间隔的关系，可以改写为：

$$ \max_{w, b} \frac {\hat \gamma} {||w||}

\\ s.t. \;\; y_i(w·x_i+b) \ge \hat \gamma，i=1,2,…N $$

函数间隔 $\hat \gamma$ 对目标函数的优化没有任何影响，所以我们可以令 $\hat \gamma =1$，而最大化 $\frac 1 {||w||}$ 和最小化 $\frac 1 2 ||w||^2$ 也是等价的，于是就有：

$$ \min_{w, b} \frac 1 2 ||w||^2

\\ s.t. \;\; y_i(w·x_i+b) -1 \ge 0，i=1,2,…N $$

线性可分支持向量机

硬边距支持向量机又被称作线性可分支持向量机，其原始优化问题：

$$ \begin{align} \min_{w, b} &\;\; \frac 1 2 ||w||^2 \nonumber

\\ s.t. & \;\; y_i(w·x_i+b) -1 \ge 0，i=1,2,…N \nonumber \end{align}$$

对偶优化问题：

$$ \begin{align} \min_{\alpha} &\;\; \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_jy_iy_j \langle x_i, x_j\rangle - \sum_{i=1}^n \alpha_i \nonumber

\\ s.t. &\;\; \sum_{i=1}^n \alpha_i y_i = 0 \nonumber

\\ &\;\; \alpha_i \ge 0,\;i=1,2,…N \nonumber \end{align}$$

求得最优解 $\alpha^*$ 后，最优参数：

$$ w^* = \sum_{i=1}^n \alpha^*_i y_i x_i \\ b^* = y_j - \sum_{i=1}^n \alpha^*_i y_i \langle x_i, x_j\rangle $$

推导：

原问题的拉格朗日函数：

$$ L(w, b, \alpha) = \frac 1 2 ||w||^2 - \sum_{i=1}^n \alpha_iy_i(w·x_i+b) + \sum_{i=1}^n \alpha_i $$

显然：

$$ \frac 1 2 ||w||^2 ≥ L(w, b, \alpha) ≥ \mathop{inf} \limits_{w, b} L(w, b,\alpha)$$

对偶问题是拉格朗日函数的极大极小问题，首先求 $L(w, b, \alpha)$ 对 $w, b,$ 的极小，再求对 $\alpha$ 的极大。

1. 求 $\min_{w, b}L(w, b,\alpha) $

   由：

   $$ \nabla_w L(w, b, \alpha) = w - \sum_{i=1}^n \alpha_iy_ix_i = 0 \\ \nabla_b L(w, b, \alpha) = - \sum_{i=1}^n \alpha_iy_i = 0 $$

   得：

   $$ w = \sum_{i=1}^n \alpha_iy_ix_i \\ \sum_{i=1}^n \alpha_iy_i = 0 $$

   代入易得：

   $$ L(w, b, a) = \sum_{i=1}^n \alpha_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_iy_j \langle x_i, x_j\rangle $$

2. 求 $\min_{w, b}L(w, b,\alpha)$ 对 $\alpha$ 的极大值，即求解对偶问题

   $$ \begin{align} \max_{\alpha} &\;\; - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_jy_iy_j \langle x_i, x_j\rangle + \sum_{i=1}^n \alpha_i \nonumber

   \\ s.t. &\;\; \sum_{i=1}^n \alpha_i y_i = 0 \nonumber

   \\ &\;\; \alpha_i \ge 0,\;i=1,2,…N \nonumber \end{align}$$

   将上式的极大转换成极小问题，就得到最终的对偶最优化问题

   $$ \begin{align} \min_{\alpha} &\;\; \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_jy_iy_j \langle x_i, x_j\rangle - \sum_{i=1}^n \alpha_i \nonumber

   \\ s.t. &\;\; \sum_{i=1}^n \alpha_i y_i = 0 \nonumber

   \\ &\;\; \alpha_i \ge 0,\;i=1,2,…N \nonumber \end{align}$$

3. 参数最优化

   由 $\nabla_w L(w, b, \alpha)$ 得：

$$ w = \sum_{i=1}^n \alpha^*_iy_ix_i $$

根据 $y_j(w^*·x+b^*)-1=0$ 得：

$$ b^* = y_j - \sum_{i=1}^n \alpha^*_i y_i \langle x_i, x_j\rangle $$

其中，$y_j^2=1$。

软边距支持向量机

线性支持向量机

硬边距支持向量机并不适合线性不可分的情况，对于其改进产生了软边距支持向量机，也就是线性支持向量机。对每个样本点 $(x_i,y_i)$ 引入一个松弛变量 $\xi_i \ge 0$，是函数间隔加上松弛变量后大于等于 $1$，这样，就得到软边距支持向量机的原始问题：

$$ \begin{align} \min_{w, b} &\;\; \frac 1 2 ||w||^2 + C\sum_{i=1}^n\xi_i \nonumber

\\ s.t. & \;\; y_i(w·x_i+b) \ge 1-\xi_i,\; i=1,2,…N \nonumber

\\ & \;\;\xi_i \ge 0,\;i=1,2,…Ni \nonumber \end{align}$$

其中，$C\gt0 $ 是惩罚参数，一般来讲，$C$ 值越大，对误分类的惩罚越大，分类器越严格，边距越窄，$C$ 值越小，对误分类的惩罚越小，分类器越宽松，边距越大。目标函数最优化包含两层含义，使 $1/2 ||w||^2$ 尽可能小，也就是说使边距尽可能大，$\xi_i$ 又使误分类点的个数尽可能少，$C$ 就是调和二者的系数。

原问题是一个凸二次规划问题，我们可以通过优化其对偶函数求解：

$$ \begin{align} \min_{\alpha} &\;\; \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_jy_iy_j \langle x_i, x_j\rangle - \sum_{i=1}^n \alpha_i \nonumber

\\ s.t. &\;\; \sum_{i=1}^n \alpha_i y_i = 0 \nonumber

\\ &\;\; 0 \le \alpha_i \le C,\;i=1,2,…N \nonumber \end{align}$$

求得最优解 $\alpha^*$ 后，最优参数：

$$ w^* = \sum_{i=1}^n \alpha^*_i y_i x_i \\ b^* = y_j - \sum_{i=1}^n \alpha^*_i y_i \langle x_i, x_j\rangle $$

对任一适合条件的 $0\le \alpha^*_j \le C$，都有不同的 $b^*$，但是由于原始问题对 $b$ 的解并不唯一，所以在实际计算过程中可以取在所有符合条件的样本点上的平均值。

推导：

原问题的拉格朗日函数：

$$ L(w, b, \xi, \mu, \alpha) = \frac 1 2 ||w||^2 + C \sum_{i=1}^n \xi_i - \sum_{i=1}^n \alpha_i(y_i(w·x_i+b)-1+\xi_i)-\sum_{i=1}^n\mu_i \xi_i$$

显然：

$$ \frac 1 2 ||w||^2 ≥ L(w, b, \xi, \mu, \alpha) ≥ \mathop{inf} \limits_{w,b} L(w, b, \xi, \mu, \alpha)$$

对偶问题是拉格朗日函数的极大极小问题，首先求 $L(w, b, \xi, \mu, \alpha)$ 对 $w, b, \xi$ 的极小值，再求对 $\alpha$ 的最大，由：

$$ \nabla_w L(w, b, \xi, \mu, \alpha) = w - \sum_{i=1}^n \alpha_iy_ix_i = 0 \\ \nabla_b L(w, b, \xi, \mu, \alpha) = - \sum_{i=1}^n \alpha_iy_i = 0 \\ \nabla_{\xi} L(w, b, \xi, \mu, \alpha) = C - \alpha_i - \mu_i = 0 $$

得：

$$ w = \sum_{i=1}^n \alpha_iy_ix_i \\ \sum_{i=1}^n \alpha_iy_i = 0 \\ C - \alpha_i - \mu_i = 0 $$

原式可化为：

$$ L(w, b, \xi, \mu, \alpha) = \frac 1 2 ||w||^2 + \sum_{i=1}^n \xi_i (C - \alpha_i - \mu_i) - \sum_{i=1}^n \alpha_iy_i(w·x_i+b) + \sum_{i=1}^n \alpha_i $$

代入易得：

$$ L(w, b, \xi, \mu, \alpha) = \sum_{i=1}^n \alpha_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_jy_iy_j \langle x_i, x_j\rangle $$

对拉格朗日乘子有以下约束：

$$ \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 $$

对上式整理，消去变量 $\mu_i$ 得到约束：

$$ \sum_{i=1}^n \alpha_iy_i = 0 \\ 0 \le \alpha_i \le C \\ i=1,2,…N $$

线性支持向量机的支持向量

对于线性支持向量机，支持向量 $x_i$ 可能在间隔边界上，或者在间隔边界与分类超平面之间，或者在分类超平面的误分类一侧。

• 若 $\alpha_i^* \lt C$ 则 $ \xi_i=0$，支持向量恰好落在间隔边界上
• 若 $\alpha_i^* = C, \; 0\lt \xi_i \lt 1$，支持向量落在间隔边界与分类超平面之间
• 若 $\alpha_i^* = C, \; \xi_i = 1$，支持向量落在分类超平面上
• 若 $\alpha_i^* = C, \; \xi_i \gt 1$，支持向量落在分类超平面误分类一侧

线性支持向量机的损失函数

对于线性支持向量机来说，原始优化问题：

$$ \begin{align} \min_{w, b} &\;\; \frac 1 2 ||w||^2 + C\sum_{i=1}^n\xi_i \nonumber

\\ s.t. & \;\; y_i(w·x_i+b) \ge 1-\xi_i,\; i=1,2,…N \nonumber

\\ & \;\;\xi_i \ge 0,\;i=1,2,…Ni \nonumber \end{align}$$

等价于最优化问题：

$$\min_{w,b} \;\; \sum_{i=1}^N [1-y_i(w·x_i+b)]_+ +\lambda ||w||^2 $$

目标函数的第一项是经验损失，第二项是正则项，形如 $[1-y_i(w·x_i+b)]_+$ 的损失函数被称为合页损失函数，即 $hinge\;loss$，下标的 $+$ 表示 $[·]$ 取正值的函数，直观上的理解就是，当被正确分类时，$y_i(w·x_i+b) \gt 1 $，$1 - y_i(w·x_i+b) \lt 0$，在合页损失函数下无损失，当被错误分类时，$y_i(w·x_i+b) \lt 1 $，$1 - y_i(w·x_i+b) \gt 0$，损失等于 $1 - y_i(w·x_i+b)$。

在二分类问题中，通常使用的是 $0-1$ 损失，因为 $0-1$ 损失不可导，通常使用可导的合页损失函数作为其上界。相比之下，合页损失函数不仅要求分类正确，而却确信度足够高时损失才为 $0$，也就是说，合页损失函数对学习有更高的要求。

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

核函数方法

如下图所示，在线性不可分的情况下，支持向量机通过某种事先选择的非线性映射（核函数）将输入变量映射到一个高维特征空间，在这个空间中构造最优分类超平面，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题，核函数的价值在于它虽然也是把特征进行从低维映射到高维，但它事先 在低维上进行计算 ，而将实质上的 分类效果表现在了高维 上，也就避免了直接在高维空间中的复杂计算。

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

$$ \phi(x): X \rightarrow H $$

使得对所有的 $x,z\in X$，函数 $K(x,z)$ 满足条件：

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

则称 $K(x,z)$ 为核函数，$\phi(x)$ 为映射函数，其中 $\phi(x)·\phi(z)$ 为 $\phi(x)$ 和 $\phi(z)$ 的内积。

核技巧的想法是，在学习和预测中只定义核函数 $K(x,z)$，而不显式地定义应设函数 $\phi$，对于给定的核，特征空间和映射函数的取法并不唯一，可以取不同的特征空间，即使是在同一个特征空间内也可以有不同的映射。

在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都值设计输入实例与实例之间的内积，在对偶问题的目标函数中的内积 $\langle x_i, x_j\rangle$ 可以用核函数 $K(x_i,x_j) = \phi(x_i)·\phi(x_j)$ 来代替，这样就等价于把映射函数将原来的输入空间变换到一个新的特征空间，在新的特征空间里从训练样本学习线性支持向量机。

处理非线性数据

有如下图所示的一个数据集，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时我们该如何把这两类数据分开呢？

事实上，上图所述的这个数据集，是用两个半径不同的圆圈加上了少量的噪音生成得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线。如果用 $X_1$ 和 $X_2$ 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线的方程可以写作这样的形式:

$$ a_1X_1 + a_2X_1^2 + a_3X_2 + a_4X_2^2 + a_5X_1X_2 + a_6 = 0 $$

针对上式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 $Z_1=X_1, X_2=X_1^2, Z_3 = X_2, Z_4 = X_2^2, Z_5 = X_1X_2$，显然可以把上式改写为：

$$ \sum_{i=1}^5 \alpha_iZ_i +\alpha_6 = 0 $$

这正是一个超平面的方程，也就是说，我们做了这样一个映射将 $X_1,X_2$ 映射成了 $Z_1,Z_2,Z_3,Z_4,Z_5$，即把特征空间从二维映射到五维，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。

特别地，我们把它映射到 $Z_1 = X^2_1, Z_2 = X_2, Z_3 = X_2$ 这样一个三维空间中，将坐标轴经过适当的旋转，就可以很明显地看出，数据是可以通过一个平面来分开的。

一般地，核函数能简化映射空间中的内积运算，向量的内积可以直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果，我们可以把决策函数可以写成：

$$f(x) = \sum_{i=1}^n \alpha^*_i y_i K(x_i · x_j) $$

对偶问题可以写成：

$$ \begin{align} \min_{\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 \nonumber

\\ s.t. &\;\; \sum_{i=1}^n \alpha_i y_i = 0 \nonumber

\\ &\;\; 0 \le \alpha_i \le C,\;i=1,2,…N \nonumber \end{align}$$

常用核函数

高斯核会将原始空间映射为无穷维空间。不过，如果 $\sigma$ 选得很大的话，高次特征上的权重衰减得非常快，所以实际上相当于一个低维的子空间，反过来，如果 $\sigma$ 选得很小，则可以将任意的数据映射为线性可分，随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数 $\sigma$ ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。

序列最小最优化算法

拉格朗日乘子法与 KKT 条件

拉格朗日乘子法

引入

拉格朗日说的是，我们要求 $\min f (x)$，我们可以通过令导数等于零来求解，如果给我们约束 $\min f (x)$，一定要满足等式 $g_i(x) = 0$ 的条件，再加入不等式条件 $h_i(x) \le 0$。

即拉格朗日乘子法的引入是通过以下三步：

1. 没有约束条件：
   $$ \min f(x)$$
2. 加入等式条件：
   $$ \begin{align} \min &\quad f(x) \\s.t. &\quad g_i(x) = 0\;\; i=1,2,\dots, m\end{align}$$
3. 再加入不等式条件：
   $$ \begin{align} \min &\quad f(x) \\s.t. &\quad g_i(x) = 0\;\; i=1,2,\dots, m \\&\quad h_i(x) \le 0\;\; i=1,2,\dots, m\end{align}$$

求解

我们考虑以下问题：

$$ \begin{align} \min &\quad f(x,y) \\s.t. &\quad g(x,y) = 0 \end{align}$$

我们把 $g(x, y) = 0$ 这条曲线画在图上，给 $f (x, y)$ 画等高线，比如说图上等于 $1$ 和 $2$，我们的目标是要在 $g(x, y) = 0$ 这条曲线上找一个点使得 $f (x, y)$ 越小越好。

我们就把它想成气球，这个气球一开始比较大，这上面与 $g(x, y) = 0$ 交了两个点，这时候能找到两个点且 $f(x,y)$ 等于 $2$，然后我们尝试 $f(x,y)$ 变小，直到与 $g(x, y) = 0$ 有一个交点，最后变成没有交点，这个时候 $f(x, y)$ 达到最小，所以可以得到最后最小的点肯定是 $g(x, y)$ 与等高线若近若离的，这个若近若离的表示方法就是 $g(x, y) = 0$ 与等高线相切的，那个点就是最优点。

所以得到以下式子：

$$ \begin{align} & \nabla f(x, y) = \lambda \nabla g(x, y) \\& L(x, y, \lambda) = f(x, y) - \lambda g(x, y) \\& L(x^*, y^*, \lambda) = 0 \end{align}$$

我们直观上看，假如说 $(x^∗, y^∗)$ 是最优解的话，那么沿着这条线走的话 $f(x,y)$ 数值不变，也就是说 $f(x,y)$ 和 $g(x,y)$ 的梯度要在同一条直线上，有可能同向也有可能反向。可以表示为两个梯度成一定比例，我们把比例用 $\lambda$ 表示 $\nabla f (x, y) = \lambda \nabla g(x, y)$。对拉格朗日方程 $ L(x, y, \lambda) = f(x, y) - \lambda g(x, y) $ 求导，令导数等于零，可以得到 $\nabla f (x, y) = \lambda \nabla g(x, y)$，所以得到求有约束的最小值，可以转化成 $ L(x^*, y^*, \lambda) = 0 $。

拉格朗日方程原始的优化目标减去了一个东西，这个东西可以看作是违反约束的阈值，因为我们要求约束的结果等于 $0$，如果 $g(x, y)$ 不等于 $0$ 那么我们就要减去后面这个式子，这个 $\lambda$ 就是拉格朗日乘子。

KKT 条件

前面我们已经完成了约束为 $g(x) = 0$ 的求解方法，那如果是小于等于 $0$，那就不再是拉格朗日了，是拉格朗日的拓展，叫 $KKT$ 条件，所谓 $KKT$ 条件，是指在满足一些有规则的条件下，一个非线性规划问题能有最优化解法的一个必要和充分条件。

引入

要求 $g(x, y) \le 0$，也就是说我们是要在阴影区或者边界上找一个点， 使得 $f (x, y)$ 最小，我们把他分成两种情况:

1. 如果最优解恰好在边界上，那么这个就可以通过拉格朗日来求解。
2. 如果最优解在阴影区内部，我们是要找最优解，这个最优解在内部，那这个解一定是单纯考虑 $f (x, y)$ 的最优解，也就是直接求 $\nabla f(x,y) = 0$ 的解。

满足条件

$KKT$ 条件可以这样来表示，首先先写一个拉格朗日 $L(x, y, \lambda) = f(x, y) - \lambda g(x, y)$， 这个最优解需要满足的条件就是：

1. 原式导数等于零
2. 原可行：$g(x, y) \le 0$
3. 对偶可行：$\lambda_i \le 0$
4. 互补松弛性：$\lambda_i g_i(x) = 0$

SMO 算法

SMO 的直观理解

序列最小最优化算法即 $SMO$ 算法，采用启发式的方法认为如果所有变量的解都满足此最优化问题的 $KKT$ 条件，那么这个最优化问题的解就得到了。否则选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。其中，子问题的两个变量中只有一个是自由变量，假设 $\alpha_1,\alpha_2$ 为两个变量，$\alpha_3,…\alpha_N$ 固定，那么：

$$ \alpha_1 = -y_1 \sum_{i=1}^N a_i y_i$$

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

$SMO$ 算法包括两个部分：

• 求解两个变量二次规划的解析方法
• 选择变量的启发式方法

SMO 的公式推导

我们首先定义一个输出函数：

$$ u = w·x - b $$

这里的这个 $u$ 与我们通常意义上所定义的 $f(x) = w·x + b$ 实质上是一样的，写出支持向量机的通用优化目标：

$$ \begin{align} \min_{\alpha} &\;\; \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_jy_iy_j K\langle x_i, x_j\rangle - \sum_{i=1}^n \alpha_i \nonumber

\\ s.t. &\;\; \sum_{i=1}^n \alpha_i y_i = 0 \nonumber

\\ &\;\; 0 \le \alpha_i \le C,\;i=1,2,…n \nonumber \end{align}$$

上式是带有松弛变量和核函数的支持向量机的对偶优化目标，根据 $KKT$ 条件可以得到其中 $\alpha_i$ 取值的意义：

$$ \begin{align} \alpha_i = 0 & \Leftrightarrow y_iu_i \ge 1 \\ 0 \lt \alpha_i \lt C & \Leftrightarrow y_iu_i = 1 \\ \alpha_i = C & \Leftrightarrow y_iu_i \le 1

\end{align}$$

1. 第一个式子表明是正常分类，在边界内部，我们知道正确分类的点 $y_if(x_i) \ge 0$
2. 第二个式子表明了是支持向量，在边界上
3. 第三个式子表明了是在两条边界之间

而最优解需要满足 $KKT$ 条件，即上述 $3$ 个条件都得满足，以下几种情况出现将会出现不满足：

1. $y_iu_i \le 1$ 但是 $\alpha_i \lt C$，则是不满足的，而原本 $\alpha_i = C$
2. $y_iu_i \le 1$ 但是 $\alpha_i \gt 0$，则是不满足的，而原本 $\alpha_i = 0$
3. $y_iu_i =1$ 但是 $\alpha_i = 0$ 或者 $\alpha_i = C$，则表明不满足的，而原本应该是 $0 \lt \alpha_i \lt C$

所以要找出不满足 $KKT$ 条件的这些 $\alpha_i$，并更新这些 $\alpha_i$，但这些 $\alpha_i$ 又受到另外一个约束：

$$ \sum_{i=1}^n \alpha_i y_i = 0 $$

因此，我们通过另一个方法，即同时更新 $\alpha_i$ 和 $\alpha_j$，要求满足下面这个式子，就能保证和为零的约束：

$$ \alpha_i^{new}y_i + \alpha_j^{new}y_j = \alpha_i^{old}y_i + \alpha_j^{old}y_j = c $$

其中 $c$ 代表一个常数，又以为 $y_i^2=1$，我们可以消去 $\alpha_i$，得到一个关于单变量 $\alpha_j$ 的凸二次规划问题，不考虑其约束 $0 \le \alpha_i \le C$，可以得到：

$$ \alpha_j^{new} = \alpha_j^{old} + \frac {y_j(E_i-E_j)} {\eta} $$

其中：

$$ \begin{align} &E_i = u_i-y_i \\ &E_j = u_j-y_j \\ &\eta = K\langle x_i, x_i\rangle + K\langle x_j, x_j\rangle -2K\langle x_i, x_j\rangle \end{align}$$

然后考虑约束 $0\le \alpha_j \le C$可以得到 $\alpha_i$ 的解析解为：

$$ \alpha_i^{new,clipped} = \begin{cases} H, & \alpha_i^{new} \ge H \\ \alpha_i^{new} , & L \lt \alpha_i^{new} \lt H \\ L, & \alpha_i^{new} \le L \end{cases} $$

把 $SMO$ 中对于两个参数求解过程看成线性规划来理解来理解的话，根据 $y_i$ 和 $y_j$ 是否同号，可以得出两个上下界：

$$ y_i \neq y_j : \begin{cases} L=\max {0, \alpha_j-\alpha_i} \\ H = \min {C, C+\alpha_j-\alpha_i} \end{cases} \\ y_i = y_j : \begin{cases} L=\max {0, \alpha_j+\alpha_i-C} \\ H = \min {C, \alpha_j-\alpha_i} \end{cases} $$

对于 $\alpha_i$，有：

$$\alpha_i^{new} = \alpha_i + y_iy_j(\alpha_j-\alpha_j^{new,clipped})$$

对于 $\alpha_i$，可以通过刚刚说的那 $3$ 种不满足 $KKT$ 的条件来找；而对于 $\alpha_j$，可以通过 $\max|E_i − E_j|$ 求得；而 $b$ 的更新则是：

$$ b = \begin{cases} b_1, & 0\lt \alpha_i \lt C \\ b_2, & 0\lt \alpha_j \lt C \\ \frac 1 2(b_1+b_2), & otherwise \end{cases} $$

其中：

$$ b_1 = b-E_i-y_i(\alpha_i-\alpha_i^{old})K\langle x_i, x_i\rangle - y_j(\alpha_j-\alpha_j^{old})K\langle x_i, x_j\rangle \\ b_2 = b-E_j-y_i(\alpha_i-\alpha_i^{old})K\langle x_i, x_j\rangle - y_j(\alpha_j-\alpha_j^{old})K\langle x_j, x_j\rangle $$

每次更新完 $\alpha_i$ 和 $\alpha_j$ 后，都需要再重新计算 $b$，及对应的 $E_i$ 和 $E_j$。

最后更新所有 $\alpha_i, y, b$，这样模型就出来了，从而即可求出我们开始提出的分类函数。

SMO 的算法流程

1. 选择接下来要更新的一对 $\alpha_i$ 和 $\alpha_j$：采用启发式的方法进行选择，以使目标函数最大程度地接近其全局最优值
2. 将目标函数对 $\alpha_i$ 和 $\alpha_j$ 进行优化，保持其它所有的 $\alpha_k(k\neq i,j)$ 不变

假定在某一次迭代中，需要更新 $\alpha_1$ 和 $\alpha_2$，那么优化目标可以写成：

$$ \max_{\alpha} \alpha_1 + \alpha_2 + \sum_{i=3}^n \alpha_i - \frac 1 2 ||\alpha_1 y_1 \phi (x_1) + \alpha_2 y_2 \phi (x_2) + \sum_{i=3}^n\alpha_i y_i \phi (x_i)||^2 $$

更新 $\alpha_1$ 和 $\alpha_2$ 的步骤如下

1. 计算上下界 $L$ 和 $H$
2. 计算上式中目标函数的二阶导数
3. 更新 $\alpha_2$
4. 更新 $\alpha_1$

对于每次迭代选择 $\alpha_i$ 和 $\alpha_j$ 的启发式方法，其包括以下两个步骤：

1. 先扫描所有乘子，把第一个违反 $KKT$ 条件的作为更新对象，令为 $\alpha_j$
2. 在所有不违反 $KKT$ 条件的乘子中，选择使 $|E_i − E_j|$ 最大的 $\alpha_i$。 需要注意的是，每次更新完所选的 $\alpha_i$ 和 $\alpha_j$ 后，都需要再重新计算 $b,E_i,E_j$。另外，$\alpha_i$ 和 $\alpha_j$ 的选择务必遵循两个原则：$a.$ 满足 $KKT$ 条件，$b.$ 更新应能最大限度地增大目标函数的值

综上，$SMO$ 算法每次迭代只选出两个分量 $\alpha_i$ 和 $\alpha_j$ 进行调整，其它分量则保持固定不变，在得到解 $\alpha_i$ 和 $\alpha_j$ 之后，再用 $\alpha_i$ 和 $\alpha_j$ 改进其它分量。与通常的分解算法比较，尽管它可能需要更多的迭代次数，但每次迭代的计算量比较小，所以该算法表现出整体的快速收敛性，且不需要存储核矩阵，也没有矩阵运算。

参考文献：

[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程

[2] 卜东波,《计算机算法设计与分析》,中国科学院大学2017年秋季研究生课程

[3] 李航,《统计学习方法》,清华大学出版社

[4] 周志华,《机器学习》,清华大学出版社

[5] 支持向量机通俗导论-CSDN