Kernels 🍿 & Support Vector Machines

• Reproducing kernel Hilbert spaces in Machine Learning from Arthur Gretton
• Kernel Methods from A Course in Machine Learning by Hal Daumé III
• Notes on Kernel Methods and Support Vector Machines from CS229 (Fall 2020) by Andrew Ng
• Kernel Methods - CS229 Lecture Notes Part V by by Tengyu Ma and Andrew Ng October 7, 2020
• Kernels - Stanford CS229 (Lecture 7) from Machine Learning Andrew Ng (Autumn 2018)
• Implicit Lifting and the Kernel Trick blog post by Gregory Gundersen
• The Kernel Trick - THE MATH YOU SHOULD KNOW! - very good, very succinct video published by Ajay Halthor outlining the significance of kernels and introducing the kernel trick via Mercer’s Theorem
• Notes on Support Vector Machines from CS 511 Theoretical Machine Learning by Rob Schapire
• A Tutorial on Support Vector Machines for Pattern Recognition by Chris J.C. Burges [PDF]

Reproducing kernel Hilbert spaces in Machine Learning - Arthur Gretton (with Hugh Dance)

INFO

This is taken from / the first half of Advanced Topics in Machine Learning (COMP0083) UCL Module Catalogue - UCL – University College London (COMP 0083) from the UCL CS MSc on Machine Learning.

About

This course represents half of Advanced Topics in Machine Learning (COMP 0083) from the UCL CS MSc on Machine Learning. The other half is a course on Convex Optimization.

This page will contain slides and detailed notes for the kernel part of the course. The assignment may also be found here (at the bottom of the page). Note that the slides will be updated as the course progresses, and I modify them to answer questions I get in the classes. I’ll put the date of last update next to each document - be sure to get the latest one. Let me know if you find errors.

There are sets of practice exercises and solutions further down the page (after the slides).

For questions on the course material, please email Hugh Dance.

Slides and notes

Lectures 1 and 2 slides and notes, last modified 09 Oct 2024

• Definition of a kernel, how it relates to a feature space
• Combining kernels to make new kernels
• The reproducing kernel Hilbert space and smoothness

Lecture 3 slides (notes same as for lectures 1 and 2), last modified 20 Oct 2021

• Basic kernel algorithms: difference in means, kernel PCA, kernel ridge regression

Lecture 4,5 slides and notes, last modified 02 November 2024

• Distance between means in RKHS, integral probability metrics, the maximum mean discrepancy (MMD)
• Two-sample tests with MMD
• Choice of kernels for distinguishing distributions, characteristic kernels

Lecture 6,7 slides and notes (notes same as lecture 4), last modified 14 Nov 2023

• Covariance operator in RKHS: proof of existence, definition of norms (including HSIC, the Hilbert-Schmidt independence criterion)
• Application of HSIC to independence testing

Lecture 7 slides and notes (notes same as lecture 4), last modified 07 Nov 2018

• Application of HSIC to feature selection, taxonomy discovery.
• Introduction to independent component analysis, HSIC for ICA

Lecture 8 slides, last modified 01 Dec 2021

• Kernel Stein Discrepancy for testing goodness of fit of a model

Lecture 9 slides and notes, last modified 01 Dec 2021

• Introduction to convex optimization
• The representer theorem
• Large margin classification, support vector machines for clasification

Lecture 10 Slides, last modified 19 Dec 2023

• Average treatment effect, conditional average treatment effect
• Proxy variables

Theory lectures Slides 1, Slides 2 , and notes, last modified 20 Mar 2013

• Metric, normed, and unitary spaces, Cauchy sequences and completion, Banach and Hilbert spaces
• Bounded linear operators and the Riesz Theorem
• Equivalent notions of an RKHS: existence of reproducing kernel, boundedness of the evaluation operator
• Positive definiteness of reproducing kernels, the Moore-Aronszajn Theorem
• Mercer’s Theorem for representing kernels

Supplementary lecture slides, last modified 22 Mar 2012

• Loss and risk, estimation and approximation error, a new interpretation of MMD
• Why use an RKHS: comparison with other function classes (Lipschitz and bounded Lipschitz)
• Characteristic kernels and universal kernels

Assignment

The assignment (first part due on Friday Nov 22, 2024). You will need this extract on incomplete Cholesky (scanned from Shawe-Taylor and Cristianini, Kernel Methods for Pattern Analysis). Last modified 09 October 2024.

Practice exercises and solutions

The exercises are taken from exams in previous years, with minor modifications. Worked solutions are provided. These will be posted after the course begins.- Set 1

Contact

arthur.gretton@gmail.com