Source-linked AI summary
Extreme Algorithm Selection With Dyadic Feature Representation
Alexander Tornede, Marcel Wever, Eyke Hüllermeier
TL;DR
Traditional algorithm selection typically considers only tens of candidates, while CASH can involve vast candidate spaces and costly online evaluations. The paper proposes XAS and dyadic feature approaches that represent both instances and algorithms; on a benchmark with more than 1,200 candidates, these approaches perform particularly well across various metrics and outperform other state-of-the-art AS approaches.
Problem
Traditional AS benchmarks usually have at most tens of candidate algorithms, while CASH can involve very large candidate spaces and costly online evaluations.
Source: §1 · p. 2Method
The paper defines XAS and evaluates dyadic approaches that use feature representations of both problem instances and algorithms.
Source: §7 · p. 14Results
On the proposed benchmark, dyadic feature approaches perform particularly well across various metrics and outperform other state-of-the-art AS approaches.
Source: §7 · p. 14Takeaways & Limitations
The results suggest that XAS needs methods suited to large candidate sets and sparse training data.
Source: §5.5 · p. 13Current algorithm features support cold start only to a limited extent: new candidates can be considered only when their hyperparameters are known.
Source: §7 · p. 14
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces extreme algorithm selection (XAS) for prompt recommendations over very large, finite candidate sets. It proposes dyadic feature methods and reports significant improvements over existing approaches.
1 Introduction
- CASH may involve so many candidates that effective meta-model learning becomes infeasible, leaving costly search and online evaluations.Source: §1 · p. 2
- XAS targets prompt recommendations from extremely large, but finite, candidate algorithm sets.The setting is positioned between traditional algorithm selection and algorithm configuration or CASH.Source: §1 · p. 2
- For on-the-fly computing, XAS offers a compromise that supports quick service recommendations without costly online evaluations.It can also recommend configurations not previously encountered.Source: §1 · p. 2
- Dyadic feature methods yield significant improvements in an extensive experimental study.They describe both problem instances and algorithms with feature vectors.Source: §1 · p. 2
2 From Standard to Extreme Algorithm Selection
Standard algorithm selection maps problem instances to algorithms that optimize a performance measure. XAS retains a finite candidate set but assumes it is extremely large and the training performance matrix is sparse.
2 From Standard to Extreme Algorithm Selection
- A standard algorithm selector maps each problem instance to a candidate algorithm that optimizes a performance measure.Source: §2 · p. 2
- AS approaches can use a fast surrogate model of performance to select an algorithm, trained from instances with observed algorithm performances.Source: §2 · p. 3
- XAS assumes an extremely large candidate set and sparse training evaluations, potentially including algorithms with no observed performance values.Suitable approaches must learn from very few data and address zero-shot learning.Source: §2 · p. 3
- Unlike AC and CASH, XAS keeps its candidate set finite and requires recommendations without online evaluations at recommendation time.Source: §2 · p. 3
3 Exploiting Instance Features
Instance-feature methods use instance descriptors to model algorithm performance, either by predicting scores, ranking candidates, or factorizing sparse performance data.
3 Exploiting Instance Features
- Instance-specific selection assumes problem instances can be represented by feature vectors that support learning a surrogate model.The feature representation can be paired with different data types and loss functions.Source: §3 · pp. 3–4
3.1 Regression
- Per-algorithm regression models require precise performance values and can degrade sharply when sparse data leave algorithms with few or no training examples.Predicting absolute performance is sufficient but not necessary for ranking algorithms by expected performance.Source: §3.1 · p. 4
3.2 Ranking
- Label ranking learns algorithm orderings from instance features, and Plackett-Luce models fit probabilities over those rankings rather than absolute performance errors.The ranking data require qualitative comparisons instead of real-valued performance estimates.Source: §3.2 · pp. 4–5
3.3 Collaborative Filtering
- Collaborative filtering factorizes a sparse performance matrix into latent instance and algorithm features, enabling utility estimates for unobserved instance–algorithm pairs.Alors uses NDCG as a ranking loss that gives greater weight to top-ranked algorithms.Source: §3.3 · pp. 5–6
4 Dyadic Feature Representation
Dyadic feature representation combines instance and algorithm features in a joint utility model instead of fitting algorithm-specific models. Its regression and ranking adaptations can assign utilities to unknown algorithms and are suited to sparse performance matrices.
4 Dyadic Feature Representation
- Earlier approaches generalize over instances but not algorithms, motivating algorithm features to avoid separate models trained on few or no observations.The dyadic approach uses a single joint model based on instance and algorithm representations.Source: §4 · p. 6
4.1 Regression
- Dyadic regression combines instance and algorithm features into a joint representation and learns one model to estimate performance for each pair.Its feature map and model can be generic; the approach generalizes SMAC's concatenated features and random forest.Source: §4.1 · p. 7
4.2 Ranking
- Dyad ranking replaces algorithm labels with algorithm features and learns a single neural-network utility model from rankings.The network can implicitly learn a joint feature representation; dyadic methods can assign utility to unknown algorithms and suit sparse performance matrices.Source: §4.2 · pp. 7–8
5 Experimental Evaluation
The evaluation tests algorithm recommendation for unseen classification datasets under sparse training, using a benchmark with many candidate classifiers. Dyadic feature approaches outperform the standard AS methods and baselines across the reported metrics.
5.1 Benchmark Dataset
- The benchmark has 1,270 WEKA classifier configurations and 71 OpenML datasets, with 55,919 of 88,900 possible performance values observed.Performance is mean accuracy over five cross-validation folds; the authors describe accuracy as reasonable but somewhat arbitrary.Source: §5.1 · pp. 8–9
5.2 Baselines
- AvgPerformance, k-NN LR, and RandomRank provide comparison baselines; AvgRank is omitted because rankings of varying lengths make average ranks difficult to compute.Source: §5.2 · p. 10
5.3 Experimental Setup
- The setup uses 10-fold cross-validation and samples 25, 50, or 125 algorithm pairs per training instance, then tests 10 algorithms per unseen instance across 100 repetitions.The sampled training pairs yield maximum performance-matrix fill degrees of 4%, 8%, or 20%.Source: §5.3 · pp. 10–11
5.4 Performance Metrics
- Regret@k measures the gap from the actual best algorithm, NDCG@k emphasizes correct high ranks, and Kendall’s τ measures ranking correlation.Regret ranges from 0 to 1, NDCG from 0 to 1, and Kendall’s τ from −1 to 1.Source: §5.4 · pp. 11–12
5.5 Results
- With few performance values per instance, PAReg and Alors tend to fail; PAReg improves as training examples increase but never leads on a metric or setting.Alors does not improve over AvgPerformance or k-NN LR, and its NDCG variant has a slight edge over its regression variant.Source: §5.5 · p. 12
- Dyadic feature approaches outperform standard AS methods and baselines across all reported metrics; their differences are not significant, but their gains over other methods are.DFReg leads with 25 performance-value pairs, while DR has an edge at 50 and 125 pairs.Source: §5.5 · p. 12, Table 4 · p. 13
- The benchmark exhibits per-instance selection potential: AvgPerformance is worse than the oracle, and models generalize strongly despite few training examples.The results also suggest methods should address XAS’s large candidate sets and sparse training data.Source: §5.5 · pp. 12–13
6 Related Work
Related work covers per-algorithm regression models, ranking approaches, collaborative filtering, and methods that use algorithm features or latent factors.
Regression-based methods
- Regression-based methods estimate per-algorithm runtime for SAT solver selection using ridge regression and winner determination using statistical (non-)linear regression; instead learns conditional runtime models using ridge linear regression based on whether a SAT instance is presumably satisfiable.Source: §6 · pp. 13–14
Ranking approaches
- A label-ranking approach selects collaborative-filtering algorithms for recommender systems using nearest-neighbor and random-forest rankers.Source: §6 · p. 14
Feature-based and other approaches
- Related approaches use binary algorithm features for ranking over up to tens of algorithms [19], matrix factorization, SVD with a complete performance matrix [14], or survival analysis for timeouts.Source: §6 · p. 14
7 Conclusion
The evaluation finds that dyadic feature representations outperform standard-setting AS approaches across various metrics on the proposed XAS benchmark. The current algorithm features, however, support cold start only for algorithms with known hyperparameters.
7 Conclusion
- Dyadic feature approaches outperform standard-setting AS approaches across various metrics on the proposed benchmark.The benchmark uses OpenML CC-18 classification datasets and more than 1,200 candidate algorithms.Source: §7 · p. 14
- The paper proposes dyadic ranking using feature representations of both datasets and algorithms to work with very few training data.The study introduces XAS and investigates the scalability of algorithm-selection approaches in this setting.Source: §7 · p. 14
- Cold-start support is limited to new candidate algorithms whose hyperparameters are known.Describing completely new algorithms with features is identified as future work.Source: §7 · p. 14