提出衡量多样性的三个基本准则，发现现有方法均不满足。
Measuring Diversity: Axioms and Challenges
- 定义多样性度量的单调性、唯一性与连续性三原则
- 证明现有方法均不满足全部准则，且构造出理论可行但计算昂贵的反例
- 公开挑战：能否设计出实用且满足三准则的度量方法
本文研究如何对一组对象的多样性进行量化。首先系统回顾现有多样性度量方法，揭示其在某些情形下的不良行为。基于此，提出三个理想的性质（公理）：单调性、唯一性和连续性。我们证明，现有的所有度量方法都不具备全部三个性质，因此不适用于可靠地量化多样性。随后，构造了两个满足所有性质的度量例子，证明该公理集并非自相矛盾。然而，这些构造方法计算复杂度极高（NP-hard），无法实际应用。因此，本文提出一个开放问题：能否构造出既满足全部公理又可在实际中计算的多样性度量，或证明所有此类度量都为NP-hard。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。