茶年 · 中文维基百科

支持向量机

Wikipedia · 2026-02-24 维基百科 👁 1 阅读

在机器学习中，-{zh-cn:支持向量机; zh-tw:支援向量機; zh-hk:支援向量機;}-
（-{zh-cn:台湾称支援向量機; zh-tw:中國大陸稱支持向量机}-，，常简称為SVM，又名支援向量网络，当数据未被标记或者仅一些数据被标记时，支援向量聚类经常在工业应用中用作分类步骤的预处理。

动机
将数据进行分类是机器学习中的一项常见任务。
假设某些给定的数据点各自属于两个类之一，而目标是确定新数据点将在哪个类中。对于支持向量机来说，数据点被视为 p 维向量，希望知道是否可以用 (p-1) 维超平面来分开这些点。这就是所谓的线性分类器。可能有许多超平面可以把数据分类。最佳超平面的一个合理选择是以最大间隔把两个类分开的超平面。因此，要选择能够让到每边最近的数据点的距离最大化的超平面。如果存在这样的超平面，则称为最大间隔超平面，而其定义的线性分类器被称为最大，或者叫做最佳稳定性感知器。*

定义
更正式地来说，支持向量机在高维或无限维空间中构造超平面或超平面集合，其可以用于分类、回归或其他任务。直觀來說，分類邊界距離最近的訓練資料點越遠越好，因為這樣可以缩小分類器的泛化誤差。

尽管原始问题可能是在有限维空间中陈述的，但用于区分的集合在该空间中往往。为此，有人提出将原有限维空间映射到维数高得多的空间中，在该空间中进行分离可能会更容易。为了保持计算负荷合理，人们选择适合该问题的 k(x,y) 来定义SVM方案使用的映射，以确保用原始空间中的变量可以很容易计算点积。高维空间中的超平面定义为与该空间中的某向量的点积是常数的点的集合。定义超平面的向量可以选择在数据集中出现的特征向量 x_i 的图像的参数 \alpha_i 的线性组合。通过选择超平面，被映射到超平面上的特征空间中的点集 x 由以下关系定义：\textstyle\sum_i \alpha_i k(x_i,x) = \mathrm{constant}. 注意，如果随着 y 逐渐远离 x，k(x,y) 变小，则求和中的每一项都是在衡量测试点 x 与对应的数据基点 x_i 的接近程度。这样，上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近度。

应用

  • 用于文本和超文本的分类，在归纳和直推方法中都可以显著减少所需要的有类标的样本数。
  • 用于图像分类。实验结果显示：在经过三到四轮相关反馈之后，比起传统的查询优化方案，支持向量机能够取得明显更高的搜索准确度。这同样也适用于图像分割系统，比如使用Vapnik所建议的使用特权方法的修改版本SVM的那些图像分割系统。
  • 用于手写字体识别。
  • 用于医学中分类蛋白质，超过90%的化合物能够被正确分类。基于支持向量机权重的置换测试已被建议作为一种机制，用于解释的支持向量机模型。支持向量机权重也被用来解释过去的SVM模型。为识别模型用于进行预测的特征而对支持向量机模型做出事后解释是在生物科学中具有特殊意义的相对较新的研究领域。

历史
原始SVM算法是由蘇聯數學家弗拉基米尔·瓦普尼克和亞歷克塞·澤范蘭傑斯于1963年发明的。1992年，伯恩哈德·E·博瑟（Bernhard E. Boser）、伊莎贝尔·M·盖昂（Isabelle M. Guyon）和瓦普尼克提出了一种通过将核技巧应用于最大间隔超平面来创建非线性分类器的方法。当前标准的前身（软间隔）由科琳娜·科特斯和瓦普尼克于1993年提出，并于1995年发表。

线性SVM
我们考虑以下形式的 n 点测试集：
: (\vec{x}_1, y_1),\, \ldots ,\, (\vec{x}_n, y_n)
其中 y_i 是 1 或者 −1，表明点 \vec{x}_i 所属的类。 \vec{x}_i 中每个都是一个 p 维实向量。我们要求将 y_i=1 的点集 \vec{x}_i 与 y_i=-1 的点集分开的 “最大间隔超平面”，使得超平面与最近的点 \vec{x}_i 之间的距离最大化。

任何超平面都可以写作满足下面方程的点集 \vec{x}
: \vec{w}\cdot\vec{x} - b=0,\,
其中 {\vec{w}}（不必是归一化的）是该法向量。参数 \tfrac{b}{\|\vec{w}\|} 决定从原点沿法向量 {\vec{w}} 到超平面的偏移量。

