模式分析是从一批数据中寻找普遍关系的过程。它逐渐成为许多学科的核心，从神经网络到所谓句法模式识别，从统计模式识别到机器学习和数据挖掘。模式分析的应用覆盖了广泛领域，从复杂的生物信息学到相对简单的文档检索等。
　　本书所描述的核方法为所有这些学科提供了一个有力的和统一的框架，推动了可以用于各种普遍形式的数据 (如字符串、向量、文本等) 的各种算法的发展，并可以用于寻找各种普遍的关系类型 (如排序、分类、回归和聚类等)。本书有两个主要目的。首先，为专业人员提供了一个包容广泛的工具箱，其中包含各种易于实现的算法、核函数和解决方案。许多算法给出了MATLAB编码，可适用于许多领域的模式分析任务。其次，为学生和研究人员提供了一个方便的入门向导，帮助他们了解基于核的模式分析这个发展迅速的领域。书中举例说明了如何针对新的特定应用手工写出一个算法或核函数，同时还给出了为完成此任务所需的初步方案及数学工具。
　　本书分三部分。第一部分介绍了这个领域的基本概念，书中不仅给出了一个展开的入门例子，而且还阐述了这种方法的主要理论基础。第二部分包含了若干基于核的算法，从最简单的到较复杂的系统，例如核偏序最小二乘法、典型相关分析、支持向量机、主成分分析等。第三部分描述了若干核函数，从基本的例子到高等递归核函数、从生成模型导出的核函数 (如HMM) 到基于动态规划的串匹配核函数，以及用于处理文本文档的特殊核函数。

无

