----------------------------------------------------------------------------- Corrections for the first printing and second printing of Information Theory, Inference, and Learning Algorithms http://www.inference.phy.cam.ac.uk/mackay/itila/ [You can find out which printing your book is by looking at page xi, where a section `About this edition' was added in the second printing.] ----------------------------------------------------------------------------- Please email further corrections to mackay@mrao.cam.ac.uk Thanks! ----------------------------------------------------------------------------- This document has three sections: S1. FIRST PRINTING S2. FIRST AND SECOND PRINTING S3. SECOND PRINTING ----------------------------------------------------------------------------- S1. FIRST PRINTING ----------------------------------------------------------------------------- Corrections for the first printing of Information Theory, Inference, and Learning Algorithms http://www.inference.phy.cam.ac.uk/mackay/itila/ ----------------------------------------------------------------------------- p.ii Copyright notice: "(c) Cambrdige" should read "(c) Cambridge". p.3 Replace mmm by mm in section heading 1.1. p.29 probablities -> probabilities p.34 line 11 regretably -> regrettably p.46 occuring -> occurring p.48 contructing -> constructing p.49 Add labels $x$ and $\lambda$ respectively to the first two figures' horizontal axes. p.50 reproduceable -> reproducible p.61, and numerous other pages: occured -> occurred; occuring -> occurring p.66 pp.37-36 should read pp. 36-37 p.86 Curiousities -> curiosities p.92 line 5 punctutation -> punctuation p.97 end of sec 5.2 inquality -> inequality p.117 left hand side of eqs 6.11 and 6.12, $a$ should read $\tt a$; subscript P_L in 6.12 should be P_D p.125 last line probabilties -> probabilities p.129 center of page: probablity -> probability p.168 add label $R$ to x-axis. p.174 Fig 10.9 overhangs the right margin. The label $p_1$ is missing. p.188 Downgrade the rating of ex 11.7 from [5] to [4]. p.226 line 2. coresponding -> corresponding p.245 sec 16.3 Delete "." after algorithm p.248 orientiation -> orientation p.260 Crossword A line 3: BORB should read SORB. Line 12, YEA should read TEA. p.260 Delete "the" in the phrase: in the `word p.261 `previous page' should read `table 18.2' p.269 octupuses -> octopuses p.276 para 2. mutuation -> mutation p.278 line 7-8 parthonegens -> parthenogens p.280 line 11, replace "." by "?" p.335 The square boxes in the figure 26.1 have come out broken. p.337 The square boxes in the figure 26.4 have come out broken. p.343 artifical -> artificial p.383 Ex 29.16, line 12. Replace refeq.assignII by 22.22; and responsiblities -> responsibilities p.412 partitition -> partition p.418 Top paragraph. Replace 32.3b by 32.3a; 32.3(c,d) by 32.3(b,c); (c) by (b); and (d) by (c). p.430 line 2. denotes-> denote p.430 Equation (33.43) could be improved. Replace Q_sigma(sigma) by Q_sigma(beta) (twice in eq 33.43), and add to the text: "We represent Q_sigma(sigma) using the density over beta=1/sigma^2, Q_sigma(beta) \equiv Q_sigma(sigma) |d sigma/d beta|." p.436 Equation (33.61): add parentheses around the second two fractions on the right hand side. p.453 line 2 descision -> decision p.453 Add {$\sigma_n$} label to vertical axis fig 36.1. Add words "Contour plot of " to figure caption. p.463 Cut the word "probability" before two-tailed p.486 penultimate line: exisiting -> existing p.493 after eq 41.11 probabillity -> probability p.500 fig 41.9 caption evalutations -> evaluations p.518 fig 42.11 caption line 2 continous -> continuous p.548 comparision -> comparison p.554 Replace (Ratliff and L.A., 1950) by (Ratliff and Riggs, 1950) p.583 sec 49.3: multipled -> multiplied p.584 last line: diagramatic -> diagrammatic p.614 Childs et al reference: Add volume 63: 036113 p.615 Harvey and Neal reference: remove spurious "/" p.618 Ratliff reference details incorrect - should read: Ratliff, F. and Riggs, L. A. p.618 Ratzer, E. A., and MacKay, D. J. C. (missing initial) p.618 Rasmussen refs: (2000) eds: S.A. Solla and T.K. Leen and K.-R. M\"uller (2003) editor={Suzanna Becker and Sebastian Thrun and Klaus Obermayer} Thanks to --------- Atsushi Shimotani Iain Murray Ed Ratzer Chris Ball Aesthetic changes or improvements I would make if I edited the book again (All done, second printing, Mon 22/12/03) ------------------------------------------------------------------------- p.v machine-learning -> machine learning p.38 line 6 Change "results" to "is obtained". p.261 line 12. Cut the word "these" p.335 Too much space between x_n and ' p.iii, p. 435, p.572 Have tiny left margin problems. p.123 "the next few chapters" -> "Part II" p.171 Fig 10.8 caption missing "." p.182 Fig 11.5 axis is dotty. p.214 Realign figures with right margin. p.221 Realign fig 13.17 vertically. p.408 Fig 31.12 - grey fuzziness has appeared around the black dots. p.566 Line 3 overhangs right margin. Additions to the text --------------------------------- Chapter 19: Add a citation of @book{MarkRidley, title={Mendel's Demon: gene justice and the complexity of life}, publisher={Phoenix}, address={London}, year={2000}, author={Mark Ridley}, isbn={0753814102} } - another book that explains Kondrashov's theory of sex; it has as its theme `Who said that life forms had to be complex?'. In its second half, this super book addresses the question `why have sexes?' (i.e., why do most sexual organisms have males and females?) Additions to the index ---------------------- {correlated sources} p.236 \index{Slepian-Wolf|see{correlated sources}} Add "communication" to the index?! ==================================================================== S2. FIRST AND SECOND PRINTING ==================================================================== Corrections to the Second Printing (version 6.6, Mon 22/12/03) that also apply to the First Printing -------------------------------------------------------------------- Throughout: replace "c.f." by "cf." Five exercises have solutions, but the solution pointer (eg "p. 45") is lacking. The solutions in question are on p.45, 45, 46, 86, and 280. The exercises that should point to these destinations are exs 2.28 (p38), 2.29 (p38), 2.39 (p40), 4.2 (p68) and 19.1 (p275). p.33 eq 2.36: replace 1/|X| by 1/|A_X| p.37 ex 2.25: replace |X| by |A_X| three times p.42 After (2.67) replace (2.63-2.63) by (2.63-2.65). p.52 Middle of page Replace "that next toss is a" by "that the next toss is an". p.103 Ex 5.27. Line 1. Delete the word "binary". p.117 after eq (6.10) replace "and" by "and define" p.138 Chapter 8, "Correlated Random Variables", should have been called "Dependent Random Variables", and the word "correlated" should be "dependent" throughout that chapter. p.152 In theorem (part one): insert space between `,' and `there'. p.159 Eq 9.51: log should be ln (twice). p.166 After eq 10.17: P_ERR should be P_TOT. p.168 hypthenate " rate-R' " after Asymptotically. p.174 eq 10.28: insert "partial" operator before each p_i on left hand side. p.190 Add rating "2" to ex. 11.10. p.206 I used the word "minimum" when I should have used "maximum" in six bizarre and embarrassing places in this chapter! p.206 Example 13.1 line 2. minimum -> maximum p.206 Sec 13.2 line 1. minimum -> maximum p.212 Second Definition, line 1. minimum -> maximum p.212 fig 13.9 Caption: Three times! minimum -> maximum p.210 Sec 13.4 line 6: typically by -> typically be p.215 Sec 13.8, last paragraph, line 2: must at least than -> must be at least p.218 7 lines from bottom: insert "the" before "overlap". p.237 Fig 15.2 Caption, "correlated sources" -> "dependent sources" p.245, 4th line from the last, "edge H-K" should be "edge I-K". p.257 line 13: change kT to -kT p.257 line 16: replace "trellis section" by "connection matrix". p.257 line 2 from bottom: insert "be" before "encoded". p.261 Before eqn 18.4, insert "approximately" p.261 eqns 18.5,6 Replace subscripts l by 1 in f_l, twice. p.261 eqns 18.6,7 Replace H_w by H_W p.261 eqn 18.5 Delete \log \beta^{f_w S} |T| at end of r.h.s. p.261 I might add the following cautionary comment to this calculation: The calculation of the number of valid Wenglish crosswords on page 261 underestimates this number by counting only `typical' crosswords. It is likely that atypical fillings-in of the crossword dominate the true count. p.261 Second to last paragraph: replace "previous page" by "table 18.2". p.278 Fig 19.5 caption: final sentence should read: "Vertical axes show the fitnesses of the two sub-populations, and the percentage of the population that is parthenogenetic." (I should replot the top left figure to make the parthen fitness clearer.) p.279 line 12. Insert "a" before "highly". p.286 Line 8: r_nk should be r_k^{(n)}. p 301, line 5. Replace comma by full stop. p.301 Fig 22.1 Caption. Add, at end of (c): "(shown as a density over $\ln \sigma$)" p 303, 7th line of sec 22.3: cut "figure 20.8 and" p.303 Line after the data figure, delete the symbol "L" p.311 Chapter 23: all occurrences of log should be changed to ln (natural log) p 317, Figure 23.8 caption: should say $p_3 = 1 - (p_1+p_2)$. [$p_1+p_2+p_3=1$] p.318. Entropic distribution (23.35) is wrong, it's missing the measure. Replace eq (23.35) by: P(\bp | \a,\bm) = \frac{1}{Z(\a,\bm)} \exp [ - \a D_{\rm KL}(\p||\bm) ] \delta \! \left( \sum_i p_i - 1 \right) , where $\bm$, the measure, is a positive vector, and $D_{\rm KL}(\bp||\bm) = \sum_i p_i \log p_i/m_i$. p.321 Fig 24.1 Caption. Add, at end of (c): "(shown as a density over $\ln \sigma$)" p 321, fig 24.1 last two lines of caption: Delete ", sigma". And add: (Both probabilities are shows as densities over $\ln \sigma$.) p.326 eq 25.9 Replace =1 by =0 p.330 First Line after Ex 25.5: replace alpha_i by alpha_I. Last line of Ex 25.7: delete the symbol $n$ after "subsequent". p.335 Fig 26.1 caption - Replace g(x) by P^*(x) p.337 Fig 26.4 caption - Replace g(x) by P^*(x) p.340 line 2. and replaced by -> are replaced by p.360 line 3 replace "can can" by "can" p.375 In steps 3d and 3e replace u by u' p.377 End of middle line: (top line of para 4) add "the" after "help of" p.378 Top algorithm, line "7:" replace P*(X) by P*(X') p.378 Second algorithm, line "2f:" replace P*(X) by P*(X') p.378 Ex 29.11, 5th line: replace P*(X) by P*(X') p.418 Algorithm 32.4. Line 3. Insert factor of 2 before a_i. p.419 line 1. Insert "of" after "idea". p.421 The second sentence of section 32.5 is easy to misread. Better: "We can prove this using the example of..." p.449 before eq 35.9: unbiased estimator should read $\hat{a} = (\bar{n}/N) / \log N$. p 454. Ex 36.4 Clarify that the phrases "other non-winner" and "another non-winner" do not imply that the current door is either a winner or a non-winner. p 454. Ex 36.5. Remove "p.715/729" solution reference. Change "A to B and D to C" to "A to B, and, at the same time, D to C". p.455 Delete word `made' in `having not chosen the most desirable'. p.484 Definition 40.1 (General position) The definition given is insufficient. An extra constraint is needed, namely - and no $K+1$ of them lie in a $(K-1)$-dimensional plane. The text around Definition 40.1 contains an ugly repetition. There is also an unnecessary reference to p484. p.522 Before eq 43.3: Replace subscripts "n" by "i". Add a reference to equation (42.3) for the definition of the activation. Eq 43.3: add subscript "i" to "a". p.528 Last para of sec 44.1, line 1 - 44.3 should read 44.4 p.529 line 11: delete "reading aloud". Add entry to index: "reading aloud, p.529". p.576 Middle of page, after (48.1) replace "whereas is" by "whereas in" p.583, bottom paragraph. Where it says "Figure 49.3", it should be "Figure 49.2". p.595 Upgrade difficulty of ex 50.12 from 3C to 4C. Aesthetic corrections: p.538-9 Figures 44.2 and 44.3 occur in the wrong order. Index additions: p 627, add index entry for "softmax" on p 316 (first occurrence, before p 339). Additional entries for {law of large numbers}. Add union bound: page 166. ==================================================================== S3. SECOND PRINTING ==================================================================== Corrections to the Second Printing (version 6.6, Mon 22/12/03) that do not apply to the First. -------------------------------------------------------------------- p.430 Subsection "Optimization of Q_sigma(sigma)": I messed up the correction to the first printing! The first line should read "We represent Q_sigma(sigma) using the density over beta, Q_sigma(beta) \equiv Q_sigma(sigma) |d sigma/d beta|." [Delete \propto 1/\beta at end of first line.] Add marginal note: The prior P(\sigma) \propto 1/\sigma transforms to P(\beta) \propto 1/\beta. -------------------------------------------------------------------- Corrections to the Online copy of the second printing -------------------------------------------------------------------- Page numbers may be off by 2 compared to the printed book. -------------------------------------------------------------------- Aesthetic changes -------------------------------------------------------------------- page 429 a small protrusion Consistency: p 289 has "soft-min", index p 627 has "softmin", p.454 Replace `people' by `anyone' p.454 Insert `large' before queue p.61 "There is a general rule which helps immensely in confusing probability problems" is poor and confusing English! As a quick fix, add a comma thus: "There is a general rule which helps immensely, in confusing probability problems" ==================================================================== S4. FIRST, SECOND, THIRD PRINTINGS ==================================================================== Corrections to the Third Printing (version 7.0, Mon 30/8/04) that also apply to the First and Second. -------------------------------------------------------------------- p.244 sec 16.2 line 3 of point "2." the the -> the ==================================================================== S5. THIRD PRINTING ==================================================================== Corrections to the Third Printing (version 7.0, Mon 30/8/04) that do not apply to the First or Second. -------------------------------------------------------------------- p.(Music Hash) pointer to www.name-this-tune.com changed to http://musipedia.org/ -------------------------------------------------------------------- Additional references -------------------------------------------------------------------- 1. Recommended for readers who want practice with elementary probability: @book{Ambegaokar1996, title={Reasoning about Luck: Probability and its Uses in Physics}, author={Vinay Ambegaokar}, year={1996}, isbn={0521447372} } 2. Highly recommended for further reading on Bayesian inference, rational decision making, and the question `does ordinary human reasoning obey Bayesian probability?' (to which the answer is `often not!') @book{Tversky1982, title={Judgment under Uncertainty: Heuristics and Biases}, editor={Daniel Kahneman and Paul Slovic and Amos Tversky}, year={1982}, annote={544 pages}, ISBN={0521284147} } 3. Have not read this yet, but I should probably include it @article{arith_coding_revisited, author={Moffat, A., Neal, R. M., and Witten, I. H.}, year={1998}, title={Arithmetic coding revisited}, journal={ACM Transactions on Information Systems}, volume={16}, pages={256-294} } 4. Add a reference to @inproceedings{Huber1998, author={Mark Huber}, title={Exact Sampling and Approximate Counting Techniques}, booktitle={Proceedings of the 30th ACM Symposium on the Theory of Computing}, pages={31-40}, year={1998}, annote={Mark Huber. Exact Sampling and Approximate Counting Techniques. In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 31--40, 1998.} } on page 419, thus: Summary state methods were first introduced by \citeasnoun{Huber1998}; they also go by the names {sandwiching method}s and {bounding chain}s. 5. Add a reference to @article{Berlekamp1976, author={Elwyn R. Berlekamp}, title={Cooperative bridge bidding}, journal={IEEE Transactions on Information Theory}, month={Nov}, year={1976}, vol=22, number=6, pages={753-756} } @article{Cohn1976 author={David L. Cohn}, title={An Enumeration Scheme for Bidding Sequences in Bridge}, journal={IEEE Transactions on Information Theory}, month={Nov}, year={1976}, vol=22, number=6, pages={756-757} } in the bridge exercise. 6. Add to the bibliography @Article{Ziv_Lempel77, author = "J. Ziv and A. Lempel", title = "A Universal Algorithm for Sequential Data Compression", journal = "IEEE Trans. on Info. Theory", year = 1977, volume = 23, number = 3, pages = "337-343", month = "May" } -------------------------------------------------------------------- Thanks to --------- Atsushi Shimotani Iain Murray Ed Ratzer Chris Ball Keith M. Briggs Ole Winther jan-hendrik Nachiketa Sahoo Ros Polis Sergio Verdu KANEMURA Atsunori Alan N. Hampton Danilo Silva Mike Potts Laurent Perrinet ----------------------------------------------------------------------------- VERSION NUMBERS ----------------------------------------------------------------------------- Version 6.0 is the version of the first printing of the book. (Thu 26/6/03) Version 6.6, Mon 22/12/03. Second Printing version 7.0, Mon 30/8/04 Third printing