查看“︁支持向量机”︁的源代码

{{NoteTA
|G1=IT
|T=zh-tw:支援向量機;zh-cn:支持向量机;zh-hk:支援向量機
|1=zh-tw:支援向量;zh-cn:支持向量;zh-hk:支援向量}}
{{redirect|SVM}}
{{Machine learning bar}}

在[[机器学习]]中，'''-{zh-cn:支持向量机; zh-tw:支援向量機; zh-hk:支援向量機;}-'''
（-{zh-cn:台湾称'''支援向量機'''; zh-tw:中國大陸稱'''支持向量机'''}-，{{lang-en|support vector machine}}，常简称為'''SVM'''，又名'''支援向量网络'''<ref name="CorinnaCortes"/>）是在[[分类问题|分类]]与[[迴歸分析]]中分析数据的[[監督式學習]]模型与相关的学习[[算法]]。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法建立一个将新的实例分配给两个类别之一的模型，使其成为非概率{{le|二元分类器|binary classifier|二元}}[[线性分类器]]。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

除了进行线性分类之外，SVM还可以使用所谓的{{le|核技巧|kernel trick}}有效地进行非线性分类，将其输入隐式映射到高维特征空间中。

当数据未被标记时，不能进行监督式学习，需要用[[非監督式學習]]，它会尝试找出数据到簇的自然聚类，并将新数据映射到这些已形成的簇。将支援向量机改进的聚类算法被称为'''支援向量聚类'''<ref name="HavaSiegelmann">Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137.</ref>，当数据未被标记或者仅一些数据被标记时，支援向量聚类经常在工业应用中用作分类步骤的预处理。

== 动机 ==
[[Image:Svm separating hyperplanes (SVG).svg|thumb|right|H<sub>1</sub> 不能把类别分开。H<sub>2</sub> 可以，但只有很小的间隔。H<sub>3</sub> 以最大间隔将它们分开。]]
[[分类问题|将数据进行分类]]是[[机器学习]]中的一项常见任务。
假设某些给定的数据点各自属于两个类之一，而目标是确定新数据点将在哪个类中。对于支持向量机来说，数据点被视为 <math>p</math> 维向量，而我们想知道是否可以用 <math>(p-1)</math> 维[[超平面]]来分开这些点。这就是所谓的[[线性分类器]]。可能有许多超平面可以把数据分类。最佳超平面的一个合理选择是以最大间隔把两个类分开的超平面。因此，我们要选择能够让到每边最近的数据点的距离最大化的超平面。如果存在这样的超平面，则称为最大间隔超平面，而其定义的线性分类器被称为最大{{le|间隔分类器|margin classifier}}，或者叫做最佳稳定性[[感知器]]。''{{Citation needed|date=2013年6月}}

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

