支持向量机原理

支持向量机原理

支持向量机于1995年正式发表，由于在文本分类任务中显示出卓越性能，很快成为机器学习的主流技术，并直接掀起了“统计学习”在2000年前后的高潮。但实际上，支持向量机的概念早在20世纪六十年代就已经出现，统计学习理论在70年代就已成型。对核函数的研究更早，Mercer定理可追溯到1909年，RKHS则在40年代就已被研究，但在统计学习兴起后，核技巧才真正成为机器学习的通用基本技术。

支持向量机(support vector machine)是一种分类算法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。支持向量机是针对二分类任务设计的，对多分类任务要进行专门的推广，对带结构输出的任务也已有相应的算法。

核函数直接决定了支持向量机于核方法的最终性能，但遗憾的是，核函数的选择是一个未决问题。多核学习使用多个核函数并通过学习获得其最优凸组合作为最终的核函数，这实际上是在借助集成学习机制。

替代损失函数在机器学习中被广泛使用。但是，通过求解替代损失函数得到的是否仍是原问题的解？这在理论上称为替代损失的“一致性”问题。给出了基于替代损失进行经验风险最小化的一致性充要条件，证明了几种常见凸替代损失函数的一致性。

支持向量机的求解通常是借助于凸优化技术。如何提高效率，使SVM能适用于大规模数据一直是研究重点。对线性核SVM已有很多成果，例如基于割平面法的SVM具有线性复杂度，基于随机梯度下降的Pegasos速度甚至更快，而坐标下降法则在稀疏数据上有很高的效率。非线性核SVM的时间复杂度在理论上不可能低于O（m2），因此研究重点是设计快速近似算法，如基于采样的CVM、基于低秩逼近的Nystr?m方法、基于随机傅里叶特征的方法等。最近有研究显示，当核矩阵特征值有很大差别时，Nystr?m方法往往优于随机傅里叶特征方法。

具体原理：

1.在n维空间中找到一个分类超平面，将空间上的点分类。如下图是线性分类的例子。

直观上看，应该去找位于两类训练样本“正中间”的划分超平面，因为该划分超平面对训练样本局部扰动的“容忍”性最好。例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比图中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而“正中间”的超平面影响最小。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。

2.一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。SVM就是要最大化这个间隔值。而在虚线上的点便叫做支持向量Supprot Verctor。

3.实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去(如下图)；

线性不可分映射到高维空间，可能会导致维度大小高到可怕的(19维乃至无穷维的例子)，导致计算复杂。核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。

4.使用松弛变量处理数据噪音

松弛变量的引入常常是为了便于在更大的可行域内求解。若为0，则收敛到原有状态，若大于零，则约束松弛。

对线性规划问题的研究是基于标准型进行的。因此对于给定的非标准型线性规划问题的数学模型，则需要将其化为标准型。一般地，对于不同形式的线性规划模型，可以采用一些方法将其化为标准型。其中，

当约束条件为\(或者减去)一个非负的新变量，即可化为等式。这个新增的非负变量称为松弛变量(或剩余变量)，也可统称为松弛变量。在目标函数中一般认为新增的松弛变量的系数为零。

SVM的优点：

1. SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）