Measuring Diversity: Axioms and Challenges

Thank you for your feedback!

To confirm, do the authors believe that it is a reliable metric as long as these three properties are satisfied? My question is, how is a reliable diversity metric defined? Do related studies support it? Does a reliable diversity metric only need to satisfy these three properties, and are there no other properties that need to be satisfied?

In the paper, we only claim that a reliable measure has to satisfy these properties and explain why each property is needed. We do not say that if a measure satisfies all three of them, then it is necessarily good. It can be the case that some additional properties are desirable for a good measure of diversity (for instance, for specific applications there can be specific requirements). However, we could not come up with more properties that are undoubtedly desirable for a general measure. Also, we do observe that none of the existing measures has all the properties and thus even this set of axioms is hard to satisfy.

On line 78 of page 2, what is the range of i and j, and is there a size relationship?

In lines 76-78 we write the following: “We assume that we are given a collection of $n$ (possibly duplicated) objects $X=(x_1, \dots, x_n)$ and pairwise distances (dissimilarities) between them such that $d_{ij} \ge 0$ and $d_{ij} = 0$ iff $x_i$ and $x_j$ coincide.” It follows from the text above that the indices $i$ and $j$ are in the range $[1,n]$. Could you please clarify what you mean by size relationship?

On line 90 of page 2, what is the meaning of t? There is no explanation and no reference for it.

It is a parameter of the Circle measure (can be any positive value) and is used as a radius of circles, as explained in lines 91-93. We also refer to the corresponding paper in line 88.

On line 364 of page 7, what is the Equation (7)?

That is a typo, thanks for noticing. It should be Equation (2) instead (Equation (7) is the same expression, but in Appendix, page 12).

Some writing needs to be more clear. For example, on lines 78-79 of page 2, the authors say that, "For generality purposes, we do not require the triangle inequality to be satisfied by dij." No more explanations. I do not know why.

We could assume that the dissimilarities $d_{ij}$ between the elements are formal distances, i.e., satisfy all the axioms of a distance measure. However, all our theoretical results work in a more general case, when we do not require the triangle inequality. Thus, we do not limit our analysis and consider a more general setup. Also, note that our formal setup with all assumptions is described in lines 224-243.

Diversity is a scientific topic that has been studied for a long time, but the paper has only just a few references. It is recommended that the authors add references when introducing each comparative metric. Moreover, compare more diversity metrics, such as the Gini index, Coverage, etc.

If we adapt the Gini index to our setup, we get a diversity measure that is equivalent to Average. All variants of the Coverage metric that we are aware of require all elements to be embedded in some space over which we can iterate (or integrate). For instance, Coverage of a set in a space can be defined as a Maximal/Mean/Median distance to the closest point from the set, measured over all points of the space. Another definition of Coverage is that given a set of points in a space and a desired coverage radius $r$, we calculate the proportion of points of this space that are within a distance $r$ of at least one point from the set. Given only $n$ objects with pairwise distances, Coverage cannot be defined. For instance, even if texts (or graphs or other objects) are embedded in $\mathbb{R}^k$, we do not know which area of $\mathbb{R}^k$ corresponds to space of valid embeddings, and thus can not iterate (or integrate) over space of valid embeddings. If you could refer us to a variant of the Coverage metric that applies to our setup or if there are any other suitable measures we will be happy to add them to our analysis.

Thank you for pointing us to some typos, we will update the paper accordingly.

Thank you for the review and constructive feedback!

The paper would benefit from more extensive experiments that highlight the drawbacks of existing methods and demonstrate the necessity of the three proposed axioms. Such experiments would make the work more convincing.

Note that the proposed properties come with explanations of why they are required and with examples of measures that have undesirable behavior when not satisfying some of them. Also, for each previous diversity measure we show its drawbacks with empirical examples (Section 3). Could you please specify what kind of additional experiments you would find convincing?

Similar axioms have already been proposed in Leinster's work [1]. It would be helpful to clarify the differences between the axioms in Leinster's work and those presented in this paper.

