Course on Mathematical Foundations of Machine Learning

Overview

Literature

• L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recog- nition. Springer, New York, 1996.
• T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer, New York, 2001.
• V. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, New York, 1995.
• B. Schölkopf and A. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
• A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer, New York, 1996.
• R. Dudley. Uniform central limit theorems. Cambridge University Press, 1999.
• L. Györfi, M. Kohler, A. Krzyzak, and H. Walk. A distribution-free theory of non-parametric regression. Springer, New York, 2002.
• L. Devroye and G. Lugosi. Combinatorial Methods in Density Estimation. Springer, New York, 2001.

• Shiryaev: Probability. Springer, 1996.
• Jacod, Protter: Probability essentials. Springer, 2004.

Script

Summary of all lectures

• Overview: what is machine learning? Examples, terms and conditions, ideas, ...
• Formal setup of binary classification
• Bayes classifier: definition and examples

• Recap: joint distributions, marginal distributions, conditional distributions, conditional expectations
• Definition and properties of the regression function
• Can decompose joint distribution of (X,Y) in marginal P_X and regression function
• Theorem: The Bayes classifier is optimal.
• Definition: different notions of consistency of classifiers

• Recap: types of convergence of random variables
• Consistency: examples and counterexamples
• Plug-in classifiers: definition, first bounds on the risk
• Theorem: Plug-in classifiers based on partitioning rules are consistent.

• Application of consistency theorem for plug-in classifiers: cubic histogram rules
• The k-nearest neighbor classifier: definition
• Examples: The k-NN classifier for fixed k is not consistent.
• Theorem of Stone

• Theorem: The k-NN classifier is consistent if k grows "suitably".
• Matlab demo of the kNN classifier. Demo can be downloaded here (9 MB, as it contains the USPS data set...)

• No free lunch theorems in a discrete setting: averaged over all possible distributions, all classifiers perform the same.
• Arbitrary bad finite sample performance: For each classification rule there exists a distribution with Bayes error 0, such that the risk of the classifier on n training points has error 1/2 - epsilon.
• Arbitrary slow rates of convergence: Even for a consistent classifier there always exists a distribution such that the risk converges arbitrarily slow.

• Formalization of the ERM principle
• Decompositions of the risk (estimation/approximation, bias/variance, ... )
• Concentration inequalities of Hoeffding and McDiarmid
• Generalization bound for a fixed function
• Generalization bound for a finite function class

• The shattering coefficient (growth function)
• Generalization bound using the shattering coefficient
• The VC dimension: definition and many examples

• The Sauer-Shelah lemma
• Generalization bound using the VC dimension
• [Sample compression bounds, skipped for time reasons, for references see below
• Support vector machines: large margin classifier, hard and soft margin SVM (primal)

• Convex optimization: basic definitions, duality theory, Lagrangian, duality gap, strong duality, constraint qualifications ...
• Derivation of the dual problems of hard and soft margin SVM

• Recap: Hilbert spaces
• Kernels and the reproducing kernel Hilbert space RKHS
• The kernel trick, SVM with kernels
• Representer theorem
• Implementation, demos, and software packages

• Generalization bounds for SVMs: Large margin bounds, sparsity bounds, trace bound,...
• Universal kernels and consistency of the SVM
• Regularization