Fast Exact Inference for Recursive Cardinality Models

Daniel Tarlow, Kevin Swersky, Richard S. Zemel, Ryan Prescott Adams, Brendan J. Frey

Introduction

Probabilistic graphical models (PGMs) are powerful tools for representing complex distributions, but their utility is often limited by the computational cost of inference. A particularly challenging class of constraints involves cardinality potentials—high-order functions that depend on the number of active variables in a set. These are essential for modeling real-world requirements, such as ensuring a document contains a specific number of keywords or that a reviewer is assigned a fixed number of papers. While finding the most likely configuration (MAP inference) for these models is relatively efficient, performing exact marginalization and sampling has historically been prohibitively slow, scaling cubically ($O(D^3)$) with the number of variables $D$.

The Recursive Cardinality Framework

This paper introduces Recursive Cardinality (RC) models, a framework that enables exact inference for nested high-order constraints. The core requirement for this efficiency is "nestedness": subsets of variables must either be disjoint or one must be a complete subset of the other. This structure allows the model to be represented as a hierarchy, where constraints at one level do not conflict with the boundaries of constraints at another.

Comparison of nested and non-nested variable subsets. Nestedness is the structural requirement that enables the construction of an efficient auxiliary tree for inference.

To perform inference, the authors transform these high-order potentials into a tree-structured model using auxiliary variables ($z$). Each auxiliary node in the tree represents the sum of its children, effectively "counting" the active variables in its subtree. By the time the message reaches the root of the tree, it represents the total count of all active binary variables in the model, allowing global cardinality constraints to be treated as simple unary potentials.

FFT-Accelerated Belief Propagation

Even with an auxiliary tree, standard belief propagation remains slow because the messages passed between nodes are probability distributions over counts. Combining two such messages typically requires a nested loop, resulting in a computational bottleneck.

The authors' key insight is that the operation to combine these count-based messages is mathematically equivalent to a discrete convolution. By leveraging Fast Fourier Transforms (FFTs), they can perform these convolutions in $O(N \log N)$ time. This optimization reduces the overall complexity of exact marginalization from $O(D^3 \log D)$ to $O(D \log^2 D)$, a dramatic improvement that makes large-scale exact inference feasible.

Experimental Results

The proposed "FFT Tree" algorithm was evaluated against standard "Chain" and "Tree" baselines using synthetic and real-world datasets. The results demonstrate a massive leap in scalability. As shown in the runtime analysis, the FFT Tree algorithm maintains near-linear scaling, successfully processing models with 500,000 variables in under 100 seconds. In contrast, previous state-of-the-art chain-based methods failed due to memory constraints at just 16,000 variables.

Runtime scaling of the FFT Tree algorithm compared to standard tree and chain methods. The FFT-based approach enables exact inference on problems orders of magnitude larger than previously possible.

Beyond speed, the RC model proved superior in practical applications:

  • Multiple Instance Learning (MIL): On the Musk dataset, using a "Normal" (Gaussian-like) cardinality potential provided more flexibility than the standard Noisy-OR model, leading to better classification performance.
  • Generative Modeling: When applied to image data, the RC model captured long-range, high-order statistics that standard pairwise tree models missed, producing more realistic synthetic samples.

Conclusion and Future Work

By bridging the gap between graphical models and signal processing, this work provides a path toward exact inference in massive-scale systems with complex counting constraints. While the current framework requires a nested structure, future research may focus on automatically learning these structures from data or extending the FFT acceleration to overlapping, non-nested constraints.

Summary updated

Abstract

Cardinality potentials are a generally useful class of high order potential that affect probabilities based on how many of D binary variables are active. Maximum a posteriori (MAP) inference for cardinality potential models is well-understood, with efficient computations taking O(DlogD) time. Yet efficient marginalization and sampling have not been addressed as thoroughly in the machine learning community. We show that there exists a simple algorithm for computing marginal probabilities and drawing exact joint samples that runs in O(Dlog2 D) time, and we show how to frame the algorithm as efficient belief propagation in a low order tree-structured model that includes additional auxiliary variables. We then develop a new, more general class of models, termed Recursive Cardinality models, which take advantage of this efficiency. Finally, we show how to do efficient exact inference in models composed of a tree structure and a cardinality potential. We explore the expressive power of Recursive Cardinality models and empirically demonstrate their utility.
BibTeX
@inproceedings{tarlow2012fast,
  author = {Daniel Tarlow and Kevin Swersky and Richard S. Zemel and Ryan Prescott Adams and Brendan J. Frey},
  title = {{Fast Exact Inference for Recursive Cardinality Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
  url = {https://openreview.net/forum?id=UN1kWzylhXY},
}
Figure