An Introduction to Support Vector Machines

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.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

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

Summary

Table of Contents

Supplemental Materials