News for hackers. Stuff that matters.
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by paulsutter on Thursday March 02, 2017 @08:15AM (#13773770)
No Free Lunch theorem refesher:

"if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems"

https://en.m.wikipedia.org/wiki/No_free_lunch_theorem

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by eutectic on Thursday March 02, 2017 @08:40AM (#13773892)
The No Free lunch theorem is basically a consequence of the fact that almost all problems 'look random'; it doesn't really apply to the tiny subset that are of interest to humans.
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by Cybiote on Thursday March 02, 2017 @01:49PM (#13776961)
An often missed point is that the NFL has a practical consequence and that is, learning doesn't happen if the model architecture is not well adapted to the structure of the data. There being structure is not on its own strong enough to allow for any algorithm to do well. The model itself needs to be aligned with the structure in the data. This applies to animals, humans too, by inserting structural priors, evolution sacrificed performance on certain kinds of problems to do well on the kind we met in the natural world.

You can read more in: Antipredictable Sequences: Harder to Predict Than Random Sequences by Huaiyu Zhu and Wolfgang Kinzel

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by cgearhart on Thursday March 02, 2017 @09:17AM (#13774097)
> it doesn't really apply to the tiny subset that are of interest to humans.

That's a very misleading TL;DR. NFLT certainly _applies_ -- deep networks are not immune to NFLT -- it's just that NFLT isn't very useful because we can't use it as a basis for decisions. You can't detect that your algorithm's performance is being limited as a consequence of NFLT; and even if it were consequential, you would just see that the algorithm wasn't working very well, and there are _much_ more likely causes for that than NFLT.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by eutectic on Thursday March 02, 2017 @10:11AM (#13774510)
If you have two predictors p0 and p1 then it can be shown that the mixture p(data) = (p0(data) + p1(data)) / 2 incurs at most 1 bit of loss compared to the better of p0 and p1.

In other words, for any pair of machine learning algorithms there is an algorithm which only performs marginally worse than either of the two on any given problem, and which may perform arbitrarily better. NFL equalises these two cases by smearing tiny losses over vast regions of possibility-space that are vanishingly unlikely.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by ssivark on Thursday March 02, 2017 @10:35AM (#13774749)
I often hear the claim that NFL just implies that different algorithms and learning strategies will succeed for different tasks. And that NFL has no practical consequences apart from that.

Is there a resource I can refer to, that is clear and explicit about the reasoning?

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by BickNowstrom on Thursday March 02, 2017 @01:53PM (#13777001)
NFL is probably the worst mis-quoted theorem in ML.

The subtle elements of the theorems (both for inference and search) have had huge impact on the field of optimization theory. They touch upon (Kolmogorov) Complexity, Incompleteness, Halting Problems, and later related work on the physical limits of inference: One can not know everything about the universe, if you are a part of it, and philosophy: Is the universe itself a computer?

That different algorithms and search strategies will succeed for different tasks, does not imply that we have to try them all: We can use prior knowledge on what worked on related tasks. Also the tasks we care about, is only a very small (explorable) subset of all possible tasks.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by eutectic on Thursday March 02, 2017 @10:48AM (#13774875)
The fact that different algorithms are best for different tasks has more to do with computational complexity.

If we didn't care about resource usage then we could just pick a sufficiently expressive model class (e.g. all algorithms) to mix over, and perform Bayesian inference. You can look up AIXI and Solomonoff induction for more thoughts along these lines.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by Houshalter on Thursday March 02, 2017 @10:41AM (#13774804)
There is a theoretically optimal machine learning algorithm called Solomonoff Induction. Solomonoff Induction assumes a prior over all possible computer programs that could have produced the data. And it assumes that shorter, simpler programs are more likely than longer, more complex ones. Under such a prior, the no free lunch theorem doesn't apply.

NFLT assumes that all machine learning problems have infinite information. Infinite Kolmogorov complexity. That all positive and negative examples are labelled completely randomly without any underlying pattern or reason. Which is obviously untrue.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by deong on Thursday March 02, 2017 @01:49PM (#13776952)
Solomonoff Induction isn't really an "algorithm" in the way we normally think of algorithms, as it isn't computable. There are computable approximations, but at that point, you lose the claim of theoretically optimal.
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by Xcelerate on Thursday March 02, 2017 @02:35PM (#13777426)
> There are computable approximations, but at that point, you lose the claim of theoretically optimal.

True, but I'm surprised more work isn't being done on "searching the space of programs that produce the data". There's very little research on this topic other than a few papers on minimum description length (MDL). I feel that this is probably the eventual route to AGI. We know what the "optimal" predictor is in theory; now work out the best time/memory approximation to it for practical purposes.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by Cybiote on Thursday March 02, 2017 @03:36PM (#13777941)
There's lots of work that's being done related to program synthesis and inductive logic programming. You can even view the more sophisticated recurrent Neural nets, with more complex memory structures, as differentiable programs. Then you're searching the space of programs guided by gradients. SGD effectively acts as an additional prior (assumption) by the kind of solutions it tends towards.

The reason (the general) you don't hear much about them if you don't go looking is that the state of the art hasn't budged much for the past couple decades. It's the same graph algorithms, searching and sorting toy problems. The search space over programs is difficult to traverse and it remains to be seen what the added compute power + gradients gets us.

On a more practical level, the learning 2 search paradigm can be viewed as also searching for a particular program under certain strict constraints that make search tractable. Probabilistic programming where the priors and likelihoods are themselves complex programs instead of simple distributions from the exponential family are effectively also searching for programs.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by Houshalter on Thursday March 02, 2017 @08:14PM (#13779968)
This is pedantic and I'm not even certain correct. Full SI will run forever without returning an answer, sure. But as it runs it will get closer and closer to the true answer. Eventually it will approach an answer within whatever degree of precision you want. And it will be more accurate than any alternative algorithm, so it's still optimal.
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by idanoeman on Wednesday March 08, 2017 @02:30PM (#13822939)
Isn't Solomonoff Induction only given a Free Lunch if its priors are true? What if its priors are false?
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by mljoe on Thursday March 02, 2017 @09:34AM (#13774201)
"All remaining problems" in this case means the universe of all potential functions. Everything. Only a vanishingly small subset of every kind of function or dataset are of interest or even observable in nature.
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by CuriouslyC on Thursday March 02, 2017 @08:29AM (#13773830)
That doesn't apply to an ensemble of algorithms where the weights of a given member of the ensemble are adapted based on observations from the given domain. If it did, humans wouldn't be able to choose a good algorithm for specific cases, and obviously we can.

Deep neural networks can be thought of as ensembles of smaller neural networks, though of course each member of the ensemble is going to share some degree of algorithmic bias. This suggests that perhaps deep neural networks with heterogeneous activation functions and branching structures will perform better than homogeneous networks.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by IanCal on Thursday March 02, 2017 @08:58AM (#13773992)
The No Free Lunch theorem doesn't really care how your algorithm does it, and an ensemble of algorithms is just another algorithm. It certainly applies.

The reason it's not actually all that useful for real world applications is that problems we value are a subset of "all possible problems" for want of a better explanation. Problems are typically smooth, that is a small change in input variables results in a small change in 'fitness', which already limits how applicable the NFL theorem is.

[disclaimer, based on lectures 10 years ago now]

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by paulsutter on Thursday March 02, 2017 @08:36AM (#13773871)
The human brain is exactly such an ensemble of algorithms, and look at all the cognitive biases we have[1]. That our brain was developed for foraging, hunting, and reproducing could explain why the code we write is so buggy.

Look I'm just kidding around. Every algorithm has its advocates, and the arguments get tedious after a while.

[1] https://en.m.wikipedia.org/wiki/List_of_cognitive_biases

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by deong on Thursday March 02, 2017 @01:53PM (#13777000)
> If it did, humans wouldn't be able to choose a good algorithm for specific cases, and obviously we can.

This is a surprisingly commonly held fallacy in some AI circles. It's the idea that humans are mathematically perfect. When you phrase it that way, it's fairly obviously false, but you still see a lot of people argue things like "NFL doesn't apply to ensembles because humans..." or "machines can never be as intelligent as humans because...".

The reality is that humans are subject to the same mathematical laws as machines. It's far more likely that my brain can't solve an NP-hard problem in polynomial time either. My brain can't beat random search on the set of all possible problems.

Re:Deep Forest: Towards an Alternative to Deep Neural Networks by CuriouslyC on Thursday March 02, 2017 @04:17PM (#13778319)
It doesn't imply that humans are mathematically perfect, but our brains are basically algorithm generating algorithms - we're not just weighting a set of preexisting solutions. To generalize quite a bit, saying NFL applies to general intelligence ends up implying there are problems for which efficient algorithms exist, but intelligence is literally incapable of discovering. That seems pretty absurd to me.
Re:Deep Forest: Towards an Alternative to Deep Neural Networks by deong on Monday March 06, 2017 @10:19AM (#13803185)
The problem is that if our brains are not "magic" (essentially making this a religious argument), then they're operating via some algorithmic principles. If our brains are "algorithm generating algorithms", then I can in principle write an "algorithm generating algorithm" in silicon that does the same thing. And I know with mathematical certainty that my digital version is subject to NFL. So either my brain is too or we go back to religion to explain what non-physical process is responsible for our super-turing capabilities.

The second point is that NFL is often interpreted in a weird way, where we only think about "interesting problems". It is defined on the set of all search or optimization problems. It says if your algorithm is better than exhaustive search over some subset of problems, it must be worse on the complement of that set.

What does it mean for an algorithm to be efficient? Well, it's roughly speaking the number of steps it needed to take (assuming each step is the same amount of work, blah blah). OK, so an "efficient" algorithm must, by definition, prioritize some steps over others -- it's picking the "best" steps to take each time it has the choice. OK, so I'll just make up some instances of the problem that are custom-tailored so that what the algorithm thinks are the "best" steps always lead me in the wrong direction. You algorithm will then be worse than exhaustive search on my set of problems, precisely because it's choosing to avoid the steps I know to be good -- I defined the problem to make that happen.

That is true of any algorithm you can conceive of. There will be problems for which the bias that makes the algorithm good on the problems you intended it to work on will be exactly the wrong bias.

It doesn't matter if you say, "Aha, I'll let my algorithm generate new algorithms! Gotcha!" I'll just design a set of problems for which your algorithm generating algorithm will generate the wrong algorithms.

Search is always about bias. Without bias, you have random search -- that's literally the textbook machine learning definition of bias. All NFL says is that if you have to worry about every possible problem, any bias you choose will be worse than random sometimes. There's no escape clause here. Your algorithm generating algorithm is still a search algorithm with its own biases, and it will still be worse than random on some subset of all possible problems.