正文

支持向量机（Support Vector Machine，SVM）——　线性SVM

IP云
IP云V管理员/0 阅读
08/31
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

  支持向量机（Support Vector Machine，简称 SVM）于 1995 年正式发表，由于其在文本分类任务中的卓越性能，很快就成为机器学习的主流技术。尽管现在 Deep Learning 很流行，SVM 仍然是一种很有的机器学习算法，在数据集小的情况下能比 Deep Learning 取得更好的结果。

  本文将详细介绍线性 SVM，非线性 SVM 涉及到的 kernel，本文中没有介绍。我将从以下两个方面展开介绍线性 SVM：

  • 间隔和支持向量
  • 对偶问题

1. 间隔和支持向量

  给定一个训练集 \(D= \{( \boldsymbol{x}_1, y_1), (\boldsymbol{x}_2, y_2),..., (\boldsymbol{x}_m, y_m)\}, y \in \{ -1, +1\}\)，我们想要找一个超平面对其进行划分，可以有多种选择，如下图所示：


图 1 存在多个超平面可以将训练集划分开

凭直觉，我们会选择最中间的那个超平面（也就是图 1 中最粗的那条，注：在 2 维情况下，超平面就是一条直线），为什么？因为更 robust，测试集中的点一般没有在训练集中出现过，这个时候难免会有些点会偏向分类的超平面，要是该分类超平面离训练数据点近了，这些偏向超平面的数据点岂不是直接分错了。这个时候最中间的那条线受到的影响最小，所以最优。

  在样本空间中，划分超平面可以通过以下线性方程来描述：

\begin{equation}
\boldsymbol{w}^T \boldsymbol{x} + b = 0
\end{equation}

其中 \(\boldsymbol{w} = [w_1; w_2; ...; w_d]\)（注：\(\boldsymbol{w}\) 是列向量）为法向量，决定了超平面的方向；\(b\) 是位移，决定了超平面和原定之间的距离。知道 \(\boldsymbol{w}\) 和 \(b\)，我们也就能确定该超平面的位置。样本空间中任一点 \(\boldsymbol{x}\) 到超平面 \(\boldsymbol{w}^T \boldsymbol{x} + b = 0\) 的距离可以记为：

\begin{equation}
r = \frac{ |\boldsymbol{w}^T \boldsymbol{x} + b |}{ \Vert \boldsymbol{w} \Vert }
\end{equation}

  假设超平面 \(\boldsymbol{w}^T \boldsymbol{x} + b = 0\) 能够将训练集 \(D\) 完全正确分类，即对于 \(D\) 中任一样本 \(( \boldsymbol{x}_i, y_i)\)，若 $y_i = +1 $，则 \(\boldsymbol{w}^T \boldsymbol{x}_i + b > 0\)；若 $y_i = -1 $，则 \(\boldsymbol{w}^T \boldsymbol{x}_i + b < 0\)。我们再假设训练集 \(D\) 的两个类别中，离超平面最近的点到超平面的距离都是 \(r^*(r^* > 0 )\)（两个类别离超平面最近的点到超平面的距离是一样的，不然超平面就不在“最中间”，该超平面肯定不是最优的，可以对其平移满足这个条件）。此时所有训练集 \(D\) 中点都满足以下方程：
\begin{equation}
\begin{cases}
\boldsymbol{w}^T \boldsymbol{x}_i + b \ge +r^*, & y_i = +1 \cr
\boldsymbol{w}^T \boldsymbol{x}_i + b \le -r^*, & y_i = -1
\end{cases}
\end{equation}

  此时我们对公式（3）做一个变换，不等式两边都除以 \(r^*\) 可以得到：

\begin{equation}
\begin{cases}
\frac{ \boldsymbol{w} ^T}{r^*} \boldsymbol{x}_i + \frac{b}{r^*} \ge +1, & y_i = +1 \cr
\frac{ \boldsymbol{w} ^T}{r^*} \boldsymbol{x}_i + \frac{b}{r^*} \le -1, & y_i = -1
\end{cases}
\end{equation}

  对于公式（4）中的 \(\frac{ \boldsymbol{w} ^T}{r^*}\) 和 \(\frac{b}{r^*}\)，我们令其分别为新的 \(\boldsymbol{w}^T\) 和 \(b\)，这样做只是对原超平面 \(\boldsymbol{w}^T \boldsymbol{x} + b = 0\) 的法向量和位移项进行了缩放，实际上并没有改变超平面的位置。（对位移项和法向量同时进行缩放，不会改变原点到超平面的距离，可以代入公式（2）进行检验。同样地，该变换也不会改变样本点和分类超平面之间的距离。）故而，公式（4）可以写成如下最常见的形式：

