机器学习是研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构,从而不断改善自身性能。它是人工智能最早关注的问题之一,是使计算机具有智能的根本途径。一个不具有学习能力的智能系统难以称得上真正的智能系统,但以往的智能系统普遍缺少学习能力。例如,它们的推理仅限于演绎而缺少归纳,因此至多只能够证明已存在的事实、定理,而不能发现新的定理、定律和规则等。随着人工智能的深入发展,这些局限性表现得愈加突出。机器学习历经几十年发展,产生了各种各样的方法。从学习所依赖的经验(输入)与学习所要获得的结果(输出)之间的关系来看,学习策略可分为归纳、类比和演绎三种。归纳:输入概念的实例,学习目标是从这些实例概括出关于这个概念的描述,或改进概念的已有描述。类比:输入新问题的描述,学习目标是寻找系统先前已解决的类似问题,并用解决该问题的经验知识处理新问题。演绎:输入的新问题能够用学习系统已有的知识解决,但知识库的相关部分不能被有效地利用,学习目标是将这些部分转换为更好的形式。实际上,类比策略可看作归纳和演绎策略的综合,因而最基本的学习策略只有归纳和演绎。从学习内容角度看,归纳是从个别到一般、从部分到整体的行为,所学知识超过原有知识库所蕴含的范围,我们称之为知识级学习;而演绎是“保真”变换和特化的过程,尽管所学知识能够提高系统的效率,但仍被原有的知识库所蕴含,我们称之为符号级学习。从实现技术角度看,归纳学习使用基于统计的方法,演绎学习使用基于规则的方法。基于规则的方法,优点是简单、效率高,而且发现新规则后可以方便地加入。但规则总会有例外,规则过多以后,需要权衡这些规则,保持其一致性,这是很困难的。另外,基于规则的方法对领域的依赖性强,可移植性差。基于统计的方法需要有合适的方法产生大量廉价的训练数据,计算复杂度高,但它与应用领域无关,可移植性好。20世纪60年代中期至80年代中期,由于人工智能的研究重点是符号系统和基于知识的方法,机器学习以基于规则的方法为主。20世纪80年代后期,随着神经网络研究重新崛起及其成功应用,基于统计的学习方法迅速发展。特别是最近十几年,互联网的普及和计算机在各个领域的应用,大量数据潮水般涌来,如何从中发现隐含的知识,对机器学习提出了重大挑战,也给基于统计的学习方法带来新的发展机遇。在众多基于统计的学习方法中,支持向量机(Support Vector Machine,简称SVM)是个新秀,但因其深厚的理论背景和出色的实际表现备受人们青睐。支持向量机是20世纪90年代中期出现的机器学习技术,是近年来机器学习领域的研究热点。这项技术从提出到现在不过十年时间,但其研究进展非常之快、之大。它有坚实的理论基础,应用上也是有口皆碑,在手写体数字识别、文本分类等具体问题上创造和保持着目前的最好记录。这项既经得起理论推敲又经得起实践检验的技术,是传统机器学习技术不能比的,它的发展潜力是令人鼓舞的。基于这样的认识,我选择了这一研究领域。支持向量机的理论基础是统计学习理论,该理论的研究始于20世纪60年代末。此后近20年时间里,前苏联学者Vapnik做了大量开创性、奠基性的工作,提出了“结构风险最小化”原理。这个时期的工作主要是纯理论性的,没有引起人们重视。1995年,Corts&Vapnik在其论文“Support Vector Networks”中提出支持向量机,它实现了“结构风险最小化”原理。支持向量机有很强的泛化能力,它在解决复杂问题,诸如手写体数字识别、人脸检测、文本分类、大规模生物信息处理等方面的上乘表现,引起人们极大关注。国内外著名大学和大公司的研发机构纷纷成立了相关的研究小组,越来越多的人加入这一研究行列,形成近年来机器学习领域的研究热点。基础研究涉及训练算法、模型选择、多目标分类等,应用研究涉及三维目标识别、非线性模式重建、智能信号处理、信息检索、文本分类和数据挖掘等。有关的国际学术会议、专业杂志和专业网站雨后春笋般地从无到有,规模由小到大。如今,支持向量学习已成为机器学习的主流技术之一。不夸张地说,就像信息论为信息技术的崛起开辟道路一样,统计学习理论带来了机器学习领域一场深刻变革。支持向量机本质上是一种非线性数据处理方法。与传统的人工神经网络不同,后者基于“经验风险最小化原理”,前者基于“结构风险最小化原理”。“结构风险最小化原理”建立在严谨的数学理论基础之上,令人耳目一新,使人们对学习机的认识发生了深刻变化。支持向量机具有以下显著特征。(1)结构简单。(2)凸优化问题。有关的优化问题无局部极小点。(3)稀疏表示。最优分离超平面之法向量w是训练样本的线性组合,每个样本的系数在某种意义上反映了该样本的重要性。分类问题的有用信息全部包含在系数不为零的那些样本即支持向量中。如果从训练集中去掉非支持向量,或使其在原来位置附近有微小偏移,则重新训练后,所得最优超平面与原来相同。即问题的解仅与支持向量有关。(4)模块化。它清楚地分成两个模块:一个通用的学习机和与具体问题有关的核函数。这使我们能够把设计一个好的学习算法和设计一个好的核函数分开来研究。这种模块化处理方法便于理论分析和工程实现。(5)本质上是线性学习机。它是核函数诱导的(隐含的)特征空间上的线性函数,因而便于理论分析。支持向量机体现了以下重要思想和方法。(1)边缘最大化思想。通过最优超平面来构造判决函数,实现了“结构风险最小化原理”,避免了对训练集过度拟合,保证了支持向量机的泛化能力。(2)对偶表示。在对偶表示中训练数据仅以内积形式出现,因此可以用核函数来代替内积。(3)核方法。从线性分类器转变成非线性分类器,只需要以核函数替换原来的内积。除此之外,原来的线性算法保持不变,线性分类器的全部优点都被继承下来,如计算简单、无局部极小点等。通过核函数能够在输入空间间接地完成高维特征空间(具有更丰富的结构)中的操作,计算复杂度没有实质性增加,但解决了复杂函数的表示问题。引进核函数之后,特征空间的维数变得不再重要了,甚至不必知道特征映射的具体形式,避免了维数灾难。通过改变核函数,可以得到不同的分类器。支持向量机最初是用来解决分类问题的,其思想和方法后来被拓展到其他领域,如回归分析、函数逼近、密度估计,还有主成分分析、K-近邻、费歇判决等。核方法也发展成了一种方法论,把许多重要的数据处理方法纳入统一的框架,开辟了更加宽广的研究天地。本文仅研究用来分类的支持向量机。支持向量机并非尽善尽美,作为发展中的机器学习技术,还有很多问题有待解决。例如,1.训练算法支持向量机的训练归结为求解二次规划问题,但该问题的Hessian矩阵通常是稠密的,处理大规模问题时存储代价很高。例如,当样本个数为50000时,Hessian矩阵元素个数达25亿之巨,普通计算机的内存根本不够用。所以,经典的优化方法不适用,开发耗时短且占用内存少的算法成为人们追求的目标。训练算法又可以分为线性SVM训练算法与非线性SVM训练算法、在线算法与离线算法、精确算法与近似算法等。训练算法一直是最活跃的研究课题。2.模型选择模型选择是指:对于具体问题,如何选择核函数,以及支持向量机中的一些参数。这些参数包括:惩罚系数c,它在训练误差与泛化能力之间进行平衡;核函数中的参数,如高斯核中的σ和多项式核中的p等,不同的参数对应着不同的特征空间和特征映射,它们与支持向量机的泛化能力密切相关。怎样自动地进行模型选择?3.知识嵌入所谓知识,是指除训练样本外的信息,如问题领域的专业知识,专家经验等。标准的支持向量机是基于训练样本的,隐含的特征映射使得嵌入知识很困难。但经验告诉我们,一个系统所含知识的多少,对知识的利用程度如何,反映了其能力的高低。这在解决具体问题时尤其重要,但SVM还没有从根本上解决嵌入领域知识的问题。4.多类问题最初,SVM是针对二分类问题的,但实际应用中常常是多类问题。如何把它推广到多类问题?多类问题训练集的规模通常很大,如何有效地训练?我的论文就是围绕这些问题开展研究。论文的主要贡献是:(1)提出“有附加信息的统计学习理论框架”。经典统计学习理论的重要结论,都是假设训练样本服从某个固定分布,或者服从任意分布,这是两个极端情形。实际情况是,人们对所处理的问题不全了解,但又知道一部分信息,这个新框架能够描述这种情况(见第二章)。(2)分六个专题,即支持向量机训练算法、支持向量机的各种表现形式、支持向量机的泛化能力、模型选择、多类问题和支持向量机的应用,系统地论述了(分类)支持向量机的研究进展(见第三章)。(3)提高支持向量机性能的关键,是设计适合特定问题的核函数,这要求对核函数本身有深入了解。针对三类重要核函数,即平移不变核函数、旋转不变核函数和卷积核,提出了简单易用的判别准则,并给出数学证明(见第四章)。(4)支持向量机的优势在于处理非线性问题,但设计大规模、非线性支持向量机训练算法比较困难。本文深入研究了NPA算法,分析了该算法存在的不足,对第一、第二类检验下的迭代过程做了实质性改进。实验结果表明,新版本性能稳定,在未增加计算代价的条件下,训练速度明显提高(见第五章)。(5)利用本文设计的训练算法,开发了一个自动分类模拟系统(见第六章)。论文共分七章,具体组织如下:第一章,什么是支持向量机。本章由三部分构成。第一部分阐述什么是支持向量机,先从简单的线性分类器入手,然后推广到更复杂的情况。第二部分概括了支持向量机的特征和重要思想。第三部分简要分析支持向量机与传统神经网络的异同。第二章,支持向量机的理论基础。本章用严谨、精炼的语言描述了统计学习理论的概貌,它与支持向量机的关系。在此基础上,提出一个“有附加信息的统计学习理论框架”。第三章,支持向量机研究进展。本章分六个专题,即训练算法、支持向量机的各种表现形式、支持向量机的泛化能力、模型选择、多分类问题和支持向量机的应用,综述支持向量机的研究进展,涵盖了迄今为止主要的研究内容和成果,从中可以了解人们所研究的问题、所付出的努力、所取得的成就和所面临的困难。第四章,核函数的性质及其构造方法。支持向量机由核函数与训练集完全刻画。提高支持向量机性能的关键之一,是设计适合特定问题的核函数,这就要求对核函数本身有深入了解。本章由四部分组成:第一部分论述核函数与正定矩阵的关系及核函数的基本性质。第二部分对三类重要核函数,即平移不变核、旋转不变核和卷积核,提出了简单实用的判别准则,并在此基础上构造了很多重要核函数。第三部分介绍了一种自适应核函数。第四部分指出把问题领域的知识与核函数设计联系起来,即通过设计特殊的核函数来嵌入领域知识,是今后努力的方向。第五章,加速NPA算法的收敛。支持向量机的优势在于处理非线性问题,但设计大规模、非线性支持向量机训练算法比较困难。1998年Platt提出的SMO算法(Sequential Minimal Optimization),和2001年Keerthi等人提出的NPA算法(Nearest Point Algorithm)是目前常用的。NPA算法有明确的几何背景,与SMO相比训练速度毫不逊色,并且在惩罚系数较大时有显著优势。本章分析了NPA算法存在的不足,对其第一、第二类检验下的迭代过程做了实质性改进。实验结果表明,新版本性能稳定,在未增加计算代价的条件下,训练速度明显提高。第六章,支持向量机自动分类模拟系统。本章根据第五章设计的算法,开发了一个自动分类模拟系统,它由三个主要模块构成,介绍了系统界面、系统功能,给出了关键代码。其核心模块很容易嵌入到实用系统中。第七章,存在的问题与今后的研究方向。总结了支持向量机研究中有待解决的关键问题,对今后的研究重点提出建议。