硬间隔
如果这些训练数据是线性可分的，可以选择分离两类数据的两个平行超平面，使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为“间隔”，最大间隔超平面是位于它们正中间的超平面。这些超平面可以由方程：
: \vec{w}\cdot\vec{x} - b=1\,
或是
: \vec{w}\cdot\vec{x} - b=-1.\,
来表示。通过几何不难得到这两个超平面之间的距离是 \tfrac{2}{\|\vec{w}\|}，因此要使两平面间的距离最大，我们需要最小化 \|\vec{w}\|。同时为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的 i 满足其中的一个条件：
: \vec{w}\cdot\vec{x}_i - b \ge 1, 若 y_i = 1
或是
: \vec{w}\cdot\vec{x}_i - b \le -1, 若 y_i = -1.
这些约束表明每个数据点都必须位于间隔的正确一侧。

这两个式子可以写作：
: y_i(\vec{w}\cdot\vec{x}_i - b) \ge 1, \quad \text{ for all } 1 \le i \le n.\qquad\qquad(1)
可以用这个式子一起来得到优化问题：“在 y_i(\vec{w}\cdot\vec{x_i} - b) \ge 1 条件下，最小化 \|\vec{w}\|，对于 i = 1,\,\ldots,\,n "
这个问题的解 \vec w 与 b 决定了我们的分类器 \vec{x} \mapsto \sgn(\vec{w} \cdot \vec{x} - b)。

此几何描述的一个显而易见却重要的结果是，最大间隔超平面完全是由最靠近它的那些 \vec{x}_i 确定的。这些 \vec{x}_i 叫做支持向量。

软间隔
为了将SVM扩展到数据线性不可分的情况，我们引入铰链损失函数，\max\left(0, 1-y_i(\vec{w}\cdot\vec{x_i} - b)\right).
当约束条件 (1) 满足时（也就是如果 \vec{x}_i 位于边距的正确一侧）此函数为零。对于间隔的错误一侧的数据，该函数的值与距间隔的距离成正比。

然后我们希望最小化\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(\vec{w}\cdot \vec{x_i} - b)\right) \right] + \lambda\lVert \vec{w} \rVert^2,
其中参数 \lambda 用来权衡增加间隔大小与确保 \vec{x}_i 位于间隔的正确一侧之间的关系。因此，对于足够小的 \lambda 值，如果输入数据是可以线性分类的，则软间隔SVM与硬间隔SVM将表现相同，但即使不可线性分类，仍能学习出可行的分类规则。

非线性分类
弗拉基米尔·瓦普尼克在1963年提出的原始最大间隔超平面算法构造了一个线性分类器。而1992年，伯恩哈德·E·博瑟（Bernhard E. Boser）、伊莎贝尔·M·盖昂（Isabelle M. Guyon）和瓦普尼克提出了一种通过将（最初由Aizerman et al.提出）应用于最大边界超平面来创建非线性分类器的方法。所得到的算法形式上类似，除了把点积换成了非线性核函数。这就允许算法在变换后的特征空间中拟合最大间隔超平面。该变换可以是非线性的，而变换空间是高维的；虽然分类器是变换后的特征空间中的超平面，但它在原始输入空间中可以是非线性的。

值得注意的是，更高维的特征空间增加了支持向量机的泛化误差，但给定足够多的样本，算法仍能表现良好。

常见的核函数包括：

  • 齊次多項式：k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j})^d
  • ：k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j} + 1)^d
  • 高斯径向基函数：k(\vec{x_i},\vec{x_j})=\exp(-\gamma \|\vec{x_i} - \vec{x_j}\|^2)，其中 \gamma > 0。有时参数化表示 \gamma=1/{2 \sigma^2}
  • 双曲正切：k(\vec{x_i},\vec{x_j})=\tanh(\kappa \vec{x_i} \cdot \vec{x_j}+c)，其中一些（而非所有）\kappa > 0 且 c

由等式 k(\vec{x_i}, \vec{x_j}) = \varphi(\vec{x_i})\cdot \varphi(\vec{x_j})，核函数与变换 \varphi(\vec{x_i}) 有关。变换空间中也有 w 值，\textstyle\vec{w} = \sum_i \alpha_i y_i \varphi(\vec{x}_i)。与 w 的点积也要用核技巧来计算，即 \textstyle \vec{w}\cdot\varphi(\vec{x}) = \sum_i \alpha_i y_i k(\vec{x}_i, \vec{x})。

