搜索
人工神经网络及应用主讲何东健第八章支持向量机BP网络及RBF网络解决了模式分类与非线性映射问题。Vapnik提出的支持向世机(SupportVectorMachine，SVM)，同样可以解决模式分类与非线性映射问题。从线性可分模式分类角度看，SVM的主要思想是：建立一个最优决策超平面，使得该平面两侧距平面最近的两类样本之间的距离最大化，从而对分类问题提供良好的泛化能力。根据cover定理：将复杂的模式分类问题非线性地投射到高维特征空间可能是线性可分的，因此只要特征空间的维数足够高，则原始模式空间能变换为一个新的高维特征空间，使得在特征空间中模式以较高的概率为线性可分的。此时，应用支持向量机算法在特征空间建立分类超平面，即可解决非线性可分的模式识别问题。支持向量机基于统计学习理论的原理性方法，因此需要较深的数学基础。下面的阐述避免过多抽象的数学概念，推导过程尽量详细。8.1支持向量机的基本思想线性可分数据的二值分类机理：系统随机产生一个超平面并移动它，直到训练集中属于不同类别的样本点正好位于该超平面的两侧。显然，这种机理能够解决线性分类问题，但不能够保证产生的超平面是最优的。支持向量机建立的分类超平面能够在保证分类精度的同时，使超平面两侧的空白区域最大化，从而实现对线性可分问题的最优分类。什么叫线性可分？就是可以用一条或几条直线把属于不同类别的样本点分开。实际上，求解分类问题，就是要求出这条或这几条直线！问题是：怎么求？进一步理解支持向量机：支持向量机（SupportVectorMachine，SVM）中的“机（machine，机器）”：实际上是一个算法。在机器学习领域，常把一些算法看作是一个机器（又叫学习机器，或预测函数，或学习函数）。“支持向量”：则是指训练集中的某些训练点,这些点最靠近分类决策面，是最难分类的数据点。SVM:它是一种有监督（有导师）学习方法，即已知训练点的类别，求训练点和类别之间的对应关系，以便将训练集按照类别分开，或者是预测新的训练点所对应的类别。SVM主要针对小样本数据进行学习、分类和预测（有时也叫回归）的一种方法，能解决神经网络不能解决的过学习问题。类似的根据样本进行学习的方法还有基于案例的推理（Case-BasedReasoning），决策树归纳算法等。过学习问题：训练误差过小导致推广能力下降，即真实风险的增加。推广能力：generalizationability，也可以说是泛化能力，就是对未知样本进行预测时的精确度。下面讨论线性可分情况下支持向量机的分类原理。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+b0dp=-1超平面与最近的样本点之间的间隔称为分离边缘，用ρ表示。支持向量机的目标是找到一个分离边缘最大的超平面，即最优超平面。也就是要确定使ρ最大时的W和b。图8.1给出二维平面中最优超平面的示意图。可以看出，最优超平面能提供两类之间最大可能的分离，因此确定最优超平面的权值W0和偏置b0应是唯一的。在式(8.1)定义的一簇超平面中，最优超平面的方程应为:WTX0+b0=0（应该是W0X+b0=0吧？）直接求W0和b0基本上不太可能，除了训练集无别的信息可用，如何办？一种方法：使求得的预测函数y=f(x)=sgn(W·X+b)对原有样本的分类错误率最小。如何使分类错误率最小？下面慢慢分析。由解析几何知识可得样本空间任一点X到最优超平面的距离为(8.3)从而有判别函数g(X)=r||W0||=W0TX+b0g(X)给出从X到最优超平面的距离的一种代数度量。将判别函数进行归一化，使所有样本都满足则对于离最优超平面最近的特殊样本Xs满足：Ig(Xs)I=1，称为支持向量。由于支持向量最靠近分类决策面，是最难分类的数据点，因此这些向量在支持向量机的运行中起着主导作用。式(8.5)中的两行也可以组合起来用下式表示(8.5)dp(WTXP+b)≥1（8.6）其中，W0用W代替。由式(8.3)可导出从支持向量到最优超平面的代数距离为因此，两类之间的间隔可用分离边缘表示为上式表明，分离边缘最大化等价于使权值向量的范数||W||最小化。因此，满足式(8.6)的条件且使||W||最小的分类超平面就是最优超平面。r设x=(x1,x2,…,xn)Tx的范数:||x||=|x1|+|x2|+…+|xn|如何构造这个最优分类面呢？方法：平分最近点法和最大间隔法。两个方法殊途同归，它们求解得到同一个超平面。这两个方法与一个最优化问题求解方法等价。分类机是将最大间隔法求解最优分类面的最优化问题转化为其对偶问题，从而通过求解相对简单的对偶问题来求解原分类问题的算法。随后引入松弛变量和惩罚因子来解决非线性分类问题，并且允许一定的分类错误（软间隔），最终得到非线性软间隔的标准的C-支持向量机(C-SVC)。把一个复杂的最优化问题的求解简化为对原有样本数据的内积运算。只需选择适当的核函数及其参数、惩罚因子。8.1.2线性可分数据最优超平面的构建建立最优分类面问题可表示成如下的约束优化问题，即对给定的训练样本{(X1，d1)，(X2，d2)，…，(Xp，dp)，…(XP，dP)}，找到权值向量W和阈值B的最优值，使其在式(8.6)的约束下，有最小化代价函数该约束优化问题的代价函数是W的凸函数，且关于W的约束条件是线性的，因此可用Lagrange系数方法解决约束最优问题。引入Lagrange函数如下式中αp≥0，称为Lagrange系数。式(8.10)中的第一项为代价函数φ(w)，第二项非负，因此最小化φ(w)就转化为求Lagrange函数的最小值。观察Lagrange函数可以看出，欲使该函数值最小化，应使第一项φ(w)↓，使第二项↑。为使第一项最小化，将式(8.10)对W和b求偏导，并使结果为零利用式(8.10)和式(8.11)，可导出最优化条件1(8.11)(8.10)利用式(8.10)和式(8.11)可导出最优化条件2为使第二项最大化，将式(8.10)展开如下根据式(8.13)，上式中的第三项为零。根据式(8.12)，可将上式表示为(8.13)(8.12)根据式(8.12)可得关于α的目标函数为Q(α)＝L(W,b,α)，则有(8.12)最小化L(W,b,α)问题，转化为一个最大化函数Q(α)的对偶问题，即给定{(X1，d1)，(X2，d2)，…，(Xp，dp)，…(XP，dP)}，使（8.14）为最大值的Lagrange系数{α1,α2,......,αp}，并满足约束条件αp0以上为不等式约束的二次函数极值问题(QuadraticProgramming，QP)。由KuhnTucker定理知，式(8.14)的最优解必须满足以下最优化条件(KKT条件)（8.14）上式等号成立的两种情况：一是αp为零；另一种是(WTXP+b)dp=1。第二种情况仅对应于样本为支持向量。设Q(α)的最优解为{α01,α02,......,α0p}，可通过式(8.12)计算最优权值向量，其中多数样本的Lagrange系数为零，因此即最优超平面的权向量是训练样本向量的线性组合，且只有支持向量影响最终的划分结果，如果去掉其他训练样本重新训练，得到分类超平面相同。但如果一个支持向量未能包含在训练集内时，最优超平面会被改变。(8.16)利用计算出的最优权值向量和一个正的支持向量，可通过式(8.5)进一步计算出最优偏置b0=1－W0TXs(8.17)求解线性可分问题得到的最优分类判别函数为在上式中的P个输入向量中，只有若干个支持向量的Lagrange系数不为零，因此计算复杂度取决于支持向量的个数。对于线性可分数据，该判别函数对训练样本的分类误差为零，而对非训练样本具有最佳泛化性能。(8.18)8.1.3非线性可分数据最优超平面的构建若将上述思想用于非线性可分模式的分类时，会有一些样本不能满足dp(WTXP+b)≥1的约束，而出现分类误差。因此需要适当放宽该式的约束，将其变为式中引入了松弛变量ξp≥0，用于度量一个数据点对线性可分理想条件的偏离程度。当0≤ξp≤1时，数据点落入分离区域的内部，且在分类超平面的正确一侧；当ξp1时，数据点进入分类超平面的错误一侧；当ξp=0时，相应的数据点即为精确满足式(8.6)的支持向量Xs。(8.19)dp(WTXP+b)≥1建立非线性可分数据的最优超平面可以采用与线性可分情况类似的方法，即对于给定的训练样本{(X1，d1)，(X2，d2)，…，(Xp，dp)，…(XP，dP)},寻找权值W和阈值B的最优值，使其在式(8.19)的约束下，最小化关于权值W和松弛变量ξp的代价函数C是选定的正参数。与前述方法相似，采用Laglange系数方法解决约束最优问题。需要注意的是，在引入Lagrange函数时，使式(8.10)中的1被1-ξp代替，从而使Lagrange函数变为对式(8.21)采用与前类似推导，得到非线性可分数据的对偶问题的表示为：给定训练样本，求解使以下目标函数为最大值的Lagrange系数{α1,α2,......,αp}，并满足以下约束条件(8.21)可以看出在上述目标函数中，松弛变量ξp和它们的Lagrange系数都未出现，因此线性可分的目标函数与非线性可分的目标函数表达式完全相同。不同的只是线性可分情况下的约束条件αp≥0,在非线性可分情况下被替换为约束更强的0≤αp≤C，因此线性可分情况下的约束条件αp≥0可以看作非线性可分情况下的一种特例。此外，W和b的最优解必须满足的KuhnTucker最优化条件改变为最终推导得到的W和b的最优解计算式以及最优分类判别函数与式(8.16)、(8.17)和(8.18)完全相同。8.2非线性支持向量机对非线性可分模式分类，SVM的方法是，将输入向量映射到一个高维特征向量空间，如果选用的映射函数适当且特征空间的维数足够高，则大多数非线性可分模式在特征空间中可以转化为线性可分模式，因此可以在该特征空间构造最优超平面进行模式分类，这个构造与内积核相关。8.2.1基于内积核的最优超平面设X为N维输入空间的向量，令Φ(X)=[φ1(X)，φ2(X)，…，φM(X)]T表示从输入空间到M维特征空间的非线性变换，称为输入向量X在特征空间诱导出的“像”。照前思路，可在该特征空间构建一个分类超平面式中的wj为将特征空间连接到输出空间的权值，b为偏置或负阈值。令φ0(x)=1，w0=b，上式可简化为或将适合线性可分模式输入空间的式(8.12)用于特征空间中线性可分的“像”，只需用Φ(X)替换X，得到(8.26)将上式代入式(8.26)可得特征空间的分类超平面为式中ΦT(XP)Φ(X)表示第p个输入模式XP在特征空间的像Φ(XP)与输入向量X在特征空间的像Φ(X)的内积，因此在特征空间构造最优超平面时，仅使用特征空间中的内积。若能找到一个函数K()，使得则在特征空间建立超平面时无需考虑变换φ的形式。K(X,XP)称为内积核函数。(8.28)p(8.29)泛函分析中的Mercer定理给出作为核函数的条件：K(X,X’)表示一个连续的对称核，其中X定义在闭区间a≤X≤b，X’类似。核函数K(X，X’)可以展开为级数式中所有λi0。保证式(8.30)一致收敛的充要条件是对于所有满足可以看出式(8.29)对于内积核函数K(X,XP)的展开是Mercer定理的一种特殊情况。Mercer定理指出如何确定一个候选核是不是某个空间的内积核，但没有指出如何构造函数φi(X)。(8.30)对核函数K(X,XP)的要求是满足Mercer定理，因此其选择有一定的自由度。下面给出4种常用的核函数。(1)线性核函数:K(X,Xp)=X’*Xp(2)多项式核函数采用该函数的支持向量机是一个q阶多项式分类器，其中q为由用户决定