Information theory, inference, and learning algorithms

Contents......Page 3
1 Introduction to Information Theory......Page 15
2 Probability, Entropy, and Inference......Page 34
3 More about Inference......Page 60
I Data Compression......Page 77
4 The Source Coding Theorem......Page 79
5 Symbol Codes......Page 103
6 Stream Codes......Page 122
7 Codes for Integers......Page 144
II Noisy-Channel Coding......Page 149
8 Correlated Random Variables......Page 150
9 Communication over a Noisy Channel......Page 158
10 The Noisy-Channel Coding Theorem......Page 174
11 Error-Correcting Codes and Real Channels......Page 189
III Further Topics in Information Theory......Page 203
12 Hash Codes: Codes for Efficient Information Retrieval......Page 205
13 Binary Codes......Page 218
14 Very Good Linear Codes Exist......Page 241
15 Further Exercises on Information Theory......Page 245
16 Message Passing......Page 253
17 Communication over Constrained Noiseless Channels......Page 260
18 Crosswords and Codebreaking......Page 272
19 Why have Sex? Information Acquisition and Evolution......Page 281
IV Probabilities and Inference......Page 294
20 An Example Inference Task: Clustering......Page 296
21 Exact Inference by Complete Enumeration......Page 305
22 Maximum Likelihood and Clustering......Page 312
23 Useful Probability Distributions......Page 323
24 Exact Marginalization......Page 331
25 Exact Marginalization in Trellises......Page 336
26 Exact Marginalization in Graphs......Page 346
27 Laplace’sMethod......Page 353
28 Model Comparison and Occam's Razor......Page 355
29 Monte Carlo Methods......Page 369
30 Efficient Monte Carlo Methods......Page 399
31 Ising Models......Page 412
32 Exact Monte Carlo Sampling......Page 425
33 Variational Methods......Page 434
34 Independent Component Analysis and Latent Variable Modelling......Page 449
35 Random Inference Topics......Page 457
36 Decision Theory......Page 463
37 Bayesian Inference and Sampling Theory......Page 469
V Neural networks......Page 479
38 Introduction to Neural Networks......Page 480
39 The Single Neuron as a Classifier......Page 483
40 Capacity of a Single Neuron......Page 495
41 Learning as Inference......Page 504
42 Hopfield Networks......Page 517
43 Boltzmann Machines......Page 534
44 Supervised Learning in Multilayer Networks......Page 539
45 Gaussian Processes......Page 547
46 Deconvolution......Page 561
VI Sparse Graph Codes......Page 567
47 Low-Density Parity-Check Codes......Page 569
48 Convolutional Codes and Turbo Codes......Page 586
49 Repeat Accumulate Codes......Page 594
50 Digital Fountain Codes......Page 601
VII Appendices......Page 609
A Notation......Page 610
B Some Physics......Page 613
C Some Mathematics......Page 617
Bibliography......Page 625
Index......Page 632