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

141–150 of 177 posts

Re: Markov Chains are the Original Language Models

#141

Post by famouswaffles »

lukev wrote: post #139
famouswaffles wrote: post #101

Earlier quoted context omitted.

>The training and loss function of the foundation models are completely oriented towards next-token accuracy. This doesn't mean anything. Loss function and training only concern themselves with the result of the prediction. The in-between, the computation, training does not care except as a means to an end. It's not Input A > Output B. It's Input A > Computation > Output B. That Computation could quite literally be a…

But in an LLM it is not an arbitrary computation. Very specifically, it is a single forward pass through a neural network. Neural networks are very general function approximators so yes, there is some room for emergent behavior. But it could _not_ be "quite literally anything." It's plugging in values for a single (very big) equation. I think we do ourselves a disservice by pretending it's more of a black box than it…

How many passes it is irrelevant. You can perform any computation you like in a single pass if you have enough compute time.

Trained transformers have limited computer time per token so each query is compute limited, but this is trivially increased, by increasing tokens, or by increasing dimensions in the next training round so that each token permits more compute time.

A forward pass is not one big equation and I have no clue who you think it is. It's a series of computations, computations that depends on the query awaiting prediction. It's not even the same series of computations for each query because not all neurons are getting activated period and even when the same neurons get activated, they are not necessarily getting activated in the same way.

Re: Markov Chains are the Original Language Models

#142

Post by famouswaffles »

max_ wrote: post #80
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?

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

Re: Markov Chains are the Original Language Models

#143

Post by acjohnson55 »

SilasX wrote: post #69
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…

>However, explaining that a LLMs are really just iterated next-word prediction based on a statistical model of the preceding words is something that most people can grok, and in a useful way: in my experience, it actually helps give people a useful intuition for why and how models hallucinate and what kind of things they're good/bad at. At risk of showing my deficient understanding: that isn't actually true, is it?[1…

My understanding is that LLMs are basically approximations of Markov chains where the state and probability distribution is thousands of words long. If you could directly compute and use that matrix, you'd get the same result. But that would be insane.

Re: Markov Chains are the Original Language Models

#144

Post by acjohnson55 »

kromem wrote: post #137
Jensson wrote: post #124

Earlier quoted context omitted.

LLM are markov chains, a markov chain is a general concept and not just a text model technique. You must be thinking about the very simple markov chain models we had before where you just predicted the next word by looking up sentences with the same preceding words and picking a random of those words, that is also a markov chain just like LLM but a much simpler one, you are right LLMs aren't like that but they are st…

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.

Re: Markov Chains are the Original Language Models

#145

Post by yobbo »

If we let Markov model mean a probability distribution over a sequence defined as P[ X(t) | X(t-1) ] , then a transformer is specifically not a Markov model. The Markov property means each element is conditional on only the previous element ("context length" = 1).

A discrete table based probability distribution over possible words, as in the link, is a Markov language model, but not a meaningful contestant among Markov models for language modelling. The latest contestants here are things like RWKV, ResNet, SSMs, and so on which might be better thought of as HMMs.

An HMM is a Markov chain of hidden ("latent") states, rather than over tokens or words. Variations have been used for speech recognition and language modelling for 20-30 years.

Re: Markov Chains are the Original Language Models

#146

Post by yobbo »

Jensson wrote: post #124
kromem wrote: post #123

Earlier quoted context omitted.

It would be more accurate to say that a Markov chain is an example of a method that would perform relatively well at the same training task as a LLM. So too, might a human trying to predict the next tokens. But a human and a Markov chain are not the same underlying process to achieve next token prediction, and neither is the same underlying process as a LLM.

LLM are markov chains, a markov chain is a general concept and not just a text model technique. You must be thinking about the very simple markov chain models we had before where you just predicted the next word by looking up sentences with the same preceding words and picking a random of those words, that is also a markov chain just like LLM but a much simpler one, you are right LLMs aren't like that but they are st…

The term "Markov chain" is used only for sequences where the "current" state depends only on the previous state.

https://en.wikipedia.org/wiki/Markov_property

Re: Markov Chains are the Original Language Models

#147

Post by jjtheblunt »

samus wrote: post #131
thfuran wrote: post #112

Earlier quoted context omitted.

If the minimal representation of a model of the behavior is "way bigger", why are you disputing that it's more complicated? What's the difference?

The difference is the capabilities. LLMs don't necessarily need billions of Parameters. In fact, useful models (like the one used in never Apple devices' autocomplete) has only like 50 million. Markov chain... I guess there is probably a reason why we don't use them instead of neuronal networks. Maybe somebody more knowledgeable can enlighten us, but I suspect one might need magnitudes more parameters.

well the neuronal networks are able (when sized appropriately) to memorize the seen markov chains, and more, really.

Re: Markov Chains are the Original Language Models

#148

Post by dwattttt »

famouswaffles wrote: post #141
lukev wrote: post #139

Earlier quoted context omitted.

But in an LLM it is not an arbitrary computation. Very specifically, it is a single forward pass through a neural network. Neural networks are very general function approximators so yes, there is some room for emergent behavior. But it could _not_ be "quite literally anything." It's plugging in values for a single (very big) equation. I think we do ourselves a disservice by pretending it's more of a black box than it…

How many passes it is irrelevant. You can perform any computation you like in a single pass if you have enough compute time. Trained transformers have limited computer time per token so each query is compute limited, but this is trivially increased, by increasing tokens, or by increasing dimensions in the next training round so that each token permits more compute time. A forward pass is not one big equation and I ha…

> 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).

Re: Markov Chains are the Original Language Models

#149

Post by oopsthrowpass »

Back around 2002 we built an IRC bot that logged everything in a channel, built up a frequency table of which word follows what word and then randomly would spew out some text using a random walk of the frequency tables and had some logic for when to stop (I think probability increased with sentence length).

Sometimes it came up with very funny stuff, but mostly non-sense.

Re: Markov Chains are the Original Language Models

#150

Post by famouswaffles »

dwattttt wrote: post #148
famouswaffles wrote: post #141

Earlier quoted context omitted.

How many passes it is irrelevant. You can perform any computation you like in a single pass if you have enough compute time. Trained transformers have limited computer time per token so each query is compute limited, but this is trivially increased, by increasing tokens, or by increasing dimensions in the next training round so that each token permits more compute time. A forward pass is not one big equation and I ha…

> 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.
Post reply on HN