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:

Wald: Sequential Analysis (1947)

I've always thought that Shannon's insights in the 1940s papers seemed like pure magic, but this book suggests that at parts of his way of thinking were already in the air at the time: From his own frequentist perspective, Wald comes oddly close to defining a version of information theory.

The central question of the book is:

How can we devise decision procedures that map observations into {Accept, Reject, Continue} in such a way that (1) the probability of wrongly choosing Accept or Reject is low, and (2) the expected number of Continue decisions is low?

Throughout the book, the answer that he proposes is to use likelihood ratio tests. This puts him strangely close to the Bayesian tradition, including for instance Chapter 5 of Jeffreys' Theory of Probability.

A sequential binomial test ending in rejection (p. 94)

In particular, the coin flipping example that Jeffreys considers in his Chapter 5.1 is very close in spirit to the sequential binomial test that Wald considers in Chapter 5 of Sequential Analysis. However, some differences are:

• Wald compares two given parameter values p₀ and p₁, while Jeffreys compares a model with a free parameter to one with a fixed value for that parameter.
• Jeffreys assigns prior probabilities to everything; but Wald only uses the likelihoods given the two parameters. From his perspective, the statistical test will thus have different characteristics depending on what the underlying situation is, and he performs no averaging over these values.

This last point also means that Wald is barred from actually inventing the notion of mutual information, although he comes very close. Since he cannot take a single average over the log-likelihood ratio, he cannot compute any single statistic, but always has to bet on two horses simultanously.

Stockwell: "The Transformational Model of Generative or Predictive Grammar" (1963)

This essay by Robert Stockwell is a pretty much a rehash of Chomsky's ideas from Syntactic Structures, and as such quite boringly predictable. (Stockwell also thanks Chomsky for critical comments in the acknowledgments.) However, it does touch on some interesting issues on the last couple of pages, so I'll give a couple of excerpts here.

The essay is a part of an anthology called Natural Language and the Computer, which (in addition to being quite wonderfully techno-camp) is one of the most boldly and beautifully typeset books I've seen in a while.

The title page, with gargantuan print and the editor's name in a spacy font.

Some aspects of its graphical design has an undeniable 1950s feel to it; others look like a kind of 1960s Space Odyssey futurism; and others again look like they were taken straight out of Blade Runner. It's all quite remarkable.

Title page of Part 1, with an unmistakably 1950s italic font and a "etched" figure 1.

And then of course there's the always charming prospect of reliving a lecture taking stock of the computer revolution anno 1960. One of the other books in the same series is even called – I kid you not – The Foundations of Future Eletronics. How can you not love a 1961 book with that title?

At any rate, the essay that I'm interested in plods through the familiar details of Chomskyan grammar, pushing in particular the hard sell of transformational grammar over "immediate constituent" grammar (i.e., phrase structure grammars without any postprocessing).

The last section of the essay is called "Grammaticalness and Choice" and gets a bit into the issue of how sentences are selected, and what goes on in the head of the alleged "ideal speaker" of Chomskyan linguistics. This part contains a number of interesting quotes, and I'll provide some generous extracts below.

"Forced to Operate Empirically"

The first notion taken up in the section is that of grammaticality itself, which it seems that he sees some problems making empirically precise:

Presumably the notion of "grammatical sentence" is characterized by the grammar itself, since in principle we formulate our rules in such a way as to generate only and always such sentences. It is a question of some interest whether there is a possibility of characterizing this notion independently of the grammar. It seems extremely unlikely that there is, and we will be forced to operate empirically with the machinery of the grammar, treating each sentence that it generates as a hypothesis to be tested for grammaticalness against the the reaction of native speakers. For each sentence rejected, we either revise the grammar to exclude the sentence (if we believe the rejection is on proper grounds–that is, not motivated by school grammar and the like), or we revise the grammar to generate the sentence in some special status (i.e., as only partially well formed). Each sentence accepted is, of course, a confirmation of the validity of the rules up to that point. (p. 43)

