On 'No Free Lunch' Theorems
The old saying “There ain’t no such thing as a free lunch” suggests that you can’t get something for nothing. It is also the namesake for the topic of this post: the “no free lunch” theorems (NFLT). NFLT revolves around the difficult problem of optimisation; finding the best result out of a set of alternatives.
As an example, I previously came across optimisation for computer vision in the task of separating an image’s background (also known as ‘background subtraction’). Different background subtraction algorithms such as ‘MOG’, ‘GMG’ and ‘KNN’ [1] yield different results depending on the nature of the image. MOG might work better in low detail scenes than KNN, which might work better with high contrast, and so on…
Essentially it seems to boil down to NFLT, which states that two algorithms optimal for two problems (e.g. background subtraction algorithms optimal in day and night) are equivilent when their performance for all problems (e.g. background subtraction in general) is averaged [2].
NFLT actually goes much deeper through two mathematical derivations for supervised machine learning (Wolpert, 1996) and search/optimisation (Wolpert and Macready, 1997) [3]. It’s somewhat depressing consequence is that a universal optimisation strategy that can be applied to any problem and provide optimal results is impossible [4]. Appreciating that fact, however, forces you to practice trial and error as a problem solving method. This approach is both a good way to learn and a creatively valuable one, as experimenting often leads to surprising results.
In question of NFLT, I wonder how it fares with the simulation hypothesis. If a computer is simulating our reality then does it perform optimally for all possible problems? Could we then use such an algorithm to simulate a universe within our own? Even if the answer is “probably not” it’s an interesting thought to ponder.
[1] OpenCV Background Subtraction
[2] Coevolutionary free lunches
[4] Simple Explanation of the No-Free-Lunch Theorem and Its Implications
For Natural Computing (IS53052A)