MSc by Research in Computer Science
Back to MSc by Research in Computer Science Home Page
Machine Learning Strand
This course provides a modern view of inductive
inference, and a rapid introduction to several active
research areas in machine learning and computational learning theory.
At the end of this course the student should have a good theoretical
understanding of inductive inference, and should be able
to make practical use of several recent learning methods.

Universal approaches to learning

Overview:
an introduction to Solomonoff's approach to
inductive inference, and the theory of Kolmogorov
complexity, leading to learning with resourcebounded algorithms.

Topics:
Solomonoff's formulation of inductive inference,
Kolmogorov complexity, induction using
resourcebounded algorithms, and the minimum description length
principle for induction.

Prediction using the Aggregating Algorithm

Overview: The aggregating algorithm (AA) can be regarded as a tool for
extending the universal learning techniques to problems with
arbitrary loss functions. The AA performs perhaps the simplest and
most general method of statistical prediction possible: it is a
general minimax procedure that makes no statistical assumptions
whatsoever about the sequence that is to be predicted, and yet it
can achieve results that are close to those achieved by statistical
prediction methods that make the far stronger (and often
unjustified) assumption that the sequence to be predicted is
stationary.

Topics:
Derivation of AA, and proof of upper bounds on relative
loss. Extension of AA to bandit problems.
Applications of AA to leastsquares regression, choice of investment portfolios, and
choice of optimal hypothesis complexity.

Support Vector Machines

Learning in Bayesian Belief Networks
 Overview:
An introduction to the representation of independence assumptions
as networks, and to the propagation of probabilities by local
computations on these networks, leading to learning algorithms for
finding belief networks empirically from data.

Topics:
Probabilistic and graphical representations; algorithms on tree
structures; learning algorithms; practical implementations and case
studies.

Reinforcement Learning
 Overview:
Reinforcement learning is a method of learning control policies from
experience. It can be regarded as a method of dynamic programming
using a MonteCarlo method.

Topics
Dynamic programming and control. Temporal difference estimation.
Qlearning and realtime dynamic programming. Linear
estimation of optimal value functions in optimal stopping problems.
Applications of
reinforcement learning to scheduling and control problems in
operational research.

The uniform convergence approach to statistical learning

Overview:
This session is an introduction to Vapnik's nonBayesian approach to statistical
learning. Given a set of possible statistical models, the approach is
to construct an a priori uniform bound on the rate of
convergence of the empirical losses of hypotheses in the set to their true
values. The VapnikChervonenkis dimension, and the basic proof techniques and core theorems will be covered
in some detail.

Topics:
VapnikChervonenkis dimension, uniform bounds on empirical losses,
structural risk minimisation, generalisation of the VC dimension
for realvalued function classes.

Data dependent generalisation and boosting

Overview:
An introduction to bounds on generalisation error that depend on the
data actually observed.
A technique known as ``boosting'' for constructing classification
rules appears remarkably effective in practice. The most convincing
explanation for the effectiveness of boosting is that it is from
datadependent bounds on generalisation error.

Topics: Data dependent bounds, boosting.
In addition to weekly question sheets which will form the basis of the
tutorial sessions, there will be two substantial assessed pieces of
coursework as follows:
Implementation of AA for a finite number of experts, and application
to a selected data set.
Practical use of SVM, including nonlinear PCA and a comparison of
different kernels, applied to a selected data set.
A. Gammerman, V.N. Vapnik, V. Vovk, C. Watkins

Ming Li and Paul Vitanyi, An Introduction to Kolmogorov
Complexity and its Applications, Springer

Vladimir Vapnik, The Nature of Statistical Learning Theory,
Springer

Judea Pearl, Probabilistic Reasoning in Intelligent Systems, 1995
Back to MSc by Research in Computer Science Home Page
Last updated
Fri, 23Jan2009 15:12
GMT / PS
•
•
Department of Computer Science,
University of London,
Egham,
Surrey TW20 0EX
Tel/Fax : +44 (0)1784 443421
/439786