Thanks for this reference, we will add a discussion of it to our paper.

Leinster et al. propose a measure of diversity and discuss its properties.

Let us consider the diversity of order $q$ in Leinster et al. (Equation (1)). To apply this measure to our setting, we consider all $p_i$ to be equal to $1/n$, thus the diversity of order $q$ becomes $(\sum \limits_{i=1}^n (\sum \limits_{j=1}^n s_{ij})^{q-1})^\frac{1}{1-q}$ (up to a constant multiplier), where $s_{ij}$ is a similarity score and $q$ is some constant not equal to $1$ or $\infty$. It is easy to prove that the diversity of order $q$ is continuous and monotonic, but does not have the uniqueness property, we can provide the complete proof if required and we can also add this measure to our list of diversity measures in the paper.

Let us now discuss the properties listed in Leinster at al. Partitioning properties are not applied to our case since we consider the diversity only for a fixed number of objects. For Elementary properties: Symmetry corresponds to our requirement of diversity function to be permutation invariant, and Absent species and Identical species properties are not applicable in our case (since we consider $n$ objects with equal weight and not $n$ probabilities summing to $1$). From the list of three properties in the subsection Effect of species similarity on diversity, the only property applicable in our case is Monotonicity, which is equivalent to our Monotonicity axiom. We will add this discussion to Section 4.2.

In Lines 126-128, the situation where a dataset appears more diverse from a human perspective but is less diverse in actual measurements may be strongly related to the embedding used for computing distances or similarities. This could indicate an issue with the embedding rather than the diversity measurement method. Additionally, such a case seems relatively rare, and it might be reasonable to conduct experiments to verify its occurrence.

Let us provide an intuitive example that shows that even having good embeddings, problems can be caused by a diversity measure itself. For instance, in the context of LLM generation, one can measure diversity as follows. Given several texts from an LLM as answers on the same prompt, we embed each text as a vector in some space (for instance, using a BERT-like model) and define the distance or similarity in this space (for instance, cosine similarity). After that, we can treat this collection of texts as a collection of points with pairwise distances, and measure its diversity using any measure discussed in the paper. Now, our examples in Section 3 can be interpreted in terms of LLM-generated texts. Consider, for example, an illustration in lines 162-170 of the paper. Then, the left figure may correspond to a situation when all 16 texts are on the same topic but are slightly different. In the second case, there are 15 texts that cover different topics but there is one text that coincides (or almost coincides) with one of the 15. Then, some of the measures (Energy, Bottleneck) rank the first case higher while it is clearly less diverse. Note that such an example is valid even if we have a good embedder.

Thank you for your feedback!

While the paper has some merits, it suffers from a key limitation in the method itself. The proposed diversity measures are NP-hard, making them computationally expensive as the authors acknowledge.

The main goal of discussing MultiDimVolume and IntegralMaxClique is to show that the proposed properties (axioms) do not contradict each other. Thus, they rather serve as a theoretical contribution and we do not suggest using them in practice due to their complexity.

Additionally, the lack of experimental results comparing the proposed method with prior studies raises questions about the effectiveness of the proposed method. Making the proposed method computationally tractable and including comparative experiments, therefore, would significantly strengthen the proposed approach.

First, as we discuss above, our paper does not propose any method.

However, during the discussion period, we conducted additional experiments comparing MultiDimVolume and IntegralMaxClique to existing measures using the simple examples from Section 3. The results are the following:

• The example in lines 138-148: for the left configuration MDV = 3.66, IMC = 7.41; for the right configuration MDV = 12.97, IMC = 35.67.
• The example in lines 149-156: for the left configuration MDV = 1.41, IMC = 2.00; for the right configuration MDV = 12.97, IMC = 35.67.
• The example in lines 162-170: for the left configuration MDV = 4.32, IMC = 3.96; for the right configuration MDV = 11.90, IMC = 30.35.
• The example in lines 172-178: for the left configuration MDV = 0.1, IMC = 0.01; for the right configuration MDV = 4.46, IMC = 5.25.

