✳flâneur — a map of the web's best reading

"Occam"-style Bounds for Long Programs

bactra.org · 883 words · saved by 1 readers

A common idea in machine learning is that one can explain, or even prove, Occam's Razor in terms of algorithmic information content. This rests on results which say that if one finds a simple classification rule which works well in-sample, then it is highly probable that it will continue to work well out-of-sample. (The clearest and most elementary explanation of such results I've seen is in Kearns and Vazirani's Introduction to Computational Learning Theory.) I think there are several things wrong with this --- not with the theorem, which is perfectly valid, but with the argument. The technical results say that a classification rule is simple if it has a short description, measured in bits. (That is, we are in minimum description length land, or very close to it.) The shorter the description, the tighter the bound on the generalization error. I am happy to agree that this is a reasonable (if language-dependent) way of defining "simplicity" for classifier rules. However, so far as I ca

"Occam"-style Bounds for Long Programs Notebooks "Occam"-style Bounds for Long Programs Last update : 07 Jul 2025 12:15 First version : 17 June 2010 What follows is essentially the first draft I wrote sometime on or before 17 June 2010, with a few old links fixed and nicer mathematical type-setting. I still think it's right. A common idea in machine learning is that one can explain, or even prove, Occam's Razor in terms of algorithmic information content. This rests on results which say that if one finds a simple classification rule which works well in-sample, then it is highly probable that i

Explore this link on the map →

related reading