Reproducing Kernel Hilbert Spaces Lorenzo Rosasco 9 520 Class 03 February 9 2011 L Rosasco RKHS About this class Goal In this class we continue our journey in the world of RKHS We discuss the Mercer theorem which gives a new characterization of RKHS while introducing the concept of feature map Then we discussed the concept of feature map and its interpretation Finally we show the computational implication of using RKHS by deriving the general solution of Tikhonov regularization the so called he representer theorem L Rosasco RKHS Plan Part I RKHS are Hilbert spaces with bounded continuous evaluation functionals Part II Reproducing Kernels Part III Mercer Theorem Part IV Feature Maps Part V Representer Theorem L Rosasco RKHS Part III Mercer Theorem L Rosasco RKHS Different Views on RKHS L Rosasco RKHS Integral Operator RKH space can be characterized via the integral operator Z LK f x K x s f s p s dx X where p x is the probability density on X The operator has domain and range in L2 X p x dx the space of functions f X R such that Z hf f iL2 f x 2 p x dx X L Rosasco RKHS Integral Operator If X is a compact set and K is a continuous reproducing kernel i e symmetric and PD then LK is a compact positive and self adjoint operator There is a decreasing sequence i i 0 such that limi i 0 and Z LK i x K x s i s p s ds i i x X where i is an orthonormal basis in L2 X p x dx The action of LK can be written as X LK f i hf i i i i 1 L Rosasco RKHS Integral Operator If X is a compact set and K is a continuous reproducing kernel i e symmetric and PD then LK is a compact positive and self adjoint operator There is a decreasing sequence i i 0 such that limi i 0 and Z LK i x K x s i s p s ds i i x X where i is an orthonormal basis in L2 X p x dx The action of LK can be written as X LK f i hf i i i i 1 L Rosasco RKHS Integral Operator If X is a compact set and K is a continuous reproducing kernel i e symmetric and PD then LK is a compact positive and self adjoint operator There is a decreasing sequence i i 0 such that limi i 0 and Z LK i x K x s i s p s ds i i x X where i is an orthonormal basis in L2 X p x dx The action of LK can be written as X LK f i hf i i i i 1 L Rosasco RKHS Mercer Theorem The kernel function have the following representation K x s X i i x i s i 1 A symmetric positive definite and continuous Kernel is called a Mercer kernel L Rosasco RKHS Different Definition of RKHS It is possible to prove that H f L2 X p x dx X hf i i22 L i 1 i The scalar product in H is hf giH X hf i iL hg i iL2 2 i i 1 L Rosasco RKHS Different Definition of RKHS It is possible to prove that H f L2 X p x dx X hf i i22 L i 1 i The scalar product in H is hf giH X hf i iL hg i iL2 2 i i 1 L Rosasco RKHS Part IV Feature Map L Rosasco RKHS Different Views on RKHS L Rosasco RKHS Mercer Theorem and Feature Map K x s X i i x i s i 1 Let x i i x i then X 2 and by definition K x s h x x i The above is an example of feature map associated to K L Rosasco RKHS Feature Maps and Kernels The above remark shows that we can associate a feature map to every kernel In fact multiple feature maps can be associated to a kernel Let x Kx Then X H Let x j x j where j x j is an orthonormal basis of H Then X 2 Why L Rosasco RKHS Feature Map and Feature Space In general a feature map is a map X F where F is a Hilbert space and is called Feature Space Every feature map defines a kernel via K x s h x x i L Rosasco RKHS Kernel from Feature Maps Often times feature map and hence kernels are defined through a dictionary of features D j i 1 p j X R j where p We can interpret the above functions as possibly non linear measurements on the inputs If p we can always define a feature map If p we need extra assumptions Which ones L Rosasco RKHS Kernel from Feature Maps Often times feature map and hence kernels are defined through a dictionary of features D j i 1 p j X R j where p We can interpret the above functions as possibly non linear measurements on the inputs If p we can always define a feature map If p we need extra assumptions Which ones L Rosasco RKHS Kernel from Feature Maps Often times feature map and hence kernels are defined through a dictionary of features D j i 1 p j X R j where p We can interpret the above functions as possibly non linear measurements on the inputs If p we can always define a feature map If p we need extra assumptions Which ones L Rosasco RKHS Function as Hyperplanes in the Feature Space The concept of feature map allows to give a new interpretation of RKHS Functions can be seen as hyperplanes f x hw x i This can be seen for any of the previous examples Let x j j x j Let x Kx Let x j x j L Rosasco RKHS Feature Maps Illustrated L Rosasco RKHS Kernel Trick and Kernelization Any algorithm which works in a euclidean space hence requiring only inner products in the computations can be kernelized K x s h x x i Kernel PCA Kernel ICA Kernel CCA Kernel LDA Kernel L Rosasco RKHS Part V Regularization Networks and Representer Theorem L Rosasco RKHS Again Tikhonov Regularization The algorithms Regularization Networks that we want to study are defined by an optimization problem over RKHS n fS arg min f H 1X V f xi yi kf k2H n i 1 where the regularization parameter is a positive number H is the RKHS as defined by the pd kernel K and V is a loss function Note that H is possibly infinite dimensional L Rosasco RKHS Existence and uniqueness of minimum If the positive loss function V is convex with respect to its first entry the functional n f 1X V f xi yi kf k2H n i 1 is strictly convex and coercive hence it has exactly one local global minimum Both the squared loss and the …
View Full Document
Unlocking...