Scott Garrabrant

Research Papers

Logical Uncertainty

Logical Inductionwith Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, and Jessica Taylor, preprint

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 it 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).

Uniform Coherencewith Benya Fallenstein, Abram Demski, and Nate Soares, preprint

While probability theory is normally applied to external environments, there has been some recent interest in probabilistic modeling of the outputs of computations that are too expensive to run. Since mathematical logic is a powerful tool for reasoning about computer programs, we consider this problem from the perspective of integrating probability and logic. Recent work on assigning probabilities to mathematical statements has used the concept of coherent distributions, which satisfy logical constraints such as the probability of a sentence and its negation summing to one. Although there are algorithms which converge to a coherent probability distribution in the limit, this yields only weak guarantees about finite approximations of these distributions. In our setting, this is a significant limitation: Coherent distributions assign probability one to all statements provable in a specific logical theory, such as Peano Arithmetic, which can prove what the output of any terminating computation is; thus, a coherent distribution must assign probability one to the output of any terminating computation. To model uncertainty about computations, we propose to work with approximations to coherent distributions. We introduce uniform coherence, a strengthening of coherence that provides appropriate constraints on finite approximations, and propose an algorithm which satisfies this criterion.

Asymptotic Convergence in Online Learning with Unbounded Delayswith Nate Soares and Jessica Taylor, preprint

We study the problem of predicting the results of computations that are too expensive to run, via the observation of the results of smaller computations. We model this as an online learning problem with delayed feedback, where the length of the delay is unbounded, which we study mainly in a stochastic setting. We show that in this setting, consistency is not possible in general, and that optimal forecasters might not have average regret going to zero. However, it is still possible to give algorithms that converge asymptotically to Bayes-optimal predictions, by evaluating forecasters on specific sparse independent subsequences of their predictions. We give an algorithm that does this, which converges asymptotically on good behavior, and give very weak bounds on how long it takes to converge. We then relate our results back to the problem of predicting large computations in a deterministic setting.

Asymptotic Logical Uncertainty and The Benford Testwith Tsvi Benson-Tilsen, Siddharth Bhaskar, Abram Demski, Joanna Garrabrant, George Koleszarik, and Evan Lloyd, Paper presented at the Ninth Conference on Artificial General Intelligence.

Almost all formal theories of intelligence suffer from the problem of logical omniscience, the assumption that an agent already knows all consequences of its beliefs. Logical uncertainty codifies uncertainty about the consequences of existing beliefs. This implies a departure from beliefs governed by standard probability theory. Here, we study the asymptotic properties of beliefs on quickly computable sequences of logical sentences. Motivated by an example we call the Benford test, we provide an approach which identifies when such subsequences are indistinguishable from random, and learns their probabilities.

Computational Combinatorics

Pattern avoidance is not P-recursivewith Igor Pak, preprint

Let F ⊂ S_k be a finite set of permutations and let C_n(F) denote the number of permutations σ ∈ S_n avoiding the set of patterns F. The Noonan-Zeilberger conjecture states that the sequence {C_n(F)} is P-recursive. We disprove this conjecture.

Words in Linear Groups, Random Walks, Automata and P-Recursivenesswith Igor Pak, preprint, To appear in the inaugural issue of the Journal of Combinatorial Algebra.

Fix a finite set S ⊂ GL(k, Z). Denote by a_n the number of products of matrices in S of length n that are equal to 1. We show that the sequence {a_n} is not always P-recursive. This answers a question of Kontsevich.

Counting with Irrational Tileswith Igor Pak, preprint

We introduce and study the number of tilings of unit height rectangles with irrational tiles. We prove that the class of sequences of these numbers coincides with the class of diagonals of N-rational generating functions and a class of certain binomial multisums. We then give asymptotic applications and establish connections to hypergeometric functions and Catalan numbers.

Using TPA to Count Linear Extensionswith Jacqueline Banks, Mark Huber and Anne Perizzolo, preprint

A linear extension of a poset P is a permutation of the elements of the set that respects the partial order. Let L(P) denote the number of linear extensions. It is a #P complete problem to determine L(P) exactly for an arbitrary poset, and so randomized approximation algorithms that draw randomly from the set of linear extensions are used. In this work, the set of linear extensions is embedded in a larger state space with a continuous parameter β. The introduction of a continuous parameter allows for the use of a more efficient method for approximating L(P) called TPA. Our primary result is that it is possible to sample from this continuous embedding in time that as fast or faster than the best known methods for sampling uniformly from linear extensions. For a poset containing n elements, this means we can approximate L(P) to within a factor of 1+ε with probability at least 1−δ using an expected number of random bits and comparisons in the poset which is at most O(n³(ln n)(ln L(P))²ε⁻²ln δ⁻¹).

Combinatorial Game Theory

Cofinite Induced Subgraphs of Impartial Combinatorial Games: An Analysis of CIS-Nimwith Eric Friedman and Adam Landsberg, Integers 13, 2013

Given an impartial combinatorial game G, we create a class of related games (CIS- G) by specifying a finite set of positions in G and forbidding players from moving to those positions (leaving all other game rules unchanged). Such modifications amount to taking cofinite induced subgraphs (CIS) of the original game graph. Some recent numerical/heuristic work has suggested that the underlying structure and behavior of such “CIS-games” can shed new light on, and bears interesting relationships with, the original games from which they are derived. In this paper we present an analytical treatment of the cofinite induced subgraphs associated with the game of (three-heap) Nim. This constitutes one of the simplest nontrivial cases of a CIS game. Our main finding is that although the structure of the winning strategies in games of CIS-Nim can differ greatly from that of Nim, CIS-Nim games inherit a type of period-two scale invariance from the original game of Nim.

Knot Theory

Upper Bounds in the Ohtsuki-Riley-Sakuma Partial Order on 2-Bridge Knotswith Jim Hoste and Patrick Shanahan, J. Knot Theory and Ramifications 21, No.9, 2012

In this paper we use continued fractions to study a partial order on the set of 2-bridge knots derived from the work of Ohtsuki, Riley, and Sakuma. We establish necessary and sufficient conditions for any set of 2-bridge knots to have an upper bound with respect to the partial order. Moreover, given any 2-bridge knot K₁ we characterize all other 2-bridge knots K₂ such that {K₁,K₂} has an upper bound. As an application we answer a question of Suzuki, showing that there is no upper bound for the set consisting of the trefoil and figure-eight knots.

Invited Talks

Recent Progress on the Noonan-Zeilberger ConjectureAMS Sectional Meeting, Georgetown University, March 7, 2015

Counting with Irrational TilesSimon Fraser University, September 16, 2014

Counting with Irrational Tiles (UCLA Advancement To Candidacy)UCLA, February 4, 2014

Cofinite Induced Subgraph NimRutgers University, October 4, 2012 (Part 1, Part 2)Claremont Colleges, April 19, 2011

Teaching

UCLA Math 167, Mathematical Game TheorySummer 2014Summer 2013

UCLA Math 61, Introduction to Discrete StructuresSummer 2013Spring 2013Winter 2013

UCLA Math 3C, Probability for Life Sciences StudentsWinter 2015Summer 2014Fall 2012