INFORMATION THEORY, INFERENCE, AND LEARNING ALGORITHMS
CONTENTS INTRODUCTION TO INFORMATION THEORY PROBABILITY, ENTROPY, AND INFERENCE MORE ABOUT INFERENCE I DATA COMPRESSION THE SOURCE CODING THEOREM SYMBOL CODES STREAM CODES CODES FOR INTEGERS II NOISY-CHANNEL CODING CORRELATED RANDOM VARIABLES COMMUNICATION OVER A NOISY CHANNEL THE NOISY-CHANNEL CODING THEOREM ERROR-CORRECTING CODES AND REAL CHANNELS III FURTHER TOPICS IN INFORMATION THEORY HASH CODES: CODES FOR E?CIENT 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 IV 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 E?CIENT MONTE CARLO METHODS ISING MODELS EXACT MONTE CARLO SAMPLING VARIATIONAL METHODS INDEPENDENT COMPONENT ANALYSIS AND LATENT VARIABLE MOD- ELLING RANDOM INFERENCE TOPICS DECISION THEORY BAYESIAN INFERENCE AND SAMPLING THEORY V NEURAL NETWORKS INTRODUCTION TO NEURAL NETWORKS THE SINGLE NEURON AS A CLASSI?ER CAPACITY OF A SINGLE NEURON LEARNING AS INFERENCE HOP?ELD 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 DIGITAL FOUNTAIN CODES ABOUT CHAPTER 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 STIRLING’S APPROXIMATION FOR THE FACTORIAL FUNCTION, X! ?XX E?X, AND BE ABLE TO APPLY IT TO N R = N! (N?R)!R! THESE TOPICS ARE REVIEWED BELOW UNFAMILIAR NOTATION? SEE APPENDIX A, P 598 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? 0 1 2 3 4 5 6 7 8 9 P(R | F, N)R2 ?(E[R])2 (1 4) 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; VAR[X + Y] = VAR[X] + VAR[Y] IF X AND Y ARE INDEPENDENT (1 5) 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 H F × 12 + (1 ?F) × 02I ?F 2 = F ?F 2 = F(1 ?F), (1 6) SO THE MEAN AND VARIANCE OF R ARE: E[R] = NF AND VAR[R] = NF(1 ?F) (1 7) APPROXIMATING X! AND N R R FIGURE 1 2 THE POISSON DISTRIBUTION P(R | ? = 15) LET’S DERIVE STIRLING’S APPROXIMATION BY AN UNCONVENTIONAL ROUTE WE START FROM THE POISSON DISTRIBUTION WITH MEAN ?, P(R | ?) = E?? ?R R! R ?{0, 1, 2, } (1 8) FOR LARGE ?, THIS DISTRIBUTION IS WELL APPROXIMATED – AT LEAST IN THE VICINITY OF R ?? – BY A GAUSSIAN DISTRIBUTION WITH MEAN ? AND VARIANCE ?: E?? ?R R! ? 2? (1 9) LET’S PLUG R = ? INTO THIS FORMULA E?? ?? ?! ? ? 2?? (1 10) ??! ? ?? E??? 2?? (1 11) THIS IS STIRLING’S APPROXIMATION FOR THE FACTORIAL FUNCTION X! ?XX E?X? 2?X ? LN X! ?X LN X ?X + 2 LN 2?X (1 12) WE HAVE DERIVED NOT ONLY THE LEADING ORDER BEHAVIOUR, X! ?XX E?X, BUT ALSO, AT NO COST, THE NEXT-ORDER CORRECTION TERM ? 2?X WE NOW APPLY STIRLING’S APPROXIMATION TO LN N R : LN N R ! ?LN N! (N ?R)!R! ? (N ?R) LN N N ?R + R LN N R (1 13) SINCE ALL THE TERMS IN THIS EQUATION ARE LOGARITHMS, THIS RESULT CAN BE REWRITTEN IN ANY BASE WE WILL DENOTE NATURAL LOGARITHMS (LOGE) BY ‘LN’, AND LOGARITHMS RECALL THAT LOG2 X = LOGE X LOGE 2 NOTE THAT ?LOG2 X ?X = LOGE X TO BASE 2 (LOG2) BY ‘LOG’ IF WE INTRODUCE THE BINARY ENTROPY FUNCTION, H2(X) ?X LOG X + (1?X) LOG (1?X), (1 14) THEN WE CAN REWRITE THE APPROXIMATION (1 13) AS H2(X)