Fano: The Transmission of Information (1949)

There are three different coding methods associated with Claude Shanon's name:

1. Shannon coding;
2. Shannon-Fano coding;
3. Shannon-Fano-Elias coding.

These are not the same. Even more confusingly, Shannon-Fano-Elias coding is in fact much closer in kind to Shannon coding than it is to Shanon-Fano coding, making the names even more misleading. Moreover, neither Fano nor Elias published any conventional research articles on the topic, and Elias may not even have invented Elias coding. I'll try to sort out these issues now.

Downwards Interval Approximations

Shannon coding is the name for the data compression algorithm that Shannon exhibited as his second and more constructive proof of the source coding theorem (his Theorem 9, page 17 in the Bell Labs transcription). It derives the code words from binary approximations to cumulative probabilities.

The process is the following:

1. Sort the event probabilities so that $p_1 \geq p_2 \geq \ldots \geq p_n$;
2. Let $F_m = \sum_{i=1}^{m-1}p_i$ be the cumulative probability of the most probable events (up to, but not including, the $m$th).
3. Let $K_m=\lceil{-\log_2{p_m}}\rceil$.
4. Let the code for event number $m$ be the first $K_m$ binary digits of $F_m$ (i.e., round $F_m$ down to the nearest multiple of $2^{-K_m}$).

As an example, with the probabilities
$$
p = (.4, .3, .2, .1),
$$Shannon coding produces the codewords
$$
(00, 01, 101, 1110).
$$Shanon coding only produces a prefix-free code when the probabilities are in fact sorted. If we think of the probabilities $p_1,p_2,\ldots,p_n$ as a stack of intervals filling out the space between 0 and 1, then the rounding-off corresponds to approximating $[F_m,F_{m+1}]$ by an interval whose left-hand boundary is a binary number smaller than $F_m$, and whose right-hand boundary is a binary number of the same precision which lies below $F_{m+1}$. If wider intervals follow narrower ones, the corresponding increase in coarseness can cause overlaps between the approximations.

Inner Interval Approximations

Shannon-Fano-Elias coding is a variation on this theme which does not require the codewords to be sorted. According to Cover and Thomas' textbook (Chapter 5), it was developed by Peter Elias but never published. However, this other textbook claims that Elias denied this, and that the idea perhaps came from a talk Shannon gave at the MIT.

At any rate, the idea behind the method is the following:

1. Let $F^*_m = \sum_{i=1}^{m-1}p_i+\frac{1}{2}p_m$ be the point halfway between $F_m$ and $F_{m+1}$.
2. Let $K_m=\lceil{-\log_2{p_m}}\rceil + 1$.
3. Let the code for event number $m$ be the first $K_m$ binary digits of $F^*_m$.

Since these codewords are one bit longer than the ones used in Shannon coding, we can dispense with the requirement of using sorted probabilities. Instead, we use a binary fraction that is guaranteed to lie completely inside the interval between $F_m$ and $F_{m+1}$, even if the binary expansion continues with $1111\ldots$ after our selected truncation point.

With the example above, $(.4, .3, .2, .1),$ this gives the codewords
$$
(001, 100, 1100, 11110).
$$These are exactly one bit longer than the Shannon codewords.

Recursive Batch Splitting

Shannon-Fano coding is a different approach to the problem. Instead of using binary approximation, it uses a recursive, top-down method to construct a binary tree:

1. If there is only one event on the list, return the empty codeword;
2. Otherwise, sort the event probabilities so that $p_1 \geq p_2 \geq \ldots \geq p_n$;
3. Of the $n-1$ possible ways of splitting this list up into a head and a tail, select the one that makes the two lists most equal in probability.
4. Recursively use Shannon-Fano coding to assign codewords to each of those two lists;
5. Prepend a 0 to all the codewords in the first list and a 1 to the codewords on the second.

For the example above, this gives
$$
(0, 10, 110, 111).
$$Notice that the codeword lengths here differ from the ones produced by the Shannon code.

Shannon-Fano coding was invented by Robert Fano at some point in the 1940s and described in his 1949 technical report "Transmission of Information" (published by the MIT). This report is hard to come by, but an akwardly transcribed .pdf without pictures is available here.

An number of excerpts and scanned figures from the report are available in these teaching materials. I'll just paste the three relevant figures here so that they don't get lost in the desert of the internet:

