# On Tractable Computation of Expected Predictions

arXiv: https://arxiv.org/abs/1910.02182 · HTML: https://mlsanity.com/paper/1910.02182/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2019.

## Built on by (most cited first, 19 of 19)

- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Probabilistic Sufficient Explanations](https://mlsanity.com/paper/2105.10118/) (2021)
- [Sparse Probabilistic Circuits via Pruning and Growing](https://mlsanity.com/paper/2211.12551/) (2022)
- [Semantic Strengthening of Neuro-Symbolic Learning](https://mlsanity.com/paper/2302.14207/) (2023)
- [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024)
- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation](https://mlsanity.com/paper/2504.18535/) (2025)
- [A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries](https://mlsanity.com/paper/2102.06137/) (2021)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Irregularly-Sampled Time Series Modeling with Spline Networks](https://mlsanity.com/paper/2210.10630/) (2022)
- [Tractable Computation of Expected Kernels](https://mlsanity.com/paper/2102.10562/) (2021)
- [A Quantum Information Theoretic Approach to Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01824/) (2025)
- [REASON: Accelerating Probabilistic Logical Reasoning for Scalable Neuro-Symbolic Intelligence](https://mlsanity.com/paper/2601.20784/) (2026)
- [A Probabilistic Circuit-Induced Pseudo-Metric for Out-of-Distribution Detection](https://mlsanity.com/paper/2608.09117/) (2026)
- [Grab a Coffee: Future-Aware Guidance for Discrete Diffusion with Compiled Objectives](https://mlsanity.com/paper/2609.35924/) (2026)

## Abstract (arXiv)

Computing expected predictions of discriminative models is a fundamental task in machine learning that appears in many interesting applications such as fairness, handling missing values, and data analysis. Unfortunately, computing expectations of a discriminative model with respect to a probability distribution defined by an arbitrary generative model has been proven to be hard in general. In fact, the task is intractable even for simple models such as logistic regression and a naive Bayes distribution. In this paper, we identify a pair of generative and discriminative models that enables tractable computation of expectations, as well as moments of any order, of the latter with respect to the former in case of regression. Specifically, we consider expressive probabilistic circuits with certain structural constraints that support tractable probabilistic inference. Moreover, we exploit the tractable computation of high-order moments to derive an algorithm to approximate the expectations for classification scenarios in which exact computations are intractable. Our framework to compute expected predictions allows for handling of missing data during prediction time in a principled and accurate way and enables reasoning about the behavior of discriminative models. We empirically show our algorithm to consistently outperform standard imputation techniques on a variety of datasets. Finally, we illustrate how our framework can be used for exploratory data analysis.