1,526
个编辑
更改
创建页面，内容为“{{#seo: |keywords=分类,支持向量机,集智 |description=分类,支持向量机,集智 }} 在机器学习中，支持向量机（support vector machine，…”
{{#seo:
|keywords=分类,支持向量机,集智
|description=分类,支持向量机,集智
}}
在[[机器学习]]中，支持向量机（support vector machine，常简称为SVM，又名支持向量网络<ref name="cortes95">[https://en.wikipedia.org/wiki/Corinna_Cortes Cortes, Corinna]; Vapnik, Vladimir N. (1995). "Support-vector networks". [https://en.wikipedia.org/wiki/Machine_Learning_(journal) Machine Learning]. 20 (3): 273–297. doi:10.1007/BF00994018</ref>）指的是一种有[[监督式学习]]模型及其相关的学习[[算法]]，广泛用于[https://zh.wikipedia.org/wiki/%E5%88%86%E7%B1%BB%E9%97%AE%E9%A2%98 分类]及[https://zh.wikipedia.org/wiki/%E8%BF%B4%E6%AD%B8%E5%88%86%E6%9E%90 回归分析]。当给定一组训练实例，并标记这些训练实例属于两个类别的其中之一，SVM训练算法基于这些实例创建一个模型将新的实例归类为两个类别中的一个，使其成为非概率[[二元线性分类器]](尽管SVM中有些方法如[https://en.wikipedia.org/wiki/Platt_scaling 概率输出]会在概率分类集合中使用)。SVM模型将实例表示为空间中的点，使得不同类别的实例被尽可能明显的间隔所分开。然后，新的实例将被映射到同一空间中，并基于它们落在间隔的哪一侧来预测其所属类别。
除了进行线性分类之外，SVM还可以使用所谓的[https://zh.wikipedia.org/w/index.php?title=%E6%A0%B8%E6%8A%80%E5%B7%A7&action=edit&redlink=1 核技巧]实现有效地非线性分类，将其输入实例映射到高维特征空间中。对于未标记数据，无法进行有监督式学习，但是可以使用[[非监督式学习]]进行训练。非监督式学习会尝试找出数据到簇的自然聚类，并将新数据映射到这些已形成的簇中。Hava Siegelmann 和 Vladimir Vapnik创造了支持向量聚类<ref name="ben01">Ben-Hur, Asa; Horn, David; Siegelmann, Hava; and Vapnik, Vladimir N.; "Support vector clustering"; (2001); Journal of Machine Learning Research, 2: 125–137</ref>算法，该算法利用支持向量机算法生成的支持向量统计数据对未标记的数据分类。这一算法也成为了工业应用最广泛的聚类算法之一。
==动机==
[https://en.wikipedia.org/wiki/Statistical_classification 数据分类]是机器学习中的一项常见任务。 假设给定的一些[https://en.wikipedia.org/wiki/Data_point 数据点]各自属于两个类其中之一，而数据分类的目标是利用这些数据确定新给定的数据点将在哪个类中。对于支持向量机来说，数据点被视为<math>p</math>维向量，而我们想知道是否可以用<math>p-1</math>维[https://en.wikipedia.org/wiki/Hyperplane 超平面]来分开这些点。这就是所谓的[https://en.wikipedia.org/wiki/Linear_classifier 线性分类器]。可能存在许多超平面可以把数据分类，而最佳超平面的一个合理选择标准是找出把两个类以[https://en.wikipedia.org/wiki/Maximum-margin_hyperplane 最大间隔分开的超平面]。
[[File:220px-Svm_separating_hyperplanes_(SVG).svg.png|220px|thumb|right|<math>H_1</math> 不能把类别分开。<math>H_{2}</math> 可以，但只有很小的间隔。<math>H_3</math> 以最大间隔将它们分开。]]
所以，我们要选择的超平面是实现距离超平面最近点之间距离间隔最大的。如果存在这样的超平面，则可将其称为最大间隔超平面，而基于其定义的线性分类器被称为最大间隔分类器，或叫做最佳稳定性[https://en.wikipedia.org/wiki/Perceptron 感知器]。
==定义==
更正式地来说，支持向量机在高维或无限维空间中构造超平面或超平面集合，其可用于[https://en.wikipedia.org/wiki/Statistical_classification 分类]、[https://en.wikipedia.org/wiki/Regression_analysis 回归]或类似异常检测的其他任务<ref name="archived'>"[http://scikit-learn.org/stable/modules/svm.html Archived copy]". [https://web.archive.org/web/20171108151644/http://scikit-learn.org/stable/modules/svm.html Archived] from the original on 2017-11-08. Retrieved 2017-11-08</ref>。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的[https://en.wikipedia.org/wiki/Generalization_error 泛化误差]<ref name="trevor">Trevor_Hastie,_Robert_Tibshirani,_Jerome_Friedman - The elements of Statistical Learning Pg. 134</ref>。
[[File:Kernel_Machine.png|300px|thumb|right|核机器]]
尽管原始问题可能是在有限维空间中陈述的，但用于区分的集合在该空间中往往不是[https://en.wikipedia.org/wiki/Linear_separability 线性可分]的。为此，有人提出将原始的限维空间映射到维数高得多的空间中，在这种空间中进行分离可能会更容易。为了保证计算负荷合理，人们选择适合该问题的核函数 k(x,y) 来定义SVM方案使用的映射<ref name="press07">*Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). [http://apps.nrbook.com/empanel/index.html#pg=883 "Section 16.5. Support Vector Machines"]. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. [https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=883 Archived] from the original on 2011-08-11.</ref>，以确保用原始空间中的变量可以很容易计算[https://en.wikipedia.org/wiki/Dot_product 点积]。高维空间中的超平面指的是与该空间中的某向量的点积是常数的点的集合。定义超平面的向量可以被选择成为在数据集合中出现的[https://en.wikipedia.org/wiki/Feature_vector 特征向量]<math>x_i</math>的图像的参数 <math>\alpha _i</math>的线性组合。通过选择超平面，被映射到超平面上的[https://en.wikipedia.org/wiki/Feature_space 特征空间]中的点集 <math>x</math> 由以下关系定义：<small><math>\sum_i\alpha _ik(x_i,x)=constant</math></small>. 需要注意的是，如果随着<math>y</math> 逐渐远离 <math>x</math>， <math>{k}(x,y) </math>变小，则求和中的每一项都是在衡量测试点 <math>x</math>与对应的数据集中点 <math>x_i</math>的接近程度。在这种情况下，上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近度。也要注意到，点<math>x</math>的集合映射到任何超平面的结果可以特别复杂，同时也允许复杂得多的在原始空间里为非凸集合间的分离。
== 应用==
SVM可以用于解决多种真实世界的问题：
*用于[https://zh.wikipedia.org/wiki/%E6%96%87%E6%A1%A3%E5%88%86%E7%B1%BB 文本和超文本的分类]，在归纳和[https://en.wikipedia.org/wiki/Transduction_(machine_learning) 转导]方法中都可以显著减少所需要的有类标的样本数。
*用于[https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E8%A7%86%E8%A7%89 图像分类]。实验结果显示：相比于传统的查询优化方案，在经过三到四轮相关反馈之后，支持向量机能够获取明显更高的搜索准确度。这同样也适用于[https://zh.wikipedia.org/wiki/%E5%9B%BE%E5%83%8F%E5%88%86%E5%89%B2 图像分区]系统，比如使用Vapnik所建议用特权方法的修改版本SVM的那些图像分区系统。<ref name="vapnlk14">Vapnik, Vladimir N.: Invited Speaker. IPMU Information Processing and Management 2014)</ref><ref name="barghout15">Barghout, Lauren. [https://pdfs.semanticscholar.org/917f/15d33d32062bffeb6401eee9fe71d16d6a84.pdf "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>
*用于手写字体[https://zh.wikipedia.org/wiki/%E6%89%8B%E5%86%99%E8%AF%86%E5%88%AB 识别]。<ref name="decoste02">DeCoste, Dennis (2002). [https://people.eecs.berkeley.edu/~malik/cs294/decoste-scholkopf.pdf "Training Invariant Support Vector Machines"] (PDF). Machine Learning. 46: 161–190.</ref>
*SVM算法已被广泛应用于生物和其他科学。SVM用于分类蛋白质，可达到90%以上分类准确度。基于支持向量机权重的[https://en.wikipedia.org/wiki/Resampling_(statistics)#Permutation_tests 置换测试]可作为一种机制，用于解释的支持向量机模型。<ref name="gaonkar">Gaonkar, Bilwaj; Davatzikos, Christos; "Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification"</ref><ref name="cuingnet11">Cuingnet, Rémi; Rosso, Charlotte; Chupin, Marie; Lehéricy, Stéphane; Dormont, Didier; Benali, Habib; Samson, Yves; and Colliot, Olivier; [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3767485/ "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 name="statnikov06">Statnikov, Alexander; Hardin, Douglas; & Aliferis, Constantin; (2006); [http://www.aramislab.fr/perso/colliot/files/media2011_remi_published.pdf "Using SVM weight-based methods to identify causally relevant and non-causally relevant variables"], Sign, 1, 4</ref>在生命科学领域，利用支持向量机的Posthoc Posthoc interpretation进行特征识别，并用于预测是一个相对较新的研究方向，而且有着特殊的意义。
==历史==
最初的SVM算法是[https://zh.wikipedia.org/wiki/%E5%BC%97%E6%8B%89%E5%9F%BA%E7%B1%B3%E5%B0%94%C2%B7%E4%B8%87%E6%99%AE%E5%B0%BC%E5%85%8B Vladimir N. Vapnik]和[https://en.wikipedia.org/wiki/Alexey_Chervonenkis Alexey Ya. Chervonenkis] 于1963年发明。1992年，Bernhard E. Boser、Isabelle M. Guyon和[https://zh.wikipedia.org/wiki/%E4%BA%9E%E6%AD%B7%E5%85%8B%E5%A1%9E%C2%B7%E6%BE%A4%E8%8C%83%E8%98%AD%E5%82%91%E6%96%AF Vladimir N. Vapnik]提出了一种通过将[https://en.wikipedia.org/wiki/Kernel_method 核技巧]应用于最大间隔超平面来创建非线性分类器的方法。<ref name="boser92"> Boser, Bernhard E.; Guyon, Isabelle M.; Vapnik, Vladimir N. (1992). "A training algorithm for optimal margin classifiers". Proceedings of the fifth annual workshop on Computational learning theory – COLT '92. p. 144. doi:10.1145/130385.130401. ISBN 089791497X.</ref>现行标准的前身（软间隔）由[https://en.wikipedia.org/wiki/Corinna_Cortes Corinna Cortes]和Vapnik于1993年提出，并于1995年发表。
==线性SVM==
按照以下形式给出 <math> n</math> 点测试集：
<math> (\overrightarrow{x_{1}},y_{1}),...,(\overrightarrow{x_{n}},y_{n}) </math>
其中 <math>y_1</math> 是 1 或者 −1，表明点 <math>\overrightarrow{x_i}</math> 所属的类。 <math>\overrightarrow{x_i}</math>中每个都是一个 <math>p</math> 维实向量。我们希望找出可将 <math>y_i=1</math>的点集<math>\overrightarrow{x_i}</math> 与 <math>y_i=-1</math>的点集分开的 “最大间隔超平面”，使得超平面与最近的点<math>\overrightarrow{x_i}</math> 之间的距离最大化。
任何[https://zh.wikipedia.org/wiki/%E8%B6%85%E5%B9%B3%E9%9D%A2 超平面]都可以表示为满足下面方程的点集 <math>\overrightarrow{x_i}</math>
[[File:SVMClassifier2.svg.png|200px|thumb|right|设样本属于两个类，用该样本训练SVM得到的最大间隔超平面。在超平面上的样本点也称为支持向量。]]
<math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b=0</math>
其中 <math>\overrightarrow{\omega }</math>（不必是归一化的）是该超平面的[https://zh.wikipedia.org/wiki/%E6%B3%95%E7%BA%BF 法向量]，其更像是[https://en.wikipedia.org/wiki/Hesse_normal_form 海赛正规形式]，但 <math>\overrightarrow{\omega }</math>不必是单位向量。参数<math> \frac{b}{\left \| \overrightarrow{\omega } \right \|}</math>决定了从原点沿法向量<math>\overrightarrow{\omega }</math>到超平面的偏移量。
===硬间隔===
如果这些训练数据是[https://en.wikipedia.org/wiki/Linearly_separable 线性可分]的，我们可以选择两个平行超平面分离这两类数据，使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为“间隔”，最大间隔超平面是位于它们正中间的超平面。这些超平面可以由以下方程式表示：
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b=1</math> (所有位于或者高于这条分界线的属于一类，标签为1）
或是
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b=-1</math>(所有位于或者低于这条分界线的属于一类，标签为-1）
利用几何方法不难得到这两个超平面之间的距离是<math> \frac{2}{\left \| \overrightarrow{\omega } \right \|}</math><ref name="stack">[https://math.stackexchange.com/q/1305925/168764 "Why does the SVM margin is $\frac{2}{\-\mathbf{w}\-}$"].Mathematics Stack Exchange.</ref>，因此要使两平面间的距离最大，我们需要实现<math>\left \| \overrightarrow{\omega } \right \|</math>最小化。同时，为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的 <math>i</math> 满足如下条件之一：
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b>or= 1 </math>, 若<math>y_i=1</math>
或是：
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b\leq 1</math>, 若<math>y_i=-1</math>
这些限制表明每个数据点都必须位于间隔的正确一侧。
这两个式子也可以写成如下形式：
: <math>y_i(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)\geq 1</math>, 对所有<math>1\leq i\leq 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,...,n </math>”</blockquote>这个问题的解 <math>\vec w</math> 与 <math>b</math> 决定了我们的分类器 <math>\overrightarrow{x} \mapsto sgn(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)</math>.
这一几何描述的一个显而易见却重要的结果是，最大间隔超平面完全是由最靠近它的那些 <math> \overrightarrow{x}_i</math> 确定，这些 <math> \overrightarrow{x}_i</math> 叫做'''支持向量'''。
=== 软间隔 ===
为了将SVM扩展到数据线性不可分的情况，我们引入[https://en.wikipedia.org/wiki/Hinge_loss 铰链损失]函数，
: <math>max(0,1-y_{i}(\overrightarrow{\omega }\cdot \overrightarrow{x_{i}}-b))</math>.
注意<math>y_i</math>是第<math>i</math>个目标（例如，在本例中，1或者-1），<math>\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b</math>是当前输出。
当约束条件 (1) 满足时（也就是如果 <math>\overrightarrow{x}_i</math> 位于边距的正确一侧）此函数为零。对于位于间隔的错误一侧的数据，该函数的值与该数据与间隔的距离成正比。
当我们希望其最小化：<blockquote><math>[\frac{1}{n}\sum_{i=1}^{n}max(0,1-y_i(\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b))]+\lambda \left \| \overrightarrow{\omega } \right \|^{2}</math>,</blockquote>其中参数 <math>\lambda</math> 用来权衡增加间隔大小与确保 <math>\overrightarrow{x_i}</math> 位于间隔的正确一侧之间的关系。因此，对于足够小的 <math>\lambda</math> 值，如果输入数据是可以线性分类的，则软间隔SVM与硬间隔SVM将表现相同，但即使数据不可线性分类，仍能学习出可行的分类规则。
== 非线性分类 ==
[[File:Kernel_Machine.png|400px|thumb|核机器]]
Vapnik在1963年提出的最原始的最大间隔超平面算法构造了一个[[线性分类器]]。而1992年，Bernhard E. Boser、Isabelle M. Guyon和[https://zh.wikipedia.org/wiki/%E5%BC%97%E6%8B%89%E5%9F%BA%E7%B1%B3%E5%B0%94%C2%B7%E4%B8%87%E6%99%AE%E5%B0%BC%E5%85%8B Vladimir N. Vapnik]提出了一种通过将[https://en.wikipedia.org/wiki/Kernel_method 核技巧]（由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|journal = Automation and Remote Control|volume = 25|pages = 821–837}}</ref>最先提出）应用于最大边界超平面来创建非线性分类器的方法。<ref name="boser92"></ref> 除了把[https://zh.wikipedia.org/wiki/%E7%82%B9%E7%A7%AF 点积]换成了非线性[https://zh.wikipedia.org/wiki/%E7%A7%AF%E5%88%86%E5%8F%98%E6%8D%A2 核]函数，所得到的算法形式上与前者类似。这种变化允许算法在变换后的[https://en.wikipedia.org/wiki/Feature_(machine_learning)#Extensions 特征空间]中拟合最大间隔超平面。这类变换可以是非线性的，但变换空间是高维的；尽管分类器是变换后的特征空间中的超平面，但它在原始输入空间中可以是非线性的。
值得注意的是，更高维的特征空间增加了支持向量机的[https://zh.wikipedia.org/wiki/%E6%B3%9B%E5%8C%96%E8%AF%AF%E5%B7%AE 泛化误差]，但是当给定了足够多的样本，算法仍能表现良好。<ref>Jin, Chi; Wang, Liwei (2012). [http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound Dimensionality dependent PAC-Bayes margin bound]. Advances in Neural Information Processing Systems. [https://web.archive.org/web/20150402185336/http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound Archived] from the original on 2015-04-02.</ref>
常见的核函数包括：
* [https://zh.wikipedia.org/wiki/%E9%BD%8A%E6%AC%A1%E5%A4%9A%E9%A0%85%E5%BC%8F 齐次多项式]：<math>k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j})^d</math>
* [https://en.wikipedia.org/wiki/Polynomial_kernel 非齐次多项式]：<math>k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j} + 1)^d</math>
* 高斯[https://zh.wikipedia.org/wiki/%E5%BE%84%E5%90%91%E5%9F%BA%E5%87%BD%E6%95%B0%E6%A0%B8 径向基函数]：<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>
* [https://zh.wikipedia.org/wiki/%E5%8F%8C%E6%9B%B2%E5%87%BD%E6%95%B0 双曲正切]：<math>k(\vec{x_i},\vec{x_j})=\tanh(\kappa \vec{x_i} \cdot \vec{x_j}+c)</math>，其中一些（而非所有）<math> \kappa </math>大于0， 且 <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)简化为[https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92 二次规划]问题的经典方法。之后会讨论一些最近才出现的方法，如次梯度下降法和坐标下降法。
=== 原型 ===
求方程式(2)最小解可用下面的方式改写为目标函数可微的约束优化问题。
对所有 <math>i\in \left \{ 1,...,n \right \}</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(\omega \cdot x_i-b)\geq 1-\zeta _i \,\text{ and }\zeta_i \geq 0,\text{for all }i.</math> </blockquote>这就叫做''原型''问题。
=== 对偶型 ===
通过求解上述问题的[https://en.wikipedia.org/wiki/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> 的二次函数，所以它可以通过[https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92 二次规划]算法高效地解出。
这里，变量 <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(\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b)=1\Leftrightarrow b=\overrightarrow{\omega }\cdot \overrightarrow{x_i}-y_i</math></blockquote>
得到偏移量 <math> b</math>。（注意由于 <math>y_i=\pm 1</math> 因而 <math>y_{i}^{-1}=y_{i}</math>）。
=== 核技巧 ===
[[File:220px-Kernel_trick_idea.svg.png|300px|thumb|right|SVM训练实例，核为：<math>\Phi \left ( \left ( a,b \right ) \right )=(a,b,a^{2}+b^{2})</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> \overrightarrow{\omega }=\sum_{i=1}^{n}c_iy_i\varphi (\overrightarrow{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的[https://zh.wikipedia.org/wiki/%E6%AC%A1%E6%A2%AF%E5%BA%A6%E6%B3%95 次梯度下降]算法直接用表达式<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> 的[https://zh.wikipedia.org/wiki/%E5%87%B8%E5%87%BD%E6%95%B0 凸函数]。因此，可以采用传统的[https://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95 梯度下降]（或[https://en.wikipedia.org/wiki/Stochastic_gradient_descent SGD]）方法，其不是在函数梯度的方向上前进，而是在从函数的[https://zh.wikipedia.org/wiki/%E6%AC%A1%E5%AF%BC%E6%95%B0 次梯度]中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 <math>n</math> 而增加或减少。<ref>Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew (2010-10-16). [https://link.springer.com/article/10.1007/s10107-010-0420-4 "Pegasos: primal estimated sub-gradient solver for SVM"]. Mathematical Programming. 127 (1): 3–30. [https://doi.org/10.1007/s10107-010-0420-4 doi:10.1007/s10107-010-0420-4]. [https://www.worldcat.org/issn/0025-5610 ISSN 0025-5610].</ref>
==== 坐标下降 ====
SVM的[https://en.wikipedia.org/wiki/Coordinate_descent 坐标下降]算法基于对偶问题
<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 \left \{ 1,...,n \right \}</math> 进行迭代，使系数 <math> c_i</math> 的方向与 <math> \partial f/ \partial c_i</math> 一致。然后，将所得的系数向量 <math> (c_1',\,\ldots,\,c_n')</math> 投影到满足给定约束的最接近的系数向量（通常使用欧氏距离）。然后重复该过程，直到获得接近最佳的系数向量。尽管已证明的性能保证很少，其所得的算法在实践中运行的非常快。<ref>Hsieh, Cho-Jui; Chang, Kai-Wei; Lin, Chih-Jen; Keerthi, S. Sathiya; Sundararajan, S. (2008-01-01). [https://dl.acm.org/citation.cfm?doid=1390156.1390208 "A Dual Coordinate Descent Method for Large-scale Linear SVM"]. Proceedings of the 25th International Conference on Machine Learning. ICML '08. New York, NY, USA: ACM: 408–415. [https://doi.org/10.1145/1390156.1390208 doi:10.1145/1390156.1390208] .[https://en.wikipedia.org/wiki/Special:BookSources/978-1-60558-205-4 ISBN 978-1-60558-205-4].</ref>
==经验风险最小化==
上文所描述的软间隔支持向量机是[https://en.wikipedia.org/wiki/Empirical_risk_minimization 经验风险最小化](ERM)算法用于[https://en.wikipedia.org/wiki/Hinge_loss 铰链损失(hinge loss)]的一个例子。从这方面看，支持向量机属于推断统计学算法的一个自然类，而它许多独特的特点都缘于合页损失的行为。这一观点可以提供对于SVMs如何工作以及为何有效这一问题更深入的了解，并让我们更好的分析他们的统计性质。
===风险最小化===
在监督学习中，给定一个训练实例集合<math>X_{1}...X_{n}</math> 及对应标签<math>y_{1}...y_{n}</math>，我们希望利用给定的<math>X_{n+1}</math>预测<math>y(n+1)</math>。为实现这一预测我们给出[https://en.wikipedia.org/wiki/Hypothesis 假设]，<math>f</math>，例如<math>f(X_{n+1})</math>是<math>y(n+1)</math>的一个“好”近似值。“好”近似值通常由[https://en.wikipedia.org/wiki/Loss_function 损失函数]<math>\ell(y,z)</math>定义，损失函数描述作为<math>y</math>的预测值<math>z</math>的不准确度。我们希望选择一个最小化[https://en.wikipedia.org/wiki/Loss_function#Expected_loss 期望风险]的假设：
<math>\varepsilon (f)=\mathbb{E}\left [ \ell(y_{n+1},f(X_{n+1})) \right ]</math>.
在大多数情况下，我们不知道<math>X_{n+1}</math>和<math>y(n+1)</math>的联合分布，因此，通常的策略是选择一个最小化经验风险的假设：
<math>\hat{\varepsilon }(f)=\frac{1}{n}\sum_{k=1}^{n}\ell(y_{k},f(X_{k}))</math>.
在某些关于随机变量<math>X_{k}</math>和<math>y_{k}</math>序列（例如由有限马尔可夫过程产生）的假设下，如果该假设集合足够小，那么随着<math>n</math>的增大，经验风险的最小化将近似接近期望风险的最小化。这一过程被叫做经验风险最小化，简称ERM。
===正则化和稳定性===
为了最小化问题有一个良好定义的解决方法，我们必须对所考虑的假设集合<math>\mathcal{H}</math>给出约束条件。如果<math>\mathcal{H}</math>是一个[https://zh.wikipedia.org/wiki/%E8%B3%A6%E7%AF%84%E5%90%91%E9%87%8F%E7%A9%BA%E9%96%93 赋范向量空间]（例如SVM），一个有效的特殊办法是仅考虑满足<math>\left \| f \right \|_{\mathcal H}<k</math>这一条件的假设<math> f</math>。这等同于添加一项“正则化惩罚”<math>\mathcal R(f)=\lambda \left \| f \right \|_{\mathcal H}</math>，并解决这一新的优化问题。
:<math>\hat f = \mathrm{arg}\min_{f \in \mathcal{H}} \hat \varepsilon(f) + \mathcal{R}(f).</math>
该方法被称作[https://en.wikipedia.org/wiki/Tikhonov_regularization 吉洪诺夫正则化]。
一般来说，<math>R(f)</math>可以衡量假设<math>f</math>的复杂度，因此更倾向于更简单的假设。
===SVM与铰链损失===
利用（软间隔）SVM分类器<math>\overrightarrow{\omega} ,b:x\mapsto sgn(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)</math>对以下表达式求最小化解：
:<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.</math>
从上述讨论我们可以看到，SVM技术等同于经验风险最小化加上吉洪诺夫正则化，此时的损失函数是[https://en.wikipedia.org/wiki/Hinge_loss 铰链损失]：
: <math>\ell(y,z) = \max\left(0, 1 - yz \right).</math>
在这一观点下, SVM与其他基础的[https://en.wikipedia.org/wiki/Statistical_classification#Linear_classifiers 分类算法]联系紧密，如 [https://en.wikipedia.org/wiki/Regularized_least_squares 正则化最小二乘法] and [[ 逻辑回归]]。这三者的不同在于损失函数的选择：正则化最小二乘法统计经验风险最小化使用[https://zh.wikipedia.org/wiki/%E5%88%86%E9%A1%9E%E5%95%8F%E9%A1%8C%E4%B9%8B%E6%90%8D%E5%A4%B1%E5%87%BD%E6%95%B8 平方损失函数]， <math>\ell_{sq}(y,z) = (y-z)^2</math>；逻辑回归使用[https://zh.wikipedia.org/wiki/%E5%88%86%E9%A1%9E%E5%95%8F%E9%A1%8C%E4%B9%8B%E6%90%8D%E5%A4%B1%E5%87%BD%E6%95%B8 对数损失函数]，
:<math>\ell_{\log}(y,z) = \ln(1 + e^{-yz}).</math>
====目标函数====
合页损失与其他损失函数区别主要在于“目标函数”，而目标函数使一对给定的随机变量<math>X,y</math>期望风险最小化。
特别的，在 <math>X = x</math>事件的条件下，让<math>y_x</math> 表示 <math>y</math>。在这个分类集合里，我们有：
: <math>y_x = \begin{cases} 1 & \text{with probability } p_x \\ -1 & \text{with probability } 1-p_x \end{cases}</math>
那么最理想分类器为：
:<math>f^*(x) = \begin{cases}1 & \text{if }p_x \geq 1/2 \\ -1 & \text{otherwise}\end{cases} </math>
对于平方损失，目标函数就是条件期望函数，<math>f_{sq}(x) </math><math>=\mathbb{E}[y_{x}]</math>；而对于对数损失，目标函数是逻辑函数，<math>f_{\log}(x) = \ln\left(p_x / ({1-p_x})\right)</math>。当这两个目标函数都是正确分类器，即 <math>\sgn(f_{sq}) = \sgn(f_\log) = f^*</math>，它们能给我们信息要比我们需要的更多。实际上，他们能给我们充足的信息来充分描绘<math> y_x</math>的分布。
在另一方面，合页损失的目标函数正是<math>f^*</math>。因此，在充分假设空间，或适当选择的核，SVM分类器会趋于可实现正确数据分类的最简单函数（ <math>\mathcal{R}</math>）。这一方面拓展了SVM的几何解释：对于线性分类，间隔在支持向量和最简单的最大间隔分类器之间的函数使得经验风险最小化。<ref>Rosasco, Lorenzo; De Vito, Ernesto; Caponnetto, Andrea; Piana, Michele; Verri, Alessandro (2004-05-01). [https://ieeexplore.ieee.org/document/6789841/?arnumber=6789841&abstractAccess=no&userType=inst "Are Loss Functions All the Same?"]. Neural Computation. 16 (5): 1063–1076. [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.6786 10.1.1.109.6786] Freely accessible. [https://doi.org/10.1162/089976604773135104 doi:10.1162/089976604773135104]. [https://www.worldcat.org/issn/0899-7667 ISSN 0899-7667]. [https://www.ncbi.nlm.nih.gov/pubmed/15070510 PMID 15070510].</ref>
----------------------
== 性质 ==
SVM属于广义[[线性分类器]]的一族，并且可以解释为[[感知机]]的延伸。它们也可以被认为是[https://en.wikipedia.org/wiki/Tikhonov_regularization 提克洛夫规范化]的特例。它们有一个特别的性质，就是可以同时最小化经验误差和最大化几何边缘区; 因此它们也被称为'''最大[https://en.wikipedia.org/wiki/Margin_classifier 间隔分类器]'''。
Meyer、Leisch和Hornik对SVM与其他分类器进行了比较。<ref>Meyer, David; Leisch, Friedrich; Hornik, Kurt (2003). "The support vector machine under test". Neurocomputing. 55: 169. [https://doi.org/10.1016/S0925-2312%2803%2900431-4 doi:10.1016/S0925-2312(03)00431-4].</ref>
=== 参数选择 ===
SVM的有效性取决于核函数、核参数和软间隔参数 ''C'' 的选择。
通常会选只有一个参数 ''<math>\gamma</math>'' 的高斯核。''C'' 和 <math>\gamma</math> 的最佳组合通常通过在 ''C'' 和 ''<math>\gamma</math>'' 为指数增长序列下[https://en.wikipedia.org/wiki/Hyperparameter_optimization#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>。通常情况下，使用[https://zh.wikipedia.org/wiki/%E4%BA%A4%E5%8F%89%E9%A9%97%E8%AD%89 交叉验证]来检查参数选择的每一个组合，并选择具有最佳交叉验证精度的参数。[https://en.wikipedia.org/wiki/Bayesian_optimization 贝叶斯优化]的一些近期工作可以用于选择C和γ，通常只需要评估比网格搜索少得多的参数组合。然后，使用所选择的参数在整个训练集上训练用于测试和分类新数据的最终模型。<ref>Hsu, Chih-Wei; Chang, Chih-Chung & Lin, Chih-Jen (2003). [https://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf A Practical Guide to Support Vector Classification] (PDF) (Technical report). Department of Computer Science and Information Engineering, National Taiwan University. [https://web.archive.org/web/20130625201224/http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf Archived] (PDF) from the original on 2013-06-25.</ref>
=== 问题 ===
SVM的潜在缺点包括以下方面：
* 需要对输入数据进行完全标记
* 未校准[https://en.wikipedia.org/wiki/Probabilistic_classification 类成员概率]——起源于Vapnik理论的SVM避免了在有限数据中估计概率。
* SVM仅直接适用于两类任务。因此，必须应用将多类任务减少到几个二元问题的算法；请参阅[https://en.wikipedia.org/wiki/Support_vector_machine#Multiclass_SVM 多类SVM]一节。
* 解出的模型的参数很难理解。
== 延伸 ==
===支持向量聚类===
支持向量聚类是一种建立在核函数上的类似方法，同样适用于无监督学习和数据挖掘。它被认为是[[数据科学]]中的一种基本方法。
===多元分类SVM===
多元分类SVM旨在应用支持向量机对实例赋上标签，标签是从一个含几种元素的有限集合拟定的。
主要的方法是将单独的[https://zh.wikipedia.org/wiki/%E5%A4%9A%E5%85%83%E5%88%86%E7%B1%BB 多元分类问题]降到多个[https://en.wikipedia.org/wiki/Binary_classification 二元分类]问题。<ref name="duan05">Duan, Kai-Bo; Keerthi, S. Sathiya (2005). "Which Is the Best Multiclass SVM Method? An Empirical Study". Multiple Classifier Systems. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS]. 3541. pp. 278–285. [https://doi.org/10.1007/11494683_28 doi:10.1007/11494683_28]. [https://en.wikipedia.org/wiki/International_Standard_Book_Number ISBN] [https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-26306-7 978-3-540-26306-7].</ref>通常有以下几种方法：<ref name="duan05"></ref><ref name="hsu02">Hsu, Chih-Wei & Lin, Chih-Jen (2002). [http://www.cs.iastate.edu/~honavar/multiclass-svm.pdf "A Comparison of Methods for Multiclass Support Vector Machines"] (PDF). IEEE Transactions on Neural Networks.</ref>
* 构造二元分类器区分(i)其中一个标签及剩余标签（一对多）或(ii)每一个对类（一对一）。一对多情况下对新实例进行分类由胜者全得策略完成，由最高输出函数的分类器分类（输出函数的分数必须标准化）。一对一情况下采用投票策略，每一分类器将实例赋给两类中的一类，最终拥有最多票数的类决定实例分类。
* [https://zh.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE 有向无环图]SVM (DAGSVM)<ref name="platt00"> Platt, John; [https://en.wikipedia.org/wiki/Nello_Cristianini Cristianini, Nello]; [https://en.wikipedia.org/wiki/John_Shawe-Taylor Shawe-Taylor], John (2000). [http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/DAGSVM.pdf "Large margin DAGs for multiclass classification"]. In Solla, Sara A.; Leen, Todd K.; and Müller, Klaus-Robert; eds. [http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/DAGSVM.pdf Advances in Neural Information Processing Systems (PDF)]. MIT Press. pp. 547–553. [https://web.archive.org/web/20120616221540/http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/DAGSVM.pdf Archived] (PDF) from the original on 2012-06-16.</ref>
* [https://en.wikipedia.org/wiki/Error_correction_code 纠错输出编码]<ref name="die95">Dietterich, Thomas G.; Bakiri, Ghulum (1995). [http://www.jair.org/media/105/live-105-1426-jair.pdf "Solving Multiclass Learning Problems via Error-Correcting Output Codes"] (PDF). Journal of Artificial Intelligence Research. 2: 263–286. [https://en.wikipedia.org/wiki/ArXiv arXiv]:[https://arxiv.org/abs/cs/9501101 cs/9501101] Bibcode:1995cs........1101D. [https://web.archive.org/web/20130509061344/http://www.jair.org/media/105/live-105-1426-jair.pdf Archived] (PDF) from the original on 2013-05-09.. </ref>
Crammer和Singer提议多元分类SVM将多类分类问题变成单个优化问题而不是分解为多个二元分类问题。<ref name="crammer01">Crammer, Koby & Singer, Yoram (2001). [http://jmlr.csail.mit.edu/papers/volume2/crammer01a/crammer01a.pdf "On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines"] (PDF). Journal of Machine Learning Research. 2: 265–292. [https://web.archive.org/web/20150829102651/http://jmlr.csail.mit.edu/papers/volume2/crammer01a/crammer01a.pdf Archived] (PDF) from the original on 2015-08-29.</ref>也可以参考Lee，Lin和Wahba的论文。<ref name="lee01">Lee, Yoonkyung; Lin, Yi & Wahba, Grace (2001). [http://www.interfacesymposia.org/I01/I2001Proceedings/YLee/YLee.pdf "Multicategory Support Vector Machines"] (PDF). Computing Science and Statistics. 33. [https://web.archive.org/web/20130617093314/http://www.interfacesymposia.org/I01/I2001Proceedings/YLee/YLee.pdf Archived] (PDF) from the original on 2013-06-17.</ref>
<ref name="lee04">Lee, Yoonkyung; Lin, Yi; Wahba, Grace (2004). "Multicategory Support Vector Machines". Journal of the American Statistical Association. 99 (465): 67. [https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1198/016214504000000098 10.1198/016214504000000098].</ref>
===转导支持向量机===
转导支持向量机拓展了SVMs，通过[https://en.wikipedia.org/wiki/Transduction_(machine_learning) 转导]法则，它们也可以在[[半监督学习]]中处理部分标注数据。除了训练集 <math>D</math>，学习器也被赋予一个待分类的测试实例集合。
:<math>\mathcal{D}^\star = \{ \vec{x}^\star_i \mid \vec{x}^\star_i \in \mathbb{R}^p\}_{i=1}^k \, </math>
转导支持向量机由以下主要的优化问题定义：<ref>Joachims, Thorsten; "[http://www1.cs.columbia.edu/~dplewis/candidacy/joachims99transductive.pdf Transductive Inference for Text Classification using Support Vector Machines]", ''Proceedings of the 1999 International Conference on Machine Learning (ICML 1999)'', pp. 200–209</ref>
最小化 (在 <math>{\vec{w}, b, \vec{y^\star}}</math>中)
: <math>\frac{1}{2}\|\vec{w}\|^2</math>
受约束于 (对任意 <math>i = 1, \dots, n</math> 和任意 <math>j = 1, \dots, k</math>)
: <math>y_i(\vec{w}\cdot\vec{x_i} - b) \ge 1,\,</math>
: <math>y^\star_j(\vec{w}\cdot\vec{x^\star_j} - b) \ge 1,</math>
以及
: <math>y^\star_{j} \in \{-1, 1\}.\,</math>
转导支持向量机由Vladimir N. Vapnik于1998年提出。
===结构化支持向量机===
支持向量机可以被拓展为[https://en.wikipedia.org/wiki/Structured_support_vector_machine 结构化的支持向量机]，推广后标签空间是结构化的并且可能具有无限的大小。
===回归===
[[File:440px-Svr_epsilons_demo.svg.png|300px|thumb|right|不同''ε''的支持向量回归（预测）。随着''ε''增大，预测对误差的敏感度降低。]]
[https://zh.wikipedia.org/wiki/%E8%BF%B4%E6%AD%B8%E5%88%86%E6%9E%90 回归] 形式的支持向量机于1996年由[https://zh.wikipedia.org/wiki/%E5%BC%97%E6%8B%89%E5%9F%BA%E7%B1%B3%E5%B0%94%C2%B7%E4%B8%87%E6%99%AE%E5%B0%BC%E5%85%8B Vladimir N. Vapnik], Harris Drucker, Christopher J. C. Burges, Linda Kaufman and Alexander J. Smola提出。<ref>Drucker, Harris; Burges, Christopher J. C.; Kaufman, Linda; Smola, Alexander J.; and Vapnik, Vladimir N. (1997); "[http://papers.nips.cc/paper/1238-support-vector-regression-machines.pdf Support Vector Regression Machines]", in ''Advances in Neural Information Processing Systems 9, NIPS 1996'', 155–161, MIT Press.</ref>该方法称为支持向量回归（SVR）。支持向量分类的模型仅依靠训练数据的子集，因为模型的损失函数不关心边缘以外的训练点。类似的，SVR模型仅依靠因为模型的损失函数不关心边缘以外的训练点，因为模型的损失函数忽视了接近模型预测的训练数据。另一形式的SVM，即[https://en.wikipedia.org/wiki/Least_squares_support_vector_machine 最小二乘支持向量机] 已经由Suykens和Vandewalle提出。<ref>Suykens, Johan A. K.; Vandewalle, Joos P. L.; "[https://lirias.kuleuven.be/bitstream/123456789/218716/2/Suykens_NeurProcLett.pdf Least squares support vector machine classifiers]", ''Neural Processing Letters'', vol. 9, no. 3, Jun. 1999, pp. 293–300</ref>
训练原始SVR意味着求解<ref>{{cite journal |last1=Smola |first1=Alex J. |first2=Bernhard |last2=Schölkopf |title=A tutorial on support vector regression |journal=Statistics and Computing |volume=14 |issue=3 |year=2004 |pages=199–222 |url=http://eprints.pascal-network.org/archive/00000856/01/fulltext.pdf |deadurl=no |archiveurl=https://web.archive.org/web/20120131193522/http://eprints.pascal-network.org/archive/00000856/01/fulltext.pdf |archivedate=2012-01-31 }}</ref>
:minimize <math>\frac{1}{2} \|w\|^2 </math>
:subject to <math>\begin{cases}
y_i - \langle w, x_i \rangle - b \le \varepsilon \\
\langle w, x_i \rangle + b - y_i \le \varepsilon
\end{cases}</math>
其中<math>x_i</math>是目标值为<math>y_i</math>的训练样本。内积加上截距<math>\langle w, x_i \rangle + b</math>是样本的预测值，<math>\varepsilon</math>是一个作为限制的自由参量：所有的预测值都应与真实预测值在<math>\varepsilon</math>的范围内。通常加入松弛变量来使不可行情况下产生误差和近似值。
===贝叶斯SVM===
2011年，Polson和Scott运用[https://en.wikipedia.org/wiki/Convolutional_neural_network#Artificial_data 数据增强]在SVM中加入贝叶斯解释。<ref> Polson, Nicholas G.; Scott, Steven L. (2011). "Data Augmentation for Support Vector Machines". Bayesian Analysis. 6 (1): 1–23. [https://doi.org/10.1214/11-BA601 doi:10.1214/11-BA601].</ref>在这一方法中，SVM被视为[[ 概率图模型]]（参数由概率分布联系）。这一延伸视角使得贝叶斯方法应用于SVMs，例如灵活特征模型，自动[https://en.wikipedia.org/wiki/Hyperparameter_(machine_learning) 超参数调优]，以及[https://en.wikipedia.org/wiki/Posterior_predictive_distribution 预测不确定性量化]。近期，一种可标度的贝叶斯SVM模型由Wenzel等提出来实现贝叶斯SVM在[https://zh.wikipedia.org/wiki/%E5%A4%A7%E6%95%B8%E6%93%9A 大数据]上的应用。<ref>Wenzel, Florian; Galy-Fajou, Theo; Deutsch, Matthäus; Kloft, Marius (2017). "Bayesian Nonlinear Support Vector Machines for Big Data". Machine Learning and Knowledge Discovery in Databases (ECML PKDD). [https://arxiv.org/abs/1707.05532 arXiv:1707.05532]. [http://adsabs.harvard.edu/abs/2017arXiv170705532W Bibcode:2017arXiv170705532W].</ref>
== 实现 ==
最大间隔超平面的参数是通过求解优化得到的。有几种专门的算法可用于快速解决由SVM产生的[https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92 QP]问题，它们主要依靠启发式算法将问题分解成更小、更易于处理的子问题。
另一种方法是使用[https://en.wikipedia.org/wiki/Interior-point_method 内点法]，其使用类似[https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95 牛顿法]的迭代找到[https://zh.wikipedia.org/wiki/%E5%8D%A1%E7%BE%85%E9%9C%80%EF%BC%8D%E5%BA%AB%E6%81%A9%EF%BC%8D%E5%A1%94%E5%85%8B%E6%A2%9D%E4%BB%B6 卡罗需-库恩-塔克条件]下原型和对偶型的解。<ref>Ferris, Michael C.; Munson, Todd S. (2002). [http://www.cs.wisc.edu/~ferris/papers/siopt-svm.pdf "Interior-Point Methods for Massive Support Vector Machines"] (PDF). SIAM Journal on Optimization. 13 (3): 783. [https://doi.org/10.1137/S1052623400374379 doi:10.1137/S1052623400374379]. [https://web.archive.org/web/20081204224416/http://www.cs.wisc.edu/~ferris/papers/siopt-svm.pdf Archived] (PDF) from the original on 2008-12-04.</ref>
这种方法不是去解决一系列分解问题，而是直接完全解决该问题。为了避免求解核矩阵很大的线性系统，在核技巧中经常使用矩阵的低秩近似。
另一个常见的方法是普莱特的[https://zh.wikipedia.org/wiki/%E5%BA%8F%E5%88%97%E6%9C%80%E5%B0%8F%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95 序列最小优化算法]（SMO），它把问题分成了若干个可以解析求解的二维子问题，这样就可以避免使用数值优化算法和矩阵存储。<ref>Platt, John C. (1998). [http://research.microsoft.com/pubs/69644/tr-98-14.pdf Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines] (PDF). NIPS. [https://web.archive.org/web/20150702075055/http://research.microsoft.com/pubs/69644/tr-98-14.pdf Archived] (PDF) from the original on 2015-07-02.</ref>
线性支持向量机的特殊情况可以通过用于优化其类似问题[https://zh.wikipedia.org/wiki/%E9%82%8F%E8%BC%AF%E8%BF%B4%E6%AD%B8 逻辑回归]的同类算法更高效求解；这类算法包括[https://en.wikipedia.org/wiki/Stochastic_gradient_descent 次梯度下降法]（如PEGASOS<ref>Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan (2007). [http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf Pegasos: Primal Estimated sub-GrAdient SOlver for SVM] (PDF). ICML. [https://web.archive.org/web/20131215051700/http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf Archived] (PDF) from the original on 2013-12-15.</ref>）和[https://zh.wikipedia.org/wiki/%E5%9D%90%E6%A0%87%E4%B8%8B%E9%99%8D%E6%B3%95 坐标下降法]（如LIBLINEAR<ref>Fan, Rong-En; Chang, Kai-Wei; Hsieh, Cho-Jui; Wang, Xiang-Rui; Lin, Chih-Jen (2008). [https://www.csie.ntu.edu.tw/~cjlin/papers/liblinear.pdf "LIBLINEAR: A library for large linear classification"] (PDF). [https://en.wikipedia.org/wiki/Journal_of_Machine_Learning_Research Journal of Machine Learning Research]. 9: 1871–1874.</ref>）。LIBLINEAR有一些引人注目的训练时间上的特性。每次收敛迭代花费在读取训练数据上的时间是线性的，而且这些迭代还具有[https://zh.wikipedia.org/wiki/%E6%94%B6%E6%96%82%E9%80%9F%E5%BA%A6 Q-线性收敛]特性，使得算法非常快。
一般的核SVM也可以用[https://en.wikipedia.org/wiki/Stochastic_gradient_descent 次梯度下降法]（P-packSVM<ref>Allen Zhu, Zeyuan; Chen, Weizhu; Wang, Gang; Zhu, Chenguang; Chen, Zheng (2009). [http://people.csail.mit.edu/zeyuan/paper/2009-ICDM-Parallel.pdf P-packSVM: Parallel Primal grAdient desCent Kernel SVM] (PDF). ICDM. [https://web.archive.org/web/20140407095709/http://people.csail.mit.edu/zeyuan/paper/2009-ICDM-Parallel.pdf Archived] (PDF) from the original on 2014-04-07.
</ref>）更快求解，在允许[https://zh.wikipedia.org/wiki/%E5%B9%B6%E8%A1%8C%E8%AE%A1%E7%AE%97 并行化]时求解速度尤其快。
许多机器学习工具包都可以使用核SVM，有[https://en.wikipedia.org/wiki/LIBSVM LIBSVM]、[https://zh.wikipedia.org/wiki/MATLAB MATLAB]、[http://support.sas.com/documentation/cdl/en/whatsnew/64209/HTML/default/viewer.htm#emdocwhatsnew71.htm SAS]、SVMlight、[https://cran.r-project.org/package=kernlab kernlab]、[https://en.wikipedia.org/wiki/Scikit-learn scikit-learn]、[https://en.wikipedia.org/wiki/Shogun_(toolbox) Shogun]、[https://zh.wikipedia.org/wiki/Weka Weka]、[http://image.diku.dk/shark/ Shark]、[https://mloss.org/software/view/409/ JKernelMachines]、[https://zh.wikipedia.org/wiki/OpenCV OpenCV]等。
== 简单实现与演示 ==
<syntaxhighlight lang="python">
from sklearn.datasets.samples_generator import make_blobs
# revised from https://github.com/Madhu009/Deep-math-machine-learning.ai/blob/master/SVM-FromScratch.ipynb
# data preparation
(X,y) = make_blobs(n_samples=50,n_features=2,centers=2,cluster_std=1.05,random_state=40)
#we need to add 1 to X values (we can say its bias)
X1 = np.c_[np.ones((X.shape[0])),X]
plt.scatter(X1[:,1],X1[:,2],marker='o',c=y)
plt.axis([-5,10,-12,-1])
plt.show()
</syntaxhighlight>
[[File:未分类.png|800px]]
<syntaxhighlight lang="python">
postiveX=[]
negativeX=[]
for i,v in enumerate(y):
if v==0:
negativeX.append(X[i])
else:
postiveX.append(X[i])
#our data dictionary
data_dict = {-1:np.array(negativeX), 1:np.array(postiveX)}
#all the required variables
w=[] #weights 2 dimensional vector
b=[] #bias
max_feature_value=float('-inf')
min_feature_value=float('+inf')
for yi in data_dict:
if np.amax(data_dict[yi])>max_feature_value:
max_feature_value=np.amax(data_dict[yi])
if np.amin(data_dict[yi])<min_feature_value:
min_feature_value=np.amin(data_dict[yi])
learning_rate = [max_feature_value * 0.1, max_feature_value * 0.01, max_feature_value * 0.001,]
def SVM_Training(data_dict):
i=1
global w
global b
# { ||w||: [w,b] }
length_Wvector = {}
transforms = [[1,1],[-1,1],[-1,-1],[1,-1]]
b_step_size = 2
b_multiple = 5
w_optimum = max_feature_value*0.5
for lrate in learning_rate:
w = np.array([w_optimum,w_optimum])
optimized = False
while not optimized:
#b=[-maxvalue to maxvalue] we wanna maximize the b values so check for every b value
for b in np.arange(-1*(max_feature_value*b_step_size), max_feature_value*b_step_size, lrate*b_multiple):
for transformation in transforms: # transforms = [[1,1],[-1,1],[-1,-1],[1,-1]]
w_t = w*transformation
correctly_classified = True
# every data point should be correct
for yi in data_dict:
for xi in data_dict[yi]:
if yi*(np.dot(w_t,xi)+b) < 1: # we want yi*(np.dot(w_t,xi)+b) >= 1 for correct classification
correctly_classified = False
if correctly_classified:
length_Wvector[np.linalg.norm(w_t)] = [w_t,b] #store w, b for minimum magnitude
if w[0] < 0:
optimized = True
else:
w = w - lrate
norms = sorted([n for n in length_Wvector])
minimum_wlength = length_Wvector[norms[0]]
w = minimum_wlength[0]
b = minimum_wlength[1]
w_optimum = w[0]+lrate*2
SVM_Training(data_dict)
def visualize(data_dict):
#[[ax.scatter(x[0],x[1],s=100,color=colors[i]) for x in data_dict[i]] for i in data_dict]
plt.scatter(X1[:,1],X1[:,2],marker='o',c=y)
# hyperplane = x.w+b
# v = x.w+b
# psv = 1
# nsv = -1
# dec = 0
def hyperplane_value(x,w,b,v):
return (-w[0]*x-b+v) / w[1]
datarange = (min_feature_value*0.9,max_feature_value*1.)
hyp_x_min = datarange[0]
hyp_x_max = datarange[1]
# (w.x+b) = 1
# positive support vector hyperplane
psv1 = hyperplane_value(hyp_x_min, w, b, 1)
psv2 = hyperplane_value(hyp_x_max, w, b, 1)
ax.plot([hyp_x_min,hyp_x_max],[psv1,psv2], 'k')
# (w.x+b) = -1
# negative support vector hyperplane
nsv1 = hyperplane_value(hyp_x_min, w, b, -1)
nsv2 = hyperplane_value(hyp_x_max, w, b, -1)
ax.plot([hyp_x_min,hyp_x_max],[nsv1,nsv2], 'k')
# (w.x+b) = 0
# positive support vector hyperplane
db1 = hyperplane_value(hyp_x_min, w, b, 0)
db2 = hyperplane_value(hyp_x_max, w, b, 0)
ax.plot([hyp_x_min,hyp_x_max],[db1,db2], 'y--')
plt.axis([-5,10,-12,-1])
plt.show()
visualize(data_dict)
</syntaxhighlight>
[[File:分类.png|800px]]
==参见==
* [https://en.wikipedia.org/wiki/In_situ_adaptive_tabulation 动态自适应建表算法]
* [https://en.wikipedia.org/wiki/Kernel_method 核方法]
* [https://en.wikipedia.org/wiki/Fisher_kernel Fisher核]
* [https://en.wikipedia.org/wiki/Platt_scaling 概率输出]
* [https://en.wikipedia.org/wiki/Polynomial_kernel 多项式核]
* [https://zh.wikipedia.org/wiki/%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90 预测分析]
* [https://en.wikipedia.org/wiki/Regularization_perspectives_on_support_vector_machines SVM正则化]
* [https://zh.wikipedia.org/wiki/%E7%9B%B8%E5%85%B3%E5%90%91%E9%87%8F%E6%9C%BA 相关向量机]，是一个函数形式与支持向量机相同的概率稀疏核模型。
* [https://zh.wikipedia.org/wiki/%E5%BA%8F%E5%88%97%E6%9C%80%E5%B0%8F%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95 序列最小优化算法]
* [https://en.wikipedia.org/wiki/Space_mapping 空间映射]
* [https://en.wikipedia.org/wiki/Winnow_(algorithm) Winnow算法]
==参考==
<references />
==文献 ==
* Theodoridis, Sergios; and Koutroumbas, Konstantinos; ''Pattern Recognition'', 4th Edition, Academic Press, 2009, ISBN|978-1-59749-272-0
* Cristianini, Nello; and Shawe-Taylor, John; ''[http://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]", in ''Supervised, Semi-supervised, and Unsupervised Learning'', Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN|3-540-31681-7
* Kecman, Vojislav; ''[http://www.support-vector.ws Learning and Soft Computing — Support Vector Machines, Neural Networks, Fuzzy Logic Systems]'', 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]'', 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.] (2004); [http://www.csse.monash.edu.au/~dld/David.Dowe.publications.html#TanDowe2004 ''MML Inference of Oblique Decision Trees''], Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, [http://www.csse.monash.edu.au/~dld/Publications/2004/Tan+DoweAI2004.pdf pp. 1082–1088] ''(This paper uses 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 ''(this is a reprint of Vapnik's early book describing philosophy behind SVM approach; the 2006 Appendix describes recent developments)''
* Fradkin, Dmitriy; and Muchnik, Ilya; "[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. 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?]", ''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]", in ''Reviews in Computational Chemistry'', Volume 23, 2007, pp. 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]'', Morgan and Claypool, 2011 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
== 外部链接 ==
* [http://www.csie.ntu.edu.tw/~cjlin/libsvm/ libsvm], LIBSVM is a popular library of SVM learners
* [http://www.csie.ntu.edu.tw/~cjlin/liblinear/ liblinear] is a library for large linear classification including some SVMs
* [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] is a GUI demo for [https://en.wikipedia.org/wiki/JavaScript JavaScript] implementation of SVMs
----
本中文词条由乌丢丢 翻译编辑，由 HengFlynn 审校，[[用户:张江|张江]]总审校，[[用户:费米子|费米子]]编辑，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[category:神经网络]]
[[category:机器学习]]
[[category:人工智能]]
|keywords=分类,支持向量机,集智
|description=分类,支持向量机,集智
}}
在[[机器学习]]中，支持向量机（support vector machine，常简称为SVM，又名支持向量网络<ref name="cortes95">[https://en.wikipedia.org/wiki/Corinna_Cortes Cortes, Corinna]; Vapnik, Vladimir N. (1995). "Support-vector networks". [https://en.wikipedia.org/wiki/Machine_Learning_(journal) Machine Learning]. 20 (3): 273–297. doi:10.1007/BF00994018</ref>）指的是一种有[[监督式学习]]模型及其相关的学习[[算法]]，广泛用于[https://zh.wikipedia.org/wiki/%E5%88%86%E7%B1%BB%E9%97%AE%E9%A2%98 分类]及[https://zh.wikipedia.org/wiki/%E8%BF%B4%E6%AD%B8%E5%88%86%E6%9E%90 回归分析]。当给定一组训练实例，并标记这些训练实例属于两个类别的其中之一，SVM训练算法基于这些实例创建一个模型将新的实例归类为两个类别中的一个，使其成为非概率[[二元线性分类器]](尽管SVM中有些方法如[https://en.wikipedia.org/wiki/Platt_scaling 概率输出]会在概率分类集合中使用)。SVM模型将实例表示为空间中的点，使得不同类别的实例被尽可能明显的间隔所分开。然后，新的实例将被映射到同一空间中，并基于它们落在间隔的哪一侧来预测其所属类别。
除了进行线性分类之外，SVM还可以使用所谓的[https://zh.wikipedia.org/w/index.php?title=%E6%A0%B8%E6%8A%80%E5%B7%A7&action=edit&redlink=1 核技巧]实现有效地非线性分类，将其输入实例映射到高维特征空间中。对于未标记数据，无法进行有监督式学习，但是可以使用[[非监督式学习]]进行训练。非监督式学习会尝试找出数据到簇的自然聚类，并将新数据映射到这些已形成的簇中。Hava Siegelmann 和 Vladimir Vapnik创造了支持向量聚类<ref name="ben01">Ben-Hur, Asa; Horn, David; Siegelmann, Hava; and Vapnik, Vladimir N.; "Support vector clustering"; (2001); Journal of Machine Learning Research, 2: 125–137</ref>算法，该算法利用支持向量机算法生成的支持向量统计数据对未标记的数据分类。这一算法也成为了工业应用最广泛的聚类算法之一。
==动机==
[https://en.wikipedia.org/wiki/Statistical_classification 数据分类]是机器学习中的一项常见任务。 假设给定的一些[https://en.wikipedia.org/wiki/Data_point 数据点]各自属于两个类其中之一，而数据分类的目标是利用这些数据确定新给定的数据点将在哪个类中。对于支持向量机来说，数据点被视为<math>p</math>维向量，而我们想知道是否可以用<math>p-1</math>维[https://en.wikipedia.org/wiki/Hyperplane 超平面]来分开这些点。这就是所谓的[https://en.wikipedia.org/wiki/Linear_classifier 线性分类器]。可能存在许多超平面可以把数据分类，而最佳超平面的一个合理选择标准是找出把两个类以[https://en.wikipedia.org/wiki/Maximum-margin_hyperplane 最大间隔分开的超平面]。
[[File:220px-Svm_separating_hyperplanes_(SVG).svg.png|220px|thumb|right|<math>H_1</math> 不能把类别分开。<math>H_{2}</math> 可以，但只有很小的间隔。<math>H_3</math> 以最大间隔将它们分开。]]
所以，我们要选择的超平面是实现距离超平面最近点之间距离间隔最大的。如果存在这样的超平面，则可将其称为最大间隔超平面，而基于其定义的线性分类器被称为最大间隔分类器，或叫做最佳稳定性[https://en.wikipedia.org/wiki/Perceptron 感知器]。
==定义==
更正式地来说，支持向量机在高维或无限维空间中构造超平面或超平面集合，其可用于[https://en.wikipedia.org/wiki/Statistical_classification 分类]、[https://en.wikipedia.org/wiki/Regression_analysis 回归]或类似异常检测的其他任务<ref name="archived'>"[http://scikit-learn.org/stable/modules/svm.html Archived copy]". [https://web.archive.org/web/20171108151644/http://scikit-learn.org/stable/modules/svm.html Archived] from the original on 2017-11-08. Retrieved 2017-11-08</ref>。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的[https://en.wikipedia.org/wiki/Generalization_error 泛化误差]<ref name="trevor">Trevor_Hastie,_Robert_Tibshirani,_Jerome_Friedman - The elements of Statistical Learning Pg. 134</ref>。
[[File:Kernel_Machine.png|300px|thumb|right|核机器]]
尽管原始问题可能是在有限维空间中陈述的，但用于区分的集合在该空间中往往不是[https://en.wikipedia.org/wiki/Linear_separability 线性可分]的。为此，有人提出将原始的限维空间映射到维数高得多的空间中，在这种空间中进行分离可能会更容易。为了保证计算负荷合理，人们选择适合该问题的核函数 k(x,y) 来定义SVM方案使用的映射<ref name="press07">*Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). [http://apps.nrbook.com/empanel/index.html#pg=883 "Section 16.5. Support Vector Machines"]. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. [https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=883 Archived] from the original on 2011-08-11.</ref>，以确保用原始空间中的变量可以很容易计算[https://en.wikipedia.org/wiki/Dot_product 点积]。高维空间中的超平面指的是与该空间中的某向量的点积是常数的点的集合。定义超平面的向量可以被选择成为在数据集合中出现的[https://en.wikipedia.org/wiki/Feature_vector 特征向量]<math>x_i</math>的图像的参数 <math>\alpha _i</math>的线性组合。通过选择超平面，被映射到超平面上的[https://en.wikipedia.org/wiki/Feature_space 特征空间]中的点集 <math>x</math> 由以下关系定义：<small><math>\sum_i\alpha _ik(x_i,x)=constant</math></small>. 需要注意的是，如果随着<math>y</math> 逐渐远离 <math>x</math>， <math>{k}(x,y) </math>变小，则求和中的每一项都是在衡量测试点 <math>x</math>与对应的数据集中点 <math>x_i</math>的接近程度。在这种情况下，上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近度。也要注意到，点<math>x</math>的集合映射到任何超平面的结果可以特别复杂，同时也允许复杂得多的在原始空间里为非凸集合间的分离。
== 应用==
SVM可以用于解决多种真实世界的问题：
*用于[https://zh.wikipedia.org/wiki/%E6%96%87%E6%A1%A3%E5%88%86%E7%B1%BB 文本和超文本的分类]，在归纳和[https://en.wikipedia.org/wiki/Transduction_(machine_learning) 转导]方法中都可以显著减少所需要的有类标的样本数。
*用于[https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E8%A7%86%E8%A7%89 图像分类]。实验结果显示：相比于传统的查询优化方案，在经过三到四轮相关反馈之后，支持向量机能够获取明显更高的搜索准确度。这同样也适用于[https://zh.wikipedia.org/wiki/%E5%9B%BE%E5%83%8F%E5%88%86%E5%89%B2 图像分区]系统，比如使用Vapnik所建议用特权方法的修改版本SVM的那些图像分区系统。<ref name="vapnlk14">Vapnik, Vladimir N.: Invited Speaker. IPMU Information Processing and Management 2014)</ref><ref name="barghout15">Barghout, Lauren. [https://pdfs.semanticscholar.org/917f/15d33d32062bffeb6401eee9fe71d16d6a84.pdf "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>
*用于手写字体[https://zh.wikipedia.org/wiki/%E6%89%8B%E5%86%99%E8%AF%86%E5%88%AB 识别]。<ref name="decoste02">DeCoste, Dennis (2002). [https://people.eecs.berkeley.edu/~malik/cs294/decoste-scholkopf.pdf "Training Invariant Support Vector Machines"] (PDF). Machine Learning. 46: 161–190.</ref>
*SVM算法已被广泛应用于生物和其他科学。SVM用于分类蛋白质，可达到90%以上分类准确度。基于支持向量机权重的[https://en.wikipedia.org/wiki/Resampling_(statistics)#Permutation_tests 置换测试]可作为一种机制，用于解释的支持向量机模型。<ref name="gaonkar">Gaonkar, Bilwaj; Davatzikos, Christos; "Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification"</ref><ref name="cuingnet11">Cuingnet, Rémi; Rosso, Charlotte; Chupin, Marie; Lehéricy, Stéphane; Dormont, Didier; Benali, Habib; Samson, Yves; and Colliot, Olivier; [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3767485/ "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 name="statnikov06">Statnikov, Alexander; Hardin, Douglas; & Aliferis, Constantin; (2006); [http://www.aramislab.fr/perso/colliot/files/media2011_remi_published.pdf "Using SVM weight-based methods to identify causally relevant and non-causally relevant variables"], Sign, 1, 4</ref>在生命科学领域，利用支持向量机的Posthoc Posthoc interpretation进行特征识别，并用于预测是一个相对较新的研究方向，而且有着特殊的意义。
==历史==
最初的SVM算法是[https://zh.wikipedia.org/wiki/%E5%BC%97%E6%8B%89%E5%9F%BA%E7%B1%B3%E5%B0%94%C2%B7%E4%B8%87%E6%99%AE%E5%B0%BC%E5%85%8B Vladimir N. Vapnik]和[https://en.wikipedia.org/wiki/Alexey_Chervonenkis Alexey Ya. Chervonenkis] 于1963年发明。1992年，Bernhard E. Boser、Isabelle M. Guyon和[https://zh.wikipedia.org/wiki/%E4%BA%9E%E6%AD%B7%E5%85%8B%E5%A1%9E%C2%B7%E6%BE%A4%E8%8C%83%E8%98%AD%E5%82%91%E6%96%AF Vladimir N. Vapnik]提出了一种通过将[https://en.wikipedia.org/wiki/Kernel_method 核技巧]应用于最大间隔超平面来创建非线性分类器的方法。<ref name="boser92"> Boser, Bernhard E.; Guyon, Isabelle M.; Vapnik, Vladimir N. (1992). "A training algorithm for optimal margin classifiers". Proceedings of the fifth annual workshop on Computational learning theory – COLT '92. p. 144. doi:10.1145/130385.130401. ISBN 089791497X.</ref>现行标准的前身（软间隔）由[https://en.wikipedia.org/wiki/Corinna_Cortes Corinna Cortes]和Vapnik于1993年提出，并于1995年发表。
==线性SVM==
按照以下形式给出 <math> n</math> 点测试集：
<math> (\overrightarrow{x_{1}},y_{1}),...,(\overrightarrow{x_{n}},y_{n}) </math>
其中 <math>y_1</math> 是 1 或者 −1，表明点 <math>\overrightarrow{x_i}</math> 所属的类。 <math>\overrightarrow{x_i}</math>中每个都是一个 <math>p</math> 维实向量。我们希望找出可将 <math>y_i=1</math>的点集<math>\overrightarrow{x_i}</math> 与 <math>y_i=-1</math>的点集分开的 “最大间隔超平面”，使得超平面与最近的点<math>\overrightarrow{x_i}</math> 之间的距离最大化。
任何[https://zh.wikipedia.org/wiki/%E8%B6%85%E5%B9%B3%E9%9D%A2 超平面]都可以表示为满足下面方程的点集 <math>\overrightarrow{x_i}</math>
[[File:SVMClassifier2.svg.png|200px|thumb|right|设样本属于两个类，用该样本训练SVM得到的最大间隔超平面。在超平面上的样本点也称为支持向量。]]
<math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b=0</math>
其中 <math>\overrightarrow{\omega }</math>（不必是归一化的）是该超平面的[https://zh.wikipedia.org/wiki/%E6%B3%95%E7%BA%BF 法向量]，其更像是[https://en.wikipedia.org/wiki/Hesse_normal_form 海赛正规形式]，但 <math>\overrightarrow{\omega }</math>不必是单位向量。参数<math> \frac{b}{\left \| \overrightarrow{\omega } \right \|}</math>决定了从原点沿法向量<math>\overrightarrow{\omega }</math>到超平面的偏移量。
===硬间隔===
如果这些训练数据是[https://en.wikipedia.org/wiki/Linearly_separable 线性可分]的，我们可以选择两个平行超平面分离这两类数据，使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为“间隔”，最大间隔超平面是位于它们正中间的超平面。这些超平面可以由以下方程式表示：
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b=1</math> (所有位于或者高于这条分界线的属于一类，标签为1）
或是
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b=-1</math>(所有位于或者低于这条分界线的属于一类，标签为-1）
利用几何方法不难得到这两个超平面之间的距离是<math> \frac{2}{\left \| \overrightarrow{\omega } \right \|}</math><ref name="stack">[https://math.stackexchange.com/q/1305925/168764 "Why does the SVM margin is $\frac{2}{\-\mathbf{w}\-}$"].Mathematics Stack Exchange.</ref>，因此要使两平面间的距离最大，我们需要实现<math>\left \| \overrightarrow{\omega } \right \|</math>最小化。同时，为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的 <math>i</math> 满足如下条件之一：
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b>or= 1 </math>, 若<math>y_i=1</math>
或是：
: <math>\overrightarrow{\omega }\cdot \overrightarrow{x}-b\leq 1</math>, 若<math>y_i=-1</math>
这些限制表明每个数据点都必须位于间隔的正确一侧。
这两个式子也可以写成如下形式：
: <math>y_i(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)\geq 1</math>, 对所有<math>1\leq i\leq 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,...,n </math>”</blockquote>这个问题的解 <math>\vec w</math> 与 <math>b</math> 决定了我们的分类器 <math>\overrightarrow{x} \mapsto sgn(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)</math>.
这一几何描述的一个显而易见却重要的结果是，最大间隔超平面完全是由最靠近它的那些 <math> \overrightarrow{x}_i</math> 确定，这些 <math> \overrightarrow{x}_i</math> 叫做'''支持向量'''。
=== 软间隔 ===
为了将SVM扩展到数据线性不可分的情况，我们引入[https://en.wikipedia.org/wiki/Hinge_loss 铰链损失]函数，
: <math>max(0,1-y_{i}(\overrightarrow{\omega }\cdot \overrightarrow{x_{i}}-b))</math>.
注意<math>y_i</math>是第<math>i</math>个目标（例如，在本例中，1或者-1），<math>\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b</math>是当前输出。
当约束条件 (1) 满足时（也就是如果 <math>\overrightarrow{x}_i</math> 位于边距的正确一侧）此函数为零。对于位于间隔的错误一侧的数据，该函数的值与该数据与间隔的距离成正比。
当我们希望其最小化：<blockquote><math>[\frac{1}{n}\sum_{i=1}^{n}max(0,1-y_i(\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b))]+\lambda \left \| \overrightarrow{\omega } \right \|^{2}</math>,</blockquote>其中参数 <math>\lambda</math> 用来权衡增加间隔大小与确保 <math>\overrightarrow{x_i}</math> 位于间隔的正确一侧之间的关系。因此，对于足够小的 <math>\lambda</math> 值，如果输入数据是可以线性分类的，则软间隔SVM与硬间隔SVM将表现相同，但即使数据不可线性分类，仍能学习出可行的分类规则。
== 非线性分类 ==
[[File:Kernel_Machine.png|400px|thumb|核机器]]
Vapnik在1963年提出的最原始的最大间隔超平面算法构造了一个[[线性分类器]]。而1992年，Bernhard E. Boser、Isabelle M. Guyon和[https://zh.wikipedia.org/wiki/%E5%BC%97%E6%8B%89%E5%9F%BA%E7%B1%B3%E5%B0%94%C2%B7%E4%B8%87%E6%99%AE%E5%B0%BC%E5%85%8B Vladimir N. Vapnik]提出了一种通过将[https://en.wikipedia.org/wiki/Kernel_method 核技巧]（由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|journal = Automation and Remote Control|volume = 25|pages = 821–837}}</ref>最先提出）应用于最大边界超平面来创建非线性分类器的方法。<ref name="boser92"></ref> 除了把[https://zh.wikipedia.org/wiki/%E7%82%B9%E7%A7%AF 点积]换成了非线性[https://zh.wikipedia.org/wiki/%E7%A7%AF%E5%88%86%E5%8F%98%E6%8D%A2 核]函数，所得到的算法形式上与前者类似。这种变化允许算法在变换后的[https://en.wikipedia.org/wiki/Feature_(machine_learning)#Extensions 特征空间]中拟合最大间隔超平面。这类变换可以是非线性的，但变换空间是高维的；尽管分类器是变换后的特征空间中的超平面，但它在原始输入空间中可以是非线性的。
值得注意的是，更高维的特征空间增加了支持向量机的[https://zh.wikipedia.org/wiki/%E6%B3%9B%E5%8C%96%E8%AF%AF%E5%B7%AE 泛化误差]，但是当给定了足够多的样本，算法仍能表现良好。<ref>Jin, Chi; Wang, Liwei (2012). [http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound Dimensionality dependent PAC-Bayes margin bound]. Advances in Neural Information Processing Systems. [https://web.archive.org/web/20150402185336/http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound Archived] from the original on 2015-04-02.</ref>
常见的核函数包括：
* [https://zh.wikipedia.org/wiki/%E9%BD%8A%E6%AC%A1%E5%A4%9A%E9%A0%85%E5%BC%8F 齐次多项式]：<math>k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j})^d</math>
* [https://en.wikipedia.org/wiki/Polynomial_kernel 非齐次多项式]：<math>k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j} + 1)^d</math>
* 高斯[https://zh.wikipedia.org/wiki/%E5%BE%84%E5%90%91%E5%9F%BA%E5%87%BD%E6%95%B0%E6%A0%B8 径向基函数]：<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>
* [https://zh.wikipedia.org/wiki/%E5%8F%8C%E6%9B%B2%E5%87%BD%E6%95%B0 双曲正切]：<math>k(\vec{x_i},\vec{x_j})=\tanh(\kappa \vec{x_i} \cdot \vec{x_j}+c)</math>，其中一些（而非所有）<math> \kappa </math>大于0， 且 <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)简化为[https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92 二次规划]问题的经典方法。之后会讨论一些最近才出现的方法，如次梯度下降法和坐标下降法。
=== 原型 ===
求方程式(2)最小解可用下面的方式改写为目标函数可微的约束优化问题。
对所有 <math>i\in \left \{ 1,...,n \right \}</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(\omega \cdot x_i-b)\geq 1-\zeta _i \,\text{ and }\zeta_i \geq 0,\text{for all }i.</math> </blockquote>这就叫做''原型''问题。
=== 对偶型 ===
通过求解上述问题的[https://en.wikipedia.org/wiki/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> 的二次函数，所以它可以通过[https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92 二次规划]算法高效地解出。
这里，变量 <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(\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b)=1\Leftrightarrow b=\overrightarrow{\omega }\cdot \overrightarrow{x_i}-y_i</math></blockquote>
得到偏移量 <math> b</math>。（注意由于 <math>y_i=\pm 1</math> 因而 <math>y_{i}^{-1}=y_{i}</math>）。
=== 核技巧 ===
[[File:220px-Kernel_trick_idea.svg.png|300px|thumb|right|SVM训练实例，核为：<math>\Phi \left ( \left ( a,b \right ) \right )=(a,b,a^{2}+b^{2})</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> \overrightarrow{\omega }=\sum_{i=1}^{n}c_iy_i\varphi (\overrightarrow{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的[https://zh.wikipedia.org/wiki/%E6%AC%A1%E6%A2%AF%E5%BA%A6%E6%B3%95 次梯度下降]算法直接用表达式<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> 的[https://zh.wikipedia.org/wiki/%E5%87%B8%E5%87%BD%E6%95%B0 凸函数]。因此，可以采用传统的[https://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95 梯度下降]（或[https://en.wikipedia.org/wiki/Stochastic_gradient_descent SGD]）方法，其不是在函数梯度的方向上前进，而是在从函数的[https://zh.wikipedia.org/wiki/%E6%AC%A1%E5%AF%BC%E6%95%B0 次梯度]中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 <math>n</math> 而增加或减少。<ref>Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew (2010-10-16). [https://link.springer.com/article/10.1007/s10107-010-0420-4 "Pegasos: primal estimated sub-gradient solver for SVM"]. Mathematical Programming. 127 (1): 3–30. [https://doi.org/10.1007/s10107-010-0420-4 doi:10.1007/s10107-010-0420-4]. [https://www.worldcat.org/issn/0025-5610 ISSN 0025-5610].</ref>
==== 坐标下降 ====
SVM的[https://en.wikipedia.org/wiki/Coordinate_descent 坐标下降]算法基于对偶问题
<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 \left \{ 1,...,n \right \}</math> 进行迭代，使系数 <math> c_i</math> 的方向与 <math> \partial f/ \partial c_i</math> 一致。然后，将所得的系数向量 <math> (c_1',\,\ldots,\,c_n')</math> 投影到满足给定约束的最接近的系数向量（通常使用欧氏距离）。然后重复该过程，直到获得接近最佳的系数向量。尽管已证明的性能保证很少，其所得的算法在实践中运行的非常快。<ref>Hsieh, Cho-Jui; Chang, Kai-Wei; Lin, Chih-Jen; Keerthi, S. Sathiya; Sundararajan, S. (2008-01-01). [https://dl.acm.org/citation.cfm?doid=1390156.1390208 "A Dual Coordinate Descent Method for Large-scale Linear SVM"]. Proceedings of the 25th International Conference on Machine Learning. ICML '08. New York, NY, USA: ACM: 408–415. [https://doi.org/10.1145/1390156.1390208 doi:10.1145/1390156.1390208] .[https://en.wikipedia.org/wiki/Special:BookSources/978-1-60558-205-4 ISBN 978-1-60558-205-4].</ref>
==经验风险最小化==
上文所描述的软间隔支持向量机是[https://en.wikipedia.org/wiki/Empirical_risk_minimization 经验风险最小化](ERM)算法用于[https://en.wikipedia.org/wiki/Hinge_loss 铰链损失(hinge loss)]的一个例子。从这方面看，支持向量机属于推断统计学算法的一个自然类，而它许多独特的特点都缘于合页损失的行为。这一观点可以提供对于SVMs如何工作以及为何有效这一问题更深入的了解，并让我们更好的分析他们的统计性质。
===风险最小化===
在监督学习中，给定一个训练实例集合<math>X_{1}...X_{n}</math> 及对应标签<math>y_{1}...y_{n}</math>，我们希望利用给定的<math>X_{n+1}</math>预测<math>y(n+1)</math>。为实现这一预测我们给出[https://en.wikipedia.org/wiki/Hypothesis 假设]，<math>f</math>，例如<math>f(X_{n+1})</math>是<math>y(n+1)</math>的一个“好”近似值。“好”近似值通常由[https://en.wikipedia.org/wiki/Loss_function 损失函数]<math>\ell(y,z)</math>定义，损失函数描述作为<math>y</math>的预测值<math>z</math>的不准确度。我们希望选择一个最小化[https://en.wikipedia.org/wiki/Loss_function#Expected_loss 期望风险]的假设：
<math>\varepsilon (f)=\mathbb{E}\left [ \ell(y_{n+1},f(X_{n+1})) \right ]</math>.
在大多数情况下，我们不知道<math>X_{n+1}</math>和<math>y(n+1)</math>的联合分布，因此，通常的策略是选择一个最小化经验风险的假设：
<math>\hat{\varepsilon }(f)=\frac{1}{n}\sum_{k=1}^{n}\ell(y_{k},f(X_{k}))</math>.
在某些关于随机变量<math>X_{k}</math>和<math>y_{k}</math>序列（例如由有限马尔可夫过程产生）的假设下，如果该假设集合足够小，那么随着<math>n</math>的增大，经验风险的最小化将近似接近期望风险的最小化。这一过程被叫做经验风险最小化，简称ERM。
===正则化和稳定性===
为了最小化问题有一个良好定义的解决方法，我们必须对所考虑的假设集合<math>\mathcal{H}</math>给出约束条件。如果<math>\mathcal{H}</math>是一个[https://zh.wikipedia.org/wiki/%E8%B3%A6%E7%AF%84%E5%90%91%E9%87%8F%E7%A9%BA%E9%96%93 赋范向量空间]（例如SVM），一个有效的特殊办法是仅考虑满足<math>\left \| f \right \|_{\mathcal H}<k</math>这一条件的假设<math> f</math>。这等同于添加一项“正则化惩罚”<math>\mathcal R(f)=\lambda \left \| f \right \|_{\mathcal H}</math>，并解决这一新的优化问题。
:<math>\hat f = \mathrm{arg}\min_{f \in \mathcal{H}} \hat \varepsilon(f) + \mathcal{R}(f).</math>
该方法被称作[https://en.wikipedia.org/wiki/Tikhonov_regularization 吉洪诺夫正则化]。
一般来说，<math>R(f)</math>可以衡量假设<math>f</math>的复杂度，因此更倾向于更简单的假设。
===SVM与铰链损失===
利用（软间隔）SVM分类器<math>\overrightarrow{\omega} ,b:x\mapsto sgn(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)</math>对以下表达式求最小化解：
:<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.</math>
从上述讨论我们可以看到，SVM技术等同于经验风险最小化加上吉洪诺夫正则化，此时的损失函数是[https://en.wikipedia.org/wiki/Hinge_loss 铰链损失]：
: <math>\ell(y,z) = \max\left(0, 1 - yz \right).</math>
在这一观点下, SVM与其他基础的[https://en.wikipedia.org/wiki/Statistical_classification#Linear_classifiers 分类算法]联系紧密，如 [https://en.wikipedia.org/wiki/Regularized_least_squares 正则化最小二乘法] and [[ 逻辑回归]]。这三者的不同在于损失函数的选择：正则化最小二乘法统计经验风险最小化使用[https://zh.wikipedia.org/wiki/%E5%88%86%E9%A1%9E%E5%95%8F%E9%A1%8C%E4%B9%8B%E6%90%8D%E5%A4%B1%E5%87%BD%E6%95%B8 平方损失函数]， <math>\ell_{sq}(y,z) = (y-z)^2</math>；逻辑回归使用[https://zh.wikipedia.org/wiki/%E5%88%86%E9%A1%9E%E5%95%8F%E9%A1%8C%E4%B9%8B%E6%90%8D%E5%A4%B1%E5%87%BD%E6%95%B8 对数损失函数]，
:<math>\ell_{\log}(y,z) = \ln(1 + e^{-yz}).</math>
====目标函数====
合页损失与其他损失函数区别主要在于“目标函数”，而目标函数使一对给定的随机变量<math>X,y</math>期望风险最小化。
特别的，在 <math>X = x</math>事件的条件下，让<math>y_x</math> 表示 <math>y</math>。在这个分类集合里，我们有：
: <math>y_x = \begin{cases} 1 & \text{with probability } p_x \\ -1 & \text{with probability } 1-p_x \end{cases}</math>
那么最理想分类器为：
:<math>f^*(x) = \begin{cases}1 & \text{if }p_x \geq 1/2 \\ -1 & \text{otherwise}\end{cases} </math>
对于平方损失，目标函数就是条件期望函数，<math>f_{sq}(x) </math><math>=\mathbb{E}[y_{x}]</math>；而对于对数损失，目标函数是逻辑函数，<math>f_{\log}(x) = \ln\left(p_x / ({1-p_x})\right)</math>。当这两个目标函数都是正确分类器，即 <math>\sgn(f_{sq}) = \sgn(f_\log) = f^*</math>，它们能给我们信息要比我们需要的更多。实际上，他们能给我们充足的信息来充分描绘<math> y_x</math>的分布。
在另一方面，合页损失的目标函数正是<math>f^*</math>。因此，在充分假设空间，或适当选择的核，SVM分类器会趋于可实现正确数据分类的最简单函数（ <math>\mathcal{R}</math>）。这一方面拓展了SVM的几何解释：对于线性分类，间隔在支持向量和最简单的最大间隔分类器之间的函数使得经验风险最小化。<ref>Rosasco, Lorenzo; De Vito, Ernesto; Caponnetto, Andrea; Piana, Michele; Verri, Alessandro (2004-05-01). [https://ieeexplore.ieee.org/document/6789841/?arnumber=6789841&abstractAccess=no&userType=inst "Are Loss Functions All the Same?"]. Neural Computation. 16 (5): 1063–1076. [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.6786 10.1.1.109.6786] Freely accessible. [https://doi.org/10.1162/089976604773135104 doi:10.1162/089976604773135104]. [https://www.worldcat.org/issn/0899-7667 ISSN 0899-7667]. [https://www.ncbi.nlm.nih.gov/pubmed/15070510 PMID 15070510].</ref>
----------------------
== 性质 ==
SVM属于广义[[线性分类器]]的一族，并且可以解释为[[感知机]]的延伸。它们也可以被认为是[https://en.wikipedia.org/wiki/Tikhonov_regularization 提克洛夫规范化]的特例。它们有一个特别的性质，就是可以同时最小化经验误差和最大化几何边缘区; 因此它们也被称为'''最大[https://en.wikipedia.org/wiki/Margin_classifier 间隔分类器]'''。
Meyer、Leisch和Hornik对SVM与其他分类器进行了比较。<ref>Meyer, David; Leisch, Friedrich; Hornik, Kurt (2003). "The support vector machine under test". Neurocomputing. 55: 169. [https://doi.org/10.1016/S0925-2312%2803%2900431-4 doi:10.1016/S0925-2312(03)00431-4].</ref>
=== 参数选择 ===
SVM的有效性取决于核函数、核参数和软间隔参数 ''C'' 的选择。
通常会选只有一个参数 ''<math>\gamma</math>'' 的高斯核。''C'' 和 <math>\gamma</math> 的最佳组合通常通过在 ''C'' 和 ''<math>\gamma</math>'' 为指数增长序列下[https://en.wikipedia.org/wiki/Hyperparameter_optimization#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>。通常情况下，使用[https://zh.wikipedia.org/wiki/%E4%BA%A4%E5%8F%89%E9%A9%97%E8%AD%89 交叉验证]来检查参数选择的每一个组合，并选择具有最佳交叉验证精度的参数。[https://en.wikipedia.org/wiki/Bayesian_optimization 贝叶斯优化]的一些近期工作可以用于选择C和γ，通常只需要评估比网格搜索少得多的参数组合。然后，使用所选择的参数在整个训练集上训练用于测试和分类新数据的最终模型。<ref>Hsu, Chih-Wei; Chang, Chih-Chung & Lin, Chih-Jen (2003). [https://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf A Practical Guide to Support Vector Classification] (PDF) (Technical report). Department of Computer Science and Information Engineering, National Taiwan University. [https://web.archive.org/web/20130625201224/http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf Archived] (PDF) from the original on 2013-06-25.</ref>
=== 问题 ===
SVM的潜在缺点包括以下方面：
* 需要对输入数据进行完全标记
* 未校准[https://en.wikipedia.org/wiki/Probabilistic_classification 类成员概率]——起源于Vapnik理论的SVM避免了在有限数据中估计概率。
* SVM仅直接适用于两类任务。因此，必须应用将多类任务减少到几个二元问题的算法；请参阅[https://en.wikipedia.org/wiki/Support_vector_machine#Multiclass_SVM 多类SVM]一节。
* 解出的模型的参数很难理解。
== 延伸 ==
===支持向量聚类===
支持向量聚类是一种建立在核函数上的类似方法，同样适用于无监督学习和数据挖掘。它被认为是[[数据科学]]中的一种基本方法。
===多元分类SVM===
多元分类SVM旨在应用支持向量机对实例赋上标签，标签是从一个含几种元素的有限集合拟定的。
主要的方法是将单独的[https://zh.wikipedia.org/wiki/%E5%A4%9A%E5%85%83%E5%88%86%E7%B1%BB 多元分类问题]降到多个[https://en.wikipedia.org/wiki/Binary_classification 二元分类]问题。<ref name="duan05">Duan, Kai-Bo; Keerthi, S. Sathiya (2005). "Which Is the Best Multiclass SVM Method? An Empirical Study". Multiple Classifier Systems. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS]. 3541. pp. 278–285. [https://doi.org/10.1007/11494683_28 doi:10.1007/11494683_28]. [https://en.wikipedia.org/wiki/International_Standard_Book_Number ISBN] [https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-26306-7 978-3-540-26306-7].</ref>通常有以下几种方法：<ref name="duan05"></ref><ref name="hsu02">Hsu, Chih-Wei & Lin, Chih-Jen (2002). [http://www.cs.iastate.edu/~honavar/multiclass-svm.pdf "A Comparison of Methods for Multiclass Support Vector Machines"] (PDF). IEEE Transactions on Neural Networks.</ref>
* 构造二元分类器区分(i)其中一个标签及剩余标签（一对多）或(ii)每一个对类（一对一）。一对多情况下对新实例进行分类由胜者全得策略完成，由最高输出函数的分类器分类（输出函数的分数必须标准化）。一对一情况下采用投票策略，每一分类器将实例赋给两类中的一类，最终拥有最多票数的类决定实例分类。
* [https://zh.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE 有向无环图]SVM (DAGSVM)<ref name="platt00"> Platt, John; [https://en.wikipedia.org/wiki/Nello_Cristianini Cristianini, Nello]; [https://en.wikipedia.org/wiki/John_Shawe-Taylor Shawe-Taylor], John (2000). [http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/DAGSVM.pdf "Large margin DAGs for multiclass classification"]. In Solla, Sara A.; Leen, Todd K.; and Müller, Klaus-Robert; eds. [http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/DAGSVM.pdf Advances in Neural Information Processing Systems (PDF)]. MIT Press. pp. 547–553. [https://web.archive.org/web/20120616221540/http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/DAGSVM.pdf Archived] (PDF) from the original on 2012-06-16.</ref>
* [https://en.wikipedia.org/wiki/Error_correction_code 纠错输出编码]<ref name="die95">Dietterich, Thomas G.; Bakiri, Ghulum (1995). [http://www.jair.org/media/105/live-105-1426-jair.pdf "Solving Multiclass Learning Problems via Error-Correcting Output Codes"] (PDF). Journal of Artificial Intelligence Research. 2: 263–286. [https://en.wikipedia.org/wiki/ArXiv arXiv]:[https://arxiv.org/abs/cs/9501101 cs/9501101] Bibcode:1995cs........1101D. [https://web.archive.org/web/20130509061344/http://www.jair.org/media/105/live-105-1426-jair.pdf Archived] (PDF) from the original on 2013-05-09.. </ref>
Crammer和Singer提议多元分类SVM将多类分类问题变成单个优化问题而不是分解为多个二元分类问题。<ref name="crammer01">Crammer, Koby & Singer, Yoram (2001). [http://jmlr.csail.mit.edu/papers/volume2/crammer01a/crammer01a.pdf "On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines"] (PDF). Journal of Machine Learning Research. 2: 265–292. [https://web.archive.org/web/20150829102651/http://jmlr.csail.mit.edu/papers/volume2/crammer01a/crammer01a.pdf Archived] (PDF) from the original on 2015-08-29.</ref>也可以参考Lee，Lin和Wahba的论文。<ref name="lee01">Lee, Yoonkyung; Lin, Yi & Wahba, Grace (2001). [http://www.interfacesymposia.org/I01/I2001Proceedings/YLee/YLee.pdf "Multicategory Support Vector Machines"] (PDF). Computing Science and Statistics. 33. [https://web.archive.org/web/20130617093314/http://www.interfacesymposia.org/I01/I2001Proceedings/YLee/YLee.pdf Archived] (PDF) from the original on 2013-06-17.</ref>
<ref name="lee04">Lee, Yoonkyung; Lin, Yi; Wahba, Grace (2004). "Multicategory Support Vector Machines". Journal of the American Statistical Association. 99 (465): 67. [https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1198/016214504000000098 10.1198/016214504000000098].</ref>
===转导支持向量机===
转导支持向量机拓展了SVMs，通过[https://en.wikipedia.org/wiki/Transduction_(machine_learning) 转导]法则，它们也可以在[[半监督学习]]中处理部分标注数据。除了训练集 <math>D</math>，学习器也被赋予一个待分类的测试实例集合。
:<math>\mathcal{D}^\star = \{ \vec{x}^\star_i \mid \vec{x}^\star_i \in \mathbb{R}^p\}_{i=1}^k \, </math>
转导支持向量机由以下主要的优化问题定义：<ref>Joachims, Thorsten; "[http://www1.cs.columbia.edu/~dplewis/candidacy/joachims99transductive.pdf Transductive Inference for Text Classification using Support Vector Machines]", ''Proceedings of the 1999 International Conference on Machine Learning (ICML 1999)'', pp. 200–209</ref>
最小化 (在 <math>{\vec{w}, b, \vec{y^\star}}</math>中)
: <math>\frac{1}{2}\|\vec{w}\|^2</math>
受约束于 (对任意 <math>i = 1, \dots, n</math> 和任意 <math>j = 1, \dots, k</math>)
: <math>y_i(\vec{w}\cdot\vec{x_i} - b) \ge 1,\,</math>
: <math>y^\star_j(\vec{w}\cdot\vec{x^\star_j} - b) \ge 1,</math>
以及
: <math>y^\star_{j} \in \{-1, 1\}.\,</math>
转导支持向量机由Vladimir N. Vapnik于1998年提出。
===结构化支持向量机===
支持向量机可以被拓展为[https://en.wikipedia.org/wiki/Structured_support_vector_machine 结构化的支持向量机]，推广后标签空间是结构化的并且可能具有无限的大小。
===回归===
[[File:440px-Svr_epsilons_demo.svg.png|300px|thumb|right|不同''ε''的支持向量回归（预测）。随着''ε''增大，预测对误差的敏感度降低。]]
[https://zh.wikipedia.org/wiki/%E8%BF%B4%E6%AD%B8%E5%88%86%E6%9E%90 回归] 形式的支持向量机于1996年由[https://zh.wikipedia.org/wiki/%E5%BC%97%E6%8B%89%E5%9F%BA%E7%B1%B3%E5%B0%94%C2%B7%E4%B8%87%E6%99%AE%E5%B0%BC%E5%85%8B Vladimir N. Vapnik], Harris Drucker, Christopher J. C. Burges, Linda Kaufman and Alexander J. Smola提出。<ref>Drucker, Harris; Burges, Christopher J. C.; Kaufman, Linda; Smola, Alexander J.; and Vapnik, Vladimir N. (1997); "[http://papers.nips.cc/paper/1238-support-vector-regression-machines.pdf Support Vector Regression Machines]", in ''Advances in Neural Information Processing Systems 9, NIPS 1996'', 155–161, MIT Press.</ref>该方法称为支持向量回归（SVR）。支持向量分类的模型仅依靠训练数据的子集，因为模型的损失函数不关心边缘以外的训练点。类似的，SVR模型仅依靠因为模型的损失函数不关心边缘以外的训练点，因为模型的损失函数忽视了接近模型预测的训练数据。另一形式的SVM，即[https://en.wikipedia.org/wiki/Least_squares_support_vector_machine 最小二乘支持向量机] 已经由Suykens和Vandewalle提出。<ref>Suykens, Johan A. K.; Vandewalle, Joos P. L.; "[https://lirias.kuleuven.be/bitstream/123456789/218716/2/Suykens_NeurProcLett.pdf Least squares support vector machine classifiers]", ''Neural Processing Letters'', vol. 9, no. 3, Jun. 1999, pp. 293–300</ref>
训练原始SVR意味着求解<ref>{{cite journal |last1=Smola |first1=Alex J. |first2=Bernhard |last2=Schölkopf |title=A tutorial on support vector regression |journal=Statistics and Computing |volume=14 |issue=3 |year=2004 |pages=199–222 |url=http://eprints.pascal-network.org/archive/00000856/01/fulltext.pdf |deadurl=no |archiveurl=https://web.archive.org/web/20120131193522/http://eprints.pascal-network.org/archive/00000856/01/fulltext.pdf |archivedate=2012-01-31 }}</ref>
:minimize <math>\frac{1}{2} \|w\|^2 </math>
:subject to <math>\begin{cases}
y_i - \langle w, x_i \rangle - b \le \varepsilon \\
\langle w, x_i \rangle + b - y_i \le \varepsilon
\end{cases}</math>
其中<math>x_i</math>是目标值为<math>y_i</math>的训练样本。内积加上截距<math>\langle w, x_i \rangle + b</math>是样本的预测值，<math>\varepsilon</math>是一个作为限制的自由参量：所有的预测值都应与真实预测值在<math>\varepsilon</math>的范围内。通常加入松弛变量来使不可行情况下产生误差和近似值。
===贝叶斯SVM===
2011年，Polson和Scott运用[https://en.wikipedia.org/wiki/Convolutional_neural_network#Artificial_data 数据增强]在SVM中加入贝叶斯解释。<ref> Polson, Nicholas G.; Scott, Steven L. (2011). "Data Augmentation for Support Vector Machines". Bayesian Analysis. 6 (1): 1–23. [https://doi.org/10.1214/11-BA601 doi:10.1214/11-BA601].</ref>在这一方法中，SVM被视为[[ 概率图模型]]（参数由概率分布联系）。这一延伸视角使得贝叶斯方法应用于SVMs，例如灵活特征模型，自动[https://en.wikipedia.org/wiki/Hyperparameter_(machine_learning) 超参数调优]，以及[https://en.wikipedia.org/wiki/Posterior_predictive_distribution 预测不确定性量化]。近期，一种可标度的贝叶斯SVM模型由Wenzel等提出来实现贝叶斯SVM在[https://zh.wikipedia.org/wiki/%E5%A4%A7%E6%95%B8%E6%93%9A 大数据]上的应用。<ref>Wenzel, Florian; Galy-Fajou, Theo; Deutsch, Matthäus; Kloft, Marius (2017). "Bayesian Nonlinear Support Vector Machines for Big Data". Machine Learning and Knowledge Discovery in Databases (ECML PKDD). [https://arxiv.org/abs/1707.05532 arXiv:1707.05532]. [http://adsabs.harvard.edu/abs/2017arXiv170705532W Bibcode:2017arXiv170705532W].</ref>
== 实现 ==
最大间隔超平面的参数是通过求解优化得到的。有几种专门的算法可用于快速解决由SVM产生的[https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92 QP]问题，它们主要依靠启发式算法将问题分解成更小、更易于处理的子问题。
另一种方法是使用[https://en.wikipedia.org/wiki/Interior-point_method 内点法]，其使用类似[https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95 牛顿法]的迭代找到[https://zh.wikipedia.org/wiki/%E5%8D%A1%E7%BE%85%E9%9C%80%EF%BC%8D%E5%BA%AB%E6%81%A9%EF%BC%8D%E5%A1%94%E5%85%8B%E6%A2%9D%E4%BB%B6 卡罗需-库恩-塔克条件]下原型和对偶型的解。<ref>Ferris, Michael C.; Munson, Todd S. (2002). [http://www.cs.wisc.edu/~ferris/papers/siopt-svm.pdf "Interior-Point Methods for Massive Support Vector Machines"] (PDF). SIAM Journal on Optimization. 13 (3): 783. [https://doi.org/10.1137/S1052623400374379 doi:10.1137/S1052623400374379]. [https://web.archive.org/web/20081204224416/http://www.cs.wisc.edu/~ferris/papers/siopt-svm.pdf Archived] (PDF) from the original on 2008-12-04.</ref>
这种方法不是去解决一系列分解问题，而是直接完全解决该问题。为了避免求解核矩阵很大的线性系统，在核技巧中经常使用矩阵的低秩近似。
另一个常见的方法是普莱特的[https://zh.wikipedia.org/wiki/%E5%BA%8F%E5%88%97%E6%9C%80%E5%B0%8F%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95 序列最小优化算法]（SMO），它把问题分成了若干个可以解析求解的二维子问题，这样就可以避免使用数值优化算法和矩阵存储。<ref>Platt, John C. (1998). [http://research.microsoft.com/pubs/69644/tr-98-14.pdf Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines] (PDF). NIPS. [https://web.archive.org/web/20150702075055/http://research.microsoft.com/pubs/69644/tr-98-14.pdf Archived] (PDF) from the original on 2015-07-02.</ref>
线性支持向量机的特殊情况可以通过用于优化其类似问题[https://zh.wikipedia.org/wiki/%E9%82%8F%E8%BC%AF%E8%BF%B4%E6%AD%B8 逻辑回归]的同类算法更高效求解；这类算法包括[https://en.wikipedia.org/wiki/Stochastic_gradient_descent 次梯度下降法]（如PEGASOS<ref>Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan (2007). [http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf Pegasos: Primal Estimated sub-GrAdient SOlver for SVM] (PDF). ICML. [https://web.archive.org/web/20131215051700/http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf Archived] (PDF) from the original on 2013-12-15.</ref>）和[https://zh.wikipedia.org/wiki/%E5%9D%90%E6%A0%87%E4%B8%8B%E9%99%8D%E6%B3%95 坐标下降法]（如LIBLINEAR<ref>Fan, Rong-En; Chang, Kai-Wei; Hsieh, Cho-Jui; Wang, Xiang-Rui; Lin, Chih-Jen (2008). [https://www.csie.ntu.edu.tw/~cjlin/papers/liblinear.pdf "LIBLINEAR: A library for large linear classification"] (PDF). [https://en.wikipedia.org/wiki/Journal_of_Machine_Learning_Research Journal of Machine Learning Research]. 9: 1871–1874.</ref>）。LIBLINEAR有一些引人注目的训练时间上的特性。每次收敛迭代花费在读取训练数据上的时间是线性的，而且这些迭代还具有[https://zh.wikipedia.org/wiki/%E6%94%B6%E6%96%82%E9%80%9F%E5%BA%A6 Q-线性收敛]特性，使得算法非常快。
一般的核SVM也可以用[https://en.wikipedia.org/wiki/Stochastic_gradient_descent 次梯度下降法]（P-packSVM<ref>Allen Zhu, Zeyuan; Chen, Weizhu; Wang, Gang; Zhu, Chenguang; Chen, Zheng (2009). [http://people.csail.mit.edu/zeyuan/paper/2009-ICDM-Parallel.pdf P-packSVM: Parallel Primal grAdient desCent Kernel SVM] (PDF). ICDM. [https://web.archive.org/web/20140407095709/http://people.csail.mit.edu/zeyuan/paper/2009-ICDM-Parallel.pdf Archived] (PDF) from the original on 2014-04-07.
</ref>）更快求解，在允许[https://zh.wikipedia.org/wiki/%E5%B9%B6%E8%A1%8C%E8%AE%A1%E7%AE%97 并行化]时求解速度尤其快。
许多机器学习工具包都可以使用核SVM，有[https://en.wikipedia.org/wiki/LIBSVM LIBSVM]、[https://zh.wikipedia.org/wiki/MATLAB MATLAB]、[http://support.sas.com/documentation/cdl/en/whatsnew/64209/HTML/default/viewer.htm#emdocwhatsnew71.htm SAS]、SVMlight、[https://cran.r-project.org/package=kernlab kernlab]、[https://en.wikipedia.org/wiki/Scikit-learn scikit-learn]、[https://en.wikipedia.org/wiki/Shogun_(toolbox) Shogun]、[https://zh.wikipedia.org/wiki/Weka Weka]、[http://image.diku.dk/shark/ Shark]、[https://mloss.org/software/view/409/ JKernelMachines]、[https://zh.wikipedia.org/wiki/OpenCV OpenCV]等。
== 简单实现与演示 ==
<syntaxhighlight lang="python">
from sklearn.datasets.samples_generator import make_blobs
# revised from https://github.com/Madhu009/Deep-math-machine-learning.ai/blob/master/SVM-FromScratch.ipynb
# data preparation
(X,y) = make_blobs(n_samples=50,n_features=2,centers=2,cluster_std=1.05,random_state=40)
#we need to add 1 to X values (we can say its bias)
X1 = np.c_[np.ones((X.shape[0])),X]
plt.scatter(X1[:,1],X1[:,2],marker='o',c=y)
plt.axis([-5,10,-12,-1])
plt.show()
</syntaxhighlight>
[[File:未分类.png|800px]]
<syntaxhighlight lang="python">
postiveX=[]
negativeX=[]
for i,v in enumerate(y):
if v==0:
negativeX.append(X[i])
else:
postiveX.append(X[i])
#our data dictionary
data_dict = {-1:np.array(negativeX), 1:np.array(postiveX)}
#all the required variables
w=[] #weights 2 dimensional vector
b=[] #bias
max_feature_value=float('-inf')
min_feature_value=float('+inf')
for yi in data_dict:
if np.amax(data_dict[yi])>max_feature_value:
max_feature_value=np.amax(data_dict[yi])
if np.amin(data_dict[yi])<min_feature_value:
min_feature_value=np.amin(data_dict[yi])
learning_rate = [max_feature_value * 0.1, max_feature_value * 0.01, max_feature_value * 0.001,]
def SVM_Training(data_dict):
i=1
global w
global b
# { ||w||: [w,b] }
length_Wvector = {}
transforms = [[1,1],[-1,1],[-1,-1],[1,-1]]
b_step_size = 2
b_multiple = 5
w_optimum = max_feature_value*0.5
for lrate in learning_rate:
w = np.array([w_optimum,w_optimum])
optimized = False
while not optimized:
#b=[-maxvalue to maxvalue] we wanna maximize the b values so check for every b value
for b in np.arange(-1*(max_feature_value*b_step_size), max_feature_value*b_step_size, lrate*b_multiple):
for transformation in transforms: # transforms = [[1,1],[-1,1],[-1,-1],[1,-1]]
w_t = w*transformation
correctly_classified = True
# every data point should be correct
for yi in data_dict:
for xi in data_dict[yi]:
if yi*(np.dot(w_t,xi)+b) < 1: # we want yi*(np.dot(w_t,xi)+b) >= 1 for correct classification
correctly_classified = False
if correctly_classified:
length_Wvector[np.linalg.norm(w_t)] = [w_t,b] #store w, b for minimum magnitude
if w[0] < 0:
optimized = True
else:
w = w - lrate
norms = sorted([n for n in length_Wvector])
minimum_wlength = length_Wvector[norms[0]]
w = minimum_wlength[0]
b = minimum_wlength[1]
w_optimum = w[0]+lrate*2
SVM_Training(data_dict)
def visualize(data_dict):
#[[ax.scatter(x[0],x[1],s=100,color=colors[i]) for x in data_dict[i]] for i in data_dict]
plt.scatter(X1[:,1],X1[:,2],marker='o',c=y)
# hyperplane = x.w+b
# v = x.w+b
# psv = 1
# nsv = -1
# dec = 0
def hyperplane_value(x,w,b,v):
return (-w[0]*x-b+v) / w[1]
datarange = (min_feature_value*0.9,max_feature_value*1.)
hyp_x_min = datarange[0]
hyp_x_max = datarange[1]
# (w.x+b) = 1
# positive support vector hyperplane
psv1 = hyperplane_value(hyp_x_min, w, b, 1)
psv2 = hyperplane_value(hyp_x_max, w, b, 1)
ax.plot([hyp_x_min,hyp_x_max],[psv1,psv2], 'k')
# (w.x+b) = -1
# negative support vector hyperplane
nsv1 = hyperplane_value(hyp_x_min, w, b, -1)
nsv2 = hyperplane_value(hyp_x_max, w, b, -1)
ax.plot([hyp_x_min,hyp_x_max],[nsv1,nsv2], 'k')
# (w.x+b) = 0
# positive support vector hyperplane
db1 = hyperplane_value(hyp_x_min, w, b, 0)
db2 = hyperplane_value(hyp_x_max, w, b, 0)
ax.plot([hyp_x_min,hyp_x_max],[db1,db2], 'y--')
plt.axis([-5,10,-12,-1])
plt.show()
visualize(data_dict)
</syntaxhighlight>
[[File:分类.png|800px]]
==参见==
* [https://en.wikipedia.org/wiki/In_situ_adaptive_tabulation 动态自适应建表算法]
* [https://en.wikipedia.org/wiki/Kernel_method 核方法]
* [https://en.wikipedia.org/wiki/Fisher_kernel Fisher核]
* [https://en.wikipedia.org/wiki/Platt_scaling 概率输出]
* [https://en.wikipedia.org/wiki/Polynomial_kernel 多项式核]
* [https://zh.wikipedia.org/wiki/%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90 预测分析]
* [https://en.wikipedia.org/wiki/Regularization_perspectives_on_support_vector_machines SVM正则化]
* [https://zh.wikipedia.org/wiki/%E7%9B%B8%E5%85%B3%E5%90%91%E9%87%8F%E6%9C%BA 相关向量机]，是一个函数形式与支持向量机相同的概率稀疏核模型。
* [https://zh.wikipedia.org/wiki/%E5%BA%8F%E5%88%97%E6%9C%80%E5%B0%8F%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95 序列最小优化算法]
* [https://en.wikipedia.org/wiki/Space_mapping 空间映射]
* [https://en.wikipedia.org/wiki/Winnow_(algorithm) Winnow算法]
==参考==
<references />
==文献 ==
* Theodoridis, Sergios; and Koutroumbas, Konstantinos; ''Pattern Recognition'', 4th Edition, Academic Press, 2009, ISBN|978-1-59749-272-0
* Cristianini, Nello; and Shawe-Taylor, John; ''[http://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]", in ''Supervised, Semi-supervised, and Unsupervised Learning'', Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN|3-540-31681-7
* Kecman, Vojislav; ''[http://www.support-vector.ws Learning and Soft Computing — Support Vector Machines, Neural Networks, Fuzzy Logic Systems]'', 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]'', 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.] (2004); [http://www.csse.monash.edu.au/~dld/David.Dowe.publications.html#TanDowe2004 ''MML Inference of Oblique Decision Trees''], Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, [http://www.csse.monash.edu.au/~dld/Publications/2004/Tan+DoweAI2004.pdf pp. 1082–1088] ''(This paper uses 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 ''(this is a reprint of Vapnik's early book describing philosophy behind SVM approach; the 2006 Appendix describes recent developments)''
* Fradkin, Dmitriy; and Muchnik, Ilya; "[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. 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?]", ''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]", in ''Reviews in Computational Chemistry'', Volume 23, 2007, pp. 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]'', Morgan and Claypool, 2011 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
== 外部链接 ==
* [http://www.csie.ntu.edu.tw/~cjlin/libsvm/ libsvm], LIBSVM is a popular library of SVM learners
* [http://www.csie.ntu.edu.tw/~cjlin/liblinear/ liblinear] is a library for large linear classification including some SVMs
* [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] is a GUI demo for [https://en.wikipedia.org/wiki/JavaScript JavaScript] implementation of SVMs
----
本中文词条由乌丢丢 翻译编辑，由 HengFlynn 审校，[[用户:张江|张江]]总审校，[[用户:费米子|费米子]]编辑，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[category:神经网络]]
[[category:机器学习]]
[[category:人工智能]]