# Graduate Course: Foundations of Machine Learning (10 ECTS)

This course surveys techniques, methods and ideas underlying the design of modern Machine Learning (ML) algorithms. The focus is on the theoretical analysis, and on deterministic or frequentist methods. That is, there exists a few standard ML algorithms (e.g. the PERCEPTRON, the Support Vector Machine, TD-lambda, ...) which possess surprisingly strong and complete theoretical characterisations. Once one gets to know those, better insight on how the modern field of ML is organised and develops, will follow. The emphasis of this course lies on conceptual ideas for analysis, rather than on a specific application of machine learning.

Machine Learning in a wide sense is evolving into a central place in contemporary IT, and it is felt that a rigorous treatment is proper to an academical approach to the topic. This course is seen as interfacing the mathematical sciences with the IT-oriented sciences, and aims to draw audiences from both areas.

(This course is orthogonal to earlier ML-courses organised in the department).

## Message board

- The first lecture is scheduled for 8 September. Welcome!
- Today's (18 sept.) lecture will finish the material of the last two lectures.
- The lecture of 'multi-class classification' is going to be rescheduled to a 12- October 1315-1500 in room 2414b.
- Thanks Jakob, Fredrik and Andreas for today's lecture on Ranking.
- Thanks Juozas, Tilo and Yevgen for the presentation of the results on stability FOML_stability.pdf.
- Thanks Kalyan for the presentation of the results on multi-class classification FoML_MCC.pdf.
- Thanks Tatiana and Ruben for the lecture on regression.
- Thanks Ali, Tomas, Fredrik for the lecture on dimensionality reduction foml_dimentionality.pdf.
- Thanks Sholeh, Vahan, Teo for the lecture on reinforcement learning foml_rl.pdf.
- The computerlab is scheduled for next tuesday (3e of november) at 1315-1500. The room is ITC 1312D. The report is compFOML.pdf.
- Can you send me the reports of the miniprojects in the next days? The announced deadline is 31e of october.The hard deadline is friday 6e of November.

## Course material

- The course follows the textbook of M. Mohri et al. ('Foundations of Machine Learning' by M. Mohri, A. Rostamizadeh, and A. Talwalkar, MIT Press, 2012). It is recommended to purchase this book before the course starts.
- You can find supporting material for this book at http://www.cs.nyu.edu/~mohri/ml14/.
- The slides I used are based on Mohri's: lecture 1, lecture 2, lecture 3, lecture 4, lecture 5.

## Organisation

Evaluation is based on pairing students up for

- Presenting a class to the other students, based on the text and slides provided, and
- Making/presenting/reporting results of a mini-project regarding a chosen research topic.

This mini-project has to indicate that the successful student knows how to extend (tune, analyse) a standard technique (perceptron, support vector machine, or a reinforcement learning algorithm, ...) in order to start formalising and analysing a relevant task. This has to result in

- A well-written report of the project including a formalisation of the task, reduction to a standard algorithm, and a first application of the method of choice, and
- Concisely (20-30 mins) presenting this result for their colleagues.

Successful delivery of this will earn you 10 ECTS.

The course will consist of:

- September-October 2015: 5+6 lectures, twice a week (Tuesday am, Friday pm) in Polacksbacken/UU.
- October 2015: 1 computer class.
- October 2015: preparation, reporting and presentation of the mini-project.

## Content

Classes:

- Introduction.
- Support Vector Machines.
- Probably Approximatively Correct (PAC) analysis.
- Boosting.
- Online Learning.
- Multi-class classification (*).
- Ranking (*).
- Regression (*).
- Stability-based analysis (*).
- Dimensionality reduction (*).
- Reinforcement learning (*).
- Presentations of the mini-projects.

(*: items containing an * are to presented by the students, to the students, based on the relevant chapters in the textbook).

There will be one computer-class after the 5e lecture illustrating the basic algorithms in MATLAB, and giving a tour of state-of-the-art implementations of those.

## Prerequisites

The participants (graduate students) are assumed to be exposed to basic calculus, linear algebra and statistics courses. The technical tools which are involved are often not very cumbersome. Graduate students who have a proper, mathematically oriented background in automatic control, computer science, statistics or similar will have no problem in taking the course. Students lacking a proper mathematical background might need to compensate this before taking the course: the course book is entirely self-contained, and the appendices in the book contain appropriate introductions. Mathematically skilled students who lack the context of computer science, engineering, or machine learning, will have a (tailored) introduction to those in the first lecture(s).

## Registration