支持向量机算法的详细推导.ppt

《支持向量机算法的详细推导.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工神经网络及应用主讲何东健第八章支持向量机BP网络及RBF网络解决了模式分类与非线性映射问题。Vapnik提出的支持向世机(SupportVectorMachine，SVM)，同样可以解决模式分类与非线性映射问题。从线性可分模式分类角度看，SVM的主要思想是：建立一个最优决策超平面，使得该平面两侧距平面最近的两类样本之间的距离最大化，从而对分类问题提供良好的泛化能力。根据cover定理：将复杂的模式分类问题非线性地投射到高维特征空间可能是线性可分的，因此只要特征空间的维数足够高，则原始模式空间能变换为一个新的高维特征空间，使得在特征空间中模式以较高的概率为线性可分

2、的。此时，应用支持向量机算法在特征空间建立分类超平面，即可解决非线性可分的模式识别问题。支持向量机基于统计学习理论的原理性方法，因此需要较深的数学基础。下面的阐述避免过多抽象的数学概念，推导过程尽量详细。8.1支持向量机的基本思想线性可分数据的二值分类机理：系统随机产生一个超平面并移动它，直到训练集中属于不同类别的样本点正好位于该超平面的两侧。显然，这种机理能够解决线性分类问题，但不能够保证产生的超平面是最优的。支持向量机建立的分类超平面能够在保证分类精度的同时，使超平面两侧的空白区域最大化，从而实现对线性可分问题的最优分类。什么叫线性可分？就是可以用一条或几条直线

3、把属于不同类别的样本点分开。实际上，求解分类问题，就是要求出这条或这几条直线！问题是：怎么求？进一步理解支持向量机：支持向量机（SupportVectorMachine，SVM）中的“机（machine，机器）”：实际上是一个算法。在机器学习领域，常把一些算法看作是一个机器（又叫学习机器，或预测函数，或学习函数）。“支持向量”：则是指训练集中的某些训练点,这些点最靠近分类决策面，是最难分类的数据点。SVM:它是一种有监督（有导师）学习方法，即已知训练点的类别，求训练点和类别之间的对应关系，以便将训练集按照类别分开，或者是预测新的训练点所对应的类别。SVM主要针对小样

4、本数据进行学习、分类和预测（有时也叫回归）的一种方法，能解决神经网络不能解决的过学习问题。类似的根据样本进行学习的方法还有基于案例的推理（Case-BasedReasoning），决策树归纳算法等。过学习问题：训练误差过小导致推广能力下降，即真实风险的增加。推广能力：generalizationability，也可以说是泛化能力，就是对未知样本进行预测时的精确度。下面讨论线性可分情况下支持向量机的分类原理。8.1.1最优超平面的概念考虑P个线性可分样本{(X1，d1)，(X2，d2)，…，(Xp，dp)，…(XP，dP)}，对于任一输入样本Xp，期望输出为dp=±1

5、（代表两类类别标识）。用于分类的超平面方程为WTX+b=0(8.1)式中，X为输入向量，W为权值向量，b为偏置（相当于前述负阈值），则有WTXP+b>0dp=+1WTXP+b<0dp=-1超平面与最近的样本点之间的间隔称为分离边缘，用ρ表示。支持向量机的目标是找到一个分离边缘最大的超平面，即最优超平面。也就是要确定使ρ最大时的W和b。图8.1给出二维平面中最优超平面的示意图。可以看出，最优超平面能提供两类之间最大可能的分离，因此确定最优超平面的权值W0和偏置b0应是唯一的。在式(8.1)定义的一簇超平面中，最优超平面的方程应为:WTX0+b0=0（应该是W0X+b0

6、=0吧？）直接求W0和b0基本上不太可能，除了训练集无别的信息可用，如何办？一种方法：使求得的预测函数y =f(x)=sgn(W·X+b)对原有样本的分类错误率最小。如何使分类错误率最小？下面慢慢分析。由解析几何知识可得样本空间任一点X到最优超平面的距离为(8.3)从而有判别函数g(X)=r

7、

8、W0

9、

10、=W0TX+b0g(X)给出从X到最优超平面的距离的一种代数度量。将判别函数进行归一化，使所有样本都满足则对于离最优超平面最近的特殊样本Xs满足：Ig(Xs)I=1，称为支持向量。由于支持向量最靠近分类决策面，是最难分类的数据点，因此这些向量在支持向量机的运行中起着主

11、导作用。式(8.5)中的两行也可以组合起来用下式表示(8.5)dp(WTXP+b)≥1（8.6）其中，W0用W代替。由式(8.3)可导出从支持向量到最优超平面的代数距离为因此，两类之间的间隔可用分离边缘表示为上式表明，分离边缘最大化等价于使权值向量的范数

12、

13、W

14、

15、最小化。因此，满足式(8.6)的条件且使

16、

17、W

18、

19、最小的分类超平面就是最优超平面。r设x=(x1,x2,…,xn)Tx的范数:

20、

21、x

22、

23、=

24、x1

25、+

26、x2

27、+…+

28、xn

29、如何构造这个最优分类面呢？方法：平分最近点法和最大间隔法。两个方法殊途同归，它们求解得到同一个超平面。这两个方法与一个最优化问题求解