支持向量机概述

支持向量机(SupportVectorMachine，SVM)概述支持向量机(SupportVectorMachine，SVM)是基于统计学习理论发展起来的新一代机器学习算法，由Vapnik于1992年介绍进入机器学习领域，之后受到广泛关注。支持向量机理论处理的是两类分类问题，对于多类分类问题，通过多个二分类模型组合构成。SVM的基本原理是将样本映射到高维空间，然后在高维空间中构建线性分类器，寻找使分类间隔最大的最优超平面，这个特点在保证分类器在具有较好的泛化能力的同时解决了维数灾难问题。SVM的目标是在有限样本信息下寻求学习精度和学习能力的最优解，该问题最终转化成为一个二次型寻优问题，从理论上来看，将得到全局最优解，解决了神经网络中无法避免的局部极值问题。由于SVM具有以上多个优点，使得该算法在众多领域获得较好应用，包括图像分类，生物信息学，病虫害识别等。下面将具体介绍SVM的原理和求解过程。（1）线性可分的情况给定一些样本数据，分别属于两个不同的类，标记为：{𝑥𝑖,𝑦𝑖},𝑥𝑖∈𝑅𝑑𝑦𝑖∈{1,−1},𝑖=1,2,…,𝑛。由于这些样本数据是线性可分的，因此，存在一个超平面H：𝑤𝑇∙𝑥+𝑏=0，可以把这两类数据正确分开。同时存在两个平行于H的超平面H1：𝑤𝑇∙𝑥+𝑏=1和H2：𝑤𝑇∙𝑥+𝑏=−1，使得距离超平面H最近的样本分别位于H1和H2之上，这些样本称为支持向量。而剩余其他样本都将位于H1和H2之外，即满足式（1）或式（2）的约束条件。𝑤𝑇∙𝑥𝑖+𝑏≥1𝑦𝑖=1(1)𝑤𝑇∙𝑥𝑖+𝑏≤−1𝑦𝑖=−1(2)在两类分类问题中，由于表示分类标记的𝑦𝑖只有1和-1两个值，因此可将式（1）和式（2）合并得到式（3）𝑦𝑖(𝑤𝑇∙𝑥𝑖+𝑏)−1≥0(3)由两个平行平面之间的距离公式可得超平面H1和H2之间的间隔为𝑓(𝑤)=2‖𝑤‖(4)SVM的目标就是寻找在满足式（3）约束的同时能够把样本准确分开，并且使H1和H2的距离最大的超平面H。此时，寻找最优分类超平面的问题就转化为在式（3）的约束下，求𝑓(𝑤)的最大值，也就是求‖𝑤‖2的最小值，为后续计算方便，采用等价函数12‖𝑤‖2替换‖𝑤‖2。对于不等式约束的条件极值问题，可以用拉格朗日方法求解，其方程如式（5）所示：𝐿(𝑤,𝑏,𝛼𝑖)=12‖𝑤‖2−∑𝛼𝑖(𝑦𝑖(𝑤𝑇∙𝑥𝑖+𝑏)−1)𝑛𝑖=1(5)其中𝛼𝑖≥0，为拉格朗日系数。那么我们要处理的优化问题就转换为min𝑤,𝑏max𝛼𝑖≥0𝐿(𝑤,𝑏,𝛼𝑖)(6)(6)式是一个凸规划问题，直接求解该式比较困难，为此，将该拉格朗日函数做一个等价变换，min𝑤,𝑏max𝛼𝑖≥0𝐿(𝑤,𝑏,𝛼𝑖)=max𝛼𝑖≥0min𝑤,𝑏𝐿(𝑤,𝑏,𝛼𝑖)(7)式（7）即为对偶变换，原凸规划问题就转换为对偶问题：max𝛼𝑖≥0min𝑤,𝑏𝐿(𝑤,𝑏,𝛼𝑖)(8)通过(8)式计算w和b的偏导数，由(5)式可得𝜕𝐿(𝑤,𝑏,𝛼𝑖)𝜕𝑤=𝑤−∑𝛼𝑖𝑦𝑖𝑥𝑖𝑛𝑖=1(9)𝜕𝐿(𝑤,𝑏,𝛼𝑖)𝜕𝑏=−∑𝛼𝑖𝑦𝑖𝑛𝑖=1(10)令式(9)、(10)分别为0可得𝑤=∑𝛼𝑖𝑦𝑖𝑥𝑖𝑛𝑖=1(11)∑𝛼𝑖𝑦𝑖𝑛𝑖=1=0(12)将(11)式带入(8)式有：max𝛼𝑖≥0min𝑤,𝑏𝐿(𝑤,𝑏,𝛼𝑖)=max𝛼𝑖≥0{∑𝛼𝑖𝑛𝑖=1−12∑∑𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑛𝑗=1𝑥𝑖𝑇𝑥𝑗𝑛𝑖=1}(13)对偶问题最终转换为：{max𝛼𝑖≥0{∑𝛼𝑖𝑛𝑖=1−12∑∑𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑖𝑇𝑥𝑗𝑛𝑗=1𝑛𝑖=1}𝑠𝑢𝑏𝑗𝑒𝑐𝑡𝑡𝑜∑𝛼𝑖𝑦𝑖𝑛𝑖=1=0𝛼𝑖≥0(14)(14)式可以直接通过数值方法计算求解。需要指出的是，在(6)式的凸规划问题中包含了一个隐含条件，即𝛼𝑖(𝑦𝑖(𝑤𝑇∙𝑥𝑖+𝑏)−1)=0(15)(15)式表示的意义是：如果一个样本是支持向量，则其对应的拉格朗日系数大于0，否则，其对应的拉格朗日系数等于0。由此可知，只有支持向量对应的拉格朗日系数不为0。求出拉格朗日系数后可通过式(11)求出w，而阈值b也可通过(15)式求出。最终得到最优分类超平面H和决策函数((16)式)。𝑓(𝑥)=∑𝛼𝑖𝑦𝑖𝑥𝑖𝑇𝑥𝑛𝑖=1+𝑏=∑𝛼𝑖𝑦𝑖〈𝑥𝑖,𝑥〉𝑛𝑖=1+𝑏(16)(16)式中〈𝑥𝑖,𝑥〉表示向量内积。（2）线性不可分的情况对于线性不可分问题，SVM的处理方法是选择一个核函数𝐾(𝑥𝑖,𝑥)将数据映射到高维空间，在高维空间中构建线性分类器，来解决在原始空间中线性不可分的问题。引入核函数后决策函数的形式变为：𝑓(𝑥)=∑𝛼𝑖𝑦𝑖𝐾(𝑥𝑖,𝑥)𝑛𝑖=1+𝑏(17)目前常用的核函数如表1所示。核函数的选择决定了特征空间的结构。核函数的选定非常关键，它的选择好坏直接影响到算法的实现与效果。从大量已有的研究结果来看，径向基核函数的分类效果较好。表1几种常用核函数核函数名称核函数表达式线性核函数𝐾(𝑥,𝑦)=〈𝑥,𝑦〉多项式核函数𝐾(𝑥,𝑦)=[〈𝑥,𝑦〉+1]𝑑径向基核函数𝐾(𝑥,𝑦)=𝑒𝑥𝑝[−‖𝑥−𝑦‖2/2𝜎2]Sigmoid核函数𝐾(𝑥,𝑦)=𝑡𝑎𝑛ℎ(𝑎〈𝑥,𝑦〉+𝛿)虽然引入核函数后使得原始数据再高维空间线性可分的概率大大增加，但是并不能使所有在原始空间线性不可分的问题得到解决。为此SVM引入非负变量𝜉𝑖，𝐶。其中𝜉𝑖是松弛变量，表示对应样本点𝑥𝑖偏离最优超平面的程度，𝐶称为惩罚系数，是已知常数，用于控制寻找最优超平面H和使样本点偏离最优超平面程度的权重。此时，约束条件式(3)变成𝑦𝑖(𝑤𝑇∙𝑥𝑖+𝑏)−(1−𝜉𝑖)≥0(18)原线性可分问题的目标函数𝑚𝑖𝑛12‖𝑤‖2变为𝑚𝑖𝑛12‖𝑤‖2+𝐶∑𝜉𝑖𝑛𝑖=1(19)同线性可分情况，在此构建拉格朗日函数：𝐿(𝑤,𝑏,𝜉𝑖,𝛼𝑖,𝑟𝑖)=12‖𝑤‖2+𝐶∑𝜉𝑖𝑛𝑖=1−∑𝛼𝑖(𝑦𝑖(𝑤𝑇∙𝑥𝑖+𝑏)−1+𝜉𝑖)𝑛𝑖=1−∑𝑟𝑖𝜉𝑖𝑛𝑖=1(20)分析方法同线性可分情况，对(20)式计算w、b和𝜉的偏导数并令偏导数为0，可得𝑤=∑𝛼𝑖𝑦𝑖𝑥𝑖𝑛𝑖=1(21)∑𝛼𝑖𝑦𝑖𝑛𝑖=1=0(22)𝐶−𝛼𝑖−𝑟𝑖=0(23)由于𝑟𝑖≥0，且𝐶−𝛼𝑖−𝑟𝑖=0，因此有𝐶≥𝛼𝑖，非线性问题的对偶问题最终可以写为将式(21)带回式(20)可得目标函数：max𝛼∑𝛼𝑖𝑛𝑖=1−12∑∑𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑛𝑗=1𝑥𝑖𝑇𝑥𝑗𝑛𝑖=1(24)线性不可分情况下的对偶问题最终转换为：{max𝛼{∑𝛼𝑖𝑛𝑖=1−12∑∑𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑖𝑇𝑥𝑗𝑛𝑗=1𝑛𝑖=1}𝑠𝑢𝑏𝑗𝑒𝑐𝑡𝑡𝑜∑𝛼𝑖𝑦𝑖𝑛𝑖=1=00≤𝛼𝑖≤𝐶(25)式(25)与线性可分情况下的目标函数求解方法相同。最终的决策函数与(17)式相同。（3）多类分类问题SVM是典型的两类分类器，对于多类分类问题，SVM有两种较常用的方法，以N类问题为例，一种是依次将其中一类定位正样本，其余类看作是负样本，这样我们可以得到N个两类分类器。对于某个输入样本，其分类结果为各两类分类器输出值最大的类别。另一种方法是从N类中选取两类构建分类器，从而需要构建N(N-1)/2个两类分类器，最后采取投票法确定最终分类结果。