This essay demonstrates a previously unnoticed connection between formal and statistical learning theory with regard to Nelson Goodman’s new riddle of induction. Discussions of Goodman’s riddle in formal learning theory explain how conjecturing “all green” before “all grue” can enhance efficient convergence to the truth, where efficiency is understood in terms of minimizing the maximum number of retractions or “mind changes.” Vapnik-Chervonenkis (VC) dimension is a central concept in statistical learning theory and is similar to Popper’s notion of degrees of (...) testability. I show that for a class inductive problems of which Goodman’s riddle is one example, a reliable inductive method minimizes the maximum number of mind changes exactly if it always conjectures the hypothesis from the set with lowest VC dimension consistent with the data. I also discuss the relevance of these results to language invariance and curve fitting. (shrink)

A finite data set is consistent with infinitely many alternative theories. Scientific realists recommend that we prefer the simplest one. Anti-realists ask how a fixed simplicity bias could track the truth when the truth might be complex. It is no solution to impose a prior probability distribution biased toward simplicity, for such a distribution merely embodies the bias at issue without explaining its efficacy. In this note, I argue, on the basis of computational learning theory, that a fixed simplicity bias (...) is necessary if inquiry is to converge to the right answer efficiently, whatever the right answer might be. Efficiency is understood in the sense of minimizing the least fixed bound on retractions or errors prior to convergence. (shrink)

This article argues that a successful answer to Hume's problem of induction can be developed from a sub-genre of philosophy of science known as formal learning theory. One of the central concepts of formal learning theory is logical reliability: roughly, a method is logically reliable when it is assured of eventually settling on the truth for every sequence of data that is possible given what we know. I show that the principle of induction (PI) is necessary and sufficient for logical (...) reliability in what I call simple enumerative induction. This answer to Hume's problem rests on interpreting PI as a normative claim justified by a non-empirical epistemic means-ends argument. In such an argument, a rule of inference is shown by mathematical or logical proof to promote a specified epistemic end. Since the proof concerning PI and logical reliability is not based on inductive reasoning, this argument avoids the circularity that Hume argued was inherent in any attempt to justify PI. (shrink)

In a recent article in this journal, Daniel Steel charges me with committing a fallacy in my discussion of inductive rules. I show that the charge is false, and that Steel's own attempt to validate enumerative induction in terms of formal learning theory is itself fallacious. I go on to argue that, contra Steel, formal learning theory is in principle incapable of answering Hume's famous claim that any attempt to justify induction will beg the question.