Hacker News Reader

Comment by marcodiego | Hacker News Reader

> This is a baby GPT with two tokens 0/1 and context length of 3, viewing it as a finite state markov chain.

What is actually the difference between this and a "pure" Markov chain? Is GPT simply a Markov chain?

EDIT: Better explained here: https://colab.research.google.com/drive/1SiF0KZJp75rUeetKOWq...

The mathematical modeling of most NLP tasks is Markovian. (More specifically, they tend to be HMMs, Hidden Markov Models). One of the popular "solutions" for Markovian processes is the Metropolis algorithm which you might find relevant. Note in statistical learning the mathematical formulation generally operates as part of the loss function, the actual "model" is usually a neural network (in the context of deep or variational learning).

Yes but in the same way as saying that computers are just a Markov chain.

After all the epic content and research, I think this was your worst explanation ever.

Pay no mind to him I think it’s brilliant. There, canceled out :)

Many of us look to you as the GOAT of teaching

Sorry, I just didn't like the comparison between saying GPT is a markov chain and computers are a markov chain. Really learned something from the actual colab. Thank you, appreciated. Nobody likes a sad karpathy.

Unfair and irrelevant. Keep it up, Andrej!

Computers are (with a couple caveats) deterministic, so I think the better analogy would be to say that it's the same as saying that "computers are just state machines".

But this is a bit nitpicky. The core idea is of course conveyed either way, that yes, this very abstract model does describe it while also completely missing that the magic is in how it's done.

If I can continue the nitpickery, plenty of computer algorithms are deterministic but also pseudorandom--including Markov chains. Only when the randomness is outside your control are things truly non-deterministic. A simulation with many possible outcomes is still deterministic if you get to choose the "seed".

In other words, statistical permutations are deterministic if you control all the input variables (in terms of computer science; physics is another story).

Computers have memory! Oh, wait... so does ChatGPT. Or am I forgetting something...

>Is GPT simply a Markov chain?

Yes, but much more efficiently stored and looked up than just a massive table. The way its very large space is encoded in a small amount of memory is what makes GPT so interesting.

A neural net instead of a table?

A markov chain maps states to states. You move from word "I" to word "will" or "can" or "want" The transition probabilities could be stored in a huge table. You have a word and the probability of each other word. Draw a number and hop. [1,2]

Alternatively you could ask a neural net for the next state. Pass it the current token or the last 4000 token.

[1] https://towardsdatascience.com/text-generation-with-markov-c... [2] https://crowintelligence.org/2021/05/27/a-simple-markov-chai...

GPT is not architecturally implemented as a Markov chain.

But given enough time one could model it as one.

Even in the case of a full size GPT, one could equivalently write out a lookup table for every possible permutation of tokens in the context window and the resulting output distribution. The table would of course be impossibly large.

Due to combinatorial explosion this would be infeasible even for a single input vector.

Sort of, but only if you consider that the states are massive. It’s not just “what’s the next word after this one.” It’s, “what’s the next word after this one, considering the other several hundred other words that came first.”

So, the input sequence is an extremely high-dimensional state value in a gigantic Markov chain.

To me, that sounds like not a Markov chain. Yes if you consider the Markov chain over entire sequences, but that’s not what people mean with Markovian.

No, gpt is generative.

How is a Markov chain “non-generative”?

Since every state has a set of probabilities for the next state, I guess you could call it that. It would be very misleading, though.

Reply on news.ycombinator.com