Contents Acknowledgments Symbols 1 Introduction 1.1 Decision functions 1.1.1 Decision Functions for Two-Class Problems 1.1.2 Decision Functions for Multiclass problems 1.2 Determination of decision functions 122489 1. 3 Data Sets Used in the book 1. 4 Classifier Evaluation 2 Two-Class Support Vector Machines 21 2.1 Hard-Margin Support Vector Machines 2.2 LI Soft-Margin Support Vector Machines 2.3 Mapping to a High-Dimensional Space 2.3.1 Kernel Tricks 2.3.2 Kernels reels 2.3.4 Properties of Mapping Functions Associated with 2.3.5 Implicit Bias Terms 2.3.6 Empirical Feature Space 2.4 L2 Soft-Margin Support Vector Machines 2.5 Advantages and Disadvantages 2.5.1 Advantages 2.5.2 Disadvantages 2. 6 Characteristics of Solutions 60 2.6.2D of solutionsContents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix 1 Introduction .............................................. 1 1.1 Decision Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Decision Functions for Two-Class Problems . . . . . . . . . . 2 1.1.2 Decision Functions for Multiclass Problems . . . . . . . . . . 4 1.2 Determination of Decision Functions . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Data Sets Used in the Book. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Classifier Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 Two-Class Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . 21 2.1 Hard-Margin Support Vector Machines . . . . . . . . . . . . . . . . . . . . 21 2.2 L1 Soft-Margin Support Vector Machines . . . . . . . . . . . . . . . . . . 28 2.3 Mapping to a High-Dimensional Space . . . . . . . . . . . . . . . . . . . . 31 2.3.1 Kernel Tricks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.2 Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.3 Normalizing Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.4 Properties of Mapping Functions Associated with Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.3.5 Implicit Bias Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3.6 Empirical Feature Space . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.4 L2 Soft-Margin Support Vector Machines . . . . . . . . . . . . . . . . . . 56 2.5 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.1 Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.2 Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.6 Characteristics of Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.6.1 Hessian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.6.2 Dependence of Solutions on C . . . . . . . . . . . . . . . . . . . . . 62 xiii