3 ms·

The No Free Lunch Theorem is irrelevant to the real world [0][1]. It assumes all functions, even those with infinite algorithmic complexity, are equally likely.

The No Free Lunch Theorem is irrelevant to the real world [0][1]. It assumes all functions, even those with infinite algorithmic complexity, are equally likely. You should look into algorithmic probability for a better foundation. [0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.540.7938 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.540.... [1] https://arxiv.org/abs/1111.3846.pdf https://arxiv.org/abs/1111.3846.pdf

eli_gottlieb 8y ago
On the one hand, yes, the No Free Lunch Theorem seems to intuitively rely on the set-theoretic definition of functions, rather than building on a constructive foundation to hypothesize that functions which are "physically harder", in some sense, are less likely. On the other hand, algorithmic probability requires first defining a Turing machine, rendering the Solomonoff Measure defined only up to a specific programming language, which can bias it some arbitrary amount. That's on top of the Solomonoff Measure itself being incomputable, and so utterly useless as a foundation for real-world machine learning and computational cognitive science. I agree that positing a Bayesian prior on functions/programs/causal structures gets you around the No Free Lunch Theorem. The question just then ends up being: what sort of hypothesis space, and what sort of prior, sufficiently resemble the real world (the data-generating process) to allow for learning from a given data set? That's a matter of science.