# The Sum-Product Theorem: A Foundation for Learning Tractable Models

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2016.

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

- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Characteristic Circuits](https://mlsanity.com/paper/2312.07790/) (2023)
- [Dynamic programming by polymorphic semiring algebraic shortcut fusion](https://mlsanity.com/paper/2107.01752/) (2021)
- [To be Continuous, or to be Discrete, Those are Bits of Questions](https://mlsanity.com/paper/2406.07812/) (2024)
- [Tractable Computation of Expected Kernels](https://mlsanity.com/paper/2102.10562/) (2021)
- [Quantum Algorithms for Weighted Constrained Sampling and Weighted Model Counting](https://mlsanity.com/paper/2407.12816/) (2024)
- [The Gradient of Algebraic Model Counting](https://mlsanity.com/paper/2502.18406/) (2025)
- [Maximum margin learning of t-SPNs for cell classification with filtered input](https://mlsanity.com/paper/2303.09065/) (2023)

## Abstract (arXiv)

Inference in expressive probabilistic models is generally intractable, which makes them difficult to learn and limits their applicability. Sum-product networks are a class of deep models where, surprisingly, inference remains tractable even when an arbitrary number of hidden layers are present. In this paper, we generalize this result to a much broader set of learning problems: all those where inference consists of summing a function over a semiring. This includes satisfiability, constraint satisfaction, optimization, integration, and others. In any semiring, for summation to be tractable it suffices that the factors of every product have disjoint scopes. This unifies and extends many previous results in the literature. Enforcing this condition at learning time thus ensures that the learned models are tractable. We illustrate the power and generality of this approach by applying it to a new type of structured prediction problem: learning a nonconvex function that can be globally optimized in polynomial time. We show empirically that this greatly outperforms the standard approach of learning without regard to the cost of optimization.