Listwise frameworks for ranking and rank aggregation
MetadataShow full item record
The goal in Learning to Rank (LETOR) is to learn to order a novel set of items, given training data comprising sets of items and their orderings. There are three important problems in LETOR: capturing individual item relevance, using item interaction information to diversify rankings and aggregating ranked lists. The first has been the subject of considerable recent work; this dissertation contributes to the latter two. LETOR is a key component in Information Retrieval (IR) systems. IR approaches first select relevant items using naïve but scalable strategies, then apply sophisticated LETOR algorithms to re-rank them before user presentation. Most existing LETOR approaches assign scores to each item independently of the other retrieved items and simply rank them according to these scores. These methods are described as listwise in the literature but we finesse these as pointwise ranking functions being used with listwise losses. However sophisticated such an approach may be, it can never hope to diversify rankings if it does not take interactions between items into account at test time. Our contributions are as follows: we introduce listwise ranking functions (LRFs) and a corresponding representation theorem. Then, we discuss a listwise boosting procedure for combining LRFs, and analyze boostability, weak-learnability in this context. Motivated by empirical concerns, we introduce and address the problem of learning a "best" surrogate function from among those consistent with an underlying metric, i.e. one most suited to the data distribution. We study fundamental limitations of unsupervised rank aggregation procedures by connecting them to impossibility results in social choice theory, namely Arrow's theorem, and consider relaxed variants of social choice axioms. Towards the aim of modeling ranking and diversity in a flexible manner, we study how to handle ranking factors in Graphical Models and test these ideas empirically in an oceanographic float-tracking problem setting which requires ranking as a key component. The ideas presented in this dissertation are supported by experiments primarily on MSLETOR datasets; we conclude with thoughts on the limitations of these datasets for learning LRFs and propose directions for the future.