【关于 支持向量机】那些你不知道的事

​

​

一、原理篇​

1.1 什么是SVM？​

•

数学模型​

支持向量机的提出基于统计学习理论和结构风险最小化准则，统计学习理论避免分类模型受样本量的限制，结构风险最小化准则避免模型训练时出现的模型问题。在这样的背景下，支持向量机技术的推广及其判别能力较强，其最终的目的是根据输入数据样本寻找到一个最优分类超平面。​

支持向量机最优分类面的求解问题可转化为求数据样本分类间隔最大化的二次函数的解，关键是求得分类间隔最大值的目标解。以两类线性可分数据为例，一类数据用圆形代表，另一类数据用菱形代表,则最优分类线示例图如图1所示。​

​

​

​

代码块​

Plain Text

图1中， margin代表分类平面间的最大分类间隔，处于分类线两侧的数据点为待分类的样本。​

在该例图中，基本分类判别面方程如公式(1)所示，若对线性可分的样本集进行数据归一化处理，分类间隔表达式如公式(2)所示。​

​

​

​

​

代码块​

Plain Text

基于上述分析，通过加入有效约束条件，引入拉格朗日乘子后，解得最优分类判别函数，且其参数的确定依赖于支持向量。实际应用中，核函数结合最优分类判别面形成的支持向量机模型解决了其只处理线性可分样本的弊端，两者结合形成最终的支持向量机模型。​

​

相应的通用支持向量机分类函数表达式如公式(3)所示。​

​

​

​

​

代码块​

Plain Text

公式(3)中, a*i和b*i是调控支持向量机确定最优分类平面的参数。​

​

•

核支持向量机​

支持向量机是基于两类线性可分的样本数据发展而来，但是在实际应用中，需要识别和分类的数据大多数情况下都处于非线性不可分状态，并非理想化状态。由此，研究人员设计一个核函数应用于支持向量机的分类过程中解决该问题，其主要目的是将原低维空间中非线性不可分数据映射到高维空间中，即解决低维特征空间无法构造分类超平面的问题。支持向量机的应用性能关键在于核函数方法的选取。​

核函数方法计算公式如下所示:​

​

​

​

代码块​

Plain Text

公式(4)表示在特征空间直接计算内积，φ代表x映射到内积特征空间的过程。​

​

(1)线性核​

​

​

​

代码块​

Plain Text

公式(5)代表数据所处的原空间中的内积计算。其作用是统一两空间数据形式，即数据处于原空间的形式与数据经映射后所处空间的形式。​

​

(2)多项式核​

​

​

​

代码块​

Plain Text

公式(6)代表多项式空间中的内积计算,注重数据的全局性。其计算过程不同于线性核,这是由于直接在多项式空间计算会造成维数灾难，所以其计算包含一个转换过程,即从高维空间转到低维空间，利用低维空间计算其内积值。​

​

(3) Sigmoid核​

​

​

​

代码块​

Plain Text

公式(7)实现将 Sigmoid函数作为核函数，其近似为多层感知器神经网络，注重样本数据的全局最优值。​

​

(4)Gauss径向基核(RBF)​

​

​

​

代码块​

Plain Text

公式(8)可将原始特征空间映射到无穷维特征空间中，其性能好坏在于y参数的调控,局部性较强。y参数选取的值较小,映射后的特征空间近似一个低维空间；y参数选取的值较大,易造成过拟合问题.正因为其具有较强的可调控性,其在实际应用中更为广泛。​

​

实际应用中，研究者通过权衡各个核函数的优势与劣势，通常将最佳的核函数应用于特定数据分类领域中。将上述介绍的核函数与支持向量机结合后用于实验中的Matlab 代码实现如表1所示。​

​

​

​

二、算法篇​

​

代码块​

Plain Text

基本的支持向量机算法基本思想是在二次规划的基础上不断迭代寻找支持向量,主要有块算法、分解算法、序列最小优化算法﹑增量算法等，下面介绍这几种基本的支持向量机算法。​

​

2.1 什么是块算法？​

​

代码块​

Plain Text

