{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T17:18:22Z","timestamp":1771521502175,"version":"3.50.1"},"reference-count":53,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T00:00:00Z","timestamp":1748217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"2022 Google Research Scholar program awarded for project \u201cAlgorithms for Topological Analysis of Neural Networks\u201d","award":["524578210"],"award-info":[{"award-number":["524578210"]}]},{"name":"DFG Project","award":["524578210"],"award-info":[{"award-number":["524578210"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["MAKE"],"abstract":"<jats:p>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 extending it to the family of Bregman divergences, which includes the popular Kullback\u2013Leibler divergence (also known as relative entropy). The resulting dissimilarity measure is called a Bregman\u2013Hausdorff divergence and compares two collections of vectors\u2014without assuming any pairing or alignment between their elements. We propose new algorithms for computing Bregman\u2013Hausdorff divergences based on a recently developed Kd-tree data structure for nearest neighbor search with respect to Bregman divergences. The algorithms are surprisingly efficient even for large inputs with hundreds of dimensions. As a benchmark, we use the new divergence to compare two collections of probabilistic predictions produced by different machine learning models trained using the relative entropy loss. In addition to the introduction of this technical concept, we provide a survey. It outlines the basics of Bregman geometry, and motivated the Kullback\u2013Leibler divergence using concepts from information theory. We also describe computational geometric algorithms that have been extended to this geometry, focusing on algorithms relevant for machine learning.<\/jats:p>","DOI":"10.3390\/make7020048","type":"journal-article","created":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T11:12:57Z","timestamp":1748344377000},"page":"48","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Bregman\u2013Hausdorff Divergence: Strengthening the Connections Between Computational Geometry and Machine Learning"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7379-4057","authenticated-orcid":false,"given":"Tuyen","family":"Pham","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7841-0091","authenticated-orcid":false,"given":"Hana","family":"Dal Poz Kou\u0159imsk\u00e1","sequence":"additional","affiliation":[{"name":"Applied Geometry and Topology, University of Potsdam, Am Neuen Palais 10, 14469 Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hubert","family":"Wagner","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,5,26]]},"reference":[{"key":"ref_1","unstructured":"Gray, R. (2013). Entropy and Information Theory, Springer."},{"key":"ref_2","unstructured":"Cover, T., and Thomas, J. (2012). Elements of Information Theory, Wiley."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_4","unstructured":"Kingma, D.P., and Welling, M. (2022). Auto-Encoding Variational Bayes. arXiv."},{"key":"ref_5","unstructured":"Pathria, R.K., and Beale, P.D. (2011). Statistical Mechanics, Academic Press. [3rd ed.]."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Amari, S.I. (2016). Information Geometry and Its Applications, Springer.","DOI":"10.1007\/978-4-431-55978-8"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","article-title":"The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming","volume":"7","author":"Bregman","year":"1967","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"ref_8","first-page":"27","article-title":"Legendre functions and the method of random Bregman projections","volume":"4","author":"Bauschke","year":"1997","journal-title":"J. Convex Anal."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T. (1970). Convex Analysis, Princeton University Press.","DOI":"10.1515\/9781400873173"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1109\/83.982822","article-title":"Wavelet-based texture retrieval using generalized Gaussian density and Kullback-Leibler distance","volume":"11","author":"Do","year":"2002","journal-title":"IEEE Trans. Image Process."},{"key":"ref_11","unstructured":"Itakura, F. (1968, January 21\u201328). Analysis synthesis telephony based on the maximum likelihood method. Proceedings of the 6th International Congress on Acoustics, Tokyo, Japan."},{"key":"ref_12","first-page":"49","article-title":"On the generalised distance in statistics","volume":"2","author":"Mahalanobis","year":"1936","journal-title":"Proc. Natl. Inst. Sci. India"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1111\/j.1467-985X.2005.00368_10.x","article-title":"Discriminant Analysis and Statistical Pattern Recognition","volume":"168","author":"Sapatinas","year":"2005","journal-title":"J. R. Stat. Soc. Ser. Stat. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Law, M.T., Yu, Y., Cord, M., and Xing, E.P. (2016, January 27\u201330). Closed-Form Training of Mahalanobis Distance for Supervised Clustering. Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, NV, USA.","DOI":"10.1109\/CVPR.2016.424"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/j.neucom.2016.06.039","article-title":"A dual-layer supervised Mahalanobis kernel for the classification of hyperspectral images","volume":"214","author":"Li","year":"2016","journal-title":"Neurocomputing"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Nock, R., and Nielsen, F. (2005). Fitting the Smallest Enclosing Bregman Ball. Machine Learning: ECML 2005, Springer.","DOI":"10.1007\/11564096_65"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s00454-010-9256-1","article-title":"Bregman Voronoi diagrams","volume":"44","author":"Boissonnat","year":"2010","journal-title":"Discret. Comput. Geom."},{"key":"ref_18","unstructured":"Nielsen, F. (2011). Chernoff information of exponential families. arXiv."},{"key":"ref_19","unstructured":"Edelsbrunner, H., Virk, \u017d., and Wagner, H. (2018, January 11\u201314). Smallest Enclosing Spheres and Chernoff Points in Bregman Geometry. Proceedings of the 34th International Symposium on Computational Geometry, Budapest, Hungary."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/LSP.2013.2243726","article-title":"An Information-Geometric Characterization of Chernoff Information","volume":"20","author":"Nielsen","year":"2013","journal-title":"IEEE Signal Process. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Nielsen, F. (2022). Revisiting Chernoff Information with Likelihood Ratio Exponential Families. Entropy, 24.","DOI":"10.3390\/e24101400"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","first-page":"1705","article-title":"Clustering with Bregman Divergences","volume":"6","author":"Banerjee","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"ref_24","first-page":"209","article-title":"\u00dcber die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen","volume":"1850","author":"Dirichlet","year":"1850","journal-title":"J. Pure Appl. Math. Crelles J."},{"key":"ref_25","first-page":"97","article-title":"Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. Premier m\u00e9moire. Sur quelques propri\u00e9t\u00e9s des formes quadratiques positives parfaites","volume":"1908","author":"Voronoi","year":"1908","journal-title":"J. Pure Appl. Math. Crelles J."},{"key":"ref_26","first-page":"198","article-title":"Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. Deuxi\u00e8me m\u00e9moire. Recherches sur les parall\u00e9llo\u00e8dres primitifs","volume":"1908","author":"Voronoi","year":"1908","journal-title":"J. Pure Appl. Math. Crelles J."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF02573985","article-title":"An optimal convex hull algorithm in any fixed dimension","volume":"10","author":"Chazelle","year":"1993","journal-title":"Discrete Comput. Geom."},{"key":"ref_28","unstructured":"Omohundro, S.M. (2025, May 12). Five Balltree Construction Algorithms. Available online: https:\/\/steveomohundro.com\/wp-content\/uploads\/2009\/03\/omohundro89_five_balltree_construction_algorithms.pdf."},{"key":"ref_29","unstructured":"Yianilos, P.N. (1993, January 25\u201327). Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Austin, TX, USA."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Cayton, L. (2008, January 5\u20139). Fast Nearest Neighbor Retrieval for Bregman Divergences. Proceedings of the 25th International Conference on Machine Learning, ICML \u201908, New York, NY, USA.","DOI":"10.1145\/1390156.1390171"},{"key":"ref_32","unstructured":"Nielsen, F., Piro, P., and Barlaud, M. (2009, January 16\u201318). Tailored Bregman ball trees for effective nearest neighbors. Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), Brussels, Belgium."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Nielsen, F., Piro, P., and Barlaud, M. (July, January 28). Bregman Vantage Point Trees for Efficient Nearest Neighbor Queries. Proceedings of the 2009 IEEE International Conference on Multimedia and Expo, (ICME), New York, NY, USA.","DOI":"10.1109\/ICME.2009.5202635"},{"key":"ref_34","unstructured":"Pham, T., and Wagner, H. (2025, January 11\u201315). Fast Kd-trees for the Kullback\u2013Leibler Divergence and other Decomposable Bregman Divergences. Proceedings of the 19th Algorithms and Data Structures Symposium (WADS 2025), Toronto, ON, Canada."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"13","DOI":"10.14778\/1687627.1687630","article-title":"Similarity Search on Bregman Divergence: Towards Non-Metric Indexing","volume":"2","author":"Zhang","year":"2009","journal-title":"Proc. VLDB Endow."},{"key":"ref_36","unstructured":"Song, Y., Gu, Y., Zhang, R., and Yu, G. (2020). BrePartition: Optimized High-Dimensional kNN Search with Bregman Distances. arXiv."},{"key":"ref_37","first-page":"280","article-title":"Engineering Efficient and Effective Non-metric Space Library","volume":"Volume 8199","author":"Brisaboa","year":"2013","journal-title":"Proceedings of the Similarity Search and Applications\u20146th International Conference, SISAP 2013"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","article-title":"Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs","volume":"42","author":"Malkov","year":"2020","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_39","unstructured":"Edelsbrunner, H., Letscher, D., and Zomorodian, A. (2000, January 12\u201314). Topological persistence and simplification. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","article-title":"Topology and data","volume":"46","author":"Carlsson","year":"2009","journal-title":"Bull. Amer. Math. Soc."},{"key":"ref_41","unstructured":"Edelsbrunner, H., and Wagner, H. (2017, January 4\u20137). Topological Data Analysis with Bregman Divergences. Proceedings of the 33th International Symposium on Computational Geometry (SoCG), Brisbane, Australia."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., and Harer, J. (2010). Computational Topology: An Introduction, American Mathematical Society.","DOI":"10.1090\/mbk\/069"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., \u00d6lsb\u00f6ck, K., and Wagner, H. (2024). Understanding Higher-Order Interactions in Information Space. Entropy, 26.","DOI":"10.3390\/e26080637"},{"key":"ref_44","unstructured":"Hausdorff, F. (1914). Grundz\u00fcge der Mengenlehre, Von Veit."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1109\/34.232073","article-title":"Comparing Images Using the Hausdorff Distance","volume":"15","author":"Huttenlocher","year":"1993","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Karimi, D., and Salcudean, S.E. (2019). Reducing the Hausdorff Distance in Medical Image Segmentation with Convolutional Neural Networks. arXiv.","DOI":"10.1109\/TMI.2019.2930068"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1111\/1467-8659.00236","article-title":"Metro: Measuring Error on Simplified Surfaces","volume":"17","author":"Cignoni","year":"1998","journal-title":"Comput. Graph. Forum"},{"key":"ref_48","first-page":"41","article-title":"Fast and Accurate Hausdorff Distance Calculation between Meshes","volume":"13","author":"Guthe","year":"2005","journal-title":"J. WSCG"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1162\/08997660460734047","article-title":"Divergence Function, Duality, and Convex Analysis","volume":"16","author":"Zhang","year":"2004","journal-title":"Neural Comput."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Nielsen, F., and Nock, R. (2009, January 23\u201326). The Dual Voronoi Diagrams with Respect to Representational Bregman Divergences. Proceedings of the 2009 Sixth International Symposium on Voronoi Diagrams, Copenhagen, Denmark.","DOI":"10.1109\/ISVD.2009.15"},{"key":"ref_51","unstructured":"Tan, M., and Le, Q. (2019, January 9\u201315). Efficientnet: Rethinking model scaling for convolutional neural networks. Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1093\/imamat\/24.1.59","article-title":"Nearest Neighbour Searches and the Curse of Dimensionality","volume":"24","author":"Marimont","year":"1979","journal-title":"IMA J. Appl. Math."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/502807.502808","article-title":"Searching in metric spaces","volume":"33","author":"Navarro","year":"2001","journal-title":"ACM Comput. Surv."}],"container-title":["Machine Learning and Knowledge Extraction"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2504-4990\/7\/2\/48\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:40:41Z","timestamp":1760031641000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2504-4990\/7\/2\/48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,26]]},"references-count":53,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["make7020048"],"URL":"https:\/\/doi.org\/10.3390\/make7020048","relation":{},"ISSN":["2504-4990"],"issn-type":[{"value":"2504-4990","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,26]]}}}