Abstract
The problem of replicating the flexibility of human common-sense reasoning has captured the imagination of computer scientists since the early days of Alan Turing's foundational work on computation and the philosophy of artificial intelligence. In the intervening years, the idea of cognition as computation has emerged as a fundamental tenet of Artificial Intelligence (AI) and cognitive science. But what kind of computation is cognition? We describe a computational formalism centered around a probabilistic Turing machine called QUERY, which captures the operation of probabilistic conditioning via conditional simulation. Through several examples and analyses, we demonstrate how the QUERY abstraction can be used to cast common-sense reasoning as probabilistic inference in a statistical model of our observations and the uncertain structure of the world that generated that experience. This formulation represents a surprising convergence of several of Turing's pioneering insights in AI, the foundations of computation, and statistics.
1. Introduction
In his landmark paper Computing Machinery and Intelligence (1950), Alan Turing predicted that by the end of the twentieth century, “general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted.” Even if Turing has not yet been proven right, the idea of cognition as computation has emerged as a fundamental tenet of Artificial Intelligence (AI) and cognitive science. But what kind of computation—what kind of computer program—is cognition?
Despite the success of "brute-force" AI in specific domains like chess, machines still lack the flexible common-sense reasoning that humans use to navigate the world. We can make "inductive leaps"—predicting the future or diagnosing a cause from sparse, noisy data—in ways that traditional rule-based AI cannot. This paper seeks a formal language that can describe how a system learns from experience, manages uncertainty, and makes complex, sequential decisions.
2. The QUERY Abstraction
The centerpiece of this framework is the QUERY abstraction, built upon Probabilistic Turing Machines (PTMs). PTMs are standard Turing machines equipped with a source of independent random bits, allowing them to model stochastic processes.
QUERY takes two inputs:
- A Prior Program ($P$): A generative model (a PTM) that describes a process in the world.
- A Conditioning Predicate ($C$): A set of observations or constraints (another PTM).
The semantics of QUERY involve conditional simulation: conceptually, the machine runs the prior program repeatedly until it finds an execution that satisfies the predicate, then returns that sample. This process captures the mathematical operation of Bayesian conditioning. The authors extend this to Hierarchical Bayesian Models, where QUERY learns parameters and causal structures from historical data, and Recursive Decision Making, where optimal actions are defined self-referentially.
3. Illustrative Model: Medical Diagnosis
To demonstrate the QUERY abstraction, the paper utilizes a toy medical diagnosis model (referred to as "DS"). This model includes 11 diseases and 7 symptoms, with parameters (marginal probabilities and symptom rates) fabricated for illustrative purposes.
While not a real-world benchmark, this model serves as a stand-in for complex diagnostic systems like QMR-DT. It demonstrates how the QUERY abstraction handles "explaining away"—where discovering one cause for a symptom makes other potential causes less likely—and structure learning.
4. Key Insights and Results
The paper synthesizes several of Turing’s legacies—foundations of computation, wartime statistics (the "weight of evidence"), and biological morphogenesis—into modern probabilistic AI. Key insights include:
- Reasoning as Simulation: Common-sense reasoning is cast as simulating the world and "filtering" for simulations that match observations.
- Bayesian Occam's Razor: The framework naturally favors simpler models over complex ones when data is limited, an emergent property of marginal likelihoods.
- Unified Planning: Reinforcement learning and planning are cast as probabilistic inference by conditioning on the event of "future success."
- Structure Learning:
QUERYcan distinguish between independent and dependent variables by accumulating "weight of evidence" from data.
5. Limitations and Future Work
While the QUERY abstraction provides an elegant formalism, several challenges remain:
- Efficiency: Rejection sampling is computationally "intractable" for real-world problems. Bridging the gap between formalism and efficient execution (e.g., via MCMC) is a major research frontier.
- Continuous Conditioning: Conditioning on exact values in continuous spaces is often non-computable; adding "noise" to measurements is a suggested workaround.
- Model Invention: The framework does not yet explain how a mind "invents" brand-new conceptual models from scratch, a hallmark of human scientific reasoning.
Summary updated