(Here we slightly modified the formula of MultiDimVolume by raising each summand to the power of $\frac{2}{k(k-1)}$. This does not affect our theoretical analysis or the empirical comparisons above but makes the expression more natural for using in practice, see our discussion with Reviewer 1pux.)

In all these examples, the right configuration is more diverse according to both measures, as desired. Thus, these measures do not have the drawbacks that we found for other measures.

Thank you for the feedback!

I think you should discuss in the context of several specific tasks. For example, how do you define diversity in the context of generations from LLMs? What are the intuitions regarding diversity in such a context?

In the context of LLM generation, one can define diversity in the following way. Given several texts from an LLM as answers to the same prompt, we want to measure how diverse the output is. We embed each text as a vector in some space (for instance, using a BERT-like model) and define the distance or similarity in this space (for instance, cosine similarity). After that, we can treat this collection of texts as a collection of points with pairwise distances, and measure its diversity using any measure mentioned in Section 2 of our paper, or using MultiDimVolume, or IntegralMaxClique.

Analysis of existing diversity measures is limited to simple cases. It would be better to examine whether such analysis holds for more practical scenarios, such as diversity metrics in the recommendation task or NLG generations.

Let us show how our examples in Section 3 relate to more practical scenarios. As described above, texts generated by an LLM can be represented as points in some space. Consider, for example, an illustration in lines 162-170 of the paper. Then, the left figure may correspond to a situation when all 16 texts are on the same topic but are slightly different. In the second case, there are 15 texts that cover different topics but there is one more text that coincides (or almost coincides) with one of the 15. Then, some of the measures (Energy, Bottleneck) rank the first case higher while it is clearly less diverse.

No explanation provided to "why a measure satisfying all three axioms can effectively evaluate diversity or lead to good performance while being optimized."

Note that we do not claim that any measure satisfying all three axioms is necessarily good. We claim that it is necessary for a reliable measure to have these properties but not necessarily sufficient. However, we do show that having a measure that satisfies these three axioms is already a challenging task.

How do you concretely define "our intuitive perception of diversity"?

This is the main research question of the paper - how to formalize our intuitive perception of diversity. In Section 3, we provide some examples of how we expect a good diversity measure to behave, and in Section 4.2 we formalize our intuition via three desirable properties. These are the properties that we expect a general diversity measure to satisfy (we show that measures that do not have some of the properties may have clearly unwanted behavior).

Thank you for your review and positive evaluation of our work. Regarding computational complexity, we agree that it is the main issue with MultiDimVolume and IntegralMaxClique. The main goal of discussing these two measures was to show that the proposed properties (axioms) do not contradict each other and thus we originally did not evaluate how MultiDimVolume and IntegralMaxClique perform in practice. However, as Reviewer 1pux mentions, such measures can still be used when the size of the output is small. Motivated by that, we also conducted a simple experiment and analyzed how MultiDimVolume and IntegralMaxClique rank the examples in Section 3. We see that in all the cases the ranking agrees with our expectations.

Thank you for the detailed review! We address the concerns below.

Regarding the comparison with hypervolume-based multiobjective optimization. Can the authors:

1. Clarify connections to existing work
2. Revise claim of novelty with respect to prior work

We think that this question refers to (Auger et al., 2012). This paper concerns getting an optimal distribution of several points maximizing the (weighted) hypervolume indicator. The resulting distribution is intuitively diverse (for instance if all points coincide the indicator is definitely not optimized), but there was no specific goal to maximize the diversity of these points and no definition of diversity was given. The authors do not claim that maximizing the hypervolume indicator does at the same time maximize diversity of the set of points. If you could give us (or refer to) a specific diversity function, we will investigate it.

Another weakness is a lack of experiments. … For an ICLR contribution, I would expect to see some empirical validation of the proposed methods

