The objective function here defines a Markov random field (MRF) with boolean random variables and certain local statistics of nearest neighbours, either uniform if the target is a white image, or varying with location to produce an image. MRFs define Gibbs probability distributions, which you can sample from (which will already produce a good image here) or perform gradient ascent on to reach a local maxima. The negative log-likelihood of the MRF distribution is equal to the loss function of the original optimisation problem, so the maximum likelihood estimate (MLE) (there will often be multiple due to symmetry) of the MRF is the optimal solution(s) to the original problem. (But in general the MLE can look completely different to a sample.)
The statistics are 9th-order (of 3x3 blocks of pixels) but of a simple form which are hardly more expressive than 2nd-order nearest neighbour statistics (in terms of the different textures that they can reproduce) which are well known. In the approximate case where you only care about the average value of each pixel I think it would collapse to 2nd-order. Texture synthesis with MRFs with local statistics is discretized (in space) Turing reaction-diffusion. I did my PhD on this topic.
Probably the most influential early paper on this kind of simple texture model, where you will see similar patterns, is:
Cross & Jain, 1983, PAMI, Markov Random Field Texture Models
I should mention Restricted Boltzmann Machines (RBMs, which Hinton got the Nobel for): it's really natural to use hidden variables in formulating a problem like this: one lattice of binary variables for GoL time step 0, a second for timestep 1, and optionally a third of continuous variables (or eg 256-level greyscale) for the unquantised target image. (Keep stacking RBMs for more timesteps.) Then you have a bi/tri-partite undirected graphical model. RBMs can be generalised in many ways and one of them is to replace the 2nd-order (pairwise) interactions between variables with higher-order interactions like these 9th order ones -- their most essential property is being bipartite so you can infer each variable on a layer independently given the other (or neighbouring) layers. The article didn't say how the target (timestep 1) configuration was picked, but you can simultaneously optimise for the timestep 0->1 error and the timestep 1->image distance, which could give a better looking result.
And when you have a (two-layer) RBM you can integrate out the hidden variables and get a MRF without them (as I first described), or vice-versa. Which is more useful depends.
Or if you're more interested in textures, RBMs are used for texture and image modelling (e.g. [1]), and higher order statistics are far more interesting. In virtually all papers they take the form of the responses of linear filters (like that 3x3 filter in OP, often wavelets for natural images). But you can use completely different statistics. I found that long-range local binary patterns (LBPs), used for texture recognition, are good for texture generation too.
I've switched away from textures, but energy-based models are harder to escape. A surprising intersection of old and new topics at [2].
[1] R Liao, S Kornblith, M Ren, D Fleet & G Hinton, 2022, "Gaussian-Bernoulli RBMs Without Tears" https://arxiv.org/pdf/2210.10318
Inference/learning of densely connected graphical models is a huge difficulty. It's not a big problem for MRFs with nearest neighbours only, but it is for anything interesting (e.g. long-range connections), so I felt quite jealous of neural networks with simple feed-forward computation. Using feed-forward computations in one direction (likely observed->latent) of hybrid models is really appealing to me. Instead of having to use approximations (e.g. Contrastive Divergence (CD) instead of actually sampling from an RBM) which are easy to work with, why not just build your model around the easy thing in the first place so it's not an approximation, and use approximation in the other direction only. I'm not very familiar with Helmholtz machines but they seem to do that, but (unsurpisingly) seem just as difficult? I'm not sure. But I don't like Helmholtz machines and VAEs with Gaussian priors over latents, that seems like making zero use of the power of graphical models. I want the best of both!
I'm so glad to see others working on this. I've attempted it too, but not with any measure of success.
Trying to trade space for time, I used a model that gives every cell a set of all 512 of the possible 3x3 neighborhoods that could have caused that cell's present state ("alibis"). It then goes to each cell, comparing its alibis to those of neighboring cells and eliminating mutually impossible ones from either set. This step has to be repeated until no more alibis are shed in a pass.
When it finally stabilizes, the model is a solution kernel that can then field further manual guesses against it. If a cell's alibis all agree it was dead in the "before", there's no need to guess, but if they're not unanimous, what if we hazard a guess one way or the other for a bit? How does that ripple through the rest of the board? If any of the cells ran completely out of alibis given a certain guess, that guess was clearly not a proper solution, and it's time to back out and try a different one. If there's no solution at all, that's a Garden of Eden.
Ultimately I wanted to generate not just one solution, but all the solutions for a given board. I got stumped because I wasn't convinced I wasn't still working in 2**(n*m) time or worse trying guesses against the kernel.
It's a really fascinating problem, so much so that I even made a pico8 game about it years ago! Even the 6x6 grids are really tough!
It tries to "evolve" the target image (right) by making random changes to the origin (left) -- output after 1 step is in center.
It's eventually supposed to be a genetic algorithm, but for now it just goes through it pixel by pixel, and if the pixel doesn't match the target, it inverts one of its neighbors. If that's beneficial (checking loss in a 5x5 rect centered on the test pixel), we keep the change. I get loss down to about 25% then it plateaus.
Feel free to fiddle, fork, etc! (I stayed up pretty late so the code is bad! Suggestions welcome!)
Another strat I thought about is to precompute all possible outputs for all possible inputs. This is feasible for small tiles (e.g. 5x5 grid has ~35 million permutations), maybe a sliding window could be used. I'm stuck on how to deal with tile overlap, and the fact that many outputs have more than one input -- you'd want to check all possible input tiles against all possible neighboring input tiles?
Maybe! That's a good idea! I guess I'd get natural dithering as the result of running a loss function on small windows against a grayscale image. (Per-pixel loss would be very high though, I guess you'd want to take the average brightness for some chunk?) I'm not sure how dithering is supposed to work though, maybe there's some improvements there over just taking the average brightness?
I saw an interesting video on the same topic last week. By Brian Haidet (AlphaPhoenix) on reversing the GOL - it turns out that NP hard is hard! https://www.youtube.com/watch?v=g8pjrVbdafY
Lovely video, and it was enormously personally satisfying to me while he was describing his evolutionary algorithm I just sat thinking "why not just use a SAT solver, this seems like child's play for z3?" and then hearing him go "then I asked Reddit and someone suggested using a SAT solver". Hell yeah, good job, brain! I mean, not as good a job as Brian who actually implemented it and made the video and everything, but still!
> First of all, while I said “Predecessorifier” in the talk, “Ataviser” seems to be the accepted word, coming from “Atavism”, which the online Merriam-Webster dictionary defines as “recurrence of or reversion to a past style, manner, outlook, approach, or activity”.
I disagree, getting a scramble is trivial for a Rubik's cube (because any scramble will do, and unlike with Conway's Game of Life, here going in reverse is simple). If there was a particular scramble and you want to recover it, you just can't do it without some additional information.
Really cool to see. Was curious about the author's other work and was very annoyed that the blog does not link to the author's other posts, either with a "next/previous" link, an archive, or a homepage where a list of posts can be viewed. The only way to see other posts is to subscribe to the RSS. I can't imagine there being a good reason for having such a bad UX.
Feels to me like there is no need for backpropagation. I think you can just iteratively grab a random pixel and flip it of that would bring you closer to the target after one step.
It would probably work even better if you tweak the loss function with some kind of averaging/blurring filter.
This is just the brute force solution. I'm pretty sure that's no more efficient than guessing all pixels at once and trying to check of that worked or not.
It's the trivial solution. It's significantly more efficient than using backprop. It's much simpler and leads to practically the same result.
This makes me wonder why you would use backprop to do this. It feels like a waste of time, and I'm not sure why this post generates so much attention on HN.
Guessing all pixels at once and then checking is massively worse, since it's basically the first step of GP's proposed approach -- which then iteratively changes things in a way that never makes it worse.
It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future. Everything will have a 50/50 probability of being "correct" based on any given scenario. What you're saying is somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip, or even 20 of the last flips in a row. I'm actually not a great statistician myself, but I think I'm right on this one. :)
>It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future.
It's true that a "good" decision now might turn out to be "bad" later, but whether it's effective in improving a solution depends on the fraction of times that happens, which is almost certainly not 50%. Hill-climbing methods like this are used everywhere in optimisation when you want a decent solution quickly and don't require optimality.
>somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip
I'm no statistician either, but this is not analogous at all.
What you described wasn't Hill Climbing at all tho. You have to be able to take the derivative of a function to do that. The derivative is what tells you how to "go uphill" (or down)
Well you're right there's infinite variations of algos that all can legitimately be called hill-climb. It's about as generic as the term "curve fitting".
I just mean with the known complexity and nature of Game of Life, trying to guess things based on an objective function, when going back in time, seems no more efficient than trying to guess coin flips, based on prior flips. There's probably some Logic Theorem (sorry I don't know it) that describes why objective functions cannot be used to help solve the backwards Game of Life problem.
It's a complexity problem like which butterfly "caused" a tornado, or which initial clumping of rocks "caused" a black hole, because there are infinite numbers of solutions. Like how many initial GoL boards are there that result in a particular final state? I say for any final state there will be infinite possible starting states that can lead up to it.
Simulated annealing (basically MCMC sampling with a temperature schedule) is how you optimise or sample the equivalent MRF, which I discussed in my other comment. You can hope to escape local minima using annealing, and lower the temperature to zero to fall into a local minima, minimising the noise added by annealing. In practice if you're trying to produce something that looks like a target image as in the article I'm pretty sure the results will be indistinguishable. If you actually cared about how many individual pixels are correct, yes, annealing is better than gradient descent. That's why stochastic gradient descent is used in ML.
I found this post absolutely fascinating! I got thinking, is there a Turing-complete simple abstraction that is differentiable, without approximation? I have heard about Neural Turing machines (but only as a layman), but from a quick peek they are similarly hard to reason about as other NNs?
The objective function here defines a Markov random field (MRF) with boolean random variables and certain local statistics of nearest neighbours, either uniform if the target is a white image, or varying with location to produce an image. MRFs define Gibbs probability distributions, which you can sample from (which will already produce a good image here) or perform gradient ascent on to reach a local maxima. The negative log-likelihood of the MRF distribution is equal to the loss function of the original optimisation problem, so the maximum likelihood estimate (MLE) (there will often be multiple due to symmetry) of the MRF is the optimal solution(s) to the original problem. (But in general the MLE can look completely different to a sample.)
The statistics are 9th-order (of 3x3 blocks of pixels) but of a simple form which are hardly more expressive than 2nd-order nearest neighbour statistics (in terms of the different textures that they can reproduce) which are well known. In the approximate case where you only care about the average value of each pixel I think it would collapse to 2nd-order. Texture synthesis with MRFs with local statistics is discretized (in space) Turing reaction-diffusion. I did my PhD on this topic.
Probably the most influential early paper on this kind of simple texture model, where you will see similar patterns, is:
Cross & Jain, 1983, PAMI, Markov Random Field Texture Models
Anything you’ve found to be additionally interesting or curious along this path or different but somewhat related?
Are you still working on this topic or other things now?
I should mention Restricted Boltzmann Machines (RBMs, which Hinton got the Nobel for): it's really natural to use hidden variables in formulating a problem like this: one lattice of binary variables for GoL time step 0, a second for timestep 1, and optionally a third of continuous variables (or eg 256-level greyscale) for the unquantised target image. (Keep stacking RBMs for more timesteps.) Then you have a bi/tri-partite undirected graphical model. RBMs can be generalised in many ways and one of them is to replace the 2nd-order (pairwise) interactions between variables with higher-order interactions like these 9th order ones -- their most essential property is being bipartite so you can infer each variable on a layer independently given the other (or neighbouring) layers. The article didn't say how the target (timestep 1) configuration was picked, but you can simultaneously optimise for the timestep 0->1 error and the timestep 1->image distance, which could give a better looking result.
And when you have a (two-layer) RBM you can integrate out the hidden variables and get a MRF without them (as I first described), or vice-versa. Which is more useful depends.
Or if you're more interested in textures, RBMs are used for texture and image modelling (e.g. [1]), and higher order statistics are far more interesting. In virtually all papers they take the form of the responses of linear filters (like that 3x3 filter in OP, often wavelets for natural images). But you can use completely different statistics. I found that long-range local binary patterns (LBPs), used for texture recognition, are good for texture generation too.
I've switched away from textures, but energy-based models are harder to escape. A surprising intersection of old and new topics at [2].
[1] R Liao, S Kornblith, M Ren, D Fleet & G Hinton, 2022, "Gaussian-Bernoulli RBMs Without Tears" https://arxiv.org/pdf/2210.10318
[2] C Zhang, B Jia, Y Zhu & S-C Zhu, 2024, "Human-level few-shot concept induction through minimax entropy learning" https://www.science.org/doi/10.1126/sciadv.adg2488
I've been really interesting in simulated annealing abstractions for ways to handle various parameters over time. Thanks for sharing!
Any thoughts on Helmholtz machines or wild more fringe models of computation but might be interesting to explore if you had more time?
Inference/learning of densely connected graphical models is a huge difficulty. It's not a big problem for MRFs with nearest neighbours only, but it is for anything interesting (e.g. long-range connections), so I felt quite jealous of neural networks with simple feed-forward computation. Using feed-forward computations in one direction (likely observed->latent) of hybrid models is really appealing to me. Instead of having to use approximations (e.g. Contrastive Divergence (CD) instead of actually sampling from an RBM) which are easy to work with, why not just build your model around the easy thing in the first place so it's not an approximation, and use approximation in the other direction only. I'm not very familiar with Helmholtz machines but they seem to do that, but (unsurpisingly) seem just as difficult? I'm not sure. But I don't like Helmholtz machines and VAEs with Gaussian priors over latents, that seems like making zero use of the power of graphical models. I want the best of both!
I'm so glad to see others working on this. I've attempted it too, but not with any measure of success.
Trying to trade space for time, I used a model that gives every cell a set of all 512 of the possible 3x3 neighborhoods that could have caused that cell's present state ("alibis"). It then goes to each cell, comparing its alibis to those of neighboring cells and eliminating mutually impossible ones from either set. This step has to be repeated until no more alibis are shed in a pass.
When it finally stabilizes, the model is a solution kernel that can then field further manual guesses against it. If a cell's alibis all agree it was dead in the "before", there's no need to guess, but if they're not unanimous, what if we hazard a guess one way or the other for a bit? How does that ripple through the rest of the board? If any of the cells ran completely out of alibis given a certain guess, that guess was clearly not a proper solution, and it's time to back out and try a different one. If there's no solution at all, that's a Garden of Eden.
Ultimately I wanted to generate not just one solution, but all the solutions for a given board. I got stumped because I wasn't convinced I wasn't still working in 2**(n*m) time or worse trying guesses against the kernel.
It's a really fascinating problem, so much so that I even made a pico8 game about it years ago! Even the 6x6 grids are really tough!
You may like the discrete algorithm from https://a.tulv.in/finding-mona-lisa-in-the-game-of-life.html. HN discussed it at the time in https://news.ycombinator.com/item?id=26384403, which was where I found this story's link.
What do you think might be the path / solution but needs playful experiments ? Ideas to seed others?
Inspired by this, I stayed up all night building this!
https://jsbin.com/josuxarufu/1/edit?js,console,output
It tries to "evolve" the target image (right) by making random changes to the origin (left) -- output after 1 step is in center.
It's eventually supposed to be a genetic algorithm, but for now it just goes through it pixel by pixel, and if the pixel doesn't match the target, it inverts one of its neighbors. If that's beneficial (checking loss in a 5x5 rect centered on the test pixel), we keep the change. I get loss down to about 25% then it plateaus.
Feel free to fiddle, fork, etc! (I stayed up pretty late so the code is bad! Suggestions welcome!)
Another strat I thought about is to precompute all possible outputs for all possible inputs. This is feasible for small tiles (e.g. 5x5 grid has ~35 million permutations), maybe a sliding window could be used. I'm stuck on how to deal with tile overlap, and the fact that many outputs have more than one input -- you'd want to check all possible input tiles against all possible neighboring input tiles?
Wouldn't it be better to have the target image as grayscale or black/white instead of dithered?
Maybe! That's a good idea! I guess I'd get natural dithering as the result of running a loss function on small windows against a grayscale image. (Per-pixel loss would be very high though, I guess you'd want to take the average brightness for some chunk?) I'm not sure how dithering is supposed to work though, maybe there's some improvements there over just taking the average brightness?
I saw an interesting video on the same topic last week. By Brian Haidet (AlphaPhoenix) on reversing the GOL - it turns out that NP hard is hard! https://www.youtube.com/watch?v=g8pjrVbdafY
Lovely video, and it was enormously personally satisfying to me while he was describing his evolutionary algorithm I just sat thinking "why not just use a SAT solver, this seems like child's play for z3?" and then hearing him go "then I asked Reddit and someone suggested using a SAT solver". Hell yeah, good job, brain! I mean, not as good a job as Brian who actually implemented it and made the video and everything, but still!
Few days ago I posted this: https://news.ycombinator.com/item?id=41743887
Atavising was new to me. From https://nbickford.wordpress.com/2012/04/15/reversing-the-gam... :
> First of all, while I said “Predecessorifier” in the talk, “Ataviser” seems to be the accepted word, coming from “Atavism”, which the online Merriam-Webster dictionary defines as “recurrence of or reversion to a past style, manner, outlook, approach, or activity”.
I disagree, getting a scramble is trivial for a Rubik's cube (because any scramble will do, and unlike with Conway's Game of Life, here going in reverse is simple). If there was a particular scramble and you want to recover it, you just can't do it without some additional information.
It's a good analogy for someone who doesn't know how to solve a Rubik's cube.
breaking analogies is the only reason people comment at this point
ive caught myself doing this
There's a continuous GoL called LENIA.
https://www.youtube.com/watch?v=PlzV4aJ7iMI (in French)
https://news.ycombinator.com/item?id=34108724
I made a related crossword puzzle. You can find it here if you want to give it a try! https://jacobw.xyz/projects/crossword/
It's always fun when people use autodiff in packages like PyTorch for completely unrelated usecases :)
Really cool to see. Was curious about the author's other work and was very annoyed that the blog does not link to the author's other posts, either with a "next/previous" link, an archive, or a homepage where a list of posts can be viewed. The only way to see other posts is to subscribe to the RSS. I can't imagine there being a good reason for having such a bad UX.
The article asks the following:
> I can’t help but wonder if there’s a reaction-diffusion-model-esque effect at work here as well
There are continuous approximations of the game of life that show this, for example this implantation:
https://smooth-life.netlify.app
Related: https://a.tulv.in/finding-mona-lisa-in-the-game-of-life.html
Albeit, using a different stochastic technique
Feels to me like there is no need for backpropagation. I think you can just iteratively grab a random pixel and flip it of that would bring you closer to the target after one step.
It would probably work even better if you tweak the loss function with some kind of averaging/blurring filter.
This is just the brute force solution. I'm pretty sure that's no more efficient than guessing all pixels at once and trying to check of that worked or not.
> This is just the brute force solution.
It's the trivial solution. It's significantly more efficient than using backprop. It's much simpler and leads to practically the same result.
This makes me wonder why you would use backprop to do this. It feels like a waste of time, and I'm not sure why this post generates so much attention on HN.
Also see https://nullprogram.com/blog/2020/11/24/
> I'm pretty sure that's no more efficient than guessing all pixels at once and trying to check of that worked or not.
It's iterative so you don't have to run for a very long time, and it will keep improving the loss function for longer.
Guessing all pixels at once and then checking is massively worse, since it's basically the first step of GP's proposed approach -- which then iteratively changes things in a way that never makes it worse.
It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future. Everything will have a 50/50 probability of being "correct" based on any given scenario. What you're saying is somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip, or even 20 of the last flips in a row. I'm actually not a great statistician myself, but I think I'm right on this one. :)
>It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future.
It's true that a "good" decision now might turn out to be "bad" later, but whether it's effective in improving a solution depends on the fraction of times that happens, which is almost certainly not 50%. Hill-climbing methods like this are used everywhere in optimisation when you want a decent solution quickly and don't require optimality.
>somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip
I'm no statistician either, but this is not analogous at all.
What you described wasn't Hill Climbing at all tho. You have to be able to take the derivative of a function to do that. The derivative is what tells you how to "go uphill" (or down)
You don't need a derivative to hill-climb. You only need an objective function, and a way to generate "moves" (similar, new solutions).
Well you're right there's infinite variations of algos that all can legitimately be called hill-climb. It's about as generic as the term "curve fitting".
I just mean with the known complexity and nature of Game of Life, trying to guess things based on an objective function, when going back in time, seems no more efficient than trying to guess coin flips, based on prior flips. There's probably some Logic Theorem (sorry I don't know it) that describes why objective functions cannot be used to help solve the backwards Game of Life problem.
It's a complexity problem like which butterfly "caused" a tornado, or which initial clumping of rocks "caused" a black hole, because there are infinite numbers of solutions. Like how many initial GoL boards are there that result in a particular final state? I say for any final state there will be infinite possible starting states that can lead up to it.
I feel like just doing simulated annealing on the starting grid would work better and be faster to implement?
(Not saying the goal was working well and being fast to implement.)
Simulated annealing (basically MCMC sampling with a temperature schedule) is how you optimise or sample the equivalent MRF, which I discussed in my other comment. You can hope to escape local minima using annealing, and lower the temperature to zero to fall into a local minima, minimising the noise added by annealing. In practice if you're trying to produce something that looks like a target image as in the article I'm pretty sure the results will be indistinguishable. If you actually cared about how many individual pixels are correct, yes, annealing is better than gradient descent. That's why stochastic gradient descent is used in ML.
I found this post absolutely fascinating! I got thinking, is there a Turing-complete simple abstraction that is differentiable, without approximation? I have heard about Neural Turing machines (but only as a layman), but from a quick peek they are similarly hard to reason about as other NNs?
Not exactly an answer to your question, but in the ballpark and hopefully you might find interesting https://arxiv.org/pdf/2404.17625
In the section on "Automatic differentiation" he considers the question of differentiable computation graphs.
Related: https://news.ycombinator.com/item?id=41817808
The emerging pattern looks a little like Blue Noise!
Interesting. I can't zoom on mobile which is frustrating.
https://github.com/vtempest/Automated-Automata One idea is to have the gradient patterns emergent from simple rules calculating prior numbers with no need for hand of God intrvention.
Seeing alot of parallels to the article by Stephen Wolfram posted a few days back on the fundamental nature of time .
which?
https://news.ycombinator.com/item?id=41782534
Very cool!
[dead]
[dead]