支持向量机

在机器学习中,支持向量机是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。

来源:Wikipedia
简介

在机器学习中,支持向量机是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。

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

当数据未被标记时,不能进行监督式学习,需要用非监督式学习,它会尝试找出数据到簇的自然聚类,并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类,当数据未被标记或者仅一些数据被标记时,支持向量聚类经常在工业应用中用作分类步骤的预处理。

[来源:wiki, URL:https://en.wikipedia.org/wiki/Support_vector_machine]

原理:

数据集:n个数据点

任何超平面都可以写成点集x向量满足:

如果训练数据是线性可分的,可以选择两个并行的超平面,将两类数据分开,这样它们之间的距离就尽可能大。被这两个超平面包围的区域称为“边缘”,最大限度的超平面是位于它们中间的超平面。有了适当的数据集,这些超平面可以被下列方程描述:

Soft margin:

这是计算margin的一种方法,当然计算margin的方法有hard margin。为了将SVM扩展到数据不可线性可分的情况,引入了sort margin.

如果上面的函数值为0,那么意思就是xi向量在正确的一边。对于错误边的数据,函数的值与边界的距离成比例。那么就是最小化所有点的Margin和,公式如下:

这里λ权衡边缘尺寸之间增加的变化,来保证xi向量能在正确的一边。对于足够小的λ值,如果输入数据是线性可分类的,那么soft margin SVM的行为将与hard margin SVM一致,但如果分类规则是可行的,则仍然会学习。

计算支持向量机分类器:

根据以上的了解,分类器的目的就是找到一个足够小的λ使得它能够服从hard margin分类器。为了最小化上述的目标函数,很多方法被提出:sub-gradient descent和coordinate descent。例子有:Primal,Dual,Kernel trick,Sub-gradient descent,Coordinate descent等。

SVM的求解过程,就是在一个n维向量空间中的点,找到个“超平面”把两种类型分开 ,并且“margin”最大。如上图所示,Boundary线就是超平面(这里展示的是两维空间,这也支持多个维度),涂满红色的苹果,和涂满黄色的香蕉就是支持向量。目标就是最大化margin.

发展历史

描述

最初的SVM算法是由Vladimir N. Vapnik和Alexey YaChervonenkis在1963年发明的。1992年,Bernhard E. Boser, Isabelle M. Guyon和Vladimir N. Vapnik提出了一种方法,通过将内核技巧应用到最大限度的超平面上,来创建非线性分类器。1993年,Corinna Cortes和Vapnik提出了目前的标准化身(soft margin),并于1995年出版。

1996年,Vladimir N. Vapnik、Harris Drucker、Christopher J. C. Burges、Linda Kaufman和Alexander J. Smola提出了支持回归的SVM版本。这种方法称为支持向量回归(SVR)。Transductive support vector machinesVladimir N. Vapnik in 1998,认为可以用过转换来获得用于没有标签的数据的半监督算法.2000,Scholkopf等人提出ν-Support Vector Regression.

Bayesian SVM 2011年,Polson和Scott展示了SVM通过数据增强技术承认贝叶斯解释。在这种方法中,SVM被视为一个图形化模型(通过概率分布来连接参数)。该扩展视图允许将贝叶斯技术应用于SVM,例如灵活的特性建模、自动超参数调优和预测不确定性量化。最近,Wenzel等人开发了一个可扩展的Bayesian SVM版本,使Bayesian SVMs应用于大数据。Multiclass SVM;Transductive support vector machines;Structured SVM;Bayesian SVM(2011)等都是SVM算法的变形和衍生,

主要事件

年份

事件

相关论文/Reference

1995

提出标准的SVM with Soft margin

Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20(3), 273-297.

1998

Burges, C. J.介绍了特征识别应用中的SVM

Burges, C. J. (1998). A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2(2), 121-167.

1999

Suykens, J. A., & Vandewalle, J.提出SVM分类器,讲SVM用于分类问题上

Suykens, J. A., & Vandewalle, J. (1999). Least squares support vector machine classifiers. Neural processing letters, 9(3), 293-300.

2011

Chang, C. C., & Lin, C. J.对当前的SVM算法进总结

Chang, C. C., & Lin, C. J. (2011). LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3), 27.

发展分析

瓶颈

SVM算法对大规模训练样本难以实施,由于SVM是借助二次规划来求解支持向量,而求解二次规划将涉及m阶矩阵的计算(m为样本的个数),当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法

未来发展方向

用SVM解决多分类问题存在困难,经典的支持向量机算法只给出了二类分类的算法,而在数据挖掘的实际应用中,一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树;再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点,结合其他算法的优势,解决多类问题的分类精度。如:与粗集理论结合,形成一种优势互补的多类问题的组合分类器。

Contributor: Ruiying Cai

相关人物
简介
相关人物