Evolutionary Risk-Sensitive Feature Selection for Learning to Rank

Abstract

Learning to Rank (L2R) is one of the main research lines in Information Retrieval. However with ever increasing data and more complex machine learning algorithms, the effort to process all sub-tasks in L2R has increased tremendously. More specifically, after a ranking algorithm provides a huge subset (sometimes gigabytes) of documents from query terms, there is an extensive work of L2R phase to generate meta-features on the fly and to process the time consuming state-of-the-art machine learning algorithms. In this context, feature selection (FS) becomes an important alternative to withdraw unimportant features. Besides improving the overall L2R execution time, FS can also try to improve the effectiveness with the absence of noisy and redundant features. However, for years the literature has focused mostly on effectiveness and feature reduction as the main objective criteria for Feature Selection. But removing certain features may damage the effectiveness of the learned model for some specific but important queries. In fact, we have noted in our work that by optimizing only an average effectiveness and number of features as criteria in FS for L2R one can deteriorate the ranking effectiveness of some queries, providing less robust models. Therefore, in this dissertation we propose to evaluate FS for L2R with an additional objective in mind, named risk-sensitiveness. We introduce the risk-sensitiveness to the FS for L2R, providing novel single and multi-objective criteria to optimize feature reduction, effectiveness and risk-sensitiveness, sometimes at the same time. To achieve our goal, we consider distinct risk-sensitive measures, such as FRISK, TRISK, and GRISK. As results of this front, we show that risk-sensitiveness is a crucial objective criterion in FS for L2R, providing still better results than the effectiveness criterion. Mainly because more than an average value, risk-sensitiveness assesses the comparison of several queries against one or a set of Information Retrieval baselines, providing a larger comparison of two subsets of features. In order to evaluate our new objective criteria for FS in L2R, we also propose a new methodology to explore the multi-objective search space, suggesting effective and efficient extensions of wrapper and a well-known Pareto Frontier algorithm, e.g. Strength Pareto Evolutionary Algorithm (SPEA2). By effective, we mean a more strict comparison for sets of features, using a paired statistical test to increase the strength of the dominance relationship in the Pareto set. In case of the efficient extensions, we introduce a weak learner as a blackbox in order to improve the evaluation of the wrapper strategy. Besides decreasing the time performance, this proposal also provides a more accurate comparison of features, improving the effectiveness of the final individual for the evolutionary process. Our experimental results show that the proposal objective criteria outperforms the state-of-the-art FS methods concerning effective and risk-sensitive evaluation. For instance, for WEB10K dataset we allow a feature reduction of up 35% with same effective and risksensitive performance. Moreover, we show that the risk-sensitiveness criterion provided results more effective and robust than using only effectiveness. We show strong evidence towards the benefits of using weak learner as a black-box and the improvements of selecting the final individual from the Pareto set by using the paired statistical test. In this dissertation we also provide a thorough analysis of our methodology and its impact on feature reduction, risk-sensitiveness and effectiveness on FS for L2R.