This article suggests a ‘best alternative' justification of induction (in the sense of Reichenbach) which is based on meta-induction . The meta-inductivist applies the principle of induction to all competing prediction methods which are accessible to her. It is demonstrated, and illustrated by computer simulations, that there exist meta-inductivistic prediction strategies whose success is approximately optimal among all accessible prediction methods in arbitrary possible worlds, and which dominate the success of every noninductive prediction strategy. The proposed justification of meta-induction is (...) mathematically analytical. It implies, however, an a posteriori justification of object-induction based on the experiences in our world. *Received November 2005; revised March 2008. †To contact the author, please write to: Department of Philosophy, University of Duesseldorf, Universitaetsstrasse 1, Geb. 23.21, Duesseldorf, Germany D-40225; e-mail: [email protected]. (shrink)

This is the first of two papers that use off-training set (OTS) error to investigate the assumption-free relationship between learning algorithms. This first paper discusses the senses in which there are no a priori distinctions between learning algorithms. (The second paper discusses the senses in which there are such distinctions.) In this first paper it is shown, loosely speaking, that for any two algorithms A and B, there are “as many” targets (or priors over targets) for which A has lower (...) expected OTS error than B as vice versa, for loss functions like zero-one loss. In particular, this is true if A is cross-validation and B is “anti-cross-validation” (choose the learning algorithm with largest cross-validation error). This paper ends with a discussion of the implications of these results for computational learning theory. It is shown that one cannot say: if empirical misclassification rate is low, the Vapnik-Chervonenkis dimension of your generalizer is small, and the training set is large, then with high probability your OTS error is small. Other implications for “membership queries” algorithms and “punting” algorithms are also discussed. (shrink)

The no free lunch theorem is a radicalized version of Hume’s induction skepticism. It asserts that relative to a uniform probability distribution over all possible worlds, all computable prediction algorithms—whether ‘clever’ inductive or ‘stupid’ guessing methods —have the same expected predictive success. This theorem seems to be in conflict with results about meta-induction. According to these results, certain meta-inductive prediction strategies may dominate other methods in their predictive success. In this article this conflict is analyzed and dissolved, by means of (...) probabilistic analysis and computer simulation. (shrink)

According to the paradigm of adaptive rationality, successful inference and prediction methods tend to be local and frugal. As a complement to work within this paradigm, we investigate the problem of selecting an optimal combination of prediction methods from a given toolbox of such local methods, in the context of changing environments. These selection methods are called meta-inductive strategies, if they are based on the success-records of the toolbox-methods. No absolutely optimal MI strategy exists—a fact that we call the “revenge (...) of ecological rationality”. Nevertheless one can show that a certain MI strategy exists, called “AW”, which is universally long-run optimal, with provably small short-run losses, in comparison to any set of prediction methods that it can use as input. We call this property universal access-optimality. Local and short-run improvements over AW are possible, but only at the cost of forfeiting universal access-optimality. The last part of the paper includes an empirical study of MI strategies in application to an 8-year-long data set from the Monash University Footy Tipping Competition. (shrink)

This article poses a challenge to Schurz’s proposed metainductive justification of induction. It is argued that Schurz’s argument requires a notion of optimality that can deal with an expanding pool of prediction strategies.