Information Theory, Inference, and Learning Algorithms

Textbook by David J.C. MacKay

Published by Cambridge University Press, 2003.

In 2003 this book will be published by CUP.
It will continue to be available from this website for on-screen viewing.

Want to give feedback on the book, or report typos?

Cambridge students might wish to look at the course website for Information Theory, Pattern Recognition, and Neural Networks

Want to ask a question?

Order your copy

Price: £30.00 / $50.00 from |CUP UK/USA| |amazon.co.uk/.com/.ca/.co.jp| |Barnes and Noble USA | fetchbook.info | allbookstores | walmart | biggerbooks | blackwells |

Best buy (US) - Barnes and Noble, $35.00 | Blackwells, UKP:28.50

Download the book too

You may download The book in one file (640 pages):

	Cambridge U.K.		Toronto Canada
PDF (A4)	pdf (9M)		pdf mirror
Postscript (A4)	postscript (5M)		postscript mirror
DJVU	djvu file, Cambridge (6M)		djvu file
	(djvu information | Download djView)
Just the words	(latex) [provided for convenient searching] (2.4M)		(latex mirror)
Individual chapters	postscript and pdf available from this page		mirror

Notes:

• Draft 6.0 was released Thu 26/6/03; the book is finished. You are welcome to view the book on-screen.

Copyright issues: The book is copyright (c) Cambridge University Press. You can buy it from September 2003. The price will be 30 pounds (UK) and $50 (USA).

Now the book is published, these files will remain viewable on this website. The same copyright rules will apply to the online copy of the book as apply to normal books. [e.g., copying the whole book onto paper is not permitted.]

History:
Draft 1.1.1 - March 14 1997.
Draft 1.2.1 - April 4 1997.
Draft 1.2.3 - April 9 1997.
Draft 1.2.4 - April 10 1997. Margins altered so as to print better on Northamerican paper
Draft 1.3.0 - December 23 1997.
Draft 1.9.0 - Feb 1 1999.
Draft 2.0.0 - Jan 6 2000. New page layout.
Draft 2.2.0 - Dec 23 2000. Fresh draft.
Draft 3.1415 - Jan 12 2003. Nearly finished.
Draft 4.0 - April 15 2003. Chapter sequence finalized.
Draft 4.1 - April 18 2003. Adding new frontmatter (Preface etc)to book. Corrected printing of letter version.
Version 6.0 - Thu 26 June 2003. Final version.

• Here is my method for converting to two-up under linux:
  

  pstops '4:0L@.67(20cm,1cm)+1L@.67(20cm,15cm),3R@.67(1cm,15.25cm)\
  +2R@.67(1cm,29.25cm)' $*.ps $*.dps 

(Shorter versions of the jacket blurb)

Endorsements by famous people

Endorsements by users

David Lindsay, Computer Learning Research Centre (www.clrc.rhul.ac.uk)

I am compelled to state categorically that this is one of the finest text books I have read on these subjects. I have even pilfered some of the material for use in my classes.

Samir Chettri, UMBC

Full blurb from back cover

Alternate blurbs

Jacket blurb (215 words)

Information theory and inference, often taught separately, are here united in one entertaining textbook. These topics lie at the heart of many exciting areas of contemporary science and engineering -- communication, signal processing, data mining, machine learning, pattern recognition, computational neuroscience, bioinformatics, and cryptography.

This textbook introduces theory in tandem with applications. Information theory is taught alongside practical communication systems, such as arithmetic coding for data compression and sparse-graph codes for error-correction. A toolbox of inference techniques, including message-passing algorithms, Monte Carlo methods, and variational approximations, are developed alongside applications of these tools to clustering, convolutional codes, independent component analysis, and neural networks.

The final part of the book describes the state of the art in error-correcting codes, including low-density parity-check codes, turbo codes, and digital fountain codes -- the twentyfirst-century standards for satellite communications, disk drives, and data broadcast.

Richly illustrated, filled with worked examples and over 400 exercises, some with detailed solutions, the book is ideal for self-learning and for undergraduate or graduate courses. Interludes on crosswords, evolution, and sex provide entertainment along the way.

The result is a textbook on information, communication, and coding for a new generation of students, and an unparalleled entry point into these subjects for professionals in areas as diverse as computational biology, financial engineering, and machine learning.

old jacket blurb