Chunking算法的出发点是删除矩阵中对应Lagrange乘数为零的行和列将不会影响最终的结果。对于给定的样本，Chunking算法的目标是通过某种迭代方式逐步排除非支持向量，从而降低训练过程对存储器容量的要求。具体做法是，将一个大型QP问题分解为一系列较小规模的QP问题,然后找到所有非零的Lagrange乘数并删除。在算法的每步中Chunking都解决一个QP问题，其样本为上一步所剩的具有非零Lagrange乘数的样本以及M个不满足KKT条件的最差样本。如果在某一步中,不满足KKT条件的样本数不足M个，则这些样本全部加入到新的QP问题中。每个QP子问题都采用上一个QP子问题的结果作为初始值。在算法进行到最后一步时，所有非零Lagrange乘数都被找到，从而解决了初始的大型QP问题。​

​

2.2 什么是分解算法？​

​

代码块​

Plain Text

分解算法最早在1997年OSUNA等人中提出，是目前有效解决大规模问题的主要方法。分解算法将二次规划问题分解成一系列规模较小的二次规划子问题，进行迭代求解。在每次迭代中，选取拉格朗日乘子分量的一个子集做为工作集，利用传统优化算法求解一个二次规划的子问题。以分类SVM为例，分解算法的主要思想是将训练样本分成工作集B和非工作集N，工作集B中的样本个数为q，q远小于训练样本总数。每次只针对工作集B中的样本进行训练，而固定N中的训练样本。该算法的关键在于选择一种最优工作集选择算法，而在工作集的选取中采用了随机的方法，因此限制了算法的收敛速度。​

​

2.3 什么是序列最小优化算法？​

​

代码块​

Plain Text

​

2.4 什么是增量算法？​

​

代码块​

Plain Text

增量学习是机器学习系统在处理新增样本时，能够只对原学习结果中与新样本有关的部分进行增加修改或删除操作，与之无关的部分则不被触及。增量训练算法的一个突出特点是支持向量机的学习不是一次离线进行的，而是一个数据逐一加入反复优化的过程。​

​

SYED等人在1999年最早提出了SVM增量训练算法，每次只选一小批常规二次算法能处理的数据作为增量，保留原样本中的支持向量和新增样本混合训练，直到训练样本用完。GAUWENBERGHS等人提出了增量训练的精确解，即增加一个训练样本或减少一个样本对Lagrange系数和支持向量的影响。RALAIVOLA等人提出了另一种增量式学习方法，其思想是基于高斯核的局部特性，只更新对学习机器输出影响最大的Lagrange系数，以减少计算复杂度。孔锐等人提出了一种“快速增量学习算法”，该算法依据边界向量不一定是支持向量，但支持向量一定是边界向量的原理，首先选择那些可能成为支持向量的边界向量，进行SVM的增量学习，找出支持向量，最终求出最优分类面，提高训练速度。孔波等人提出了基于中心距离比值的增量运动向量机，利用中心距离比值，在保证训练和测试准确率没有改变的情况下，提高收敛速度。李东晖等人提出了基于壳向量的线性SVM增量学习算法，通过初始样本集求得壳向量，进行SVM训练，得到支持向量集降低二次规划过程的复杂度，提高整个算法的训练速度和分类精度。​

​

三、其他SVM篇​

3.1 什么是最小二次支持向量机？​

​

​

​

代码块​

Plain Text

​

​

​

3.2 什么是模糊支持向量机？​

​

代码块​

Plain Text

由于实际样本检测时存在不同程度的噪声，需要从样本数据中将非正常数据筛以除降低其影响。具体实施方法为:通过在训练样本数据集中增加每个样本的隶属度项,如对样本中的噪声数据和孤立点给予较小的隶属度,正常的样本赋予较大的隶属度,从而对不同的样本起到惩罚作用，降低噪声数据对分类最优平面的影响。模糊支持向量机算法结合模糊数学方法通过在基本支持向量机算法的基础上增加隶属度值对最优平面起到调节作用,提高分类精度。但样本数据中如果异常数据较多时,会影响支持向量机的泛化学习能力,另外由于增加了隶属度项,使得核函数计算复杂,训练速度降低。​

​

3.3 什么是粒度支持向量机？​

​

代码块​

Plain Text

GSVM的主要思想是通过常用的粒度划分方法构建粒度空间获得一系列信息粒，然后在每个信息粒上进行学习，最后通过聚合信息粒上的信息(或数据、规则知识、属性等)获得最终的支持向量机决策函数。该学习机制通过数据的粒化可以将一个线性不可分问题转化为一系列线性可分问题，从而获得多个决策函数;该学习机制还使数据的泛化性能增强，即可在SVM的训练中得到间隔更宽的超平面。​

​

