支持向量机算法的详细推导PPT课件

.,1,人工神经网络及应用,主讲何东健,第八章支持向量机,.,2,BP网络及RBF网络解决了模式分类与非线性映射问题。Vapnik提出的支持向世机(SupportVectorMachine，SVM)，同样可以解决模式分类与非线性映射问题。从线性可分模式分类角度看，SVM的主要思想是：建立一个最优决策超平面，使得该平面两侧距平面最近的两类样本之间的距离最大化，从而对分类问题提供良好的泛化能力。根据cover定理：将复杂的模式分类问题非线性地投射到高维特征空间可能是线性可分的，因此只要特征空间的维数足够高，则原始模式空间能变换为一个新的高维特征空间，使得在特征空间中模式以较高的概率为线性可分的。此时，应用支持向量机算法在特征空间建立分类超平面，即可解决非线性可分的模式识别问题。支持向量机基于统计学习理论的原理性方法，因此需要较深的数学基础。下面的阐述避免过多抽象的数学概念，推导过程尽量详细。,.,3,8.1支持向量机的基本思想线性可分数据的二值分类机理：系统随机产生一个超平面并移动它，直到训练集中属于不同类别的样本点正好位于该超平面的两侧。显然，这种机理能够解决线性分类问题，但不能够保证产生的超平面是最优的。支持向量机建立的分类超平面能够在保证分类精度的同时，使超平面两侧的空白区域最大化，从而实现对线性可分问题的最优分类。什么叫线性可分？就是可以用一条或几条直线把属于不同类别的样本点分开。实际上，求解分类问题，就是要求出这条或这几条直线！问题是：怎么求？,.,4,进一步理解支持向量机：支持向量机（SupportVectorMachine，SVM）中的“机（machine，机器）”：实际上是一个算法。在机器学习领域，常把一些算法看作是一个机器（又叫学习机器，或预测函数，或学习函数）。“支持向量”：则是指训练集中的某些训练点,这些点最靠近分类决策面，是最难分类的数据点。SVM:它是一种有监督（有导师）学习方法，即已知训练点的类别，求训练点和类别之间的对应关系，以便将训练集按照类别分开，或者是预测新的训练点所对应的类别。,.,5,SVM主要针对小样本数据进行学习、分类和预测（有时也叫回归）的一种方法，能解决神经网络不能解决的过学习问题。类似的根据样本进行学习的方法还有基于案例的推理（Case-BasedReasoning），决策树归纳算法等。过学习问题：训练误差过小导致推广能力下降，即真实风险的增加。推广能力：generalizationability，也可以说是泛化能力，就是对未知样本进行预测时的精确度。下面讨论线性可分情况下支持向量机的分类原理。,.,6,8.1.1最优超平面的概念考虑P个线性可分样本(X1，d1)，(X2，d2)，(Xp，dp)，(XP，dP)，对于任一输入样本Xp，期望输出为dp=1（代表两类类别标识）。用于分类的超平面方程为WTX+b=0(8.1)式中，X为输入向量，W为权值向量，b为偏置（相当于前述负阈值），则有WTXP+b0dp=+1WTXP+b0以上为不等式约束的二次函数极值问题(QuadraticProgramming，QP)。由KuhnTucker定理知，式(8.14)的最优解必须满足以下最优化条件(KKT条件),（8.14）,.,17,上式等号成立的两种情况：一是p为零；另一种是(WTXP+b)dp=1。第二种情况仅对应于样本为支持向量。设Q()的最优解为01,02,.,0p，可通过式(8.12)计算最优权值向量，其中多数样本的Lagrange系数为零，因此即最优超平面的权向量是训练样本向量的线性组合，且只有支持向量影响最终的划分结果，如果去掉其他训练样本重新训练，得到分类超平面相同。但如果一个支持向量未能包含在训练集内时，最优超平面会被改变。,(8.16),.,18,利用计算出的最优权值向量和一个正的支持向量，可通过式(8.5)进一步计算出最优偏置b0=1W0TXs(8.17)求解线性可分问题得到的最优分类判别函数为在上式中的P个输入向量中，只有若干个支持向量的Lagrange系数不为零，因此计算复杂度取决于支持向量的个数。对于线性可分数据，该判别函数对训练样本的分类误差为零，而对非训练样本具有最佳泛化性能。,(8.18),.,19,8.1.3非线性可分数据最优超平面的构建若将上述思想用于非线性可分模式的分类时，会有一些样本不能满足dp(WTXP+b)1的约束，而出现分类误差。因此需要适当放宽该式的约束，将其变为式中引入了松弛变量p0，用于度量一个数据点对线性可分理想条件的偏离程度。当0p1时，数据点落入分离区域的内部，且在分类超平面的正确一侧；当p1时，数据点进入分类超平面的错误一侧；当p=0时，相应的数据点即为精确满足式(8.6)的支持向量Xs。,(8.19),dp(WTXP+b)1,.,20,建立非线性可分数据的最优超平面可以采用与线性可分情况类似的方法，即对于给定的训练样本(X1，d1)，(X2，d2)，(Xp，dp)，(XP，dP),寻找权值W和阈值B的最优值，使其在式(8.19)的约束下，最小化关于权值W和松弛变量p的代价函数C是选定的正参数。与前述方法相似，采用Laglange系数方法解决约束最优问题。需要注意的是，在引入Lagrange函数时，使式(8.10)中的1被1-p代替，从而使Lagrange函数变为,.,21,对式(8.21)采用与前类似推导，得到非线性可分数据的对偶问题的表示为：给定训练样本，求解使以下目标函数为最大值的Lagrange系数1,2,.,p，并满足以下约束条件,(8.21),.,22,可以看出在上述目标函数中，松弛变量p和它们的Lagrange系数都未出现，因此线性可分的目标函数与非线性可分的目标函数表达式完全相同。不同的只是线性可分情况下的约束条件p0,在非线性可分情况下被替换为约束更强的0pC，因此线性可分情况下的约束条件p0可以看作非线性可分情况下的一种特例。此外，W和b的最优解必须满足的KuhnTucker最优化条件改变为最终推导得到的W和b的最优解计算式以及最优分类判别函数与式(8.16)、(8.17)和(8.18)完全相同。,.,23,8.2非线性支持向量机对非线性可分模式分类，SVM的方法是，将输入向量映射到一个高维特征向量空间，如果选用的映射函数适当且特征空间的维数足够高，则大多数非线性可分模式在特征空间中可以转化为线性可分模式，因此可以在该特征空间构造最优超平面进行模式分类，这个构造与内积核相关。8.2.1基于内积核的最优超平面设X为N维输入空间的向量，令(X)=1(X)，2(X)，M(X)T表示从输入空间到M维特征空间的非线性变换，称为输入向量X在特征空间诱导出的“像”。照前思路，可在该特征空间构建一个分类超平面,.,24,式中的wj为将特征空间连接到输出空间的权值，b为偏置或负阈值。令0(x)=1，w0=b，上式可简化为或将适合线性可分模式输入空间的式(8.12)用于特征空间中线性可分的“像”，只需用(X)替换X，得到,(8.26),.,25,将上式代入式(8.26)可得特征空间的分类超平面为式中T(XP)(X)表示第p个输入模式XP在特征空间的像(XP)与输入向量X在特征空间的像(X)的内积，因此在特征空间构造最优超平面时，仅使用特征空间中的内积。若能找到一个函数K()，使得则在特征空间建立超平面时无需考虑变换的形式。K(X,XP)称为内积核函数。,(8.28),p,(8.29),.,26,泛函分析中的Mercer定理给出作为核函数的条件：K(X,X)表示一个连续的对称核，其中X定义在闭区间aXb，X类似。核函数K(X，X)可以展开为级数式中所有i0。保证式(8.30)一致收敛的充要条件是对于所有满足可以看出式(8.29)对于内积核函数K(X,XP)的展开是Mercer定理的一种特殊情况。Mercer定理指出如何确定一个候选核是不是某个空间的内积核，但没有指出如何构造函数i(X)。,(8.30),.,27,对核函数K(X,XP)的要求是满足Mercer定理，因此其选择有一定的自由度。下面给出4种常用的核函数。(1)线性核函数:K(X,Xp)=X*Xp(2)多项式核函数采用该函数的支持向量机是一个q阶多项式分类器，其中q为由用户决定的参数。(3)Gauss核函数采用该函数的支持向量机是一种径向积函数分类器。(4)Sigmoid核函数,.,28,K(X,XP)=tanh(k(XXP)+ctanh(x)=(ex-e-x)/(ex+e-x)(双曲正切函数)采用该函数的支持向量机实现的是一个单隐层感知器神经网络。使用内积核在特征空间建立的最优超平面定义为8.2.2非线性支持向量机神经网络支持向量机的思想是，对于非线性可分数据，在进行非线性变换后的高维特征空间实现线性分类，此时最优分类判别函数为,.,29,令支持向量的数量为Ns，去除系数为零的项，上式可改写为从支持向量机分类判别函数的形式上看，它类似于一个3层前馈神经网络。其中隐层节点对应于输入样本与一个支持向量的内积核函数，而输出节点对应于隐层输出的线性组合。图8.2给出支持向量机神经网络的示意图。设计一个支持向量机时，只需选择满足Mercer条件的核函数而不必了解将输入样本变换到高维特征空间的(*)的形式，但下面给出的简单的核函数实际上能够构建非线性映射(*)。,.,30,支持向量机神经网络,.,31,设输入数据为二维平面的向量X=x1，x2T，共有3个支持向量，因此应将二维输入向量非线性映射为三维空间的向量(x)=1(x),2(x),3(x)T。选择K(Xi，Xj)=(xi)TXj，使映射()从R2R3满足对于给定的核函数，映射()和特征空间的维数都不是唯一的，例如，对于本例的情况可选(X)x12,2(x),3(x)T，或(X)1(x),2(x),3(x)T。,.,32,8.3支持向量机的学习算法在能够选择变换(取决于设计者在这方面的知识)的情况下，用支持向量机进行求解的学习算法如下：(1)通过非线性变换将输入向量映射到高维特征空间;(2)在约束条件下求解使目标函数最大化的op。(3)计算最优权值,.,33,(4)对于待分类模式X，计算分类判别函数根据f(x)为1或一1，决定X的类别归属。若能选择一个内积核函数K(XP,X)，可避免进行变换，此时用支持向量机进行求解的学习算法如下：(1)准备一组训练样本(X1，d1)，(X2，d2)，(Xp，dp)，(XP，dP)(2)在约束条件下求解使目标函数,.,34,最大化的op。，其中K(XP,Xj)，p,j=1,2,P可以看作是PP对称矩阵K的第pj项元素；(3)计算最优权值Y为隐层输出向量；(4)对于待分类模式X，计算分类判别函数根据f(x)为1或-l，决定X的类别归属。上面讨论的支持向量机只能解决二分类问题，目前没有一个统一的方法将其推广到多分类的情况。,.,35,支持向量机被用于径向基函数网络和多层感知器的设计中。在径向基函数类型的支持向量机中，径向基函数的数量和它们的中心分别由支持向量数和支持向量的值决定，而传统RBF网络则依赖于经验知识。在单隐层感知器类型的支持向量机中，隐节点的个数和它们的权值向量分别由支持向量的个数和支持向量的值决定。与RBF和多层感知器相比，SVM的算法（1）不依赖于设计者的经验知识;（2）能求全局最优值;（3）有良好的泛化能力而不会出现过学习。SVM算法复杂导致训练速度较慢，其中的主要原因是在算法寻优过程中涉及大量矩阵运算。目前提出的一些改进训练算法是基于循环迭代的思想，3类改进算法。,.,36,(1)Vapnik等提出的块算法(2)Qsuna等提出的分解算法(3)Platt的SMO算法（应用最广！）8.4支持向量机设计应用实例8.4.1XOR问题用SVM处理XOR问题。4个输入样本和期望输出如图8.3(a)所示。方法一：选择映射函数(x)将输入样本映射到高维的空间，使其在该空间是线性可分的。如(x)可将二维训练样本映射到一个六维特征空间。这个六,.,37,x1x2d-1-1-1-1111-1111-1,.,38,维空间在平面上的投影如图8.3(b)所示。可以看出分离边缘为=，通过支持向量的超平面在正负两侧平行于最优超平面，其方程为，对应于原始空间的双曲线x1x2=1。寻求使：最大化的Lagrange系数，约束条件为,.,39,从该问题的对称性，可取求导并令导数为零，得到下列联立方程组解得Lagrange系数的最优值为op=1/8，p=1，2，3，4，可见4个样本都是支持向量，Q()的最优值为14。根据式(8.39)可写出,.,40,在六维特征空间中找到的最优超平面为,.,41,图8.3中将最优超平面x1x2=0投影到二维空间后成为与轴平行的直线