Contents
Nomenclature xi
1 Introduction 1
1.1 Statistical Learning Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 VC Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Structural Risk Minimisation . . . . . . . . . . . . . . . . . . . . . 4
2 Support Vector Classification 5
2.1 The Optimal Separating Hyperplane . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Linearly Separable Example . . . . . . . . . . . . . . . . . . . . . . 10
2.2 The Generalised Optimal Separating Hyperplane . . . . . . . . . . . . . . 10
2.2.1 Linearly Non-Separable Example . . . . . . . . . . . . . . . . . . . 13
2.3 Generalisation in High Dimensional Feature Space . . . . . . . . . . . . . 14
2.3.1 Polynomial Mapping Example . . . . . . . . . . . . . . . . . . . . 16
2.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Feature Space 19
3.1 Kernel Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Gaussian Radial Basis Function . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Exponential Radial Basis Function . . . . . . . . . . . . . . . . . . 20
3.1.4 Multi-Layer Perceptron . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.5 Fourier Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.6 Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.7 B splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.8 Additive Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.9 Tensor Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Implicit vs. Explicit Bias . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Data Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Kernel Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Classification Example: IRIS data 25
4.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Support Vector Regression 29
5.1 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1.1 -insensitive Loss Function . . . . . . . . . . . . . . . . . . . . . . 30
5.1.2 Quadratic Loss Function . . . . . . . . . . . . . . . . . . . . . . . . 31
iii
iv CONTENTS
5.1.3 Huber Loss Function . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Non Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.2 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6 Regression Example: Titanium Data 39
6.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7 Conclusions 43
A Implementation Issues 45
A.1 Support Vector Classification . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.2 Support Vector Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
B MATLAB SVM Toolbox 51
Bibliography 53
List of Figures
1.1 Modelling Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 VC Dimension Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Optimal Separating Hyperplane . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Canonical Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Constraining the Canonical Hyperplanes . . . . . . . . . . . . . . . . . . . 7
2.4 Optimal Separating Hyperplane . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Generalised Optimal Separating Hyperplane . . . . . . . . . . . . . . . . . 11
2.6 Generalised Optimal Separating Hyperplane Example (C = 1) . . . . . . . 13
2.7 Generalised Optimal Separating Hyperplane Example (C = 10
5
) . . . . . 14
2.8 Generalised Optimal Separating Hyperplane Example (C = 10
−8
) . . . . . 14
2.9 Mapping the Input Space into a High Dimensional Feature Space . . . . . 14
2.10 Mapping input space into Polynomial Feature Space . . . . . . . . . . . . 16
3.1 Comparison between Implicit and Explicit bias for a linear kernel . . . . . 22
4.1 Iris data set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Separating Setosa with a linear SVC (C = ∞) . . . . . . . . . . . . . . . . 26
4.3 Separating Viginica with a polynomial SVM (degree 2,C = ∞) . . . . . . 26
4.4 Separating Viginica with a polynomial SVM (degree 10, C = ∞) . . . . . 26
4.5 Separating Viginica with a Radial Basis Function SVM (σ = 1.0, C = ∞) 27
4.6 Separating Viginica with a polynomial SVM (degree 2, C = 10) . . . . . . 27
4.7 The effect of C on the separation of Versilcolor with a linear spline SVM . 28
5.1 Loss Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3 Polynomial Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.4 Radial Basis Function Regression . . . . . . . . . . . . . . . . . . . . . . . 35
5.5 Spline Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.6 B-spline Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.7 Exponential RBF Regression . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.1 Titanium Linear Spline Regression ( = 0.05, C = ∞) . . . . . . . . . . . 39
6.2 Titanium B-Spline Regression ( = 0.05, C = ∞) . . . . . . . . . . . . . . 40
6.3 Titanium Gaussian RBF Regression ( = 0.05, σ = 1.0, C = ∞) . . . . . . 40
6.4 Titanium Gaussian RBF Regression ( = 0.05, σ = 0.3, C = ∞) . . . . . . 40
6.5 Titanium Exponential RBF Regression ( = 0.05, σ = 1.0, C = ∞) . . . . 41
6.6 Titanium Fourier Regression ( = 0.05, degree 3, C = ∞) . . . . . . . . . 41
6.7 Titanium Linear Spline Regression ( = 0.05, C = 10) . . . . . . . . . . . 42
v
