ALORS: An algorithm recommender system

doi:10.1016/j.artint.2016.12.001

2017-03-01

Mustafa Mısır *

Michèle Sébag

DOI：10.1016/j.artint.2016.12.001

原文链接

查看原文

摘要

En 中文

Algorithm selection (AS), selecting the algorithm best suited for a particular problem instance, is acknowledged to be a key issue to make the best out of algorithm portfolios. This paper presents a collaborative filtering approach to AS. Collaborative filtering, popularized by the Netflix challenge, aims to recommend the items that a user will most probably like, based on the previous items she liked, and the items that have been liked by other users. As first noted by Stern et al. [47], algorithm selection can be formalized as a collaborative filtering problem, by considering that a problem instance likes better the algorithms that achieve better performance on this particular instance. Two merits of collaborative filtering (CF) compared to the mainstream algorithm selection (AS) approaches are the following. Firstly, mainstream AS requires extensive and computationally expensive experiments to learn a performance model, with all algorithms launched on all problem instances, whereas CF can exploit a sparse matrix, with a few algorithms launched on each problem instance. Secondly, AS learns a performance model as a function of the initial instance representation, whereas CF builds latent factors to describe algorithms and instances, and uses the associated latent metrics to recommend algorithms for a specific problem instance. A main contribution of the proposed algorithm recommender ALORS system is to handle the cold start problem emitting recommendations for a new problem instance - through the non-linear modeling of the latent factors based on the initial instance representation, extending the linear approach proposed by Stern et al. [47]. The merits and generality of ALORS are empirically demonstrated on the ASLib [6] and OpenML [53] benchmarks. (C) 2016 Elsevier B.V. All rights reserved.

Keyword:

Algorithm selection

Constraint satisfaction

Constraint programming

Collaborative filtering

Meta-learning