Sean O’Riordain writes:
Your article, “The holes in my philosophy of Bayesian data analysis” caused me to wonder whether it was possible to have a consistent philosophy of data analysis and whether it could it be possible that Godel’s incompleteness theorem extends as far as to say that it wasn’t possible?
I don’t know but my guess is that this is all related to our lack of a good model for hypothesis generation. Statistics focuses on deductive inference within models and model checking to evaluate models, but we don’t have a good handle on the creation of models. (I’m hoping that some of our network-of-models stuff will be helpful.)
I don’t think Godel’s incompleteness theorem would say that a consistent philosophy was not possible. But, it seems to me that it might say that a consistent philosophy is not provable because the theorem is all about what true theorems can or can not be proven (based on my recollection from graduate school 20 years ago).
Gödel’s incompletness theorem applies to all mathematical endeavors. In essence it says that if you have a consistent set of axioms, there are statements which must be true but are not provable within whatever your axiom set is. This isn’t particularly interesting for data analysis, where we don’t even have a way to prove that the scientific method of observing things and assuming that the future is enough like the past that explanations for our past observations may be explanatory for future observations. Logically speaking it’s entirely possible that quantum mechanics will cease to explain physical reality starting next tuesday at 11 AM.
If a philosophy (of data analysis in this instance) could be thought of as a set of statements and axioms, then surely Gödel’s incompletness theorem could apply. In this case, there are statements that must be true but are not provable within that axiom set and conversely that the set of axioms is not consistent with itself. So the question really comes down to – can a philosophy of data analysis be (hypothetically) written down as a set of statements and axioms?
“…can a philosophy of data analysis be (hypothetically) written down as a set of statements and axioms?”
No. ;-)
Andrew: You want a model of statistical hypothesis generation? Or scientific hypothesis generation? It’s hard for me to imagine a good model of the former (though I admit I’m entirely ignorant of your network-of-models work), and I can’t imagine we’ll ever have a good model of the latter (which doesn’t mean we don’t know anything about it, of course).
There are models for the generation of scientific hypotheses, for instance Gold’s identification in the limit, and it’s possible to build toy machine learning systems on the back of it. That said I think it’s hard to shoehorn statistical learning in there – and of course you might disagree that it’s a good model.
Goedel’s incompleteness results show that there are (uncountably many) true arithmetical statements that are not provable within formal systems of arithmetic. This shows some in principle limitations of finitary formal systems of arithmetic, but at the same time entails that humans are in this sense “smarter” than formal systems: we can recognize claims as true (about system S) informally that are not provable within a formalism of S. These true statements are therefore metatruths, so we have the development of metalogic (after Goedel)as a way to obtain true statements about formal systems (metatruths). The very notions of algorithmic and computable remain intuitive and informal: humans grasp them, while they are not reducible to mathematical formulations (at least not provably so).
I don’t see a connection with data analysis (but I don’t know the author’s paper). Fortunately, statistics is not limited to deductive entailments, or rather, any account that is limited to deductive entailments (e..g, if A and B, then A) is irrelevant to gaining empirical knowledge or to learning about the world. (It’s purely analytic, not synthetic). I don’t think anyone would be bothering to do applied statistics if they thought that gathering data failed to warrant claims that go beyond the data. I realize there’s an enormous amount of confusion regarding the nature of induction vs deduction (as I know from teaching logic for years and years).
A conjecture: just as Heisenberg’s uncertainty principle is valid at the atomic level but has no meaning at the human level, perhaps Godel’s incompleteness theorem is true at the philosophical level but not at the computational level. Besides, statisticians just estimate stuff anyway. :-)
Didn’t C.S.Peirce have something to say about this? He saw a triumvirate of deduction, induction, and “abduction.” Abduction pertained (roughly) to creative hypothesis generation, inter alia.
(Despite his mathematical abilities, I gather Peirce’s work in this area was frankly conjectural and thoroughly philosophical.)
Yes he did, but even was not fully convinced by it – roughly that humans had evolved to be good at abduction (making productive scientific hypotheses).
But he was also a statistician, both practicing and theoretical.
Unfortunately he never wrote up anything comprehensive on his work so its a real struggle to get him “right” or suggest to others what to read to get a good sense of that.
I always thought that since probabilistic inference is an extension of logic (see Jaynes, etc), Goedel’s incompleteness theorem implies that there are probabilities that cannot be computed.
While Goedel’s theorem talks about statements that are either tautological or contradictory, i.e., have probability one or zero, independently of contingent facts about the world, there are also statements whose probability is neither zero or one and whose probability cannot be computed without additional knowledge.
In any case, I don’t see this as a serious problem in probabilistic (Bayesian) inference, just like people are quite comfortable applying predicate logic despite Goedel’s result.
There are probabilities that are uncomputable. For example, Chaitin’s Constant is more or less the probability that a randomly chosen computer program of n bits length will halt, which is uncomputable in general. see: http://en.wikipedia.org/wiki/Chaitin's_constant
However, those probabilities are not probabilities over real events, they’re purely theoretical. The incompleteness theorem doesn’t really cause much in the way of problems for everyday mathematics.
I agree fully on both points: Chaitin’s ‘Omega’ is a prime example of an incomputable probability; and I have never heard of a situation where incomputability is really a practical concern.
Yikes! The comments are so full of misrepresentations of Gödel’s incompleteness theorem and its consequences that I fear everyone skimmed Gödel, Escher, Bach rather than studying Boolos and Jeffrey’s classic, Computability and Logic. (Boolos and Jeffrey reduce the incompleteness theorem to the halting problem, making it easier for us computer scientists.)
The proofs all rely on the unprovability one way or the other of liar-paradox-type assertions (i.e., “this sentence is false”). Gödel originally used something like “this statement cannot be proven”, which he coded along with axiomatic logic in arithmetic. The halting problem uses the same idea for computation given the deep link between computation and logic (specifically, the arithmetic system Gödel presupposes in his proof is powerful enough to encode Turing machines as well as axiomatic systems). The incompleteness that arises is that “this statement cannot be proven” can’t be derived as either true or false in a consistent system (a reductio ad absurdum argument, and hence non-constructive, like other “diagonalization” results), thus the resulting system is incomplete (meaning it doesn’t assign truth values to all statements).
What the original correspondent, Sean O’Riordain, was getting at is the deep connection between computation/logic/set theory and the philosophical notion of randomness and information developed by Solomonoff/Kolmogorov/Chaitin in the 1960s. The Li and Vitanyi book is the standard reference, though it really presupposes you already understand Gödel, probability theory, information theory, and axiomatic set theory, and the theory of computation (the connections truly are deep). The coolest part is that it gives you a universal theory of randomness, now known as Kolmogorov complexity, which solves the sensitivity to representation of standard information theory a la Shannon. If you thought Kolmogorov’s application of measure theory to modeling probability was cool, it’s nothing compared to his universal theory of information.
It is true that Goedel uses a statement, call it G, akin to “this statement cannot be proven” but the brilliant part that moves it far away from any of these semantic paradoxes is arithmetization. Let “G-#” abbreviate Goedel number. Formulas (wffs) and (finite) sets of formulas each get a corresponding G-#. The C formula thereby becomes arithmetical statement:
C: There is no number that is the G-# of a proof of the wff whose G-# is y.
C also has a G-#, call it k. Then “diagonalize”, i.e., instantiate, substituting y with k, giving the G formula:
G: for all x, it’s not the case that x is the G-# of a proof of the wff whose G-# is k.
that’s how G says about itself “there’s no proof of me”.
So, if there is a proof of G, then there’s no proof of G.
and
If there’s no proof of G, then there’s a proof of G.
contradiction.
Rather than studying Boolos and Jeffrey’s, which I actually don’t like, study Goedel’s little “On formally undecidable props in PM and Related Systems”. A very long time ago I wrote an undergraduate honor’s thesis in math on Goedel’s theorem, and turned it into a kind of “authentic Goedel, simplified” after years of trying to make it clear enough to my metalogic class to actually put on a final.
I almost certainly wrote the above too quickly, and it is too late for one who is sleep deprived—but you get the gist.
I’m truly sorry about the language in my post. I shouldn’t be so flippant and dismissive of anyone. Yours (MAYO) was the one comment that was on the right track. I really liked your short-form version of the proof in arithmetic in the followup, too — that gets at the heart of the matter a bit more concretely than I was doing.
I have to disagree about Boolos and Jeffrey, though. After going through several math logic book proofs which rely heavily on properties of induction in axiomatizations of arithmetic, I found the reduction to the halting problem was much easier to follow. It actually seems like a better conceptual basis for most people than axiomatic arithmetic: we can’t write a computer program (always in the Church-Turing sense in this argument) that can tell if any other computer program (encoded for the first program) and input (also encoded for the first program) will terminate.
The problem is that we can’t improve our lot by stacking on meta logics. That is, there’s no computable (again in the Church-Turing sense, not the generalized transfinite recursion sense) meta-logic of computation where the halting problem can be solved by a computer (in the Church-Turing sense). You can add transfinite recursion, and get a meta-logic that handles the halting problem, but that meta-logic’s no longer computable in the Church-Turing sense.
If you like logic and stats, you should definitely follow up on Kolmogorov complexity. It’s a nice, simple idea, but the math involved is pretty complex even for someone at my level (I was an undergrad math major and I took math logic, set theory, topology, analysis and measure theory, and lots of theory of comuptation, and I did a lot of domain theory in grad school and my first academic career — now that I know stats and information theory much better, I should give Li and Vitanyi another whirl).
I don’t see how human intelligence enters the equation. It’s not like we can compute the halting problem where the computers can’t. At least I’ve never seen a demonstration that we can.
Bob:
Of course that was just a snippet from the simple but non-distorting sketch of Goedel’s incompleteness results; I figured if people wanted to see more, they would ask.
Boolos and Jeffrey is OK, I just don’t think it produces a deep understanding of the Goedel results, as opposed to a way to sort of state it without much logical formalism. It’s also too cute for me. I prefer formulations closer to Goedel’s and to related metalogical results.
The point isn’t that we compute what the (idealized) computers can’t, but rather that we can ascertain the truth of claims (about a formal system) that are not formally provable within (finitary) formalisms of that system.
Bob:
> I shouldn’t be so flippant and dismissive of anyone. Yours (MAYO) was *the one* comment that was on the right track.
(emphasis added)
That’s rather funny (although perhaps not intentionally). I mean, talking about contradictions…