I suppose what Stockwell has in mind here is that there might in principle exists some kind of objective test of grammaticality which could relieve us of having to trust laypeople to know the difference between "ungrammatical" and "nonsensical." (If you'll allow me a bit of self-citation, I've written a short paper on the idea of having such a distinction.)

Today, linguists might fantasize about such a test taking the form of an fMRI scan; in the 1980s, they would have imagined it as an EEG; and in the 1950s, a polygraph reading. But in the absence of such a test, we are forced to use live and conscious people even though

Informant reaction is difficult to handle, because such reactions involve much more than merely the question of grammaticalness. (p. 43)

We thus only have indirect access to the alleged grammatical engine of the brain.

"The Rest Takes Care of Itself"

After briefly considering a couple of borderline grammatical cases, Stockwell continues:

One might consider the utilization of grammar by the speaker as follows. The essence of meaning is choice; every time an element is chosen in proceeding through the rules, that choice is either obligatory (in which case it was not really a choice at all, since there were no alternatives), or it is optional (in which case the choice represented simultaneously both the positive decision and the rejection of all alternatives–the meaning of the choice inheres in the [sic] constrastive value of the chosen element as compared with all the possible choices that were rejected). (p. 44)

Oddly enough, Stockwell's meditation on the actual role and implementation of Chomskyan grammar in a person's behavior brings him around to confirming not only de Saussure's picture of meaning, but also Shannon's. I wonder whether he is aware of the implications of this.

He then goes on to consider an example:

Thus these are the choices involved in a simple sentences such

 Did the boy leave.

NP + VP	Obligatory
D + N	Obligatory
D == the	Optional
N == boy	Optional
aux + VP1	Obligatory
aux == past	Optional
VP1 == Vi	Optional
Vi == leave	Optional
Tintrg	Optional
Inversion of Te	Obligatory
Empty carrier for past	Obligatory
Rising intonation	Obligatory

Of the twelve choices, half are obligatory–either initiating the derivation, or following out obligatory consequences of optional choices. The additional rules of the phonetic component are nearly all obligatory. To include these would increase the obligatory choices to about twice the number of optional choices. In fact it is quite probable that in real discourse even the element the is obligatory (that is, the choice of the versus a seems quite predictable in a larger context). This would leave us with only five meaning-carrying (optional) choices. Everything else that goes into making up the sentence is in a valid sense perfectly mechanical, perfectly automatic. It can be argued that a grammar must maximize the obligatory elements and cut the optional choice to the barest minimum in order to get any reasonable understanding of how the human brain is capable of following complex discourse at all. That is, the hearer's attention is focused on matching, with his own generating machinery, the sequence of optional choices; since he has identical obligatory machinery, the rest takes care of itself. In this way, the same grammatical model accounts for both encoding and decoding. We do not need separate and distinct analogs for both sending and receiving messages. (pp. 44–45)

Again, this is oddly similar to the kind of generative model one would employ in information theory, and the notion of having a sparse language to minimize cognitive effort here takes the place of error-correction. But presumably, the philosophical difference is whether we need a source model (of the "optional choices") or only a channel model (of the "perfectly mechanical, perfectly automatic" choices).

"From Which He Knowingly Deviates"

This reading of the differences is backed up by his elaboration:

Encoding and decoding does not imply that a speaker of hearer proceeds step by step in any literal sense through the choices characterized by the grammar in order to produce or understand sentences. The capacities characterized by the grammar are but one contributing factor of undetermined extent in the total performance of the user of language. The grammar enumerates only well-formed sentences and deviant sentences, which, recognized as ranging from slightly to extremely deviant by the language user, are interpreted somehow by comparison with well-formed ones. The grammar enumerates sentences at random; it does not select, as the user does, just that sentences appropriate to a context. The grammar clacks relentlessly through the possible choices; the user starts, restarts, jumps the grammatical traces, trails off. A generative grammar is not a speaker-writer analog. It is a logical analog of the regularities to which the language user conforms or from which he knowingly deviates. (p. 45)

I take it that this entails that grammars are essentially and necessarily logical in nature, since their purpose is to describe the set of available sentences of the language rather than to predict their occurrence. From such a perspective, a probabilistic context-free grammar would be something of an oxymoron.

