And I like the bayesian interpretation too. Murphy's "Probabilistic machine learning" has an occam's razor section.
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.
This is a longstanding principle in model-fitting. More parameters, almost always, improves the ability of the model to fit to any particular data, in-sample. The model with the least parameters is both the simplest in principle and has the best chance of not overfitting.
This is provably not true, and you can use the marginal likelihood / PAC-Bayes to prove it (or any other framework for measuring model quality). Increase the number of parameters in a linear model way beyond the point of interpolation, and concentrate the likelihood around the zero loss set. Then reduce the variance on a Gaussian prior. You can balance the two temperatures at exactly the right rate so that any measure of model quality will monotonically increase with model size and achieve a maximum at infinite model size.
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.
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.
You can choose the prior according to any selection rule that does not see the data (actually, you can do more, but justifying this is the realm of empirical Bayes and requires some more precise arguments). In this case, you can choose it according to the model size and provided that your Jacobian is full rank, you will get increasing marginal likelihood.
What threw me off was the (possibly misunderstood) suggestion for minimizing the generalization bound over the prior after the data has been incorporated.
You are saying something interesting, but talking like Grok and skipping a lot of the details, without any references to common check-in points like terminology or specific studies.
> 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.
Apologies, I'm skipping details, because that's how I speak with my colleagues, but I realize this is an external environment without context. No references since this is folklore (you can look at Hastie et al's Surprises in High-Dimensional Ridgeless Regression paper for the non-Bayesian version, Bruno Loureiro or Andrew Gordon Wilson probably have a paper with something similar).
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.
Another useful link [0], page 91. Effectively, the more complex the solution, the heavier is the upper bound on true risk. It doesn't mean a simpler model is necessarily better. But the complexity brings its own larger support for mistakes to live in. The _likelihood_ of being _more correct_ is probably related to larger sample required to learn a more complex model.
Absolutely not. This link is a reference on PAC learning, which is thoroughly misleading in the land of deep learning and inevitably leads to vacuous bounds. This is common knowledge in deep learning. I would not recommend that any student learn any part of this theory at this point, since we have far better alternatives in terms of simplicity, accuracy, and generality.
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.
"Can be misleading" is an accurate characterization.
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 agree that this is a good nuanced take. However, I find that students who have learned PAC (which usually takes quite some time) often have to unlearn certain principles to do PAC-Bayes, so my comments come from a fair amount of frustration with the topic. On the other hand, I find that teaching students PAC-Bayes from the get-go is easier, it still works for simpler models (you can derive the same PAC bounds, so you can't do any worse), and they get the full story. Obviously for those of us who learned both, it is good to know both. But I am skeptical for the next generation coming through whether it is worth teaching PAC at all.
There are also various metaphysical theories that posit that the universe is algorithmically generated in some sense or the other, and from many of those theories it follows that simplicity is a fundamental feature of reality, which yields an even stronger version of Occam’s Razor.
You don't need the onerous assumption that the universe is algorithmically generated, just that all ways to reason about and communicate intelligently for the purpose of making decisions is digital.
The notion of "simplicity" can be completely arbitrary, though. It's enough that there are only finitely many hypotheses simpler than the best hypothesis (assuming there's such a thing as a best hypothesis). So as you eliminate hypotheses incompatible with the data, at some point you'll have eliminated all simpler hypotheses, and the simplest hypothesis left will also be the best hypothesis. If simpler hypotheses are also more likely to be correct, you get there faster, but it's not required.
It doesn't have to be arbitrary. The Kolmogorov/Solomonoff definition, that the simpler models are the shortest programs that can generate what we know about a domain, measured in bits, have a solid mathematical foundation, based on information entropy and even thermodynamic entropy if you cross over into computer hardware.
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 is some art to it, especially in model architecture choices.
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.
Except for the fact that eventually we are all dead.
So it is kind of important to get there faster.
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.
To be clear, I was doing a reductio ad absurdum. PAC is precisely the kind of theoretical framework that concerns itself with asymptotic long-run behavior. An appropriate definition of simplicity certainly gets you to the goal much faster than the worst-case bound. For example, you could order hypotheses from most to less likely. But that would render the claim that simpler hypotheses are more likely rather tautological.
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.)
PAC isn't asymptotic in general. It gives finite estimates for finite sizes of training data.
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.
It has been a while, but I was quite surprised by how good gcc/g++ was at explaining why it had failed to vectorize a certain loop. At that time clang was being positioned as the better-than-gcc at optimization and error messages and it turned out that on my code it was the other way round -- hence the surprise.
I had written a expressions template C++ helper library with sort of the same functionality as Python's itertools before I was familiar with itertools.
This was for my own consumption. I expected very little from g++ and it had me impressed. Would be around 2008 - 2010.
Actually, one caveat is that GCC's optimization info can be rather inscrutable because it's in terms of compiler internal nomenclature. That's a definite area for improvement (or compiling some sort of key to it).
Indeed, GCC optimizes well. Last time I ran a set of Fortran benchmarks, the geometric mean for them was competitive with other compilers on multiple architectures, and some of the benchmarks could have been sped up considerably with specific compiler options or by re-writing a function sacrificing numerical equivalence, which the Intel compiler seemed to do itself.
I am more of an applied mathematician and a complete ignoramus in compiler technology. So I cannot emphasize enough the surprise ... wait I can actually understand what this compiler is saying and this is not clang, this is not supposed to happen on templates heavy code.
This is by no means a humble brag. Kudos to the GCC engineers. Competition with Clang certainly helped.
These days GCC has much better error messages even for non-vector code, IMO. I feel like Clang has become more of a research platform and GCC is winning on the usability front
If you turned on specific optimization and warning flags it emitted a lot of useful information to stdout/stderr. It was quite helpful even to a compiler technology ignoramus like me.
It would identify specific loops and would provide reasons why it could not vectorize it, usually some sort of aliasing that it could not rule out. I would then rewrite the code if the rewrite was simple, to make it obvious that such aliasing wouldn't occur. If it wasn't aliasing it was some sort of a cost benefit model that my loop had not crossed.
Seen a photograph of starlings when the flock takes on the silhouette of a giant bird. I've always been fascinated by that kind of (apparent?) collective intelligence. There's seemingly no leader, but from the interactions of swarms of independent actors emerge (what seems like) a larger mind. Surely we humans exhibit such behavior also, when seen from a certain elevated perspective like statistics.
Ooh boids, yes! One of my favorite books is Vehicles: Experiments in Synthetic Psychology. I learned about it from another favorite, Nature of Code, which has a great list of related books. https://natureofcode.com/resources/#further-reading
I didn't vote, but my guess would be that it's because "aphantasia" (the inability to visualize images) is a popular topic on this site: https://en.wikipedia.org/wiki/Aphantasia. Some people see images in their head, and others (possibly overrepresented here) simply don't. My guess would be that a comment that starts by assuming everyone sees images in their heads was considered misleading and simplistic.
My confusion was slightly different. The parent comment was the top ranked comment yet grayed and continued to remain gray after I upvoter.
About your comment, I am very because I am not sure where I myself fall.
My mental imagery is certainly not so strong that I can claim with any confidence that I have one. My wife, on the otherhand claims strongly that she can see things in her minds eye and I have ample evidence to believe it.
Can those with aphantasia do rough sketches of some familiar object from memory of the object ?
There is a loophole in the task though. One can translate the visual imagery into words and remember them. Then one can sketch using the remembered words, not that different from the workings of a deep autoencoder.
It really comes down to the nature and geometry of the latent space. Is it a topological space with a topology less boring than a discrete topology. Is it spatial/geometric or symbolic.
Then why don't you ? and did you mean all or those that halt ? I presume you have a way of separating those.
reply