The Random Conditional Distribution for Higher-Order Probabilistic Inference.

Zenna Tavares, Xin Zhang, Edgar Minaysan, Javier Burroni, Rajesh Ranganath, Armando Solar-LezamaarXiv 2019 · OpenReview

In the world of probabilistic programming, we are used to treating data as random variables. We can model the weather, predict stock prices, or estimate the bias of a coin. But what if we want to talk about the properties of those distributions themselves? What if we want to find a model that is "fair" (where the probability of an outcome is equal across groups) or "robust" (where the expected error is low even under attack)?

Traditionally, properties like expectation, variance, and entropy are treated as fixed values calculated after a model is defined. The paper "The Random Conditional Distribution for Higher-Order Probabilistic Inference" by Zenna Tavares and colleagues argues that this is a missed opportunity. They introduce a new mathematical construct and a programming language, Omega, that treats these distributional properties as random variables in their own right.

TL;DR

The authors introduce the random conditional distribution (rcd), a higher-order random variable that allows probabilistic programs to treat distributional properties (like mean or variance) as first-class citizens. This enables researchers to condition models on complex constraints like algorithmic fairness or adversarial robustness with just a few lines of code.

What Problem Does This Paper Address?

Standard probabilistic programming languages (PPLs) have a "blind spot." They are great at defining random variables and conditioning them on observed data. However, they struggle when you want to condition on a distributional property.

For example, in algorithmic fairness, you might want to ensure that the probability of a positive outcome for a minority group is close to that of a majority group. In a standard PPL, this probability is a fixed number derived from the model; it isn't a "random variable" you can easily manipulate. To solve this today, engineers often have to manually split their models and write complex, nested inference loops—a process that is error-prone and violates the principle that models should be separate from the queries we run on them.

Methods

The core innovation is the random conditional distribution (rcd), denoted as $X \parallel \Theta$.

  • Higher-Order Logic: An rcd is a "random distribution"—a random variable whose realizations are themselves conditional random variables.
  • Pointwise Extension: The authors extend standard operators like mean, variance, and entropy to work on these rcds. Instead of returning a single number, mean(X || Θ) returns a distribution over means.
  • The Omega Language: The authors built Omega, a functional PPL that implements the || operator as a primitive. It uses measure-theoretic foundations to ensure that these higher-order constructs are mathematically well-defined.
  • Likelihood-Free Inference: Because conditioning on properties like "entropy" often results in intractable likelihoods, Omega uses a sophisticated likelihood-free inference engine. It transforms predicates into "energy functions" and uses a variant of replica exchange Markov Chain Monte Carlo (MCMC) to find valid samples.

Datasets

The researchers evaluated Omega using:

  1. Synthetic Benchmarks: A suite of models (Rainfall, Alarm, Gauss) designed to test how easily a language can express changes in distributional queries.
  2. Adult Income Dataset: A standard machine learning dataset from the UCI repository used for the two main case studies:
  3. Fairness: Training a Support Vector Machine (SVM) to predict income while satisfying "equality of opportunity" constraints.
  4. Robustness: Improving a neural network's resilience against adversarial attacks.

Key Insights and Ideas

  • Properties are Contingent: The "aha moment" is realizing that distributional properties are not static. The "expected rainfall" is a fixed value for a whole year, but it becomes a random variable if you consider it contingent on the season or the presence of clouds.
  • Minimal Syntax, Maximum Power: By making the rcd a primitive, Omega allows users to express complex "what-if" scenarios without rewriting the generative model. You define the world once and then query its properties flexibly.
  • Type Safety for Probability: The paper frames the inability of current PPLs to condition on means as a "type error." By expanding the type system to include higher-order random variables, they bridge the gap between statistical theory and programming practice.

Key Results

The authors compared Omega to WebPPL, a popular modern PPL. As shown in Figure 5, Omega drastically reduces the effort required to modify models for higher-order queries.

Figure 5. Empirical comparison of lines of code
  • Expressiveness: In WebPPL, changing a distributional query required roughly 30 lines of manual model restructuring. In Omega, it required exactly one line.
  • Fairness Case Study: Omega successfully took an "unfair" SVM and generated fair versions of it in just 30 seconds.
  • Robustness Case Study: The team used Omega to improve a neural network's robustness against the Fast Gradient Sign Method (a common adversarial attack). The baseline network was resilient to 97% of attacks; the Omega-conditioned version improved this to an average of 98.8% in 86 seconds.

Limitations and Future Work

While powerful, the approach has clear hurdles:

  • Computational Cost: Higher-order inference is inherently expensive. While 30-90 seconds is fast for these case studies, scaling to massive deep learning models remains a challenge.
  • Approximation: The inference relies on sampling to estimate properties like the mean. This means the constraints (like fairness) are satisfied approximately, not perfectly.
  • Language Maturity: The current version of Omega is a research prototype. The authors note it lacks features like user-defined polymorphic types, which would be necessary for a production-grade language.

Future work involves developing more efficient inference algorithms specifically tuned for the "energy functions" generated by distributional constraints.

Summary updated

Abstract

The need to condition distributional properties such as expectation, variance, and entropy arises in algorithmic fairness, model simplification, robustness and many other areas. At face value however, distributional properties are not random variables, and hence conditioning them is a semantic error and type error in probabilistic programming languages. On the other hand, distributional properties are contingent on other variables in the model, change in value when we observe more information, and hence in a precise sense are random variables too. In order to capture the uncertain over distributional properties, we introduce a probability construct -- the random conditional distribution -- and incorporate it into a probabilistic programming language Omega. A random conditional distribution is a higher-order random variable whose realizations are themselves conditional random variables. In Omega we extend distributional properties of random variables to random conditional distributions, such that for example while the expectation a real valued random variable is a real value, the expectation of a random conditional distribution is a distribution over expectations. As a consequence, it requires minimal syntax to encode inference problems over distributional properties, which so far have evaded treatment within probabilistic programming systems and probabilistic modeling in general. We demonstrate our approach case studies in algorithmic fairness and robustness.
BibTeX
@misc{tavares2019random,
  author = {Zenna Tavares and Xin Zhang and Edgar Minaysan and Javier Burroni and Rajesh Ranganath and Armando Solar-Lezama},
  title = {{The Random Conditional Distribution for Higher-Order Probabilistic Inference.}},
  year = {2019},
  eprint = {1903.10556},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.10556},
}
Figure