We consider our main contribution to be theoretical and we believe that such theoretical research fits the scope of ICLR since diversity is a concept that is widely used in machine learning. The main goal of discussing MultiDimVolume and IntegralMaxClique is to show that the proposed properties (axioms) do not contradict each other. However, following your suggestion, we do conduct a comparison of these measures with the existing ones (see below).

Contrary to the author's conclusion, an NP-hard objective can be practical if the number of candidates are few. For example, it is possible to compute the MultiDimVolume of Top-K recommended items from a recommender system, provided that K is in the range of 100-1000.

Thank you for this comment. We agree that NP-hard measures can indeed be applied to measure diversity when the output is small, we will discuss it in the paper. Because of that, we also plan to slightly modify the formula of MultiDimVolume by raising each summand to the power of $\frac{2}{k(k-1)}$. This does not change our theoretical analysis and properties of this measure but makes the formula more natural since each summand is a product of $k(k-1)/2$ distances.

Regarding empirical evaluation. Can the authors validate an empirical comparison between the proposed methods and DPP or Vendi Scores. Here are some examples of empirical papers on the topic of diversity …

It is hard to empirically compare two diversity measures since usually such measures are used to validate the results of some algorithms, and validating validation measures can be challenging. Thank you for providing relevant references. After considering their experimental setup, we see that an approach that can be applied in our case is a human evaluation that is used to decide which result is more diverse (as done in Carbonell et al.). Since our measures and analysis are general (domain-agnostic) it is natural to analyze how new measures perform for elements distributed in some space since in most applications objects are described by their vector representations and diversity is then computed for such representations. As a first step in this direction, we consider the examples from Section 3 and verify whether MultiDimVolume and IntegralMaxClique behave as desired in these examples. The results are the following (we use MultiDimVolume with a modification described above since this version seems to be more natural, but the conclusions for the original version are the same in all the cases below):

• The example in lines 138-148: for the left configuration MDV = 3.66, IMC = 7.41; for the right configuration MDV = 12.97, IMC = 35.67.
• The example in lines 149-156: for the left configuration MDV = 1.41, IMC = 2.00; for the right configuration MDV = 12.97, IMC = 35.67.
• The example in lines 162-170: for the left configuration MDV = 4.32, IMC = 3.96; for the right configuration MDV = 11.90, IMC = 30.35.
• The example in lines 172-178: for the left configuration MDV = 0.1, IMC = 0.01; for the right configuration MDV = 4.46, IMC = 5.25.

In all these examples, the right configuration is more diverse according to both measures, as desired. Thus, these measures do not have the drawbacks that we found for other measures. If you have any other examples for which we should test our measures, we will be happy to conduct such experiments.

Regarding DPP discussion, please provide the sample points that are used to create the K matrices on Line 210.

For the matrix $K_1$, consider three points A, B, C on a unit 2D sphere with pairwise spherical distances between A and B equal to arccos(0.6)= 0.927, between B and C equal to arccos(0.7)=0.795 and between A and C equal to arccos(0.2) = 1.369. The similarity is given by the cosine function. For the matrix $K_2$ we decrease the distance between A and C from arccos(0.2) = 1.369 to arccos(0.3) = 1.266, while keeping the distance between A and B unchanged, and the distance between B and C unchanged.

Are the sample points themselves violating monotonicity?

As discussed above, the points themselves violate monotonicity.

What normalization steps are commonly used for DPP calculation?

Would diagonal regularization (adding an lambda x Identity matrix) alleviate some of the drawbacks?

The informal intuition regarding the non-monotonicity of DPP is that the determinant is not a monotonically decreasing function of the non-diagonal matrix coefficients.

To the best of our knowledge, in the general DPP calculation setup, the only transformation of a matrix that is usually used before calculating the determinant is indeed a diagonal regularization. For small lambdas, the diagonal regularization won’t solve the non-monotonicity problem. For large lambdas the determinant will be approximately equal to $(1+\lambda)^n- (1+\lambda)^{(n-2)} \sum \limits_{i>j} s_{ij}^2$, which is indeed monotone. But now it degenerates to some version of the Average measure.