John Cassian: The Institutes, Book 4

Here's a little illustration of what "love" could mean in the fourth century:

Now I shall relate a deed of Abba Patermutus that is worthy of remebrance. He, desiring to renounce this world, persisted in keeping watch outside the monastery until, thanks to his unwavering perserverance and against every custom of the cenobia, he was called an received along with his young son, who was about eight years old. And when they were at last taken in, they were at once not only handed over to different superiors but even made to live in separate cells, lest the father think, from constantly seeing the lad, that, of all the goods and carnal feelings of his that he had renounced and cast aside, at least his son was still his. Thus, just as he knew that he was no longer a rich man, so he might also know that he was not a father. (bk. 4, ch. XXVII.1, p. 92)

That's not enough, though:

In order to find out more clearly whether he made more of his feeling for his kindred and of his own heart's love or of obedience and mortification in Christ (which every renunciant ought to prefer out of love for him), the little boy was purposely neglected, clothed in rags rather than garments, and so covered over and marred with filth as to shock rather than delight his father whenever he would see him. He was also exposed to the blows and slaps of different persons, which he often with his own eyes saw inflicted even arbitrarily on the innocent youngster, such that whenever he saw his cheeks they were streaked with the dirty traces of tears. And although the child was treated this was under his eyes day after day, the father's heart nonetheless remained ever stern and unmoved out of love for Christ and by the virtue of obedience. For he no longer considered as his son the child whom he had offered to Christ along with himself, nor did he worry about his present sufferings; instead he rejoiced because he saw that they were not being borne fruitlessly, and, concerned about his own humility and perfection, he gave little thought to his tears. (ch. XXVII.2–3, pp. 92–93)

You probably thought the "rejoice" was the climax of this story. You were wrong:

The elder of the cenobium, on noticing the steadfastness of his mind and his unmoving sternness, and with a view to testing his strength of mind to the utmost, made believe that he was upset with the child when one day he saw him crying, and ordered his father to take him and throw him into the river. Thereupon, as if he had been ordered to do so by the Lord, he immediately ran, took his son in his own arms and brought him to the edge of the river, intending to hurl him in. Given the fervor of his faith and obedience this would certainly have been brought to a bitter end were there not brothers purposely stationed by the back of the river, carefully watching, who somehow snatched the child from the currecnt when he had been thrown in and prevented the command, which had been fulfilled by the obedient devotion of the father, from being carried out with all its consequences. (ch. XXVII.3–4)

The other monks recognize this event as an reenactment of Abraham's almost-sacrifice of his son and afterwards hold the father in high esteem. (When the old "Abba" dies, he is appointed as his successor.)

John Cassian tells quite a few stories of this sort in his Institutes, a book in which he reconstructs from memory the practices and rules of the ascetic Christian cults he visited in Egypt as a young man. Common to all of these are the theme of striving for an extreme, self-negating obedience, sometimes bordering on the (absurdly) comical.

In one story, for instance, a monk later known as John the Dwarf is commanded to water a dry stick so that it can take root. He does so dutifully and unquestioningly for an entire year until his elder decides the game is over, pulls up the stick and looks at it, then throws it away (ch. XXIV.2–4, pp. 90–91). Cassian seems to delight in this display of a lack of independent will:

And so the youth, trained every day in exercises of this kind, matured in the virtue of obedience and shone with the grace of humility, and the sweet odor of his obedience spread through the monasteries. (ch. XXV, p. 91)

The sadomasochist vibe is not out of character. We are often told that the various religious men are "inflamed" with an "ardent desire for humility" and the like (e.g., ch. XXXI, p. 96), and there is a clear sense that there is a kind of competition going on to be most self-abnegating, most humble, most lowly, and most poor.

This has, of course, the paradoxical effect of making the lack of pride be itself a point of pride. One wins the greatest honor by heading straight for the bottom of society.

The Dialogues of Saint Gregory the Great, book II, ch. 4

How do your cure an attention deficit in the sixth century? By magic, it seems.

In his biography of Saint Benedict, Pope Gregory I relates a story of how he "cured a monk that had an idle and wandering mind." Here it is:

