模式分析的核方法

·本书既提供了大量的实用算法帮助应用者解决各种领域的实际问题，又是一本供学生和科研人员初学模式分析中核方法的入门导论。

·两位英国科学家作者是国际上极富盛名的人工智能专家。

　　模式分析是从一批数据中寻找普遍关系的过程。它逐渐成为许多学科的核心，从生物信息学到文档检索都有广泛需求。本书所描述的核方法为所有这些学科提供了一个有力统一的框架，推动了可用于各种普遍形式的数据（如字符串、向量、文本等）的各种算法的发展，还可用于寻找各种普遍的关系类型（如排序、分类、回归和聚类等）。书中提供了大量算法、核函数和具体解决方案供各种实际问题选择使用。书中描述了各种核函数，从基本的例子到高等递归核函数，从生成模型导出的核函数（如HMM）到基于动态规划的串匹配核函数，以及用于处理文本文档的特殊核函数等。本书适用于所有从事人工智能、模式识别、机器学习、神经网络及其应用的学生、教师和研究人员，也可供相关领域的科研人员参考。

约翰·肖·泰勒（John Shawe-Taylor）目前是英国伦敦大学学院联合国教科文组织人工智能讲席教授，并担任计算机科学系系主任和计算统计和机器学习中心主任。他还协调组织了多个机器学习欧洲联合研究项目，比如NeuroCOLT（“神经计算学习”）项目和PASCAL（“模式分析、统计建模与计算学习”）项目。

内洛·克里斯蒂安尼尼（Nello Cristianini）目前是英国布里斯托尔大学计算机科学系的人工智能教授。他获得过英国皇家学会沃尔夫森杰出研究成就奖和欧洲研究理事会高阶研究基金奖。2014年他被汤森路透列入2002至2012十年间具影响力的科学家名单，2016年被AMiner列入机器学习领域具影响力的百位研究者名单。

Preface

Part I. Basic Concepts

1. Pattern analysis

2. Kernel methods: an overview

3. Properties of kernels

4. Detecting stable patterns

Part II. Pattern Analysis Algorithms

5. Elementary algorithms in feature space

6. Pattern analysis using eigen-decompositions

7. Pattern analysis using convex optimisation

8. Ranking, clustering and data visualisation

Part III. Constructing Kernels

9. Basic kernels and kernel types

10. Kernels for text

11. Kernels for structured data: strings, trees, etc.

12. Kernels from generative models

Appendix A. Proofs omitted from the main text

Appendix B. Notational conventions

Appendix C. List of pattern analysis methods

Appendix D. List of kernels

References

　　The study of patterns in data is as old as science. Consider，for example，the astronomical breakthroughs of Johannes Kepler formulated in his three famous laws of planetary motion. They can be viewed as relations that he detected in a large set of observational data compiled by Tycho Brahe.
　　Equally the wish to automate the search for patterns is at least as old as computing. The problem has been attacked using methods of statistics，machine learning，data mining and many other branches of science and en-gineering.
　　Pattern analysis deals with the problem of （automatically） detecting and characterising relations in data.Most statistical and machine learning meth-ods of pattern analysis assume that the data is in vectorial form and that the relations can be expressed as classification rules，regression functions orcluster structures，these approaches often go under the general heading of 'statistical pattern recognition'.cSyntactical' or 'structural pattern recogni-tion' represents an alternative approach that aims to detect rules among，for example，strings，often in the form of grammars or equivalent abstractions.
　　The evolution of automated algorithms for pattern analysis has undergone three revolutions. In the 1960s efficient algorithms for detecting linear rela-tions within sets of vectors were introduced. Their computational and sta-tistical behaviour was also analysed. The Perceptron algorithm introduced in 1957 is one example. The question of how to detect nonlinear relations was posed as a major research goal at that time. Despite this developing algorithms with the same level of efficiency and statistical guarantees has proven an elusive target.
　　In the mid 1980s the field of pattern analysis underwent a 'nonlinear revo-lution' with the almost simultaneous introduction of backpropagation multi layer neural networks and efficient decision tree learning algorithms. These approaches for the first time macle it possible to detect nonlinear patterns，albeit with heuristic algorithms and incomplete statistical analysis.The impact of the nonlinear revolution cannot be overemphasised： entire fields such as data mining and bioinformatics were enabled by it. These nonlinear algorithms，however，were based on gradient descent or greedy heuristics and so suffered from local minima. Since their statistical behaviour was not well understood，they also frequently suffered from overfitting.
　　A third stage in the evolution of pattern analysis algorithms took place in the mid-1990s with the emergence of a new approach to pattern analy-sis known as kernel-based learning methods that finally enabled researchers to analyse nonlinear relations with the efficiency that had previously been reserved for linear algorithms.Furthermore advances in their statistical analysis made it possible to do so in high-dimensional feature spaces while avoiding the dangers of overfitting. From all points of view，computational，statistical and conceptual，the nonlinear pattern analysis algorithms devel-oped in this third generation are as efficient and as well founded as linear ones.The problems of local minima and overfitting that were typical of neural networks and decision trees have been overcome. At the same time，these methods have been proven very effective on non vectorial data，in this way creating a connection with other branches of pattern analysis.
　　Kernel-based learning first appeared in the form of support vector ma-chines，a classification algorithm that overcame the computational and sta-tistical difficulties alluded to above. Soon，however，kernel-based algorithmsable to solve tasks other than classification were developed，making it in-creasingly clear that the approach represented a revolution in pattern analy-sis.Here was a whole new set of tools and techniques motivated by rigorous theoretical analyses and built with guarantees of computational efficiency.
　　Furthermore，the approach is able to bridge the gaps that existed be-tween the different subdisciplines of pattern recognition. It provides a uni-fied framework to reason about and operate on data of all types be they vectorial，strings，or more complex objects，while enabling the analysis of a wide variety of patterns，including correlations，rankings，clusterings，etc.
　　This book presents an overview of this new approach. We have attempted to condense into its chapters an intense decade of research generated by a new and thriving research community. Together its researchers have created
　　a class of methods for pattern analysis，which has become an important part of the practitioner's toolkit.