Algorithm Selection as a Collaborative Filtering Problem

Mustafa Misir 1 Michèle Sebag 2
1 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Résumé : Cet article s'intéresse á la sélection de l'algorithme le plus adapté á l'instance de probléme considérée, parmi les algorithmes d'une plate-forme donnée. L'approche proposée s'inspire du filtrage collaboratif. Popularisé par le challenge Netflix, le filtrage collaboratif recommande les produits qu'un utilisateur peut apprécier, en se fondant sur l'historique des produits appréciés par cet utilisateur et par la communauté des utilisateurs. Comme noté par Stern et al. (2010), la sélection d'algorithmes peut être vue comme un probléme d'apprentissage collaboratif, oú une instance de probléme est vue comme un utilisateur qui ''préfére'' les algorithmes dont la performance sur cette instance est la meilleure. Une différence essentielle de l'approche par CF par rapport à l'état de l'art en sélection d'algorithme est de caractériser les instances de problèmes et les algorithmes en terme de facteurs latents au lieu de se limiter aux attributs initiaux (comme e.g. CPHydra ou SATzilla). S'inspirant de Stern et al. (2010), cet article présente l'algorithme ARS ({\em Algorithm Recommender System}), exploitant les données des performances des algorithmes sur les instances disponibles pour faire de la sélection d'algorithme. Une contribution essentielle concerne le probléme dit du démarrage á froid, oú on ne dispose d'aucune information sur une nouvelle instance de probléme. L'approche proposée s'appuie sur l'apprentissage d'un modéle non-linéaire, estimant les facteurs latents á partir des descripteurs initiaux. ARS réalise ainsi la sélection d'algorithmes pour les instances nouvelles á coût de calcul constant. La validation expérimentale d'ARS considére les domaines de la programmation par contraintes (2011 SAT Competition problems et CSP 2008 Competition benchmarks) et de l'optimisation stochastique continue (BBOB 2012 noiseless datasets), démontrant la généricité de l'approche proposée.
Type de document :
Rapport
[Research Report] 2013, pp.43
Liste complète des métadonnées

Littérature citée [53 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00922840
Contributeur : Michele Sebag <>
Soumis le : mardi 31 décembre 2013 - 02:39:27
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : lundi 31 mars 2014 - 22:06:08

Fichier

techrep_ARS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

738

Téléchargements de fichiers

1158