Information theory, probabilistic reasoning, coding theory and algorithmics lie at the heart of some of the most exciting areas of contemporary science and engineering. They are integral to such areas as communication, signal processing, data mining, machine learning, pattern recognition, computational neuroscience, bioinformatics, and cryptography. David MacKay breaks new ground in this exciting and entertaining textbook by introducing mathematical technology in tandem with applications, providing at once both motivation and hands-on guidance for problem-solving and modelling. For example, he covers not only the theoretical foundations of information theory, but practical methods for communication systems, including arithmetic coding for practical data compression, and low-density parity-check codes for reliable communication over noisy channels. The duality between communication and machine learning is illustrated through data modelling and compression; machine learning is also represented by clustering, classification, feedforward networks, Hopfield networks, Boltzmann machines and independent component analysis. A toolbox of probabilistic techniques are covered in detail: message-passing, Monte Carlo, and variational methods. The final part of the book, on sparse graph codes, describes the state-of-the-art in error-correcting codes, including chapters on low-density parity-check codes, turbo codes, and digital fountain codes. There are over 390 exercises, some with full solutions, which, together with worked examples, extend the text and enhance technique and understanding. A profusion of illustrations enliven and complement the text. Interludes on crosswords, evolution, and sex provide entertaining glimpses on unconventional applications. In sum, this is a textbook for courses in information, communication and coding for a new generation of students, and an unparalleled entry point to these subjects for professionals working in areas as diverse as computational biology, data mining, financial engineering and machine learning.

150 word blurb

90 word blurb

50 word blurb

This exciting and entertaining textbook is ideal for courses in information, communication and coding for a new generation of students, and an unparalleled entry point to these subjects for professionals working in areas as diverse as computational biology, datamining, financial engineering and machine learning.

Another old short blurb

Yet another old blurb

• 400x300 (tif)
• 800x600 (gif)
• 1600x1200 (gif)
• 2400x1800 (gif)
• 2400x1800 (tif) <---
• 3200x2400 (gif)

Errors in the book

I would be grateful to hear about errors in the book.

A list of corrections is provided.

Please send me new corrections by email. Thank you!

The tcl programs and other links marked (*) can be run directly in netscape if you have got the tcl/tk plugin. You can also run the tcl programs in the normal way if you have a linux machine with X windows and tcl and you download the tcl files then execute them (this is preferable to the netscape approach, I think). [The top four lines of each tcl file contain flags which change the program from working with the netscape plugin to working alone under X.] The other programs can be used by people on unix systems that have the relevant software (perl, gnuplot, octave.)

• about Octave

Please select a software category from the sidebar.

Information theory, coding theory, source coding

• (*) Demonstration of iterative probabilistic decoding
• (*) Hamming (7,4) code demonstration (tcl)
• `Submarine' (tcl)
• `Mine Hunt' (tcl)
• (*) Demonstration of Typical Set concept (tcl)
• Perl program that creates Huffman codes
• (*) Symbol code demonstration (tcl)
• old Huffman code demonstration (tcl)
• old Huffman code demonstration (tcl) (can also be used to demonstrate arbitrary symbol codes)
• (*) Arithmetic coding demonstration (tcl)

  Note: this demonstration and the above Symbol code demonstration allow you to compare a simple arithmetic code with a Huffman code for English, both optimized on the same data.
  See also the Dasher project.

• (*) Gibbs Inequality demonstration (tcl)
• (*) Mutual information computer: make arbitrary noisy channels and find their I(X;Y) as you vary the input distribution P(x)
• Some notes on the "iTap" code for English.

The tcl programs and other links marked (*) can be run directly in netscape if you have got the tcl/tk plugin. You can also run the tcl programs in the normal way if you have a linux machine with X windows and tcl and you download the tcl files then execute them (this is preferable to the netscape approach, I think). [The top four lines of each tcl file contain flags which change the program from working with the netscape plugin to working alone under X.] The other programs can be used by people on unix systems that have the relevant software (perl, gnuplot, octave.)

• about Octave

Inference methods