原空间的GSVM模型在原空间进行粒划分，然后在核空间进行SVM学习。基于关联规则的GSVM是TANG等人提出的，其基本思想是通过RBF核函数原空间的样本映射到特征空间并展开成麦克劳林级数，并从展开式中挖掘对分类分析起重要作用的关联规则，利用这些有用的相关关联规则划分粒度，从而在SVM的分类模式中学习出关联规则分类器。基于聚类的GSVM，其基本思想是首先采用常用的聚类方法结合一定的评价规则将原始数据划分为若干个粒，然后选择其中含有较多信息量的粒参与SVM的分类或者回归，使SVM在大规模数据集的训练中能得到较高的效率和泛化能力。基于粗糙集的GSVM，其基本思想是首先用粗糙集对数据进行预处理，以达到减少冗余数据，压缩数据规模的目的，进而提高支持向量机的分类速度。基于树形层次结构的GSVM33其基本思想是根据聚类训练结果对正类数据与负类数据分别构造两棵“支持向量粒度树”，离边缘较近的继续延伸，直到达到需要的精度为止。此外，我国还有很多学者研究基于商空间(34-35]、决策树、神经网络的GSVM学习算法。​

​

GUO和王文剑等人提出的核空间的GSVM(KGSVM)模型首先将原始数据映射到核空间，然后在核空间进行粒的划分和粒的代替，最后在相同的核空间中进行粒的SVM训练。与传统的GSVM模型相比，KGSVM模型克服了核空间数据分布不一致的问题。传统的GSVM由于分粒是在原空间中进行的，粒划分时非常可能丢失大量有用的信息。但是GSVM是在核空间中进行粒的划分和替代，因此可以利用半径规则获得更好的分类精度和泛化性能。张文浩等人对KGSVM模型进行了改进,提出了核粒度下基于关联规则的GSVM。​

​

3.4 什么是多类训练算法？​

​

代码块​

Plain Text

随着研究问题的复杂化,现实的分类问题不单纯是正反两类,会存在多类的现象。对多分类问题需构造多类SVM分类器,主要通过目标函数和分类器来完成。对应的实现途径主要有两种:一种是通过选取合适的目标函数来实现k类分类支持向量机。由于实际问题存在多类,因而选择的目标函数变量多,求解过程复杂,一般只用于解决小型问题。另--种实现方法基于两分类器的分类思想,将多个两分类器进行组合,主要方法有一对多算法、一对一算法﹑决策导向无环图。一对多算法对k个类的样本需构造k个分类器,样本对应的决策函数最大即为所对应的类。一对一算法对k类训练样本中的任两类构造一个分类器,两两组合构造多个分类器,然后在这些分类器中使用投票法累计各个类的投票数,其中得票数最多的类即为样本点所属的类。当类别较大时组合分类器数量较多,影响分类预测速度。对此Platt等提出了一个新的学习架构:决策导向无环图。每个分类器有两类,类似于二叉树,在分类过程中由根部开始经各层中间节点逐步向叶节点分类,这种分类方法能提高支持向量机的分类速度和性能。​

​

3.5 什么是孪生支持向量机？​

​

代码块​

Plain Text

JAYADCVA等人提出了一种二值数据的分类器——孪生支持向量机(又称双分界面支持向量机)。TWSVMs在形式上类似于传统的支持向量机,不仅具有传统支持向量机的优点，而且对大规模数据具有更好的处理能力。TWSVMs为两个类各自得到一个分类平面，属于每个类的数据尽量围绕在与之相对应的分类平面周围，然后TWSVMs通过优化一对分类平面来构建分类超平面。也就是说，TWSVMs需要解决一对QP问题，而SVM则是解决一个QP问题，但是在TWSVMs中，其中一个类的数据要作为另一个QP问题的约束条件，反之亦然。​

​

尽管TWSVMs相比较于SVM具有更为快速的训练速度，但如今信息时代面临的是“数据海量，知识匮乏”，对于机器学习是一个很大的挑战，同样，对TWSVMs而言，训练速度也非常重要。尽管目前传统SVM已有许多成熟的学习算法,并且也可以推广到孪生模型，但这些算法并没有考虑到孪生模型的具体区别，因而有必要提出基于具体孪生模型的高效学习算法，以体现TWSVMs的具体特性。另外，现有的孪生模型并不具有类似于传统支持向量机的特性，即间隔。因此，如果能将孪生模型与传统支持向量的优点成功结合在一起，则可以得到既具有较快训练速度又具有较好理论基础的孪生支持向量机模型。​