[[File:Kernel_Machine.png|thumb|核机器，图中核函数Φ，将低维非线性可分离函数（左）计算成高维线性可分离函数（右）]]
尽管原始问题可能是在有限维空间中陈述的，但用于区分的集合在该空间中往往{{le|线性可分|Linear separability|线性不可分}}。为此，有人提出将原有限维空间映射到维数高得多的空间中，在该空间中进行分离可能会更容易。为了保持计算负荷合理，人们选择适合该问题的{{le|正定核|Positive-definite kernel|核函数}} <math>k(x,y)</math> 来定义SVM方案使用的映射，以确保用原始空间中的变量可以很容易计算[[数量积|点积]]。<ref>*{{Cite book |last1=Press |first1=William H. |last2=Teukolsky |first2=Saul A. |last3=Vetterling |first3=William T. |last4=Flannery |first4=B. P. |year=2007 |title=Numerical Recipes: The Art of Scientific Computing |edition=3rd |publisher=Cambridge University Press |publication-place=New York |isbn=978-0-521-88068-8 |chapter=Section 16.5. Support Vector Machines |chapter-url=http://apps.nrbook.com/empanel/index.html#pg=883 |access-date=2016-11-06 |archive-date=2011-08-11 |archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=883 |dead-url=no }}</ref> 高维空间中的超平面定义为与该空间中的某向量的点积是常数的点的集合。定义超平面的向量可以选择在数据集中出现的特征向量 <math>x_i</math> 的图像的参数 <math>\alpha_i</math> 的线性组合。通过选择超平面，被映射到超平面上的特征空间中的点集 <math>x</math> 由以下关系定义：<math>\textstyle\sum_i \alpha_i k(x_i,x) = \mathrm{constant}.</math>  注意，如果随着 <math>y</math> 逐渐远离 <math>x</math>，<math>k(x,y)</math> 变小，则求和中的每一项都是在衡量测试点 <math>x</math> 与对应的数据基点 <math>x_i</math> 的接近程度。这样，上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近度。<!--Note the fact that the set of points <math>x</math> mapped into any hyperplane can be quite convoluted as a result, allowing much more complex discrimination between sets which are not convex at all in the original space.-->

== 应用 ==
* 用于文本和超文本的分类，在归纳和直推方法中都可以显著减少所需要的有类标的样本数。
* 用于图像分类。实验结果显示：在经过三到四轮相关反馈之后，比起传统的查询优化方案，支持向量机能够取得明显更高的搜索准确度。这同样也适用于图像分割系统，比如使用Vapnik所建议的使用特权方法的修改版本SVM的那些图像分割系统。<ref>Vapnik, V.: Invited Speaker. IPMU Information Processing and Management 2014)</ref><ref>Barghout, Lauren. "Spatial-Taxon Information Granules as Used in Iterative Fuzzy-Decision-Making for Image Segmentation." Granular Computing and Decision-Making. Springer International Publishing, 2015. 285-318.</ref>
* 用于手写字体识别。
* 用于医学中分类蛋白质，超过90%的化合物能够被正确分类。基于支持向量机权重的置换测试已被建议作为一种机制，用于解释的支持向量机模型。<ref>Bilwaj Gaonkar, Christos Davatzikos Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification</ref><ref>R. Cuingnet, C. Rosso, M. Chupin, S. Lehéricy, D. Dormont, H. Benali, Y. Samson and O. Colliot, Spatial regularization of SVM for the detection of diffusion alterations associated with stroke outcome, Medical Image Analysis, 2011, 15 (5): 729–737</ref> 支持向量机权重也被用来解释过去的SVM模型。<ref>Statnikov, A., Hardin, D., & Aliferis, C. (2006). Using SVM weight-based methods to identify causally relevant and non-causally relevant variables. sign, 1, 4.</ref> 为识别模型用于进行预测的特征而对支持向量机模型做出事后解释是在生物科学中具有特殊意义的相对较新的研究领域。

== 历史 ==
原始SVM算法是由[[蘇聯]]數學家[[弗拉基米尔·瓦普尼克]]和[[亞歷克塞·澤范蘭傑斯]]于1963年发明的。1992年，伯恩哈德·E·博瑟（Bernhard E. Boser）、伊莎贝尔·M·盖昂（Isabelle M. Guyon）和瓦普尼克提出了一种通过将核技巧应用于最大间隔超平面来创建非线性分类器的方法。<ref name="ReferenceA">{{Cite book | doi = 10.1145/130385.130401| chapter = A training algorithm for optimal margin classifiers| title = Proceedings of the fifth annual workshop on Computational learning theory – COLT '92| pages = 144| year = 1992| last1 = Boser | first1 = B. E. | last2 = Guyon | first2 = I. M. | last3 = Vapnik | first3 = V. N. | isbn = 089791497X}}</ref> 当前标准的前身（软间隔）由[[科琳娜·科特斯]]和瓦普尼克于1993年提出，并于1995年发表。<ref name="CorinnaCortes">{{Cite journal|last2=Vapnik|first2=V.|year=1995|title=Support-vector networks|journal={{tsl|en|Machine Learning (journal)||Machine Learning}}|volume=20|issue=3|pages=273–297|doi=10.1007/BF00994018|last1=Cortes|first1=C.|authorlink1=Corinna Cortes}}</ref>

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

任何超平面都可以写作满足下面方程的点集 <math>\vec{x}</math>
: <math>\vec{w}\cdot\vec{x} - b=0,\,</math> [[File:Svm_max_sep_hyperplane_with_margin.png|right|thumb|设样本属于两个类，用该样本训练SVM得到的最大间隔超平面。在边缘上的样本点称为支持向量。]]
其中 <math>{\vec{w}}</math>（不必是归一化的）是该[[法线|法向量]]。参数 <math>\tfrac{b}{\|\vec{w}\|}</math> 决定从原点沿法向量 <math>{\vec{w}}</math> 到超平面的偏移量。

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

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

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

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

然后我们希望最小化<blockquote><math>\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,</math></blockquote>其中参数 <math>\lambda</math> 用来权衡增加间隔大小与确保 <math>\vec{x}_i</math> 位于间隔的正确一侧之间的关系。因此，对于足够小的 <math>\lambda</math> 值，如果输入数据是可以线性分类的，则软间隔SVM与硬间隔SVM将表现相同，但即使不可线性分类，仍能学习出可行的分类规则。

== 非线性分类 ==
[[File:Kernel_Machine.png|thumb|核机器，图中核函数Φ，将低维非线性可分离函数（左）计算成高维线性可分离函数（右）]]
[[弗拉基米尔·瓦普尼克]]在1963年提出的原始最大间隔超平面算法构造了一个[[线性分类器]]。而1992年，伯恩哈德·E·博瑟（Bernhard E. Boser）、伊莎贝尔·M·盖昂（Isabelle M. Guyon）和瓦普尼克提出了一种通过将{{le|核技巧|kernel trick}}（最初由Aizerman et al.<!--
--><ref>{{cite journal |author1=Aizerman, Mark A. |author2=Braverman, Emmanuel M. |author3=Rozonoer, Lev I.  |last-author-amp=yes |year = 1964|title = Theoretical foundations of the potential function method in pattern recognition learning|url=https://archive.org/details/sim_automation-and-remote-control_1964-06_25_6/page/821 |journal = Automation and Remote Control|volume = 25|pages = 821–837}}</ref>提出）应用于最大边界超平面来创建非线性分类器的方法。<ref name="ReferenceA2">{{Cite book |doi = 10.1145/130385.130401|chapter = A training algorithm for optimal margin classifiers|title = Proceedings of the fifth annual workshop on Computational learning theory – COLT '92|pages = 144|year = 1992|last1 = Boser|first1 = B. E.|last2 = Guyon|first2 = I. M.|last3 = Vapnik|first3 = V. N.|isbn = 089791497X}}</ref> 所得到的算法形式上类似，除了把[[数量积|点积]]换成了非线性[[积分变换|核]]函数。这就允许算法在变换后的[[特征空间]]中拟合最大间隔超平面。该变换可以是非线性的，而变换空间是高维的；虽然分类器是变换后的特征空间中的超平面，但它在原始输入空间中可以是非线性的。

值得注意的是，更高维的特征空间增加了支持向量机的[[泛化误差]]，但给定足够多的样本，算法仍能表现良好。<ref>{{cite conference|last1 = Jin|first1 = Chi|last2 = Wang|first2 = Liwei|title = Dimensionality dependent PAC-Bayes margin bound|conference = Advances in Neural Information Processing Systems|year = 2012|url = http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound|access-date = 2016-11-06|archive-date = 2015-04-02|archive-url = https://web.archive.org/web/20150402185336/http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound|dead-url = no}}</ref>

常见的核函数包括：
* [[齊次多項式]]：<math>k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j})^d</math>
* {{le|多项式核函数|Polynomial kernel|非齐次多项式}}：<math>k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j} + 1)^d</math>
* 高斯[[径向基函数核|径向基函数]]：<math>k(\vec{x_i},\vec{x_j})=\exp(-\gamma \|\vec{x_i} - \vec{x_j}\|^2)</math>，其中 <math>\gamma > 0</math>。有时参数化表示 <math>\gamma=1/{2 \sigma^2}</math>
* [[双曲函数|双曲正切]]：<math>k(\vec{x_i},\vec{x_j})=\tanh(\kappa \vec{x_i} \cdot \vec{x_j}+c)</math>，其中一些（而非所有）<math>\kappa > 0 </math> 且 <math> c < 0 </math>
由等式 <math>k(\vec{x_i}, \vec{x_j}) = \varphi(\vec{x_i})\cdot \varphi(\vec{x_j})</math>，核函数与变换 <math>\varphi(\vec{x_i})</math> 有关。变换空间中也有 '''w''' 值，<math>\textstyle\vec{w} = \sum_i \alpha_i y_i \varphi(\vec{x}_i)</math>。与 '''w''' 的点积也要用核技巧来计算，即 <math>\textstyle \vec{w}\cdot\varphi(\vec{x}) = \sum_i \alpha_i y_i k(\vec{x}_i, \vec{x})</math>。

== 计算SVM分类器 ==
计算（软间隔）SVM分类器等同于使下面表达式最小化<blockquote><math>\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)</math></blockquote>如上所述，由于我们关注的是软间隔分类器，<math>\lambda</math> 选择足够小的值就能得到线性可分类输入数据的硬间隔分类器。下面会详细介绍将(2)简化为[[二次规划]]问题的经典方法。之后会讨论一些最近才出现的方法，如次梯度下降法和坐标下降法。

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

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

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

=== 对偶型 ===
通过求解上述问题的{{le|对偶 (最优化)|Duality (optimization)|拉格朗日对偶}}，得到简化的问题<blockquote><math> \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,</math></blockquote><blockquote><math> \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.</math></blockquote>这就叫做''对偶''问题。由于对偶最小化问题是受线性约束的 <math> c_i</math> 的二次函数，所以它可以通过[[二次规划]]算法高效地解出。

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

可以通过在间隔的边界上找到一个 <math> \vec x_i</math> 并求解<blockquote><math> y_i(\vec w \cdot \vec x_i + b) = 1 \iff b = y_i - \vec w \cdot \vec x_i.</math></blockquote>
得到偏移量 <math> b</math>。（注意由于 <math>y_i=\pm 1</math> 因而 <math>y_i^{-1}=y_i</math>。）

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

我们知道变换空间中的分类向量 <math>  \vec w</math> 满足<blockquote><math>  \vec w = \sum_{i=1}^n c_iy_i\varphi( \vec x_i),</math></blockquote>其中 <math>  c_i</math> 可以通过求解优化问题<blockquote><math> \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}
</math></blockquote><blockquote><math> \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.</math></blockquote>得到。与前面一样，可以使用二次规划来求解系数 <math> c_i</math>。同样，我们可以找到让 <math> 0 < c_i <(2n\lambda)^{-1}</math> 的索引 <math> i</math>，使得 <math> \varphi(\vec x_i)</math> 位于变换空间中间隔的边界上，然后求解<blockquote><math> \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}</math></blockquote>最后，可以通过计算下式来分类新点 <blockquote><math> \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).</math></blockquote>

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

