A Structured Prediction Approach for Label Ranking
We propose to solve a label ranking problem as a structured output regression task. In this view, we adopt a least square surrogate loss approach that solves a supervised learning problem in two steps: a regression step in a well-chosen feature space and a pre-image (or decoding) step. We use specific feature maps/embeddings for ranking data, which convert any ranking/permutation into a vector representation. These embeddings are all well-tailored for our approach, either by resulting in consistent estimators, or by solving trivially the pre-image problem which is often the bottleneck in structured prediction. Their extension to the case of incomplete or partial rankings is also discussed. Finally, we provide empirical results on synthetic and real-world datasets showing the relevance of our method.
This paper presents an interesting approach to the label ranking problem, by first casting it as a Structured Prediction problem that can be optimized using a surrogate least square methodology, and then demonstrating an embedding representation that captures a couple of common ranking loss functions -- most notable being the Kendall-Tau distance.  Overall I liked the paper and found a decent mix of method, theory and experiments (though I would have liked to see more convincing experimentation as further detailed below). In particular I liked the demonstration of the Kendall tau distance and Hamming distances to be representable in this embedding formulation/  That said I had a few concerns with this work as well:  - Specifically the empirical results were not very convincing. While this may not have been a problem for a theory-first paper, part of the appeal of an approach like this it is supposed to work in practice. Unfortunately with the current (some what limited) set of experiments I am not entirely convinced.  For example: This only looked at a couple of very specific (and not particularly common loss functions) with the evals only measuring Kendall Tau. Instead metrics like MAP and NDCG are the more standard metrics typically used these days. Absence of any of those metrics or other standard metrics was quite concerning.  Coupled with the result that indicated that optimizing the specific metric does not always lead to the best results on other metrics is why more eval metrics would have helped paint a clearer picture.  Furthermore as the authors themselves point out: top-k rankings are a primary focus in most applications and towards this end the paper does not exactly provide a solution for this more practical problems or even discuss variants to tackle it. Furthermore there are no metrics or evals either on this important setting.  The datasets used in these evals also are not the most common or standard from the IR perspective and I would have liked to see more standard ranking datasets be used for the evaluation.  Lastly I would have liked to see more competitive baselines that capture performance of the different previous works in this field that may not be label-ranking based. This may help contrast this approach versus other methodologies. Would also be great to understand running time for the different methods compared.  ----  POST-AUTHOR FEEDBACK EDIT: Thank you to the authors for their response. I appreciate you taking time to clarify some of my concerns.  Regarding my main concern about the evaluation: Unfortunately I don't think I felt that was adequately addressed. I shoulder some of the blame for not not being more detailed so let me try to convey my thoughts in more detail below:  - The authors mention that their approach is specific  to label ranking and not LTR and other related problems. However I think that reduces the appeal of the paper since label ranking is a far less common problem than LTR with a lot more niche applications. If the sole focus was label ranking then I'd like the authors to have explained what problems can only be tackled by label ranking approaches and not by approaches from LTR or multi-class classification approaches.  - In particular the latter (multi-class classification) could easily be used as well to produce a "ranking" over the different labeled class. What I don't see is an evaluation justifying the approach for the niche cases multi-class classification cannot handle as well (say where there is a relationship among the labels).  - Lastly when I referred to previous approaches, I was thinking about the works by Thorsten Joachims and collaborators for example. I failed to see any mention of how well something like a structual SVM would do on this problem.  I feel the paper would be a lot stronger if it discussed (and ideally compared) against these existing approaches.