TY - JOUR
AU - Lee, Loong Kuan
AU - Piatkowski, Nico
AU - Petitjean, François
AU - Webb, Geoffrey I.
PY - 2023/06/26
Y2 - 2024/09/11
TI - Computing Divergences between Discrete Decomposable Models
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 37
IS - 10
SE - AAAI Technical Track on Reasoning Under Uncertainty
DO - 10.1609/aaai.v37i10.26443
UR - https://ojs.aaai.org/index.php/AAAI/article/view/26443
SP - 12243-12251
AB - 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.
ER -