Measuring Diversity: Axioms and Challenges

Mikhail Mironov, Liudmila Prokhorenkova
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:44396-44411, 2025.

Abstract

This paper addresses the problem of quantifying diversity for a set of objects. First, we conduct a systematic review of existing diversity measures and explore their undesirable behavior in certain cases. Based on this review, we formulate three desirable properties (axioms) of a reliable diversity measure: monotonicity, uniqueness, and continuity. We show that none of the existing measures has all three properties and thus these measures are not suitable for quantifying diversity. Then, we construct two examples of measures that have all the desirable properties, thus proving that the list of axioms is not self-contradictory. Unfortunately, the constructed examples are too computationally expensive (NP-hard) for practical use. Thus, we pose an open problem of constructing a diversity measure that has all the listed properties and can be computed in practice or proving that all such measures are NP-hard to compute.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-mironov25a, title = {Measuring Diversity: Axioms and Challenges}, author = {Mironov, Mikhail and Prokhorenkova, Liudmila}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {44396--44411}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/mironov25a/mironov25a.pdf}, url = {https://proceedings.mlr.press/v267/mironov25a.html}, abstract = {This paper addresses the problem of quantifying diversity for a set of objects. First, we conduct a systematic review of existing diversity measures and explore their undesirable behavior in certain cases. Based on this review, we formulate three desirable properties (axioms) of a reliable diversity measure: monotonicity, uniqueness, and continuity. We show that none of the existing measures has all three properties and thus these measures are not suitable for quantifying diversity. Then, we construct two examples of measures that have all the desirable properties, thus proving that the list of axioms is not self-contradictory. Unfortunately, the constructed examples are too computationally expensive (NP-hard) for practical use. Thus, we pose an open problem of constructing a diversity measure that has all the listed properties and can be computed in practice or proving that all such measures are NP-hard to compute.} }
Endnote
%0 Conference Paper %T Measuring Diversity: Axioms and Challenges %A Mikhail Mironov %A Liudmila Prokhorenkova %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-mironov25a %I PMLR %P 44396--44411 %U https://proceedings.mlr.press/v267/mironov25a.html %V 267 %X This paper addresses the problem of quantifying diversity for a set of objects. First, we conduct a systematic review of existing diversity measures and explore their undesirable behavior in certain cases. Based on this review, we formulate three desirable properties (axioms) of a reliable diversity measure: monotonicity, uniqueness, and continuity. We show that none of the existing measures has all three properties and thus these measures are not suitable for quantifying diversity. Then, we construct two examples of measures that have all the desirable properties, thus proving that the list of axioms is not self-contradictory. Unfortunately, the constructed examples are too computationally expensive (NP-hard) for practical use. Thus, we pose an open problem of constructing a diversity measure that has all the listed properties and can be computed in practice or proving that all such measures are NP-hard to compute.
APA
Mironov, M. & Prokhorenkova, L.. (2025). Measuring Diversity: Axioms and Challenges. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:44396-44411 Available from https://proceedings.mlr.press/v267/mironov25a.html.

Related Material