小样本机器学习理论_统计学习理论
第25卷第1期
南 京 理 工 大 学 学 报Vol . 25No . 1小样本机器学习理论:统计学习理论*
谭东宁 谭东汉 ①
(信息产业部电子第55研究所, 南京210016) (①南京理工大学机械学院, 南京210094)
摘要 统计学习理论是由Vapnik 等人提出的一种有限样本统计理论, 是模式识别领域新近发展的一种新理论, 着重研究在小样本情况下的统计规律及学习方法性质。它为小样本机器学习问题建立了一个较好的理论框架, 也发展了一种新的通用学习算法———支持向量机, 较好地解决了小样本机器学习问题。该文旨在介绍统计学习理论的基本思想、特点、研究现状和一些思考。
关键词 样本, 统计估计, 模式识别; 统计学习理论, 机器学习
分类号 TP 202. 4, TP 391. 42
基于数据的机器学习是现代智能技术中的重要方面, 研究从观测数据(样本) 出发寻找统计规律, 并利用这些规律对未来数据或无法观测的数据进行预测。现有机器学习方法共同的重要理论基础之一是统计学, 传统统计学研究的是样本数目趋于无穷大时的渐近理论, 现有的学习方法也是基于此假设。但在实际问题中, 样本数往往是有限的, 因此一些理论上很优秀的学习方法在实际中却表现得不尽人意。鉴于此, V . Vapnik 等人从60年代开始就致力于有限样本统计理论的研究, 并将其理论称为统计学习理论(SLT ) , 到90年代中期, 随着其理论的不断发展和成熟, 也由于神经网络等学习方法在理论上缺乏实质性进展, 该理论开始受到越来越广泛的重视[2, 3]。有学者认为, SLT 和SVM 正在成为继神经网络研究之后新的研究热点, 并将推动机器学习理论和技术有重大的发展[3]。我国早在80年代末就有学者注意到统计学习理论的基础成果[4], 但之后较少研究, 目前只有少部分学者认识到这个重要的研究方向。本文旨在向国内学者介绍统计学习理论的基本思想和特点, 以使更多的学者能够看到它们的优势, 从而积极地进行研究和探索, 并使该理论在解决实际问题中发挥作用。[1]
1 机器学习的基本问题
1. 1 问题的表示
机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计, 使收稿日期:2000-04-28
国家自然科学基金资助项目 国家教委博士后基金资助项目(项目号69885004)
谭东宁 男 39岁 博士后
总第116期 谭东宁 谭东汉 小样本机器学习理论:统计学习理论109它能够对未知输出作出尽可能准确的预测。
一般地, 变量y 与x 存在一定的未知依赖关系, 即遵循某一未知的联合概率F (x , y ) , x 和y 之间的确定性关系可视作是其特例, 机器学习问题就是根据n 个独立同分布观测样本
(x 1, y 1) , (x 2, y 2) , …,(x n , y n ) (1) 在一组函数{f (x , w ) }中求一个最优的函数f (x , w 0) 对y 与x 之间的依赖关系进行估计, 并使期望风险
R (w )=L (y , f (x , w ) ) d F (x , y )
最小。其中,{f (x , w ) }称作预测函数集(也称作学习函数、学习模型或学习机器) , w 为函数的广义参数, {f (x , w ) }可以表示任何函数集; L (y , f (x , w ) ) 为由于用f (x , w ) 对y 进行预测而造成的损失, 不同类型的学习问题有不同形式的损失函数。
对模式识别问题而言, 输出y 是类别标号。比如2类情况下y ={0, 1}或{1, -1}, 其预测函数称作指示函数, 而损失函数则可定义为
0 y =f (x , w ) L (y , f (x , w ) 1 y ≠f (x , w )
使风险最小就是Bayes 决策中使错误率最小。∫(2) (3)
对函数逼近问题而言, y 是连续变量(这里假设为单值函数) , 可采用最小平方误差准则, 其损失函数可定义为
2 L (y , f (x , w ) )=(y -f (x , w ) ) (4)
对概率密度估计问题而言, 学习的目的是根据训练样本确定x 的概率密度。若估计的密度函数为p (x , w ) , 则损失函数可以定义为密度函数的自然对数, 即
L (p (x , w ) )=-ln p (x , w )
1. 2 经验风险最小化(5)
在上面的问题表述中, 学习的目标在于使期望风险最小化, 但是, 由于可以利用的信息只有样本(1) 式, 这样(2) 式的期望风险并无法计算, 因此传统的学习方法中采用了所谓经验风险最小化(ERM ) 准则, 即用样本来定义经验风险
R emp (w )=∑L (y i , f (x i , w ) ) (6) n i =1
作为对(2) 式的估计, 设计学习算法使它最小化。对损失函数(3) , 经验风险就是训练样本错误率; 对损失函数(4) , 经验风险就是平方训练误差; 而对损失函数(5) , ERM 准则就等价于最大似然方法。
事实上, 用ERM 准则代替期望风险最小化并没有经过充分的理论论证, 只是直观上合理的想当然做法, 但这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上, 而实际上, 即使可以假定当n 趋向于无穷大时,(6) 式趋近于(2) 式, 在很多问题中的样本数目也离无穷大相去甚远。那么在有限样本下ERM 准则得到的结果就很难说能使真实风险也较小。
1. 3 复杂性与推广能力
ERM 准则不成功的一个例子是神经网络的过学习问题。开始, 很多注意力都集中在如何使R emp (w ) 更小, 但很快就发现, 训练误差小并不总能导致好的预测效果。某些情况下, 训练误差过小反而会导致推广能力的下降, 即真实风险的增加, 这就是过学习问题。n
110南 京 理 工 大 学 学 报 第25卷第1期之所以出现过学习现象, 一是因为样本不充分, 二是学习机器设计不合理, 这2个问题是互相关联的。设想一个简单的例子, 假设有1组实数样本{x , y }, y 取值在[0, 1]之间, 那么不论样本是依据什么模型产生的, 只要用函数f (x , α)=sin (αx ) 去拟合它们(α是待定参数) , 总能找到一个α使训练误差为零, 但显然得到的“最优”函数并不能正确代表真实的函数模型。究其原因, 是试图用一个十分复杂的模型去拟合有限的样本, 导致丧失了推广能力。学习机器的复杂性与推广性之间的这种矛盾同样可以在许多学习方法中看到。
文献[3]给出1个实验例子, 在有噪声条件下用模型y =x 产生10个样本, 分别用1个一次函数和1个二次函数根据ERM 准则去拟合, 结果显示, 虽然真实模型是二次, 但由于样本数有限且受噪声的影响, 用一次函数预测的结果更好。同样的实验进行了100次, 71%的结果是一次拟合好于二次拟合。
由此可见, 在有限样本情况下, (1) 经验风险最小并不一定意味着期望风险最小; (2) 学习机器的复杂性不但应与所研究的系统有关, 而且也要和有限数目的样本相适应。需要一种能够指导在小样本情况下建立有效的学习和推广方法的理论。2
2 统计学习理论的核心内容
统计学习理论正是研究小样本统计估计和预测的理论, 主要内容包括4个方面[2]:(1) 经验风险最小化准则下统计学习一致性的条件; (2) 在这些条件下关于统计学习方法推广性的界的结论; (3) 在这些界的基础上建立的小样本归纳推理准则; (4) 实现新的准则的实际方法(算法) 。其中, 最有指导性的理论结果是推广性的界, 与此相关的一个核心概念是VC 维。
2. 1 VC 维
为了研究学习过程一致收敛的速度和推广性, 统计学习理论定义了一系列有关函数集学习性能的指标, 其中最重要的是VC 维。模式识别方法中VC 维的直观定义是, 对1个指示函数集, 如果存在h 个样本能够被函数集中的函数按所有可能的2种形式分开, 则称函数集能够把h 个样本打散; 函数集的VC 维就是它能打散的最大样本数目h 。若对任意数目的样本都有函数能将它们打散, 则函数集的VC 维是无穷大。有界实函数的VC 维可以通过用一定的阈值将它转化成指示函数来定义。
VC 维反映了函数集的学习能力, VC 维越大则学习机器越复杂(容量越大) 。遗憾的是, 目前尚没有通用的关于任意函数集VC 维计算的理论, 只对一些特殊的函数集知道其VC 维。比如在n 维实数空间中线性分类器和线性实函数的VC 维是n +1, 对于一些比较复杂的学习机器(如神经网络) , 其VC 维除了与函数集(神经网结构) 有关外, 还受学习算法等的影响, 其确定更加困难。对于给定的学习函数集, 如何(用理论或实验的方法) 计算其VC 维是当前统计学习理论中有待研究的一个问题[5]。
2. 2 推广性的界
统计学习理论系统地研究了对于各种类型的函数集, 经验风险和实际风险之间的关系, 即推广性的界[2]。关于2类分类问题, 结论是, 对指示函数集中的所有函数(包括使经验风险最小的函数) , 经验风险R emp (w ) 和实际风险R (w ) 之间以至少1-η的概率满足如下关系:h
总第116期 谭东宁 谭东汉 小样本机器学习理论:统计学习理论111
(7) n
式中, h 是函数集的VC 维, n 是样本数。
这一结论从理论上说明了学习机器的实际风险由2部分组成:一部分是经验风险(训练 R (w )≤R e m p (w ) +误差) , 另一部分称作置信范围, 它和学习机器的VC 维h 及训练样本数n 有关。可以简单地表示为
R (w )≤R e m p (w ) +Υ(h /n ) (8) 它表明在有限训练样本下, 学习机器的VC 维越高(复杂性越高) 则置信范围越大, 导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小, 还要使VC 维尽量小, 以缩小置信范围, 才能取得较小的实际风险, 从而对未来样本有较好的推广性。
需要指出, 推广性的界是对于最坏情况的结论, 在很多情况下是较松的, 尤其当VC 维较高时更是如此。而且, 这种界只在对同一类学习函数进行比较时有效, 可以指导从函数集中选择最优的函数, 但在不同函数集之间比较却不一定成立。Vapnik 指出, 寻找更好地反映学习机器能力的参数和得到更紧的界是学习理论今后的研究方向之一。
2. 3 结构风险最小化
从上面的结论看到, ERM 准则在样本有限时是
不合理的, 需要同时最小化经验风险和置信范围。
其实, 在传统方法中, 选择学习模型和算法的过程就
是调整置信范围的过程, 如果模型比较适合现有的
训练样本(相当于h /n 值适当) , 则可以取得比较好
的效果。但因为缺乏理论指导, 这种选择只能依赖
先验知识和经验, 造成了如神经网络等方法对使用
者“技巧”的过分依赖。
统计学习理论提出了一种新的策略, 即把函数
集构造为1个函数子集序列, 使各个子集按照VC
维的大小(亦即Υ的大小) 排列, 在每个子集中寻找函数集子集:S 1 S 2 S 3VC 维:h 1≤h 2≤h 3[2]图1 有序风险最小化示意Fig . 1 Demonstration of SRM
最小经验风险, 在子集间折衷考虑经验风险和置信范围, 以取得实际风险的最小, 如图1所示。这种思想称作结构风险最小化(Structural Risk M inimization , 或译为有序风险最小化[4]) , 即S RM 准则。统计学习理论还给出了合理的函数子集结构应满足的条件及在SRM 准则下实际风险收敛的性质[2]。
实现SRM 原则可以有2种思路, 一是在每个子集中求最小经验风险, 然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时, 当子集数目很大甚至无穷时不可行。因此有第2种思路, 即设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为0) , 然后只需选择适当的子集使置信范围最小, 则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思想的具体实现, 其具体细节可参考文献[2, 5]。
3 结束语
由于统计学习理论建立了一套较好的有限样本下机器学习的理论框架和通用方法, 较好地解决了小样本、非线性、高维数和局部极小点等实际问题, 因此成为90年代末发展最快的研究方向之一, 其核心思想就是学习机器要与有限的训练样本相适应。本文对它们的基本思想、方法及研究方向进行了介绍, 也阐述了笔者对该理论的一些认识, 希望读者对这一领域有一个基本的了解。统计学习理论虽然提出已经多年, 但从它自身的发展到现在被重视毕竟才只有几年的时间, 其中还有很多尚未解决或尚未充分解决的问题, 在应用方面的研究更是刚刚开始。因此, 这是一个十分值得重视并大有可为的研究领域。
参考文献
1 V apnik V N . Estimation of dependencies based o n empirical data . Berlin :Spring er -Verlag , 19822 V apnik V N . T he nature of statistical learning theory . New York :Springer -V erlag , 1995
3 Cherkassky V , M ulier F . Learning from data :co ncepts , theory and methods . N ew York :Jo hn V iley &Sons , 1997
4 加肇祺. 模式识别. 北京:清华大学出版社, 1988
5 V apnik V N , Levin E , Le Cun Y . M easuring the V C -dimensio n of a learning machine . N eural Computation , M IT Press , 1994(6) :851~876
Small -sample Machine Learning Theory :
Statistical Learning Theory
Tan Dongnin T an Donghan ①
(Electronic 55th Institude , Ministry of Information Industry , Nanjing 210016)
(①School of Mechanics , NUST , Nanjing 210094)
ABSTRAC T Statistical Learning Theory , a recently developed new theo ry for pattern recogni -tion , is a small -sample statistics proposed by Vapnik et al , w hich deals mainly with the statistic principles w hen samples are limited , especially to describe the properties of learning procedure in such cases . It provides us a new framewo rk for the small -sample learning problem , and also a novel powerful learning method called Suppo rt Vector Machine , w hich can solve small -sample learning problem better . This paper will introduce the basic ideas of the theory , its m ajor charac -teristics , some current research trends of it and some thinking from us about it .
KEY W ORDS sam ple trees , statistical estimation , pattern recognition ; statistical learning theo -ry , machine learning