支持向量机

维基百科,自由的百科全书
跳转至: 导航搜索

支持向量机英语Support Vector Machine,常简称為SVM)是一种監督式學習的方法,可广泛地应用于统计分类以及回归分析

支持向量机属于一般化线性分类器,也可以被认为是提克洛夫规范化(Tikhonov Regularization)方法的一个特例。这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区,因此支持向量机也被称为最大边缘区分类器。

介绍[编辑]

支持向量机构造一个超平面或者多个超平面,这些超平面可能是高维的,甚至可能是无限多维的。在分类任务中,它的原理是,将决策面(超平面)放置在这样的一个位置,两类中接近这个位置的点距离的都最远。我们来考虑两类线性可分问题,如果要在两个类之间画一条线,那么按照支持向量机的原理,我们会先找两类之间最大的空白间隔,然后在空白间隔的中点画一条线,这条线平行于空白间隔。通过核函数,可以使得支持向量机对非线性可分的任务进行分类。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt和Barnard将支持向量机和其他分类器进行了比较。

机的意思就是算法,机器学习领域里面常常用“机”这个字表示算法。支持向量意思就是数据集种的某些点,位置比较特殊,我们找这条直线的时候,一般就看聚集在一起的两类数据,他们各自的最边缘位置的点,也就是最靠近划分直线的那几个点,而其他点对这条直线的最终位置的确定起不了作用,所以我姑且叫这些点叫“支持点”(即有用的点),但是在数学上,没这种说法,数学里的点,又可以叫向量,比如二维点(x,y)就是二维向量,三维度的就是三维向量(x,y,z)。所以“支持点”改叫“支持向量”。

动机[编辑]

有很多个分类器(超平面)可以把数据分开,但是只有一个能够达到最大分割。

我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是\mathbb{R}^2中的点,而可以是任意\mathbb{R}^p(统计学符号)中或者\mathbb{R}^n(计算机科学符号)的点。我们希望能够把这些点通过一个n-1维的超平面分开,通常这个被称为线性分类器。有很多分类器都符合这个要求,但是我们还希望找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。

问题定义[编辑]

设样本属于两个类,用该样本训练svm得到的最大间隔超平面。在超平面上的样本点也称为支持向量.

我们考虑以下形式的n个点的测试集\mathcal{D},

\mathcal{D}=\{(\mathbf{x}_i,y_i)| \mathbf{x}_i \in \mathbb{R}^p, y_i \in \{-1,1\} \}_{i=1}^{n}

其中y_i-1或者1

超平面的数学形式可以写作:

\mathbf{w}\cdot\mathbf{x} - b=0

其中\mathbf{x}是超平面上的点,\mathbf{w}是垂直于超平面的向量。

根据几何知识,我们知道\mathbf{w}向量垂直于分类超平面。加入位移b的目的是增加间隔。如果没有b的话,那超平面将不得不通过原点,限制了这个方法的灵活性。

由于我们要求最大间隔,因此我们需要知道支持向量以及(与最佳超平面)平行的并且离支持向量最近的超平面。我们可以看到这些平行超平面可以由方程族:

\mathbf{w}\cdot\mathbf{x} - b=1
\mathbf{w}\cdot\mathbf{x} - b=-1。来表示。由于\mathbf{w}只是超平面的法向量,长度未定,是一个变量,所以等式右边的1和-1只是为计算方便而取的常量,其他常量只要互为相反数亦可。

如果这些训练数据是线性可分的,那就可以找到这样两个超平面,在它们之间没有任何样本点并且这两个超平面之间的距离也最大。通过几何不难得到这两个超平面之间的距离是2/|w|,因此我们需要最小化 |w|。同时为了使得样本数据点都在超平面的间隔区以外,我们需要保证对于所有的i满足其中的一个条件

\mathbf{w}\cdot\mathbf{x_i} - b \ge 1\qquad\mathrm{or}
\mathbf{w}\cdot\mathbf{x_i} - b \le -1\qquad\mathrm{}

这两个式子可以写作:

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1, \quad 1 \le i \le n.\qquad\qquad (1)

原型(Primal form)[编辑]

现在寻找最佳超平面这个问题就变成了在(1)这个约束条件下最小化|w|.这是一个二次規劃QP (quadratic programming)最优化中的问题。

更清楚的表示:

\arg\min_{\mathbf{w},b}{||\mathbf{w}||^2\over2},满足y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1其中i = 1, \dots, n

1/2这个因子是为了数学上表达的方便加上的。

