Rank-Biased Centroids (RBC)

The Rank-Biased Centroids (RBC) rank fusion method to combine multiple-rankings of objects.

This code implements the RBC rank fusion method, as described in:

@inproceedings{DBLP:conf/sigir/BaileyMST17,
  author    = {Peter Bailey and
               Alistair Moffat and
               Falk Scholer and
               Paul Thomas},
  title     = {Retrieval Consistency in the 
               Presence of Query Variations},
  booktitle = {Proc of {ACM} {SIGIR} Conference on
               Research and Development in Information Retrieval,
  pages     = {395--404},
  publisher = {{ACM}},
  year      = {2017},
  url       = {https://doi.org/10.1145/3077136.3080839},
  doi       = {10.1145/3077136.3080839},
  timestamp = {Wed, 25 Sep 2019 16:43:14 +0200},
  biburl    = {https://dblp.org/rec/conf/sigir/BaileyMST17.bib},
}

The fundamental step in the working of RBC is the usage a persistence parameter (p or phi) to to fusion multiple ranked lists based only on rank information. Larger values of p give higher importance to elements at the top of each ranking. From the paper:

As extreme values, consider p = 0 and p = 1. When p = 0, the agents only ever examine the first item in each of the input rankings, and the fused output is by decreasing score of firstrst preference; this is somewhat akin to a first-past-the-post election regime. When p = 1, each agent examines the whole of every list, and the fused ordering is determined by the number of lists that contain each item – a kind of "popularity count" of each item across the input sets. In between these extremes, the expected depth reached by the agents viewing the rankings is given by 1/(1 − p). For example, when p = 0.9, on average the first 10 items in each ranking are being used to contribute to the fused ordering; of course, in aggregate, across the whole universe of agents, all of the items in every ranking contribute to the overall outcome.

More from the paper:

Each item at rank 1 <= x <= n when the rankings are over n items, we suggest that a geometrically decaying weight function be employed, with the distribution of d over depths x given by (1 − p) p^{x-1} for some value 0 <= p <= 1 determined by considering the purpose for which the fused ranking is being constructed.

Example fusion

For example (also taken from the paper) for diffent rank orderings (R1-R4) of items A-G:

Depending on the persistence parameter p will result in different output orderings based on each items accumulated weights:

Code Example:

Non weighted runs:

use rank_biased_centroids::rbc;
let r1 = vec!['A', 'D', 'B', 'C', 'G', 'F'];
let r2 = vec!['B', 'D', 'E', 'C'];
let r3 = vec!['A', 'B', 'D', 'C', 'G', 'F', 'E'];
let r4 = vec!['G', 'D', 'E', 'A', 'F', 'C'];
let p = 0.9;
let res = rbc(vec![r1, r2, r3, r4], p).unwrap();
let exp = vec![
    ('D', 0.35),
    ('C', 0.28),
    ('A', 0.27),
    ('B', 0.27),
    ('G', 0.23),
    ('E', 0.22),
    ('F', 0.18),
];
for ((c, s), (ec, es)) in res.into_ranked_list_with_scores().into_iter().zip(exp.into_iter()) {
    assert_eq!(c, ec);
    approx::assert_abs_diff_eq!(s, es, epsilon = 0.005);
}

Weighted runs:

use rank_biased_centroids::rbc_with_weights;
let r1 = vec!['A', 'D', 'B', 'C', 'G', 'F'];
let r2 = vec!['B', 'D', 'E', 'C'];
let r3 = vec!['A', 'B', 'D', 'C', 'G', 'F', 'E'];
let r4 = vec!['G', 'D', 'E', 'A', 'F', 'C'];
let p = 0.9;
let run_weights = vec![0.3, 1.3, 0.4, 1.4];
let res = rbc_with_weights(vec![r1, r2, r3, r4],run_weights, p).unwrap();
let exp = vec![
    ('D', 0.30),
    ('E', 0.24),
    ('C', 0.23),
    ('B', 0.19),
    ('G', 0.19),
    ('A', 0.17),
    ('F', 0.13),
];
for ((c, s), (ec, es)) in res.into_ranked_list_with_scores().into_iter().zip(exp.into_iter()) {
    assert_eq!(c, ec);
    approx::assert_abs_diff_eq!(s, es, epsilon = 0.005);
}

License

MIT