What are some "nice" properties a "similarity index" should have?

Question

I am reading a book that talks about how to construct a similarity index operating on a probability vector $\mathbf{p}=(p_1,...,p_k)$ to describe how similar its elements are. In my book, indexes of similarity are described briefly, mentioning just that a good index should achieve its minimum value when:

$$p_1 = p_2 = … = p_{j-1} = p_{j+1} = … = p_k = 0 \quad \text{ and } \quad p_j = 1,$$

and should achieve its maximum value when:

$$p_1 = p_2 = … = p_j = … = p_k = \tfrac{1}{k}.$$

After that, my book gives the formulas for the Gini index and the entropy. I think that the two properties above are essential for a good similarity index, but there must be some other properties they need to have. What are some other properties that a "similarity index" should have?

Answer 1

To facilitate analysis, consider a similarity measure $S: \mathbf{p} \mapsto \mathbb{R}$. The two properties you have mentioned imply that $S$ is a bounded measure, so we have $s_* \leqslant S(\mathbf{p}) \leqslant s^*$ for all $\mathbf{p}$. The measure achieves its minimum $s_*$ when a single element dominates the vector, and acheives its maximum $s^*$ when all elements are equal. In addition to these two properties, some other useful properties are:

• Symmetry: This property means that the similarity measure treats each element in the vector the same --- i.e., it is invariant to permutations of the elements. Formally, a similarity measure is symmetric if we have $S(\pi(\mathbf{p})) = S(\mathbf{p})$ for any permutation $\pi$. This property ensures that each of the elements in the probability vector are treated the same way, so that it is not biased towards any of the individual probabilities.

• Smoothness: This property means that the similarity measure has continuous derivatives up to a some specified order. At the most extreme, we could specify that the measure has derivatives at all orders. This is a useful property for the function because it allows the use of derivatives, but it also makes sense because it ensures that the similarity changes smoothly as we move the probability vector around its allowable range.

• Convexity: This property means that the similarity measure for a convex combination of two probability vectors cannot be greater than the similarity measure for either of those vectors. Formally, this means that $S(\alpha \mathbf{p} + (1-\alpha) \mathbf{p}') \leqslant \max(S(\mathbf{p}), S(\mathbf{p}'))$ for all $0 \leqslant \alpha \leqslant 1$. If we have also assumed smoothness up to the second derivative (i.e., that the Hessian for the similarity measure exists) then the property of convexity implies that the Hessian is negative definite over its entire range. This is a useful property because it ensures that the similarity increases more rapidly when you move an extreme probability towards the centre, and increases more slowly when you move a less extreme probability towards the centre.

These properties are generally very useful for a measure of similarity. Both the Gini index and the entropy have these properties.