5 ms·

"Consequently they cannot generate and recognize matching brackets correctly." Can you expand on this? Not quite following.

• contravariant 3y ago
  This 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 ago
    So I can go on to ChatGPT and expect it will never be able to close brackets for me?
    • xigency 3y ago
      No, 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 ago
        You 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 ago
      It 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 ago
        I 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 ago
  Sipser[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