svm支持向量机.ppt

1、支持向量机 SVM,同时适用于线性和非线性数据的分类方法 使用非线性映射将原始的训练数据映射到一个更高维的空间中 利用新的维度，SVM寻找线性的最佳决策边界 使用一个恰当的到足够高维空间的非线性映射，两个分类的数据总可以用一个超平面分离 SVM 通过使用支持向量机来找到这个超平面和它的边缘,SVM支持向量机,支持向量机,寻找一个线性超平面 (决策边界) 用来分离两个类的样本,支持向量机线性可分情况,考虑一个包含N个训练样本的二元分类问题。 每个样本表示为一个二元组(xi,yi)(i=1,2,.,N)，其中xi=(xi1,xi2,.xin),对应于第i个样本的属性集。 令yi-1，+1表示它的类

2、标号 假设有如图所示的数据，每个数据只有两个属性A1和A2 从图中可以看到该数据集是线性可分的，因为可以画一条直线将类+1的样本与类-1的样本分开,支持向量机,一个可能的解,支持向量机,另一个解,支持向量机,其它可能的解,支持向量机,B1或B2哪一个是最好的? 如何定义“最好”?,支持向量机,可以画出无限多条分离直线。那条是最好的呢？ 希望对先前未见到的样本具有最小分类误差的那一条。 在3维情形，我们要找的是最佳分离平面。推广到一般的n维空间，则希望找出最佳超平面来分离样本,支持向量机,SVM通过搜索最大边缘超平面（maximum marginal hyperplane）来处理该问题。下图显示

3、了两个可能的分离超平面和相关连的边缘。 两个超平面对所有已知的样本正确地进行了分类。 从图上观察，直观地我们期望具有较大边缘的超平面在对未来的样本分类比具有较小边缘的超平面更准确。 在学习阶段，SVM要搜索具有最大边缘的超平面。最大超平面（MMH）相关联的边缘给出类之间的最大分离,支持向量机,最大化边缘的超平面 = B1要比 B2 好,决策边界,边缘可以定义为从超平面到其边缘的一个侧面的最短距离等于从该超平面到其边缘的另一个侧面的最短距离，其中边缘的侧面平行于超平面 一个线性分类器的决策边界可以写成如下形式： wx+b=0 其中w和b是模型的参数。w是权重向量，即w=(w1,w2,.wn)，n

4、是属性数，b是一个标量，通常称作偏倚（bias）,决策边界,如果xa和xb是两个位于决策边界上的点，则 两式相减得到,其中xb-xa是一个平行于决策边界的向量，它的方向是从xa到xb。从上式中可以推出w的方向必然垂直于决策边界。,w,决策边界,位于分离超平面上方的点xs满足 位于分离超平面下方的点xc满足 可以用以下方事预测任何测试样本z的类标号,线性分类器的边缘,可以调整参数W和b使得定义边缘“侧面”的超平面可以记为 H1:w0+w1x1+w2x2=1，对所有yi=+1 H2:w0+w1x1+w2x2=1，对所有i,给出两个平行的超平面的方程如下 H1:w0+w1x1+w2x2=1，对所有y

5、i=+1 H2:w0+w1x1+w2x2=-1，对所有yi=-1 决策边界的边缘由这两个超平面之间的距离给定。 令x1是H1上的一个数据点，x2是H2上的一个数据点，将它们分别代入H1和H2，则边缘(宽度)可以通过两式相减得到：,学习线性SVM模型,SVM的训练阶段包括从训练数据中估计决策边界的参数w和b。选择的参数必须满足如下两个条件： 类标号为1的训练实例都必须位于超平面 上或位于它的上方 类标号为-1的训练实例都必须位于超平面 上或位于它的下方,支持向量机,学习线性SVM模型,上述两个不等式可以写成一条式子 SVM相较于其他线性分类器的区别在于SVM要求其决策边界的边缘必须是最大的。这等

6、价于最小化下面的函数,学习线性SVM模型,在线性可分的情况下，SVM的学习任务可以形式化地描述为如下的优化问题： 由于目标函数是二次的，约束在参数w和b上是线性的，因此这个问题是一个凸优化问题，下面使用标准的拉格朗日乘子方法求解。,学习线性SVM模型,将约束条件写入目标函数将原问题变成一个无约束问题。新目标函数称为该优化问题的拉格朗日算子 参数 称为拉格朗日乘子。 拉格朗日算子中的第一项与原目标函数相同，而第二项表达了不等式约束。,不考虑约束时，原目标函数 当w=0时取得最小值。 这个解是不满足约束条件的，因为b没有可行解！ 拉格朗日算子通过从原目标函数减去约束条件的方式合并了约束条件。,假定

7、 ，则任何不可行解仅仅是增加了拉格朗日算子的值。 为了最小化拉格朗日算子，必须对Lp关于w和b求偏导并令其等于0： 由于拉格朗日乘子未知，从上式无法求得w和b,限制拉格朗日乘子非负，则可以将不等式约束转化为一组等式约束。这种变换导致如下拉格朗日乘子，称作Karuch-Kuhn-Tucher(KKT)条件 看起来好像拉格朗日乘子的数目和训练样本一样多。实际上使用第二个约束后很多拉格朗日乘子变为0 该约束表明除非训练实例满足方程 否则拉格朗日乘子必须为0,对应于 的训练实例位于超平面bi1或bi2上，称为支持向量。 而不在超平面上的训练实例满足 定义决策边界的参数w和b仅依赖于支持向量 优化问题的

