1
$\begingroup$

I am trying to delve a little bit deeper into the implications of the No Free Lunch (NFL) theorem for supervised learning. The basic form of NFL is that averaged all data generating distributions all ML algorithms perform equally well.

The title basically summarizes my question:

If we fix the data generating distribution and the number of training samples to $N_\text{train}$, do all ML algorithms have the same performance if we average over all possible data sets of size $N_\text{train}$?

I find this resource that discusses the implications of the no free lunch theorem but I can't understand what is conditioned on during averaging:

All algorithms are equivalent, on average, by any of the following measures of risk:

E(C|d), E(C|m), E(C|f,d), or E(C|f,m).

where:

  • d = training set
  • m = number of elements in training set
  • f = target input-output relationships
  • h = hypothesis (the algorithm's guess for f made in response to d)
  • C = off-training-set loss associated with f and h (generalization error)
Improve this question
$\endgroup$
5
  • $\begingroup$ I have made an edit to clarify what NFL means. If I have made a mistake, please do correct it. $\endgroup$
    – Dave
    Commented Jul 23 at 18:13
  • $\begingroup$ When you see statements like this: "Wolpert's result, in essence, formalizes Hume, extends him and calls the whole of science into question." on a website (the one you linked to), you might call the whole of the web post into question. The Wikipedia page (en.wikipedia.org/wiki/No_free_lunch_theorem) gives a much clearer and less hyperbolic description, IMO. $\endgroup$
    – jbowman
    Commented Jul 23 at 18:20
  • 1
    $\begingroup$ NFL theorem is fundamentally wrong. I have never seen centillions in any dataset. All equipment on our planet emits human readable numbers. Hence Occam’s razor and/or regularization works. It works maybe in an idealized universe but not on earth. $\endgroup$
    – Cagdas Ozgenc
    Commented Jul 23 at 18:31
  • $\begingroup$ See arxiv.org/pdf/1111.3846 $\endgroup$
    – Cagdas Ozgenc
    Commented Jul 23 at 18:37
  • $\begingroup$ @CagdasOzgenc - it's not wrong, it's just that the universe is too small! $\endgroup$
    – jbowman
    Commented Jul 23 at 22:18

1 Answer 1

Reset to default
1
$\begingroup$

No, the no-free-lunch theorems are specifically about averaging over all possible data generating distributions on the same set of values, not just over data sets.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.