When algorithm selection meets Bi-linearLearning to Rank: accuracy and inference time trade off with candidates expansion

AutorJing Yuan, Christian Geissler, Weijia Shao, Andreas Lommatzsch, Brijnesh Jain
QuelleInternational Journal of Data Science and Analytics, 
LinksBibTeX   |   Uni-Bibliothek 

Algorithm selection (AS) tasks are dedicated to find the optimal algorithm for an unseen problem instance. With the knowledge of problem instances' meta-features and algorithms' landmark performances, Machine Learning (ML) approaches are applied to solve AS problems. However, the standard training process of benchmark ML approaches in AS either needs to train the models specifically for every algorithm or relies on the sparse one-hot encoding as the algorithms' representation. To escape these intermediate steps and form the mapping function directly, we borrow the learning to rank framework from Recommender System (RS) and embed the bi-linear factorization to model the algorithms' performances in AS. This Bi-linear Learning-to-Rank (BLR) has proven to work with competence in some AS scenarios and thus is also proposed as a benchmark approach. Thinking from the evaluation perspective in the modern AS challenges, precisely predicting the performance is usually theme assuring goal. Though approaches' inference time also needs to be counted for the running time cost calculation, it's always overlooked in the evaluation process. The multi-objective evaluation metric Adjusted Ratio of Root Ratios (A3R) is therefore advocated in this paper to balance the trade-off between the accuracy and inference time in AS. Concerning A3R, BLRout performs other benchmarks when expanding the candidates range toTOP3. The better effect of this candidate expansion results from the cumulative optimum performance during the AS process. We take the further step in the experimentation to represent the advantage of such TOP-K expansion, and illustrate that such expansion can be considered as the supplement for the convention of TOP-1 selection during the evaluation process.