文档介绍：数学与计算机学院彭宏
支持向量机及其应用 Support Vector Machines and its Application
智能算法讲座(一)
目录
线性可分的支持向量(分类)机
线性支持向量(分类)机
支持向量(分类)机
最小二乘支持向量(分类)机
硬-带支持向量(回归)机
软-带支持向量(回归)机
-支持向量(回归)机
最小二乘支持向量(回归)机
支持向量机应用
SVM的描述
SVM是一种基于统计学****理论的模式识别方法,它是由Boser,Guyon,Vapnik在COLT-92上首次提出,从此迅速的发展起来,现在已经在许多领域(生物信息学,文本,图像处理,语言信号处理和手写识别等)都取得了成功的应用
putational Learning Theory)
SVM的描述
目标:找到一个超平面,使得它能够尽可能多的将两类数据点正确的分开,同时使分开的两类数据点距离分类面最远。
解决方法:构造一个在约束条件下的优化问题,具体的说是一个约束二次规划问题(constrained quadratic programing),求解该问题,得到分类器。
模式识别问题的一般描述
已知:n个观测样本,(x1,y1), (x2,y2)……(xn,yn)
求:最优函数y’= f(x,w)
满足条件:期望风险最小
损失函数
SVM的描述
期望风险R(w)要依赖联合概率F(x,y)的信息,实际问题中无法计算。
一般用经验风险Remp(w)代替期望风险R(w)
一般模式识别方法的问题
经验风险最小不等于期望风险最小,不能保证分类器的推广能力.
经验风险只有在样本数无穷大趋近于期望风险,需要非常多的样本才能保证分类器的性能。
需要找到经验风险最小和推广能力最大的平衡点。
一、线性可分的支持向量(分类)机
首先考虑线性可分情况。设有如下两类样本的训练集:
线性可分情况意味着存在超平面使训练点中的正类和
负类样本分别位于该超平面的两侧。
如果能确定这样的参数对(w,b)
的话,就可以构造决策函数来进行
识别新样本。
线性可分的支持向量(分类)机
问题是:这样的参数对(w,b)有许多。
解决的方法是采用最大间隔原则。
最大间隔原则:选择使得训练集D对于线性函数
(w·x)+b的几何间隔取最大值的参数对(w,b),并
由此构造决策函数。
在规范化下,超平面的几何间隔为
于是,找最大几何间隔的超平面
表述成如下的最优化问题:
(1)
线性可分的支持向量(分类)机
为求解问题(1),使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数:
其中, 称为Lagrange乘子。
首先求Lagrange函数关于w,b的极小值。由极值条件有:
得到:
(2)
(3)
(4)