6 ms·
Written 53 years ago, if only Shannon experimented predicting next word instead of next letter....
by marvel_boy 3y ago
Written 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.
- mywittyname 3y agoIt think the OP is getting at, a model can never be 100% accurate at this. Instead, the limit approaches 100% as the language model grows, but it never actually gets there. There will always be aliasing going on. I think an analogy would be like saying that you can't represent pi as a floating point number. Precision can be increased by adding more bits, but there's a fundamental limitation because of the underlying storage mechanism.
- SilasX 3y agoI see. In any case, I don't think anything stops them from augmenting ChatGPT(-as-seen-by-the-user) so that it incorporates modules that aren't mere language models and thus allow richer behavior, as I suspected they were already doing: https://news.ycombinator.com/item?id=35472089 https://news.ycombinator.com/item?id=35472089
- User23 3y agoSipser[1] provides the clearest detailed description I've seen. You don't have to read anywhere near the whole thing. He covers the regular languages and (non)deterministic finite automata in the first few chapters. [1] https://www.goodreads.com/en/book/show/400716 https://www.goodreads.com/en/book/show/400716
- 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.