David J C MacKay - Information theory, inference, and learning algorithms

Information Theory, Inference, and Learning Algorithms David J.C. MacKay mackay@mrao.cam.ac.uk c 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003 Draft 4.0 April 15, 2003 Please send feedback on this book via http://www.inference.phy.cam.ac.uk/mackay/itprnn/ About the exercises I rmly believe that one can only understand a subject by recreating it for oneself. To this end, I think it is essential to work through some exercises on each topic. For guidance, each exercise has a rating (similar to that used by Knuth (1968)) from 1 to 5 that indicates the level of diculty. In addition, exercises that are especially recommended are marked by a marginal encouraging rat . Exercises that require the use of a computer may be marked with a C.

Answers to many of the exercises are provided. Please use them wisely. (Where a solution is provided, this is indicated by including the page number of the solution with the diculty rating.) Summary of codes for exercises Especially recommended [1] Simple (one minute) [2] Medium (quarter hour) Recommended [3] Moderately hard C Some parts require a computer [4] Hard [p. 42] Solution provided on page 42 [5] Research project Roadmaps The diagrams on the following pages will indicate the dependencies between chapters and a few possible routes through the book. c David J.C. Draft 4.0. Draft 4.0.

April 15, 2003 Introduction to Information Theory IV Probabilities and Inference Probability, Entropy, and Inference An Example Inference Task: Clustering More about Inference Exact Inference by Complete Enumeration Maximum Likelihood and Clustering I Data Compression Useful Probability Distributions The Source Coding Theorem Exact Marginalization Symbol Codes Exact Marginalization in Trellises Stream Codes Exact Marginalization in Graphs An Aside: Codes for Integers Laplaces Method Model Comparison and Occams Razor II Noisy-Channel Coding Monte Carlo Methods Correlated Random Variables Ecient Monte Carlo Methods Communication over a Noisy Channel Ising Models The Noisy-Channel Coding Theorem Exact Monte Carlo Sampling Error-Correcting Codes and Real Channels Variational Methods Independent Component Analysis III Further Topics in Information Theory Random Inference Topics Hash Codes Decision Theory Binary Codes Bayesian Inference and Sampling Theory Very Good Linear Codes Exist Further Exercises on Information Theory V Neural networks Message Passing Introduction to Neural Networks Constrained Noiseless Channels The Single Neuron as a Classier Crosswords and Codebreaking Capacity of a Single Neuron Why have Sex? Learning as Inference Hopeld Networks Boltzmann Machines Supervised Learning in Multilayer Networks Gaussian Processes Deconvolution VI Sparse Graph Codes Low-Density Parity-Check Codes Convolutional Codes and Turbo Codes Repeat-Accumulate Codes c David J.C. MacKay. Draft 4.0. April 15, 2003 Digital Fountain Codes

Contents Introduction to Information Theory ............. Probability, Entropy, and Inference.............. 24 More about Inference ......................

I Data Compression......................... 71 The Source Coding Theorem.................. Symbol Codes ........................... Stream Codes ........................... Codes for Integers ........................ 149 Correlated Random Variables ................. 149 Correlated Random Variables .................

Communication over a Noisy Channel............ 10 The Noisy-Channel Coding Theorem............. 11 Error-Correcting Codes and Real Channels ........ III Further Topics in Information Theory............ 209 12 Hash Codes: Codes for Ecient Information Retrieval . 14 Very Good Linear Codes Exist................. 249 15 Further Exercises on Information Theory.......... 16 Message Passing.......................... 261 17 Communication over Constrained Noiseless Channels .. 18 An Aside: Crosswords and Codebreaking ......... 19 Why have Sex? Information Acquisition and Evolution . 19 Why have Sex? Information Acquisition and Evolution .

IV Probabilities and Inference................... 305 20 An Example Inference Task: Clustering........... 21 Exact Inference by Complete Enumeration......... 22 Maximum Likelihood and Clustering............. 23 Useful Probability Distributions................ c David J.C. MacKay. Draft 4.0. Draft 4.0.

April 15, 2003

25 Exact Marginalization in Trellises............... 350 26 Exact Marginalization in Graphs ............... 27 Laplaces Method ......................... 28 Model Comparison and Occams Razor ........... 29 Monte Carlo Methods ...................... 31 Ising Models ............................ 32 Exact Monte Carlo Sampling ................. 33 Variational Methods ....................... 34 Independent Component Analysis and Latent Variable Modelling.............................. 470 35 Random Inference Topics.................... 478 36 Decision Theory.......................... 484 37 Bayesian Inference and Sampling Theory.......... 484 37 Bayesian Inference and Sampling Theory..........

V Neural networks.......................... 501 38 Introduction to Neural Networks ............... 39 The Single Neuron as a Classier............... 505 40 Capacity of a Single Neuron .................. 41 Learning as Inference....................... 43 Boltzmann Machines....................... 557 44 Supervised Learning in Multilayer Networks........ 45 Gaussian Processes ........................ 46 Deconvolution ........................... 46 Deconvolution ...........................

VI Sparse Graph Codes....................... 591 47 Low-Density Parity-Check Codes............... 593 48 Convolutional Codes and Turbo Codes ........... 49 Repeat-Accumulate Codes ................... 50 Digital Fountain Codes ..................... 633 A Notation............................... 634 B Some Physics............................ 637 C Some Mathematiics........................ 641 Bibliography............................... 651 c David J.C. MacKay. Draft 4.0. Draft 4.0.

April 15, 2003 About Chapter 1 In the rst chapter, you will need to be familiar with the binomial distribution. And to solve the exercises in the text which I urge you to do you will need to know Stirlings approximation for the factorial function, x! xxex, and be able to apply it to N = N ! . These topics are reviewed below. Unfamiliar notation? r (N r)!r! See appendix A, p.634. The binomial distribution Example 1.1: A bent coin has probability f of coming up heads. The coin is tossed N times.

What is the probability distribution of the number of heads, r? What are the mean and variance of r? Solution: The number of heads has a binomial distribution. 0.3 0.25 0.2 N 0.15 P (r|f, N) = f r(1 f)Nr (1.1) 0.1 r 0.05 0 1 2 3 4 5 6 7 8 9 10 The mean, E[r], and variance, var[r], of this distribution are dened by r N P (r Figure 1.1. The binomial E[r] |f, N) r (1.2) r=0 distribution P (r|f=0.3, N=10). var[r] E (r E[r])2 (1.3) N = E[r2] (E[r])2 = P (r|f, N)r2 (E[r])2 . (1.4) r=0 Rather than evaluating the sums over r in (1.2) and (1.4) directly, it is easiest to obtain the mean and variance by noting that r is the sum of N independent random variables, namely, the number of heads in the rst toss (which is either zero or one), the number of heads in the second toss, and so forth. In general, E[x + y] = E[x] + E[y] for any random variables x and y; (1.5) var[x + y] = var[x] + var[y] if x and y are independent.

So the mean of r is the sum of the means of those random variables, and the variance of r is the sum of their variances. The mean number of heads in a single toss is f 1 + (1 f) 0 = f, and the variance of the number of heads in a single toss is f 12 + (1 f) 02 f 2 = f f 2 = f(1 f), (1.6) so the mean and variance of r are: E[r] = Nf and var[r] = N f (1 f). (1.7) c David J.C. MacKay. Draft 4.0. April 15, 2003 About Chapter 1 Approximating x! and Nr 0.12 Lets derive Stirlings approximation by an unconventional route.

Next page