9

Back in September 2006, Scott Aaronson wrote a famous blog post giving 10

  • Reasons to believe that N!=NP. In March 2014, he wrote a more ambitious post about
  • The scientific case for N!=NP. He claims: "This post supersedes my 2006 post on the same topic, which I hereby retire." His post seems to be strongly influenced by previous intellectual exchanges with a convinced Bayesian "climate change" critic. The central Bayesian argument from the post left me with a feeling similar to the following quote from the post (replace "probability" with "science"):

    John Oliver’s deadpan response was classic: "I’m ... not sure that’s how probability works..."

    As a reaction, some computer scientists sympathetic to Scott wrote serious posts about

  • Why do we think N NE NP? They actually started by asking themselves: "Why do scientists believe any particular theory?" and listed the following actual reasons: "(1) By doing Popperian experiments- experiments that really can fail. (2) Great Explanatory power. (3) (Kuhn-light) It fits into the paradigm that scientists already have."

    Other computer scientists more explicitly raised questions "with regard to the main technical argument in a recent post by Scott" by asking

  • Could we have felt evidence for SDP!=P? My impression is that the main technical argument failed to convince them, but their high esteem for Scott prevents them from being blunt about this.

My question is the following: The post from 2014 tries to construct a single Bayesian argument with a single "Bayesian probability" for P!=NP. All the other posts work with multiple independent reasons, and make no attempt at all to unify this into a single Bayesian probability argument. Is subsuming multiple independent reasons into a single Bayesian judgment really in agreement with the scientific method? What does epistemology says about this? (There are statements which are either true or false, but I'm not sure whether this implies that I should only assign a single Bayesian probability to such a statement quantifying how sure I am that it's true.)

