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

151–160 of 177 posts

Re: Markov Chains are the Original Language Models

#151

Post by kromem »

acjohnson55 wrote: post #144
kromem wrote: post #137

Earlier quoted context omitted.

No, the self-attention for the transformer in GPT means it isn't a Markov Chain. A blog post of you want to read more: https://medium.com/@andrew_johnson_4/are-transformers-markov...

Isn't it though, if you consider the entire context to be part of the state? It seems like his argument is based on an assumption of the Markov model only using the current word as its state.

It's not the only one stating this:

https://safjan.com/understanding-differences-gpt-transformer...

If we're broadening the scope of a Markov chain to consider the entire system as the current state that's being used to determine the next step of operation, then isn't literally every computer program a Markov chain under that definition?

You can't just include the memory of previous states which the current state is depending on as being part of the "current state" to fit the definition of a Markov chain without having broadened the scope to the point the definition becomes meaningless.

Re: Markov Chains are the Original Language Models

#152

Post by acjohnson55 »

kromem wrote: post #151
acjohnson55 wrote: post #144

Earlier quoted context omitted.

Isn't it though, if you consider the entire context to be part of the state? It seems like his argument is based on an assumption of the Markov model only using the current word as its state.

It's not the only one stating this: https://safjan.com/understanding-differences-gpt-transformer... If we're broadening the scope of a Markov chain to consider the entire system as the current state that's being used to determine the next step of operation, then isn't literally every computer program a Markov chain under that definition? You can't just include the memory of previous states which the current state is…

No, every computer program is not a Markov chain, because computer programs aren't random processes.

Look up the concepts of "higher-order Markov chains" or "Markov chains with memory".

Obviously, there are reasons that people don't directly implement LLMs as very high-order Markov chains. But it doesn't mean that the equivalence isn't mathematically or intuitively useful.

I'm just a non expert, but as far as I can tell, if there's an upper bound to the lookback in the context window, I don't see how that transformer isn't strictly less powerful than a Markov chain of that order. It's just a computationally tractable way to closely approximate it.

If the potential lookback distance is unbounded, then I think you could say that it's different from a finite-order Markov chain.

Re: Markov Chains are the Original Language Models

#153

Post by candiodari »

fjkdlsjflkds wrote: post #134
Jensson wrote: post #126

Earlier quoted context omitted.

> It's not. There's fundamental architectural differences that couldn't be bigger. LLM architecture is a markov chain to the core. It isn't a lookup table like old markov chains but it is still a markov chain: next word prediction based on previous words.

Thanks for repeating this. Seems like most people fail to understand that LLMs (as they are implemented these days) are markov chains by definition , regardless of how much "better" they are compared to "Dissociated Press"-style markov chains based on lookup tables. > A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which *the probability of each event depends only on…

This is the magical human intelligence/“AI has no soul” argument just presented in reverse. It totally ignores that human minds are emergent: no single part of your brain, nor it’s connection to the outside world are intelligent.

Despite this it’s equally obvious that the intelligence IS in the human brain, inside the skull. Shoot the right parts (frequently done by accident, so many subjects for research) and the intelligence is gone. It IS possible to radically change behaviour of a human by destroying part of the brain. There is no external soul that manages things behind the scene. Human intelligence and our souls are emergent. The are “software”, not hardware.

All the criticism against AI you make therefore applies equally to a human mind. Yet obviously it shouldn’t. To be more exact: it fails to differentiate between human minds and AI. Behaviours could emerge at any time in AI, even in transformer networks. Hell, transformers are famous for their emergent behaviours. Yes their components are obviously not intelligent. Neither are your components, or mine.

Yes the machine has no soul. The problem is: neither do you.

Re: Markov Chains are the Original Language Models

#154

Post by kromem »

acjohnson55 wrote: post #152
kromem wrote: post #151

Earlier quoted context omitted.

It's not the only one stating this: https://safjan.com/understanding-differences-gpt-transformer... If we're broadening the scope of a Markov chain to consider the entire system as the current state that's being used to determine the next step of operation, then isn't literally every computer program a Markov chain under that definition? You can't just include the memory of previous states which the current state is…

No, every computer program is not a Markov chain, because computer programs aren't random processes. Look up the concepts of "higher-order Markov chains" or "Markov chains with memory". Obviously, there are reasons that people don't directly implement LLMs as very high-order Markov chains. But it doesn't mean that the equivalence isn't mathematically or intuitively useful. I'm just a non expert, but as far as I can t…

