Machine learning with kernel methods, Spring 2015

Jean-Philippe Vert, Mines ParisTech

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

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

Slides

Results

The final note will be an average of the homeworks.

Jobs / internships / PhD proposals

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.

References

Schedule and Homework

Lecture take place at ENS Cachan in amphi Marie Curie.

Homeworks can be made by groups of 1 to 3 students, and are due at the begining of the following lecture, by hard copy or (better) e-mail to Jean-Philippe.Vert@mines.org. Implementations can be done in the programming language of your choice, e.g., the free R language, or Matlab and its free clone Octave

Schedule:

DateTopicSlidesHomeworkData
Jan 21, 1pm-4pmPositive definite kernel, RKHS, Aronszajn's theorem1-45Homework 1
Jan 28 1pm-4pmKernel trick, Representer theorem, kernel PCA46-90Homework 2
Feb 4, 1pm-4pmKernel ridge regression, pattern recognition, large-margin classifiers91-127Homework 3
Feb 11, 1pm-4pmSVM, MKL128-165no homework
Feb 25, 1pm-4pmMKL, Mercer kernels, Green functions, translation invariant and semigroup kernels 166-243Homework 4
Mar 4, 1pm-4pmString kernels244-326no homework
Mar 11, 1pm-4pmGraph kernels, kernels on graphs326-444no homework

2014 course evaluation by students


Back to homepage