Abstract

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.