论文标题
具有二元特征表示的极端算法选择
Extreme Algorithm Selection With Dyadic Feature Representation
论文作者
论文摘要
算法选择（AS）涉及从固定的候选算法中选择最适合算法问题特定实例的算法，例如，为SAT问题选择求解器。基准套件通常包括由大多数算法组成的候选套件，而在合并的算法选择和超参数优化问题中，候选人的数量变得棘手，阻碍了学习有效的元模型，因此需要成本成本的在线绩效评估。因此，在这里，我们提出了极端算法选择（XAS）的设置，其中我们考虑了数千种候选算法的固定集，从而促进了元学习。我们将最新技术作为XAS设置的技术评估，并提出了利用二元特征表示的方法，其中描述了问题实例和算法。我们发现，在各种指标中，后者可以显着改善当前艺术的状态。
Algorithm selection (AS) deals with selecting an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem, e.g., choosing solvers for SAT problems. Benchmark suites for AS usually comprise candidate sets consisting of at most tens of algorithms, whereas in combined algorithm selection and hyperparameter optimization problems the number of candidates becomes intractable, impeding to learn effective meta-models and thus requiring costly online performance evaluations. Therefore, here we propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms, facilitating meta learning. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation in which both problem instances and algorithms are described. We find the latter to improve significantly over the current state of the art in various metrics.