对数据模式的研究与科学研究一样有非常漫长的历史。例如，考虑一下在天文学上取得重大突破的约翰尼斯·开普勒（Johannes Kepler），他阐明了著名的三大行星运动定律，我们可以把这三个定律看做是开普勒从第谷·布拉赫（Tycho Brahe）编纂的大量的观测数据中发现的关系。
　　同样地，对于自动搜索模式的期望的历史至少与计算一样漫长。人们运用许多科学方法和工程方法，比如统计学、机器学习和数据挖掘等等，已在着手处理这个问题了。
　　模式分析（pattern analysis）处理的是（自动）检测和辨别数据中的关系这一问题。在模式分析领域，大多数统计方法和机器学习方法都假定，数据以向量形式存在，关系可以被表达成分类规则、回归函数或者聚类结构；人们通常把这些方法统称为“统计模式识别”。“句法模式识别”或者“结构模式识别”则代表了另外一种方法，其目的是从诸如串之类的数据中检测规则，这些规则往往按照语法或等价的抽象形式存在。
　　模式分析自动化算法的发展，经历了3次革命。20世纪60年代，引入了在向量集内检测线性关系的高效算法，并分析了这些算法的计算行为和统计行为。1957年引入的感知机(Perceptron)算法就是一个例子。如何检测非线性关系这一问题，是那个时候的主要研究目标。尽管如此，开发具有相同效率水平的算法，并且保证该算法得到统计理论的支持，已被证明是一个很困难的目标。
　　20世纪80年代，模式分析领域经历了一场“非线性革命”，几乎同时引入了后向传播多层神经网络算法和高效的决策树学习算法。尽管这些方法用到了启发式算法和不完全统计分析，它们第一次使得检测非线性模式成为可能。非线性革命的影响怎么强调都不过分：它激活了诸如数据挖掘和生物信息学的整个领域。然而，这些非线性算法，是建立在梯度下降法或贪心启发式法的基础上，因而受到局部极小化的限制。由于没有很好地理解它们在统计上的行为，人们利用这些算法时还经常遇到过度拟合的问题。
　　模式分析算法发展的第三个阶段发生在20世纪90年代中期，当时出现了新的被称为基于核的(kernelbased)学习方法的模式分析方法，该方法最终使得研究人员能够高效地分析非线性关系，而这种高效率原先只有线性算法才能够达到。该方法在统计分析方面进一步发展之后，在高维特征空间内也能够达到很高的效率，并且避免了过度拟合的危险。从各种角度，计算的、统计的和概念的角度来看，在这第三个阶段发展起来的非线性模式分析算法，和线性算法一样，高效而富有理论根据。神经网络和决策树中典型的局部极小化问题和过度拟合问题，也已得到解决。同时，这些方法在处理非向量型数据方面非常有效，这样就建立起了和模式分析的其他分支的联系。
　　基于核的学习方法，首先以支持向量机（Support Vector Machine，SVM）的形式出现，支持向量机是一种用来摆脱上面提到的计算和统计上的困难的分类算法。然而，很快就产生了基于核的算法，它能够解决分类以外的问题。人们越来越清楚地认识到，这种方法引起了模式分析领域的一场革命。这里，全部的新工具和新技术，都由严格的理论分析所推动，在计算效率的保证下制造出来或发展起来。
　　此外，这种方法能够消除不同的模式识别子学科之间存在的差距。它提供了一个统一的框架，来思考和操作各种类型的数据，不管它们是向量、串或更复杂的对象，同时也能够进行多种类型的模式分析，包括相关、排列、聚类等等。
　　本书概括地介绍了这种新方法。我们试图把一个年轻的、茁壮成长中的研究团队的10年深入研究，浓缩到本书的章节中。该团队的研究者们已经一起创造了一个模式分析方法类，该类已成为从业人员工具箱的一个重要部分。
　　本书介绍的算法能识别多种关系，从传统的分类和回归问题，到诸如排列和聚类等各种更专门化的问题，到包括主成分分析和典型相关分析的高级技术。而且，每一个模式分析问题，都可以和本书最后一部分论述的核函数库中的一类函数结合起来应用。这就意味着这种分析可以用于多种数据，从标准向量类型，到更复杂的诸如图像和文本文档等对象，到与生物序列、图和语法相关联的高级数据类型。
　　基于核的分析，对于数学家、科学家和工程师来说，是一个强大的新工具。它提供了非常丰富的方法，可以应用在模式分析、信号处理、句法模式识别和其他模式识别（从样条到神经网络）领域。简而言之，它提供了一个崭新的视角，我们仍然远没有了解它的全部潜力。
　　本书作者参与了基于核的学习算法的发展，对于这一方法的理论、实现、应用和普及，做出了许多贡献。他们的著作《An Introduction to Support Vector Machines》已经被许多大学当做教科书和研究参考书使用。作者也在一个由欧洲委员会（European Commission）资助的工作组的机构中，协助“神经和计算学习（NeuroCOLT）”研究，这个工作组在定义新研究日程和“图像和文本的核方法（KerMIT）”项目中起到了重要作用，而该项目已经应用于文档分析领域。
　　作者要感谢很多人，他们通过参加讨论、提出建议，或在许多情况下给予了非常详细和富于启发意义的反馈信息，对本书做出了贡献。特别感谢Gert Lanckriet、Michinari Momma、Kristin Bennett、Tijl DeBie、Roman Rosipal、Christina Leslie、Craig Saunders、Bernhard Scho··lkopf、Nicolò CesaBianchi、Peter Bartlett、Colin Campbell、William Noble、Prabir Burman、JeanPhilippe Vert、Michael Jordan、Manju Pai、Andrea Frome、Chris Watkins、Juho Rousu、Thore Graepel、Ralf Herbrich和David Hardoon。作者还要感谢欧洲委员会和英国基金理事会EPSRC对他们基于核的学习方法的研究的支持。
　　Nello Cristianini是加州大学戴维斯分校（UC Davis）统计系的助理教授。Nello要感谢加州大学伯克利分校（UC Berkeley）的计算机科学系和Mike Jordan，感谢他们在2001年～2002年Nello任访问讲师期间对他的款待。他也要感谢麻省理工学院的基于计算机的学习中心（MIT CBLC）和Tommy Poggio 2002年夏天对他的款待，以及为他提供了理想的环境来写这本书的加州大学戴维斯分校（UC Davis）的统计系。本书的许多结构以Nello在加州大学伯克利分校、戴维斯分校讲授的课程和讲义为基础。
　　John ShaweTaylor是南安普顿大学（University of Southampton）的计算科学教授。John要感谢伦敦大学皇家霍洛威学院（Royal Holloway）计算机科学系的同事们。在写作本书的大部分时间，他都在那里工作。

