You are here

Latent Features for Algorithm Selection

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
The success and power of algorithm selection techniques has been empirically demonstrated on numerous occasions, most noticeably in the competition settings like those for SAT, CSP, MaxSAT, QBF, etc. Yet while there is now a plethora of competing approaches, all of them are dependent on the quality of a set of structural features they use to distinguish amongst the instances. Over the years, each domain has defined and refined its own set of features, yet at their core they are mostly a collection of everything that was considered useful in the past. As an alternative to this shotgun generation of features, this paper instead proposes a more systematic approach. Specifically, the paper shows how latent features gathered from matrix decomposition are enough for a linear model to achieve a level of performance comparable to a perfect Oracle portfolio. This information can, in turn, help guide researchers to the kinds of structural features they should be looking for, or even just identifying when such features are missing.
Conference Name: 
Proceedings of the Seventh Annual Symposium on Combinatorial Search (SOCS -2014)
Proceedings: 
Proceedings of the Seventh Annual Symposium on Combinatorial Search (SOCS -2014)
Digital Object Identifer (DOI): 
10.NA
Publication Date: 
31/07/2014
Conference Location: 
Czech Republic
Institution: 
National University of Ireland, Cork (UCC)
Project Acknowledges: 
Open access repository: 
Yes