支持向量机(SVM )原理及应用、SVM的产生与发展自1995年Vapnik (瓦普尼克)在统计学习理论的基础上提出SVM作为模式识别的新方法之后，SVMH直倍受关注同年，Vapnik和Cortes提出软间隔(soft margin)SVM,通过引进松弛变量\度量数据Xi的误分类(分类出现错误时\大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM勺寻优过程即是大的分隔间距和小的误差补偿之间的平 衡过程；1996年，Vapnik等人又提出支持向量回归 (Support Vector Regression , SVR)的方 法用于解决拟合问题SVF同SV啲出发点都是寻找最优超平面(注：一维空间为点；二维空间 为线；三维空间为面；高维空间为超平面 )，但SVR勺目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面， 两者最终都转换为最优化问题的求解；1998年, Weston 等人根据SVMM理提出了用于解决多类分类的SVM方法(Multi-Class Support Vector Mach in es，Multi-SVM)，通过将多类分类转化成二类分类，将 SVM^用于多分类问题的判断： 此外，在SVMJ法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。
例如， Suykens提出的最小二乘支持向量机 (Least Square Support Vector Machine ， LS— SVM算法,Joachims等人提出的SVM-1ight，张学工提出的中心支持向量机 (Central Support Vector Machine, CSVM)Scholkoph和Smola基于二次规划提出的v-SVM等此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM勺典型应用进行总结，并设计开发出较为完善的 SVW具包，也就是LIBSVM(A Library for Support Vector Machines) LIBSVM!—个通用的 SVM^件包，可以解决分类、回归以及分布估计等问题二、支持向量机原理SVM?法是20世纪90年代初Vapnik等人根据统计学习理论提出的一种新的机器学习方法, 它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使 学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试 集的测试误差仍然较小支持向量机的基本思想：首先，性可分情况下，在原空间寻找两类样本的最优分类 超平面。
性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输 入空间的样本映射到高维属性空间使其变为线性情况，从而使得在高维属性空间采用线性算 法对样本的非线性进行分析成为可能，并在该特征空间中寻找最优分类超平面其次，它通 过使用结构风险最小化原理在属性空间构建最优分类超平面，使得分类器得到全局最优，并在整个样本空间的期望风险以某个概率满足一定上界其突出的优点表现在：（1）基于统计学习理论中 结构风险最小化原则（注：所谓的结构风险最小化就是在保证分类精度 （经验风险）的同时，降低学习机器的 VC维，可以使学习机器在整个样本集上的期望风险得到控制 ）和V（维理论（注：VC维（Vapnik-Chervonenkis Dimension ）的概念是为了研究学习过程一致收敛的速度和推广性，由统计学理论定义的有关函数集学习性能的一个重要指标 ），具有良好的泛化能力，即由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的 误差2）支持向量机的求解问题对应的是一个凸优化问题， 因此局部最优解一定是全局最优解⑶ 核函数的成功应用，将非线性问题转化为线性问题求解 ⑷ 分类间隔的最大化，使得支持向量机算法具有较好的鲁棒性。
由于SVI自身的突出优势，因此被越来越多的研究人员作为强有力的学习工具，以解决模式识别、回归估计等领域的难题1最优分类面和广义最优分类面SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用图 1来说明对于一维空间中的点，二维空间中的直线，三维空间中的平面，以及高维空间中的超平面，图中实心 点和空心点代表两类样本，H为它们之间的分类超平面，Hi，H2分别为过各类中离分类面最近 的样本且平行于分类面的超平面，它们之间的距离△叫做分类间隔 （margin）图i最优分类面示意图所谓最优分类面要求分类面不但能将两类正确分开，而且使分类间隔最大 将两类正确分开是为了保证训练错误率为0,也就是经验风险最小（为0）使分类空隙最大实际上就是使 推广性的界中的置信范围最小？，从而使真实风险最小推广到高维空间，最优分类线就成 为最优分类面设线性可分样本集为（Xj, yj_）,i =1,...,n,x€ Rd,y€{+I,_l}是类别符号d维空间中线性判别函数的一般形式为是类别符号d维空间中线性判别函数的一般形式为 g（x^w x b （主: w代表Hilbert空间中权向量；b代表阈值分类线方程为w x 0 ？。
将判别函数进行 归一化，使两类所有样本都满足|g（x）| = 1，也就是使离分类面最近的样本的|g（x）|=1，此时 分类间隔等于2/||w|| ？，因此使间隔最大等价于使||w|| （或||w||2）最小要求分类线对所有 样本正确分类，就是要求它满足yi[（w x） b]-1 —0,i =1,2,...,n （1-1）满足上述条件（1-1），并且使||w||2最小的分类面就叫做最优分类面， 过两类样本中离分类面最近的点且平行于最优分类面的超平面 H1，H上的训练样本点就称作支持向量（supportvector），因为它们“支持” 了最优分类面利用Lagrange （拉格朗日）优化方法可以把上述最优分类面问题转化为如下这种较简单 的对偶问题，即：在约束条件，n' y「i =0 （ 1-2a）i 4_：珀-0,i =1,2,..., n （1-2b）F面对:i （主：对偶变量即拉格朗日乘子）求解下列函数的最大值：nQ (〉)八-ii -11 n--v : i ： jWyj(XiXj)2 i,j 4？（1-3）若〉为最优解，则wn八,y- ii =4（1-4）即最优分类面的权系数向量是训练样本向量的线性组合。
注释（1-3）式由来：利用Lagrange函数计算如下，2 lL（w,b,a）=2IW|| -》口心 © w）+b）-1）i仝C Cw iYiXii 二lL(w,b,J〔)二0 —L(w,b,圧)=0 ;b ；:wa aiYi =0i吕lw（：）「 : i —2、 ：「j%yj（为 Xj）i妊 i,j仝l:i —0, i =1,...,l, and 二 y =0imlf (x)二 sg nC y： i (x xj b)i 二实例计算：图略，可参见PPTx1 :=(0, 0),y1 ==+1x2 :=(1,0),y2 ==+1x3：=(2, 0),y3 ==-1x4 :=(0, 2),y4 ==-11 2 2 2Q（、f）=（冷亠’：：2 亠’：：3 亠"：：4） （用2 4： 2芒3 亠 4、；3 亠 4、；-4 ）可调用Matlab中的二次规划程序，求得：1, ： 2, ： 3, :• 4的值，进而求得w和b的值% =00(2 = 1 j 3 =3/4：-4 =1/421二」g(x) =3 _2Xr _2x2 = 0这是一个不等式约束下的二次函数极值问题，存在唯一解根据 kihn-Tucker条件，解中将只有一部分（通常是很少一部分）：、不为零，这些不为0解所对应的样本就是支持向量。
求 解上述问题后得到的最优分类函数是：nf （x）二 sgn{（ w x） b } = sgn：■ i yi （xi x） b } （1-5）根据前面的分析，非支持向量对应的 :i均为0，因此上式中的求和实际上只对支持向量进行b*是分类阈值，可以由任意一个支持向量通过式 （1-1）求得（只有支持向量才满足其中的等号条件），或通过两类中任意一对支持向量取中值求得从前面的分析可以看出，最优分类面是性可分的前提下讨论的，性不可分的情况下，就是某些训练样本不能满足式 （1-1）的条件，因此可以在条件中增加一个松弛项参数；i -0，变成：yj（w %） b]-1」—0,i =1,2,...,n （1-6）对于足够小的s>0,只要使nF"）八汀 （1-7）i=1最小就可以使错分样本数最小对应线性可分情况下的使分类间隔最大，性不可分情况下可引入约束:l|w『"k (1-8)在约束条件(1-6)幕1(1-8)下对式(1-7)求极小，就得到了线性不可分情况下的最优分类 面，称作广义最优分类面为方便计算，取s=1为使计算进一步简化，广义最优分类面问题可以迸一步演化成在条件 (1-6)的约束条件下求下列函数的极小值：1 n(w,) (w,w) C(' ；i ) (1-9)2 y其中C为某个指定的常数，它实际上起控制对锩分样本惩罚的程度的作用， 实现在错分样本的比例与算法复杂度之间的折衷。
求解这一优化问题的方法与求解最优分类面时的方法相同，都是转化为一个二次函数极值问题，其结果与可分情况下得到的(1-2)到(1-5)几乎完全相同，但是条件(1-2b)变为：0 乞：\ 乞 C, i =1,...,n (1-10)2. SVM的非线性映射对于非线性问题，可以通过非线性交换转化为某个高维空间中的线性问题，在变换空间求最优分类超平面这种变换可能比较复杂，因此这种思路在一般情况下不易实现但是我们可以看到，在上面对偶问题中，不论是寻优目标函数( 1-3)还是分类函数(1-5)都只涉及训练样本之间的内积运算(x Xi) 0设有非线性映射G：Rd > H将输入空间的样本映射到高维 (可能是无穷维)的特征空间H中，当在特征空间H中构造最优超平面时，训练算法仅使用空间 中的点积，即(Xi) (Xj)，而没有单独的(Xi)出现因此，如果能够找到一个函数 K使得K(Xi Xj)二(Xi) (Xj) (1-11)这样在高维空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实现的，我们甚至没有必要知道变换中的形式 根据泛函的有关理论，只要一种核函数K(xi內)满足Mercer条件，它就对应某一变换空间中的内积。
因此，在最优超平面中采用适当的内积 函数K(Xi Xj)就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加此时目 标函数(1-3)变为：1QC )八-'i 「jyiyj K(Xj Xj)y 2 i,j _ii而相应的分类函数也变为nf(x) =sgn{\ ： *yiK(Xi Xj) b*}i丄(1-12)(1-13)算法的其他条件不变，这就是SVM概括地说SVMft是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空 间，在这个特征空间中构造最优分类超平面在形式上 SV盼类函数类似于一个神经网络,输出是中间节点的线性组合，每个中间节点对应于一个支持向量，如图 2所示图2 SVM示意图n其中，输出(决策规则):y二sgn{/ yi K(x xi) b}，权值w-t - iyi， K(x xi)为基。