The Markov chain by definition satisfies the Markov property (https://en.m.wikipedia.org/wiki/Markov_property).

If you want a more in depth sense of why it's not, look at the following link that describes the transformer architecture in detail and specifically goes over moving from a Markov process to one that no longer satisfies it, specifically around the following paragraph:

> The first thing that becomes apparent is that, when trying to predict the word that comes after ran, we no longer look at just one line, but rather a whole set of them. We've moved out of the Markov realm now. Each row no longer represents the state of the sequence at a particular point. Instead, each row represents one of many features that may describe the sequence at a particular point. The combination of the most recent word with each of the words that came before makes for a collection of applicable rows, maybe a large collection. Because of this change in meaning, each value in the matrix no longer represents a probability, but rather a vote. Votes will be summed and compared to determine next word predictions.

- https://e2eml.school/transformers.html

Re: Markov Chains are the Original Language Models

#155

Post by fennecbutt »

klyrs wrote: post #114
jjtheblunt wrote: post #68

Earlier quoted context omitted.

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

I like your question, and I cannot answer it. But I have a benchmark: I can write a Markov chain "language model" in around 10-20 lines of Python, with zero external libraries -- with tokenization and "training" on a text file, and generating novel output. I wrote it in several minutes and didn't bother to save it. I'm curious how much time & code it would take to implement this LLM stuff at a similar level of qualit…

Generally LLM architectures are pretty low code, I thought (not written one myself).

Then all of the complexity comes with the training/weight data.

Re: Markov Chains are the Original Language Models

#156

Post by foobarqux »

famouswaffles wrote: post #150
dwattttt wrote: post #148

Earlier quoted context omitted.

> You can perform any computation you like in a single pass if you have enough compute time. You can't perform _any_ computation. A single forward pass through a neutral network can perform many classes of computation, and it can _approximate_ all... but that's not a guarantee that the approximation will be good (and there's classes for which the approximation is pretty much guaranteed to be bad).

You're right but I didn't say anything about guarantees since that wasn't really the point of the argument. Yes, you can guarantee nothing but the point of discussion was whether a forward pass would deny specific classes of computations simply because it was just a forward class. It won't.

Yes in the same way that a lookup table can compute anything if you make it large enough (and where you need to know the size beforehand).

"Transformers are not Turing complete" https://www.lifeiscomputation.com/transformers-are-not-turin...

See here for example for a survey of work on the limits of computational expressivity of transformers https://www.semanticscholar.org/paper/Transformers-as-Recogn...

Re: Markov Chains are the Original Language Models

#157

Post by acjohnson55 »

kromem wrote: post #154
acjohnson55 wrote: post #152

Earlier quoted context omitted.

No, every computer program is not a Markov chain, because computer programs aren't random processes. Look up the concepts of "higher-order Markov chains" or "Markov chains with memory". Obviously, there are reasons that people don't directly implement LLMs as very high-order Markov chains. But it doesn't mean that the equivalence isn't mathematically or intuitively useful. I'm just a non expert, but as far as I can t…

The Markov chain by definition satisfies the Markov property ( https://en.m.wikipedia.org/wiki/Markov_property ). If you want a more in depth sense of why it's not, look at the following link that describes the transformer architecture in detail and specifically goes over moving from a Markov process to one that no longer satisfies it, specifically around the following paragraph: > The first thing that becomes appare…

The author made the choice to depart from a literally implementing a Markov model. That's a practical choice, but not strictly necessary if you're not worried about practicality. I think you're getting hung up on engineering decisions made to actually implement a language model, versus the theory.

In the same section, the author says:

> The difference between this second-order-with-skips and a full umpteenth-order model is that we discard most of the word order information and combinations of preceeeding words. What remains is still pretty powerful.

This implies that sure, you could hypothetically do an umpteenth-order model, but dropping down to something that approximates it "is still pretty powerful".

Thanks for the link, by the way! I'm definitely going to read through the whole thing. I'm desperately trying to understand this technology.

Re: Markov Chains are the Original Language Models

#158

Post by max_ »

famouswaffles wrote: post #142
max_ wrote: post #80

Earlier quoted context omitted.

Have they really mastered language or are they mimicking it. Do Submarines swim like fish?

Have planes mastered flight or are they mimicking it ? Can you mimick flight ? Is that a distinction that has any meaning ?

Yes. Planes don't fly the same way that birds do.

They are go up in the air like birds but what they are doing to get up & be up in the sky is very different.

Just like LLMs, planes are way less energy efficient than birds. Just like how Human brains are way more efficient than Convents & LLMs

Re: Markov Chains are the Original Language Models

#159

Post by famouswaffles »

foobarqux wrote: post #156
famouswaffles wrote: post #150

Earlier quoted context omitted.

You're right but I didn't say anything about guarantees since that wasn't really the point of the argument. Yes, you can guarantee nothing but the point of discussion was whether a forward pass would deny specific classes of computations simply because it was just a forward class. It won't.

Yes in the same way that a lookup table can compute anything if you make it large enough (and where you need to know the size beforehand). "Transformers are not Turing complete" https://www.lifeiscomputation.com/transformers-are-not-turin... See here for example for a survey of work on the limits of computational expressivity of transformers https://www.semanticscholar.org/paper/Transformers-as-Recogn...

No, Transformers with memory are turing complete. Like i said, the modifications are trivial.

https://arxiv.org/abs/2301.04589

Re: Markov Chains are the Original Language Models

#160

Post by famouswaffles »

max_ wrote: post #158
famouswaffles wrote: post #142

Earlier quoted context omitted.

Have planes mastered flight or are they mimicking it ? Can you mimick flight ? Is that a distinction that has any meaning ?

Yes. Planes don't fly the same way that birds do. They are go up in the air like birds but what they are doing to get up & be up in the sky is very different. Just like LLMs, planes are way less energy efficient than birds. Just like how Human brains are way more efficient than Convents & LLMs

You didn't answer my question. I didn't ask you whether planes flew like birds do. I asked you if planes are "mimicking" flight and if that's a statement that makes any sense at all.
Post reply on HN