Courses in the Department of Mathematics 

MA401: Computational Learning Theory and Neural Networks 2009/10

General information

Course description

Calendar Entry for this course

Course Materials on Moodle

Past Exam Papers

General information about MA401: Computational Learning Theory and Neural Networks 

Teacher:	Dr Tugkan Batu
Office:	B405, Columbia House
E-mail:	T.Batulse.ac.uk
Telephone:	Extension 6540
Office hours:	(see Office hours page)
Departmental office:	B401, Extension 7925

Course description of MA401: Computational Learning Theory and Neural Networks

This course concerns how to mathematically model processes by which machines (such as artificial neural networks) can 'learn'. We focus, in particular, on a probabilistic model of learning, called the PAC model, and we look in some detail at mathematical approaches to some important questions in this model, such as `How much training is needed before learning has been sufficiently accurate?' and `What are the methods by which the machine achieves this learning?'. The types of learning we will be primarily interested in are the learning of Boolean functions, and neural network learning. The mathematical techniques involved are probability theory, combinatorics, and computational complexity, but no substantial prior knowledge of these is required.

Course content

The course starts off by looking at some of the basic types of `learning algorithms' for very basic classes of Boolean functions. We also introduce artificial neural networks. Having done this, we then move on to the core of the course, which is an analysis of what we mean by a successful learning algorithm. We concentrate on a model of learning (known as the `pac' model) which is defined using probability theory. (This should not be confused with the Bayesian model, another important
type of probabilistic learning model.) Our main concerns here will be: `what algorithms constitute successful learning algorithms in this model?', and `how much training data do these algorithms require?' This second question involves some interesting mathematics. Here we shall see that something known as the `Vapnik-Chervonenkis' dimension is crucial. For a learning algorithm to be successful, it must be fast. This leads us to a discussion of complexity theory. Having developed, in abstract, the probabilistic model of learning, we conclude the course with applications to artificial neural networks.

 The main topics are as follows.

• Supervised learning: The supervised learning framework; concepts and hypotheses; training and learning.

• Important concept classes: Boolean functions and formulae; monomials; disjunctive normal form and conjunctive normal form; artificial neural networks.

• Learning algorithms for some Boolean classes: A learning algorithm for monomials; learning disjunctions of small monomials.

• Probabilistic learning: The class of rays; a learning algorithm for rays; PAC learning.

• Consistent algorithms and learnability: potential learnability; potential learnability and finiteness of hypothesis space implies pac learnability; potential learnability of finite classes.

• Application to Boolean function classes: pac learnability of monomials and disjunctions of small monomials; decision lists; a consistent learning algorithm for decision lists.

• The computational complexity of learning: Running time of algorithms; polynomial-time computability; running time of learning algorithms; efficient PAC learning; sufficient conditions for efficient PAC learning; randomised algorithms; consistent-hypothesis-finders; the consistency problem; hardness of learning k-term DNF.

• Sample complexity of learning: The growth function; a `uniform convergence' result; the VC-dimension; VC-dimension of particular classes; Sauer's lemma relating growth function and VC-dimension; sample complexity in terms of VC-dimension; the perceptron and its VC-dimension.
  

• Applications to artificial neural networks: the perceptron; linear threshold networks; sigmoid networks; perceptron learning algorithms; VC-dimension of multi-layer neural networks.
  

• (If time allows): Extensions of the PAC model.
  

Past exam papers for this course

Please note: students are advised not to rely too heavily on past exam papers when revising for their exams, as they can only offer a limited indication of what might be covered in a future exam. For further information, please see the guidance here: http://www.maths.lse.ac.uk/examinations_in_mathematics.html#past_papers

Exam Paper 2007
Exam Paper 2008
[The course was not given 2008/09]