Loss optimal monotone relabeling of noisy multi-criteria data sets

A method to relabel noisy multi-criteria data sets is presented, taking advantage of the transitivity of the non-monotonicity relation to formulate the problem as an efficiently solvable maximum independent set problem. A framework and an algorithm for general loss functions are presented, and the flexibility of the approach is indicated by some examples, showcasing the ease with which the method can handle application-specific loss functions. Both didactical examples and real-life applications are provided, using the zero-one, the L1 and the squared loss functions, as well as combinations thereof.