（计算机科学与技术专业论文）基于最大化间隔的核谱学习分类算法.pdf

、 t 独创性声明 删 y 1 7 8 鲥 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：刭函鱼亟日期：2 丛竺! ! 幺廛 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：j 登蟑导师签名：二算蚴日期：互虹巡 仅要使用己标记样本，还要有效利用无标记样本。 为了解决传统算法所存在的不足之处，本文提出了一种新的半监督核谱学习算 法( s p e c t r a lk e r n e ll e a r n i n gb a s e do nm a x i m i z i n gm a r g i n ，m s k l ) 。算法同时利 用标记数据和无标记数据来学习新的核矩阵，并且采用一种更有效的泛化性能的度 量标准，能有效改善算法的分类性能。 本文的工作主要包含以下两个方面： 一是提出一种新的核谱学习算法。本文算法通过最优化泛化性能度量标准来修 改核矩阵的谱值。算法采用最大化两类数据的间隔的方式来学习新的核矩阵。比较 传统的度量标准，如目标核适合度( k e r n e lt a r g e ta l i g n m e n t ) ，分类间隔被认为是 一种更合适的度量标准。此外，本文算法是基于标准核函数来学习新的核矩阵，而 不是图核。最后算法可以被转换成一个非线性的最优化问题。使用梯度下降算法和 拉格朗日支撑向量机能够有效地求解这个最优化问题。 二是在五个公共数据集上进行实验来评估本文提出的核谱学习算法的分类性 能。实验将本文提出的算法与基于标准核函数的传统分类算法以及基于目标核的核 谱学习算法进行比较。实验结果表明本文算法比其他两种传统算法更加有效。 关键词分类；核方法；核谱学习；模式识别 i i n i a b s t r a c t a bs t r a c t k e r n e l b a s e dl e a r n i n ga l g o r i t h m sa r en e wa n d i m p o r t a n tt e c h n i q u e sf o rc l a s s i f i c a t i o n a n dh a v eb e e nw i d e l ys t u d i e dr e c e n t l y t h e ya r eu s e di np a t t e mr e c o g n i t i o n ，i m a g e p r o c e s s i n ga n dm a n yo t h e rf i e l d s t r a d i t i o n a lk e r n e lm e t h o d su s u a l l yu s et h es t a n d a r d k e r n e l ，s u c ha sl i n e a rk e r n e la n dr b fk e r n e l ，s ot h e ym a yn o tg o o de n o u g ht oc l a s s i f yt h e d a t a s e tc o r r e c t l y o nt h eo t h e rh a n d , t r a d i t i o n a lm e t h o d sa r eu s u a l l yi nas u p e r v i s e d l e a r n i n gw a y , w h i c ho n l yu s et h el a b e l e dd a t af o rt r a i n i n g ag o o dk e r n e lm e t h o ds h o u l d t a k ea d v a n t a g e so nn o to n l yt h el a b e l e dd a t a , b u ta l s ot h eu n l a b e l e dd a t a i no r d e rt os o l v et h es h o r t c o m i n g so ft h et r a d i t i o n a lk e r n e lm e t h o d s ，w ep r o p o s ea n o v e ls e m i s u p e r v i s e ds p e c t r a lk e m e ll e a r n i n gm e t h o dt ol e a r n i n gan e wk e r n e lm a t r i x w i t hb o t hl a b e l e dd a t aa n du n l a b e l e dd a t ai nt h i sp a p e r o u rm e t h o du s em o r ee f f e c t i v e g e n e r a l i z e dp e r f o r m a n c em e a s u r ea n di t c a ni m p r o v et h ea c c u r a c yo fc l a s s i f i c a t i o n e f f e c t i v e l y t h i sp a p e r sc o n t r i b u t i o nm a i n l yc o n c e n t r a t e so nt h ef o l l o w i n gt w op a r t s ： f i r s t ，w ep r o p o s ean o v e ls p e c t r a lk e r n e ll e a r n i n gm e t h o d o u rm e t h o dt u n e st h e s p e c t r a lo fk e r n e lm a t r i xt h r o u g ho p t i m i z i n gs o m eg e n e r a l i z e dp e r f o r m a n c em e a s u r e s t h i sm e t h o dl e a r n san e wk e r n e lm a t r i xb ym a x i m i z i n gt h em a r g i nb e t w e e nt w oc l a s s e d o fd a t a , w h i c hi sj u s t i f i e da sam o r ee s s e n t i a ls e m i - s u p e r v i s e dk e r n e ll e a r n i n gm e a s u r e t h a no t h e r s ，s u c ha sk e r n e lt a r g e ta l i g n m e n t i na d d i t i o n ，o u rm e t h o da r eb a s e do nt h e s t a n d a r dk e r n e l ，n o tt h eg r a p hk e r n e l t h e n ，o u ra p p r o a c hc a l lb et u m e di n t oan o n l i n e a r o p t i m i z a t i o np r o b l e m w eu s el a g r a n g i a ns u p p o r tv e c t o rm a c h i n e sa n dg r a d i e n td e s c e n t a l g o r i t h mt o g e t h e rt os o l v eo u ro p t i m i z a t i o np r o b l e me f f i c i e n t l y s e c o n d ，w ee v a l u a t et h ep e r f o r m a n c eo fo u rs p e c t r a lk e r n e ll e a r n i n ga l g o r i t h mf o r c l a s s i f i c a t i o no nf i v ed a t a s e t s w ec o m p a r eo u rm e t h o dw i t ht h et r a d i t i o n a lk e r n e lm e t h o d w i t ht h es t a n d a r dk e r n e l sa n ds p e c t r a lk e r n e ll e a r n i n gb a s e do nk e r n e lt a r g e ta l i g n m e n t e x p e r i m e n t a lr e s u l t ss h o wt h a to u rm e t h o di sm o r ee f f e c t i v ef o rc l a s s i f i c a t i o nt h a n t r a d i t i o n a la p p r o a c h e s k e y w o r d sc l a s s i f i c a t i o n ；k e m e ll e a r n i n g ；s p e c t r a lk e r n e ll e a r n i n g ；p a t t e mr e c o g n i t i o n 1 1 1 i v 一 日录 目录 摘要i a i b s t r a e t i i i 第1 章绪论1 1 1 研究背景1 1 2 核方法的研究进展2 1 3 研究的内容及意义5 1 4 本文结构5 第2 章核方法的理论基础7 2 1 引言7 2 2 统计学习理论7 2 2 1 学习问题的表示7 2 2 2 学习过程的一致性理论8 2 2 3 学习机推广性的界1 0 2 2 4 控制学习过程的泛化能力1 1 2 2 5 构造学习算法1 1 2 3 核函数1 2 2 3 1 核函数定义1 2 2 3 2 核函数性质1 3 2 3 3 常用核函数1 4 2 4 本章小结1 4 第3 章模式识别的核方法1 5 3 1 引言1 5 3 2 监督学习方法1 6 3 2 1 支撑向量机1 7 3 2 2 核逻辑回归2 l 3 3 无监督学习方法2 2 3 3 1 核k 均值聚类2 3 3 3 2 核模糊c 均值聚类2 4 3 4 半监督学习方法2 7 3 5 主动学习方法2 9 3 6 本章小结3 0 第4 章一种基于最大间隔的核谱学习算法3 1 4 1 引言3 1 4 2 基本原理3 2 北京i 业人：l 。：j 顶卜一f ? ，论之 4 2 1 无监督核设计规则3 2 4 2 2 核学习框架3 4 4 2 3 基于目标核适合度的核谱学习方法3 5 4 3 基于最大间隔的核谱学习问题3 6 4 4l a g r a n g i a n 支撑向量机3 9 4 5m s k l 算法4 1 4 6 本章小结4 3 第5 章m s k l 算法分类性能实验及分析4 5 5 1 引言4 5 5 2 衰退系数w 和维度系数d 的选取4 6 5 3 分类性能试验4 8 5 4 结论5 1 5 5 本章小结5 2 结论5 3 参考文献5 5 攻读硕士学位期间发表的学术论文5 9 致谢6 1 第1 幸绪论 1 i 研究背景 第1 章绪论 随着计算机应用技术和信息化的高速发展，人类获取的数据总量以指数级的速 度在增长，数据获取的速度和存储容量都有了飞速的提高。面对这种情况，人们必 须努力提高自己对数据信息的处理能力。如何有效分析和利用这些大规模数据是目 前计算机研究人员和专家所要面临的共同难题。目前，很多学科试图从不同的方向， 以不同的方式和不同的途径来研究和解释其中的秘密，并且希望构造能够感知、识 别、理解、自学习和有自适应能力的灵活的高效的和智能的学习算法，从大量冗余 的数据中，通过数据挖掘从而提取数据之间的潜在的规律，即称之为“模式”。模 式分析就是从一批数据中寻找普遍关系及发现数据内在规律的过程1 。模式识别有 明确的问题定义、严格的数学基础、坚实的理论框架和广泛的应用价值，获得越来 越多的重视，并且也成为许多学科的中心研究内容之一。 模式识别是一门以应用为基础的学科，它所研究的理论和方法在很多科学和技 术领域中都得到了广泛的重视。模式识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机 的出现，5 0 年代人工智能的兴起，模式识别在6 0 年代初快速发展成为一门学科雎1 。 近些年来，模式识别取得大量成果，有很多成熟的分类算法被提出，在许多的领域 都得到了成功应用。典型的应用包括语音识别、指纹识别、签名认证、文本检索、 表情和手势以及唇语识别等。同时，模式识别也同样要依靠其他学科的发展来不断 改善这些应用，如语言学、计算机图形学、计算机视觉等瞄一1 。 模式识别的发展经历漫长曲折，大体上可以分为以下几个阶段： 首先，上世纪6 0 年代，r o s e n b l a t t 首次提出了感知器的概念瞄1 ，试图模拟动物和 人脑的感知和学习能力。它是一个具有单层计算单元的向前神经网络，可以用于解 决模式识别问题。如何检测非线性关系这一问题，是那个时候的主要研究目标。尽 管如此，开发具有相同效率水平的算法，并且保证算法得到统计理论的支持，已被 证明是个很困难的目标。 其次，随着计算机计算能力的发展和7 0 年代动力系统和非线性的研究，神经网 络的理论与应用取得了重大的突破。1 9 8 2 年，h o p f i e l d 率先提出t h n n 模型m 1 ，引入 了能量函数的概念，有力地推动了神经网络的研究。1 9 8 4 年，h i n t o n 等提出了 b o l t z m a n 机模型盯1 ，它借用了统计物理中模拟退火算法，保证学习过程中收敛到全 北京i 业人学硕卜。位论文 局稳定点。1 9 8 6 年r u m e l h a r t 等提出了多层感知器的反向传播算法( b a c k p r o p a g a ti o n ，b p ) 哺1 。尽管这些方法用到了启发式算法和不完全统计分析，它们第 一次使得检测非线性模式成为可能，激活了诸如数据挖掘和生物信息学的整个领域。 该阶段是神经网络的最活跃阶段，其丰硕成果是这期间其他学习算法所无法与其比 拟的。b p 算法可以说是感知器的第二次飞跃，在此后的阶段，神经网络得到了飞速 的发展，提出了非常多的分类模型，并且在数字识别等应用问题上体现出较好的性 能。但是这些非线性算法也存在这许多难以解决的棘手问题，比如过学习问题、维 数灾难问题、模型的训练问题等等。 模式分析算法发展的第三阶段是基于核的机器学习算法或称核方法( k e r n e l m e t h o dk m ) 。它是基于核技术和统计学习理论建立的，是以所谓支撑向量为主要内 容的一类新的模式识别算法。由于核方法采用了统计学习理论中的结构风险准则， 使其不会遭遇过拟合的问题，因此具有很好的推广能力，同时它也不需要有很多的 训练样本来学习，这样也在一定程度上解决了神经网络中的过拟合和推广能力差的 问题。另一方面，核方法可以使研究人员能够高效地分析非线性问题，并且不必付 出庞大的计算代价就可以达到只有线性算法才能达到的高效率，它在一定程度上避 免了神经网络中维数灾难问题和b a y e s 网络中的网络规模爆炸问题。核技术不仅在微 分方程求解、调和分析等数学学科中有十分巧妙的应用，近些年来在许多模式分析 的应用领域都受到青睐，成为先进模式识别领域的研究重点之一。 1 2 核方法的研究进展 核方法从理论上为模式识别提供了一种系统且有原则的方法。粗略地说，在任 何一种有点积运算的方法中，用核函数来代替点积就可以称作是核方法。核方法把 数据映射到合适的特征空间，然后使用基于线性代数和统计学的方法，发现在此空 间中的模式。具体地说，核方法首先采用非线性映射将原始数据由低维输入空间映 射到高维特征空间，进而在特征空间使用线性学习器进行分类。根据模式可分性理 论，在原有空间中线性不可分的数据在更高维的空间会变得线性可分，如图卜1 所示。 尽管核方法作为模式识别的新方法，在2 0 世纪9 0 年代中期才出现了，但核方法实 际上在数学中是个古老的命题，早在1 9 0 9 年j m e r c e r 在泛函分析中就提出了再生核 ( m e r c e r 核) 和再牛核h i l b e r t 空问呻3 。在1 9 6 4 年，a i z e r m a n 等人率先在学习算法中引 入了核函数的使用，利用核方法来证明学习算法的收敛性n 们。1 9 9 2 年，v a p n i k 等人 通过引入核函数来代替内积，构建了支撑向量机n 。支撑向量机算法大幅提高了分 类性能，引导了一场模式识别的革命，成为当时非线性算法领域的研究热点之一。 第1 审绪论 接下来的十几年间，支撑向量机在文本识别“2 1 3 ，人脸识别n 引、函数拟合n 5 1 6 1 等领域 都取得了很好的效果。 一 图1 1 将数据映射到高维特征空间 f i g 1 - 1m a pd a t as e tt of e a t u r es p a c e 此后，研究人员将核方法推广到更多包含点积运算的算法中，产生了一系列的 核化方法。9 8 年，s c h o l k o p f 等人把核方法进一步引入到主成分分析中，得到了核 成分分析算法n 。随后，m i k a 等人对线性的f i s h e r 笋l j 决准则进行了核化，得到了核 f x s h e r 笋t j 决准则n8 。除此之外还有核最小均方误差( k m s e ) n 卅等等。总之，核方法已 经成功应用于许多实际领域中，并取得了相当不错的效果。 早期的核方法大多是使用传统的核函数进行分类，如线性核( 1 i n e a rk e r n e l ) ， r b f 核( r a d i a lb a s i sf u n c t i o nk e r n e l ) ，多项式核( p o l y n o m i a lk e r n e l ) 等。但随 着核方法的广泛应用，人们发现这些基于传统的核函数的分类方法对于很多复杂任 务的适应能力是非常有限的。针对于这样的问题，研究人员在传统算方法的基础上 做出了很多改进的尝试，并且取得了一定的效果。对于传统核方法的改进大致可以 归纳为几大类。如何选择核函数及其参数以适应复杂多变的分类任务是实际应用中 首先面临的现实问题。近年来，针对这些核化分类算法的改进主要集中在了核参数 的选择上。关于核参数选择问题的研究虽然已经取得了一定的进展，但对于许多复 杂任务的适应能力仍然十分有限艟仉2 k 2 引。造成这个问题的主要原因是目前核参数的选 择主要是靠人工估计，依据经验进行选择，这样做必定存在一定的随意性和局限性。 另外一类改进的方法就是利用对个基本核构造新的核函数用做核优化方法，也称作 多核学习雎3 ，2 m2 5 1 。传统核方法通常是使用了单一且标准的基本核函数，而这类方法对 多数据源或者异构数据集进行分类效果都不是太理想。多核学习能够突破这种局限 性。使用多核组合的核函数，即使不知道最优的核参数，也可以通过调整权值找到 ，。，；，卜 北片ii 、人学i 誓+ 硕十学位沦文 合适的参数，很明显这样做能够有效改善核方法的鲁棒性。多核学习方法通常是先 定义一个学习准则函数，这个准则通常可以用来判断核函数的泛化能力。然后以学 习准则做目标函数构造二次规划问题，通过求解这个最优化问题求解出核参数的最 优系数值。l a n c k i e t 等人在文献 2 3 中，利用多个核函数的凸组合来构造目标核函 数，并通过求解二次规划问题优化目标核。b a c h 等人在文献 2 4 中，针对文献 2 3 对大规模数据处理上的局限，提出了一种二次规划问题的对偶形式。文献 2 5 和文 献 2 6 提出了加速算法用于实现多种基本核的复合。多核学习方法仍然存在有一定 的缺陷，它总是需要众多的已标签样本。因为一部分样本将用来构造依赖数据核， 而另一部分则用来训练。另外，多核学习问题求解也是比较复杂的。 除了上面提到的两类方法之外，还有一类重要的方法称作核谱学习，这也是本 文研究对象。不同于多核学习算法，核谱学习主要是对单一的核函数或者图拉普拉 斯矩阵进行再学习，通过建立相应的数学规划来学习新的核谱，从而得到更加适合 问题本身的核。另外一个不同之处是核谱学习大多采用半监督学习的方式。传统的 核方法多数是采用监督学习的方式，在学习过程中仅仅使用已标记数据进行训练。 当训练样本不充足时，这类方法的分类能力通常会收到很大的影响。在实际应用中， 带标记样本的获取往往是比较网难的，要耗费相当的人力与时间。相反，无标记样 本的数量会比较多，获取也相对容易。如何利用无标记样本带来的额外信息，并以 此提高学习的准确率，是目前核方法研究的热点问题之一。一个好的分类方法不仅 要能有效利用标记数据，还要能有效利用无标记数据。半监督学习就是一种能有效 利用无标记数据的方法。在文献 2 7 和 2 8 中，作者分别归纳总结了许多的半监督 学习方法。至今，许多基于图谱理论的半监督学习算法已被提出口鲫，并且越来越受 到研究者的重视。图的拉普拉斯矩阵算法就是其中最著名的基于核的半监督学习方 法之一m 3 。3 2 1 。在文献 3 2 中，z h u 等提出了一种无参数的基于图的半监督核学习算 法。该算法通过最大化目标核适合度来学习新的谱系数，结合对应的初始图拉普拉 斯矩阵的特征向量得到新的核矩阵。目标核适合度是一个用来度量核矩阵的特征空 间和标记的特征空间的相似性的标准。此后，h o i 等人在 3 3 中对前面的算法做出了 改进，在算法中引入了快速衰退的约束，并且针对标准核函数进行学习。该算法取 得了更好的分类效果。h 标核适合度作为学习准则人存在着一定的局限性，在实际 应用中可能会产生过优化的问题。本文将采有另外一种学习准则来替代目标核适合 度，从而改善算法分类性能。 本文正是以半监督核学习这个研究热点为研究内容，在分析和借鉴了上述诸多 算法和传统方法的优缺点的基础上，提出了新的基于支撑向量机的最大分类间隔的 半监督核学习算法，并在诸多方面对传统方法和上述各算法进行了改进。 第l 尊绪论 1 3 研究的内容及意义 核方法的引入极大提高了学习算法的非线性处理能力，同时也保留了学习算法 在高维空间的内在线性，在许多的领域都得到了广泛的应用。核方法的应用领域涉 及到图像识别、生物识别技术、雷达信号处理、经济分析、信号识别和预测等等。 本文所研究的相关课题能有效改进核方法的分类性能，具有深远的理论意义和现实 意义。 由于在实际应用中传统的核方法对于许多的分类任务的适应能力都十分有限， 许多的研究者提出了各种各样的改进方法，包括核参数优化、多核学习和核谱学习 等等。与传统方法相比，这些方法在对复杂数据的适应性上有了一定的改善，但是 还都存在着一些缺陷。本文在传统核方法和改进方法的基础之上，提出了一种新的 核方法。该算法基于单一标准核函数进行学习，选择更有效的学习准则来构造优化 问题，并且能被方便快速的求解。 本文的主要工作有以下几个方面： 一是提出一种新的核谱学习算法。算法使用最大化两类数据的间隔的方式来学 习新的核矩阵。比较传统的度量标准，如目标核适合度( k e r n e lt a r g e ta l i g n m e n t ) ， 分类问隔被人文是一种更合适的度量标准。此外，本文算法是基于标准核函数来学 习新的核矩阵，而不是图核。算法最后可以被转换成一个非线性的最优化问题。使 用梯度下降算法和拉格朗日支撑向量机能够有效地求解这个最优化问题。 二是在公共数据集上进行实验来评估本文提出的核谱学习算法的分类性能。实 验将本文提出的算法与基于标准核函数的传统分类算法以及基于目标核适合度的核 谱学习算法进行比较。实验结果表明本文算法比其他两种传统算法更加有效。 1 4 本文结构 本文主要提出了一种新的基于分类间隔的核学习算法，并从理论和实验上论证 了该方法的优越性。 本文的组织结构如下： 第1 章是绪论。介绍了课题研究的背景以及本文的主要工作。 第2 章对介绍课题主要涉及的一些基本理论知识，包括统计学习理论和核方法理 论。 第3 章按学习方式对核方法进行分类，分析每类学习方法的研究现状以及发展趋 一 北京【：业大i 学硕十学f 讧论文 势。 第4 章在分析半监督学习理论的基础之上，提出了一种新的基于最大间隔的半监 督学习算法。 第5 章对本文提出的算法进行了分类准确度实验，并对实验结果进行了分析。 最后的部分是对整个论文的主要研究工作和创新的总结，并对在该研究方向将 来的研究方向和工作重点进行了展望。 第2 等核疗法的理论垦础 2 1 引言 第2 章核方法的理论基础 本章主要介绍论文研究的课题所涉及到的基本概念和理论，包括统计学习理论 和核方法的概要。统计学习理论为解决小样本的模式分类问题提供了一个统一的坚 实的理论基础。核方法则讨论了核函数定义与性质，再生核理论与m e r c e r 定理，常 用的核函数等等。上述内容是本文后面算法研究的理论基础，在许多内容的叙述中 融入了一些学习体会以及相关讨论。 2 2 统计学习理论 传统的统计学所研究的主要问题是渐进理论，即当样本趋向无穷多时的统计性 质。而在现实问题中，给定的样本数目往往是有限的。统计学习理论正是一种专门 针对小样本统计估计和预测学习的统计理论。该理论早在2 0 世纪六七十年代就被提 出，直到9 0 年代中期才发展成熟，并提出了将这一理论付诸实施的较好方法。它对 传统统计学进行了发展和补充，丰要研究经验风险最小化成立的条件、有限样本下 经验风险和期望风险的关系以及如何寻找新的学习准则和方法等问题。其涉及的主 要内容包括五个部分： 1 ) 在基于经验数据最小化风险泛函的模型基础上对学习问题的表示； 2 ) 学习过程的一致性理论 3 ) 用风险最小化原则得到的风险的非渐近界； 4 ) 控制学习过程的推广能力的理论； 5 ) 实现新原则的实际算法。 2 2 1 学习问题的表示 首先给出基于样本数据的学习问题的形式： 1 ) 随机采样的样本向量x r j ，服从未知的分布函数p ( x ) ； 8 第2 章饮 j - 法的理沦坫础 意义下一致收敛于真实风险r ( 口) 。其中，尸表示概率。这种收敛称作一致单边收 敛。 这条定理也被称作统计学习理论的关键定理。定理将学习一致性问题转化为公 式2 - 4 中的一致收敛问题。由于在学习过程中，经验风险和期望风险都是预测函数的 泛函。我们的目的不是用经验风险玄逼近期望风险，而是通过使用最小化经验风险 的函数去逼近最小化期望风险的函数。学习过程一致性的条件取决于函数集中最差 的函数。因此一致性条件要比传统统计学中的一致性条件更加严格。 针对学习过程一致性条件以及渐进收敛速度的问题，v a p n i k 等人提出了三个十 分重要的定理。这三个定理构成了建立学习机收敛速度的界的基础。 定理2 2 ：对于函数集 三( y ，s ( x ，口) ) l 口q ，学习机器学习过程双边一致收敛 p k ( r ( 口) 一足。，( 训 s j 之0 ，v g o ( 2 - 5 ) 的充要条件是 h n ( 1 ) jo( 2 6 ) z f _ 。 其中，日n ( ，) 表示函数集在观测样本上的v c 熵。 定理2 - 3 ：学习机器学习过程收敛速度快的一个充分条件是 丝也专o( 2 7 ) ， f - 。 其中，h 。a n 。( z ) 为观测样本的退火的v c 熵。 定理2 - 4 ：对于任何概率测度，e r m 原则都具有一致性的充要条件是 竺盟专o( 2 8 ) ， i - - - q o 并且该条件是学习过程快速收敛的一个充分条件。其中g n ( ，1 表示函数集的生长函 数。 依据定义，v c 熵，退火的v c 熵及生长函数之间满足一个关系：对于任何函数集 的观测样本数，h q ( ，) 砩。( ，) g n ( ，) 都成立。上面的三个定理给出满足e r m 原则 的一致性及保证快速收敛的条件，但是其程度的各不相同。由于在前两个定理中， 概率测度p 未知，不能有效地构造v c 熵h q ( ，) 和退火v c 熵硼。( ，) ，所以缺乏实用性。 定理2 - 4 是学习理论中一个极为重要的定理，它所描述的保证e r m 原则一致性并且快 速收敛的条件与所用的概率测度无关。它是下面将要讨论的问题的基础。 此j ：il 业人：li 7 硕十学位论文 2 2 3 学习机推广性的界 v a p i n k 等人在7 0 年代初提出了一个统计学习理论中的重要概念v c 维。它是反映 函数集学习能力的重要指标。 定义2 - 1 ：v c 维 对于指示函数集来说，如果可以按照全部2 的h 次幂中形式把h 个样本分开，则 称函数集能把h 个样本打散( s h a t t e r i n g ) ，h 的最大值被称为函数集的v c 维。若对 任意数目的样本都有函数将它们打散，则函数集的v c 维为无穷大。对于有界的实函 数集，可以构造与它对应的指示函数值，指示函数集的v c 维值即为对应的实函数集 的v c 维。 生长函数与v c 维存在着如下关系： f = l l n 2，h g n ( 刮 - 0 对所有厂厶( x ) ( 2 一1 3 ) 则称函数k ( x ，x ) 为半正定的核函数。若在离散情况下，令x = 五，) 为非空 数据集合，誓r j ，常数c r r v r = 1 ，聆。对称函数k ：x xx 专r 被称为有限半 正定核或核函数当且仅当满足下面等式： c f 勺尼( 玉，巧) o ，v 刀2 ， 卢l 户i 定义2 3 ：核矩阵给定一个样本集s = x 1 , x ：，x 。) 以及核函数尼( 誓，) ，g r a m 第2 争孩厅法的耻论丛础 矩阵被定义为n n 的矩阵k ，其元素巧= ( 矽( x ，) ，矽( x ，) ) = 七( x f ，x ，) 。其中，矽表示对 应于核函数k 的特征映射，这个矩阵被称为核矩阵或g r a m 矩阵。可以证明核矩阵是 半正定矩阵。 根据m e r c e r 定理，核函数可以表示为内积形式：后( 薯，) = 矽“) ( ) ，其中 矽：x 专f ，是输入空间x 到高维特征空间肭映射。满足_ m e r c e r 条件或者粗略满足正 定性的核函数称为m e r c e r 容许核( 或者再生核) 。根据m e r c e r 容许条件还可以从已知 的核函数构造出新的核函数，包括乘积核、积分核、平移不变核后( 工，y ) = k ( x - y ) 、 点积核尼( x ，y ) - - k ( 0 是用来权衡损失函数和函数复杂 度的权衡系数( t r a d e o f fp a r a m e t e r ) 。 许多的监督核方法都是基于上面的正则化学习框架。根据正则化问题( 3 - 1 ) 中的 元素的不同定义，分别发展出一下不同的监督核学习方法。 1 正则最小二乘网络( r l s ) ： 第3 尊模识刖的 幺，j 。法 ( 厂( 五) ，咒) = ( 厂( 薯) 一 ) 2 2 支撑向量回归( s v m r ) 三( 厂( 誓) ，乃) = ( 咒一厂( t ) ) 。 3 支撑向量机分类( s v m c ) 三( 厂( _ ) ，y i ) = ( 一厂( 五) ) + 下面将介绍两个典型的监督核学习算法，支撑向量机和核l o g i s t i c 回归。 3 2 1 支撑向量机 ( 3 - 2 ) ( 3 - 3 ) ( 3 - 4 ) 支撑向量机是建立在统计学习理论基础上的一种有效的基于核的模式分析方 法。支撑向量机的学习问题就是在线性空间中，寻找分类超平面。该平面首先将两 类数据正确地分开，其次使得样本到分类平面的距离尽可能的大。根据统计学习理 论，前一个性质保证了经验风险最小化，后面的性质办证了较小的置信空间。支撑 向量机在有限样本、非线性、高维的模式分类问题中表现出了独有的优势，能够避 免局部最优的问题。本小节中将要简要介绍支撑向量机模型，它是贯穿我们全文的 基本模型。 首先考虑线性可分情况。在线性空间中，分类超平面的一般形式为： ( x