《支持向量机SVM 简介》由会员分享,可在线阅读,更多相关《支持向量机SVM 简介(23页珍藏版)》请在金锄头文库上搜索。
1、Support Vector Machines,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,线性分类器,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,线性分类器,线性分类器,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,线性分类器,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b
2、),How would you classify this data?,线性分类器,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),Any of these would be finebut which is best?,线性分类器,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),线性分类器的间隔( margin):到超平面最近的样本与此超平面之间的距离。,最大间隔,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),具有最大间隔的线性分类器叫做最大间隔线性分类器。其就是一种最简单的支持向量机(SVM) (称为线性
3、支持向量机,即LSVM),线性支持向量机,f,x,y,+1 -1,f(x,w,b) = sign(w. x - b),支持向量(Support Vectors) :是那些距离超平面最近的点。,具有最大间隔的线性分类器叫做最大间隔线性分类器。其就是一种最简单的支持向量机(SVM) (称为线性支持向量机,即LSVM),线性支持向量机,最大间隔,Why 最大间隔?,+1 -1,f(x,w,b) = sign(w. x - b),支持向量(Support Vectors) :是那些距离超平面最近的点。,具有最大间隔的线性分类器叫做最大间隔线性分类器。其就是一种最简单的支持向量机(SVM) (称为线性支
4、持向量机,即LSVM),线性支持向量机,直观上感觉很好. 学习得到的线性分类器.其对未知样本的预测能力与分类器间隔有如下关系:,具体化分类超平面及其间隔,如何在数学上表示? 在m位空间中?,Plus-Plane,Minus-Plane,Classifier Boundary,zone “Predict Class = +1”,“Predict Class = -1” zone,Plus-plane = x : w . x + b = +1 Minus-plane = x : w . x + b = -1 ,具体化分类超平面及其间隔,Plus-Plane,Minus-Plane,Classifi
5、er Boundary,zone “Predict Class = +1”,“Predict Class = -1” zone,计算间隔,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin,我们怎样利用 w与b 计算margin?,Plus-plane = x : w . x + b = +1 Minus-plane = x : w . x + b = -1 ,注: 向量 w 与 Plus Plane 垂直. 为什么?,设 u 和 v 是 Plus Plane上的两个向量. 则
6、 w . ( u v ) 是多少?,所以 w 也垂直于Minus Plane,注: 向量 w 与 Plus Plane 垂直. 为什么?,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin,我们怎样利用 w与b 计算margin?,Plus-plane = x : w . x + b = +1 Minus-plane = x : w . x + b = -1 ,计算间隔,Plus-plane = x : w . x + b = +1 Minus-plane = x : w .
7、x + b = -1 向量 w 与 Plus Plane 垂直 设 x- 是 minus plane上任意一点 设 x+是plus-plane上距离 x-最近的点,x-,x+,计算间隔,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin,我们怎样利用 w与b 计算margin?,Plus-plane = x : w . x + b = +1 Minus-plane = x : w . x + b = -1 向量 w 与 Plus Plane 垂直 设 x- 是 minus pl
8、ane上任意一点 设 x+是plus-plane上距离 x-最近的点 注: 对于某实数l, x+ = x- + l w. 为什么?,x-,x+,计算间隔,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin,我们怎样利用 w与b 计算margin?,Plus-plane = x : w . x + b = +1 Minus-plane = x : w . x + b = -1 向量 w 与 Plus Plane 垂直 设 x- 是 minus plane上任意一点 设 x+是pl
9、us-plane上距离 x-最近的点 注: 对于某实数l, x+ = x- + l w. 为什么?,x-,x+,计算间隔,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin,我们怎样利用 w与b 计算margin?,x- 与 x+ 的连线与planes垂直. 于是x- 在w 的方向上移动一段距离就可与到达x+.,现在我们知道: w . x+ + b = +1 w . x- + b = -1 x+ = x- + l w |x+ - x- | = M 于是很容易由w 和b 得到 M
10、,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin Width,x-,x+,计算间隔,现在我们知道: w . x+ + b = +1 w . x- + b = -1 x+ = x- + l w |x+ - x- | = M 于是很容易由w 和b 得到 M,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin Width,w . (x - + l w) + b =
11、 1 = w . x - + b + l w .w = 1 = -1 + l w .w = 1 =,x-,x+,计算间隔,现在我们知道: w . x+ + b = +1 w . x- + b = -1 x+ = x- + l w |x+ - x- | = M,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin Width =,M = |x+ - x- | =| l w |=,x-,x+,计算间隔,学习最大间隔分类器,我们现在需要找到一种算法,来求出w 与 b,并且 能匹配上所有的样本点. 怎么做? 梯度下降? 退火算法? 矩阵求逆? 牛顿法?,Zone “Predict Class = +1”,“Predict Class = -1” zone,wx+b=1,wx+b=0,wx+b=-1,M = Margin Width =,x-,x+,利用二次优化求解,Minimizesubject to,yk (w . xk + b )= 1k=1,2,n,What You Should Know,线性 SVMs 最大间隔分类器 QP 的作用 (但是, 这里, 你不必知道如何求解它) 最大间隔问题可以转化为一个二次优化(QP)问题,