• Inferring the (mu,sigma) of a Gaussian distribution by complete enumeration (uses gnuplot)
• Monte Carlo: demonstration of importance sampling, rejection sampling, metropolis method and slice sampling
(uses octave)
• Gibbs sampling - Inferring the (mu,sigma) of a Gaussian distribution or a mixture of Gaussians (uses octave)
• Markov Chain Monte Carlo: demonstration of the Metropolis method (uses perl (version 4) and gnuplot)
• Markov Chain Monte Carlo: demonstration of the Overrelaxation method
• Markov Chain Monte Carlo: Hybrid Monte Carlo demo (fit.tar)
• EXACT SAMPLING:
  • D. B. Wilson's annotated bibliography of articles on exact sampling with Markov chains
  • An exact sampling project done by two undergrads from Caltech and me
• Radford Neal's website has lots of materials on Monte Carlo methods.
• about Octave

The tcl programs and other links marked (*) can be run directly in netscape if you have got the tcl/tk plugin. You can also run the tcl programs in the normal way if you have a linux machine with X windows and tcl and you download the tcl files then execute them (this is preferable to the netscape approach, I think). [The top four lines of each tcl file contain flags which change the program from working with the netscape plugin to working alone under X.] The other programs can be used by people on unix systems that have the relevant software (perl, gnuplot, octave.)

• about Octave

Online Hamiltonian Monte Carlo Demo

(formerly known as `Hybrid Monte Carlo')

Task: sample from the posterior distribution of a bivariate Gaussian distribution given ten data points. The left-hand image shows the details underlying a sequence of HMC transitions. The right-hand image shows 50 of the successive states produced by the Markov chain - the endpoints of the trajectories.
   
fit.tar tar file giving octave source code.

Neural networks

• Training a single neuron as a classifier
• Hopfield network demonstration: Demonstration program (perl) and Data file. Save these as demo.p and dat.
• (*) Hopfield network demonstration 2000: tcl program for demonstrating Hebbian learning
• (*) Hopfield net for TSP demonstration (tcl) This demonstration shows how the Hopfield network is connected and you can run the network manually by changing the state of each neuron that is unstable (the net settles into the optimal solution).
• Training a multilayer neural network to do regression (octave)
• Gaussian processes (octave)
• Big neural nets: see Yann Le Cun's page | old
• Independent component analysis
• Radford Neal's website has lots of materials on neural networks.

The tcl programs and other links marked (*) can be run directly in netscape if you have got the tcl/tk plugin. You can also run the tcl programs in the normal way if you have a linux machine with X windows and tcl and you download the tcl files then execute them (this is preferable to the netscape approach, I think). [The top four lines of each tcl file contain flags which change the program from working with the netscape plugin to working alone under X.] The other programs can be used by people on unix systems that have the relevant software (perl, gnuplot, octave.)

• about Octave

• Statistical physics:
  (*) Bosons, Fermions, and Classical particles (tcl)

The tcl programs and other links marked (*) can be run directly in netscape if you have got the tcl/tk plugin. You can also run the tcl programs in the normal way if you have a linux machine with X windows and tcl and you download the tcl files then execute them (this is preferable to the netscape approach, I think). [The top four lines of each tcl file contain flags which change the program from working with the netscape plugin to working alone under X.] The other programs can be used by people on unix systems that have the relevant software (perl, gnuplot, octave.)

• about Octave

Dedication

My textbook is dedicated to the Campaign Against the Arms Trade

Food for thought...

• If Iran is only allowed to use nuclear facilities for civilian purposes, not bombs, surely the same should apply to other countries, such as the United Kingdom? This concept goes by the name of the Non-Proliferation Treaty: it states an `unequivocal undertaking to accomplish the total elimination of their nuclear arsenals'. Britain has signed this treaty. So why do we still have Trident? Support the Campaign for Nuclear Disarmament of all countries.

---

• Do you think people will love the United States more or less if they go ahead with this? - `United States planning to build an unmanned hypersonic aircraft capable of striking any target in the world within two hours'

---

• Who has got weapons of mass destruction? (February 2003)

---

• `Arms Kill Mothers and Children' - Children's Nurses and Doctors against the Exploitation of Poor countries through Arms trading - see also this article in the British Medical Journal by David Southall.
• What happened to justice? Why should non-US citizens be treated differently? All is explained, in simple terms.
• Conscience online provides a nice `tax return' for sending to the UK tax blokes. They point out that in the old days when millions of men were sent to wars, it was legal to be a conscientious objector. But now, when the government uses the taxes of millions of men and women to go and bomb places, there is no mechanism for those taxpayers to be objectors.
• What can we do? Stop Weapons Fairs

Any Questions?