Original NFL Theorems
Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. The first hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.
- Theorem 1: For any pair of algorithms a1 and a2
In essence, this says that when all functions f are equally likely, the probability of observing an arbitrary sequence of m values in the course of optimization does not depend upon the algorithm. In the analytic framework of Wolpert and Macready, performance is a function of the sequence of observed values, so it follows easily that all algorithms have identically distributed performance when objective functions are drawn uniformly at random, and also that all algorithms have identical mean performance. But identical mean performance of all algorithms does not imply Theorem 1, and thus the folkloric theorem is not equivalent to the original theorem.
Theorem 2 establishes a similar, but "more subtle," NFL result for time-varying objective functions.
Read more about this topic: No Free Lunch Theorem
Famous quotes containing the word original:
“All nationalisms are at heart deeply concerned with names: with the most immaterial and original human invention. Those who dismiss names as a detail have never been displaced; but the peoples on the peripheries are always being displaced. That is why they insist upon their continuity—their links with their dead and the unborn.”
—John Berger (b. 1926)