​

有了好的模型、好的算法之后，可以考虑将孪生模型推广到一些具体问题，如半监督学习问题、模糊或区间数据的学习问题、回归问题，并将该模型推广到各类实际问题，特别是生物信息学方面的应用，如基因调控网络预测。​

​

3.6 什么是排序支持向量机？​

​

代码块​

Plain Text

排序学习是当前信息检索和机器学习领域的热点问题，广泛应用于许多领域，包括文档检索、协同过滤、关键字提取、定义发现等等。排序学习问题大致分为基于回归的排序学习和基于分类的排序学习两类。从上面的介绍可以看出，SVM的排序学习模型可以基于分类又可以基于顺序回归，所以自RSVM 61提出以来，该排序学习方法便得到了很大的发展。​

​

RSVM在应用中大部分用于信息检索，其中最主要的问题是如何针对检索问题建立适用于具体应用的损伤函数。可以与基本的SVM一样，两类数据使用相同的代价函数;也可以针对两类数据分别建立不同的代价函数，对某些应用会大大提高排序的精确度。​

​

YAJIMA等人将RSVM用于推荐系统，文中使用1-SVM对给定数据的相关度顺序进行预测，通过使用图核处理数据集，取得了很好的效果。SVM的回归排序模型也能用于推荐系统，与传统的使用启发式的推荐系统相比，该方法在大样本下的性能是相当高效的。​

​

在实际应用中，速度永远是人们追求的目标。传统的RSVM都是使用2-SVM进行学习，YU等人使用1-SVM学习排序，该方法可以使用更少的支持向量，大大提高训练速度。参数选择对于SVM的训练速度起着至关重要的作用，使用用于核方法的正则化路径方法可以加速RSVM中的参数选择并使该过程自动化，从而提高训练速度。在分子测序中，由于数据为结构数据，RSVM的训练速度很长，将粒度计算与RSVM结合，使用粒度计算进行属性约简和问题分割，在保证学习质量的情况下提高训练速度。​

​

Q.A​

•

SVM如何解决多分类问题（面试题） 或者SVM可以用来划分多类别吗? 如果可以，要怎么实现？（面试题）​

一般有两种做法：​

1）直接法：直接在目标函数上修改，将多个分类面的参数求解合并到一个最优化问题里面。看似简单但是计算量却非常的大。​

2）间接法：对训练器进行组合。其中比较典型的有一对一，和一对多。​

一对多：对每个类都训练出一个分类器，由svm是二分类，所以将此而分类器的两类设定为目标类为一类，其余类为另外一类。这样针对k个类可以训练出k个分类器，当有一个新的样本来的时候，用这k个分类器来测试，那个分类器的概率高，那么这个样本就属于哪一类。这种方法效果不太好，bias比较高。​

四、应用篇​

4.1 模式识别​

​

代码块​

Plain Text

在手写字体识别方面,当采用5层神经网络算法时,其识别的错误率为5.1%;贝尔实验室最先将SVM应用于手写字体识别研究,选取三种不同的核函数时,得到的误识率分别为4.0% ,4.1%和4.2%,可看出支持向量机方法比神经网络算法具有更好的分类准确性。柳回春等在SVM 的基础上结合与RBF神经网络将其用于UK心理测试自动分析系统的手写体数字识别问题。手写体识别属于多类问题。相关专家学者在研究2类问题的SVM前提下,形成了能够处理多类问题的相关SVM，其中主要核函数就是sigmoid核函数、径向基核函数、多项式核函数。不但可以支持比较其他分类和支持向量机，还能够支持比较不同形式的SVM,经过大量实践可以发现，存在很大优势。​

​

在人脸识别方面,由于人脸图像存储和SVM训练需要大量的存储空间,周志明等人将小波变换与支持向量机相结合,由小波变换提取人脸特征,减小特征向量维数并将其输入到SVM中,并结合最近邻分类器进行分类,提高了分类器的鲁棒性和分类精度。相关学者和专家经过不断研究和分析以后形成以层次结构形式的支持向量机分类器,由一个非线性和线性支持向量机构成，上述方式不但具备比较低的误差率和比较高的检测率，还存在比较快的速度。此后，人们利用SVM方式来有效判断人脸姿态，并且合理分为6个类别，手工标定方式在多姿态人脸库中发现测试样本和训练样本集，在SVM基础上的训练集姿态分类器,可以降低到1.67%的错误率。在支持向量机和小波技术上形成的识别人脸技术,压缩提取人脸特征的时候应用小波技术,然后结合支持向量机技术和邻近分类器进行分类，确保具备比较好的鲁棒性能和分类性能。​

