> It’s not that the simplest is more likely to be correct, it’s that you should prefer it, because it’s simple.
I don't know what Occam meant, but if you accept the formalism of PAC learning, it is more likely to be correct
https://web.archive.org/web/20170428225156/http://www.cse.bu...
https://web.archive.org/web/20130412062821/http://cs.ecs.bay...
The idea is that a complex model explains many more configurations (datasets) than a simple one. So its (prior) probability distribution is lower on the data seen (to compensate for the other possibilities it might explain). So the (marginal) likelihood that the simple model is correct is higher if it fits the data well enough.
It so happens that one gets the best generalization error bounds when one combines PAC with Bayesian ideas -- the PAC-Bayesian bounds.
Even easier, just take a limit of polynomial regression to a Gaussian process while optimizing the marginal likelihood over the prior temperature.
In all of these cases, the model with the least parameters is not the simplest in principle and does not have the best chance of not overfitting. The reality is significantly more nuanced.
> and concentrate the likelihood around the zero loss set. Then reduce the variance on a Gaussian prior.
Those phrases could mean a lot of different things. What are you proposing?
> so that any measure of model quality will monotonically increase with model size and achieve a maximum at infinite model size.
any measure of model quality? You must have some bounds of any measure, since trivially that's false because "fewer parameters is better" is a measure of model quality, even if dumb.
It's hard to even engage when you're being so imprecise, and not even giving one specific example.
Concentrating a density around a zero set means that I raise it to the power of 1/gamma (appropriately normalizing) and then take gamma to zero. If the likelihood was Gaussian, this would be equivalent to taking the variance to zero (yielding a point mass). But in overparameterized settings, this concentrates on a submanifold describing the set of interpolating solutions. In least-squares linear regression, that is the solution space. Reducing the variance on a Gaussian prior is treated as an asymptotic expansion by Laplace's method. If you choose the variance to decrease (inversely proportional to the parameter size, for example), then the marginal likelihood will increase monotonically with model size.
By any measure of model size, I mean that you can pick your favourite among the common ones, such as information metrics (e.g. mutual information / KL), statistical metrics (e.g. marginal likelihood), test error. You should be able to show the same phenomenon happening for all of them, so it isn't a quirk of marginal likelihood. It is concentration of measure working in your favor to reduce the variance in the estimator.
E.g. over-fitting.
This is why the notion of overfitting is not nearly as cut and dry as a basic ML course would have you believe. Just because you fit data exactly does not mean that your estimator has high error on out of sample data. A trivial counterexample is a spiking model that spikes to fit to the data but otherwise follows the correct trend outside of the dataset. The bias variance tradeoff gets thrown out at enormous scale and overfitting is not a meaningful concept. What matters is regularization and robustness, not how well you fit the data.
The reason why bias variance tradeoff and considerations of model size are a good approximation for smaller models is due to concentration of measure in the data which effectively kills any regularization in your modelling procedure. Once you enter settings where concentration of measure begins to bite in parameter space, everything changes. This isn't really that mysterious; any textbook on Gaussian processes (e.g. Rasmussen and Williams) will tell you this.
Does model performance also concentrate into a 'typical case' where things work pretty well and a non-typical case where it's completely unpredictable as the number of parameters increase?
Are you sure that doing this after seeing the data is valid and does not suffer from the equivalent of peeking-into-the-test-set problem ? There are ways to address the peeking problem but that requires additional machinery.
I don't dispute your broad claim but the first counterexample you quote seems problematic.
[0]: https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearnin...
PAC-Bayes is genuinely superior, for example. Instead of a uniform weighting over all hypotheses (effectively encoded in the supremum), you get to weight the hypothesis class in virtually any way that you want. This is critical to ensure that you exclude absurd hypotheses that you have almost nil chance of reaching. If you do consider a uniform weighting, then you can just easily reduce to PAC anyway, but you do so in a cleaner package.
It is an uniform bound and will have problems with very large hypothesis classes but its statement isnt wrong (just that the tool is a little heavy handed). For simpler models they are adequately useful. So I would suggest new users to learn if they want to use simpler models rather than deep learning methods.
Real world isn't the adversarial/ worst-case that these models of generalization assume. So the generalization performance you experience is usually a better than what PAC indicates, but estimating that experience was not PAC's charter. It's charter was to quantify a adversarial/legal guarantee, the minimum (infimum) guaranteed program.
I too like PAC-Bayes a lot (see my other comments) but it does have a cop out in that by definition you do not know how good your prior is, yet the quantitative estimate of generalization error depends on how good it was.
Nevertheless, PAC-Bayesian and statistical physics based bounds are closer to what we experience, but you can't guarantee that the worst case will not bite you.
I had not considered the pedagogical value of starting with PAC Bayesian bounds. It will be interesting to see ML courses that take that route.
Similar issues show up in traditional statics when considering multi-hypothesis testing. I wonder if betting/gambling over hypotheses might be a more accessible way to convey these ideas to new students.
https://books.google.co.in/books/about/User_friendly_Introdu...
Free download here
https://arxiv.org/abs/2110.11216
One of the ICMLs had a nice tutorial by Langford and Banerjee on the relationship between the different style of bounds. 2003, I think.
Regular PAC falls out by taking a uniform prior over a finite hypothesis class (and then building up VC dimension if desired, but usually by this point you realise why the bounds are unlikely to be good).
On Bayesian Bounds https://dl.acm.org/doi/10.1145/1143844.1143855
Tutorial on Practical Prediction Theory for Classification https://jmlr.csail.mit.edu/papers/v6/langford05a.html
The first one is quite in the same spirit that you like.
Fixed.
For complicated hypotheses, where complicated is defined appropriately, it takes many many examples to realize that it was a wrong hypothesis all along. There lies the rub.
For a particular instance of a learning problem we can't tell much, however using a Occams razor over many instances, one would be correct more often than not. Provided, of course, the PAC assumptions are true or they are not very far from being true.
How far is not very far ? That gets very hairy to quantify.
More typical definitions of simplicity, e.g. using the bit length of some kind of natural encoding, aren't guaranteed to offer any special advantages in terms of likelihood. So if you have prior knowledge that a particular hypothesis is more likely than another, but the less likely one is simpler in an intuitive sense, you shouldn't let that override you, but still prefer the more likely option. (And you don't need to take the circuitous route of coming up with a new encoding where the more likely hypothesis has a shorter bit length, either.)
If you say, and I think you are indeed saying so, that PAC is ridiculously pessimistic, I would be in violently agreement with you. That's one reason why for practical training data sizes and practical (infinite version space) hypothesis classes PAC gives bound such as -- probability of error is less than 41K. This isn't exactly incorrect but not very useful or informative.
A far more useful formulation is PAC-Bayesian where you get error bounds less than 1 guaranteed and usually less than 0.5 on reasonable sized training data sets.
But your smarter data scientists will try to get the best information density on test data to approximate generalization. MDL, as championed here, or AIC/BIC if working with more established and acceptable methods.
Entropy is a metric targeted in LLM training which is likely why LLMs are overfitting less and less as they improve and why they subjectively seem to obey Occam's razor.
There's lesson for software engineering in general behind that kind of simplicity. https://benoitessiambre.com/entropy.html