Measuring Diversity: Axioms and Challenges
This work addresses a foundational issue in measuring diversity, which is crucial for fields like machine learning and data analysis, but it is incremental as it builds on prior measures and highlights computational challenges.
The paper tackles the problem of quantifying diversity for sets of objects by reviewing existing measures, identifying their flaws, and proposing three desirable axioms (monotonicity, uniqueness, continuity). It shows that no existing measure satisfies all axioms, constructs two NP-hard examples to prove feasibility, and poses an open problem for a practical solution.
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.