无

John Shawe-Taylor, Nello Cristianini：John Shawe-Taylor: John Shawe-Taylor 先后在英国剑桥大学、位于斯洛文尼亚的卢布尔雅那大学、加拿大西蒙弗雷泽大学、英国伦敦大学帝国学院、英国伦敦大学皇家豪勒威学院学习。他发表了许多有关学习系统以及离散数学和计算机科学等领域的论文。他是英国南普敦大学计算科学系教授。1986年在伦敦大学皇家豪勒威学院获得博士学位。同时还是由16所大学共同成立的欧洲合作基金的协调者，该基金是为了研究神经学习和计算学习。他的主要研究领域包括：神经网络、机器学习、信息论、算法理论、机器视觉、语言处理、触觉处理等。他还是NeuroCOLT学会欧洲组成员，发表过大量技术论文。
Nello Cristianini: Nello Cristianini 先后在意大利的里雅斯特大学、英国伦敦大学皇家豪勒威学院、英国布里斯投大学、美国加州大学圣克鲁兹分校学习。他是支持向量机与其他学习系统的理论与应用方面卓有成就的年青研究人员，在各种杂志和国际学术会议上发表了许多有关这一领域的论文。

赵玲玲　翁苏明　曾华军　等：暂无简介

模式分析领域研究的是如何发现数据中潜在的关系。随着人们的注意力从线性关系转移到非线性关系，模式分析方法也发生了变化，从最初的统计模式识别，到后来的神经网络和决策树等方法，到本书所讨论的核方法，严格的理论分析推动着新技术的发展和更新。基于核的方法是从统计学习理论中发展出来的较新的研究方法，它有效解决了传统模式识别方法的局部极小化和不完全统计分析的缺点。目前基于核的模式分析方法已经应用于各种类型的数据(不管它们是向量、串或更复杂的对象)，并且能够进行多种类型的数据分析，包括相关、回归、排列、聚类等等。
　　本书是一本综合介绍模式分析的核方法各项标准技术的著作，书中从核函数和基于核的算法的一般原理与性质开始，介绍核函数的特点和性质，接着展开讨论具体的算法，最后引出构造核的技术，其中特别列举了一些适合特定应用的核。本书的叙述循序渐进，内容深入浅出，既不失严谨又易于理解。此外，本书另一大特色是它的配套网站www.kernelmethods.net提供了大量在线参考文献的链接，读者可以很方便地查询到所需的内容。
　　本书作者Nello Cristianini是机器学习领域中的一个活跃的年轻学者，在这一领域的关键杂志和会议上都有数篇文章发表，另一位作者John ShaweTaylor 研究兴趣广泛，著作涉及学习系统理论分析、离散数学和计算机科学等领域。本书可以看做是对他们之前合著的一本书《An Introduction to Support Vector Machines》的综合和深入，它浓缩了一个研究团队在模式分析方面的10年研究成果，为读者进一步学习和掌握最新技术提供了一个理想的起点。
　　译者在翻译过程中力求忠实原著，专业术语尽量遵循各学科的标准。由于水平和时间有限，对原著的理解可能会有偏差，书中不妥之处在所难免，恳请读者批评和指正。
　　本书初稿主要由赵玲玲翻译，曾华军负责审阅，翁苏明对全书进行了修改和整理。另外，肖嵘、陈正、张本宇、林晨曦、薛荣贵、孙建涛、韩捷、韩定一也进行了部分书稿翻译和修改工作。最后，特别感谢李江红老师和林宙辰老师所给予的鼓励和支持。

无

