5 ms·

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

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.

cgearhart 10y ago
> 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.
- eutectic 10y ago
  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.
  - ssivark 10y ago
    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?
    - eutectic 10y ago
      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.
    - BickNowstrom 10y ago
      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.
Cybiote 10y ago
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

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.

cgearhart 10y ago

> 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.

eutectic 10y ago
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.
- ssivark 10y ago
  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?
  - eutectic 10y ago
    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.
  - BickNowstrom 10y ago
    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.

Cybiote 10y ago

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