In one of the monasteries which he had built in those parts, a monk there was, which could not continue at prayers; for when the other monks knelt down to serve God, his manner was to go forth, and there with wandering mind to busy himself about some earthly and transitory things. And when he had been often by his Abbot admonished of this fault without any amendment, at length he was sent to the man of God, who did likewise very much rebuke him for his folly; yet notwithstanding, returning back again, he did scarce two days follow the holy man's admonition; for, upon the third day, he fell again to his old custom, and would not abide within at the time of prayer: word whereof being once more sent to the man of God, by the father of the Abbey whom he had there appointed, he returned him answer that he would come himself, and reform what was amiss, which he did accordingly: and it fell so out that when the singing of psalms was ended, and the hour come in which the monks betook themselves to prayer, the holy man perceived that the monk, which used at that time to go forth, was by a little black boy drawn out by the skirt of his garment; upon which sight, he spake secretly to Pompeianus, father of the Abbey, and also Maurus, saying : "Do you not see who it is, that draweth this monk from his prayers?" and they answered him, that they did not. "Then let us pray," quoth he, "unto God, that you also may behold whom this monk doth follow": and after two days Maurus did see him, but Pompeianus could not. Upon another day, when the man of God had ended his devotions, he went out of the oratory, where he found the foresaid monk standing idle, whom for the blindness of his heart he strake with a little wand, and from that day forward he was so freed from all allurement of the little black boy, that he remained quietly at his prayers, as other of the monks did : for the old enemy was so terrified, that he durst not any more suggest such cogitations : as though that blow, not the monk, but himself had been strooken. (pp. 61-62)

This is remarkably un-psychological: It seems like the only way these people were able to explain lack of distraction was by externalizing the problem in a devil or spirit, or as here, in the "allurement of the little black boy."

And of course, a problem so concrete should be treated with a good dose of Harry Potter-style spell-casting. Unless, that is, the wand is a club, and the spell is a beating.

Edwards: Likelihood (1972)

Edwards (from his Cambridge site)

The geneticist A. F. W. Edwards is a (now retired) professor of biometry who was massively influenced by Ronald Fisher in his scientific writings. His books Likelihood argues that the likelihood concept is the only sound basis for scientific inference, but it reads at times almost like one long rant against Bayesian statistics (particularly ch. 4) and Neyman-Pearson theory (particularly ch. 9).

Don't Do Probs

As an alternative to these approaches to statistics, Edwards proposes that we limit ourselves to makes assertions only in terms of likelihood, "support" (log-likelihood, p.12), and likelihood ratios. In the brief epilogue of the book, he states that this

… allows us to do most of the things which we want to do, whilst restraining us from doing some things which, perhaps, we should not do. (p. 212)

In particular, this approach emphatically prohibits the comparison of hypotheses in probabilitistic terms. The kind of uncertainty we have about scientific theories is simply not, Edwards states, of a nature that can be quantified in terms of probabilities: "The beliefs are of a different kind," and they are "not commensurate" (p. 53)

The Difference Between Bad and Worse

He briefly mentions Ramsey and his Dutch book-style argument for the calculus of probability, and then goes on to speculate that, had not died so young,

… perhaps he would have argued that his demonstration that absolute degrees of belief in propositions must, for consistency's sake, obey the law of probability, did not compel anyone to apply such a theory to scientific hypotheses. Should they decline to do so (as I do), then they might consider a theory of relative degrees of belief, such as likelihood supplies. (p. 28)

In other words, it might be true that you cannot assign numbers to propositions in any other way than according to the calculus of probabilities, but you can always reject to have a quantitative opinion in the first place (or not make a bet).

Nulls Only

Consistently with Fisher's approach to statistics, Edwards finds it important to distinguish between null and not-null hypotheses: That is, in opposition to Neyman-Pearson theory, he refuses to explicitly formulate the alternative hypothesis against which a chance hypothesis is tested.

Here as elsewhere, this is a serious limitation with quite profound consequences:

It should be noted that the class of hypotheses we call 'statistical' is not necessarily closed with respect to the logical operations of alternation ('or') and negation ('not'). For a hypothesis resulting from either of these operations is likely to be composite, and composite hypotheses do not have well-defined statistical consequences, because the probabilities of occurrence of the component simple hypotheses are undefined. For example, if $p$ is the parameter of a binomial model, about which inferences are to be made from some particular binomial results, '$p=\frac{1}{2}$' is a statistical hypothesis because its consequences are well-defined in probability terms, but its negation, '$p\neq\frac{1}{2}$', is not a statistical hypothesis, its consequences being ill-defined. Similarly, '$p=\frac{1}{4}$ or $p=\frac{1}{2}$' is not a statistical hypothesis, except in the trivial case of each simple hypothesis having identical consequences. (p. 5)

