Todd D. Millstein

UAI Conference 2023 Conference Paper

Scaling integer arithmetic in probabilistic programs

• William X. Cao
• Poorva Garg
• Ryan Tjoa
• Steven Holtzen
• Todd D. Millstein
• Guy Van den Broeck

Distributions on integers are ubiquitous in probabilistic modeling but remain challenging for many of today’s probabilistic programming languages (PPLs). The core challenge comes from discrete structure: many of today’s PPL inference strategies rely on enumeration, sampling, or differentiation in order to scale, which fail for high-dimensional complex discrete distributions involving integers. Our insight is that there is structure in arithmetic that these approaches are not using. We present a binary encoding strategy for discrete distributions that exploits the rich logical structure of integer operations like summation and comparison. We leverage this structured encoding with knowledge compilation to perform exact probabilistic inference, and show that this approach scales to much larger integer distributions with arithmetic.

UAI Conference 2019 Conference Paper

Generating and Sampling Orbits for Lifted Probabilistic Inference

• Steven Holtzen
• Todd D. Millstein
• Guy Van den Broeck

A key goal in the design of probabilistic inference algorithms is identifying and exploit- ing properties of the distribution that make inference tractable. Lifted inference algorithms identify symmetry as a property that enables efficient inference and seek to scale with the degree of symmetry of a probability model. A limitation of existing exact lifted inference techniques is that they do not apply to non- relational representations like factor graphs. In this work we provide the first example of an exact lifted inference algorithm for arbitrary discrete factor graphs. In addition we describe a lifted Markov-Chain Monte-Carlo algorithm that provably mixes rapidly in the degree of symmetry of the distribution.

ICML Conference 2018 Conference Paper

Sound Abstraction and Decomposition of Probabilistic Programs

• Steven Holtzen
• Guy Van den Broeck
• Todd D. Millstein

Probabilistic programming languages are a flexible tool for specifying statistical models, but this flexibility comes at the cost of efficient analysis. It is currently difficult to compactly represent the subtle independence properties of a probabilistic program, and exploit independence properties to decompose inference. Classical graphical model abstractions do capture some properties of the underlying distribution, enabling inference algorithms to operate at the level of the graph topology. However, we observe that graph-based abstractions are often too coarse to capture interesting properties of programs. We propose a form of sound abstraction for probabilistic programs wherein the abstractions are themselves simplified programs. We provide a theoretical foundation for these abstractions, as well as an algorithm to generate them. Experimentally, we also illustrate the practical benefits of our framework as a tool to decompose probabilistic program inference.

UAI Conference 2017 Conference Paper

Probabilistic Program Abstractions

• Steven Holtzen
• Todd D. Millstein
• Guy Van den Broeck

Abstraction is a fundamental tool for reasoning about complex systems. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of program abstraction is the relationship between a concrete program, which is difficult to analyze, and an abstract program, which is more tractable. Program abstractions, however, are typically not probabilistic. We generalize non-deterministic program abstractions to probabilistic program abstractions by explicitly quantifying the non-deterministic choices. Our framework upgrades key definitions and properties of abstractions to the probabilistic context. We also discuss preliminary ideas for performing inference on probabilistic abstractions and general probabilistic programs.

I&C Journal 2004 Journal Article

Bounded similarity querying for time-series data

• Dina Q. Goldin
• Todd D. Millstein
• Ayferi Kutlu

We define the problem of bounded similarity querying in time-series databases, which generalizes earlier notions of similarity querying. Given a (sub)sequence S, a query sequence Q, lower and upper bounds on shifting and scaling parameters, and a tolerance ϵ, S is considered boundedly similar to Q if S can be shifted and scaled within the specified bounds to produce a modified sequence S′ whose distance from Q is within ϵ. We use similarity transformation to formalize the notion of bounded similarity. We then describe a framework that supports the resulting set of queries; it is based on a fingerprint method that normalizes the data and saves the normalization parameters. For off-line data, we provide an indexing method with a single index structure and search technique for handling all the special cases of bounded similarity querying. Experimental investigations find the performance of our method to be competitive with earlier, less general approaches.

IJCAI Conference 1997 Conference Paper

Automatic SAT-Compilation of Planning Problems

• Michael D. Ernst
• Todd D. Millstein
• Daniel S. Weld