Kernel Method

Next, we consider datasets that are not linearly separable. In order to treat these with the methods of the last two chapters, we map our not linearly separable dataset into a higher-dimensional (sometimes even infinite-dimensional!) space. If this “embedded dataset” is linearly separable, then we may apply the perceptron algorithm or the SVM method and obtain an induced classifier for the original data. The latter leads to the so-called kernel trick, where one does not even need to know the higher-dimensional space explicitly, but can, by using only a kernel function, determine a classifier through solving a quadratic optimization problem. We address the existence of kernel functions by considering Mercer’s condition.