Fast method estimates differences between complex probability models
Total Variation Distance Estimation through Domain Reduction
Data Structures and Algorithms
Summary
Comparing two complex probability models can be extremely difficult, especially when they cover many variables. The authors develop a practical algorithm that can quickly approximate how different these models are when they come from certain structured types, like mixtures of simpler models. They do this by cleverly reducing the problem to smaller, manageable pieces without losing accuracy. This method works efficiently even for high-dimensional models and more complicated probabilistic circuits.
What this means in practice
- •For machine learning engineers: Efficiently quantify differences between probabilistic models composed of many simple components to validate or improve complex models.
- •For data scientists: Rapidly approximate distance between high-dimensional structured distributions for tasks like anomaly detection or model comparison.
Authors
Arnab Bhattacharyya, Graham Cormode, Yucheng Fu, Kuldeep S. Meel
Abstract
Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance between mixtures of product distributions and, more generally, for a natural class of structured probabilistic circuits. Our main technique is a novel application of domain reduction: Given a family of feature vectors indexed by assignments, we use Lewis-weight sampling to replace the assignment domain by a polynomial-size weighted subset that simultaneously approximates the sum of absolute values of every linear projection. For mixtures of product distributions, we construct such reduced domains incrementally over the coordinates, obtaining the first FPRAS with running time polynomial in both the dimension and the number of mixture components. We then extend the approach to smooth, deterministic, structured-decomposable probabilistic circuits with a common structured architecture.