Algorithm Selection as a Collaborative Filtering Problem

Mustafa Misir 1 Michèle Sebag 2
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Focusing on portfolio algorithm selection, this paper presents a hybrid machine learning approach, combining collaborative filtering and surrogate latent factor modeling. Collaborative filtering, popularized by the Netflix challenge, aims at selecting the items that a user will most probably like, based on the previous movies she liked, and the movies that have been liked by other users. As first noted by Stern et al (2010), algorithm selection can be formalized as a collaborative filtering problem, by considering that a problem instance ''prefers'' the algorithms with better performance {on this particular instance}. A main difference between collaborative filtering approaches and mainstream algorithm selection is to extract latent features to describe problem instances and algorithms, whereas algorithm selection most often relies on the initial descriptive features. A main contribution of the present paper concerns the so-called cold-start issue, when facing a brand new instance. In contrast with Stern et al. (2010), ARS learns a non-linear mapping from the initial features onto the latent features, thereby supporting the recommendation of a good algorithm for the new problem instance with constant computational cost. The experimental validation of ARS considers the domain of constraint programming (2008 CSP and 2011 SAT competition benchmarks) and gradient-free continuous optimization (black-box optimization benchmarks), demonstrating the merits and the genericity of the method.
Document type :
Reports
Liste complète des métadonnées

Cited literature [53 references]  Display  Hide  Download

https://hal.inria.fr/hal-00922840
Contributor : Michele Sebag <>
Submitted on : Tuesday, December 31, 2013 - 2:39:27 AM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Document(s) archivé(s) le : Monday, March 31, 2014 - 10:06:08 PM

File

techrep_ARS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00922840, version 1

Collections

Citation

Mustafa Misir, Michèle Sebag. Algorithm Selection as a Collaborative Filtering Problem. [Research Report] 2013, pp.43. ⟨hal-00922840⟩

Share

Metrics

Record views

826

Files downloads

1267