Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Markov Chains are the Original Language Models

elijahpotter.dev

Post reply on HN
Print view View original

71–80 of 177 posts

Re: Markov Chains are the Original Language Models

#71

Post by nextos »

lukev wrote: post #52

What's actually happening in a LLM is many orders of magnitude more complex than a Markov chain. However, I agree that they're an amazing pedagogical tool for the basic principles of how a LLM works, even to a non-technical audience. Many people try to "explain" LLMs starting with the principles of neural networks. This rarely works well: there are some significant conceptual leaps required. However, explaining that…

HMMs are much more similar to S3, S4, and other deep state-space models than to transformers.

In fact, HMMs are discrete shallow state-space models.

I believe S4 and successors might become serious contenders to transformers.

For a detailed tutorial, see https://srush.github.io/annotated-s4

Re: Markov Chains are the Original Language Models

#72

Post by geoelectric »

theGnuMe wrote: post #58
CamperBob2 wrote: post #42

Earlier quoted context omitted.

It's not just window size. It's the difference between syntax and semantics. A Markov model, by definition, works only with literal token histories. It can't participate meaningfully in a conversation unless the user happens to employ token sequences that the model has seen before (ideally multiple times.) An LLM can explain why it's not just a Markov model, but the converse isn't true. Now, if you were to add high-d…

>high-dimensional latent-space embedding to a Markov model That's what we call a hidden Markov model. >There's a school of thought that says that lossy compression doesn't just require intelligence, it is intelligence, and LLMs can be seen as an example of that equivalence. SVD is used to implement lossy compression as does JPEG encoding... these algorithms are in no way intelligent.

They’re doing highly specific tasks where the intelligence can come from the designer of the algorithm.

In particular, JPEG has intelligence encoded about how graphics are displayed, what detail we won’t notice is missing, and what artifacts we won’t notice are present, much like the psychoacoustic models behind lossy music compression schemes like MP3.

But we had to feed an encoder that by way of algorithmic design. It’s hardcoded intelligence, like any other function, but with a lot more outside knowledge required to do it right than a sort or swap.

I’d call an LLM a more general problem solver. It can write cogent limericks, convincingly screw up math, summarize papers it’s never seen before, generate book plots or character arcs based on specific requests, translate to a language you just made up and explained in the prompt, etc.

The intelligent bits are emergent and can do something reasonable with novel input, even if it doesn’t closely resemble the exact material it was trained on.

The comparison would be a process that could lossy-compress any kind of sensory media possible with no perceptible loss, based solely on its training on human capabilities and how the reproduction devices work—i.e. it could create the JPEG algorithm, not just perform it.

Re: Markov Chains are the Original Language Models

#73

Post by feoren »

unoti wrote: post #38

It's true that Markov chains are very limited in their capabilities. But one thing I love about them is that they are one of the simplest and most intuitive ways to write code that *learns* from input data. If you're never written something that *learns*, try it out! Here's a very primitive one I wrote recently to explain the basic idea and explains it along the way. https://github.com/unoti/markov-basics/blob/main/m…

> that they are one of the simplest and most intuitive ways to write code that learns from input data

Linear regression is significantly simpler and also learns from input data.

Re: Markov Chains are the Original Language Models

#74

Post by skrebbel »

thfuran wrote: post #70
jjtheblunt wrote: post #68

Earlier quoted context omitted.

Genuine question: what do you mean by many orders of magnitude more complex?

A typical demonstration markov chain probably has a length of around 3. A typical recent LLM probably has more than three billion parameters. That's not precisely apppes to apples, but the LLM is certainly vastly more complicated.

The way you describe it, it doesn't seem much more complicated to me, from a “how does it work” perspective, just way bigger.

Re: Markov Chains are the Original Language Models

#75

Post by rwmj »

thfuran wrote: post #70
jjtheblunt wrote: post #68

Earlier quoted context omitted.

Genuine question: what do you mean by many orders of magnitude more complex?

A typical demonstration markov chain probably has a length of around 3. A typical recent LLM probably has more than three billion parameters. That's not precisely apppes to apples, but the LLM is certainly vastly more complicated.

Number of parameters is not the difference. A Markov chain can easily be a multi-dimensional matrix with millions of entries. The significant difference is that a length 3 Markov chain can only ever find connections between 3 adjacent symbols (words, usually). LLMs seem to be able to find and connect abstract concepts at a very long and variable distances in the input.

Nevertheless I agree with the premise of the posting. I used Markov chains recently to teach someone what a statistical model of language is, followed by explaining to them the perceptron, and then (hand waving a bit) explaining how many large, deep layers scales everything up massively.

Re: Markov Chains are the Original Language Models

#76

Post by bbor »

BlueTemplar wrote: post #55
mewpmewp2 wrote: post #41

Earlier quoted context omitted.

Idea behind complexity can be very simple, but at scale work yield in very different results. To compare Markov Chain with an LLM is kind of like to compare a single cell organism to a human being because we both are based on cells.

As already mentioned, Markov chains were already used in practice as (poor) Turing tests (IMHO working best in art projects, and sadly, spam). Sure, today's LLMs blow them out of the water, but the difference was much less striking with neural networks even as late as 2010.

That’s interesting you put the date at 2010! When I learned machine learning in ~2016-2018, markov chains were THE fundamental problem tool of NLP still. Neural networks were all the rage ofc, but still… could you tell me what tech/change you’re thinking of?

For example, I remember /r/SubredditSimulator blowing my mind, and I’m pretty sure that was markov chains

Re: Markov Chains are the Original Language Models

#77

Post by max_ »

feoren wrote: post #73
unoti wrote: post #38

It's true that Markov chains are very limited in their capabilities. But one thing I love about them is that they are one of the simplest and most intuitive ways to write code that *learns* from input data. If you're never written something that *learns*, try it out! Here's a very primitive one I wrote recently to explain the basic idea and explains it along the way. https://github.com/unoti/markov-basics/blob/main/m…

> that they are one of the simplest and most intuitive ways to write code that learns from input data Linear regression is significantly simpler and also learns from input data.

Markov chains are basically lookup tables. I don't see how linear regression is simpler that that.

Re: Markov Chains are the Original Language Models

#78

Post by intalentive »

Claude Shannon showed you could use n-grams to represent language. Then Chomsky invented automata / formal languages theory to show why it couldn’t work.

IIRC transformers are at the very bottom of the Chomsky hierarchy, and yet they are clearly able to master English grammar.

What gives?

Re: Markov Chains are the Original Language Models

#80

Post by max_ »

intalentive wrote: post #78

Claude Shannon showed you could use n-grams to represent language. Then Chomsky invented automata / formal languages theory to show why it couldn’t work. IIRC transformers are at the very bottom of the Chomsky hierarchy, and yet they are clearly able to master English grammar. What gives?

Have they really mastered language or are they mimicking it.

Do Submarines swim like fish?

Post reply on HN