Kernel methods for pattern analysis / John Shawe-Taylor, Nello Cristianini.

Format:

Book

Author/Creator:

Shawe-Taylor, John.

Contributor:

Cristianini, Nello.

Anne and Joseph Trachtman Memorial Book Fund.

Language:

English

Subjects (All):

Machine learning.

Algorithms.

Kernel functions.

Pattern perception--Data processing.

Pattern perception.

Physical Description:

xiv, 462 pages : illustrations ; 26 cm

Place of Publication:

Cambridge, U.K. ; New York : Cambridge University Press, 2004.

Summary:

Pattern analysis is the process of finding general relations in a set of data, and forms the core of many disciplines, from neural networks to so-called syntactical pattern recognition, from machine learning to data mining. Applications of pattern analysis range from bioinformatics to document retrieval. The kernel methodology described here provides a powerful and unified framework for all of these disciplines, motivating algorithms that can act on general types of data (e.g. strings, vectors, text etc.) and look for general types of relations (e.g. rankings, classifications, regressions clusters etc.)

This book fulfils two major roles. Firstly it provides practitioners with a large toolk it of algorithms kernels and solutions ready to be implemented, many given as Matlab code, suitable for many pattern analysis tasks in fields such as bioinformatics, text analysis and image analysis. Secondly it furnishes students and researchers with an easy introduction to the rapidly expanding field of kernel-based pattern analysis, demonstrating with examples how to hand-craft an algorithm or a kernel for a new specific application, while covering the required conceptual and mathematical tools necessary to do so.

The book is in three parts. The first provides the conceptual foundations of the field, both by giving an extended introductory example, and by covering the main theoretical underpinnings of the approach. The second part contains a number of kernel-based algorithms, from the simplest to sophisticated systems such as kernel partial least squares, canonical correlation analysis, support vector machines, principal components analysis etc. The final part describes a number of kernel functions, from basic examples to advanced recursive kernels, kernels derived from generative models such as HMMs and string matching kernels based on dynamic programming, as well as special kernels designed to handle text documents.

All those involved in pattern recognition, machine learning, neural networks and their applications from computational biology to text analysis will welcome this account.

Contents:

1 Pattern analysis 3

1.1 Patterns in data 4

1.2 Pattern analysis algorithms 12

1.3 Exploiting patterns 17

2 Kernel methods: an overview 25

2.1 The overall picture 26

2.2 Linear regression in a feature space 27

2.4 The modularity of kernel methods 42

2.5 Roadmap of the book 43

3 Properties of kernels 47

3.1 Inner products and positive semi-definite matrices 48

3.2 Characterisation of kernels 60

3.3 The kernel matrix 68

3.4 Kernel construction 74

4 Detecting stable patterns 85

4.1 Concentration inequalities 86

4.2 Capacity and regularisation: Rademacher theory 93

4.3 Pattern stability for kernel-based classes 97

4.4 A pragmatic approach 104

Part II Pattern analysis algorithms 109

5 Elementary algorithms in feature space 111

5.1 Means and distances 112

5.2 Computing projections: Gram-Schmidt, QR and Cholesky 122

5.3 Measuring the spread of the data 128

5.4 Fisher discriminant analysis I 132

6 Pattern analysis using eigen-decompositions 140

6.1 Singular value decomposition 141

6.2 Principal components analysis 143

6.3 Directions of maximum covariance 155

6.4 The generalised eigenvector problem 161

6.5 Canonical correlation analysis 164

6.6 Fisher discriminant analysis II 176

6.7 Methods for linear regression 176

7 Pattern analysis using convex optimisation 195

7.1 The smallest enclosing hypersphere 196

7.2 Support vector machines for classification 211

7.3 Support vector machines for regression 230

7.4 On-line classification and regression 241

8 Ranking, clustering and data visualisation 252

8.1 Discovering rank relations 253

8.2 Discovering cluster structure in a feature space 264

8.3 Data visualisation 280

Part III Constructing kernels 289

9 Basic kernels and kernel types 291

9.1 Kernels in closed form 292

9.2 ANOVA kernels 297

9.3 Kernels from graphs 304

9.4 Diffusion kernels on graph nodes 310

9.5 Kernels on sets 314

9.6 Kernels on real numbers 318

9.7 Randomised kernels 320

9.8 Other kernel types 322

10 Kernels for text 327

10.1 From bag of words to semantic space 328

10.2 Vector space kernels 331

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

11.1 Comparing strings and sequences 345

11.2 Spectrum kernels 347

11.3 All-subsequences kernels 351

11.4 Fixed length subsequences kernels 357

11.5 Gap-weighted subsequences kernels 360

11.6 Beyond dynamic programming: trie-based kernels 372

11.7 Kernels for structured data 382

12 Kernels from generative models 397

12.1 P-kernels 398

12.2 Fisher kernels 421

Appendix A Proofs omitted from the main text 437

Appendix C List of pattern analysis methods 446

Appendix D List of kernels 448.

Notes:

Includes bibliographical references (pages 450-459) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Anne and Joseph Trachtman Memorial Book Fund.

ISBN:

0521813972

OCLC:

53926734

Online:

Publisher description