Support Vector Machine 支持向量机

Presentation on theme: "Support Vector Machine 支持向量机"— Presentation transcript:

1 Support Vector Machine 支持向量机
张鑫

2 提纲 SVM的有关概念介绍 SVM问题的数学表示和推导 SVM的分解算法 简单的最优分类面SVM 广义最优分类面 SVM

3 SVM的描述 SVM是一种基于统计学习理论的模式识别方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速的发展起来，现在已经在许多领域（生物信息学，文本和手写识别等）都取得了成功的应用 COLT(Computational Learning Theory)

4 目标：找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。
解决方法：构造一个在约束条件下的优化问题，具体的说是一个受限二次规划问题(constrained quadratic programing),求解该问题，得到分类器。

5 模式识别问题的一般描述 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求：最优函数y’= f(x,w)
满足条件：期望风险最小 损失函数

6 期望风险R(w)要依赖联合概率F(x,y)的信息，实际问题中无法计算。
一般用经验风险Remp(w)代替期望风险R(w)

7 一般模式识别方法的问题 经验风险最小不等于期望风险最小，不能保证分类器的推广能力.
经验风险只有在样本数无穷大趋近于期望风险，需要非常多的样本才能保证分类器的性能。 需要找到经验风险最小和推广能力最大的平衡点。

8 最优分类面 简单情况：在线性可分的情况下的最优分类面（Margine最大）

9 SVM问题的数学表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 目标：最优分类面 wx-b=0
满足条件：是分类面 经验风险最小（错分最少） 推广能力最大（空白最大）

10 分类面方程满足条件 对(xi,yi) 分类面方程g(x)=wx-b应满足 即

11 空白 空白长度 =2x样本点到直线的距离 =2x

12 SVM问题的数学表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解： 目标：最优分类面 wx-b=0

13 广义最优分类面SVM 分类面条件的放宽 经验风险最小 空白最大（不变）

14 SVM的数学表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解： 目标：最优分类面 wx-b=0

15 SVM问题求解 将上述问题表示成拉格朗日乘子式 Kuhn-Tucker条件

16 得到 只要确定，便可解出w,b

17 将上述条件代入L中 新的优化问题 (Quadratic Programing)

18 SVM问题求解 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解 根据，求得w,b ，得到最优分类面

19 非线性分类面 非线性可分的数据样本在高维空间有可能转化为线性可分。 在训练问题中，涉及到训练样本的数据计算只有两个样本向量点乘的形式
使用函数 ,将所有样本点映射到高为空间，则新的样本集为 设函数

20 SVM的一般表示 已知：n个观测样本，(x1,y1), (x2,y2)…… (xn,yn) 求解 最优非线性分类面为

21 通常的内核函数 线性内核 径向基函数内核 多项式内核 S形内核

22 多项式内核

23 SVM的计算 求解如下问题： D={ yiyjxixj } D的存储代价=0.5 x (训练样本数)2 x 单元存储空间
0.5 x(7000)2x8=196 x 106 Byte

24 二次规划问题求解

25

26 SVM的分解算法 Edgar Osuna(Cambridge ,MA)等人在IEEE NNSP’97发表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法

27 SVM的分解算法 将向量分成两个集合,工作集B,固定集N。即 每次对B解决一个小的二次规划问题,保持N中的值不变
每次迭代检查当前结果，满足优化条件，则找到了优化问题的解，算法结束。

28 SVM的分解算法

29 SVM的分解算法 常数项 相等项 工作集的大小可以人为指定

30 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

31 SVM的分解算法 Arbitrarily choose |B| points from the data set.
Solve the subproblem defined by the variable in B. While there exist some j jN,such that replace any i ,i  B,with j and solve the new subproblem.

32 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

33 谢谢