Algorithm selection

Overview

A time-limited search has to decide how to run itself before it starts: how to estimate error, how to spend budget across candidates, and which candidates to try first. The paper's point is that the best choice depends on the dataset and on the time horizon, and that no single choice wins everywhere [arxiv:2007.04074 §1] 2007.04074 §4 2007.04074 fig. 4. The approach is to record how each option performed on many earlier datasets, then map a cheap description of a new dataset to one option 2007.04074 §4.1. The selection happens once, before the run on the new training split; the test split is used only at the end 2007.04074 §4.1.

This page covers one paper so far, so the variants below are all from Auto-Sklearn 2.0 2007.04074.

Variants

Fixed policy chosen on average (single best)

The simplest option is one policy for every dataset: the one that does best on average over the meta-datasets. The paper uses this as its baseline and calls it per-set algorithm selection 2007.04074 §4.1.1. Results: with the portfolio in place it scores 3.69 at 10 minutes and 2.44 at 60 minutes, against 3.58 and 2.47 for the selector 2007.04074 tab. 8. Card: Auto-Sklearn 2.0.

Per-dataset pairwise selector

The main method. The eight policies are the combinations of four ways to estimate error (3-, 5- and 10-fold cross-validation, and holdout) with two budget rules (successive halving or full budget) 2007.04074 §4 [arxiv:2007.04074 §4.1]. For each pair of policies, a random forest predicts which one wins on a dataset with the two meta-features, number of datapoints and number of features 2007.04074 §4.1.1. The pairwise votes are normalised into a distribution over the policies. The pair models are trained on the meta-datasets and weighted by the loss difference between the two policies 2007.04074 §4.1.1. Seven hyperparameters of this selector are tuned by Bayesian optimization on meta-data cross-validation error 2007.04074 §4.1.1 [arxiv:2007.04074 tab. 4].

Reported at 10 and 60 minutes: 3.58 ± 0.23 and 2.47 ± 0.18 normalised balanced error on 39 datasets, against 4.11 and 3.19 for PoSH Auto-sklearn and 16.21 and 7.17 for Auto-sklearn 1.0 2007.04074 tab. 5. The selector was trained on the portfolio performance table, Bayesian-optimization runs and ensembles combined, which is the configuration behind those numbers 2007.04074 tab. 6.

Backup for datasets outside the meta-data

When no meta-dataset has at least as many datapoints and at least as many features as the new dataset, the selector is not trusted. The paper falls back to holdout with successive halving, which it describes as the cheapest and most aggressive policy 2007.04074 §4.1.1. Without this fallback the selector is much worse: 4.79 instead of 3.58 at 10 minutes and 5.43 instead of 2.47 at 60 minutes, with ensembles in the meta-data 2007.04074 tab. 6. The authors say the two-feature selector can be read as learning the manual fallbacks from their first part 2007.04074 §4.1.1.

Warm-start portfolio of starting pipelines

A separate mechanism that also chooses options, this time which pipelines to try first. A greedy algorithm picks 32 candidates from a performance table built on the meta-datasets, and the online search runs these first, then switches to Bayesian optimization 2007.04074 §3.1 [arxiv:2007.04074 §3.2.1] 2007.04074 alg. 1. In every setting of the portfolio table, starting from the portfolio beats starting from Bayesian optimization or the earlier k-nearest-dataset warm start 2007.04074 tab. 2. Without the portfolio the selector scores 5.63 at 10 minutes and 3.42 at 60 minutes, against 3.58 and 2.47 with it 2007.04074 tab. 8.

Reference points: random and oracle

Random picks a policy at random. The oracle picks the best policy for each test dataset and is not achievable in practice. They bracket the selector: 8.32 and 6.18 for random, and 2.33 and 1.22 for the oracle, at 10 and 60 minutes 2007.04074 tab. 6. The gap to the oracle is large, so the selector leaves room to improve.

When to use which

The paper's setting is 208 meta-training datasets and 39 test datasets 2007.04074 §3.4.1. Its results support the following reading.

The selector does not win in every setting. Without the portfolio, the single best policy beats it at 10 minutes (5.37 against 5.63), while the selector wins at 60 minutes (3.42 against 3.61) 2007.04074 tab. 8. With the portfolio the order flips at 60 minutes (2.44 against 2.47). Differences of this size are close to the standard deviations the paper reports, so the choice between a selector and a single policy should be checked on your own data.

The paper also reports that building the selector's training data is expensive, and that the cheap portfolio-only table gives the weakest selector variant at 60 minutes 2007.04074 §4.3.1 2007.04074 tab. 6.

Among the Auto-Sklearn system comparisons, the authors report the lowest mean rank and the most best-on-dataset results across 39 datasets, with a sign test against H2O AutoML of p = .053, which is not significant at 0.05 2007.04074 tab. 9. These are author-reported results and have not been reproduced here.

Implementation sketch

The core of the selector is a pairwise vote over policies, guarded by the fallback. Variants differ in the meta-features, the pair model and the fallback; the paper's choices are noted in the comments.

# Pick a search policy for a new dataset  [arxiv:2007.04074 §4.1.1]
# Input:  n_rows, n_cols of the new dataset; pair models; meta-datasets
# Output: one weight per policy, summing to 1

def choose_policy(n_rows, n_cols, meta_data, pair_models):
    # Backup if no meta-dataset is at least this large  [§4.1.1]
    covered = any(m.rows >= n_rows and m.cols >= n_cols
                  for m in meta_data)
    if not covered:
        return backup_policy  # holdout with successive halving  [§4.1.1]
    wins = zeros(num_policies)
    # Each pair model predicts that policy a beats policy b  [§4.1.1]
    for a, b in policy_pairs:
        # Soft voting: use the probability (hard voting is also tuned)  [tab. 4]
        p_a = pair_models[a, b].predict_proba([n_rows, n_cols])
        wins[a] += p_a
        wins[b] += 1 - p_a
    # Normalise the win counts into a distribution  [§4.1.1]
    return wins / wins.sum()

The released experiment scripts differ from the text in places, for example in how the backup is applied. The paper card lists these differences. Check them before you copy the rule.

Contradictions

• Selection of the portfolio. The greedy construction and its guarantees use test-split losses, but the paper's equation for the same quantity is written on validation losses 2007.04074 eq. 9 2007.04074 §3.1.1 2007.04074 §3.1.2. The authors say test losses are acceptable when the new datasets are kept separate, and they show that choosing on validation breaks the guarantees 2007.04074 app. C.3 2007.04074 app. C.4. Implementing the written equation literally therefore changes the result.

Papers

• Auto-Sklearn 2.0: Hands-free AutoML via Meta-Learning: a per-dataset selector over eight policies, a warm-start portfolio and successive halving, evaluated on 39 AutoML benchmark datasets.