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)

The paper presents a comprehensive solution to the new riddle of induction. Gruesome induction is blocked because “grue” is not independent of our sampling and observation methods. Before presenting my theory, I critically survey previous versions of what I call the “independence strategy”, tracing the strategy to three different papers from the 1970s by (respectively) Wilkerson, Moreland, and Jackson. Next I critically examine recent approaches by Okasha, Godfrey-Smith, Schramm, and Freitag. All of these approaches have their virtues, but none of (...) them rules out every problem case. Nor do any of them alone explain exactly what goes wrong in all types of gruesome reasoning. My account aims to do both. Learning lessons from my criticisms of previous theories, I argue that there are several crucial types of independence. All of them are needed to rule out every problem case. I close by suggesting that the independence solution can also be adopted by proponents of other approaches—Bayesians, fans of natural kinds, and pragmatists. (shrink)