Machine learning with kernel methods, Spring 2019

Julien Mairal and Jean-Philippe Vert

MSc Mathematics, Vision, Learning (MVA) (ENS Cachan)

MSc Data science (Ecole Polytechnique, ENSAE ParisTech, Telecom ParisTech, University Paris Saclay)

MSc Mathematics for Life Sciences (MathSV) (University Paris South, Ecole Polytechnique, ENS Cachan)

MSc Mathematiques, Apprentissage et Sciences Humaines (MASH) (PSL Research University, Paris-Dauphine University, ENS Paris)


Upload your data challenge report here (deadline: April 1)

Slides

Slides are frequently updated. Please let us know if you spot typos!

Outline

Many problems in real-world applications of machine learning can be formalized as classical statistical problems, e.g., pattern recognition, regression or dimension reduction, with the caveat that the data are often not vectors of numbers. For example, protein sequences and structures in computational biology, text and XML documents in web mining, segmented pictures in image processing, or time series in speech recognition and finance, have particular structures which contain relevant information for the statistical problem but can hardly be encoded into finite-dimensional vector representations.

Kernel methods are a class of algorithms well suited for such problems. Indeed they extend the applicability of many statistical methods initially designed for vectors to virtually any type of data, without the need for explicit vectorization of the data. The price to pay for this extension to non-vectors is the need to define a so-called positive definite kernel function between the objects, formally equivalent to an implicit vectorization of the data. The "art" of kernel design for various objects have witnessed important advances in recent years, resulting in many state-of-the-art algorithms and successful applications in many domains.

The goal of this course is to present the mathematical foundations of kernel methods, as well as the main approaches that have emerged so far in kernel design. We will start with a presentation of the theory of positive definite kernels and reproducing kernel Hilbert spaces, which will allow us to introduce several kernel methods including kernel principal component analysis and support vector machines. Then we will come back to the problem of defining the kernel. We will present the main results about Mercer kernels and semigroup kernels, as well as a few examples of kernel for strings and graphs, taken from applications in computational biology, text processing and image analysis. Finally we will touch upon topics of active research, such as large-scale kernel methods and deep kernel machines.

References

Schedule

Lecture (in english) usually take place at Campus Jourdan 48 bd Jourdan Paris 14, in amphi Jourdan, 1:30-4pm.

The first class on January 16th will take place at ENS Cachan, amphi Curie

The exam will take place at MINES ParisTech, 60 boulevard Saint-Michel, 75006 Paris (RER Luxembourg). Check your room here.

DatePlaceLecturerTopicSlidesMore material
Jan 16ENS Cachan, amphi CurieJMPositive definite kernel, RKHS, Aronszajn's theorem1-46Uniqueness of the RKHS Aronszajn's theorem
Jan 23ENS Campus Jourdan, amphi JourdanJM Kernel trick, Representer theorem, kernel ridge regression 47-103
Jan 30ENS Campus Jourdan, amphi JourdanJMSupervised classification, Kernel logistic regression, large margin classifiers, SVM103-164Bartlett et al., 2006
Feb 6ENS Campus Jourdan, amphi JourdanJMUnsupervised learning, kernel PCA, kernel-Kmeans, spectral clustering, kernel CCA165-201
Feb 13ENS Campus Jourdan, amphi JourdanJPVGreen, Mercer, Herglotz, Bochner kernels202-277
Feb 20ENS Campus Jourdan, amphi JourdanJPVKernels from generative models, kernels for sequences298-367
Feb 27Break
Mar 6ENS Campus Jourdan, amphi JourdanArthur Gretton (UCL)Hypothesis testing and MMDPart 1, Part 2
Mar 13ENS Campus Jourdan, amphi JourdanJPVGraph kernels403-503
Mar 20ENS Campus Jourdan, amphi JourdanJPVMKL, large-scale kernel methods517-588
Mar 27MINES ParisTech, room L108-L106-L2132pm-4pm: Final exam

Evaluation

The final note will be an average of a homework (20%), a data challenge (40%), and a final written exam (40%). You can work on the project alone or with up to two friends.

Data challenge is now online. Instructions will be given in class to access it.

Homework (deadline: March 13)

Internships

M2 internships are available. (see this offer with Criteo). Do not hesitate to contact us directly.
Back to homepage