Prior Knowledge in Machine Learning

A learning algorithm receives a training set and must predict labels for examples it has not observed. The central question is whether one learner could succeed on every possible learning task. The No-Free-Lunch Theorem answers no: for every learner, there is a task on which that learner fails.

The proof uses a subset C of the domain X with size 2m, where m is the size of the training set. The learner observes only m instances from C, which is half of the instances in C. The other instances remain unobserved.

The learner has information about the labels attached to the observed instances, but no information about the labels of the unobserved instances in this construction. Therefore, a target function f can assign labels to those unobserved instances that contradict the learner's predictions there.

In this setting, the theorem is applied to binary classification with the 0-1 loss. A binary classifier produces a label prediction for an instance, and the prediction is evaluated against the true label. The 0-1 loss treats the prediction as correct when it agrees with the true label and as an error when it does not.

The theorem's claim is therefore about performance measured by this classification loss. For every learner, the theorem identifies a learning task on which the learner fails under the stated binary-classification evaluation.

Empirical Risk Minimization, or ERM, selects a hypothesis using the observed examples. The theorem's source example makes the hypothesis class especially simple: H = {f}. There is only one available hypothesis, namely f, so an ERM learner using this class selects f.

A learner's failure is a statement about the match between that learner and a task. It is not a statement that the task cannot be learned by any learner. The source gives the contrasting ERM example: an ERM learner using H = {f} selects f and succeeds when L_D(f) = 0.

Thus, one learner may fail on a task constructed against it, while another learner succeeds on that same task. The No-Free-Lunch Theorem rules out a universal learner; it does not rule out learners that work well for particular tasks.

The theorem's uncertainty comes from allowing possible tasks whose labels are not determined by the observed examples. Prior knowledge matters because a learner is not successful merely by receiving data; it also needs a relationship between its available hypotheses and the task. The source's ERM example illustrates this relationship through the hypothesis class H = {f}.