5 ms·

You can model multiple-hop dependencies as a Markov chain by just blowing up the state space as a Cartesian product. Not that that would necessarily make sense

by t_mann 1y ago

You can model multiple-hop dependencies as a Markov chain by just blowing up the state space as a Cartesian product. Not that that would necessarily make sense in practice, but in theory Markov chains have enormous expressive power.

TeMPOraL 1y ago
> Not that that would necessarily make sense in practice, but in theory Markov chains have enormous expressive power. Right - but this feels like being half-way between transformers and lookup tables; the latter have enormous expressive power too, as long as you're willing to handle even more state. I'm curious what else could be put on that spectrum, and where. Maybe there's something weaker than transformers, but good enough for practical applications, while being more resource-efficient? Related thought: understanding and compression seem to be fundamentally the same thing.
- joquarky 1y ago
  > Maybe there's something weaker than transformers, but good enough for practical applications, while being more resource-efficient? I wish! Gboard is terrible at predicting the correct form of a word. It generally knows the best word, but it doesn't get from context that (e.g.) a gerund form of the verb is the most appropriate next
- joe_the_user 1y ago
  But no, as another poster comments, the state space blow up is much worse than transformers for much less [1]. Transformers have more kinds of statefulness while Markov chains seem simpler cause they just multiply the number of states - but that state-multiplication makes them completely impractical. They aren't flexible on a per-state basis, just the opposite. Basically, for most forms of complexity, Markov Chains are a strictly bad model. Perhaps if there was a way to "virtualize" the multiplication of states, you could do something reasonable. Idle speculation though. [1] https://news.ycombinator.com/item?id=45354488 https://news.ycombinator.com/item?id=45354488
- taneq 1y ago
  > Related thought: understanding and compression seem to be fundamentally the same thing. Both are fundamentally prediction. :)
- impulsivepuppet 1y ago
  Related and likely inspired by the related thought: https://www.mattmahoney.net/dc/ https://www.mattmahoney.net/dc/
  - refset 1y ago
    Specifically 1.4 "Compression is an Artificial Intelligence Problem" https://www.mattmahoney.net/dc/dce.html#Section_14 https://www.mattmahoney.net/dc/dce.html#Section_14
- jgalt212 1y ago
  Most of human life is a lookup table derived action.
  - econ 1y ago
    I notice that people with poor lookup table hardware need to think a lot more. The public part of the table is mostly populated with their thoughts. To quote a friend of mine: If I can't just trust the status quo I would have to question everything????
    - TeMPOraL 1y ago
      They're right, of course. You have to pick your battles. There's an art to that - and rules of that art are part of the lookup table too! #ItsSoMetaEvenThisAcronym
JohnHaugeland 1y ago
> but in theory Markov chains have enormous expressive power. as long as you don't care about the quality of what they're expressing. there's a reason they never did anything better than the postmodernism generator. putting paint in a cannon has enormous expressive power too, but if you aren't rothko, nobody's going to care
giovannibonetti 1y ago
> You can model multiple-hop dependencies as a Markov chain by just blowing up the state space as a Cartesian product. Where the state space would be proportional to the token length squared, just like the attention mechanisms we use today?
- AnotherGoodName 1y ago
  It blows up at 2^n for Markov chains actually. Eg imagine input of red followed by 32bits or randomness followed by blue forever. Markov chains would learn red leads to blue 32bits later. They’d just need to learn 2^32 states.
  - fooker 1y ago
    Yep, the leap away from this exponential blowup is what has made LLMs possible. A few more leaps and we should eventually get models small enough to get close to information theoretic lower bounds of compression.

by t_mann 1y ago

TeMPOraL 1y ago

> Not that that would necessarily make sense in practice, but in theory Markov chains have enormous expressive power. Right - but this feels like being half-way between transformers and lookup tables; the latter have enormous expressive power too, as long as you're willing to handle even more state. I'm curious what else could be put on that spectrum, and where. Maybe there's something weaker than transformers, but good enough for practical applications, while being more resource-efficient? Related thought: understanding and compression seem to be fundamentally the same thing.

joquarky 1y ago
> Maybe there's something weaker than transformers, but good enough for practical applications, while being more resource-efficient? I wish! Gboard is terrible at predicting the correct form of a word. It generally knows the best word, but it doesn't get from context that (e.g.) a gerund form of the verb is the most appropriate next
joe_the_user 1y ago
But no, as another poster comments, the state space blow up is much worse than transformers for much less [1]. Transformers have more kinds of statefulness while Markov chains seem simpler cause they just multiply the number of states - but that state-multiplication makes them completely impractical. They aren't flexible on a per-state basis, just the opposite. Basically, for most forms of complexity, Markov Chains are a strictly bad model. Perhaps if there was a way to "virtualize" the multiplication of states, you could do something reasonable. Idle speculation though. [1] https://news.ycombinator.com/item?id=45354488 https://news.ycombinator.com/item?id=45354488
taneq 1y ago
> Related thought: understanding and compression seem to be fundamentally the same thing. Both are fundamentally prediction. :)
impulsivepuppet 1y ago
Related and likely inspired by the related thought: https://www.mattmahoney.net/dc/ https://www.mattmahoney.net/dc/
- refset 1y ago
  Specifically 1.4 "Compression is an Artificial Intelligence Problem" https://www.mattmahoney.net/dc/dce.html#Section_14 https://www.mattmahoney.net/dc/dce.html#Section_14
jgalt212 1y ago
Most of human life is a lookup table derived action.
- econ 1y ago
  I notice that people with poor lookup table hardware need to think a lot more. The public part of the table is mostly populated with their thoughts. To quote a friend of mine: If I can't just trust the status quo I would have to question everything????
  - TeMPOraL 1y ago
    They're right, of course. You have to pick your battles. There's an art to that - and rules of that art are part of the lookup table too! #ItsSoMetaEvenThisAcronym

JohnHaugeland 1y ago

> but in theory Markov chains have enormous expressive power. as long as you don't care about the quality of what they're expressing. there's a reason they never did anything better than the postmodernism generator. putting paint in a cannon has enormous expressive power too, but if you aren't rothko, nobody's going to care

giovannibonetti 1y ago

> You can model multiple-hop dependencies as a Markov chain by just blowing up the state space as a Cartesian product. Where the state space would be proportional to the token length squared, just like the attention mechanisms we use today?

AnotherGoodName 1y ago
It blows up at 2^n for Markov chains actually. Eg imagine input of red followed by 32bits or randomness followed by blue forever. Markov chains would learn red leads to blue 32bits later. They’d just need to learn 2^32 states.
- fooker 1y ago
  Yep, the leap away from this exponential blowup is what has made LLMs possible. A few more leaps and we should eventually get models small enough to get close to information theoretic lower bounds of compression.