Online learning: expert advice and linear classification |
basic linear algebra |
- Explains the basic concepts of online learning and regret bounds
- Can implement and apply various online algorithms
- Derives a mistake bound for Weighted Majority and its simple variants
- proves the Perceptron convergence theorem
|
- Derives regret bounds for the Aggregating Algorithms with absolute loss
- Derives a loss bound for the Perceptron algorithm in the non-separable case
|
- Analyses online learning with shifting target
- Analyses Winnow and other alternative online linear classifiers
|
Statistical learning theory |
basic probability theory |
- Explains the basic concepts of statistical learning theory
- Uses basic probability techniques such as Chernoff bounds and the union bound to analyse simple statistical learning situations
|
- Explains the basic concepts related to Vapnik-Chervonenkis dimension and Rademached complexity and applies them in simple situations
- Can prove basic results related to VC dimension and Rademacher complexity
|
- Uses covering numbers to analyse sample complexity
|
Support vector machines (SVMs) |
basic linear algebra, probability theory and calculus of one variable |
- Explains the notion of margin and applies it in simple situations
- Formulates the hard and soft margin SVM as quadratic optimisation problems
- Uses the kernel trick in simple situations
|
- Does non-trivial mathematical manipulations to find the dual of a variety of quadratic optimisation problems related to SVMs
- Can cite some sample complexity bounds for SVMs
- Knows how to use some standard SVM package
|
- Knows optimisations algorithms for SVMs
- Applies SVMs to more complex settings such as structured output
|
|
|
|
|
|