Support Vector Machine 支持向量机 张鑫 2002. 2.1
提纲 SVM的有关概念介绍 SVM问题的数学表示和推导 SVM的分解算法 简单的最优分类面SVM 广义最优分类面 SVM
SVM的描述 SVM是一种基于统计学习理论的模式识别方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速的发展起来，现在已经在许多领域（生物信息学，文本和手写识别等）都取得了成功的应用 COLT(Computational Learning Theory)
目标：找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。 解决方法：构造一个在约束条件下的优化问题，具体的说是一个受限二次规划问题(constrained quadratic programing),求解该问题，得到分类器。
模式识别问题的一般描述 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求：最优函数y’= f(x,w) 满足条件：期望风险最小 损失函数
期望风险R(w)要依赖联合概率F(x,y)的信息，实际问题中无法计算。 一般用经验风险Remp(w)代替期望风险R(w)
一般模式识别方法的问题 经验风险最小不等于期望风险最小，不能保证分类器的推广能力. 经验风险只有在样本数无穷大趋近于期望风险，需要非常多的样本才能保证分类器的性能。 需要找到经验风险最小和推广能力最大的平衡点。
最优分类面 简单情况：在线性可分的情况下的最优分类面（Margine最大）
SVM问题的数学表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 目标：最优分类面 wx-b=0 满足条件：是分类面 经验风险最小（错分最少） 推广能力最大（空白最大）
分类面方程满足条件 对(xi,yi) 分类面方程g(x)=wx-b应满足 即
空白 空白长度 =2x样本点到直线的距离 =2x
SVM问题的数学表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解： 目标：最优分类面 wx-b=0
广义最优分类面SVM 分类面条件的放宽 经验风险最小 空白最大（不变）
SVM的数学表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解： 目标：最优分类面 wx-b=0
SVM问题求解 将上述问题表示成拉格朗日乘子式 Kuhn-Tucker条件
得到 只要确定，便可解出w,b
将上述条件代入L中 新的优化问题 (Quadratic Programing)
SVM问题求解 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解 根据，求得w,b ，得到最优分类面
非线性分类面 非线性可分的数据样本在高维空间有可能转化为线性可分。 在训练问题中，涉及到训练样本的数据计算只有两个样本向量点乘的形式 使用函数 ,将所有样本点映射到高为空间，则新的样本集为 设函数
SVM的一般表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解 最优非线性分类面为
通常的内核函数 线性内核 径向基函数内核 多项式内核 S形内核
多项式内核
SVM的计算 求解如下问题： D={ yiyjxixj } D的存储代价=0.5 x (训练样本数)2 x 单元存储空间 0.5 x(7000)2x8=196 x 106 Byte
二次规划问题求解
SVM的分解算法 Edgar Osuna(Cambridge ,MA)等人在IEEE NNSP’97发表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法
SVM的分解算法 将向量分成两个集合,工作集B,固定集N。即 每次对B解决一个小的二次规划问题,保持N中的值不变 每次迭代检查当前结果，满足优化条件，则找到了优化问题的解，算法结束。
SVM的分解算法
SVM的分解算法 常数项 相等项 工作集的大小可以人为指定
SVM的分解算法 Proposition(Build down): moving a variable from B to N leaves the cost function unchanged,and the solution is feasible in the subproblem Proposition(Build up) moving a variable that violates the optimality condition from N to B gives a strict improvement in the cost function when the subproblem is re-optimized
SVM的分解算法 Arbitrarily choose |B| points from the data set. Solve the subproblem defined by the variable in B. While there exist some j jN,such that replace any i ,i B,with j and solve the new subproblem.
SVM分解算法的实例 SVMlight SMO Thorsten Joachims (UniversityDortmund ,Informatik, AI-Unit) Make Large-Scale SVM Learning Practical SMO John C. Platt (Microsoft Research) Fast Training of Support Vector Machines using Sequential Minimal Optimization
谢谢