# Computing Divergences between Discrete Decomposable Models

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 30 references that are in the map.
- First posted on arXiv 8 Dec 2021.

## Builds on (most cited first, 4 of 4)

- [f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization](https://mlsanity.com/paper/1606.00709/) (2016)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [R'enyi Divergence Variational Inference](https://mlsanity.com/paper/1602.02311/) (2016)
- [Detecting Regions of Maximal Divergence for Spatio-Temporal Anomaly Detection](https://mlsanity.com/paper/1804.07091/) (2018)

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

- [The alpha-beta divergence for real and complex data](https://mlsanity.com/paper/2508.03272/) (2025)
- [Computing Marginal and Conditional Divergences between Decomposable Models with Applications](https://mlsanity.com/paper/2310.09129/) (2023)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)

## Abstract (arXiv)

There are many applications that benefit from computing the exact divergence between 2 discrete probability measures, including machine learning. Unfortunately, in the absence of any assumptions on the structure or independencies within these distributions, computing the divergence between them is an intractable problem in high dimensions. We show that we are able to compute a wide family of functionals and divergences, such as the alpha-beta divergence, between two decomposable models, i.e. chordal Markov networks, in time exponential to the treewidth of these models. The alpha-beta divergence is a family of divergences that include popular divergences such as the Kullback-Leibler divergence, the Hellinger distance, and the chi-squared divergence. Thus, we can accurately compute the exact values of any of this broad class of divergences to the extent to which we can accurately model the two distributions using decomposable models.