Ranking similarity

updated: 2022-11-25
#machine-learning/metrics

How similar are the two rankings? Answering this question leads to a variety of ranking similarity metrics.

Ranking correlation

We can measure the similarity between two entities using correlation. For example, if the entities have two variables representing their positions in two rankings, the correlation between the variables can be used to quantify the similarity.

Rank biased overlap

Rank biased overlap (RBO) is a similarity metric which is more sensitive to the differences in top rankers, as opposed to correlation-based metrics which treat all entities equally. This is preferred, as in practice, the top entities are more important than the bottom entities.

The RBO is a concept that is fundamental to many biased similarities. Let's consider two lists of entities, and , that are both sorted according to their rank. We can denote the top entities in as . The first entry in the list, , is the highest ranked entity. RBO is defined as follows:

The parameter (defaulting to ) controls the contribution of low-rank entities to RBO. The term represents the number of common entities for the top rankers, and dividing it by gives the fraction of common entities. This fraction is then summed over ranking, with the weight of the depth at given by , thus giving greater weight to top rankers than to low-rank entities.

Implementing RBO is trickly since the sum is extended over though an implementation is available:

Truncated RBO

The original RBO takes the sum over entities beyond the ranking. Since the entities outside of the ranking is unknown, the original paper introduces an exterpolation method. But this gives many complexity with additional assumptions on the input data. So I personally prefer its truncated version, where the summation is taken for the finite ranking. Since the summation is truncated, the maximum "truncated" RBO is less than one, which makes interpretation difficult. To amend this, I rescale the truncated RBO by dividing it by the maximum truncated sum.

My implementation is available here:

Interactive graph
Links to this page
Machine Learning