Prediction and Entropy of Printed English (1950) [pdf] | Hacker News Reader

Prediction and Entropy of Printed English (1950) [pdf]

princeton.edu

131 pointsalexmolas95 comments

It's incredible how Shannon published "A Mathematical Theory of Communication", while actually working on the "Communication Theory of Secrecy Systems":

https://pages.cs.wisc.edu/~rist/642-spring-2014/shannon-secr...

https://pure.mpg.de/rest/items/item_2383164/component/file_2...

What an absolute genius who disrupted two fields in two years.

I was exposed to Shannon's channel capacity theorem of a binary erasure channel in a grad comms theory course, and totally fell in love with the beauty and elegance of his mathematical formulations. Since that day, teaching Information Theory has been my most favorite hobby--which also used to a career. I love to see students' eyes pop when you eventually show how elegantly simple it is to express disorder (entropy) and to find fundamental limits on source and channel codes using this expression.

Heh, I think I'm going to start bringing up this paper whenever somebody tells me they majored in communications. This stuff is fascinating! Shannon really was a genius.

3 fields - Don't forget his Masters thesis which revolutionized digital circuit design.

Yeah, I just re-encountered Shannon while reading about the board game Hex. The Shannon Switching game is the base case of Hex. Guy was firing on all cylinders ;)

Yes, yes. How did I forget this one? Thanks for calling it out.