解如上约束问题,通常的想法可能是使用非负拉格朗日乘数\alpha_i于下式

\arg\min_{\mathbf{w},b } \max_{\boldsymbol{\alpha \geq 0} } \{ \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b)-1]} \}

此式表明我们寻找一个鞍点。这样所有可以被y_i(\mathbf{w}\cdot\mathbf{x_i} - b) - 1 > 0 分离的点就无关紧要了,因为我们必须设置相应的\alpha_i为零。

这个问题现在可以用标准二次规划技术标准和程序解决。结论可以表示为如下训练向量的线性组合

\mathbf{w} = \sum_{i=1}^n{\alpha_i y_i\mathbf{x_i}}

其中只有很少的\alpha_i会大于0.对应的\mathbf{x_i}就是支持向量,这些支持向量在边缘上并且满足y_i(\mathbf{w}\cdot\mathbf{x_i} - b) = 1.由此可以推导出支持向量也满足:\mathbf{w}\cdot\mathbf{x_i} - b = 1 / y_i = y_i  \iff b = \mathbf{w}\cdot\mathbf{x_i} - y_i。因此允许定义偏移量b.在实际应用中,把所有支持向量N_{SV}的偏移量做平均后鲁棒性更强:

b = \frac{1}{N_{SV}} \sum_{i=1}^{N_{SV}}{(\mathbf{w}\cdot\mathbf{x_i} - y_i)}

对偶型(Dual Form)[编辑]

把原型的分类规则写作对偶型,可以看到分类器其实是一个关于支持向量(即那些在间隔区边缘的训练样本点)的函数。

根据||\mathbf{w}||^2=\mathbf{w}\cdot\mathbf{w},并且带入\mathbf{w}=\sum_{i=1}^n\alpha_i y_i\mathbf{x_i},可以得到支持向量机的对偶型如下: \max_{\alpha} \sum_{i=1}^n\alpha_i - \sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^Tx_j

满足 \alpha_i \ge 0

\sum_{i=1}^n \alpha_iy_i = 0

后验svm[编辑]

后验概率对分类器非常重要分类器的输出必须结合后验概率才能确定借助后验概率更好的改进超平面的泛化能力

软间隔(Soft margin)[编辑]

1995年, Corinna Cortes与Vapnik提出了一种改进的最大间隔区方法,这种方法可以处理标记错误的样本。如果可区分正负例的超平面不存在,则“软边界”将选择一个超平面尽可能清晰地区分样本,同时使其与分界最清晰的样本的距离最大化。这一成果使术语“支持向量机”(或“SVM”)得到推广。这种方法引入了松驰参数\xi_i以衡量对数据x_i的误分类度。

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i \quad 1 \le i \le n \quad\quad (2)。随后,将目标函数与一个针对非0\xi_i的惩罚函数相加,在增大间距和缩小错误惩罚两大目标之间进行权衡优化。如果惩罚函数是一个线性函数,则等式(3)变形为
 \min ||w||^2 + C \sum_i \xi_i \quad \mathbf{subject \; to \;}y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i \quad 1 \le i \le n

非线性分类[编辑]

回归[编辑]

解决问题的参数方法大多通过解决那些最优化的问题派生出来的,现有一些从SVM问题中诞生出来的可以快速解决QP问题的的算法,他们主要依靠把问题分割成更小更容易管理的模块的方法来实现。

一个通用的算法是Platt's Sequential Minimal Optimization (SMO)算法,他把问题分成了若干个在二维空间成可以被解析的子问题,这样避开了需要解决数值最优化问题的难度。

另一个研究就是用使用了牛顿迭代的内点法找到Karush–Kuhn–Tucker情况下原始对偶问题的解决方法。与那些解决一系列小问题不同的是,这项研究直接解决了整体部分。避开解决这个线性问题的过程离不开核矩阵,矩阵的低阶近似往往是内核中使用技巧。

应用[编辑]

  • 用于文本和超文本的分类,在归纳和直推方法中都可以显著减少所需要的有类标的样本数。
  • 用于图像分类。实验结果显示:在经过三到四轮相关反馈之后,比起传统的查询优化方案,支持向量机能够取得明显更高的搜索准确度。
  • 用于医学中分类蛋白质,超过90%的化合物能够被正确分类。
  • 用于手写字体识别。

参见[编辑]

