Hacker News Reader

Over the past ten years, neural networks have been extremely successful on a range of problems that prior seemed impossibly difficult. One downside to that though is that people have forgotten the No Free Lunch theorem, and now see neural networks as a silver bullet to use everywhere and always.

NFL shows that no learning method works across the space of all possible problems. Every method bakes in a set of empirical priors. To the extent that the problem conforms to those priors, the method does well. But the contrast is that you must "pay the cost" by underperforming in other problems which contradict those priors.

To be fair often times the areas that you underperform in are so pathological that they're hardly ever encountered in the real world. Many regression type problems rely on the empirical prior that arbitrarily close real numbers are more similar than random. For example you expect the answer at 2.84394 to be closer 2.84395 than 150,000. In actual physical reality, this prior tends to hold up so well that we're barely even aware when we rely on it. But when it does break (like trying to treat Hamming distances as real distances), it breaks spectacularly. There's no free lunch, but sometimes we can pay the bill with cheap currency.

The point of all this, is that you shouldn't be picking learning methods without understanding the empirical priors embedded in your data. Just because a technique works really well on a hard problem, doesn't mean it works really well on all problems. Especially if they're two very different types of problems.

The no-free-lunch theorem is interesting in theory but not terribly relevant in practice. A prior that something can be efficiently approximated will learn anything you could desire to learn, and even stronger assumptions will work for most real world problems.

NFR is extremely important when you’re actually trying to solve specific problems. If the ideal solution involves some output randomness then neutral networks on their own are useless. Poker for example is a terrible fit.

It applies to humans too. We are terrible at generating truly random numbers, which are required for mixed game strategies.

BTW, NFL theorem proves that it itself is never terribly important. Learning algorithm, which uses NFL theorem for making decisions, are in the same position as any other learning algorithm.

Sort of, the universe isn’t completely random so we have metadata we can apply to relevant problems. It’s the same reason that in theory compression algorithms fail, but in practice that’s not an issue.

Though for arbitrary theoretical problems it’s important.

https://peekaboo-vision.blogspot.com/2019/07/dont-cite-no-fr...

I agree. I am utterly unsurprised that gradient descent was unable to optimize a “minimal” network to a complete solution of a binary state problem with a Boolean rule set.

I’d have been shocked if it went any other way.

I’m also reminded of an ‘06 paper by Kreinovich and Shpak, Aggregability is NP-Hard.

http://www.cs.utep.edu/vladik/2006/tr06-29.pdf

Neural networks aren’t magic, and optimization isn’t finding the one needle in a haystack with a blindfold on. This is an intuitive result for anyone mildly conversant in the space.

I don’t mind that they went out and did it, though.

Maybe I'm just not conversant enough in the field (I do ML "ops", not ML) but I'm surprised there aren't clever iterative ways of "reducing" the size of a model, for example, rank order the average activation of each parameter in a reducible group across the dataset, find the weakest, set it to zero, identify new misses, retrain with enrichment in the dead samples, reduce the hyperparameter by one.

There are: https://medium.com/syncedreview/mit-google-propose-automl-fo...

I went to a more recent talk by Google and results they handpicked to show were impressive.

There are, it's called network pruning. You generally can reduce network size 90-95% without loss of accuracy with these methods.

You "just" have to train a huge network first, which is the downside.

From a very high level perspective, I think what is somewhat surprising here is the fact that given that the Game of Life rules are quite simple, it should follow that a powerful generalization mechanism (which is what deep neural networks are often described to be) should be able to easily derive them.

The rules would need to be applied recursively for elegant generalization, I think? Do these networks have connections going backwards?

It depends what you mean by "easy" here, but if you define that as "throw a big enough network at it, and it'll figure it out on its own in training", the research cited shows that is the case.

The power you describe comes in part from network size (which is why NNs became more useful as we could size up as computing got more powerful/cheaper/more efficient). Small network means less powerful ability. The research showed smaller networks didn't work, but larger ones did. Seems like you'd agree?

The research showed that small networks did work, but they took manual intervention during training.

I think the whole point was that a small network is capable of solving this problem, but training from scratch without intervention only rarely produced a viable solution.

From the article

- But in most cases the trained neural network did not find the optimal solution, and the performance of the network decreased even further as the number of steps increased. The result of training the neural network was largely affected by the chosen set training examples as well as the initial parameters.

So a solution was clearly possible even in the smaller networks when trained from scratch, it just wasn't likely.

So I agree with your first point - The bigger networks did indeed "figure it out". But I don't agree at all with your second - The smaller networks weren't lacking the power to solve the problem, they were just unlikely to reach the right solution with the available training data.

