Differentiable Logic Cellular Automata

Late here, but a few comments: the main idea of the authors was to combine differential logic gates (an amazing invention I had not heard of) with cellular automata as they say in the paper, or more accurately I would say a grid topology of small neural networks (cells). The cells get and send information to their neighbors.

The idea would be you create some sort of outcome for fitness (say an image you want the cells to self organize into, or the rules of Conway’s game of life), set up the training data, and because it’s fully differentiable, Bob’s your uncle at the end.

Depending on what you think about computational complexity, this may or may not shock you.

But since they’ve been doing gradient descent on differentiable logic gates at the end of the day, when the training is done, they can just turn each cell into binary gates, think AND OR XOR, etc. You then have something that can be used for inference crazy fast. I presume it could also be laid out and sent to a fab, but that work is left for a later paper. :)

This architecture could do a LOTTT of things to be clear. But sort of as a warm up they use all the Conway life start and end rules to train cells to implement Conway. Shockingly this can be done in 5 gates(!). I note that they mention almost everywhere that they hand prune unused gates - I imagine this will eventually be automated.

They then go on to spec small 7k parameter or so neural networks that when laid out in cells can self organize into different black and white or color images, and can even do so on larger base grids than they were trained, and are resilient to noise being thrown at them. They then demonstrate that async networks (each cell updates randomly) can be trained, and are harder to train but more resilient to noise.

All this is quite a lot to take in, and spectacular in my opinion.

One thing they mention, a lot, is that a lot of hyperparameter tuning is required for “harder” problems. I can imagine like 50 lines of research out of this paper, but one of them would certainly be adding stability in to the training process. Arc-AGI is mentioned here, and is an awesome idea — could you get a “free lunch” with Arc? Or some of Arc? Different network topologies are yet another interesting question, hidden information, “backing layers” - e.g. why not give each cell 20 private cells that info goes out to and comes back in? Why not make some of those cells talk to some other cells? Why not send radio waves as signals across the custom topology and train an efficient novel analog radio? Why not give each cell access to a shared “super sized” 100k, 1mmk parameter “thinking node”? What would a good topology be for different tasks?

I’ll stop here. Amazing paper. Quite a number of PhD papers will be generated out of it, I expect.

I’d like to see Minecraft implemented though. Seems possible. Then we could have Bad Apple in Minecraft on raw circuits.

I'm not an expert on the actual biological mechanisms, but, it makes intuitive sense to me that both of those effects would occur in the situation you described from simple cells working on gradients: I was one of the authors on this paper during my undergrad[1] and the generalized idea of an eye being placed on a tail and having nerves routed successfully through the body via pheromone gradient is exactly the kind of error I watched occur a dozen times while collecting the population error statistics for this paper. Same thing with the kind of error of a face re-arranging itself. The "ants" in this paper have no communication except chemical gradients similar to the ones talked about with morphogen gradients. I'm not claiming it's a proof of it working that way, ofc, but, even simpler versions of the same mechanism can result in the same kind of behavior and error.

[1]: https://direct.mit.edu/isal/proceedings/alif2016/28/100/9940...

Lovely! Thanks for sharing. Would these patterns keep generating indefinitely?

It’s interesting to see how differentiable logic/binary circuits can be made cheap at inference time.

But what about the theoretical expressiveness of logic circuits vs baselines like MLPs? (And then of course compared to CNNs and other kernels.) Are logic circuits roughly equivalent in terms of memory and compute being used? For my use case, I don’t care about making inference cheaper (eg the benefit logical circuits brings). But I do care about the recursion in space and time (the benefit from CAs). Would your experiments work if you still had a CA, but used dumb MLPs?

Well, with all 16 logic gates available, they can express all Boolean circuits (you could get that even with NAND or NOR gates, of course, if you are working with arbitrary as opposed to fixed connectivity). And so you could have a 32 bit output vector which could be taken as a float (and you could create any circuit that computes any bitwise representation of a real).

As for efficiency, it would depend on the problem. If you're trying to learn XOR, a differentiable logic gate network can learn it with a single unit with 16 parameters (actually, 4, but the implementation here uses 16). If you're trying to learn a linear regression, a dumb MLP would very likely be more efficient.