Approximating Inconsistency at Scale in Probabilistic Dependency Graphs

We deliver significantly more performant algorithms and implementations for approximating the inconsistency of probabilistic dependency graphs (PDGs), a general problem that unifies and interpolates between many important problems in probabilistic modeling and machine learning. Previous methods are either unreliable (first-order optimizers with ad-hoc constraint penalties) or prohibitively expensive (second-order optimizers and convex solvers) for all but the smallest of PDGs. We provide the first sampling-based approach for this problem, combining a score-function gradient estimator with Rao-Blackwellization to optimize over parameterized Bayesian networks. Empirically, our method scales to substantially larger and more complex PDGs than existing approaches can handle. Our approach also naturally permits variational approximations of inconsistency, allowing the choice of Bayesian-network structure to trade computational efficiency for the tightness of the resulting upper bound.