Saturday, April 21, 2018

The "No Free Lunch" Theorem

The "No Free Lunch" theorem was first published by  David Wolpert and William Macready in their 1996 paper "No Free Lunch Theorems for Optimization".

In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. No solution therefore offers a 'short cut'. 

A model is a simplified version of the observations. The simplifications are meant to discard the superfluous details that are unlikely to generalize to new instances. However, to decide what data to keep , you must make assumptions. For example, a linear model makes the assumption that the data is fundamentally linear and the distance between the instances and the straight line is just noise, which can safely be ignored.

David Wolpert demonstrated that if you make absolutely no assumption about the data, then there is no reason to prefer one model over any other. This is called the "No Free Lunch Theorem" (NFL).

NFL states that no model is a priori guaranteed to work better. The only way to know for sure which model is the best is to evaluate them all. Since this is not possible, in practice you make some reasonable assumptions about the data and you evaluate only a few reasonable models.




2 comments:

  1. Thanks for clear explanation of this basic concept.
    Not what I was expecting, reading "a personal mind dump", but that's good, I guess. One, it's basics, broadening the blog's audience, second, good for blog optimization, for ppl looking for an explanation on NFL theorem may find it here.

    anyway,

    best
    xmoderator

    ReplyDelete
    Replies
    1. Hello, i consider it such because i don't care about building an audience or attracting a lot of people.
      It is just a personal space to push stuff that interests me and I've put some thought on.

      Delete