No Free Lunch Theorem

Definition

Setup: finite $\mathcal{X}=\{x_1,\dots ,x_m\}$, deterministic labels $\pm 1$, all $2^m$ functions as possible truths. $r_{ij}$ is the true error of the estimated $f_i$ when $f_j$ is true.

Formula

• Proposition 7: in each row, the value $k/m$ occurs $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ times.
• Proposition 8: averaged over all true functions, all classifiers perform the same.
• Proposition 9: averaged over all true functions consistent with the training data, all classifiers with 0 training error perform the same.

There is no best classifier for all problems. As soon as we assume something about the true function (similar inputs have similar labels), columns of the table disappear and some classifiers become better than others: machine learning without an inductive bias is impossible. The NFL does not contradict universal consistency, which is an asymptotic statement for each fixed distribution.

Appears in

• Lecture 1.2, setup
• Lecture 1.2, Propositions 7 to 9
• Lecture 1.2, exam-style task
• Lecture 1.2, discussion

Related concepts

• Inductive Bias
• Consistency