Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Transformer neural net learns to run Conway's Game of Life just from examples

sidsite.com

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Transformer neural net learns to run Conway's Game of Life just from examples

#31

Post by Legend2440 »

evrimoztamur wrote: post #9

I would like to point out a much more exciting modelling process, whereby neural networks extract the underlying boolean logic from simulation outputs: https://google-research.github.io/self-organising-systems/di... I firmly believe that differentiable logic CA is the winner, in particular because it extracts the logic directly, and thus leads to generalize-able programs as opposed to staying stuck in matrix multipli…

If you look at the learned gates, it does not directly extract the underlying rules of Conway's game of life. It has many more gates than are necessary and they have the same complex, uninterpretable structure you see in a neural network.

The training method they're using is the same as used for quantized neural networks. Your 'neurons' being logic gates doesn't mean you're doing logic, it's still statistics.

Re: Transformer neural net learns to run Conway's Game of Life just from examples

#32

Post by constantcrying »

gwern wrote: post #28
montebicyclelo wrote: post #6

Earlier quoted context omitted.

The diagonal-looking attention matrix shown in the post is mathematically equivalent to 3 by 3 convolution . The model learns how to do that via its attention mechanism - it's not obvious that it would be able to do that via attention. (This can be shown by comparing that attention matrix to a "manually computed Neighbour Attention matrix", which is known to be equivalent to 3 by 3 conv.)

It would be more convincing if they did an exhaustive enumeration and verified that for every possible 3x3 Life the learned NN was correct. How do I know looking at a speckled screenshot that it is exactly correct and there's not a little floating point error somewhere or something like that which results in 1 edge-case being slightly off? If the only testing is '100 Life games for 100 steps', that isn't water-tight.…

I think it would have also been very interesting to manually construct a NN, which represented the rules exactly. Maybe there is some nice mathematical way to describe them or some constraints need to be fulfilled.

Then afterwards you can check the neutral network against the exact algorithms.

Re: Transformer neural net learns to run Conway's Game of Life just from examples

#33

Post by montebicyclelo »

wrs wrote: post #29

I was hoping for an explanation of, or some insight from, the loss curve. Training makes very little progress for a long time, then suddenly converges. In my (brief) experience with NN training, I typically see more rapid progress at the beginning, then a plateau of diminishing returns, not an S-curve like this.

Hmm, just my intuition: training this model was very sensitive to the initial seed and training hyperparameters. It struggles to actually get to the 3x3 conv solution; but once it gets close to that things move much more quickly. This can kind of be seen in the animation of the attention matrix over time, which starts off random / spread out, but then once it starts to get more parts of the attention matrix in place it moves quicker. (Assuming all the experimentation wasn't in some bad part of the hyperparameter space.)

Also, it may just be the nature of the task. Some tasks you might have more to learn, all the time, with each training sample potentially giving information that's different from all the others. But with this, once it gets close to the solution of Life, it's quick.

Re: Transformer neural net learns to run Conway's Game of Life just from examples

#34

Post by awesomeMilou »

evrimoztamur wrote: post #9

I would like to point out a much more exciting modelling process, whereby neural networks extract the underlying boolean logic from simulation outputs: https://google-research.github.io/self-organising-systems/di... I firmly believe that differentiable logic CA is the winner, in particular because it extracts the logic directly, and thus leads to generalize-able programs as opposed to staying stuck in matrix multipli…

To ruin this for everyone: The underlying optimization that enables these to run as computationally efficient as they do, is patented:

https://patents.google.com/patent/WO2023143707A1/en?inventor...

Re: Transformer neural net learns to run Conway's Game of Life just from examples

#35

Post by montebicyclelo »

constantcrying wrote: post #25
montebicyclelo wrote: post #24

Earlier quoted context omitted.

> the paper does not investigate whether the resulting NN actually performs the game of life algorithm How could it not be computing the game of life algorithm? Given that it gets 100% accuracy over multiple steps on a bunch random game boards it's never seen before. And then based on the structure of the net, and by examining the attention layers and finding that it's doing 3 by 3 average pooling, we can see that th…

Do you not understand the difference between empirical evidence and mathematical proof? Surely every person talking about NN research should be aware of that distinction. > How could it not be computing the game of life algorithm? Given that it gets 100% accuracy over multiple steps on a bunch random game boards it's never seen before. This is such an insane statement.

> This is such an insane statement.

In what way? Maybe you mean something different when you say computing the game of Life algorithm.

Re: Transformer neural net learns to run Conway's Game of Life just from examples

#36

Post by montebicyclelo »

gwern wrote: post #28
montebicyclelo wrote: post #6

Earlier quoted context omitted.

The diagonal-looking attention matrix shown in the post is mathematically equivalent to 3 by 3 convolution . The model learns how to do that via its attention mechanism - it's not obvious that it would be able to do that via attention. (This can be shown by comparing that attention matrix to a "manually computed Neighbour Attention matrix", which is known to be equivalent to 3 by 3 conv.)

It would be more convincing if they did an exhaustive enumeration and verified that for every possible 3x3 Life the learned NN was correct. How do I know looking at a speckled screenshot that it is exactly correct and there's not a little floating point error somewhere or something like that which results in 1 edge-case being slightly off? If the only testing is '100 Life games for 100 steps', that isn't water-tight.…

Edit: increased the validation to 10,000 life grids for 100 steps, (taking 16 minutes to check), which is hopefully somewhat more convincing. That's 1,000,000 life steps computed without errors in total. Plus 32,000 steps computed without error during training.

When the attention grid is manually computed (to be equivalent to 3 by 3 conv), the model can be trained to be 100% perfect, verified by checking all 3 by 3 grid states. (And this manually computed attention matrix means that once the tokens reach the classifier layer, each token contains only the information of the relevant 3 by 3 grid, and the whole thing is deterministic as you say.)

However, when the model is computing the attention grid itself, just checking all 3 by 3 sub-grid states crop up is not enough, because the position of the sub-grids can impact the attention matrix, and also the state of other cells can impact the attention matrix. So as shown in the post, it does approximate 3 by 3 conv, but if it doesn't get the approximation quite right, there could be errors. But I would say that it's still computing the Game of Life algorithm in an interpretable way, it's just that maybe it has struggled to create a perfect 3 by 3 convolution via attention in that particular case. (To exhaustively check this, would require checking all 2 * (16x16) grids.)

Post reply on HN