A logical and a probabilistic conception of grammar.

 

"A Natural Extension of Scholarly Grammar"

Again in perfectly orthodox fashion, Stockwell finally tips his hat at the impossibility of formulating discovery procedures and makes a strange claim about the machine-unfriendly nature of transformation grammars:

Although the title of this book suggests the machine processing of natural-language data, it should not be assumed that the transformational model of the structure of language is in any way geared to machines of any kind, either historically or in current development. On the contrary, it is a natural extension of traditional scholarly grammar, an effort to make explicit the regularities to which speakers of a language conform, which has been the focus of grammatical studies for over 2,500 years. The effort to formulate discovery procedures for the systematic inference of grammatical structure is quite recent; few if any transformationalists believe such a goal has any possibility of success–at least, not until much more is known about the kinds of regularities which grammarians seek to discover and to formulate in explicit terms. (p. 45)

That seems a bit odd in the light of, e.g., Victor Yngve's recollection of how people were swayed by Chomsky's grammatical analyses because they "read like computer programs."

Attneave: Applications of Information Theory to Psychology (1959)

Fred Attneave's book on information theory and psychology is a sober and careful overview of the various ways in which information theory had been applied to psychology (by people like George Miller) by 1959.

Attneave explicitly tries to stay clear of the information theory craze which followed the publication of Shannon's 1948 paper:

Book cover; from Amazon.

Thus presented with a shiny new tool kit and a somewhat esoteric new vocabulary to go with it, more than a  few psychologists reacted with an excess of enthusiasm. During the early fifties some of the attempts to apply informational techniques to psychological problems were successful and illuminating, some were pointless, and some were downright bizarre. At present two generalizations may be stated with considerable confidence:
(1) Information theory is not going to provide a ready-made solution to all psychological problems; (2) Employed with intelligence, flexibility, and critical insight, information theory can have great value both in the formulation or certain psychological problems and in the analysis of certain psychological data (pp. v–vi)

Or in other words: Information theory can provide the descriptive statistics, but there is no hiding from the fact that you and you alone are responsible for your model.

Language Only, Please

Chapter 2 of the book is about entropy rates, and about the entropy of English in particular. Attneave talks about various estimation methods, and he discusses Shannon's guessing game and a couple of related studies.

As he sums up the various mathematical estimation tricks, he notes that predictions from statistical tables tend to be more reliable than predictions from human subjects with respect to the first couple of letters of a text. This means that estimates from human predictions will tend to overestimate the unpredictability of the first few letters of a string.

He then comments:

What we are concerned with above is the obvious possibility that calculated values (or rather, brackets) of H_N [= the entropy of letter N given letter 1 through N – 1] will be too high because of the subject's incomplete appreciation of statistical regularities which are objectively present. On the other hand, there is the less obvious possibility that a subject's guesses may, in a certain sense, be too good. Shannon's intent is presumably to study statistical restraints which pertain to language. But a subject given a long sequence of letters which he has probably never encountered before, in that exact pattern, may be expected to base his prediction of the next letter not only upon language statistics, but also upon his general knowledge [p. 40] of the world to which language refers. A possible reply to this criticism is that all but the lowest orders of sequential dependency in language are in any case attributable to natural connections among the referents of words, and that it is entirely legitimate for a human predictor to take advantage of of such natural connections to estimate transitional probabilities of language, even when no empirical frequencies corresponding to the probabilities exist. It is nevertheless important to realize that a human predictor  is conceivably superior to a hypothetical "ideal predictor" who knows none of the connections between words and their referents, but who (with unlimited computational facilities) has analyzed all the English ever written and discovered all the statistical regularities residing therein. (pp. 39–40; emphases in original)

I'm not sure that was "Shannon's intent." Attneave seems to rely crucially on an objective interpretation of probability as well as an a priori belief in language as an autonomous object.

Just like Laplace's philosophical commitments became obvious when he starting talking in hypothetical terms, it is also the "ideal predictor" in this quote which reveals the philosophy of language that informs Attneave's perspective.