No Free Lunch Theorem: What you should watch out for when developing your algorithms.
The “No free lunch” theorem states that there’s no one model that works for every problem. The assumptions of a great model for one problem may not hold for another problem. So it is common in Machine Learning to try multiple models and find one that works best for a particular problem. A model that works well could also be trained by multiple algorithms — for example linear regression could be trained by the normal equations or by gradient descent.
No Free Lunch (NFL) Meatphor
In the “no free lunch” metaphor, each “restaurant” (problem-solving procedure) has a “menu” associating each “lunch plate” (problem) with a “price” (the performance of the procedure in solving the problem). The menus of restaurants are identical except in on regard — the prices are shuffled from one restaurant to the next.
For an omnivore who is a s likely to order each plate as any other, the average cost of lunch does not depend on the choice of restaurant. But the Vegan who goes to lunch regularly with a carnivore who seeks economy might pay a high average cost for lunch. To methodically reduce the average cost, one must use knowledge of (a) what one will order and (b) what the order will cost at various restaurants.
That is; improvement of performance in problem-solving hinges on using prior information to match procedures to problems.
NFL in Search and Optimization
Some computational problems are solved by searching for good solutions in a space of candidate solutions. A description of how to repeatedly select candidate solutions for evaluation is called a search algorithm. On a particular problem, different search algorithms may obtain different results, but over all problems, they are indistinguishable. It follows that if an algorithm achieves superior results on some problems, it must pay with inferiority on the other problems. In this sense there is no free lunch in search. Alternatively, following Schaffer, search performance is conserved. Usually search is interpreted as optimization, and this lead to the observation that there is no free lunch in optimisation.
Conclusion.
Depending on the problem, it is important to assess the trade-offs between speed, accuracy, and complexity of different models and algorithms and find a model that works best for that particular problem.
