3 ms·

I think you should get less annoyed. > 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 k

• p-e-w 12d ago
  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.
  • jhanschoo 11d ago
    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.
• ruszki 12d ago
  None of your links work for me.
  • srean 12d ago
    Ah! from my very dated and messy bibtex file comments. Wait, let me search for them on archive.org. Fixed.
• yorwba 12d ago
  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.
  • zmgsabst 12d ago
    You choice of basis matters, eg, wavelet versus sinusoid.
  • srean 12d ago
    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.
    • deleted 12d ago
      [deleted]
    • yorwba 12d ago
      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.)
      • srean 12d ago
        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.
• miltava 12d ago
  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. [1] https://probml.github.io/pml-book/book1.html https://probml.github.io/pml-book/book1.html
  • srean 12d ago
    True. It so happens that one gets the best generalization error bounds when one combines PAC with Bayesian ideas -- the PAC-Bayesian bounds.
  • gwerbin 12d ago
    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.
    • hodgehog11 12d ago
      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.
      • 11d ago
• 5555watch 12d ago
  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. [0]: https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearnin...
  • hodgehog11 12d ago
    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.
    • srean 11d ago
      "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.