TY - GEN
T1 - A compositional atlas of tractable circuit operations for probabilistic inference
AU - Vergari, Antonio
AU - Choi, Yoo Jung
AU - Liu, Anji
AU - Teso, Stefano
AU - Van den Broeck, Guy
PY - 2021/12/6
Y1 - 2021/12/6
N2 - Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning—from computing the expectations of decision tree ensembles to information-theoretic divergences of sum-product networks—can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of simple transformations—sums, products, quotients, powers, logarithms, and exponentials—in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.
AB - Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning—from computing the expectations of decision tree ensembles to information-theoretic divergences of sum-product networks—can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of simple transformations—sums, products, quotients, powers, logarithms, and exponentials—in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.
UR - http://www.scopus.com/inward/record.url?scp=85128522017&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85128522017
VL - 34
T3 - Advances in Neural Information Processing Systems
SP - 13189
EP - 13201
BT - Advances in Neural Information Processing Systems 34 (NeurIPS 2021)
A2 - Ranzato, Marc'Aurelio
A2 - Beygelzimer, Alina
A2 - Dauphin, Yann
A2 - Liang, Percy S.
A2 - Wortman Vaughan, Jenn
PB - Neural Information Processing Systems Foundation (NeurIPS)
T2 - 35th Conference on Neural Information Processing Systems
Y2 - 6 December 2021 through 14 December 2021
ER -