Permutation Learning via Lehmer Codes
Aïssatou Diallo, Markus Zopf, Johannes Fürnkranz · Frontiers in artificial intelligence and applications · 2020
Many machine learning problems require to learn to permute a set of objects. Notable applications include ranking or sorting. One of the difficulties of learning in such a combinatorial space is the definition of meaningful and differentiable distances and loss functions. Lehmer codes are an elegant way for mapping permutations into a vector space where the Euclidean distance between two codes corresponds to the Kendall tau distance between the corresponding rankings. This transformation, therefore, allows the use of a surrogate loss converting the original permutation learning problem into a surrogate prediction problem which is easier to optimize. To that end, learning to predict Lehmer codes allows a transformation of the inference problem from permutations matrices to row-stochastic matrices, thereby removing the constraints of row and columns to sum to one. This permits a straight-forward optimization of the permutation prediction problem. We demonstrate the effectiveness of this approach for object ranking problems by providing empirical results and comparing it to competitive baselines on different tasks.