I see it as a practical yet fundamental result. Some people might dismiss it at first because it is around a "Mathematical Recreations" topic, but the problem of "learn the rules from the data" is a common one.

I've worked with autoencoder, convolutional and LSTM methods with text that appear to solve problems that they shouldn't be able to solve from

https://en.wikipedia.org/wiki/Variety_(cybernetics)#Law_of_r...

that is, they don't contain a correct structural representation of the problem space or they violate the laws of computer science.

For instance, a neural network might do a finite number of calculations to guess at a good next move and play a mean game of chess. This is an O(1) algorithm that can't possibly do things that would take an O(log N), O(N), O(N^2), ... algorithm to do it. (e.g. explore the game tree exhaustively and prove this is a winning move.) Put it in the context of a variable-runtime algorithm such as MCTS which can iterate over the network multiple times and it will crush a grandmaster.

Thus you run into the space of the halting problem, something that pretends to sort a list in O(N) time and gets away with it, ...

People in the field work with poorly defined problems, pick metrics ungrounded in practice, etc. In particular there is no requirement that the results of a neural network be 'correct' they just have to be better than some alternative.

If you have one of these things either working or almost-working you might get curious and try to set up some little experiment based on an intuition at the microscale (e.g. it's obvious how to hand-build the network, tasks the network couldn't possibly learn) and do experiments like this one where you can synthesize unlimited amounts of data...

... frequently you get lost at sea, suspect that the emperor has no clothes, wonder if you got the math wrong somewhere, might find your system performs worse the more training data you throw at it...

... thus these results don't close in a clear story, they don't get published.

The issue is that the network has to learn from an n-step transition, which is hard to do when minimally parameterized.

I believe GoL is easily solvable by ML if the task was to find parameters of the update rules with the constraint that the rules are simple.

For example, if we were presented a highly sophisticated repetitive pattern and were tasked to figure the underlying tesselation rules that generate it, we would enumerate rulesets that we know already and then try to find parameters for them with the assumption that those parameters are simple.

Again, my point is that to solve GoL, the ML model needs to be given two things: 1) a few rulesets to choose from; 2) an upper limit on complexity of ruleset parameters.

> To me, the surprising finding of the lottery ticket hypothesis was not only that you can show that only a tiny part of the final network is necessary for the final solution, but that if you would have started with only that tiny part, you would retrieve almost the complete performance.

As a developer who's dabbled in a few machine learning fields, I've always wondered if there was a way to strip all unused/unlikely paths out of a network to reduce size and increase performance. I've struggled with finding solid information on this (and just the whole ML tooling ecosystem in general). From your experience, are there any tools out there that can aid in this kind of analysis and path stripping?

> wondered if there was a way to strip all unused/unlikely paths out of a network to reduce size and increase performance.

Sure there is, it is called "pruning". You can easily find works on this with your favorite search engine. "Distillation" is another interesting technique to make models smaller.

These techniques are applied after training, to reduce the size of a big network. I don't know any method that can be applied _before_ training, just by inspecting the network.

You may be looking for "Optimal Brain Damage": http://yann.lecun.com/exdb/publis/pdf/lecun-90b.pdf

> As someone who knows quite something on this topic, I do not really see what is the surprise here.

I'm not sure it was necessarily meant to be be surprising, especially to people experienced with neural networks. (In fact, it looks to me like the article is aimed at people who are curious but do not have a deep understanding.)

Do you think GameGAN[0] will be able to pick the rules of game of life?

[0]: https://blogs.nvidia.com/blog/2020/05/22/gamegan-research-pa...

So I only dabble, but what was surprising for me with GoL on a small grid was how the performance wasn't great even if I'd shown the network almost every possible state during training (omitting a test set).

Nets do such amazing things with open ended recognition problems ("what is in this picture") that you sort of just expect them to trivially learn closed form solutions perfectly. I know this is a fallacy, but that is where the surprise came for me.

I don't know much about it, but why is it surprising that if you initially put in the answer, you get a good answer out?

Yeah, in retrospect everything is so obvious. /facepalm

How could the Greek and Roman engineers not discover and use steam machines? They were so close! The machines are so obvious!

You need a more specific question; they did discover and use steam machines.

But you probably have a particular use in mind. And once you realize that, you can ask "would steam engines have been helpful to the Greeks in this context?"

Their economy did not depend on deep mining and the need to pump water away from mines. This only happened over thousand years later.

My reading was they hand made a solution, called it optimal (no proof) and then were disappointed when the ANN didn't converge to their weights...