The Implications of the No-Free-Lunch Theorems for Meta-induction
  The important recent book by G. Schurz appreciates that the no-free-lunch
theorems (NFL) have major implications for the problem of (meta) induction.
Here I review the NFL theorems, emphasizing that they do not only concern the
case where there is a uniform prior -- they prove that there are "as many
priors" (loosely speaking) for which any induction algorithm $A$
out-generalizes some induction algorithm $B$ as vice-versa. Importantly though,
in addition to the NFL theorems, there are many \textit{free lunch} theorems.
In particular, the NFL theorems can only be used to compare the
\textit{marginal} expected performance of an induction algorithm $A$ with the
marginal expected performance of an induction algorithm $B$. There is a rich
set of free lunches which instead concern the statistical correlations among
the generalization errors of induction algorithms. As I describe, the
meta-induction algorithms that Schurz advocate as a "solution to Hume's
problem" are just an example of such a free lunch based on correlations among
the generalization errors of induction algorithms. I end by pointing out that
the prior that Schurz advocates, which is uniform over bit frequencies rather
than bit patterns, is contradicted by thousands of experiments in statistical
physics and by the great success of the maximum entropy procedure in inductive
inference.