\begin{equation}
\begin{cases}
\boldsymbol{w}^T \boldsymbol{x}_i + b \ge +1, & y_i = +1 \cr
\boldsymbol{w}^T \boldsymbol{x}_i + b \le -1, & y_i = -1
\end{cases}
\end{equation}

  如图 2 所示，距离超平面最近的这几个训练样本点使式（5）的等号成立，它们被称为“支持向量”（support vector），两个类别的支持向量到超平面的距离之和为：
\begin{equation}
\gamma = \frac{2}{\Vert \boldsymbol{w} \Vert}
\end{equation}
其中，\(\gamma\) 被称为“间隔”（margin）。


图 2 支持向量和间隔

  式（5）中两个不等式可以合成一个统一的形式，如下所示：（这也是为什么类别 \(y_i\) 的取值为 -1 和 1 的原因，方便将两个不等式统一形式）
\[
\quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1, \quad i = 1,2,...m.
\]

  欲找到具有“最大间隔”（maximum margin）的划分超平面，也就是要找到能满足式（5）中约束的参数 \(\boldsymbol{w}^T\) 和 \(b\)，使得 \(\gamma\) 最大，即
\begin{equation}
\begin{split}
& \max_{\boldsymbol{w}, b} \frac{2}{\Vert \boldsymbol{w} \Vert } \quad \
& s.t. \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1, \quad i = 1,2,...m.
\end{split}
\end{equation}

  为了最大化间隔，只需要式（7）中分母最小即可，即最小化 \(\Vert \boldsymbol{w} \Vert\)，等价于最小化 \(\Vert \boldsymbol{w} \Vert^2\)，式（7）可重新写为：

\begin{equation}
\begin{split}
& \min_{\boldsymbol{w}, b} \frac{1}{2}\Vert \boldsymbol{w} \Vert^2 \quad \
& s.t. \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1, \quad i = 1,2,...m.
\end{split}
\end{equation}

式（8）就是支持向量机想要优化的目标函数。

2. 对偶问题

  我们希望求解式（8）来得到最大间隔划分超平面所对应的模型：
\begin{equation}
f(\boldsymbol{x} ) = \boldsymbol{w}^T \boldsymbol{x} + b
\end{equation}

其中 \(\boldsymbol{w}^T\) 和 \(b\) 是模型参数，式（8）本身是一个凸二次规划（convex quadratic programming）问题，能直接用现成的优化计算包求解，但我们可以有更高效的办法，即使用拉格朗日乘子法求其“对偶问题”（dual problem）。下面我们先来了解最优化问题可以分为哪几类，什么是拉格朗日乘子法，什么又是对偶问题。

2.1 最优化问题分类

  通常，我们需要求解的最优化问题有如下几类：（注：2.1 小节的 \(f(\boldsymbol{x})\) 和公式（9）没有关系）

（i）无约束优化问题：
\[
\min_{\boldsymbol{x}} f(\boldsymbol{x})
\]

（ii）有等式约束的优化问题：
\[
\begin{split}
& \min_{\boldsymbol{x}} f(\boldsymbol{x}) \\
s.t. \quad & h_i(\boldsymbol{x}) = 0, \quad i = 1,2,\dots,n.
\end{split}
\]

（iii）有不等于约束的优化问题：
\[
\begin{split}
& \min_{\boldsymbol{x}} f(\boldsymbol{x}) \\
s.t. \quad & h_i(\boldsymbol{x}) = 0, \quad i = 1,2,\dots,n; \\
& g_j(\boldsymbol{x}) \le 0, \quad j = 1,2,\dots, m.
\end{split}
\]

  对于第（i）类的优化问题，尝试使用的方法就是费马大定理(Fermat)，即使用求取函数 $ f(\boldsymbol{x}) $ 的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。这也就是我们高中经常使用的求函数的极值的方法。

  对于第（ii）类的优化问题，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) ，即把等式约束 $ h_i(\boldsymbol{x}) = 0$ 用一个系数与 $ f(\boldsymbol{x}) $ 写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。

  对于第（iii）类的优化问题，常常使用的方法就是KKT条件。同样地，我们把所有的等式、不等式约束与 $ f(\boldsymbol{x}) $ 写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。（注：若事件 B 是事件 A 的必要条件，则从事件 A 可以推出事件 B）

  SVM 的优化问题属于第（iii）类。

