COV883: Special Module in Theoretical Computer Science
Topic: Efficient approximations of kernel functions
II semester: 2019-20
Amitabha Bagchi
Next class: TBA.
Overview
Kernel functions play an important role in machine learning, especially in classification settings. In this course we will study some of the basic properties of kernel functions and their uses in classification in order to understand better the efficient kernel approximation methods of Rahimi and Recht (NIPS 2009).
Topics
Kernels and their role in classification and pattern analysis, Functional analysis refresher including the Reisz Representation Theorem, Mercer's theorem with (partial) proof, Bochner's theorem, light introduction to matrix concentration inequalities, kernel approximations.
Background required: Probability theory, linear algebra.
Lecture record
- Lecture 1. Motivation: Support vector machines; introduction to positive definite kernels. 14 Jan 2020.
- Lecture 2. Some basic properties of positive definite and conditionally negative definite kernels. [BCR84] pages 67-69. 22 Jan 2020.
- Lecture 3. Some basic properties of p.d. and c.n.d. kernels continued. [BCR84] pages 69-70. 29 Jan 2020.
- Lecture 4. Relationships betwed p.d. and c.n.d. kernels. [BCR84] pages 71-75. 12 Feb 2020.
- Lecture 5. Basic functional analysis: Inner product spaces and norms. Mainly from [Heil06]. 19 Feb 2020.
- Lecture 6. Hilbert spaces; A Mercer theorem for finite sets; Reproducing Kernel Hilbert Spaces. 26 Feb 2020.
- Lecture 7. Random Fourier Features. [Tu16]. 4 Mar 2020.
- Lecture 8. Characterstic functions and Bochner's theorem; The Cramer-Chernoff method for concentration of random variables; Hoeffding's inequality; A tail bound for Random Fourier Features. [BLM16,Tu16]. 12 Mar 2020.
- Lecture 9. (Video Lecture) Matrix theory background; A Cramer-Chernoff-like bound for random matrices. [Tropp14]. Uploaded 14 May 2020.
- Lecture 10. (Video Lecture) The Matrix Bernstein Inequality; Matrix sampling estimators; An error estimate for Random Fourier Features. [Tropp15]. Uploaded 21 May 2020.
Lecture notes. Updated 4 May 2020.
Texts and other supplementary material
- [SS01] Bernhard Scholkopf and Alexander J. Smola. Learning with Kernels
Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, 2001.
- [NM19] Andrew Ng, Tengyu Ma. Support vector machines, Lecture notes for CS229: Machine Learning, Stanford University, 2019.
- [BCR84] Christian Berg, Jens Peter Reus Christensen, Paul Ressel. Harmonic analysis on semigroups: Theory of positive definite and related functions, Springer, 1984.
- [Heil06] Christopher Heil. Chapter 1: Hilbert Spaces, Functional Analysis lecture notes, 2006.
- [Tu16] Stephen Tu. Discussion 12: A discussion of random Fourier features. Discussion Notes for CS189 Fall 2016, Stanford University, 2016.
- [BLM16] Stephane Boucheron, Gabor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2016.
- [Tropp15] Joel A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Mach. Learn., 8(1-2):1–230, May 2015.
Evaluation
Evaluation will be through scribing class notes.
Scribing
- Each student will be expected to scribe at least one lecture. This
will involve taking careful and complete notes during the lecture and
then typing them out in latex.
- Please download the template file and the
latex class file that will be needed.
- The first draft of the notes will be due three days after the lecture. This will
have to be emailed either to me.
- I will return
the draft with comments and, three days after that, a final version will
have to be made and submitted with all the required changes
incorporated.
- Here are some general
guidelines which may help you with scribing class notes. Please
read them before you begin typing.
- Also the tex source for some notes scribed in a previous course are available for your reference: lecture
1 and lecture
4 of CSL863, I Sem 2007-08 (local access only.)
- Some latex tips here.
Amitabha
Bagchi