Bregman-Hausdorff divergence: strengthening the connections between computational geometry and machine learning
This work strengthens connections between computational geometry and machine learning by providing a new tool for model comparison, though it is incremental as it builds on existing divergences and algorithms.
The paper introduces the Bregman-Hausdorff divergence, an extension of the Hausdorff distance to asymmetric Bregman divergences like Kullback-Leibler, and demonstrates its application in efficiently comparing probabilistic predictions from machine learning models, with algorithms handling large inputs in hundreds of dimensions.
The purpose of this paper is twofold. On a technical side, we propose an extension of the Hausdorff distance from metric spaces to spaces equipped with asymmetric distance measures. Specifically, we focus on the family of Bregman divergences, which includes the popular Kullback--Leibler divergence (also known as relative entropy). As a proof of concept, we use the resulting Bregman--Hausdorff divergence to compare two collections of probabilistic predictions produced by different machine learning models trained using the relative entropy loss. The algorithms we propose are surprisingly efficient even for large inputs with hundreds of dimensions. In addition to the introduction of this technical concept, we provide a survey. It outlines the basics of Bregman geometry, as well as computational geometry algorithms. We focus on algorithms that are compatible with this geometry and are relevant for machine learning.