Dr Tugkan Batu, COL 4.04

This course is primarily intended for students taking MSc Applicable Mathematics. It may also be taken by other students having a suitable mathematical background.

This course uses mathematical techniques (including probability theory, discrete mathematics and computational complexity) to analyse the representational and learning properties of artificial neural networks and other machine learning systems (including classes of Boolean functions).

The key topics to be covered are: Neural networks and other learning systems; Boolean functions; A framework for supervised learning; Probabilistic modelling of learning; Consistent algorithms, sample error minimisation algorithms and learnability; The VC-dimension and the sample complexity of learning; Computational complexity of learning; The complexity of neural network learning. Other topics may be explored, if time permits.

20 lectures in MT and nine classes.

Summary lecture notes and research papers will be distributed. The most useful books are the following: Martin Anthony & Norman L Biggs, Computational Learning Theory: An Introduction, Cambridge (1992); Martin Anthony & Peter L Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press  (1999); Michael J Kearns & Umesh Vazirani, Introduction to Computational Learning Theory, MIT Press (1995); Martin Anthony, Discrete Mathematics of Neural Networks: Selected Topics, SIAM (2001).

A two-hour written examination in the ST (90%) and one piece of assessed coursework (10%).