计算SVM分类器
计算（软间隔）SVM分类器等同于使下面表达式最小化\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(w\cdot x_i + b)\right) \right] + \lambda\lVert w \rVert^2. \qquad(2)
如上所述，由于我们关注的是软间隔分类器，\lambda 选择足够小的值就能得到线性可分类输入数据的硬间隔分类器。下面会详细介绍将(2)简化为二次规划问题的经典方法。之后会讨论一些最近才出现的方法，如次梯度下降法和坐标下降法。

原型
最小化(2)可以用下面的方式改写为目标函数可微的约束优化问题。

对所有 i \in \{1,\,\ldots,\,n\} 我们引入变量 \zeta_i = \max\left(0, 1 - y_i(w\cdot x_i + b)\right)。注意到 \zeta_i 是满足 y_i(w\cdot x_i + b) \geq 1- \zeta_i 的最小非负数。

因此，我们可以将优化问题叙述如下 \text{minimize } \frac 1 n \sum_{i=1}^n \zeta_i + \lambda\|w\|^2
\text{subject to } y_i(x_i \cdot w + b) \geq 1 - \zeta_i \,\text{ and }\,\zeta_i \geq 0,\,\text{for all }i.
这就叫做原型问题。

对偶型
通过求解上述问题的，得到简化的问题 \text{maximize}\,\, f(c_1 \ldots c_n) = \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(x_i \cdot x_j)y_jc_j,
\text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.
这就叫做对偶问题。由于对偶最小化问题是受线性约束的 c_i 的二次函数，所以它可以通过二次规划算法高效地解出。

这里，变量 c_i 定义为满足 \vec w = \sum_{i=1}^n c_iy_i \vec x_i.
此外，当 \vec x_i 恰好在间隔的正确一侧时 c_i = 0，且当 \vec x_i 位于间隔的边界时 0 。因此， \vec w 可以写为支持向量的线性组合。

可以通过在间隔的边界上找到一个 \vec x_i 并求解 y_i(\vec w \cdot \vec x_i + b) = 1 \iff b = y_i - \vec w \cdot \vec x_i.

得到偏移量 b。（注意由于 y_i=\pm 1 因而 y_i^{-1}=y_i。）

核技巧
假设我们要学习与变换后数据点 \varphi(\vec x_i) 的线性分类规则对应的非线性分类规则。此外，我们有一个满足 k(\vec x_i, \vec x_j) = \varphi(\vec x_i) \cdot \varphi(\vec x_j) 的核函数 k。

我们知道变换空间中的分类向量 \vec w 满足 \vec w = \sum_{i=1}^n c_iy_i\varphi( \vec x_i),
其中 c_i 可以通过求解优化问题 \begin{align}
\text{maximize}\,\, f(c_1 \ldots c_n) &= \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(\varphi(\vec x_i) \cdot \varphi(\vec x_j))y_jc_j \\
&= \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_ik(\vec x_i,\vec x_j)y_jc_j \\
\end{align}

\text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.
得到。与前面一样，可以使用二次规划来求解系数 c_i。同样，我们可以找到让 0 的索引 i，使得 \varphi(\vec x_i) 位于变换空间中间隔的边界上，然后求解 \begin{align}
b = \vec w \cdot \varphi(\vec x_i) - y_i &= \left[\sum_{k=1}^n c_ky_k\varphi(\vec x_k)\cdot\varphi(\vec x_i)\right] - y_i \\
&= \left[\sum_{k=1}^n c_ky_kk(\vec x_k, \vec x_i)\right] - y_i.
\end{align}
最后，可以通过计算下式来分类新点 \vec z \mapsto \sgn(\vec w \cdot \varphi(\vec z) + b) = \sgn\left(\left[\sum_{i=1}^n c_iy_ik(\vec x_i, \vec z)\right] + b\right).

现代方法
用于找到SVM分类器的最近的算法包括次梯度下降和坐标下降。当处理大的稀疏数据集时，这两种技术已经被证明有着显著的优点——当存在许多训练实例时次梯度法是特别有效的，并且当特征空间的维度高时，坐标下降特别有效。

次梯度下降
SVM的次梯度下降算法直接用表达式f(\vec w, b) = \left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(w\cdot x_i + b)\right) \right] + \lambda\lVert w \rVert^2.
注意 f 是 \vec w 与 b 的凸函数。因此，可以采用传统的梯度下降（或）方法，其中不是在函数梯度的方向上前进，而是在从函数的次梯度中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 n 而增加或减少。

坐标下降
SVM的坐标下降算法基于对偶问题