​

4.2 网页分类​

​

代码块​

Plain Text

在中文网页分类问题上,贺海军等在网页文本的特征表示和二分类问题的基础上,把二叉决策树和SVM算法相结合构成多类分类器,实现网页文本的分类,取得了较好的分类效果和训练速度。​

​

在网络入侵检测分类方面,网络入侵检测其实也是一种网页分类。徐文龙等提出了一种基于从特殊到特殊的直推式支持向量机,从获取的网络数据中进行归纳式学习和标记样本,从中提出特征输入到TSVM学习机中进行学习,检测其异常的网络入侵,提高了测试样本的分类准确度。​

​

4.3 系统建模与系统辨识​

​

代码块​

Plain Text

在未知非线性系统建模方面,张浩然等'利用对象的输入输出数据集,在非线性系统的控制结构设计中采用支持向量机建模来获取对象的动态特性,以SVM作为辨识器在控制器中采用指数梯度法实现控制作用。​

​

在非线性系统的辨识方面,崔万照等将最小二乘方法应用于支持向量机算法中并选择小波函数作为支持向量机的核函数,构造最小二乘小波支持向量机来解决单输人单输出(SISO)非线性系统的辨识问题,仿真结果表明此方法能提高辨识效果,加快系统响应时间。​

​

4.4 其他​

​

代码块​

Plain Text

支持向量机具备一定的优越性,已经得到大量应用。专家学者提出了支持向量机基础上的水印算法,在数字水印中合理应用支持向量机，存在十分良好的应用效果。并且入侵监测系统已经是十分重要的网络安全技术之一，在分析入侵检测系统的时候，主要应用的就是SVM基础上的主动学习算法，可以在一定程度上降低学习样本,能够增加入侵监测系统整体分类性能。在处理图像中迷糊噪音的时候,依据SVM模糊推理方式形成的一种噪音检测系统,上述方式能够合理除去检测中的噪音,适当保存图像相关信息。在分析混合气体定量和多维光谱定性的时候，不能应用同一种方式来定性和定量分析组合气体吸收普线重叠、输入光谱的维数,训练样本数目有限，在分析地混合气体多维光谱的时候应用支持向量机,依据核函数有效把重叠光谱数据变为支持向量机回归模型,此时可以定量分析混合气体的组分浓度以及定性分析种类。​

​

五、对比篇​

•

SVM和LR的区别与联系？（面试题）​

•

或者SVM和Logistic回归的异同？（面试题）​

1）相同点​

​

代码块​

Plain Text

第一，LR和SVM都是分类算法。​

​

看到这里很多人就不会认同了，因为在很大一部分人眼里，LR是回归算法。我是非常不赞同这一点的，因为我认为判断一个算法是分类还是回归算法的唯一标准就是样本label的类型，如果label是离散的，就是分类算法，如果label是连续的，就是回归算法。很明显，LR的训练数据的label是“0或者1”，当然是分类算法。其实这样不重要啦，暂且迁就我认为它是分类算法吧，再说了，SVM也可以回归用呢。​

​

​

2）不同点​

​

代码块​

Plain Text

第一，本质上是其损失函数（loss function）不同。lr的损失函数是 cross entropy loss， adaboost的损失函数是 expotional loss ,svm是hinge loss，常见的回归模型通常用 均方误差 loss。​

​

SVM 和正则化的逻辑回归它们的损失函数：​

​

​

​

​

代码块​

Plain Text

第二，支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局（远离的点对边界线的确定也起作用）。​

​

第三，在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法。​

​

第四，线性SVM依赖数据表达的距离测度，所以需要对数据先做normalization，LR不受其影响。​

​

第五，SVM的损失函数就自带正则（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因；而LR必须另外在损失函数上添加正则项。​

​

•

说LR和SVM损失函数。（面试题）​

•

SVM框架下引入Logistic函数:输出条件后验概率？（面试题）​

•

感知机的对偶形式和SVM对偶形式的对比（面试题）​

•

为什么要用对偶形式？如何理解对偶函数的引入对计算带来的优势？（面试题）​

​