Note on free lunches and cross-validation

                                Cyril Goutte

               Department of Mathematical Modelling, Bygn. 321,
           Technical University of Denmark, DK-2800 Lyngby, Denmark.


The ``no free lunch'' theorems~\cite{wolpert95} have sparked heated
debate in the computational learning community. A recent
communication, \cite{zhu96} attempts to demonstrate the inefficiency
of cross-validation on a simple problem. We elaborate on this result
by considering a broader class of cross-validation. We show that when
used more strictly, cross-validation can yield the expected results on
simple examples.


Keywords: 'No Free Lunch' theorem, cross-validation.