Bayesian Intractability Is Not an Ailment That Approximation Can Cure

Cognitive Science 35 (5):779-784 (2011)
  Copy   BIBTEX


Bayesian models are often criticized for postulating computations that are computationally intractable (e.g., NP-hard) and therefore implausibly performed by our resource-bounded minds/brains. Our letter is motivated by the observation that Bayesian modelers have been claiming that they can counter this charge of “intractability” by proposing that Bayesian computations can be tractably approximated. We would like to make the cognitive science community aware of the problematic nature of such claims. We cite mathematical proofs from the computer science literature that show intractable Bayesian computations, such as postulated in existing Bayesian models, cannot be tractably approximated. This does not mean that human brains do not (or cannot) implement the type of algorithms that Bayesian modelers are advancing, but it does mean that proposing that they do by itself does nothing to parry the charge of intractability, because the postulated algorithms are as intractable (i.e., require exponential time) as the computations they try to approximate. Besides our negative message for the community, our letter also makes a positive contribution by referring to a methodology that Bayesian modelers can use to try and parry the charge of intractability in a mathematically sound way



    Upload a copy of this work     Papers currently archived: 84,361

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

60 (#219,167)

6 months
1 (#513,269)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Iris van Rooij
Radboud University Nijmegen

Citations of this work

Being Realist about Bayes, and the Predictive Processing Theory of Mind.Matteo Colombo, Lee Elkin & Stephan Hartmann - 2021 - British Journal for the Philosophy of Science 72 (1):185-220.
Subjective Probability as Sampling Propensity.Thomas Icard - 2016 - Review of Philosophy and Psychology 7 (4):863-903.
Bayesian Cognitive Science, Monopoly, and Neglected Frameworks.Matteo Colombo & Stephan Hartmann - 2015 - British Journal for the Philosophy of Science 68 (2):451–484.

View all 22 citations / Add more citations

References found in this work

Simple Heuristics That Make Us Smart.Gerd Gigerenzer, Peter M. Todd & A. B. C. Research Group - 1999 - New York, NY, USA: Oxford University Press USA. Edited by Peter M. Todd.
Probabilistic models of cognition: Conceptual foundations.Nick Chater & Alan Yuille - 2006 - Trends in Cognitive Sciences 10 (7):287-291.
Vision as Bayesian inference: analysis by synthesis?Alan Yuille & Daniel Kersten - 2006 - Trends in Cognitive Sciences 10 (7):301-308.

View all 16 references / Add more references