This should also be contrasted with Jeffreys' approach, in which the alternative hypothesis has a free parameter and thus is allowed to 'learn', while the null has the parameter fixed at a certain value.

Scientists With Attitude

At several points, in the book, Edwards uses the concerns of the working scientist as an argument in favor of a likelihood-based reasoning calculus. He thus faults Bayesian statistics for "fail[ing] to answer questions of the type many scientists ask" (p. 54).

This question, I presume, is "What does the data tell my about my hypotheses?" This is distinct from "What should I do?" or "Which of these hypotheses is correct?" in that it only supplies the objective, quantitative measure of support, not the conclusion:

The scientist must be the judge of his own hypotheses, not the statistician. The perpetual sniping which statisticians suffer at the hands of practising scientists is largely due to their collective arrogance in presuming to direct the scientists in his consideration of hypotheses; the best contribution they can make is to provide some measure of 'support', and the failure of all but a few to admit the weaknesses of the conventional approaches has not improved the scientists' opinion. (p. 34)

In brief form, this leads to the following tirade against Bayesian statistics:

Inverse probability, in its various forms, is considered and rejected on the grounds of logic (concerning the representation of ignorance), utility (it does not allow answers in the form desired), oversimplicity (in problems involving the treatment of frequency probabilities) and inconsistency (in the allocation of prior probability distributions). (p. 67–68)

Fisher: The Design of Experiments (4th ed., 1947), Chapter I

Fisher; from Judea Pearl's website.

Now, here's a revealing turn of phrase:

In the foregoing paragraphs the subject-matter of this book has been regarded from the point of view of an experimenter, who wishes to carry out his work competently, and having done so wishes to safeguard his results, so far as they are validly established, from ignorant criticism by different sorts of superior persons. (p. 3)

You could hardly spell out more explicitly the philosophy that lies behind Fisher's concept of statistics: It's a strategic ritual, not designed to ensure a result, but to protect against criticism.

Perfectly Rigorous and Unequivocal

Such protection only goes as far as the mathematical consensus on the validity of the logic. But Fisher goes on to state that "rigorous deductive argument" is possible even in the context of random events, citing gambling as a proof of concept:

The mere fact that inductive inferences are uncertain cannot, therefore, by accepted as precluding perfectly rigorous and unequivocal inference. (p. 4)

This seems to confuse the issues of probability and statistics, unless his argument here really only amounts to saying that distributions are non-stochastic entities.

Useless for Scientific Purposes

This leads him to a discussion of "inverse probability," which he gives three reasons for rejecting: First,

… advocates of inverse probability seem forced to regard mathematical probability, not as an objective quantity measured by observed frequencies, but as measuring merely psychological tendencies, theorems respecting which are useless for scientific purposes. (p. 6–7)

Second, Bayes' axiom (about the flat prior for a coin flip) is not self-evident, that is, the choice of prior is not unequivocal (p. 7).

Ever Since the Dawn of Man…

And third,

… inverse probability has been only very rarely used in the justification of conclusions from experimental facts, although the theory has been widely taught, and is widespread in the literature of probability. Whatever the reasons are which could give experimenters confidence that they can draw valid conclusions from their results, they seem to act just as powerfully whether the experimenter has heard of the theory of inverse probability or not. (p. 7)

That's a funny sociological proof, given that he has just rejected Bayesian statistics for its psychologism. But he himself sometimes seems to think that his statistics is a kind of theory of learning, whatever that means:

Men have always been capable of some mental processes of the kind we call "learning by experience." … Experimental observations are only experience carefully planned in advance, and designed to form a secure basis of new knowledge; (p. 8)

Chernoff: "A career in statistics" (2014)

Chernoff makes some interesting remarks about the philosophy of statistics in his recent autobiographical essay.

First, an anecdote about the three classical decision criteria considered in decision theory:

