Logical Induction

By Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor. 2016

40 citations recorded by the source corpus.

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running computations, and its own probabilities. We show that our algorithm, an instance of what we call a logical inductor, satisfies a number of intuitive desiderata, including: (1) it learns to predict patterns of truth and falsehood in logical statements, often long before having the resources to evaluate the statements, so long as the patterns can be written down in polynomial time; (2) it learns to use appropriate statistical summaries to predict sequences of statements whose truth values appear pseudorandom; and (3) it learns to have accurate beliefs about its own current beliefs, in a manner that avoids the standard paradoxes of self-reference. For example, if a given computer program only ever produces outputs in a certain range, a logical inductor learns this fact in a timely manner; and if late digits in the decimal expansion of π are difficult to predict, then a logical inductor learns to assign ≈ 10% probability to “the nth digit of π is a 7” for large n. Logical inductors also learn to trust their future beliefs more than their current beliefs, and their beliefs are coherent in the limit (whenever φ → ψ, P∞(φ) ≤ P∞(ψ), and so on); and logical inductors strictly dominate the universal semimeasure in the limit. These properties and many others all follow from a single logical induction criterion, which is motivated by a series of stock trading analogies. Roughly speaking, each logical sentence φ is associated with a stock that is worth $1 per share if φ is true and nothing otherwise, and we interpret the belief-state of a logically uncertain reasoner as a set of market prices, where Pn(φ) = 50% means that on day n, shares of φ may be bought or sold from the reasoner for 50¢. The logical induction criterion says (very roughly) that there should not be any polynomial-time computable trading strategy with finite risk tolerance that earns unbounded profits in that market over time. This criterion bears strong resemblance to the “no Dutch book” criteria that support both expected utility theory (von Neumann and Morgenstern 1944) and Bayesian probability theory (Ramsey 1931; de Finetti 1937).

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistics and Probability

In Program Analysis & Verification

Tom Everitt

Citations in the corpus

Scalable agent alignment via reward modeling: a research direction (2018, background): “Yet while there has been some of progress on this research agenda (Barasz et al., 2014; Leike et al., 2016; Garrabrant et al., 2016; Everitt, 2018), some questions turned out to be quite difﬁcult.”
Eliciting Latent Predictions from Transformers with the Tuned Lens (2023, unknown): “Even when the logit lens is useful, we find that it is a biased estimator of the model’s final output: it systematically puts more probability mass on certain vocabulary items than the final layer does.”
The alignment problem from a deep learning perspective (2022, background): “Thirdly, unlike ideal Bayesian reasoners, real-world agents face uncertainty about the implications of their beliefs [Garrabrant et al., 2016].”
Embedded Agency (2019, background): “This is one of the ideas behind Garrabrant et al.’s (2016) “Logical Induction”, an early attempt at developing an analog for Solomono ﬀ induction that incorporates mathematical uncertainty.”
AGI Safety Literature Review (2018, methodology): “. Importantly, probability theory assumes that agents know all the logical consequences of their beliefs (Gaifman, 2004). An impressive model of logical non-omniscience has recently been developed by Garrabrant et al. (2016, 2017). Notably, Garrabrant’s theory avoids Godelian obstacles for agents re”
Towards Safe Artificial General Intelligence (2018, methodology): “Garrabrant et al.’s (2016, 2017) theory of logical induction leads to several theorems about systems reasoning about their own computations in a consistent manner, avoiding Gödelian and Löbian obstacles. Fallenstein and Kumar (2015) shows that systems of higher-order logic can learn to trust their o”