Information Theory, Inference and Learning Algorithms

Cover......Page 1
Title Page......Page 3
Contents......Page 5
How to use this book......Page 7
About this edition......Page 13
Acknowledgments......Page 14
About Chapter 1......Page 15
1.1 How can we achieve perfect communication over an imperfect, noisy communication channel?......Page 17
1.2 Error-correcting codes for the binary symmetric channel......Page 19
1.3 What performance can the best codes achieve?......Page 28
1.4 Summary......Page 29
1.6 Solutions......Page 30
2.1 Probabilities and ensembles......Page 36
2.2 The meaning of probability......Page 39
2.3 Forward probabilities and inverse probabilities......Page 41
2.4 Definition of entropy and related functions......Page 46
2.5 Decomposability of the entropy......Page 47
2.6 Gibbs’ inequality......Page 48
2.7 Jensen’s inequality for convex functions......Page 49
2.8 Exercises......Page 50
2.9 Further exercises......Page 52
2.10 Solutions......Page 54
About Chapter 3......Page 61
3.1 A first inference problem......Page 62
3.2 The bent coin......Page 65
3.3 The bent coin and model comparison......Page 66
3.4 An example of legal evidence......Page 69
3.5 Exercises......Page 71
3.6 Solutions......Page 73
Part I: Data Compression......Page 79
About Chapter 4......Page 80
4.1 How to measure the information content of a random variable?......Page 81
4.2 Data compression......Page 87
4.3 Information content defined in terms of lossy compression......Page 88
4.4 Typicality......Page 92
4.5 Proofs......Page 95
4.6 Comments......Page 97
4.7 Exercises......Page 98
4.8 Solutions......Page 100
About Chapter 5......Page 104
5 Symbol Codes......Page 105
5.1 Symbol codes......Page 106
5.2 What limit is imposed by unique decodeability?......Page 108
5.3 What’s the most compression that we can hope for?......Page 111
5.5 Optimal source coding with symbol codes: Huffman coding......Page 112
5.6 Disadvantages of the Huffman code......Page 114
5.8 Exercises......Page 116
5.9 Solutions......Page 118
About Chapter 6......Page 123
6.1 The guessing game......Page 124
6.2 Arithmetic codes......Page 125
6.3 Further applications of arithmetic coding......Page 132
6.4 Lempel–Ziv coding......Page 133
6.5 Demonstration......Page 135
6.6 Summary......Page 136
6.7 Exercises on stream codes......Page 137
6.8 Further exercises on data compression......Page 138
6.9 Solutions......Page 141
Solution to exercise 6.22 (p.127)......Page 146
Part II: Noisy-Channel Coding......Page 151
8.1 More about entropy......Page 152
8.2 Exercises......Page 154
8.3 Further exercises......Page 155
8.4 Solutions......Page 156
About Chapter 9......Page 159
9.1 The big picture......Page 160
9.3 Noisy channels......Page 161
9.4 Inferring the input given the output......Page 162
9.5 Information conveyed by a channel......Page 163
9.6 The noisy-channel coding theorem......Page 165
9.7 Intuitive preview of proof......Page 167
9.8 Further exercises......Page 169
9.9 Solutions......Page 171
About Chapter 10......Page 175
10.2 Jointly-typical sequences......Page 176
10.3 Proof of the noisy-channel coding theorem......Page 178
10.4 Communication (with errors) above capacity......Page 181
10.5 The non-achievable region (part 3 of the theorem)......Page 182
10.6 Computing capacity......Page 183
10.7 Other coding theorems......Page 185
10.9 Further exercises......Page 186
10.10 Solutions......Page 187
About Chapter 11......Page 190
11.1 The Gaussian channel......Page 191
11.3 Capacity of Gaussian channel......Page 193
11.4 What are the capabilities of practical error-correcting codes?......Page 197
11.5 The state of the art......Page 200
11.8 Errors other than noise......Page 201
11.9 Exercises......Page 202
11.10 Solutions......Page 203
Part III: Further Topics in Information Theory......Page 205
About Chapter 12......Page 206
12.1 The information-retrieval problem......Page 207
12.2 Hash codes......Page 209
12.3 Collision resolution......Page 211
12.5 Other roles for hash codes......Page 212
12.6 Further exercises......Page 215
12.7 Solutions......Page 216
About Chapter 13......Page 219
13.2 Obsession with distance......Page 220
13.3 Perfect codes......Page 222
13.4 Perfectness is unattainable – first proof......Page 224
13.5 Weight enumerator function of random linear codes......Page 225
13.6 Berlekamp’s bats......Page 227
13.7 Concatenation of Hamming codes......Page 228
13.8 Distance isn’t everything......Page 229
13.10 Dual codes......Page 230
13.11 Generalizing perfectness to other channels......Page 233
13.13 Further exercises......Page 234
13.14 Solutions......Page 237
About Chapter 14......Page 242
14.1 A simultaneous proof of the source coding and noisy-channel coding theorems......Page 243
14.2 Data compression by linear hash codes......Page 245
15 Further Exercises on Information Theory......Page 247
Solutions......Page 253
16.1 Counting......Page 255
16.2 Path-counting......Page 258
16.3 Finding the lowest-cost path......Page 259
16.5 Further exercises......Page 260
16.6 Solutions......Page 261
17.1 Three examples of constrained binary channels......Page 262
17.2 The capacity of a constrained noiseless channel......Page 264
17.3 Counting the number of possible messages......Page 265
17.5 Practical communication over constrained channels......Page 268
17.6 Variable symbol durations......Page 270
17.7 Solutions......Page 271
18.1 Crosswords......Page 274
18.2 Simple language models......Page 276
18.3 Units of information content......Page 278
18.4 A taste of Banburismus......Page 279
18.5 Exercises......Page 282
19 Why have Sex? Information Acquisition and Evolution......Page 283
19.1 The model......Page 284
19.2 Rate of increase of fitness......Page 285
19.3 The maximal tolerable mutation rate......Page 289
19.4 Fitness increase and information acquisition......Page 290
19.5 Discussion......Page 291
19.6 Further exercises......Page 293
19.7 Solutions......Page 294
Part IV: Probabilities and Inference......Page 295
About Part IV......Page 296
20 An Example Inference Task: Clustering......Page 298
20.1 K-means clustering......Page 299
20.3 Conclusion......Page 303
20.4 Exercises......Page 304
20.5 Solutions......Page 305
21.1 The burglar alarm......Page 307
21.2 Exact inference for continuous hypothesis spaces......Page 309
22.1 Maximum likelihood for one Gaussian......Page 314
22.2 Maximum likelihood for a mixture of Gaussians......Page 316
22.3 Enhancements to soft K-means......Page 317
22.4 A fatal flaw of maximum likelihood......Page 319
22.5 Further exercises......Page 320
22.6 Solutions......Page 324
23.1 Distributions over integers......Page 325
23.2 Distributions over unbounded real numbers......Page 326
23.3 Distributions over positive real numbers......Page 327
23.4 Distributions over periodic variables......Page 329
23.5 Distributions over probabilities......Page 330
23.6 Further exercises......Page 332
24.1 Inferring the mean and variance of a Gaussian distribution......Page 333
24.3 Solutions......Page 337
25.1 Decoding problems......Page 338
25.2 Codes and trellises......Page 340
25.3 Solving the decoding problems on a trellis......Page 341
25.4 More on trellises......Page 345
25.5 Solutions......Page 347
26.1 The general problem......Page 348
26.2 The sum–product algorithm......Page 350
26.3 The min–sum algorithm......Page 353
26.5 Exercises......Page 354
27 Laplace’s Method......Page 355
27.1 Exercises......Page 356
28.1 Occam’s razor......Page 357
28.2 Example......Page 365
28.3 Minimum description length (MDL)......Page 366
Further reading......Page 367
28.4 Exercises......Page 368
About Chapter 29......Page 370
29.1 The problems to be solved......Page 371
29.2 Importance sampling......Page 375
29.3 Rejection sampling......Page 378
29.4 The Metropolis–Hastings method......Page 379
29.5 Gibbs sampling......Page 384
29.6 Terminology for Markov chain Monte Carlo methods......Page 386
29.7 Slice sampling......Page 388
29.9 Further practical issues......Page 393
29.10 Summary......Page 395
29.11 Exercises......Page 396
29.12 Solutions......Page 398
30.1 Hamiltonian Monte Carlo......Page 401
30.2 Overrelaxation......Page 404
30.4 Skilling’s multi-state leapfrog method......Page 406
30.5 Monte Carlo algorithms as communication channels......Page 408
30.6 Multi-state methods......Page 409
30.8 Further exercises......Page 411
30.9 Solutions......Page 412
About Chapter 31......Page 413
31 Ising Models......Page 414
31.1 Ising models – Monte Carlo simulation......Page 416
31.2 Direct computation of partition function of Ising models......Page 421
31.3 Exercises......Page 426
32.2 Exact sampling concepts......Page 427
32.3 Exact sampling from interesting distributions......Page 432
Further reading......Page 433
32.4 Exercises......Page 434
32.5 Solutions......Page 435
33.1 Variational free energy minimization......Page 436
33.2 Variational free energy minimization for spin systems......Page 438
33.3 Example: mean field theory for the ferromagnetic Ising model......Page 440
33.4 Variational methods in inference and data modelling......Page 441
33.5 The case of an unknown Gaussian: approximating the posterior distribution of μ and σ......Page 443
33.6 Interlude......Page 445
33.7 K-means clustering and the expectation–maximization algorithm as a variational method......Page 446
33.8 Variational methods other than free energy minimization......Page 447
33.9 Further exercises......Page 448
33.10 Solutions......Page 449
34.2 The generative model for independent component analysis......Page 451
34.3 A covariant, simpler, and faster learning algorithm......Page 454
Further reading......Page 457
34.4 Exercises......Page 458
35.1 What do you know if you are ignorant?......Page 459
35.2 The Luria–Delbruck distribution¨......Page 460
35.3 Inferring causation......Page 461
35.4 Further exercises......Page 462
35.5 Solutions......Page 463
36.1 Rational prospecting......Page 465
36.2 Further reading......Page 467
36.3 Further exercises......Page 468
37 Bayesian Inference and Sampling Theory......Page 471
37.1 A medical example......Page 472
37.2 Dependence of p-values on irrelevant information......Page 476
37.3 Confidence intervals......Page 478
37.4 Some compromise positions......Page 479
37.5 Further exercises......Page 480
Part V: Neural networks......Page 481
38.1 Memories......Page 482
38.2 Terminology......Page 484
39.1 The single neuron......Page 485
39.2 Basic neural network concepts......Page 486
39.3 Training the single neuron as a binary classifier......Page 489
39.4 Beyond descent on the error function: regularization......Page 493
39.5 Further exercises......Page 494
Problems to look at before Chapter 40......Page 496
40.2 The capacity of a single neuron......Page 497
40.3 Counting threshold functions......Page 499
40.4 Further exercises......Page 504
40.5 Solutions......Page 505
41.1 Neural network learning as inference......Page 506
41.3 Beyond optimization: making predictions......Page 507
41.4 Monte Carlo implementation of a single neuron......Page 510
41.5 Implementing inference with Gaussian approximations......Page 515
Postscript on Supervised Neural Networks......Page 518
42.1 Hebbian learning......Page 519
42.2 Definition of the binary Hopfield network......Page 520
42.4 Convergence of the Hopfield network......Page 521
42.6 The continuous-time continuous Hopfield network......Page 524
42.7 The capacity of the Hopfield network......Page 526
42.8 Improving on the capacity of the Hebb rule......Page 529
42.9 Hopfield networks for optimization problems......Page 530
42.10 Further exercises......Page 533
42.11 Solutions......Page 534
43.1 From Hopfield networks to Boltzmann machines......Page 536
43.2 Boltzmann machine with hidden units......Page 539
43.3 Exercise......Page 540
44.1 Multilayer perceptrons......Page 541
44.2 How a regression network is traditionally trained......Page 542
44.3 Neural network learning as inference......Page 543
44.4 Benefits of the Bayesian approach to supervised feedforward neural networks......Page 544
44.5 Exercises......Page 546
About Chapter 45......Page 548
45 Gaussian Processes......Page 549
45.1 Standard methods for nonlinear regression......Page 550
45.2 From parametric models to Gaussian processes......Page 554
45.3 Using a given Gaussian process model in regression......Page 556
45.4 Examples of covariance functions......Page 557
45.5 Adaptation of Gaussian process models......Page 559
45.7 Discussion......Page 561
46.1 Traditional image reconstruction methods......Page 563
46.3 Deconvolution in humans......Page 566
46.4 Exercises......Page 568
Part VI: Sparse Graph Codes......Page 569
About Part VI......Page 570
47.2 Practical decoding......Page 571
47.3 Decoding with the sum–product algorithm......Page 573
47.4 Pictorial demonstration of Gallager codes......Page 576
47.5 Density evolution......Page 580
47.6 Improving Gallager codes......Page 581
47.7 Fast encoding of low-density parity-check codes......Page 583
47.8 Further reading......Page 585
47.10 Solutions......Page 586
48.2 Linear-feedback shift-registers......Page 588
48.3 Decoding convolutional codes......Page 592
48.4 Turbo codes......Page 593
48.6 Solutions......Page 595
49.2 Graph......Page 596
49.3 Decoding......Page 597
49.5 Generalized parity-check matrices......Page 598
About Chapter 50......Page 602
50 Digital Fountain Codes......Page 603
50.1 A digital fountain’s encoder......Page 604
50.3 Designing the degree distribution......Page 605
50.4 Applications......Page 607
50.5 Further exercises......Page 608
50.7 Conclusion......Page 610
Part VII: Appendices......Page 611
A Notation......Page 612
B.1 About phase transitions......Page 615
C.1 Finite field theory......Page 619
C.2 Eigenvectors and eigenvalues......Page 620
C.3 Perturbation theory......Page 622
C.4 Some numbers......Page 626
Bibliography......Page 627
Index......Page 634