==== 次梯度下降 ====
SVM的[[次梯度法|次梯度下降]]算法直接用表达式<blockquote><math>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.</math></blockquote>注意 <math>f</math> 是 <math>\vec w</math> 与 <math>b</math> 的[[凸函数]]。因此，可以采用传统的[[梯度下降法|梯度下降]]（或{{tsl|en|Stochastic gradient descent||SGD}}）方法，其中不是在函数梯度的方向上前进，而是在从函数的[[次导数|次梯度]]中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 <math>n</math> 而增加或减少。<ref>{{Cite journal|title = Pegasos: primal estimated sub-gradient solver for SVM|url = http://link.springer.com/article/10.1007/s10107-010-0420-4|journal = Mathematical Programming|date = 2010-10-16|issn = 0025-5610|pages = 3–30|volume = 127|issue = 1|doi = 10.1007/s10107-010-0420-4|first = Shai|last = Shalev-Shwartz|first2 = Yoram|last2 = Singer|first3 = Nathan|last3 = Srebro|first4 = Andrew|last4 = Cotter|access-date = 2016-11-06|archive-date = 2016-08-25|archive-url = https://web.archive.org/web/20160825232322/http://link.springer.com/article/10.1007/s10107-010-0420-4|dead-url = no}}</ref>

==== 坐标下降 ====
SVM的[[坐标下降法|坐标下降]]算法基于对偶问题

<math> \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,</math><blockquote><math> \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.</math></blockquote>对所有 <math> i \in \{1,\, \ldots,\, n\}</math> 进行迭代，使系数 <math> c_i</math> 的方向与 <math> \partial f/ \partial c_i</math> 一致。然后，将所得的系数向量 <math> (c_1',\,\ldots,\,c_n')</math> 投影到满足给定约束的最接近的系数向量。（通常使用欧氏距离。）然后重复该过程，直到获得接近最佳的系数向量。所得的算法在实践中运行非常快，尽管已经证明的性能保证很少。<ref>{{Cite journal|title = A Dual Coordinate Descent Method for Large-scale Linear SVM|url = http://doi.acm.org/10.1145/1390156.1390208|publisher = ACM|journal = Proceedings of the 25th International Conference on Machine Learning|date = 2008-01-01|location = New York, NY, USA|isbn = 978-1-60558-205-4|pages = 408–415|series = ICML '08|doi = 10.1145/1390156.1390208|first = Cho-Jui|last = Hsieh|first2 = Kai-Wei|last2 = Chang|first3 = Chih-Jen|last3 = Lin|first4 = S. Sathiya|last4 = Keerthi|first5 = S.|last5 = Sundararajan}}</ref>

== 性质 ==

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

Meyer、Leisch和Hornik对SVM与其他分类器进行了比较。<ref>{{Cite journal | doi = 10.1016/S0925-2312(03)00431-4| title = The support vector machine under test| journal = Neurocomputing| volume = 55| pages = 169| year = 2003| last1 = Meyer | first1 = D. | last2 = Leisch | first2 = F. | last3 = Hornik | first3 = K. }}</ref>

=== 参数选择 ===

SVM的有效性取决于核函数、核参数和软间隔参数 ''C'' 的选择。
通常会选只有一个参数 ''<math>\gamma</math>'' 的高斯核。''C'' 和 <math>\gamma</math> 的最佳组合通常通过在 ''C'' 和 ''<math>\gamma</math>'' 为指数增长序列下{{le|网格搜索|grid search}}来选取，例如 <math>C \in \{ 2^{-5}, 2^{-3}, \dots, 2^{13},2^{15} \}</math>; <math>\gamma \in \{ 2^{-15},2^{-13}, \dots, 2^{1},2^{3} \}</math>。通常情况下，使用[[交叉驗證]]来检查参数选择的每一个组合，并选择具有最佳交叉验证精度的参数。或者，最近在贝叶斯优化中的工作可以用于选择C和γ，通常需要评估比网格搜索少得多的参数组合。或者，{{le|贝叶斯优化|Bayesian optimization}}的最近进展可以用于选择 ''C'' 和 ''<math>\gamma</math>''，通常需要计算的参数组合比网格搜索少得多。然后，使用所选择的参数在整个训练集上训练用于测试和分类新数据的最终模型。<ref>{{cite techreport |url=http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf |title=A Practical Guide to Support Vector Classification |author1=Hsu, Chih-Wei |author2=Chang, Chih-Chung |author3=Lin, Chih-Jen |last-author-amp=yes |year=2003 |institution=Department of Computer Science and Information Engineering, National Taiwan University |access-date=2016-11-06 |archive-date=2013-06-25 |archive-url=https://web.archive.org/web/20130625201224/http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf |dead-url=no }}</ref>

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

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

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

== 实现 ==

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

另一种方法是使用[[内点法]]，其使用类似[[牛顿法]]的迭代找到[[卡羅需－庫恩－塔克條件]]下原型和对偶型的解。<ref>{{Cite journal | doi = 10.1137/S1052623400374379| title = Interior-Point Methods for Massive Support Vector Machines| journal = SIAM Journal on Optimization| volume = 13| issue = 3| pages = 783| year = 2002| last1 = Ferris | first1 = M. C. | last2 = Munson | first2 = T. S. }}</ref>
这种方法不是去解决一系列分解问题，而是直接完全解决该问题。为了避免求解核矩阵很大的线性系统，在核技巧中经常使用矩阵的低秩近似。

另一个常见的方法是普莱特的[[序列最小优化算法]]（SMO），它把问题分成了若干个可以解析求解的二维子问题，这样就可以避免使用数值优化算法和矩阵存储。<ref>{{cite conference |author=John C. Platt |title=Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines |conference=NIPS |year=1998 |url=http://research.microsoft.com/pubs/69644/tr-98-14.pdf |access-date=2016-11-06 |archive-date=2015-07-02 |archive-url=https://web.archive.org/web/20150702075055/http://research.microsoft.com/pubs/69644/tr-98-14.pdf |dead-url=no }}</ref>

线性支持向量机的特殊情况可以通过用于优化其类似问题[[邏輯斯諦迴歸]]的同类算法更高效求解；这类算法包括次梯度下降法（如PEGASOS<ref>{{cite conference |author1=Shai Shalev-Shwartz |author2=Yoram Singer |author3=Nathan Srebro |title=Pegasos: Primal Estimated sub-GrAdient SOlver for SVM |conference=ICML |year=2007 |url=http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf |access-date=2016-11-06 |archive-date=2013-12-15 |archive-url=https://web.archive.org/web/20131215051700/http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf |dead-url=no }}</ref>）和[[坐标下降法]]（如LIBLINEAR<ref>{{cite journal |author1=R.-E. Fan |author2=K.-W. Chang |author3=C.-J. Hsieh |author4=X.-R. Wang |author5=C.-J. Lin |title=LIBLINEAR: A library for large linear classification |journal={{tsl|en|Journal of Machine Learning Research||Journal of Machine Learning Research}} |volume=9 |pages=1871–1874 |year=2008}}</ref>）。LIBLINEAR有一些引人注目的训练时间上的特性。每次收敛迭代花费在读取训练数据上的时间是线性的，而且这些迭代还具有{{le|收敛速率|Rate of convergence|Q-线性收敛}}特性，使得算法非常快。

一般的核SVM也可以用次梯度下降法（P-packSVM<ref>{{cite conference |author1=Zeyuan Allen Zhu |author2=Weizhu Chen |author3=Gang Wang |author4=Chenguang Zhu |author5=Zheng Chen |display-authors=1 |title=P-packSVM: Parallel Primal grAdient desCent Kernel SVM |conference=ICDM |year=2009 |url=http://people.csail.mit.edu/zeyuan/paper/2009-ICDM-Parallel.pdf |access-date=2016-11-06 |archive-date=2014-04-07 |archive-url=https://web.archive.org/web/20140407095709/http://people.csail.mit.edu/zeyuan/paper/2009-ICDM-Parallel.pdf |dead-url=no }}</ref>）更快求解，在允许并行化时求解速度尤其快。

许多机器学习工具包都可以使用核SVM，有{{tsl|en|LIBSVM||LIBSVM}}、[[MATLAB]]、SAS<ref>[http://support.sas.com/documentation/cdl/en/whatsnew/64209/HTML/default/viewer.htm#emdocwhatsnew71.htm SAS] {{Wayback|url=http://support.sas.com/documentation/cdl/en/whatsnew/64209/HTML/default/viewer.htm#emdocwhatsnew71.htm |date=20161124212019 }}</ref>、SVMlight、kernlab<ref>[https://cran.r-project.org/package=kernlab kernlab]</ref>、[[scikit-learn]]、{{tsl|en|Shogun (toolbox)||Shogun}}、[[Weka]]、Shark<ref>[http://image.diku.dk/shark/ Shark] {{Wayback|url=http://image.diku.dk/shark/ |date=20161026050840 }}</ref>、JKernelMachines<ref>[https://mloss.org/software/view/409/ JKernelMachines] {{Wayback|url=https://mloss.org/software/view/409/ |date=20160909075405 }}</ref>、OpenCV等。

== 参见 ==
* [[核方法]]
* {{le|费希尔核|Fisher kernel}}
* {{le|多项式核函数|Polynomial kernel}}
* [[预测分析]]
* [[相关向量机]]，函数形式与SVM相同的概率稀疏核模型
* [[序列最小优化算法]]
* {{le|空间映射|Space mapping}}

== 参考文献 ==
=== 引用 ===
{{Reflist|30em}}

=== 来源 ===
{{refbegin}}
* Theodoridis, Sergios; and Koutroumbas, Konstantinos; "Pattern Recognition", 4th Edition, Academic Press, 2009, ISBN 978-1-59749-272-0
* Cristianini, Nello; and Shawe-Taylor, John; ''[https://web.archive.org/web/20180627015707/https://www.support-vector.net/ An Introduction to Support Vector Machines and other kernel-based learning methods]'', Cambridge University Press, 2000. ISBN 0-521-78019-5 (SVM Book)
* Huang, Te-Ming; Kecman, Vojislav; and Kopriva, Ivica (2006); ''[http://learning-from-data.com Kernel Based Algorithms for Mining Huge Data Sets] {{Wayback|url=http://learning-from-data.com/ |date=20110518133503 }}'', in ''Supervised, Semi-supervised, and Unsupervised Learning'', Springer-Verlag, Berlin, Heidelberg, 260 pp.&nbsp;96 illus., Hardcover, ISBN 3-540-31681-7
* Kecman, Vojislav; ''[http://www.support-vector.ws Learning and Soft Computing&nbsp;— Support Vector Machines, Neural Networks, Fuzzy Logic Systems] {{Wayback|url=http://www.support-vector.ws/ |date=20200918192300 }}'', The MIT Press, Cambridge, MA, 2001.
* Schölkopf, Bernhard; and Smola, Alexander J.; ''Learning with Kernels'', MIT Press, Cambridge, MA, 2002. ISBN 0-262-19475-9
* Schölkopf, Bernhard; Burges, Christopher J. C.; and Smola, Alexander J. (editors); ''[https://web.archive.org/web/20071017030144/http://kernel-machines.org/nips97/book.html Advances in Kernel Methods: Support Vector Learning]'', MIT Press, Cambridge, MA, 1999. ISBN 0-262-19416-3.
* Shawe-Taylor, John; and Cristianini, Nello; ''[http://www.kernel-methods.net Kernel Methods for Pattern Analysis] {{Wayback|url=http://www.kernel-methods.net/ |date=20180613185544 }}'', Cambridge University Press, 2004. ISBN 0-521-81397-2 ''(Kernel Methods Book)''
* Steinwart, Ingo; and Christmann, Andreas; ''[https://web.archive.org/web/20120220084913/http://www.staff.uni-bayreuth.de/~btms01/svm.html Support Vector Machines]'', Springer-Verlag, New York, 2008. ISBN 978-0-387-77241-7 ''(SVM Book)''
* Tan, Peter Jing; and [http://www.csse.monash.edu.au/~dld Dowe, David L.] {{Wayback|url=http://www.csse.monash.edu.au/~dld |date=20060212185445 }} (2004); [http://www.csse.monash.edu.au/~dld/David.Dowe.publications.html#TanDowe2004 ''MML Inference of Oblique Decision Trees''] {{Wayback|url=http://www.csse.monash.edu.au/~dld/David.Dowe.publications.html#TanDowe2004 |date=20160804182249 }}, Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, [https://web.archive.org/web/20160806013805/http://www.csse.monash.edu.au/~dld/Publications/2004/Tan+DoweAI2004.pdf pp. 1082–1088]. (This paper uses [[minimum message length]] ([[Minimum Message Length|MML]]) and actually incorporates probabilistic support vector machines in the leaves of [[Decision tree learning|decision trees]].)
* Vapnik, Vladimir N.; ''The Nature of Statistical Learning Theory'', Springer-Verlag, 1995. ISBN 0-387-98780-0
* Vapnik, Vladimir N.; and Kotz, Samuel; ''Estimation of Dependences Based on Empirical Data'', Springer, 2006. ISBN 0-387-30865-2, 510 pages [this is a reprint of Vapnik's early book describing philosophy behind SVM approach. The 2006 Appendix describes recent development].
* Fradkin, Dmitriy; and Muchnik, Ilya; ''[https://web.archive.org/web/20161019164722/http://paul.rutgers.edu/~dfradkin/papers/svm.pdf Support Vector Machines for Classification]'' in Abello, J.; and Carmode, G. (Eds); ''Discrete Methods in Epidemiology'', DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 70, pp.&nbsp;13–20, 2006. Succinctly describes theoretical ideas behind SVM.
* Bennett, Kristin P.; and Campbell, Colin; ''[http://kdd.org/exploration_files/bennett.pdf Support Vector Machines: Hype or Hallelujah?] {{Wayback|url=http://kdd.org/exploration_files/bennett.pdf |date=20160909083150 }}'', SIGKDD Explorations, 2, 2, 2000, 1–13. Excellent introduction to SVMs with helpful figures.
* Ivanciuc, Ovidiu; ''[http://www.ivanciuc.org/Files/Reprint/Ivanciuc_SVM_CCR_2007_23_291.pdf Applications of Support Vector Machines in Chemistry] {{Wayback|url=http://www.ivanciuc.org/Files/Reprint/Ivanciuc_SVM_CCR_2007_23_291.pdf |date=20160717052402 }}'', in ''Reviews in Computational Chemistry'', Volume 23, 2007, pp.&nbsp;291–400.
* Catanzaro, Bryan; Sundaram, Narayanan; and Keutzer, Kurt; ''[https://web.archive.org/web/20120302180102/http://www.eecs.berkeley.edu/~catanzar/icml2008.pdf Fast Support Vector Machine Training and Classification on Graphics Processors]'', in ''International Conference on Machine Learning'', 2008
* Campbell, Colin; and Ying, Yiming; ''[http://www.morganclaypool.com/doi/abs/10.2200/S00324ED1V01Y201102AIM010 Learning with Support Vector Machines] {{Wayback|url=http://www.morganclaypool.com/doi/abs/10.2200/S00324ED1V01Y201102AIM010 |date=20210930143814 }}'', 2011, Morgan and Claypool. ISBN 978-1-60845-616-1.
* Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137.
{{refend}}

== 外部链接 ==
* [https://web.archive.org/web/20180627015707/https://www.support-vector.net/ www.support-vector.net]  The key book about the method, "An Introduction to Support Vector Machines" with online software
* Burges, Christopher J. C.; [http://research.microsoft.com/en-us/um/people/cburges/papers/svmtutorial.pdf A Tutorial on Support Vector Machines for Pattern Recognition] {{Wayback|url=http://research.microsoft.com/en-us/um/people/cburges/papers/svmtutorial.pdf |date=20161130181730 }}, Data Mining and Knowledge Discovery 2:121–167, 1998
* [http://www.kernel-machines.org www.kernel-machines.org] {{Wayback|url=http://www.kernel-machines.org/ |date=20061104065824 }} ''(general information and collection of research papers)''
* [http://www.support-vector-machines.org www.support-vector-machines.org] {{Wayback|url=http://www.support-vector-machines.org/ |date=20200220024920 }} ''(Literature, Review, Software, Links related to Support Vector Machines&nbsp;— Academic Site)''
* [https://svmtutorial.online svmtutorial.online] {{Wayback|url=https://svmtutorial.online/ |date=20190112172813 }} A simple introduction to SVM, easily accessible to anyone with basic background in mathematics
* [http://videolectures.net/Top/Computer_Science/Machine_Learning/Kernel_Methods/Support_Vector_Machines/ videolectures.net] {{Wayback|url=http://videolectures.net/Top/Computer_Science/Machine_Learning/Kernel_Methods/Support_Vector_Machines/ |date=20161027192005 }} ''(SVM-related video lectures)''
* Karatzoglou, Alexandros et al.; [http://www.jstatsoft.org/v15/i09/paper Support Vector Machines in R] {{Wayback|url=http://www.jstatsoft.org/v15/i09/paper |date=20150828080222 }}, Journal of Statistical Software April 2006, Volume 15, Issue 9.
* [http://www.csie.ntu.edu.tw/~cjlin/libsvm/ libsvm] {{Wayback|url=http://www.csie.ntu.edu.tw/~cjlin/libsvm/ |date=20061023194316 }}, [[LIBSVM]] is a popular library of SVM learners
* [http://www.csie.ntu.edu.tw/~cjlin/liblinear/ liblinear] {{Wayback|url=http://www.csie.ntu.edu.tw/~cjlin/liblinear/ |date=20161118234206 }} is a library for large linear classification including some SVMs
* [https://web.archive.org/web/20100227221243/http://shark-project.sourceforge.net/ Shark] is a [[C++]] machine learning library implementing various types of SVMs
* [http://dlib.net/ml.html dlib] {{Wayback|url=http://dlib.net/ml.html |date=20161028061508 }} is a C++ library for working with kernel methods and SVMs
* [https://web.archive.org/web/20150419060655/http://svmlight.joachims.org/ SVM light] is a collection of software tools for learning and classification using SVM
* [http://cs.stanford.edu/people/karpathy/svmjs/demo/ SVMJS live demo] {{Wayback|url=http://cs.stanford.edu/people/karpathy/svmjs/demo/ |date=20130505185215 }} is a GUI demo for [[JavaScript]] implementation of SVMs
* [https://github.com/nickgillian/grt Gesture Recognition Toolkit] {{Wayback|url=https://github.com/nickgillian/grt |date=20170121213156 }} contains an easy to use wrapper for [http://www.csie.ntu.edu.tw/~cjlin/libsvm/ libsvm] {{Wayback|url=http://www.csie.ntu.edu.tw/~cjlin/libsvm/ |date=20061023194316 }}

{{Authority control}}
[[Category:支持向量機| ]]
[[Category:分類演算法]]
[[Category:统计分类]]