8、求解由于涉及大量参数w，b和 而较为复杂 通过将拉格朗日算子变换为仅包含拉格朗日乘子的函数可以简化该问题。,为了求解优化问题将 代入 得到仅包含 的形式，称作对偶问题 与原问题求最小值不同对偶问题是一个求最大值的问题，并且其中不含决策边界的参数,对偶问题可以使用二次规划来进行求解,对上述数据集使用二次规划求解对偶问题，得到每一个训练实例的拉格朗日乘子。注意仅前两个实例具有非零的拉格朗日乘子，它们对应于该数据集的支持向量。 令w=(w1,w2)，b为决策边界的参数。使用下式来求解w1和w2,偏倚项b使用公式 对每个支持向量进行计算(由于拉格朗日乘子是使用数值方法得到的，存在误差，所以计算出的b值

9、可能不唯一，故使用b的平均值) b=7.93,一旦确定了决策边界的参数，检验实例z可以按以下的公式来分类,支持向量机线性不可分,如果问题是不可线性分离的该如何处理?,B1,B2,右图中B1不能正确分类两个黄色的样本，而B2能够正确分类。 如果黄色的样本代表噪声，则B1更可取一些，因为它具有较宽的决策边界,前面给出的SVM公式只能构造没有错误的决策边界 对于线性不可分的情况，一种处理的方法是允许决策边界存在一定的错误，这就是“软边缘”的方法,对于上图中的数据集，决策边界不再满足公式给定的所有约束条件。 可以考虑放松不等式约束，以适应非线性可分数据 通过在优化问题的约束中引入非负的松弛变量s来实现

10、：,松弛变量的含义,圆圈P是一个违反 的实例。 设w.x+b=-1+c是一条经过P，且平行于决策边界的直线，则它与超平面w.x+b=-1之间的距离为c/|w|,软边缘的方法是要在边缘的宽度与线性决策边界允许的训练错误数目之间做一个折中。 为了防止算法找到边缘很宽，但误分了许多训练实例的决策边界，对目标函数作修改，以惩罚那些松弛变量值很大的决策边界。使用如下的目标函数 其中的C和k是用户指定的参数，表示对误分训练实例的惩罚(罚函数法)。,非线性支持向量机,对于线性不可分的数据集，另外一种方法是构造非线性的决策边界，问题是如何表示这条边界？ 采用的方法是推广线性决策边界到非线性数据上！,设法将数据

11、从原先的坐标空间X变换到一个新的坐标空间 中，从而可以在变换后的坐标空间中使用一个线性的决策边界来划分样本。 进行变换后，就可以继续使用线性支持向量机的算法在变换空间中找到一个线性的决策边界。 问题：如何进行变换？,非线性的决策边界,圆圈(类标号y=1)集中在图的中心附近，而方块(类标号y=-1)分布在离中心较远的地方,可以使用下面的公式对数据集中的实例分类 所以数据集的决策边界可以表示如下： 简化后有,需要一个非线性变换 ，将数据从原先的特征空间映射到一个新的空间，决策边界在这个空间下成为线性的。 根据原决策边界的形式，可以选择如下的变换 在变换空间中，寻找参数 使得,对于前面的数据，以 为

12、坐标绘图。在变换空间中，所有的圆圈都位于图的左下方，可以构建一个线性的决策边界,维灾难,这种方法的潜在问题是，对高纬数据可能产生维灾难。 维灾难（curse of dimensionality） 随着维度增加，许多数据分析变得非常困难。 所要考虑的因素越来越多，另一方面数据在它所在的空间中越来越稀疏。 对于分类问题，可能没有足够的数据来创建模型，可靠地将可能的对象指派给一个类 对于聚类问题，点之间的密度和距离的定义变得不太有意义,非线性SVM模型,将实例的属性通过变换映射到一个更高维的空间上这件事看起来大有可为(维尔斯特拉斯定理保证不管多复杂的边界形状，都可以用多项式函数无限逼近)，但是也存在

13、很明显的问题 如何选择映射函数，确保可以在变换后的空间中构建线性决策边界。（当然理论上可以把数据映射到无限维空间！） 在高维空间解决约束优化问题的代价很大！,非线性SVM模型,下面假定存在一个合适的函数 可以进行数据变换。在变换空间中，线性决策边界具有如下形式： 非线性SVM的学习任务可以形式化表达为如下的优化问题： 与线性SVM的区别在于学习任务是在变换后的属性 上而不是在原属性上进行的,非线性SVM模型,使用同线性SVM相同的方法，可以推导出该约束优化问题的对偶拉格朗日算子： 使用二次规划技术得到 后，就可以通过下式导出参数w和b：,非线性SVM模型,最终可以通过下式对检验实例z进行分类：

14、 由于大部分的计算公式都涉及计算变换空间中向量对之间的点积 （即相似度），这可能会导致维灾难。,核方法,解决维灾难的一种突破性方案是采用核方法 点积常用来度量两个向量间的相似度(可以理解为投影)。 点积 可以看作两个实例xi和xj在变换空间中的相似性度量。 核方法是一种使用原属性集计算变换空间中的相似度的方法。,核方法,考虑函数 两个输入向量u和v在变换空间中的点积可以写成如下形式：,核方法,上式表明，变换空间中的点积可以用原空间中的相似度函数表示： 在原属性空间中计算的相似度函数K称为核函数(kernel function),核方法,核技术在SVM中的作用 只要核函数K满足一定条件，而不需要知道变换的具体形式。 相对于使用变换后的属性集 ，使用核函数计算点积的开销更小。 计算在原空间进行，避免维灾难。,Mercer定理,对非线性SVM使用的核函数的主