Wish we had more MS theses today that at least attempted something as ambitious as this one, instead of just checking a box :(

Shannon's Masters thesis was probably the most consequential Masters thesis of the 20th century (and the 21st century so far).

100% agree. Jack Kilby's Masters thesis that realized an actual integrated circuit was another one that makes my list of GOAT.

I read Gleick's The Information[0] a few years ago and was riveted. Do you have any suggestions for further reading if I wanted to take a hobbyist interest?

[0]https://en.wikipedia.org/wiki/The_Information:_A_History,_a_...

I would read "Lifespan" by David Sinclair, who used Shannon's information theory to model epigenetic changes that cause us to age. Fascinating read and goes to show how far reaching impacts a foundational mathematical theory can have.

In EE we of course learned about the Shannon capacity of a channel, but when I read his proof using higher dimensional sphere packing I was amazed. Inspired me to attempt to look further into the math we see in engineering. I highly recommend anyone interested read his paper.

Claude Shannon also had early ideas about machine learning. AT&T has a 1950s video of the maestro himself demonstrating a maze solver with physical output. A true genius. In those days, geeks were dressed in suit.

0: https://techchannel.att.com/play-video.cfm/2010/3/16/In-Thei...

Since we are on the topic, does anyone know what Shannon was up to after disrupting 3 fields? ... He got into ball juggling and built the mathematical theory that led to creation of an automated juggling machine: https://cs.stanford.edu/people/eroberts/courses/soco/project....

He actually showed that ball juggling is one of the most complex cognitive tasks that a human can undertake: "The physical constraints that affect mastery and limit the number of objects juggled arise from gravity - more specifically, Newtonian mechanics (h=1/2gt2). Each ball must be thrown sufficiently high to allow the juggler time to deal with the other balls. The need for either speed or height increases rapidly with the number of objects juggled."

What else? Well, one thing was making a lot of money as an investor. I don't remember quite what Fortune's Formula said about his overall rate of return over many decades, but iirc he made less than Warren Buffett mainly because he started with much less. (That book is about information theory and betting.)

He was down for a period of time in his 40s or 50s (not sure of exact age), which might have been a prelude to what came next: Alzheimer’s disease.

What's funny about this is as we get better at text prediction, we revise our entropy estimations downward. The last I heard was 2016, at around 6 bits/word of EU-produced English. I'm sure it's lower now.

Will ChatGPT drag this downward even more?

I couldn't resist asking it about the word entropy of its training corpus and quite predictably it wasn't able to understand my question and instead answered similar questions. However, it stuck quite firmly to a figure of 10--12 bits per word! I'm fairly sure that refers to the vocabulary entropy and not word entropy of English.

This is like forcing a human to answer questions about brain anatomy.

You’ll be lucky to get anything reasonable at all.

I was wondering the same thing. Even the prediction as I type this in is pretty good. It seems like LLM's could be even better.

Yes, the GPT's are literally trained to minimize (cross-)entropy of text. You can see the bits-per-byte of text for lots of models here: https://crfm.stanford.edu/helm/v0.2.0/?group=targeted_evalua...

This is a good point, it happens because newer models are able to use larger and larger context - long range correlations in text. This amounts to finding more redundancy in the source text, driving down the estimated entropy.

Language models are related to text compression, except that the compression is lossy, not trying to be able to recreate the source text exactly but rather to be able to recreate something that is statistically similar.

How is that not just K-complexity? A larger model is a larger interpreter. The entropy is just moving from the stream to the state machine.

For what it's worth, GPT-2 got PTB perplexity of around 20, which translates to about 4.3 bits/word. The later language models are presumably better but they report bits-per-character or bits-per-token which doesn't convert straightforwardly into bits per word.

For a layman, can you elucidate whether this is about the entropy of its output or input?

Kind of neither, but it's more like the entropy of its output than its input. LLM's can be used to generate text but fundamentally what they do is calculate probabilities of a token given previous tokens. Given a context like "I saw a", the LLM gives a probability to each token in its vocabulary within that context. It's really a probability distribution p(token | context). You can sample from that distribution to generate text, or you can use it to get the probability of some fixed text that you feed into it, which is the probability that the model would have generated that text (at temperature 1).

The PTB perplexity numbers are based on the probabilities assigned to some text from the Wall Street Journal that used to be used as a standard test set in language modeling. It's 2 to the power of the average log probability of each word in the text under the model. So perplexity of 20 corresponds to around 4.3 bits of log probability per word, or another way of thinking of it is that the model will guess the correct following word in 1/20 cases.

The reason I say this isn't exactly the output entropy is that, since perplexity is evaluated on a fixed text, it might not correspond to the kinds of texts that the model would generate purely on its own. In other words when you're looking at some fixed txt, the contexts you get in p(token | context) might not be anything like a context that the LM would generate itself. This was a problem people pointed out a few years ago---back then it looked like LM generations were somewhat higher-entropy than what you measured looking at a fixed text. I don't know if the modern huge LMs have this same problem.

It seems plausible that the entry of written English is decreasing over time. As it becomes cheaper to 'publish' the median effort spent in writing is decreasing.

My introduction to Shannon and information theory through this book [1], which talks briefly about language entropy, is what set me on the path to my career.

[1]. An Introduction to Information Theory, Symbols, Signals & Noise By John Robinson Pierce · 1980 https://www.google.com/books/edition/An_Introduction_to_Info...

The Idea Factory is a great book describing the magical period at Bell Labs where they invented the future. It's just mind boggling how much of today's world was discovered and invented there - from the transistor to information theory.

https://www.amazon.com/Idea-Factory-Great-American-Innovatio...

The copy in the internet archive seems better

https://archive.org/details/bstj30-1-50/mode/2up

That's weird I was just sharing this today with reference to LLMs.

Btw Shannon also invented wearable computers. He did it to cheat at roulette.

pretty sure you mean Ed Thorpe, though Thorpe did eventually collaborate with Shannon.

https://www.cs.virginia.edu/~evans/thorp.pdf

According to Thorp himself they were collaborators on the roulette scheme.

“The first wearable computer was conceived in 1955 by the author to predict roulette, culminating in a joint effort at M.I.T. with Claude Shannon in 1960-61. The final operating version was tested in Shannon’s basement home lab in June of 1961. […] The Shannons and Thorps tested the computer in Las Vegas in the summer of 1961.”

It was just an idea before they jointly developed it.

Also, there is J. Doyne Farmer [1], who was part of a group that used computers in their shoes, early 1980s, to "game" roulette tables in Los Vegas. Story is told in Thomas Bass's interesting book, "The Eudaemonic Pie". [2]

[1] https://en.wikipedia.org/wiki/J._Doyne_Farmer [2] https://en.wikipedia.org/wiki/The_Eudaemonic_Pie

The full story of the invention of the first wearable computer is told in Ed Thorp's memoir https://www.amazon.com/gp/aw/d/B00SEFEYCI/

Highly recommended!

It’s amazing what throwing a ton of computers at problem gives you.

In the 80s-90s, Shannon’s predict the next token idea gave us spell check.

In 2000-2010 it gave us Siri & Google Home.

In 2020 it gave us ChatGPT.

My prediction is that it will take Apple and Google ten years to replace or upgrade their installed base of conditional liars with an installed base of statistical liars.

Sorry to be pedantic, but Siri was released 2011 and Google Home 2016. With all the recent progress on LLMs, people forget that these “old” assistants are rather recent developments.

I've been following speech recognition, in particular, since the mid-90s. Around 2000, after many hours of training the best speech recognition software available commercially, with a slight speech impediment (which does not confuse people, for some reason) I personally concluded that even tailored speech recognition of general speech for a specific person was not viable yet. General purpose speech recognition of an arbitrary speaker perhaps with an accent that was even 80% accurate would be a long, long time away. If you had asked me to guess I'd probably have said after 2050.

I remember a presentation by Bill Gates, about the cutting edge statistical modelling based translation and speech recognition at Microsoft, similar to what Google was doing. The software was live-transcribing him, well enough that he could be understood. I was floored. Assuming this wasn't tailored to Bill specifically for the demo, it was revolutionary technology of the kind I had expected to take much longer to develop. That was 2008. At the time the notion that speech might become a common interface still seemed rather far-fetched to many. By 2018 such tech was everywhere. Deep learning based models have now closed much of the remaining gap in just the last couple years.

You are right, but Adam Cheyer (the Siri founder) worked on it for a long time before it was sold to Apple. https://en.m.wikipedia.org/wiki/CALO

Of course, but going from DARPA PAL and CALO to Siri is like going from Mikolov et al. (2013)’s word2vec to ChatGPT.

Digressions on typography and formatting:

* How did Shannon get nice looking math before LaTeX? John Nash's thesis in 1950 (only 32 pages long!) had handwritten math: https://library.princeton.edu/special-collections/sites/defa...

* Strange to see see citations as footnotes, not a references section. (Nash's thesis was kind enough to include two cites in its references.) Was this typical?

There was no computer involved when publishing at the time. It certainly just took time and money for a professional typesetter to painstakingly set symbol after symbol on his manual typesetting machine.

Or type it into a Linotype.

It's called professional typesetting. The manuscript sent to BSTJ would have been typed, probably double-spaced, and I assume with hand-drawn equations. Once editing was finished, it would go to the typesetter. Answers on this Stackexchange thread go into some detail: https://tex.stackexchange.com/questions/244082/typesetting-b... On page 290 of a linked source you can see an example of typed/handwritten copy that the typesetter (a person) would have been working from: https://gwern.net/doc/design/typography/2003-matrix-typeandt...

Written 53 years ago, if only Shannon experimented predicting next word instead of next letter....

It'd still be a Markov model so much more than generating regular grammars is out of the question.

Either I'm misunderstanding you, or you're misunderstanding the GP. The GP is getting at large language models being equivalent to very high order Markov models combined with calculating argmax over all possible outputs.

Huh, I suppose we're both right. Large language models are markov models since their transition probabilities are completely determined by the input. Consequently they cannot generate and recognize matching brackets correctly.

In practice however the state space is so humongously large that this barely comes up in any reasonable example.

"Consequently they cannot generate and recognize matching brackets correctly."

Can you expand on this? Not quite following.

This is a bit of a technicality, so forgive me for introducing some technical terms first.

I'm not sure how much you know about regular grammars, but basically they're the kind of thing that a regular expression can match. Now regular expressions can do a lot but they have their limitations, in particular they cannot distinguish a sequence of matched brackets '((())())' form one of unmatched brackets '(()(', or at least not with 100% accuracy.

It turns out that regular expressions are precisely the languages that can be recognized by finite state machines. Which is kind of equivalent to the possible outputs of a markov model.

Since large language models only have a finite number of states they must have the same limitations, which means it is fundamentally impossible to make them only generate balanced brackets. They get away with it by having a ridiculous number of states, so they might not be able to deal with arbitrarily deep nesting, but they can still get far enough that you won't generally notice.

So I can go on to ChatGPT and expect it will never be able to close brackets for me?

No, it means that there is some input for which it will fail to properly balance brackets. The parameter count would have to be astronomical for this to fall outside the token window size.

ChatGPT Example:

> Add the correct number of closing parentheses to this string: (((((((((((((((((((((((((((((((

>> ))))))))))))))))))))))))))))

>> The correct number of closing parentheses to balance the opening parentheses is 21.

which is not correct

You could probably get it to generate code that does the correct operation, though, right? (Returns the correct number of parents.) It's kind of funny if that's the case.

It think the OP is getting at, a model can never be 100% accurate at this. Instead, the limit approaches 100% as the language model grows, but it never actually gets there. There will always be aliasing going on.

I think an analogy would be like saying that you can't represent pi as a floating point number. Precision can be increased by adding more bits, but there's a fundamental limitation because of the underlying storage mechanism.

I see. In any case, I don't think anything stops them from augmenting ChatGPT(-as-seen-by-the-user) so that it incorporates modules that aren't mere language models and thus allow richer behavior, as I suspected they were already doing:

https://news.ycombinator.com/item?id=35472089

Sipser[1] provides the clearest detailed description I've seen. You don't have to read anywhere near the whole thing. He covers the regular languages and (non)deterministic finite automata in the first few chapters.

[1] https://www.goodreads.com/en/book/show/400716

Transformers can't match brackets beyond some fixed depth, but RNNs and LSTMs can match unbounded brackets.

Depending on your starting assumptions, Transformers, RNNs and LSTMS can either be

a) Turing-complete, in which case they can all match unbounded brackets, or

b) they are all not Turing-complete, LSTMs might be able to match unbounded brackets (if there is only one type of bracket), while RNNs and Transformers can't.

For Transformers you would need an infinite number of self-attention layers.

For RNN/LSTM all you need is enough neurons to implement a counter.

> For RNN/LSTM all you need is enough neurons to implement a counter.

For an arbitrary depth, that would need to be an infinitely sized counter. (I presume you know this, but this is why a push-down automaton can always close parens, but a finite state machine can only close parens up to a finite nesting depth.)

So, "all you need is enough neurons" for an RNN/LSTM is equivalent to just saying you just need to scale the LMM state large enough to handle your use case.

In reality, ignoring rdrand (and other quantum noise instructions) and ignoring using I/O for external storage, all of our computers are (gigantic) finite state machines. Technically, our programming languages might be Turing complete, but our near-infinite memory implementations are actually finite state machines, not Turing-complete. Though, you only run into the difference when you fill the whole machine's memory.

So, I think a more important question is how efficiently different finite state machines make use of their state sizes for a given problem. How many neurons would it take to match parens to a maximum depth of 2^40 for an RNN/LSTM vs. an LLM?

An RNN with infinite-precision rational weights can implement a counter with a bounded number of neurons. With finite precision the number of neurons scales linearly in your desired depth of matching brackets: https://arxiv.org/pdf/2010.07515.pdf

For a Transformer you need to add a new layer of self-attention to increase bracket matching depth by 1. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306...

Transformers are formally a lot weaker than RNNs/LSTMs.

"LLMs are Markov Models"... There's a reason we don't use Markov models anymore though (for language modeling - still used heavily in RL). The density of information and composability you get from MHA makes the problem far more tractable.

Wasn't it 73 years ago?

Yes, indeed. Too late to edit.

The linked paper isn't rendering so well for me. Here's another version that's better?

http://languagelog.ldc.upenn.edu/myl/Shannon1950.pdf

Ironic that this paper / concept should be suffering from an extra dose of entropy.

For a comparison to modern language models see also

https://www.lesswrong.com/posts/htrZrxduciZ5QaCjw/language-m...

More readable PDF: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=677...

This is a good video for an overview of what Shannon influenced.

https://www.youtube.com/watch?v=z2Whj_nL-x8

"the strong tendency of H to follow T or of V to follow Q"

Shouldn't that be U instead of V? Or am I missing something.