2.2 拉格朗日乘子法

  拉格朗日乘子法（Lagrange multipliers）是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子，可以将有 \(d\) 个变量和 \(k\) 个约束条件的最优化问题转化为具有 \(d+k\) 个变量的无约束优化问题求解。

  为什么需要拉格朗日乘子法？当然是因为无约束的问题比有约束的问题更好求解。

  “我们知道我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数，使得该函数在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化问题是等价的问题。这就是使用拉格朗日方程的目的，它将约束条件放到目标函数中，从而将有约束优化问题转换为无约束优化问题。”

  随后，人们又发现，使用拉格朗日获得的函数，使用求导的方法求解依然困难。进而，需要对问题再进行一次转换，即使用一个数学技巧：拉格朗日对偶。

  所以，在拉格朗日优化的问题上，我们需要进行下面二个步骤：

  • 将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数
  • 使用拉格朗日对偶性，将不易求解的优化问题转化为易求解的优化

  下面首先将有约束的 SVM 目标函数式（8）转化为无约束的拉格朗日函数：

  式（8）中只有不等式约束 \(g_i(w, b) \le 0\) (即 \(1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \le 0, \quad i = 1,2,...m.\))，所以这里不考虑等式约束的情况。式（8）转化的无约束的拉格朗日函数如下所示：
\begin{equation}
L(\boldsymbol{w}, b, \boldsymbol{\alpha} ) = \frac{1}{2}\Vert \boldsymbol{w} \Vert^2 +\sum_{i = 1}^{m} \alpha_i (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) )
\end{equation}

其中 \(\boldsymbol{\alpha} = [\alpha_1, \alpha_2, ..., \alpha_m]^T\) 为拉格朗日乘子，且 \(\alpha_i \ge 0, i = 1,2,..., m\)。然后，我们令
\begin{equation}
\theta(\boldsymbol{w}) = \max_{\alpha_i \ge 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha} )
\end{equation}

  当样本点不满足约束条件时，即在可行解区域外：
\begin{equation}
y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) < 1
\end{equation}

此时我们将 \(\alpha_i\) 设置为正无穷，此时 $\theta(\boldsymbol{w}) $ 显然也是正无穷。

  当样本点满足约束条件时，即在可行解区域内：
\begin{equation}
y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1
\end{equation}

此时，\(\alpha_i (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) ) \le 0\)，想要最大化 $\theta(\boldsymbol{w}) $，这一项为 0 即可，即此时 $\theta(\boldsymbol{w}) = \frac{1}{2}\Vert \boldsymbol{w} \Vert^2 $。所以 $\theta(\boldsymbol{w}) $ 可以写成如下形式：
\begin{equation}
\theta(\boldsymbol{w}) =
\begin{cases}
\frac{1}{2}\Vert \boldsymbol{w} \Vert^2, & \boldsymbol{x}_i \in 可行域; \cr
+\infty, & \boldsymbol{x}_i \in 不可行域, \quad i = 1,2,...m.
\end{cases}
\end{equation}

  自此，我们建立了一个在可行域内和原目标函数相同，在可行域外函数值趋近无穷大的新函数。

  现在我们的问题变成了求新函数的最小值：
\begin{equation}
\min_{\boldsymbol{w}, b} \theta(\boldsymbol{w}) =\min_{\boldsymbol{w}, b} \max_{\alpha_i \ge 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha} ) = p^*
\end{equation}

这里的 \(p^*\) 表示这个问题的最优值，和原目标函数的最优值是一样的。

2.3 拉格朗日对偶

  在式（15）中，我们先求最大值，再求最小值，在求最大值面临的是含有未知参数 \(\boldsymbol{w}, b\) 的，而且 \(\alpha_i \ge 0\) 又是不等式约束，如果此时我们要对 \(\alpha_i\) 求偏导，那么有多少个样本就要求多少个偏导，这个求解过程不好做。所以，我们需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：
