Hacker News Reader

Comment by yorwba | Hacker News Reader

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.

View on HN

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's lesson for software engineering in general behind that kind of simplicity. https://benoitessiambre.com/entropy.html

How is the Kolmogorov definition not arbitrary? It depends on an arbitrary selection of the language you use to write the program.

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.

You choice of basis matters, eg, wavelet versus sinusoid.

Reply on news.ycombinator.com