9 ms·
Prediction and Entropy of Printed English (1950) [pdf]
- marvel_boy 3y agoWritten 53 years ago, if only Shannon experimented predicting next word instead of next letter....
- contravariant 3y agoIt'd still be a Markov model so much more than generating regular grammars is out of the question.
- KMag 3y agoEither 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.
- contravariant 3y agoHuh, 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.
- HFguy 3y ago"Consequently they cannot generate and recognize matching brackets correctly." Can you expand on this? Not quite following.
- contravariant 3y agoThis 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.
- SilasX 3y agoSo I can go on to ChatGPT and expect it will never be able to close brackets for me?
- xigency 3y agoNo, 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
- smolder 3y agoYou 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.
- 3y ago
- canjobear 3y agoTransformers can't match brackets beyond some fixed depth, but RNNs and LSTMs can match unbounded brackets.
- shawntan 3y agoDepending 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.
- canjobear 3y agoFor Transformers you would need an infinite number of self-attention layers. For RNN/LSTM all you need is enough neurons to implement a counter.
- KMag 3y ago> 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?
- 3y ago
- chaxor 3y ago"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.
- taneliv 3y agoWasn't it 73 years ago?
- marvel_boy 3y agoYes, indeed. Too late to edit.
- gdiamos 3y agoIt’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.
- davidthewatson 3y agoMy 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.
- woodson 3y agoSorry 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.
- retrac 3y agoI'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.
- gdiamos 3y ago
- abetusk 3y agoThe linked paper isn't rendering so well for me. Here's another version that's better? http://languagelog.ldc.upenn.edu/myl/Shannon1950.pdf http://languagelog.ldc.upenn.edu/myl/Shannon1950.pdf
- HlessClaudesman 3y agoIronic that this paper / concept should be suffering from an extra dose of entropy.
- cavedave 3y agoThat'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.
- xdavidliu 3y agopretty sure you mean Ed Thorpe, though Thorpe did eventually collaborate with Shannon. https://www.cs.virginia.edu/~evans/thorp.pdf https://www.cs.virginia.edu/~evans/thorp.pdf
- riemannzeta 3y agoAccording to Thorp himself they were collaborators on the roulette scheme.
- kgwgk 3y ago“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.
- ggerules 3y agoAlso, 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 https://en.wikipedia.org/wiki/J._Doyne_Farmer [2] https://en.wikipedia.org/wiki/The_Eudaemonic_Pie https://en.wikipedia.org/wiki/The_Eudaemonic_Pie
- riemannzeta 3y agoThe 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/ https://www.amazon.com/gp/aw/d/B00SEFEYCI/ Highly recommended!
- kqr 3y agoWhat'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.
- deleted 3y ago[deleted]
- madcaptenor 3y agoWill ChatGPT drag this downward even more?
- kqr 3y agoI 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.
- fooker 3y agoThis is like forcing a human to answer questions about brain anatomy. You’ll be lucky to get anything reasonable at all.
- zw123456 3y agoI 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.
- canjobear 3y agoYes, 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_evaluations https://crfm.stanford.edu/helm/v0.2.0/?group=targeted_evalua...
- 3y ago
- alberto_ol 3y agoThe copy in the internet archive seems better https://archive.org/details/bstj30-1-50/mode/2up https://archive.org/details/bstj30-1-50/mode/2up
- JoeDaDude 3y agoMy 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_Information_Theory/__uOqZeH5ZoC?hl=en https://www.google.com/books/edition/An_Introduction_to_Info...
- akhayam 3y agoIt'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-secrecy.pdf https://pages.cs.wisc.edu/~rist/642-spring-2014/shannon-secr... https://pure.mpg.de/rest/items/item_2383164/component/file_2383163/content 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.
- cosmojg 3y agoHeh, 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.
- UncleOxidant 3y ago3 fields - Don't forget his Masters thesis which revolutionized digital circuit design.
- nickpeterson 3y agoYeah, 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 ;)
- akhayam 3y agoYes, 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 :(
- bravura 3y agoDigressions 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/default/files/Non-Cooperative_Games_Nash.pdf 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?
- lelag 3y agoThere 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.
- throwuwu 3y agoOr type it into a Linotype.
- pjdesno 3y agoIt'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-before-tex-and-computers 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-typeandtypography.pdf https://gwern.net/doc/design/typography/2003-matrix-typeandt...
- deleted 3y ago[deleted]
- User23 3y agoDid Shannon introduce the term N-grams?
- javajosh 3y ago[flagged]
- dmbche 3y agoI think that's a load of nonsense.
- javajosh 3y agoIs it? https://equitablemath.org/#about https://equitablemath.org/#about As a liberal, am gonzo for diversity. As a capitalist, I recognize that talent is very rare and I think it is foolish to reject talent based on irrelevant personal details. As an intellectual, I am for focus and clarity. This kind of activism isn't the only source of distraction. But it's a big one right now. Feel free to disagree, but that's how I feel, and my feelings aren't nonsense.
- dmbche 3y ago"Resources and guidance to support Black, LatinX, and Multilingual students to thrive in grades 6-8" Literally the first line of your source Laughable
- LawTalkingGuy 3y agoThere's so much condescension in that sentence alone. They say 'LatinX', where the correct term is Latin. They specifically list black students because the constant message in the liberal USA is that black people aren't capable and need to be called out by skin color in all contexts so they can be helped across the line by virtuous white people who recognize their weakness. But keep reading the lesson plans and it goes on and on. Chapter 1 is "Dismantling Racism in Mathematics Instruction", and it claims that "White supremacy culture infiltrates math classrooms [...] perpetuate educational harm on Black, Latinx, [...]" - "greater focus on getting the 'right' answer ..." - "required to 'show their work' in standardized, prescribed ways." - "Independent practice is valued over teamwork or collaboration." God forbid individual minority students are given the ability to personally succeed without being forced into a group identity, or that they be taught how to use math to communicate with others. - "It also presupposes that “good” math teaching is about a Eurocentric type of mathematics, devoid of cultural ways of being." Yes, of course, because math is about the numbers! You can apply it to your personal cultural way of being after learning how to get correct answers. It's actual racism is to assume that all black people need to have a social-justice framework put in front of their academics to "help" them. Not help them to success, but to a white-constructed pseudo-success of wrong but "culturally correct" answers that is somehow the best they can be expected to achieve. - "study ethnomathematics and incorporate into all classrooms." In other words, don't try to help everyone achieve a common goal, create race-based targets and replace all education with them. "the practice of school mathematics in the US regulates the child by privileging:" - "algebra/calculus over geometry/topology/spatial reasoning;" - "rule following over rule breaking;" - "Western mathematics (culture free) over ethnomathematics" - "logic over intuition" Calculus encompasses geometry and spatial reasoning, so that's just wrong. They attack "Rule following" - like the rules that get you correct answers. Western mathematics (which they've just identified as the type of math focused on correct answers). And logic, damned logic, getting in the way of the "lessers" just doing what they culturally know is right rather than applying critical thought like white people. There's nothing in that course, or any of the rest, or in the critical theory that it came from, which is capable of helping, or even intended to help, any minority student. It only prioritizes raising students uneducated and with a bunch of misplaced racial baggage. If you don't believe me, or want to write it off as "what a white supremacist would say", read this: https://unherd.com/2022/02/anti-racism-betrays-asian-students/ https://unherd.com/2022/02/anti-racism-betrays-asian-student... "After the tragic killing of George Floyd in 2020, much of the virtue-signalling that followed focused on an unexpected target: admissions processes. Activists claimed children “of colour” weren’t getting their fair share of places at good schools — or, to be precise, black and Hispanic children weren’t. The same couldn’t be said of Asian children. And so Asian students became a convenient scapegoat for “anti-racists”. [...] in the months when America was rocked by race riots, self-described “equity warriors” described the Asian, mostly immigrant families of TJ as “white-adjacent” and “resource hoarders”. The white principal, Ann Bonitatibus, told us to check our “privileges”, [...] the local school board — all 12 members endorsed by the Democratic Party — voted to remove the school’s merit-based, race-blind admissions process, and replace it with one that was race-based. Along with other parents I was horrified by the school’s readiness to use identity, rather than achievement, as the basis of admissions. But when we objected, the Virginia education secretary, a Democrat, told our families that preparing for tests was like using illegal “performance enhancement drugs”. A black father, Harry Jackson, who spoke up for our cause was called a “motherfucker” selling “segregationist bullshit” — by a white activist who uses the Twitter handle @Antiracist14"
- gavi 3y agoThis is a good video for an overview of what Shannon influenced. https://www.youtube.com/watch?v=z2Whj_nL-x8 https://www.youtube.com/watch?v=z2Whj_nL-x8
- BubbleRings 3y ago"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.
- gravitronic 3y agoThe 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-Innovation/dp/0143122797 https://www.amazon.com/Idea-Factory-Great-American-Innovatio...
- cubefox 3y agoFor a comparison to modern language models see also https://www.lesswrong.com/posts/htrZrxduciZ5QaCjw/language-models-seem-to-be-much-better-than-humans-at-next?commentId=rRFqJ4bRKDBvznmyL https://www.lesswrong.com/posts/htrZrxduciZ5QaCjw/language-m...
- irsagent 3y agoMore readable PDF: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6773263 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=677...