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:
“What is most original in a man’s nature is often that which is most desperate. Thus new systems are forced on the world by men who simply cannot bear the pain of living with what is. Creators care nothing for their systems except that they be unique. If Hitler had been born in Nazi Germany he wouldn’t have been content to enjoy the atmosphere.”
—Leonard Cohen (b. 1934)