Edit Note that my confusion is not caused by using Bayesian probabilities in general, but by the procedure to subsume many different Bayesian probabilies for different facts into a single Bayesian probability for a "stronger" fact. So I'm OK that we can postulate Bayesian probabilities for facts like that N=NP would be very surprising, or that N!=NP explains many observed facts, or that P!=NP is extremely useful. But I'm confused how it should be possible to subsume these into a single Bayesian probability for a "stronger" fact like that P!=NP is true.

  • The statements about "Bayesian inference" in the comments of "The scientific case for N!=NP" are red-herrings; they're a vague justification of handwaving arguments there. – Dave Mar 25 '14 at 19:42
  • Same holds for "Reasons to believe" article -- it's just saying "what we've seen so far makes it more likely that ..." without any formal/rigorous justification. – Dave Mar 25 '14 at 19:46
  • OK, it shouldn't be any stronger or weaker - there would be nothing in the separate arguments that wouldn't be accounted for in the single probability. The single probability can do nothing more than summarise the probabilities you've assigned to the individual arguments. The only thing that could make it "stronger" in any sense would the rhetorical gain in phrasing the argument in terms of Bayesian probability, as I wrote below, its far more likely that the opposite would happen. – Lucas Mar 27 '14 at 17:58
  • Actually, maybe I'm still misunderstanding you. What you mean by stronger is a little unclear to me. The actual calculus in the cases you mention would be very difficult because "P=NP is surprising" and "P!=NP is true" are very closely related and should not be treated as independent, meaning you would need probabilities for things like "P=NP is surprising given P!=NP is true" - does that help? – Lucas Mar 27 '14 at 18:11
  • 1
    Basically, it works just like classical logic but with a number between 0 and 1 replacing true and false (see en.wikipedia.org/wiki/Cox's_theorem) - the same difficulties of evaluating premises and deciding on their relationships with each other, and whether they support a conclusion exist as it would were it logic - there's just some account of how certain you are. – Lucas Mar 27 '14 at 19:25
3

The idea that the inductive process that happens in science is best modelled by Bayesian reasoning has been around for a long time. Edwin Jaynes' book, The Logic of Science (freely available online) is usually cited in this context. I'm not going to repeat the arguments here as they have been far better articulated by others and this answer is kind of long already.

To your specific question:

I was left with the impression that the assumption that multiple independent reasons can be subsumed under a single Bayesian argument is not in agreement with the scientific method.

Within Bayesian reasoning you certainly can combine beliefs in arguments together and get a single probability. If you accept Bayesian reasoning as a model of scientific induction then you accept that you can combine arguments to yield a single probability. However, not everyone accepts the premise that Bayesian reasoning is a good model, in fact, the discussion has been rather heated over the years.

Many people think of Bayesian reasoning in science to be a model of ideal inference. As long as you give it the reasonable prior probabilities, or evidence that overwhelms the prior, you get the correct answer. If the Bayesian model does not share ones priors and there is little evidence, then you should not listen to it: GIGO.

I'll skip over the difficulty concerning giving probabilities to mathematical statements.

The practical reality preventing combining probabilities of lots arguments...

I think the main reason people don't try the approach you mention is that assigning probability to a bunch of arguments and then concluding from those probabilities (a) doesn't convince anyone and (b) is quite hard. I'll explain this further, but first I should say that the argument from the 2014 article is a very simple one

Whatever your “naïve prior probability” was that P=NP, the above considerations, together with Bayes’ Rule, suggest revising it downward.

which could be summarised as "we weren't sure but then we tried really hard to find a counter example, not finding one should only make us more sure there isn't one". Or, as long as someone thinks N=NP being true would increase the chance of finding an example of P=NP (most people would accept this), then according to Bayesian reasoning not finding examples (when you have tried to) should reduce their belief in P=NP.

More formally, this would require a prior, P(X) (where X is the statement P=NP), and a posterior P(X|d) where d is the data from each attempt to find a counter-example. With everything I have said above, we have P(X|d) < P(X). To calculate this we need to know P(d|X) and P(not d|X).

But the combination of arguments requires a whole bunch of calculation which involves how much you believe each of the separate arguments (call them Y1, Y2, ...). The calculation in this case is of P(X|Y1,Y2,Y3,...), to work this out we'd need probabilities for all the combinatorial possibilities of Y1...YN and their negation, and these would all have to be judged individually, and might be very hard to assign these probabilities.

The argument in the 2014 article only required an the widely acceptable statement that "N=NP being true increases the chance of finding an example of P=NP", the combination of many arguments requires one to provide estimates of the probability of every argument, and every interaction between arguments - pretty much everyone would disagree about the correct probabilities to at least some small extent.

One can think of it as an argument with many premises (or it is exactly that if you believe Jaynes) - the more there are the more likely it is that someone will disagree with one of them. Moreover as the degree of belief becomes important it becomes very unlikely that any two people will agree.

1

The "ideal agent" interpretation of Bayesian reasoning in science.

I thought I would add this answer, which is a more direct response to the title of the question:

How is Bayesian reasoning related to the scientific method?

Here is the story I've heard expressed by a number of scientists, statisticians, and at least one philosopher. It is certainly not the only interpretation available, but I consider it to be quite defensible. In it, Bayesian reasoning makes no claim to determining truth on its own, only to giving an all important "standard of evidence" to scientific field.

The story goes roughly as follows:

It's how it works: Bayesian reasoning is a good description of how judgements are made in science, in particular, it can be used to summarise most (if not all) statistical inferences. It is also consistent with classical logic.

It's how it should work: The way we make inferences using statistics is pretty much correct (though we might be making tacit assumptions. The argument is then that these hidden assumptions are made clearer by using Bayesian reasoning.)

and we can do it more formally: We can use mathematics to describe a fictional agent that does Bayesian inference, and allow it prior knowledge that accords with the standing assumptions of our field. We can then give it our data and see what conclusions it draws. As we have agreed on the agents prior knowledge, and agreed that it reasons correctly, then we should be agreed on the conclusions it makes.

Basically, we make a model of how we think we should think and use it to check that we are thinking in that way. Clearly this requires one to accept the validity of the statistical model. That choice is up to you, just like it's up to you to decide if p<0.1 is actually meaningful in any application of classical statistics.

As for how the agent actually combines probabilities once it has been given them a scientific community, that's just Bayes rule.

Note: In actual practice, actually choosing a prior is generally avoided (as people can disagree), and people only report how a prior would change (likelihood ratios etc). Some do use explicit priors, but only in some rather specific domains

  • I will have to think about this. I'm not sure that the issue I have with Scott's reasoning can be explained in terms of priors. I'm no longer sure whether multiple evidence that is not properly independent really helps much to reinforce a specific case. And I see that Scott was eager to claim the independence of the different examples he gave in his newest post, so this might be part of the real issue. – Thomas Klimpel Mar 27 '14 at 21:58
  • @ThomasKlimpel I just read the second article properly, I think I should mention this: "Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false." - this makes him sound more like an error statistician than a Bayesian. His rant about frogs also makes me think this. The error/severity approach suggests a very different relationship between science and statistics. Perhaps if you want to understand what Scott might be getting at you should be looking at Deborah Mayo's website errorstatistics.com – Lucas Mar 27 '14 at 23:45
  • Note in the discussion under question there is the idea that they should start from a prior probability of P=NP being about 1/2 (look up "max entropy prior" for why 1/2) -- doing this is a way of constructing the problem so that both sides need to spell out what "observations" change their beliefs away from this neutral starting position, i.e. spelling out the tacit assumptions referred to in this answer. – Dave Mar 28 '14 at 14:56
  • @Dave Exactly, the max ent guys are the first group that comes to mind when I think of people using explicit priors. – Lucas Mar 28 '14 at 15:07
0

Hypotheses should not be assigned probabilities. There are a number of problems with trying to assign such probabilities. A theory is either right or wrong so it's a bit difficult to say what it means to say that a theory has a probability of 0.5, say. If it is just about some subjective feeling you have about it, why would that matter?

Epistemology is about how knowledge can be created. If you're tying to create new ideas you don't know what you're going to end up with, so what you have to do is propose guesses and then try to eliminate them by critical discussion. The role that probabilities can play in this is that if an idea predicts the wrong probabilities that is a criticism of that theory. No probabilities are assigned to theories themselves.

Another problem is that if you were to assign probabilities to theories what explains how you assign the probabilities? If it is, say, some physical theory then how do you assign probabilities to that theory? In reality, any such theory would have to be a guess and so all you really know is that the theories to which you have assigned probabilities are also guesses.

There are other problems. For example, Arrow's theorem and similar mathematical results raise problems for any process that purports to make decisions by weighing ideas rather than criticising them.

See "Realism and the Aim of Science" by Karl Popper and "The Beginning of Infinity" by David Deutsch, especially Chapter 13.

  • 2
    Aha. Some more propaganda in the Bayesian/Frequentist war! It's great that you have an opinion, but this is exactly what makes people confused about the topic. – Lucas Mar 27 '14 at 13:31
  • I'm not a frequentist. See vimeo.com/5490979 Nor does anything I said entail frequentism. – alanf Mar 27 '14 at 13:34
  • 1
    Arrow's Theorem does not apply to the Bayesian model/approach since Bayesian approaches provide a cardinal utility function. – Dave Mar 27 '14 at 13:48
  • 1
    @alanf I just looked up "Arrow's theorem" in wikipedia upon reading your answer, and also came to the conclusion that it doesn't apply to Bayesian reasoning. Also note that my doubts were not related to using Bayesian probabilities in general, but to try to subsume all the Bayesian probabilies for different facts like that N=NP would be very surprising, or that N!=NP explains many observed facts, or that P!=NP is extremely useful into a single Bayesian probability that P!=NP is true. – Thomas Klimpel Mar 27 '14 at 14:58
  • 1
    Say, for the sake of argument, that everyone decided how to vote according to how much money they will get over the next year, a Bayesian approach (as I understand Dave interprets it - it's a highly overloaded term) would be to work out how much money everyone thinks they'll get in total and use the choice that gave them the most (money being a cardinal utility) - there would be no dispute. Arrow's theorem arises because each voter only ranks the candidates, discarding information about how much better each candidate is, making it impossible to calculate an expected utility. – Lucas Mar 27 '14 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.