Prior Knowledge in Machine Learning

The Universal-Learner Challenge

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.

Unobserved Labels

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.

Binary Classification and 0-1 Loss

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.

The ERM Choice

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.

Learner Failure versus Task Impossibility

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.

• Treating the No-Free-Lunch Theorem as saying that no learning algorithm can succeed.

  The theorem says that every learner has some task on which it fails, not that every learner fails on every task.

  Fix: Separate a limitation of one learner from impossibility of the task. The ERM example succeeds for a task when H = {f} and L_D(f) = 0.

• Assuming that observed labels determine all unobserved labels.

  In the theorem's construction, the remaining instances are unobserved, and a target function can contradict the learner's predictions there.

  Fix: Track which instances were observed and recognize the uncertainty about the rest.

• Ignoring the evaluation setting.

  The theorem here is applied to binary classification with the 0-1 loss.

  Fix: State that predictions are evaluated by whether they agree with the true binary labels.

Why Prior Knowledge Matters

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}.

Check Your Understanding

1. The No-Free-Lunch Theorem says that no single learner succeeds on every possible learning task. Its proof uses a subset C of size 2m, gives the learner only m observed instances, and exploits the uncertainty about the remaining labels. In binary classification, performance is evaluated with the 0-1 loss. A learner's failure on one task does not prove that the task is impossible: another learner, such as an ERM learner using H = {f} when L_D(f) = 0, may succeed. Prior knowledge and hypothesis choices are therefore central to generalization.