\text{maximize}\,\, f(c_1 \ldots c_n) = \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(x_i \cdot x_j)y_jc_j, \text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.
对所有 i \in \{1,\, \ldots,\, n\} 进行迭代，使系数 c_i 的方向与 \partial f/ \partial c_i 一致。然后，将所得的系数向量 (c_1',\,\ldots,\,c_n') 投影到满足给定约束的最接近的系数向量。（通常使用欧氏距离。）然后重复该过程，直到获得接近最佳的系数向量。所得的算法在实践中运行非常快，尽管已经证明的性能保证很少。

性质
SVM属于广义线性分类器的一族，并且可以解释为感知器的延伸。它们也可以被认为是吉洪诺夫正则化的特例。它们有一个特别的性质，就是可以同时最小化经验误差和最大化几何边缘区; 因此它们也被称为最大间隔分类器。

Meyer、Leisch和Hornik对SVM与其他分类器进行了比较。

参数选择
SVM的有效性取决于核函数、核参数和软间隔参数 C 的选择。
通常会选只有一个参数 \gamma 的高斯核。C 和 \gamma 的最佳组合通常通过在 C 和 \gamma 为指数增长序列下来选取，例如 C \in \{ 2^{-5}, 2^{-3}, \dots, 2^{13},2^{15} \}; \gamma \in \{ 2^{-15},2^{-13}, \dots, 2^{1},2^{3} \}。通常情况下，使用交叉驗證来检查参数选择的每一个组合，并选择具有最佳交叉验证精度的参数。或者，最近在贝叶斯优化中的工作可以用于选择C和γ，通常需要评估比网格搜索少得多的参数组合。或者，贝叶斯优化的最近进展可以用于选择 C 和 \gamma，通常需要计算的参数组合比网格搜索少得多。然后，使用所选择的参数在整个训练集上训练用于测试和分类新数据的最终模型。

问题
SVM的潜在缺点包括以下方面：

  • 需要对输入数据进行完全标记
  • 未校准类成员概率
  • SVM仅直接适用于两类任务。因此，必须应用将多类任务减少到几个二元问题的算法；请参阅多类SVM一节。
  • 解出的模型的参数很难理解。

延伸

  • 支持向量聚類：支持向量聚類是一種建立在核函數上的類似方法，同適用於非監督學習和數據挖掘。它被認為是數據科學中的一種基本方法。
  • 轉導支持向量機
  • 多元分類支持向量機：SVM算法最初是為二值分類問題設計的，實現多分類的主要方法是將一個多分類問題轉化為多個二分類問題。常見方法包括“一對多法”和“一對一法”，一對多法是將某個類別的樣本歸為一類,其他剩餘的樣本歸為另一類，這樣k個類別的樣本就構造出了k個二分類SVM；一對一法則是在任意兩類樣本之間設計一個SVM。
  • 支持向量回歸
  • 結構化支持向量機：支持向量機可以被推廣為結構化的支持向量機，推廣後標籤空間是結構化的並且可能具有無限的大小。

实现
最大间隔超平面的参数是通过求解优化得到的。有几种专门的算法可用于快速解决由SVM产生的QP问题，它们主要依靠启发式算法将问题分解成更小、更易于处理的子问题。

另一种方法是使用内点法，其使用类似牛顿法的迭代找到卡羅需－庫恩－塔克條件下原型和对偶型的解。
这种方法不是去解决一系列分解问题，而是直接完全解决该问题。为了避免求解核矩阵很大的线性系统，在核技巧中经常使用矩阵的低秩近似。

另一个常见的方法是普莱特的序列最小优化算法（SMO），它把问题分成了若干个可以解析求解的二维子问题，这样就可以避免使用数值优化算法和矩阵存储。

线性支持向量机的特殊情况可以通过用于优化其类似问题邏輯斯諦迴歸的同类算法更高效求解；这类算法包括次梯度下降法（如PEGASOS）和坐标下降法（如LIBLINEAR）。LIBLINEAR有一些引人注目的训练时间上的特性。每次收敛迭代花费在读取训练数据上的时间是线性的，而且这些迭代还具有特性，使得算法非常快。

一般的核SVM也可以用次梯度下降法（P-packSVM）更快求解，在允许并行化时求解速度尤其快。

许多机器学习工具包都可以使用核SVM，有、MATLAB、SAS、SVMlight、kernlab、scikit-learn、、Weka、Shark、JKernelMachines、OpenCV等。

参见

  • 核方法

*
*

  • 预测分析
  • 相关向量机，函数形式与SVM相同的概率稀疏核模型
  • 序列最小优化算法

*

参考文献
引用
来源

外部链接

#分類演算法 #支持向量機 #统计分类 #核方法

评论 (0)

  • 还没有评论，来抢沙发吧。