支持向量机技术及应用

基于统计学习理论的支持向量机是一种新型的机器学习方法。本文介绍了统计学习理论和支持向量机的原理,对一系列的训练算法进行了探讨和比较。由于SVM具有良好的泛化能力和全局最优性能,已经被应用于模式识别和回归估计等领域,有着良好的应用前景。

科技信息2008年第27期

SCIENCE &TECHNO LO GY INFORMATION 0.引言

传统统计学中的众多理论是渐进理论,都是在样本数目足够多的前提下得到的,所提出的各种方法和结论也只有在样本数趋于无穷大时其可靠性才有理论上的保证。而在多数实际应用中,样本数目通常是有限的,这是很多包括模式识别在内的传统统计方法都难以取得理想效果的重要原因。

支持向量机是基于有限样本的统计学习理论基础上产生的一种新的机器学习算法,具有小样本学习、泛化能力强等特点,能有效地避免传统统计方法存在的过学习、局部极小点以及“维数灾难”等问题[1]。在数据分类以及回归估计方面的应用取得了空前的成功,能够较好的解决小样本学习问题。

1.支持向量机的基本原理

1.1统计学习理论

Vapnik 等人从60年代开始就致力于有限样本统计理论的研究,到90年代中期,逐步发展成为一个完善的理论体系———统计学习理论[2-3]。从理论上系统地研究了经验风险最小化原则成立的条件,有限样本下经验风险与期望风险的关系,以及如何利用这些理论找到新的学习原则和方法等问题。统计学习理论的主要内容有:

◆函数集的VC 维

VC 维是描述函数集或学习机器的复杂性,或者说是学习能力的一个重要指标。VC 维等价的直观定义可这样表示:假如存在一个有h 个样本的样本集,能够被一个函数集f(x,w )中的函数按照所有可能的2h

种形式分为两类,则称函数集能够把样本数为h 的样本集打散。VC 维就是用这个函数集中的函数所能够打散的最大样本集的样本数目。

◆推广性的界

推广性的界指各种类型的函数集及其经验风险和实际风险之间的关系。对于两类分类的学习问题,经验风险R e mp (w )和实际风险R(w)之间至少以1-η的概率如下关系:

R(w)≤R e mp (w)+Φ=R e mp (w)+

h(ln(2n/h)+1)-ln(η/4)n

#

(1)

R emp (w)为经验风险,Φ称作置信范围,h 为指示函数集的VC 维。学习机器的实际风险由两部分组成:一是经验风险(训练误差);二称作置信范围,置信范围与学习机器的VC 维h 及训练样本数n 有关。

◆结构风险最小化原则

选择使经验风险与置信范围之和最小的函数,即为最优函数。这种思想称作有序风险最小化或结构风险最小化(Structural Risk M inim ization),简称SRM 原则。

1.2支持向量机的分类机理

SVM 方法是1992年-1995年期间,在统计学习理论的基础上发展起来的一种新的模式识别方法,是统计学习理论中的VC 维理论和SRM 原理的具体实现[1,

4]。SVM 方法最初是从线性可分情况下的最优分类面提出的。

对于两类样本线性可分的情况,如图1所示,图中实心点和空心点分别表示两类训练样本。H 是把两类正确分开的分类线,H 1,H 2分别为过两类样本中离分类线最近的点且平行于分类线的直线,H 1,H 2的距离叫做两类的分类间隔(m argin)。所谓的最优分类线能将两类样本正确分开,且分类间隔最大。推广到高维空间,最优分类线就成为最优分类面。

图1最优分类面示意图

设d 维空间线性可分样本集(x i ,y i )i=1,2,…,n,x ∈R d ,y ∈{-1,+1}是类

别标号。样本集可被一超平面独立的分成两类,分类判别函数的表示形式为:g (x )=w x+b 。其中,w ∈R d 为权值向量,b ∈R,对判别函数进行归一化,使两类中的样本都满足g (x )≥1,离分类面最近的样本点g (x )=1,这样分类间隔就等于2/&w &。使间隔最大等价于使&w &2最小,而要求分类线对所有的样本正确分类,又要满足条件:y i (w x i +b)≥1,i=1,2,…,n 。

因此,最优分类面就是满足上述条件且使&w &2最小的分类面。两类样本中离分类面最近且平行于最优分类超平面的H 1、H 2上的训练样本就是使条件中等号成立的样本。它们叫做支持向量(Support Vectors ),如图1用大圆圈标出的样本。

最优分类面问题可以表示为约束优化问题,最优分类面的权系数向量αi 为L ag range 系数就是训练样本向量的线性组合,求解后的最优分类函数为:

g (x )=sg n(n

i =1

’α*

i y i (x i x)+b *

)=sgn (∑x i ∈S V

α*

i y

i (x i x )+b *)(2)

其中,x 为待分类样本,SV 为支持向量集,b *为分类阈值。对于样本集线性不可分的情况,可以引入松弛项ξi >0,和惩罚系数C ,起到对错分样本惩罚程度的作用,实现在错分样本的比例和复杂度之间的折衷。经对问题的转化,可求得同式(2)相同的分类决策函数。

对于两类样本的非线性分类的问题,SVM 的思想就是通过非线性映射(x ),将输入空间变换到另外一个高维空间,从而将非线性问题转化为线性问题。然后在这个新的高维空间求取最优的分类超平

支持向量机技术及应用

刘印锋

(临沂师范学院信息学院山东

临沂

276005)

【摘要】基于统计学习理论的支持向量机是一种新型的机器学习方法。本文介绍了统计学习理论和支持向量机的原理,对一系列的训练算法进行了探讨和比较。由于SVM 具有良好的泛化能力和全局最优性能,已经被应用于模式识别和回归估计等领域,有着良好的应用前景。

【

关键词】统计学习理论;支持向量机;训练算法Su ppor t Vector M ach ine T echnique an d Its Application

LIU Yin -feng

(College of Information,L inyi Normal Un iver sity,Linyi Sh andon g 276005,Ch ina)

【Ab str act 】Suppo rt v ecto r m achine

(SVM )based o n statistical learning theo ry is a kind o f nov el m achine learning metho ds.In this paper,

statistical learning theory and the principle o f SVM are in troduced in detail.A series of training algo rithms are discussed and com pared.SVM has been applied to many fields such as pattern reco gnition,regressio n du e to go od g eneralizatio n ability and globally optimal performan ce.It has g oo d p rospect.

【Key words 】Statistical learning theo ry ;Suppo rt v ecto r machine;T raining alg

orithm

○高校讲坛○55k E E 0

第1页下一页