Quantifying Uncertainty due to Ties in Rank Correlation Coefficients

Rank correlation coefficients are a common tool for describing similarity between ordered data. This study examines the use of the popular coefficient Kendall's τ, specifically in the case where the rankings contain tied items that should not be tied.  Ties in this case represent uncertainty in the ranking, induced by the system that produced it, usually due to effects such as missing information or loss of precision (rounding). We propose two variants, τ^min and τ^max, which represent the lowest and highest possible correlation over all ways of arbitrating tied items. Our contribution is a novel quadratic-time algorithm for computing an arbitration of ties which yields the extremal correlation values τ^min, τ^max. We formally prove the correctness of the algorithm for the original Kendall's τ, and we suggest an adaptation for weighted variants of τ, such as τ_AP by Yilmaz et al. and τ_h by Vigna. Empirical evaluation on both synthetic ranking pairs and TREC ad-hoc system outputs demonstrates that ties often induce wide intervals [τ^min, τ^max], indicating that no single value can fully encapsulate the uncertainty in correlation. These wide intervals also appear in rankings where current methods of computing τ correlation in presence of ties, namely τ^a and τ^b,  have values large enough (≥0.9) for researchers to use as evidence of strong correlation. This indicates that currently used methods may yield false positive results. By reporting τ alongside its uncertainty bounds τ^min and τ^max, researchers are able to make more informed decisions,

by demonstrating the reliability of correlation in presence of uncertainty-induced ties.