WelcometotheKernel-Class

《WelcometotheKernel-Class》由会员分享，可在线阅读，更多相关《WelcometotheKernel-Class（11页珍藏版）》请在装配图网上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,,,*,Welcome to the Kernel-Class,My name,: Max (Welling),,Book:,,There will be class-notes/slides.,,Homework,: reading material, some exercises,,,some MATLAB implementations.,,I l

2、ike,: an active attitude in class.,,ask questions! respond to my questions.,,Enjoy.,,1,,Primary Goal,,What is the primary goal of:,,,- Machine Learning,,- Data Mining,,- Pattern Recognition,,- Data Analysis,,- Statistics,,,Automatic detection of non-coincidental structure in data.,,,2,,Desiderata,,,

3、Robust algorithms,are insensitive to outliers and wrong,,model assumptions.,,,,Stable algorithms,: generalize well to unseen data.,,,,Computationally efficient algorithms,are necessary to handle,,large datasets.,,3,,Supervised & Unsupervised Learning,,,supervised,: classification, regression,,,,uns

4、upervised,: clustering, dimensionality reduction, ranking,,,outlier detection.,,,primal vs. dual problems: generalized linear models vs.,,kernel classification.,this is like nearest neighbor,,classification.,4,,Feature Spaces,,non-linear mapping to F,,1. high-D space,,2. infinite-D countable space :

5、,,3. function space (Hilbert space),example:,5,,Kernel Trick,,Note: In the dual representation we used the Gram matrix,,to express the solution.,,,Kernel Trick:,,Replace :,kernel,If we use algorithms that only depend on the Gram-matrix, G,,,then we never have to know (compute) the actual features,T

6、his is the crucial point of kernel methods,6,,Properties of a Kernel,,Definition:,,A finitely,positive semi-definite,function,,is a,symmetric,function of its arguments for which matrices formed,,by restriction on any finite subset of points is positive semi-definite.,Theorem:,,A function

7、 can be written,,as where is a feature map,,iff k(x,y) satisfies the semi-definiteness property.,Relevance:,We can now check if k(x,y) is a proper kernel using,,only properties of k(x,y) itself,,,i.e. without the need to know the featu

8、re map!,7,,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:,some kernel algorithms:,,- support vector machine,,- Fisher dis

9、criminant analysis,,- kernel regression,,- kernel PCA,,- kernel CCA,8,,Goodies and Baddies,,Goodies:,,Kernel algorithms are typically constrained convex optimization,,problems,,solved with either spectral methods or convex optimization tools,.,,Efficient algorithms do exist in most cases.,,The simi

10、larity to linear methods facilitates analysis. There are strong,,generalization bounds on test error.,,,Baddies:,,You need to choose the appropriate kernel,,Kernel learning is prone to over-fitting,,All information must go through the kernel-bottleneck.,,9,,Regularization,,Demo Trevor Hastie.,regula

11、rization is very important!,,,,regularization parameters determined by out of sample.,,measures (cross-validation, leave-one-out).,10,,Learning Kernels,,All information is tunneled through the Gram-matrix information,,bottleneck.,,The real art is to pick an appropriate kernel.,,e.g. take the RBF kernel:,if c is very small: G=I (all data are dissimilar): over-fitting,,if c is very large: G=1 (all data are very similar): under-fitting,,,We need to,learn,the kernel. Here is some ways to combine kernels to improve them:,,k1,k2,cone,any positive,,polynomial,11,,