We describe the OpenWebSearch group's participation in the CLEF 2024 QuantumClef IR Feature Selection track. Our submitted runs focus on the observation that the importance of features in learning-to-rank models can vary and contradict itself when changing the training setup. To address this problem and identify a subset of features that is robust across diverse downstream training procedures, we bootstrap feature importance scores by repeatedly training models on randomly selected subsets of features and measuring their importance in trained models. We indeed observe that feature importance varies widely across different bootstraps and also contradicts itself. We hypothesized that quantum annealers could better explore this complex optimization landscape than simulated annealers. However, we find that quantum annealers do not find substantially more optimal solutions that yield substantially more effective learning-to-rank models.
Learning-to-Rank aims to identify a combination of features that produce an effective ranking [1]. Even in the era of pre-trained transformers [2], feature-based learning-to-rank remains important as it can integrate features not available in transformers, compensating for knowledge to which transformers have no access [3,4]. Especially commercial search engines might combine many features, e.g., a recent leak claims that Google search incorporates more than 14 000 features into their ranking. 1 Such scenarios highlight the importance of proper feature selection, as different search systems (even if they might be bundled behind a single UI) might target at different tasks (expressed via an evaluation scenario, e.g., evaluation measure with a test dataset) that require different sets of features. In the scenario of the QuantumCLEF task [5,6,7], we start from the original quadratic unconstrained binary optimization prepared in the official tutorial [8] and contrast the components of this optimization problem with bootstrapped alternatives. Bootstrapping is a frequently used approach in statistics if the mean of some population is not meaningful or can not be calculated (e.g., for categorical values) that draws repeated samples of some data [9]. We use bootstrapping for feature selection by repeatedly sampling LambdaMART models from the training data. Thereby, we follow the intuition that the original optimization problem that uses the mutual information and the conditional mutual information can not capture all potentially interesting dependencies that might impact what features are important. Our code and the bootstrapped feature-importance scores are available online. 2
We will review related work on bootstrapping and feature selection in information retrieval that inspired our work. π β π + [model.calculateFeatureImportance()] 6: end while 7: return π Bootstrapping in Information Retrieval Bootstrapping, i.e., the process of repeatedly sampling from the same distribution, has been used previously in information retrieval, e.g., to sample from the relevance judgments, from the topics, or from the document corpus [10]. The leave-out-uniques test is a form of re-sampling of relevance judgments used to estimate the reusability of test collections [11,12,13]. Bootstrapping topics has been used for significance tests [14,15] respectively for assessing the discriminatory power of evaluation measures [16,17,18]. Analogously, bootstrapping the document corpus can help to simulate different corpora [18], estimate if results transfer to other corpora [19], or, again, for meta evaluations of evaluation measures [18]. Given the wide applicability of bootstrapping in the field of information retrieval, we now intend to apply it to learning to rank. Contrary to the approaches discussed above, our approach mainly focuses on re-sampling the set of features that subsequent learning-to-rank models can access.
Feature Selection Feature selection approaches are either filter methods, wrapper methods, or embedded methods [20], distinguished on how deep (if at all) they integrate with the learning algorithm [21]. Filter methods have no integration with the learning algorithm [21] (i.e., they run before the learning starts), e.g., the original quadratic unconstrained binary optimization prepared in the official QuantumCLEF tutorial [8] falls into this category. Wrapper methods use a search algorithm to select the features [22], whereas embedd methods integrate the selection into the actual learning phase [21]. Our approach falls into the category of wrapper methods. There is already an high number of existing feature selection approaches for learning to rank [22,21,23,24,25,26], comparing respectively integrating them with boostrapping could be interesting directions for future work.
This section describes our bootstrapping approach for feature selection. Conceptually, we formulate a quadratic unconstrained binary optimization problem [5] that can be optimized via simulated annealing and via quantum annealing. The number of features that our feature selection selects is an hyperparameter that one could optimize, but we leave this for future work and always select the top-25 features (our focus was on the MQ2007 dataset that had around 50 features, so we intuitively selected 25 as number of features to target at). We create three optimization formulations for our bootstrapping feature selection that differ in if they incorporate mutual information optimization objectives or not. We submitted our three approaches within the qCLEF platform [27] for simulated annealers and quantum annealers, yielding 6 runs overall.
Algorithm 1 shows our bootstrapping algorithm. The algorithm has the features π , the target label π¦, the number of bootstraps π, an LightGBM training procedure, and a sampling approach as input. Subsequently, each bootstrapping iteration first samples a subset of features π β² together with their corresponding ground truth labels π¦ β² . With this sampled set of features, a LambdaMART model is trained for which the feature importance is calculated and added to the return vector π. For the training of the LambdaMART models, we use the LightGBM [28] implementation in PyTerrier [29]. We do not tune the hyperparameters of LambdaMART but use the hyperparameters from a different project without adoption [30]. We sample the featured π β² by randomly sorting the feature records and selecting a random subset of 25 features.
To incorporate the bootstrapped feature importance scores into the feature selection, we include them into an optimization criterion that can be optimized by quantum annealers and by simulated annealing. Therefore, we use the quadratic unconstrained binary optimization (QUBO) formulation that minimizes the following objective [5]:
Where βοΈ π π π π β’ π₯ π is the linear part of the QUBO and βοΈ π π<π π π,π β’ π₯ π β’ π₯ π is the quadratic part. The official starting point of the shared task fills the linear part of the QUBO with the negative mutual information between a feature and the ground truth label and the quadratic part with the negative conditional mutual information between two features and the ground truth label [8]. To incorporate our bootstrapped feature importance, we use the following formulation for the linear part:
Where π is the number of bootstraps, π π π is the importance of feature π in the π-th bootstrapped model, and |π| is the overall importance. Analogously, we implement the quadratic part of the bootstrapping QUBO via:
Where π is the number of bootstraps, π π π is the importance of feature π in the π-th bootstrapped model, π π π is the importance of feature π in the π-th bootstrapped model, and |π| is the overall importance. In both bootstrapping equations, we skip for a feature π or a feature combination π, π bootstraps that do not include the feature because it was not sampled.
To summarize the points above, we have four parts to build QUBO formulations, two from the original mutual information formulation, and two from our new bootstrapping formulation. We combine them to produce three systems that we run on simulated and quantum annealing: mi-linear-bootstrapped-boost-3 This QUBO uses the linear part of our bootstrapping formulation and the quadratic part from the original conditional mutual information. We multiple the bootstrapping scores with 3 as this factor provided results on a similar scale then the previous mutual information (identified by manual inspection).
This QUBO uses the linear and quadratic part of our bootstrapping formulation. We multiple the bootstrapping scores with 3 as this factor provided results on a similar scale then the previous mutual information (identified by manual inspection).
This QUBO uses the average of the mutual information and our bootstrapping variant for the linear and quadratic part.
We provide evaluations of our methods compared to the baseline of using all features on the MQ2007 and Istella [3] dataset. We report the results in terms of nDCG@10, reporting the 25-th, the 50-th,
Effectiveness of the LambdaMART models in terms of nDCG@10 on the MQ2007 dataset. We report the results of our three feature selection approaches that selected 25 features and their effectiveness at the 25-th, the 50-th and the 75-th percentile and the mean for simulated annealing and quantum annealing.
Effectiveness of the LambdaMART models in terms of nDCG@10 on the Istella dataset. We report the results of our three feature selection approaches that selected 25 features and their effectiveness at the 25-th, the 50-th and the 75-th percentile and the mean for simulated annealing and quantum annealing. ) and the Mean of the nDCG@10 for all our three approaches for simulated annealing and quantum annealing. Table 1 shows the results for the MQ2007 dataset. We observe that all feature selection approaches slightly improve upon the baseline of selecting all features, with the bootstrapping variants outperforming the mixed variant and the QUBO that uses the linear and quadratic bootstrapping part is the most effective one, for simulated and quantum annealing.
Table 2 shows the results for the Istella dataset. We observe that all feature selection approaches are substantially less effective then the baseline of using all features. It is interesting future work to investigate how this can be resolved.
We presented the Open Web Search (OWS) team's submission to the QuantumCLEF shared task at CLEF 2023. The motivation behind our approach was that LambdaMART models trained on shuffled datasets might choose different features as important ones. Therefore, we repeatedly train LambdaMART models on randomized feature sets and measure the importance of the features in the trained model. For the MQ2007 dataset, our approach substantially outperforms the baseline, while for the Istella dataset, simply selecting all features is substantially more effective than our feature selection. For future work, we believe that accurately determining the number of to-be-selected features is an important next step, as this would help to not reduce the effectiveness in the Istella scenario.
This work has received funding from the European Union's Horizon Europe research and innovation program under grant agreement No 101070014 (OpenWebSearch.EU, https://doi.org/10.3030/101070014).
1 https://sparktoro.com/blog/an-anonymous-source-shared-thousands-of-leaked-google-search-api-documents-with-meeveryone-in-seo-should-see-them 2 https://bitbucket.org/eval-labs/qc24-ows/