No Free Lunch Theorem

• There are a bunch of No Free Lunch proofs, but the canonical one is No free lunch theorems for search by Wolpert and Macready
• The short version is that no search algorithm is better on all problems.
• It also works for categorisation algorithms.
• The longer version is that on the average problem, all algorithms (including just guessing) do the same.
• The reason it's called No Free Lunch is that it requires the analyst to do some work understanding the problem.
• Once you begin to understand the problem, you can apply appropriate algorithms.
• This means that you need to know what the appropriate algorithms are.
• Moreover, once you apply an algorithm, you learn more about the problem.
• You can then use other algorithms to explore the problem.
• This is why there are a lot of jobs for people in machine learning.