0 0 5 views

**Unformatted text preview: **

chapters 1 2 3 4 Introduction to Kernels Max Welling October 1 2004 1 Introduction What is the goal of pick your favorite name Machine Learning Data Mining Pattern Recognition Data Analysis Statistics Automatic detection of non coincidental structure in data Desiderata Robust algorithms insensitive to outliers and wrong model assumptions Stable algorithms generalize well to unseen data Computationally efficient algorithms large datasets 2 Let s Learn Something Find the common characteristic structure among the following statistical methods 1 Principal Components Analysis 2 Ridge regression 3 Fisher discriminant analysis 4 Canonical correlation analysis Answer We consider linear combinations of input vector f x wT x Linear algorithm are very well understood and enjoy strong guarantees convexity generalization bounds Can we carry these guarantees over to non linear algorithms 3 Feature Spaces d F x F x R F non linear mapping to F 1 high D space L2 2 infinite D countable space 3 function space Hilbert space example 2 F 2 x y x y 2 xy 4 Ridge Regression duality l problem min w yi wT xi 2 l w 2 i 1 target solution input regularization w X T X l I d 1 X T y dxd inverse X T XX T l I l 1 y l l inverse X T G l I l 1 y Gij xi x j l xia i i 1 linear comb data Dual Representation Gram matrix 5 Kernel Trick Note In the dual representation we used the Gram matrix to express the solution Kernel Trick Replace x F x kernel Gij xi x j GijF F xi F x j K xi x j If we use algorithms that only depend on the Gram matrix G then we never have to know compute the actual features F This is the crucial point of kernel methods 6 Modularity Kernel methods consist of two modules 1 The choice of kernel this is non trivial 2 The algorithm which takes kernels as input Modularity Any kernel can be used with any kernel algorithm some kernels 2 k x y e x y c k x y x y q d k x y tanh a x y q k x y 1 2 x y c 2 some kernel algorithms support vector machine Fisher discriminant analysis kernel regression