Information Theory and Machine Learning

Research activity report, 1998 - David MacKay

Error-correcting codes

The fundamental problem of information theory is to communicate reliably over an unreliable, noisy channel. We wish to do this while adding the smallest possible redundancy to the transmitted message, and without requiring astronomical computational resources at the encoder or decoder.

Our research in this area in collaboration with Neal, Frey and McEliece in Canada and USA has been outstandingly successful. DJCM's paper on low density parity check codes is called `a landmark paper' by one of the IEEE's referees, and Matthew Davey, extending and developing these codes, has created the best known error correcting code (as of June 1998) (i.e., it can communicate over a Gaussian noise channel using a smaller signal to noise ratio than any other code). Matthew Davey and DJCM have published 3 papers (one in a refereed journal), and DJCM has coauthored five other papers with other collaborators in the last 3 years.

I am hoping to secure industrial funding for further research in this area. Future directions include applying our record breaking ideas to other error-correcting codes and exploring the use of our codes in specific applications such as mobile telephony.

Simon Wilson has worked on related error correcting codes and is also investigating the application of the decoding algorithm to other inference problems such as medical disease diagnosis.

Empirical Modelling of non-linear relationships

Latent variable models

One problem in machine learning is to discover hidden variables that are presumed to underlie visible data. Two students in my group have worked on the following problems.

Human-computer interfaces

A new project aims to combine an adaptive language model with an adaptive gesture-tracker so as to allow the user efficiently to convey text or commands to a computer. DJCM wrote a prototype interface in December 1997 and industrial support is currently being sought.

Teaching Physics

Sanjoy Mahajan will join our group in August and will continue his work on `how to teach so that the student retains an understanding of physics in ten years time'.
David MacKay <>
Last modified: Thu Jun 3 14:36:07 1999