5 ms·

Thank you. Right now, my puny little brain is searching through what I would describe as "those distant and slightly vague memories" that make up my poor man's

by cs702 3y ago

Thank you. Right now, my puny little brain is searching through what I would describe as "those distant and slightly vague memories" that make up my poor man's knowledge of computational complexity theory. > Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned. Isn't that's true for linear RNN mechanisms too? Note that linear RNNs like RWKV and Mamba are linear in the number of tokens in the sequence, but not in the number of features per token.

nyrikki 3y ago
You don't typically get to the Sigma_2^P level unless are a sadist or forced. Attention works differently in RNNs, and it may be able to find different tractable forms, and may solve different problems, but increasing generalization is a reduction of compression in the general case. A many to one reduction to a recursively enumerable set gets you to finite time, a reduction to NP gets you to quadratic time. Obviously those are upper limits and specific instances or classes of instances may do better. P being inside NP is a good example. All ANNs are binary output, which helps with that. SNN or spikey neutral networks, which better model cortical neurons and have continuous output have problems with being un-computable without much complexity as an example. That can be viewed as the problems with computable numbers in place of the reals. But there are lots of interesting and practical things to solve. It is just those solutions will be more domain specific IMHO.
- cs702 3y ago
  Hmm... You're right: It's quite possible that the new crop of linear RNNs may not be able to solve the same problems as Transformers. It could also be that we will have to increase the depth of these linear RNNs (possibly even dynamically) to enable them to perform comparably well on all problems. Right now it's hard to tell for sure. I don't know. What I do know is that recently proposed linear RNNs are performing comparably to Transformers at similar model sizes, but have not yet been evaluated at state-of-the-art scales.
  - nyrikki 3y ago
    My hunch is it will be horses for courses.

by cs702 3y ago

nyrikki 3y ago

You don't typically get to the Sigma_2^P level unless are a sadist or forced. Attention works differently in RNNs, and it may be able to find different tractable forms, and may solve different problems, but increasing generalization is a reduction of compression in the general case. A many to one reduction to a recursively enumerable set gets you to finite time, a reduction to NP gets you to quadratic time. Obviously those are upper limits and specific instances or classes of instances may do better. P being inside NP is a good example. All ANNs are binary output, which helps with that. SNN or spikey neutral networks, which better model cortical neurons and have continuous output have problems with being un-computable without much complexity as an example. That can be viewed as the problems with computable numbers in place of the reals. But there are lots of interesting and practical things to solve. It is just those solutions will be more domain specific IMHO.

cs702 3y ago
Hmm... You're right: It's quite possible that the new crop of linear RNNs may not be able to solve the same problems as Transformers. It could also be that we will have to increase the depth of these linear RNNs (possibly even dynamically) to enable them to perform comparably well on all problems. Right now it's hard to tell for sure. I don't know. What I do know is that recently proposed linear RNNs are performing comparably to Transformers at similar model sizes, but have not yet been evaluated at state-of-the-art scales.
- nyrikki 3y ago
  My hunch is it will be horses for courses.