第一部分　基 本 概 念
第1章　模式分析
　11　数据中的模式
　　111　数据
　　112　模式
　12　模式分析算法
　　121　模式的统计稳定性
　　122　通过重新编码检测模式
　13　利用模式
　　131　整体的策略
　　132　常见模式分析任务
　14　小结
　15　进一步阅读和高级主题
第2章　核方法概要
　21　概述
　22　特征空间中的线性回归
　　221　原始线性回归
　　222　原始岭回归和对偶岭回归
　　223　由核定义的非线性特征映射
　23　其他例子
　　231　算法
　　232　核
　24　核方法的模块性
　25　本书的路线图
　26　小结
　27　进一步阅读和高级主题
第3章　核的性质
　31　内积和半正定矩阵
　　311　希尔伯特空间
　　312　Gram矩阵
　32　核的描述
　33　核矩阵
　34　核的构造
　　341　核函数上的运算
　　342　核矩阵上的运算
　35　小结
　36　进一步阅读和高级主题
第4章　检测稳定的模式
　41　集中度不等式
　42　容量和正则化： Rademacher理论
　43　基于核的类的模式稳定性
　44　一种实用的方法
　45　小结
　46　进一步阅读和高级主题

第二部分　模式分析算法
第5章　特征空间中的基本算法
　51　均值和距离
　　511　一种简单的新颖检测算法
　　512　一种简单的分类算法
　52　计算投影： Gram-Schmidt法、QR法和Cholesky法
　53　衡量数据的分散度
　54　Fisher判别式分析Ⅰ
　55　小结
　56　进一步阅读和高级主题
第6章　利用特征分解法做模式分析
　61　奇异值分解
　62　主成分分析
　　621　核主成分分析
　　622　主成分分析的稳定性
　63　最大协方差的方向
　64　广义特征向量问题
　65　典型相关分析
　66　Fisher判别式分析Ⅱ
　67　用于线性回归的方法
　　671　偏最小二乘法
　　672　核偏最小二乘法
　68　小结
　69　进一步阅读和高级主题
第7章　利用凸优化法做模式分析
　71　最小封闭超球体
　　711　包含点集的最小超球体
　　712　新颖检测的稳定性
　　713　包含大部分点的超球体
　72　用于分类的支持向量机
　　721　最大间隔分类器
　　722　软间隔分类器
　73　用于回归的支持向量机
　　731　回归的稳定性
　　732　岭回归
　　733　ε不敏感回归
　74　在线分类和回归
　75　小结
　76　进一步阅读和高级主题
第8章　排列、 聚类和数据可视化
　81　发现排列关系
　　811　批排列
　　812　在线排列
　82　发现特征空间中的聚类结构
　　821　衡量聚类质量
　　822　贪婪解： k均值法
　　823　松弛解： 谱方法
　83　数据可视化　　　
　84　小结
　85　进一步阅读和高级主题

第三部分　构　造　核
第9章　基本的核和核的类型
　91　封闭形式的核
　92　ANOVA核
　93　来自图的核
　94　图结点上的扩散核
　95　集合上的核
　96　实数上的核
　97　随机化核
　98　其他的核类型
　　981　来自连续嵌入的核
　　982　一般结构上的核
　　983　来自生成信息的核
　99　小结
　910　进一步阅读和高级主题
第10章　文本核
　101　从词包到语义空间
　　1011　表示文本
　　1012　语义问题
　102　向量空间核
　　1021　设计语义核
　　1022　设计接近度矩阵
　103　小结
　104　进一步阅读和高级主题
第11章　用于结构化数据的核
　111　比较串和序列
　112　谱核
　113　所有子序列核
　114　固定长度的子序列核
　115　间隙加权的子序列核
　　1151　朴素实现法
　　1152　高效实现法
　　1153　关于主题的变形
　116　动态规划以外的方法： 基于trie树的核
　　1161　p谱核的trie树的计算
　　1162　基于trie树的不匹配核
　　1163　基于trie树的限制性间隙加权核
　117　用于结构化数据的核
　　1171　比较树
　　1172　结构化数据： 一个框架
　118　小结
　119　进一步阅读和高级主题
第12章　来自生成模型的核
　121　P核
　　1211　条件独立和边际化
　　1212　表示多元分布
　　1213　由隐藏二项式模型生成的固定长度的串
　　1214　由隐藏Markov模型生成的固定长度的串
　　1215　配对隐藏Markov模型核
　　1216　隐藏树模型核
　122　Fisher核
　　1221　从概率到几何
　　1222　隐藏Markov模型的Fisher核
　123　小结
　124　进一步阅读和高级主题
附录A　正文中省略的证明
附录B　数学符号约定
索引
参考文献