On the Role of Maximal Independent Sets in Cleaning Data Sets for Supervised Ranking

Multi-criteria data sets for training supervised ranking algorithms are prone to a special kind of noise or inaccuracies, resulting in non-monotonicity. Though general approaches for removing noise exist, the remediation of non-monotonicity is less thoroughly researched. In this paper we show the relationship between the non-monotonicity problem and the general independent set problem, discuss and quantify the adverse effects of non-monotonicity in test sets for a general monotone ranking algorithm, discuss some ways of performing remediation of non-monotonicity and apply these insights to two real-life data sets.