\begin{equation}
\max_{\alpha_i \ge 0} \min_{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha} ) = d^*
\end{equation}

  式（16）是式（15）的对偶问题，这个新问题的最优值用 \(d^*\) 表示。显然有 \(d^* \le p^*\)，这称为“弱对偶性”成立；若 \(d^* = p^*\)，则称为“强对偶性”成立，此时由对偶问题能获得主问题的最优下界。对于一般的优化问题，强对偶性通常不成立。但是若主问题是凸优化问题，如式（8）中 $\frac{1}{2} \Vert \boldsymbol{w} \Vert^2 $ 和 $1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) $ 均为凸函数，且其可行域中至少有一个点使不等式约束严格成立（即至少存在一个 \(\boldsymbol{w}, b\)，使得 \(1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) < 0\) 成立），则此时强对偶性成立。

  令 \(L(\boldsymbol{w}, b, \boldsymbol{\alpha} )\) 对 \(\boldsymbol{w}\) 和 \(b\) 分别求偏导可得：
\begin{equation}
\boldsymbol{w} = \sum_{i = 1}^m \alpha_i y_i \boldsymbol{x}_i
\end{equation}

\begin{equation}
0 = \sum_{i = 1}^m \alpha_i y_i
\end{equation}

  将公式（17）代入公式（10），即可将 \(L(\boldsymbol{w}, b, \boldsymbol{\alpha} )\) 中的 \(\boldsymbol{w}\) 和 \(b\) 消去，再考虑式（18）的约束，就得到式（8）的拉格朗日对偶问题：

