Information theory, inference and learning algorithms

David MacKay breaks new ground in this entertaining textbook by giving a united introduction to information theory and inference. These topics lie at the heart of some of the most exciting areas of contemporary science and engineering - communication, signal processing, machine learning, and bioinformatics. Theory is presented in tandem with applications. For example, MacKay covers the theoretical foundations of information theory, and practical methods for communication systems. Communication and machine learning are linked through data modelling and compression. Over 400 exercises, some with full solutions, and nearly 40 worked examples are supplied. Enlivening and enlightening illustrations abound. 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 and financial engineering.

Advanced Praise:

This is an extraordinary and important book, generous with insight and rich with detail in statistics, information theory, and probabilistic modeling across a wide swathe of standard, creatively original, and delightfully quirky topics. David MacKay is an uncompromisingly lucid thinker, from whom students, faculty and practitioners all can learn.

Peter Dayan and Zoubin Ghahramani, Gatsby Computational Neuroscience Unit, University College, London

An utterly original book that shows the connections between such disparate fields as information theory and coding, inference, and statistical physics.

Dave Forney, Massachusetts Institute of Technology

An instant classic, covering everything from Shannon's fundamental theorems to the postmodern theory of LDPC codes. You'll want two copies of this astonishing book, one for the office and one for the fireside at home.

Bob McEliece, California Institute of Technology

Contents

• Introduction to information theory
• Probability, entropy, and inference
• More about inference
• Data Compression
  • The source coding theorem
  • Symbol codes
  • Stream codes
  • Codes for integers
• Noisy-Channel Coding
  • Correlated random variables
  • Communication over a noisy channel
  • The noisy-channel coding theorem
  • Error-correcting codes and real channels
• Further Topics in Information Theory
  • Hash codes: codes for efficient information retrieval
  • Binary codes
  • Very good linear codes exist
  • Further exercises on information theory
  • Message passing
  • Communication over constrained noiseless channels
  • Crosswords and codebreaking
  • Why have sex? Information acquisition and evolution
• Probabilities and Inference
  • An example inference task: clustering
  • Exact inference by complete enumeration
  • Maximum likelihood and clustering
  • Useful probability distributions
  • Exact marginalization
  • Exact marginalization in trellises
  • Exact marginalization in graphs
  • Laplace's method
  • Model comparison and Occam's razor
  • Monte Carlo methods
  • Efficient Monte Carlo methods
  • Ising models
  • Exact Monte Carlo sampling
  • Variational methods
  • Independent component analysis and latent variable modelling
  • Random inference topics
  • Decision theory
  • Bayesian inference and sampling theory
• Neural Networks
  • Introduction to neural networks
  • The single neuron as a classifier
  • Capacity of a single neuron
  • Learning as inference
  • Hopfield networks
  • Boltzmann machines
  • Supervised learning in multilayer networks
  • Gaussian processes
  • Deconvolution
• Sparse Graph Codes
  • Low-density parity-check codes
  • Convolutional codes and turbo codes
  • Repeat-accumulate codes
  • Digital fountain codes
• Appendices
  • Notation
  • Some physics
  • Some mathematics
• Bibliography
• Index