Bayesian Intractability Is Not an Ailment That Approximation Can Cure

The popularity of probabilistic (Bayesian) modeling is growing in cognitive science as evidenced by an increase in the number of articles, conference papers, symposia, and workshops on the topic.1 The popularity of the Bayesian modeling framework can be understood as a natural outflow of its success in producing models that describe and predict a wide variety of cognitive phenomena in domains ranging from vision (Yuille & Kersten, 2006), categorization (Anderson, 1990; Griffiths, Sanborn, Canini, & Navarro, 2008), decision making (Sloman & Hagmayer, 2006), and language learning (Chater & Manning, 2006; Frank, Goodman, & Tenenbaum, 2009) to motor control (Körding & Wolpert, 2004, 2006) and theory of mind (Baker, Saxe, & Tenenbaum, 2009). Notwithstanding the empirical success of the Bayesian framework, models formulated within this framework are known to often face the theoretical obstacle of computational intractability. Formally, this means that computations that are postulated by many Bayesian models of cognition fall into the general class of so-called NP-hard problems. Informally, this means that the computations postulated by such models are too resource demanding to be plausibly performed by our resource-bounded minds/brains in a realistic amount of time for all but small inputs.2 NP-hard problems are problems with the property that they can be solved only by super-polynomial time algorithms.3 Such algorithms require an amount of time which cannot be upper bounded by any polynomial function nc (where n is a measure of the input size and c is some constant). Examples are exponential-time algorithms, which require a time that can, at best, be upper bounded by some exponential function cn. To see that such algorithms consume an excessive amount of time, even for medium input size, consider that 225 is more than the number of seconds in a year and 235 is more than the seconds in a millennium. To the extent that the cognitive abilities that Bayesian models aim to describe operate on a time scale of seconds or minutes, computations requiring on the order of years or centuries for their completion are inevitably explanatorily unsatisfactory, no matter how well the models may fit human performance data obtained in the laboratory. Opponents of Bayesian modeling Gigerenzer, Hoffrage, and Goldstein have put it as follows:4 The computations postulated by a model of cognition need to be tractable in the real world in which people live, not only in the small world of an experiment with only a few cues. This eliminates NP-hard models that lead to computational explosion such as probabilistic inference using Bayesian belief networks (...)(Gigerenzer, Hoffrage, & Goldstein, 2008, p. 236) Bayesian modelers seem to be aware that their models often face the theoretical charge of intractability. Yet we observe that they seem eager to downplay the real challenge posed by ‘‘intractability’’ and are quick to claim that—despite the intractability of exact algorithms—Bayesian computations can be efficiently approximated using inexact algorithms (see, e.g., Chater et al., 2006; Sanborn et al., 2010). Although we agree that human minds/brains likely implement all kinds of inexact or quick-and-dirty algorithms, in this letter we wish to draw attention to the fact that this assumption alone is insufficient for Bayesian modelers to guarantee tractability of their models. The reason is, simply put, that intractable Bayesian computations are not generally tractably approximable. This is not to say, of course, that cognitive algorithms do not approximate Bayesian computations, but rather to claim that approximation by itself cannot guarantee tractability. With this letter, we wish to communicate two important points with the cognitive science community: First, current claims of tractable approximability of intractable (Bayesian) models in the cognitive science are mathematically unfounded and often provably unjustified. Second, there are a variety of complexity-theoretic tools available that Bayesian modelers can use to assess the (in)tractability of their models in a mathematically sound way. To make our points, we will use a widely adopted—see, for example, Baker et al., (2009), Chater and Manning (2006), Yuille and Kersten (2006)—subcomputation of cognitive Bayesian models as an illustrative example: probabilistic abduction, a.k.a. most probable explanation (MPE). In brief, this computation is defined by the following input–output mapping: Most Probable Explanation (MPE) Input: A set of hypotheses H, a set of observations E, and a knowledge structure K encoding the probabilistic dependencies between observations, hypotheses, and possibly intermediate variables (e.g., K could be a Bayesian network). Output: A truth assignment for each hypothesis in H with the largest possible conditional probability over all such assignments (more formally, argmaxT(H)PrK(T(H)|E) where T is a function T:H→{true, false}). The computational complexity of MPE has been extensively studied in the computer science literature. Not only is it known that computing MPE is NP-hard (Shimony, 1994), but it is also known that ‘‘approximating’’ MPE—in the sense of computing a truth assignment that has close to maximal probability—is NP-hard (Abdelbar & Hedetniemi, 1998). An even more sobering result is that it has been proven NP-hard to compute a truth assignment with a conditional probability of at least q for any value 0 < q < 1 (Kwisthout, 2010). Importantly, such inapproximability results hold not only for MPE but also for many other computations postulated in Bayesian models. For instance, computations known to be NP-hard to approximate include Bayesian inference (Dagum & Luby, 1993; Sanborn et al., 2010), Bayesian decision making (Schachter, 1986, 1988; Vul, Goodman, Griffiths, & Tenenbaum, 2009), Bayesian planning (Körding & Wolpert, 2006; Littman, Goldsmith, & Mundhenk, 1998), and Bayesian learning (Chickering, 1996; Kemp & Tenenbaum, 2008). Computational complexity results such as these show that claims in the cognitive science literature about the tractable approximability of intractable Bayesian computations are not generally warranted. We realize that our message may seem counterintuitive from the perspective of the algorithmic-level modeler who implements probabilistic or randomized algorithms for approximating Bayesian computations and who may find that such algorithms may run quite fast and perform quite well. The paradox can be understood as a mismatch between the generality of the (intractable) computational-level Bayesian models and the (tractable) algorithms implemented for ‘‘approximating’’ the postulated input–output mappings. The algorithms will run fast and perform well only for a proper subset of input domains, viz., those domains for which the computation (exact or approximate) is tractable. A general methodology for identifying restricted domains of inputs for which otherwise intractable computations are tractable is available (Blokpoel, Kwisthout, van der Weide, & van Rooij, 2010; van Rooij, 2008; van Rooij & Wareham, 2008; van Rooij, Evans, Müller, Gedge, & Wareham, 2008) and builds on the mathematical theory of parameterized complexity (Downey & Fellows, 1999). Parameterized complexity theory is motivated by the observation that some NP-hard problems can be computed by algorithms whose running time is polynomial in the overall input size n and nonpolynomial only in some small aspect of the input called the input parameter.5 To illustrate, consider a Bayesian network as input structure for some Bayesian cognitive model C. Such a network has many parameters, each of which may have restricted values for the presumed domain of application. For instance, networks may have nodes with at most k1 incoming connections, or at most k2 outgoing connections, or a diameter of at most k3, or a network density of at most k4, or at most k5 independent layers, or consists of at most k6 independent subnetworks, or has node variables with at most k7 different possible values, or have a treewidth (a measure of treelikeness) of at most k8, etc. Observe that even if the computation C is NP-hard, it may still be computable in a time that is nonpolynomial only as function of one or more such parameters k ∈ {k1,k2,k3,…}, and polynomial in the rest of the input size. In those cases, as long as k is relatively small (e.g., much smaller than the size of the entire network), the computation of C may be performed quite fast even for large Bayesian networks. Using proof techniques from parameterized complexity theory, computer scientists have already been able to show that if the knowledge structure underlying MPE is a Bayesian network with a relatively small treewidth (for details on this special, constrained form of connectivity, see Bodlaender, 1997), and with relatively few possible values for each variable in the network, then computing MPE is tractable (Kwisthout, 2009, 2010; Nilsson, 1998). This means that for all cognitive domains in which such special connectivity and restricted cardinality can be assumed (e.g., psychologically and/or ecologically motivated), then the Bayesian computation MPE is no longer intractable, and approximation algorithms can tractably approximate that computation. Importantly, the tractability is achieved not by giving up on the ‘‘exactness’’ of the postulated computations, but by explicating that the modeled processes operate on domains defined by restricted parameter ranges. In closing, we wish to emphasize that our purpose is certainly not to downgrade Bayesian models of cognition or to argue that the challenge of making such models tractable cannot be met. On the contrary, we see great potential for Bayesian models to help advance the field of cognitive science and we hope to contribute to this by sharing our observations and pointing to a mathematically sound methodology for making Bayesian models tractable. Given that Bayesian modeling is now an accepted framework for approaching cognition, we think the time is ripe to start thinking seriously about the scalability of these models to real-world scenarios. In doing so, we believe that the Bayesian modeling community can (and should) display the same mathematical and scientific rigor as they have in probabilistic modeling and statistical testing. Making mathematically unfounded claims of efficient approximability of intractable Bayesian computations is not the way to move forward.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.