I had always been interested in the philosophical issues in statistics, and Jimmie Savage claimed to have resolved one. Wald had proposed the minimax criterion for deciding how to select one among the many “admissible” strategies. Some students at Columbia had wondered why Wald was so tentative in proposing this criterion. The criterion made a good deal of sense in dealing with two-person zero-sum games, but the rationalization seemed weak for games against nature. In fact, a naive use of this criterion would suggest suicide if there was a possibility of a horrible death otherwise. Savage pointed out that in all the examples Wald used, his loss was not an absolute loss, but a regret for not doing the best possible under the actual state of nature. He proposed that minimax regret would resolve the problem. At first I bought his claim, but later discovered a simple example where minimax regret had a similar problem to that of minimax expected loss. For another example the criterion led to selecting the strategy A, but if B was forbidden, it led to C and not A. This was one of the characteristics forbidden in Arrow’s thesis.

Savage tried to defend his method, but soon gave in with the remark that perhaps we should examine the work of de Finetti on the Bayesian approach to inference. He later became a sort of high priest in the ensuing controversy between the Bayesians and the misnamed frequentists. (pp. 32–33)

He immediately moves on to one of his own more dismal conclusions about the issue:

I posed a list of properties that an objective scientist should require of a criterion for decision theory problems. There was no criterion satisfying that list in a problem with a finite number of states of nature, unless we canceled one of the requirements. In that case the only criterion was one of all states being equally likely. To me that meant that there could be no objective way of doing science. I held back publishing those results for a few years hoping that time would resolve the issue (Chernoff, 1954). (p. 33)

I haven't read the paper he is referring to here, but it seems like the text has jumbled up the conclusions: I think what he meant to say is that there is no single good decision function when we have infinitely many states, since the criteria essentially require us to use a uniform distribution. But I would have to check the details.

Finally, he moves on to a more on-record explication of his position:

In the controversy, I remained a frequentist. My main objection to Bayesian philosophy and practice was based on the choice of the prior probability. In principle, it should come from the initial belief. Does that come from birth? If we use instead a non-informative prior, the choice of one may carry hidden assumptions in complicated problems. Besides, the necessary calculation was very forbidding at that time. The fact that randomized strategies are not needed for Bayes procedures is disconcerting, considering the important role of random sampling. On the other hand, frequentist criteria lead to the contradiction of the reasonable criteria of rationality demanded by the derivation of Bayesian theory, and thus statisticians have to be very careful about the use of frequentist methods. 

In recent years, my reasoning has been that one does not understand a problem unless it can be stated in terms of a Bayesian decision problem. If one does not understand the problem, the attempts to solve it are like shooting in the dark. If one understands the problem, it is not necessary to attack it using Bayesian analysis. My thoughts on inference have not grown much since then in spite of my initial attraction to statistics that came from the philosophical impact of Neyman–Pearson and decision theory. (p. 33)

Duda and Hart: Pattern Classification and Scene Analysis (1973)

A lot of references seem to indicate that this book played an important role in the popularization of Bayesian methods in machine learning. It also provides an interesting missing link between the statistics and decision theory of the 1950s and the field of machine learning in the form it now has.

Interestingly, their rejection of minimax approaches to decision theory is rather casual, relative to how toxic the debate actually was:

In fact, the Bayesian approach is avoided by many statisticians, partly because there are problems for which a decision is made only once (so that average loss is not meaningful), and partly because there may be no reasonable way to determine the a priori probabilities. Neither of these difficulties seems to present a serious problem in typical pattern recognition applications, and for simplicity we have taken a strictly Bayesian approach. (p. 36)

Compare this to David Blackwell's compact statement of intent in Basic Statistics (1969):

This book indicates the content of a lower-division basic statistics course I have taught several times at Berkeley. […] The approach is intuitive, informal, concrete, decision-theoretic, and Bayesian. (p. v)

Duda and Hart also provide a number of quite interesting references:

The text by Nilsson (1965) provides an exceptionally clear treatment of classification procedures. (p. 8)

There are many interesting subject areas that are related to this book but beyond its scope. […] Those interested in philosophical issues will find the books by Watanabe (1969) and Bongard (1970) thought provoking. (p. 8)

We are also fond of the the text by Ferguson (1967), who presents many topics in statistics from a decision theoretic viewpoint. (p. 36)

Chow (1957) was one of the first to apply Bayesian decision theory to pattern recognition. His analysis include a provision for rejection, and he later estiablished a funcamental relation between error and reject rates (Chow 1970). (p. 36)