\[
\begin{split}
& \max_{\boldsymbol{\alpha}} & \sum_{i = 1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j = 1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j \\
& s.t. & \sum_{i = 1}^m \alpha_i y_i = 0 , \\
& & \alpha_i \ge 0, \quad i = 1,2, \dots, m.
\end{split}\tag{19}
\]

  现在我们的优化问题如公式（19）所示，我们只需要求出 \(\alpha_i\)，然后将其代入公式（17）求出 \(\boldsymbol{w}\)，然后找个支持向量带入公式（9）算出 \(b\)。（支持向量代入公式（9）会得到 \(f(\boldsymbol{x} ) = \pm1\)，此时随便一个支持向量 \(\boldsymbol{x}^*\) 都能解出 $b = f(\boldsymbol{x}^* ) - \boldsymbol{w}^T \boldsymbol{x}^* = \pm1 - \boldsymbol{w}^T \boldsymbol{x}^* $。）而求解 \(\alpha_i\)，一般会用 SMO 算法。（这里不再展开）

  最后得到的 SVM 判别函数为：
\[
\begin{split}
f(\boldsymbol{x} ) & = \boldsymbol{w}^T \boldsymbol{x} + b \\
& = \sum_{i = 1}^m \alpha_i y_i \boldsymbol{x}_i^T \boldsymbol{x}_i +b
\end{split}\tag{20}
\]

  这就结束了吗？还没有，注意到公式（8）中有不等式约束，因此上述过程需满足 KKT（Karush-Kuhn-Tucker）条件，即要求
\[
\begin{cases}
\alpha_i \ge 0; \cr
1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \le 0; \cr
\alpha_i (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 0 .
\end{cases}\tag{21}
\]

  具体 KKT 条件的由来这里不做论述，但需要明白，如果目标函数求得了最优解，则 KKT 条件一定会满足，即 KKT 条件是最优解的必要条件。

  于是，对于任意的训练样本 \((\boldsymbol{x}_i, b_i)\)，总有 \(\alpha_i = 0\) 或者 $y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 1 $。若 \(\alpha_i = 0\)，则该样本将不会出现在式（20）的求和中出现，也就不会对 \(f(\boldsymbol{x} )\) 有任何影响；若 \(\alpha_i > 0\)，则必有 $y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 1 $，所对应的样本点在位于最大间隔边界上，是一个支持向量。这里显示出 SVM 的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

References

《机器学习》周志华
机器学习实战教程（八）：支持向量机原理篇之手撕线性SVM -- Jack Cui
深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件 -- xianlingmao
支持向量机（SVM）必备知识(KKT、slater、对偶）-- feilong_csdn

支持向量机（Support Vector Machine，SVM）——线性SVM的更多相关文章

  1. Support Vector Machine &lpar;1&rpar; &colon; 简单SVM原理

    目录 Support Vector Machine (1) : 简单SVM原理 Support Vector Machine (2) : Sequential Minimal Optimization ...

  2. 支持向量机 support vector machine

    SVM(support Vector machine) (1) SVM(Support Vector Machine)是从瓦普尼克(Vapnik)的统计学习理论发展而来的,主要针对小样本数据进行学习. ...

  3. Support Vector Machine&lpar;1&rpar;&colon;线性可分集的决策边界

    与Logistuc Regression相比,SVM是一种优化的分类算法,其动机是寻找一个最佳的决策边界,使得从决策边界与各组数据之间存在margin,并且需要使各侧的margin最大化.比较容易理解 ...

  4. 支持向量机&lpar;Support Vector Machine&rpar;-----SVM之SMO算法&lpar;转&rpar;

    此文转自两篇博文 有修改 序列最小优化算法(英语:Sequential minimal optimization, SMO)是一种用于解决支持向量机训练过程中所产生优化问题的算法.SMO由微软研究院的 ...

  5. 支持向量机&lpar;Support Vector Machine，SVM&rpar;

    SVM: 1. 线性与非线性 核函数: 2. 与神经网络关系 置信区间结构: 3. 训练方法: 4.SVM light,LS-SVM: 5. VC维 u-SVC 与 c-SVC 区别? 除参数不同外, ...

  6. 第八篇：支持向量机 &lpar;Support Vector Machine&rpar;

    前言 本文讲解如何使用R语言中e1071包中的SVM函数进行分类操作,并以一个关于鸢尾花分类的实例演示具体分类步骤. 分析总体流程 1. 载入并了解数据集:2. 对数据集进行训练并生成模型:3. 在此 ...

  7. 支持向量机SVM&lpar;Support Vector Machine&rpar;

    支持向量机(Support Vector Machine)是一种监督式的机器学习方法(supervised machine learning),一般用于二类问题(binary classificati ...

  8. Support Vector Machine&lpar;2&rpar;：Lagrange Duality求解线性可分SVM的最佳边界

    在上篇文章<Support Vector Machine(1):线性可分集的决策边界>中,我们最后得到,求SVM最佳Margin的问题,转化为了如下形式: 到这一步后,我个人又花了很长的时 ...

  9. 6&period; support vector machine

    1. 了解SVM 1. Logistic regression 与SVM超平面 给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类.如果用x表示数据点,用y表示类别( ...

随机推荐

  1. 常见css水平自适应布局

    左右布局,左边固定,右边自适应布局 BFC方法解决 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN&quot ...

  2. 样式PC和手机页面

    /*媒体查询--当页面大于1200px时*/ @media (min-width: 1200px) { } /*在922和1199像素之间的屏幕里,中等屏幕*/ @media (min-width: ...

  3. CSS盒状模型简介

    CSS盒状模型 在平时的开发过程中还是经常得写博客,这2天有个公司找我面试,在面试当中提到了CSS中的盒状模型.这个东西在平时的前端开发经常用到.以下简单介绍一下: CSS中的盒状模型由:margin ...

  4. iOS 上拉刷新和下拉加在更多&lpar;第三方框架EGOTableViewPullRefresh&rpar;

    #import <UIKit/UIKit.h> @interface AppDelegate : UIResponder <UIApplicationDelegate> @pr ...

  5. Windows Azure中的Affinity Group

    Affinity Group: (近亲组?个人认为直译为近亲组更好一些,不知道官方是怎么翻译的). 如何创建Affinity Group 1. 进入https://manage.windowsazur ...

  6. JAVA面向对象-----局部内部类

    局部内部类 局部内部类概述:包含在外部类的函数中的内部类称之为局部内部类. 访问:可以在包含局部内部类的方法中直接创建局部内部类的对象调用局部内部类的成员. 注意:局部内部类只能访问所在函数的fana ...

  7. 浏览器输入url回车后，会发生什么？

    通常我们想访问某一个网址,我们会在浏览器中输入它的域名,然后点击回车进行跳转,这样就可以进到网站的主页,看似简单的两步,其实背后都需要大量的代码在运行,支持,才能完成!那浏览器到底都做了哪些事呢? 一 ...

  8. leetcode18&mdash&semi;4Sum

    Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums s ...

  9. windows 系统变量

    %ALLUSERSPROFILE% : 列出所有用户Profile文件位置.%APPDATA% : 列出应用程序数据的默认存放位置.%CD% : 列出当前目录.%CLIENTNAME% : 列出联接到 ...

  10. 【项目管理】Project使用

    http://www.cnblogs.com/wangfupeng1988/p/3647166.html