参考书目[编辑]

  • B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In D. Haussler, editor, 5th Annual ACM Workshop on COLT, pages 144-152, Pittsburgh, PA, 1992. ACM Press.
  • Corinna Cortes and V. Vapnik, "Support-Vector Networks, Machine Learning, 20, 1995. [1]
  • Christopher J. C. Burges. "A Tutorial on Support Vector Machines for Pattern Recognition". Data Mining and Knowledge Discovery 2:121 - 167, 1998 (Also available at CiteSeer: [2]
  • Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000. ISBN 0-521-78019-5 [3] SVM Book)
  • Harris Drucker, Chris J.C. Burges, Linda Kaufman, Alex Smola and Vladimir Vapnik (1997). "Support Vector Regression Machines". Advances in Neural Information Processing Systems 9, NIPS 1996, 155-161, MIT Press.
  • Huang T.-M., Kecman V., Kopriva I.(2006), Kernel Based Algorithms for Mining Huge Data Sets, Supervised, Semi-supervised, and Unsupervised Learning, Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN 3-540-31681-7[4]
  • Vojislav Kecman: "Learning and Soft Computing - Support Vector Machines, Neural Networks, Fuzzy Logic Systems", The MIT Press, Cambridge, MA, 2001.[5]
  • Tapio Pahikkala, Sampo Pyysalo, Jorma Boberg, Aleksandr Mylläri and Tapio Salakoski. Improving the Performance of Bayesian and Support Vector Classifiers in Word Sense Disambiguation using Positional Information. In Proceedings of the International and Interdisciplinary Conference on Adaptive Knowledge Representation and Reasoning(AKRR'05), Jun 2005.
  • Bernhard Schölkopf and A. J. Smola: Learning with Kernels. MIT Press, Cambridge, MA, 2002. (Partly available on line: [6].)ISBN 0-262-19475-9
  • Bernhard Schölkopf, Christopher J.C. Burges, and Alexander J. Smola (editors). "Advances in Kernel Methods: Support Vector Learning". MIT Press, Cambridge, MA, 1999. ISBN 0-262-19416-3. [7]
  • John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004. ISBN 0-521-81397-2 [8] Kernel Methods Book)
  • P.J. Tan and D.L. Dowe(2004), MML Inference of Oblique Decision Trees, Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, pp1082-1088. Links require password.(This paper uses minimum message lengthMML)and actually incorporates probabilistic support vector machines in the leaves of decision trees.)
  • Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1999. ISBN 0-387-98780-0
  • Chien-Yi Wang, "The fusion of support vector machine and Multi-layer Fuzzy Neural Network". Machine Learning, Jun, 2012.

外部链接[编辑]

概念[编辑]

软件[编辑]

  • Lush -- an Lisp-like interpreted/compiled language with C/C++/Fortran interfaces that has packages to interface to a number of different SVM implementations. Interfaces to LASVM, LIBSVM, mySVM, SVQP, SVQP2 (SVQP3 in future) are available. Leverage these against Lush's other interfaces to machine learning, hidden markov models, numerical libraries(LAPACK, BLAS, GSL), and builtin vector/matrix/tensor engine.
  • SVMlight -- a popular implementation of the SVM algorithm by Thorsten Joachims; it can be used to solve classification, regression and ranking problems.
  • LIBSVM -- A Library for Support Vector Machines, Chih-Chung Chang and Chih-Jen Lin
  • YALE -- a powerful machine learning toolbox containing wrappers for SVMLight, LibSVM, and MySVM in addition to many evaluation and preprocessing methods.
  • LS-SVMLab - Matlab/C SVM toolbox - well-documented, many features
  • Gist -- implementation of the SVM algorithm with feature selection.
  • Weka -- a machine learning toolkit that includes an implementation of an SVM classifier; Weka can be used both interactively though a graphical interface or as a software library.(One of them is called "SMO". In the GUI Weka explorer, it is under the "classify" tab if you "Choose" an algorithm.)
  • OSU SVM - Matlab implementation based on LIBSVM
  • Torch - C++ machine learning library with SVM
  • Shogun - Large Scale Machine Learning Toolbox with interfaces to Octave, Matlab, Python, R
  • Spider - Machine learning library for Matlab
  • kernlab - Kernel-based Machine Learning library for R
  • e1071 - Machine learning library for R
  • SimpleSVM - SimpleSVM toolbox for Matlab
  • SVM and Kernel Methods Matlab Toolbox
  • PCP -- C program for supervised pattern classification. Includes LIBSVM wrapper.
  • TinySVM -- a small SVM implementation, written in C++

互动SVM应用[编辑]