神经计算研究现状及发展趋势

神经计算研究现状及发展趋势*陈兆乾周志华陈世福（南京大学计算机软件新技术国家重点实验室，南京210093）摘要神经计算是软计算的重要组成部分。近二十年来，该学科的研究受到了极大的重视，取得了大量成果，但也暴露出很多目前研究中存在的不足。本文综述了神经计算的研究现状及发展趋势，主要介绍了神经计算理论、方法、应用等不同层面的一些重要研究领域的研究进展，并指出了一些有待研究的重要问题。关键词神经网络，VC维，计算学习理论，集成，数据挖掘，快速学习，增量学习，规则抽取1引言神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，其组织能够模拟生物神经系统对真实世界所作出的交互反应[Koh88]。基于神经网络建立计算模型，并用于解决科学和工程中的问题就称为神经计算。该领域最早的研究可上溯到McCulloch和Pitts提出的M-P模型[MP43]。在Hebb提出了Hebb学习规则[Heb49]、Rosenblatt[Ros58]研制出感知机（Perceptron）之后，神经计算受到了极大的重视，吸引了大批研究人员参与该领域的研究工作，并取得了一定的进展。但是，由于1969年Minsky和Papert[MP69]指出感知机的缺陷并表示出对该方面研究的悲观态度，同时，以产生式规则为内部表示的专家系统方法展示出灿烂的前景，很长时间内神经计算的研究处于停滞状态。在此期间，为专家系统服务的知识工程成为了人工智能研究的主流。但是，随着知识工程的发展，Feigenbaum等[Fei81]知识工程倡导者意识到了所谓知识瓶颈问题，即将人类专家的知识转化为机器可执行的规则存在着很大的困难，而如果机器能够自学习，则可望解决该瓶颈问题。于是，机器学习研究得到了迅猛的发展[MCM83]。在研究中，研究者们[Mic87,Qui88]发现，与机械学习、类比学习等学习方式相比，示例学习是解决知识瓶颈问题唯一可行的方法。1982年，Hopfield[Hop82]利用全互连型神经网络和计算能量函数成功求解了计算复杂度为NP完全型的TSP（TravellingSalesmanProblem）问题。这充分展示了神经计算作为一种数值型示例学习方法蕴含的巨大潜力。从此，神经计算成为了一个非常热门的研究领域，经过多年的发展，已成为人工智能两大主流（连接主义和符号主义）之一。随着研究的深入，目前神经计算研究中存在的问题也逐渐暴露出来，其中的一些已成为神经计算进一步发展的阻碍。但是，从另一个方面来看，它们也揭示了该领域下一步应该着重研究的问题。本文从理论、方法、应用等不同层面，综述了神经计算一些重要研究领域的研究进展，主要包括神经网络VC维计算、神经网络集成、基于神经网络的数据挖掘，并指出了一些有待研究的重要问题。限于篇幅，本文没有对神经计算的其他重要领域做深入剖析，仅在结束语中简要述及。*国家自然科学基金、江苏省自然科学基金资助22神经网络VC维计算2.1重要性神经计算技术已经在很多领域得到了成功的应用，但由于缺少一个统一的理论框架[CC98]，经验性成分相当高。这使得研究者们难以对各种神经计算模型的性能及其适用范围进行理论分析，仅能用不十分可靠的实验性比较评价优劣。另一方面，在利用神经计算解决问题时，也只能采取具体问题具体分析的方式，通过大量费力耗时的实验摸索，确定出合适的神经网络模型、算法以及参数设置。这些缺陷已经对神经计算的进一步发展造成了极大的阻碍。如果能提供一套比较完备的理论方法，将可望解决上述问题。最近十年里，很多研究者都致力于这方面的研究，力图在一个统一的框架下来考虑学习与泛化的问题[Wol95]。PAC（ProbablyApproximatelyCorrect）学习模型[Val84]就是这样一个框架。作为PAC学习的核心以及学习系统学习能力的度量，VC维（Vapnik-Chervonenkisdimension）在确定神经网络的容量（capacity）、泛化能力（generalization）、训练集规模等的关系上有重要作用。如果可以计算出神经网络的VC维，则我们可以估计出要训练该网络所需的训练集规模；反之，在给定一个训练集以及最大近似误差时，我们可以确定所需要的网络结构。联系到Hornik等人[HSW89]所证明的结论，即“仅有一个隐层的网络就可以任意精度逼近任何函数，但确定该网络的结构是NP难问题”，显然，神经网络VC维计算的研究对神经网络的发展将会产生极大的促进作用。2.2VC维学习系统的容量对其泛化能力有重要影响[Vap82,BH89,GVBBS92]。低容量学习系统只需要较小的训练集，高容量学习系统则需要较大的训练集，但其所获的解将优于前者。对给定训练集来说，高容量学习系统的训练集误差和测试集误差之间的差别将大于低容量学习系统。Vapnik[Vap82]指出，对学习系统来说，训练集误差与测试集误差之间的差别是训练集规模的函数，该函数可以由学习系统的VC维表征。换言之，VC维表征了学习系统的容量。Anthony[Ant97]将VC维定义为：设F为一个从n维向量集X到{0,1}的函数族，则F的VC维为X的子集E的最大元素数，其中E满足：对于任意SE，总存在函数fsF，使得当xS时fs(x)=1，xS但xE时fs(x)=0。VC维可作为函数族F复杂度的度量，它是一个自然数，其值有可能为无穷大，它表示无论以何种组合方式出现均可被函数族F正确划分为两类的向量个数的最大值。对于实函数族，可定义相应的指示函数族，该指示函数族的VC维即为原实函数族的VC维。为便于讨论，我们针对典型的二元模式识别问题进行分析。设给定训练集为{(x1,y1),(x2,y2),…,(xl,yl)}，其中xiRn，y{0,1}。显然，xi是一个n维输入向量，y为二值期望输出。再假设训练样本与测试样本均满足样本空间的实际概率分布P(x,y)。对基于统计的学习方法来说，学习系统可以由一族二值函数{f(x,),}表征，其中参数可以唯一确定函数f()，为所有可能的取值集合。因此，{f(x,),}的VC维也表征了该学习系统的复杂度，即学习系统的最大学习能力，我们称其为该学习系统的VC维。3学习的目的就是通过选择一个参数*，使得学习系统的输出f(x,*)与期望输出y之间的误差概率最小化，即出错率最小化。出错率也称为期望风险（ExpectedRisk），如式1所示：),(),(21)(ydPfyRxx(1)其中P(x,y)为样本空间的实际概率分布。由于P(x,y)通常是未知的，因此无法直接计算R()。但是，对给定的训练集，其经验风险（EmpiricalRisk）Remp()却是确定的，如式2所示：liiiempfylR1),(21)(x(2)其中(xi,yi)为训练样本，l为训练集中样本数，即训练集规模。由数理统计中的大数定理可知，随着训练集规模的扩大，Remp()将逐渐收敛于R()。基于统计的学习方法大多建立在经验风险最小化原则（PrincipleofEmpiricalRiskMinimization）基础上，其思想就是利用经验风险Remp()代替期望风险R()，用使Remp()最小的f(x,l)来近似使R()最小的f(x,0)。这类方法有一个基本的假设，即如果Remp()收敛于R()，则Remp()的最小值收敛于R()的最小值。Vapnik与Chervonenkis[VC71]证明，该假设成立的充要条件是函数族{f(x,),}的VC维为有限值。Vapnik[Vap82]还证明，期望风险R()满足一个上界，即任取满足0≤1，下列边界以概率1–成立：lhlhRRemp)4/ln()1)/2(ln()()((3)其中h为函数族{f(x,),}的VC维，l为训练集规模。式3右侧第二项通常称为VC置信度（VCConfidence）。由式3可以看出，在学习系统VC维与训练集规模的比值很大时，即使经验风险Remp()较小，也无法保证期望风险R()较小，即无法保证学习系统具有较好的泛化能力。因此，要获得一个泛化性能较好的学习系统，就需要在学习系统的VC维与训练集规模之间达成一定的均衡。2.3研究进展2.3.1概述由于神经网络也是一种基于统计的学习方法，因此其VC维也满足2.2节中关于一般学习系统的讨论。从功能上来说，每一个权值、阈值等参数都已被确定的神经网络就相当于一个函数。不妨假设网络有n个输入神经元，m个输出神经元，则该网络对应于一个函数f：RnRm。如果我们用来表示所有权值、阈值等可调参数的集合，表示该集合可能的取值集合，则神经网络的学习过程可被视为通过选择*来确定函数f(x,*)。这样，如果求出函数族f()的VC维，我们就得到了该神经网络的VC维。由于神经网络的VC维取决于网络中可调参数的数目，而后者又是由网络的拓扑结构所确定的，因此，网络的VC维与拓扑结构之间有必然的联系。在给定训练集的情况下，如果我们能求出合适的VC维，则可以帮助确定网络的结构；反之，在给定网络结构的情况下，如果我们能求出其VC维，则可以确定合适的训练集规模。显然，这对寻找Hornik[HSW89]指出的最优解有重要的启发作用。4Cover[Cov65]最早进行了神经网络VC维的计算工作，在此之后，Vapnik在相关的统计学方面做了大量的工作[Vap82]，他们的成果与Blumer等人[BEHW89]在计算学习理论方面的工作一起，被Valiant[Val84]引入PAC学习模型中。从此，神经网络VC维的计算受到了极大的重视。1997年，Vidyasagar[Vid97]通过构造性方法证明，神经网络的VC维并不一定是有限的。因此，对神经网络VC维的讨论必须针对一定的网络结构，这样才能保证VC维为有限值。目前，这方面的研究成果主要集中在以阈值函数（thresholdfunction）、分段多项式函数（piecewisepolynomialfunction）和Sigmoid函数为响应函数的神经网络上。为便于讨论，我们引入三个符号：O、和。对于任意函数f和g，如果存在c10使得f≤c1g，则记为f=O(g)；如果存在c20使得f≥c2g，则记为f=(g)；如果f=O(g)和f=(g)同时满足，则记为f=(g)。2.3.2阈值网络Cover[Cov65]和Baum等人[BH89]分别证明，对以阈值函数为响应函数的前馈神经网络，若网络有w个连接权，则其VC维上界为O(wlogw)，其中log()表示以2为底的对数。1993年，Sakurai[Sak93]证明，对仅有一个隐层且输入为实值向量的前馈阈值神经网络来说，如果网络有w个可调参数，则其VC维下界为(wlogw)。1994年，Maass[Mas94]对Sakurai的结论做了进一步扩展，证明对至少有两个隐层的前馈阈值神经网络来说，其VC维下界为(wlogw)。Maass的结论表述为定理1：[定理1]设(n)nN为层数d≥3（至少两个隐层）的层间全连接神经网络的任意序列，并且n有n个输入神经元和(n)个计算神经元（包括隐层神经元和输出神经元），其中(n)个计算神经元位于第1隐层，至少4logn个位于第2隐层，则n有(n2)个权，其VC维VC(n)=(n2logn)。1999年，Carter和Oxley[CO99]研究了神经网络VC维与组合几何（combinatorialgeometry）[Zas97]之间的关系，利用Poincare多项式[OT91]给出了阈值前馈网络VC维计算公式，其结论表述为定理2：[定理2]给定向量v1,v2,…,vpRd，阈值t1,t2,…,tpR，以及参数w1,w2,…,wpR，设为阈值前馈网络，且隐层数目足够多，则该网络的第一隐层所产生的函数族为式4，该网络的VC维为式5。pkkkkkkkdpdtvwtxvHwxffF1,},,),()(|:{RR(4)