2

In this paper of Aaronson's, a proof is given of Occam's razor by appealing to PAC learning. My understanding of Valiant's bounds for PAC learners is that it requires i.i.d.

This is often a reasonable assumption to make. However, he used this proof of Occam's razor to justify the problem of induction (i.e. claim that the future will represent the past).

If you assume that the future and past data are drawn from the same distribution (which is how I think i.i.d. is being used), this strikes me as essentially assuming that the future will be similar to the past, so using PAC learning here begs the question.

Am I misunderstanding the use of i.i.d.? Is there a way around this problem?

Improve this question
1
  • 1
    I think you're right - mainly because I don't think Occams Razor is amenable to proof in the mathematical sense. Nor do I think you can get around the problem of induction so easily.
    – Mozibur Ullah
    Mar 6, 2012 at 0:51

1 Answer 1

Reset to default
3

I think you are intentionally misquoting the section about PAC learning of Aaronson's paper, in order to ask a question about that nicely written paper.

The intention of the quoted section is not to prove Occam's razor, but to explain how Valiant's theory of PAC learning can help with clarifying the following questions regarding Occam's razor:

(1) What do we mean by “simpler”?

(2) Why are simple explanations likely to be correct? Or, less ambitiously: what properties must reality have for Occam’s Razor to “work”?

(3) How much data must we collect before we can find a “simple hypothesis” that will probably predict future data? How do we go about finding such a hypothesis?

The drawback related to the i.i.d. assumption is sufficiently highlighted in the same section:

The third drawback of Theorem 2 is the assumption that the distribution D from which the learner is tested is the same as the distribution from which the sample points were drawn. To me, this is the most serious drawback, since it tells us that PAC-learning models the “learning” performed by an undergraduate cramming for an exam by solving last year’s problems, or an employer using a regression model to identify the characteristics of successful hires, or a cryptanalyst breaking a code from a collection of plaintexts and ciphertexts.

Even so I only read that paper in order to be entitled to answer this question, I think the paper is really worth reading even if you don't want to answer any question. It's easy to read, covers much ground, and even sketches the proofs for some non-obvious theorems. But is it relevant to philosophy? Well, it is an honest attempt to address an audience of philosophers and tries to reduce (or show how it might be possible to reduce) the gap between theory and reality in certain areas.

Improve this answer
2
  • Sorry to be unclear - I have no interest in insulting Aaronson or his paper, I just wonder if there is a way to use Occam's razor to prove results about induction (as he seems to imply).
    – Xodarap
    Jun 26, 2012 at 13:01
  • 1
    @Xodarap I didn't assume you wanted to insult Aaronson. Quite the opposite, I assumed that you used an excuse to draw the attention to his nice paper. He implies indeed that PAC learning helps to clarify the three cited questions related to Occam's razor and induction. For example I find it interesting that the error rate enters linearly in the formula, but the failure rate only logarithmically. So we have a high probability of being nearly right, but a low probability of being completely right (or wrong). But his goals are clarification and discussion of induction, not "proving induction".
    – Thomas Klimpel
    Jun 26, 2012 at 18:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .