An Introduction to Support Vector Machines and Other Kernel-based Learning Methods

by Nello Cristianini , John Shawe-Taylor

• ISBN13: 9780521780193
• ISBN10: 0521780195
• Format: Hardcover
• Copyright: 2000-03-28
• Publisher: Cambridge University Press

Summary

This is the first comprehensive introduction to Support Vector Machines (SVMs), a new generation learning system based on recent advances in statistical learning theory. Students will find the book both stimulating and accessible, while practitioners will be guided smoothly through the material required for a good grasp of the theory and its applications. The concepts are introduced gradually in accessible and self-contained stages, while the presentation is rigorous and thorough. Pointers to relevant literature and web sites containing software make it an ideal starting point for further study.

Table of Contents

Preface	ix
Notation	xiii
The Learning Methodology	1	(8)
Supervised Learning	1	(2)
Learning and Generalisation	3	(1)
Improving Generalisation	4	(2)
Attractions and Drawbacks of Learning	6	(1)
Support Vector Machines for Learning	7	(1)
Exercises	7	(1)
Further Reading and Advanced Topics	8	(1)
Linear Learning Machines	9	(17)
Linear Classification	9	(11)
Rosenblatt's Perceptron	11	(8)
Other Linear Classifiers	19	(1)
Multi-class Discrimination	20	(1)
Linear Regression	20	(4)
Least Squares	21	(1)
Ridge Regression	22	(2)
Dual Representation of Linear Machines	24	(1)
Exercises	25	(1)
Further Reading and Advanced Topics	25	(1)
Kernel-Induced Feature Spaces	26	(26)
Learning in Feature Space	27	(3)
The Implicit Mapping into Feature Space	30	(2)
Making Kernels	32	(14)
Characterisation of Kernels	33	(9)
Making Kernels from Kernels	42	(2)
Making Kernels from Features	44	(2)
Working in Feature Space	46	(2)
Kernels and Gaussian Processes	48	(1)
Exercises	49	(1)
Further Reading and Advanced Topics	50	(2)
Generalisation Theory	52	(27)
Probably Approximately Correct Learning	52	(2)
Vapnik Chervonenkis (VC) Theory	54	(5)
Margin-Based Bounds on Generalisation	59	(10)
Maximal Margin Bounds	59	(5)
Margin Percentile Bounds	64	(1)
Soft Margin Bounds	65	(4)
Other Bounds on Generalisation and Luckiness	69	(1)
Generalisation for Regression	70	(4)
Bayesian Analysis of Learning	74	(2)
Exercises	76	(1)
Further Reading and Advanced Topics	76	(3)
Optimisation Theory	79	(14)
Problem Formulation	79	(2)
Lagrangian Theory	81	(6)
Duality	87	(2)
Exercises	89	(1)
Further Reading and Advanced Topics	90	(3)
Support Vector Machines	93	(32)
Support Vector Classification	93	(19)
The Maximal Margin Classifier	94	(9)
Soft Margin Optimisation	103	(9)
Linear Programming Support Vector Machines	112	(1)
Support Vector Regression	112	(9)
ε-Insensitive Loss Regression	114	(4)
Kernel Ridge Regression	118	(2)
Gaussian Processes	120	(1)
Discussion	121	(1)
Exercises	121	(1)
Further Reading and Advanced Topics	122	(3)
Implementation Techniques	125	(24)
General Issues	125	(4)
The Native Solution: Gradient Ascent	129	(6)
General Techniques and Packages	135	(1)
Chunking and Decomposition	136	(1)
Sequential Minimal Optimisation (SMO)	137	(7)
Analytical Solution for Two Points	138	(2)
Selection Heuristics	140	(4)
Techniques for Gaussian Processes	144	(1)
Exercises	145	(1)
Further Reading and Advanced Topics	146	(3)
Applications of Support Vector Machines	149	(13)
Text Categorisation	150	(2)
A Kernel from IR Applied to Information Filtering	150	(2)
Image Recognition	152	(4)
Aspect Independent Classification	153	(1)
Colour-Based Classification	154	(2)
Hand-written Digit Recognition	156	(1)
Bioinformatics	157	(3)
Protein Homology Detection	157	(2)
Gene Expression	159	(1)
Further Reading and Advanced Topics	160	(2)
A Pseudocode for the SMO Algorithm	162	(3)
B Background Mathematics	165	(8)
Vector Spaces	165	(2)
Inner Product Spaces	167	(2)
Hilbert Spaces	169	(2)
Operators, Eigenvalues and Eigenvectors	171	(2)
References	173	(14)
Index	187