3 ms·

What about recurrency?

• shawntan 4y ago
  Recurrency will help, see the empirical results in this paper: https://arxiv.org/abs/2207.02098 https://arxiv.org/abs/2207.02098. LSTMs can solve the PARITY problem, generalising to longer lengths of the problem without issue. The issue with re-introducing recurrency is that no one wants to bear the O(N) growth in computation time. I wonder if we are settling in for a local-optima of bounded-depth architecture for a while due to the obsession with rapid scaling.
  • yarg 4y ago
    You don't necessarily need to move to depth N, just because you went recurrent. You can probably design a modular network that can implement the logarithmic version.
    • shawntan 4y ago
      I guess I should say the recurrence growing as a function of the input size is something people don't seem to be willing to afford, not specifically the linear dependence. Not to mention parity here is a toy problem to highlight the issue, but there can be other problems that require recurrence linear or quadratic in the size of the input.
      • yarg 4y ago
        Sure, but a toy problem that's substitutable for many other functions. In this case you could substitute the XOR function for any other merge function. As far as the variable depth is concerned, utilisation is an issue that introduces additional complexity, but otherwise I don't see the problem. (No one's expecting fixed compute time for differently sized data elements.) You can get around that one by building a log(n) threaded pipeline for your log(n) depth network (something like this: https://imgur.com/a/xL4rhFu https://imgur.com/a/xL4rhFu).
  • _0ffh 4y ago
    The RWKV people seem to have adapted a recursive model so it can be trained in a special parallel mode like attention. https://github.com/BlinkDL/RWKV-LM https://github.com/BlinkDL/RWKV-LM
    • shawntan 4y ago
      Yeah I really like this project, and I've been meaning to dive into it.
• mturmon 4y ago
  Reasonable point - in the case of parity, one bit of recurrent state avoids the combinatorial issues mentioned in OP (as OP more or less says in writing the finite state automaton). It's interesting to think about parity in relation to the image classification tasks that sparked the ANN renaissance. In image classification, the class does not strongly depend on a single feature - you don't change from cat to dog by altering one pixel, and then back to cat by altering a different pixel. But parity does depend strongly on each bit in the input. I think it's important to keep this special aspect of the parity problem in mind when thinking about good architectures for various applications.
  • yarg 4y ago
    As I noted elsewhere, the structure's not specific to parity/XOR but works on n-ary merge operations in general. It will impact the breadth and depth required for the module; the {2, 2, 1} module structure required for XOR is not generally useful - but it's a substitutable component. A bigger problem is keeping your processor fed with the decaying layer size (you'll want to target a fixed wave size if you're running on a GPU, mostly empty waves are a bad thing), but you can get around that reasonably easily (at least for base-2).