Year: 2021

Abstract:
This paper tackles the AutoML problem, aimed to automatically select an ML algorithm and its hyper-parameter configuration most appropriate to the dataset at hand. The proposed approach, MetaBu, learns new meta-features via an Optimal Transport procedure, aligning the manually designed meta-features with the space of distributions on the hyper-parameter configurations. MetaBu meta-features, learned once and for all, induce a topology on the set of datasets that is exploited to define a distribution of promising hyper-parameter configurations amenable to AutoML. Experiments on the OpenML CC-18 benchmark demonstrate that using MetaBu meta-features boosts the performance of state of the art AutoML systems, AutoSkLearn (Feurer et al. 2015) and Probabilistic Matrix Factorization (Fusi et al. 2018). Furthermore, the inspection of MetaBu meta-features gives some hints into when an ML algorithm does well. Finally, the topology based on MetaBu meta-features enables to estimate the intrinsic dimensionality of the OpenML benchmark w.r.t. a given ML algorithm or pipeline.

heading: 1 INTRODUCTION
text: Getting the peak performance of an algorithm portfolio on a particular problem instance is acknowledged a main bottleneck in domains ranging from Constraint Programming and Satisfiability to Machine Learning (Rice, 1976; Hutter et al., 2009; Stern et al., 2010; Kotthoff, 2014; Bergstra et al., 2011; Feurer et al., 2015; Hazan et al., 2018; Fusi et al., 2018; Yang et al., 2019). Early approaches have been investigating the use of general performance models (Rice, 1976), estimating a priori the performance of any algorithm on any problem instance, where each problem instance is described by a vector of so-called meta-features, and the performance model is learned in this meta-feature space.
In the context of supervised Machine Learning, many meta-features have been manually designed to describe datasets (Caliński & Harabasz, 1974; Vilalta, 1999; Bensusan & Giraud-Carrier, 2000; Pfahringer et al., 2000; Peng et al., 2002; Ali & Smith, 2006; Song et al., 2012; Bardenet et al., 2013; Feurer et al., 2014; 2015; Pimentel & de Carvalho, 2019; Lorena et al., 2019). After a series of international AutoML challenges, aimed to automating the selection and tuning of ML pipelines1 (Hutter et al., 2019; Guyon et al., 2019), it seems that a general accurate performance model can hardly be based on these meta-features (Misir & Sebag, 2017) (Section 2): for instance the challenge-winner AutoSkLearn (Feurer et al., 2015) relies on Bayesian optimization and iteratively learns and exploits one performance model specific to the dataset at hand; PMF (Fusi et al., 2018) uses a probabilistic collaborative filtering approach, where the cold-start problem is handled as in AutoSkLearn; OBOE (Yang et al., 2019) likewise uses a collaborative filtering approach, combined with active learning.
Nevertheless, the definition of good meta-features remains desirable for two reasons. The first motivation remains to achieve AutoML with a decent performance vs cost trade-off. Relevant meta-features are expected to define a reliable topology on the dataset space, such that two datasets are close iff the best hyper-parameter configurations for these datasets are close. Such a topology would support an inexpensive and efficient AutoML strategy: selecting the best hyper-parameter configurations of the nearest neighbor(s) of the current dataset. The second motivation is to better understand the dataset space w.r.t. a given ML algorithm, to estimate its intrinsic dimension and to appreciate the distribution of the ML benchmark suites thereon.
1An ML pipeline consists of a data preparation stage followed by the model learning stage. Each stage involves a number of options and a varying number of hyper-parameters, depending on the former selected options. Terms ML pipeline and ML algorithm will be used interchangeably in the remainder of the paper.
This paper presents the Meta-learning for Tabular Data (METABU) approach, formalizing and tackling the construction of good meta-features relatively to an ML algorithm A as an Optimal Transport (OT) problem (Cuturi, 2013; Peyré & Cuturi, 2019). Formally, METABU considers two representations of the datasets: the basic one consists of 135 manually designed meta-features (Appendix E). The target one, out-of-reach except for the datasets in the benchmark suite, represents a dataset as the distribution of the hyper-parameter configurations of A yielding the top performances for this dataset. Optimal Transport is used to find a linear transformation of the basic meta-features, such that the resulting Euclidean distance emulates the Wasserstein-Gromov distance (Mémoli, 2011) on the target representation (Section 3). Overall, Metabu learns once for all new meta-features, aimed to capture the topology and neighborhoods corresponding to the target representation. These meta-features can be computed from scratch for each new dataset. This approach contrasts with Yang et al. (2019) and Fusi et al. (2018) that both require a cold-start phase, launching configurations for each new dataset and using their performance to find the representation of the new dataset.
The contribution of METABU is threefold. Firstly, the METABU meta-features define an efficient topology, that can be used to sample the most promising hyper-parameter region for new datasets. Secondly, the relevance of these meta-features is demonstrated as they can be used as representation space to initialize AutoSkLearn (Feurer et al., 2014) and PMF (Fusi et al., 2018): the hybrid approaches AutoSkLearn+METABU and PMF+METABU, are shown to significantly outperform AutoSkLearn and PMF on the OpenML CC-18 (Bischl et al., 2019) benchmark. Lastly, the approach provides some hints into the AutoML problem, enabling to estimate the intrinsic dimensionality (Facco et al., 2017) of the dataset space w.r.t. an ML algorithm: the higher the dimensionality, the more complex the algorithm. It is interesting to compare the intrinsic dimensions of the OpenML CC18 w.r.t. AutoSkLearn (Feurer et al., 2015), SVM (Boser et al., 1992), or Random Forest (Breiman, 2001). Furthermore, the METABU meta-features can be inspected and confirm some "tricks of the trade" about when an algorithm does well.
The paper is organized as follows. Section 2 briefly discusses related work and introduces OT formal background for the sake of self-containedness. Section 3 describes the METABU algorithm. In Section 4, the merits of the METABU meta-features are empirically demonstrated on configuration selection and optimization tasks, comparatively to the state of the art. Lastly, we discuss how the METABU meta-features provide an interpretable description of the niche of the considered ML algorithms.

heading: 2 RELATED WORK AND FORMAL BACKGROUND
text: AutoML & meta-features Most ML meta-features (Caliński & Harabasz, 1974; Vilalta, 1999; Bensusan & Giraud-Carrier, 2000; Pfahringer et al., 2000; Peng et al., 2002; Ali & Smith, 2006; Song et al., 2012; Bardenet et al., 2013; Feurer et al., 2015; 2014; Pimentel & de Carvalho, 2019; Lorena et al., 2019) have been manually designed to describe supervised datasets based on descriptive statistics, information theory (quantifying relationships among features/labels), geometrical structure of the dataset, and landmarking (performance of cheap classifiers such as linear discriminant and decision trees). In the neighbor fields of Satisfiability or Constraint Programming, circa one hundred meta-features have also been manually designed (Nudelman et al., 2004; Xu et al., 2008). In contrast to the efficiency of SAT or CP meta-features however (Kotthoff, 2014), the AutoML search can hardly rely on the only metric defined from the ML meta-features after (Misir & Sebag, 2017; Muñoz et al., 2018); in practice, they are often used to initialize the optimization search (Feurer et al., 2015).
Another approach is to learn meta-features, e.g. by making strong assumptions on the performance model (Hazan et al., 2018) or by leveraging distributional neural networks (de Bie et al., 2019; Maron et al., 2020). In the latter case, these meta-features are functions of the dataset distribution and consist of the last layer of a distributional NN trained in view of a particular task. Dataset2Vec (Jomaa et al., 2021) learns meta-features to detect whether two data patches (subset of samples described by a subset of features) are extracted from the same whole dataset. OTDD (Alvarez-Melis & Fusi, 2020) uses OT to learn a mapping over the joint feature and label spaces. A significant drawback of distributional neural network approaches, limiting their ability to handle general tabular datasets (with widely varying number of features, missing values, heterogeneous variables) is due to the shortage of training (meta)-samples. Neural networks notoriously need large amounts of samples to be efficiently trained, while AutoML benchmarks include less than a hundred datasets. For this reason, the proposed METABU approach proceeds by building upon existing meta-features.
Optimal Transport Let (Ωx, dx) and (Ωy, dy) denote compact metric spaces, and x and y distributions2 respectively defined on Ωx and Ωy . The search space Γ(x, y) is the space of all distributions on Ωx × Ωy with marginals x and y. Let the transport cost function c : Ωx × Ωy 7→ IR+ be a scalar function on Ωx × Ωy3. The OT problem consists in finding a distribution in Γ(x, y) yielding a minimal transport cost expectation (Peyré & Cuturi, 2019); this minimal transport cost expectation defines the Wasserstein distance of x and y: dqW (x, y) = min
γ∈Γ(x,y) IE(x,y)∼γ [c
q(x, y)]1/q , with q a positive real number, set to
2 in the following. Another OT-based distance is the Gromov-Wasserstein distance (GW) (Mémoli, 2011), measuring how well a distribution in Γ(x, y) preserves the distances on both Ωx and Ωy, akin a rigid transport between both domains: dqGW (x, y) = min
γ∈Γ(x,y) IE(x,y)∼γ,(x′y′)∼γ [|dx(x, x′)− dy(y, y′)|q]1/q .
The Fused Gromov-Wasserstein (FGW) distance (Titouan et al., 2019) combines both these distances.
Definition 1 The Fused q-Gromov-Wasserstein distance is defined on Ωx × Ωy as follows:
dqFGW ;α(x, y) = min γ∈Γ(x,y) (1− α)  ∫ Ωx×Ωy cq(x, y)dγ(x, y)  1 q
︸ ︷︷ ︸ Wasserstein Loss
+ α  ∫ Ωx×Ωy ∫ Ωx×Ωy |dx(x, x′)− dy(y, y′)|qdγ(x, y)dγ(x′, y′)  1 q
︸ ︷︷ ︸ Gromov-Wasserstein Loss
(1)
α ∈ [0, 1] is a trade-off parameter: For α = 0 (resp. α = 1), the fused q-Gromov-Wasserstein distance is exactly the q-Wasserstein distance dqW (resp. the q-Gromov-Wasserstein distance d q GW ).
The Wasserstein distance and variants thereof have been successfully used to evaluate the "alignment" among datasets, e.g. between the source and the target datasets in the context of domain adaptation (Courty et al., 2017) or transfer learning (Alvarez-Melis & Fusi, 2020). FGW distance has been used to enforce the consistency of the latent space when jointly training several Variational Auto-Encoders (Xu et al., 2020; Nguyen et al., 2020). METABU will likewise take inspiration from OT to create a bridge between two representations of the datasets: the basic one, and the target one, critically using both GW and FGW distances.

heading: 3 OVERVIEW OF METABU
text: Let A and ΘA respectively denote an ML pipeline and its hyper-parameter configuration space; subscript A is omitted when clear from the context. Space Θ is embedded into the a-dimensional real-valued space IRa, using a one-hot encoding of Boolean and categorical hyper-parameters. After describing the principle of the approach, some key issues are detailed: the augmentation of the AutoML benchmark to avoid overfitting, and the setting of the number d of the METABU metafeatures, estimated from the intrinsic dimensionality of the AutoML benchmark suite.
Principle. Intuitively, two representations can be associated with a dataset: The basic representation x ∈ IRD of a dataset reports the values of the D manually designed meta-features for this dataset. By construction, it can be cheaply computed for any dataset. The target representation z of a dataset is the distribution on the space Θ supported by the configurations yielding the best performances on this dataset. This precious target representation is unreachable in practice, but can be approached after the performances of the models learned with a number of configurations (aka
2Distributions will be denoted in boldface 3When Ωx = Ωy = Ω, unless otherwise stated, the transport cost c(x, y) is the Euclidean distance d(x, y).
configuration performances) have been assessed. In practice, the configuration performances are only available for a small number n of datasets (more below). The difference between the basic and the target topologies is depicted on Fig. 1, in Θ space (projected on first two PCA eigenvectors).
In order to build a bridge between both representations, let us consider an intermediate representation derived from the target representation, mapping each (zi)1≤i≤n on some ui ∈ IRd using a distance-preserving projection, e.g. Multi-Dimensional Scaling (MDS) (Cox & Cox, 2001). METABU tackles an Optimal Transport problem so as to learn a mapping ψ : IRD 7→ IRd from the basic representation on the projected target representation space such that the ψ(xi)1≤i≤n are aligned with the uis in the sense of the q-Fused Gromov-Wasserstein distance (Section 2). In brief, mapping ψ sends the basic meta-feature space on IRd, such that the Euclidean metric on the ψ(xi) reflects the Euclidean metric on the uis, itself reflecting the metric on the target zis. The descriptive features of the ψ(xi), referred to as METABU meta-features, are meant to both be cheaply computable from the basic meta-features, and define a Euclidean distance conducive to the AutoML task.
Augmenting the AutoML benchmark. The OpenML CC-18 (Bischl et al., 2019), to our knowledge the largest curated tabular dataset benchmark (that will be used in the experiments), contains n = 72 classification datasets; the target representation is available for 64 of them. The shortage of such datasets yields a risk of overfitting the learned meta-features. This challenge is tackled by augmenting the OpenML CC-18 benchmark suite, using a bootstrap procedure (Efron, 1979).4 The goal is to pave the meta-feature space more densely and more accurately than through e.g., perturbing the basic representation with Gaussian noise (the visualization of the augmented benchmark is displayed on Fig. 6, Appendix A).
The algorithm The algorithm is provided the p = 1, 000× n training datasets of the benchmark suite, augmented as described above (pseudo-code in Appendix B). The METABU meta-features are constructed in a 3-step procedure, illustrated on Fig. 2:
Step 1: Target representation and Wasserstein distance. Considering the i-th training dataset, let Θi ⊂ T denote the set of hyper-parameter configurations with performance in the top-L known configuration performances (L = 20 in the experiments).5 The target representation zi of the i-th dataset is the discrete distribution with support Θi. The distance d2W (zi, zj) is the 2-Wasserstein distance among distributions (Section 2).
Step 2: Projecting the target representation on IRd. The second step consists in projecting the zis on IRd, where d is identified using an intrinsic dimensionality procedure (details below), using Multi-Dimensional Scaling (Cox & Cox, 2001), such that the distance d(ui, uj) approximates the 2-Wasserstein distance d2W (zi, zj) (Fig. 2, leftmost and second subplots). Note that by construction, the uis are defined up to an isometry on IRd.
Step 3: Learning the METABU meta-features. Let x = 1p ∑p i=1 δxi denote the uniform discrete distribution on IRD whose support is the set of p datasets using their basic representations. Let u = 1n ∑n i=1 δui denote the uniform discrete distribution on IR
d whose support is the set of uis defined above. The METABU meta-feature space is built by finding a mapping ψ from IRD on IRd
4For each `-size dataset E in the benchmark suite, K = 1, 000 new datasets F1, . . . FK are generated, where Fi includes ` examples selected in E uniformly with replacement. The basic representation of Fi is computed, and its target representation is set to that of E.
5Early attempts to define Θi in a more sophisticated way, e.g. using t-test to distinguish the "good" configurations from the others, led to an uninformative target representation. A tentative interpretation for this fact is that quite a few OpenML datasets are very easy, leading to retain all configurations for these datasets and blurring the target representation.
that pushes the representation metric on IRd, that is, such that the image of x via ψ is as close as possible to u, and reflects its topology in the FGW sense (Fig. 2, rightmost and third subplots).
Formally, let ψ]x def = 1p ∑p i=1 δψ(xi) be the push-forward distribution of x on IR
d for a given ψ. The overall optimization problem is to find a mapping ψ∗ that minimizes the FGW distance between the u distribution and the push distribution ψ∗#x:
ψ∗ = arg min ψ∈Ψ dFGW ;α (ψ]x,u) + λ‖ψ‖ (2)
with λ the regularization weight and ‖ψ‖ the norm of the ψ function. Note that, as u and ψ#x are distributions on the same space IRd, the transport cost c is the Euclidean distance on IRd.
In the following, only linear mappings ψ are considered for the sake of avoiding overfitting and facilitating the interpretation of the METABU meta-features w.r.t. the manually designed meta-features. The norm of ψ is set to the L1 norm of its weight vector.
Taking inspiration from Xu et al. (2020), the efficient optimization of Eq. 2 is achieved using a bilevel optimization formulation. For a given ψ, the inner optimization problem consists of minimizing dFGW,α(ψ]x,u) (Eq. 1). This problem is solved using a proximal gradient method (Xu et al., 2019), along an iterative approach: given an estimation of the transport map γ(t), a sub-problem is defined to refine γ, it is solved using the Sinkhorn algorithm (Cuturi, 2013), and its solution is used to compute γ(t+1) (the number of iterations is set to 10 in the experiments). The outer optimization problem consists of optimizing ψ: The transport matrix γ is treated as a constant, and the outer objective function (Eq. 2) is solved with ADAM optimizer (Kingma & Ba, 2015) with learning rate 0.01, α = 0.5 and λ = 0.001.
Intrinsic dimension of the space of datasets The main hyper-parameter of METABU is the number d of meta-features needed to approximate the target representation. Indeed, d depends on the considered algorithm A: the more diverse the target representations associated with datasets, the harder the AutoML problem, the higher d needs to be. In the other extreme case (all datasets have similar target representations), the AutoML problem becomes trivial.
To our best knowledge, measuring the intrinsic dimension of the dataset space w.r.t. a learning algorithm has not been tackled in the literature. The approach proposed to do so builds on Levina & Bickel (2005) and (Facco et al., 2017), exploiting the fact that the number of points in a hypersphere of radius r in dimension d increases like rd.6 It is commonplace to say that the good distance between any two items depends on the considered task. The original approach used in METABU in order to estimate the intrinsic dimensionality of the dataset space, is to set the distance of two datasets to the 2-Wasserstein distance among their target representations.
6Formally, to each sample x is associated its first and second nearest neighbors, respectively noted x(1)
and x(2) and let µ(x) = d(x,x (1))
d(x,x(2)) be the ratio of their distances to x. With no loss of generality, the samples
are ordered by decreasing value of µ (µ(xi) > µ(xi+1)). Let d be the slope of the linear approximation of the 2D curve defined by {(−log(µ(xi)),−log(1− i/(m + 1)), 1 ≤ i ≤ m}. Then d provides a guaranteed approximation of the intrinsic dimensionality of the manifold where the xis family lives (Facco et al., 2017).

heading: 4 EXPERIMENTS
text: All material (code, data, instructions) is made available as part of the supplementary material. Runtimes are measured on an Intel(R) Xeon(R) CPU E5-2660 v2 @ 2.20GHz.

heading: 4.1 EXPERIMENTAL SETTINGS
text: Goals of experiment. The first goal is to assess the dataset neighborhoods induced by the METABU meta-features (constructed on the top of the manually designed 135 meta-features from the literature) and the relevance of these dataset neighborhoods w.r.t. the AutoML problem. The performances are assessed against three baselines: AutoSkLearn meta-feature set (Feurer et al., 2014), Landmark (Pfahringer et al., 2000) and SCOT (Bardenet et al., 2013) meta-feature sets. All meta-feature sets are detailed in Appendix E. For Tasks 2 and 3 (see below), an additional baseline is based on the uniform sampling of the hyper-parameter configuration space, for sanity check. The second goal of experiments is to assess the sensitivity of METABU w.r.t. its own two hyperparameters, the weight α used to balance the importance of the Wasserstein and Gromov-Wasserstein distances in FGW (Eq. 1), and the regularization weight λ involved in the optimization of ψ (Eq. 2). The third goal is to gain some understanding of the dataset landscape, and see whether the METABU meta-features give some hints into when a given ML algorithm or pipeline does well (its niche).
Performance indicators. Three tasks are considered to investigate the relevance of the METABU meta-features. The performance indicators are measured using a Leave-One-Out process (detailed in Appendix C).
Task 1: Capturing the target topology. For each test dataset, one considers its nearest neighbors w.r.t. the target topology (the 2-Wasserstein metric on the target representation), and its nearest neighbors w.r.t. the Euclidean distance on the METABU and meta-feature sets. The alignment between both ordered lists is measured using the normalized discounted cumulative gain over the first k neighbors (NDCG@k) (Burges et al., 2005), with 5 ≤ k ≤ 35. The performance indicator is the NDCG@k averaged on test datasets.
Task 2: AutoML with no performance model (Initialization). For each test dataset and each metafeature set mf , let zmf be the distribution on the considered hyper-parameter configuration space:
zmf = 1
Z 10∑ i=` exp(−`) z`
where z` is the target representation of the `-th neighbor of the dataset w.r.t. Euclidean distance on the mf space, and Z a normalization constant. This distribution is used to iteratively and independently sample the hyper-parameter configurations, and the performances of the learned models are measured. Letting r(t,mf) denote the rank of the performance associated with meta-feature set mf after t iterations, the performance curves report r(t,mf) for the METABU and baseline meta-feature sets (plus a uniform hyper-parameter configuration sampler for sanity check), averaged over the test datasets.
Task 3: AutoML with performance model (Optimization). AutoML systems based on performance models cannot be directly compared with METABU as they acquire additional information along the AutoML search: they iteratively use a performance model to select a hyper-parameter configuration, and update the performance model using the performance of the selected configuration. In Task 3, the relevance of meta-feature sets is investigated in that they govern the initialization for AutoSkLearn and PMF performance models. The performance indicator is the rank of the performance obtained by AutoSkLearn using METABU meta-features to initialize its performance model, noted METABU+AutoSkLearn (respectively, the rank of the performance of PMF using METABU meta-features to initialize its performance model, noted METABU+PMF).
The difference between Tasks 2 and 3 can be viewed in terms of Exploration vs Exploitation: getting a good performance on Task 2 requires to identify a sweet configuration spot for each dataset (Exploitation). Quite the contrary, getting a good performance on Task 3 requires to identify a sufficiently good and diverse configuration region, such that the search initialized in this region,
gathering additional information about the performance of new configurations on the current dataset along time, eventually yields an even better configuration (Exploration).
Benchmarks. The considered AutoML benchmark is the OpenML Curated Classification suite 2018 (Bischl et al., 2019), including 72 binary or multi-class datasets out of which 64 have enough learning performance data to give a good approximation of their target representation. The performance indicators are measured using Leave-One-Out (details in Appendix C). The basic meta-features are computed for each dataset using the open source library PyMFE (Alcobaça et al., 2020).
METABU is validated in the context of three ML algorithms: Adaboost (Freund & Schapire, 1997), RandomForest (Breiman, 2001) and SVM (Boser et al., 1992), using their scikit-learn implementation (Pedregosa et al., 2011); and two AutoML pipelines, AutoSkLearn (Feurer et al., 2015) and PMF (Fusi et al., 2018). The associated hyper-parameter configuration spaces are detailed in Appendix D.
For Adaboost, RandomForest and SVM, the target representation of each training dataset is based on the top-20 configurations in OpenML (out of 37,289 for Adaboost, 81,336 for RandomForest and 37,075 for SVM), initially generated by van Rijn & Hutter (2018). For AutoSkLearn, the target representation is generated from scratch, running 500 configurations per training dataset and retaining the top-20. For PMF, the top-20 configurations are extracted from the collaborative filtering matrix for each training dataset (Fusi et al., 2018).

heading: 4.2 COMPARATIVE EMPIRICAL VALIDATION OF METABU
text: The performances of METABU and the baselines on the three tasks are displayed on Fig. 3. The overall CPU cost on Task 2 (resp. Task 3) is circa 1,900 (resp. 2,300) hours (full runtimes in Fig. 7). Appendix H reports the detailed results in Tables 6,7 and 8, indicating the confidence level of the results after a Wilcoxon rank-sum test for performances and Mann Whitney Wilcoxon test for ranks.
Task 1: Capturing the target topology, Fig. 3a. The results show that the metric based on the METABU meta-features better matches the target topology than the metric based on the baseline meta-feature sets, all the more so as the number k of nearest neighbors increases. The higher variance of NDCG@k for METABU is explained as the metric depends on the meta-feature training, while the metrics based on the baselines are deterministic. As could be expected, this variance decreases with k. Despite this variance, METABU significantly outperforms all baselines for all k and all hyper-parameter configuration spaces.
Task 2: AutoML with no performance model (Initialization), Fig. 3b. All rank curves start at 3, as five hyper-parameter configuration samplers are considered. For RandomForest, the sampler based on the SCOT meta-feature set dominates in the first 5 iterations, and remains good at all time; METABU dominates after the beginning; all other approaches but the uniform sampler yield similar performances. For Adaboost, the sampler based on the AutoSkLearn meta-feature set dominates in the first 3 iterations, and METABU is statistically significantly better than all other approaches thereafter. For SVM, METABU very significantly dominates all other approaches.
Task 3: AutoML with performance model (Optimization), Fig. 3c. In first time steps (left of the dashed bars), the performance models of AutoSkLearn or PMF are initialized using the performances of the hyper-parameter configurations sampled as in Task 2; in the following time steps, the hyperparameter configurations are sampled using the performance model. The most striking result is that the METABU+AutoSkLearn rank improves on that of AutoSkLearn (Fig. 3c, left) although they only differ in the initialization of the performance model, and the AutoSkLearn meta-feature set is optimized to Task 3. Likewise, the rank of METABU+PMF improves on that of PMF (Fig. 3c, right). The comparison also involves Random2× and Random4× uniform samplers, respectively returning the best performance out of 2 or 4 uniformly sampled configurations (Fusi et al., 2018); METABU+PMF significantly improves on Random4× after the 10th iteration. This suggests that on the OpenML benchmark, the METABU meta-features efficiently enable both to passively sample the hyper-parameter configuration space, and to retrieve the configurations best appropriate to update the performance model and explore good regions of the space.
4.3 SENSITIVITY ANALYSIS
The own two hyper-parameters of METABU are the α trade-off parameter between Wasserstein and GromovWasserstein distance (Eq. 1) and the regularization weight λ (Eq. 2). The sensitivity of METABU w.r.t. both parameters is investigated on Task 1, by inspecting the difference NDCG@10(METABU) - NDCG@10(AutoSkLearn) for α ranging in {0.1, 0.3, 0.5, 0.7, 0.99} and λ in {10−1, . . . , 10−4}. The result, displayed in Fig. 4, shows that the difference is positive in the whole considered domain, with NDCG@10(METABU) statistically significantly better than NDCG@10(AutoSkLearn) according to Student t-test with p-value 0.05.
Interestingly, a low sensitivity of METABU is observed w.r.t. the regularisation weight λ, provided that it is small enough (λ ≤ 10−3). For such small λ values, a low
sensitivity is also observed w.r.t. α in a large range (.3 ≤ α ≤ .7). This result confirms the importance of taking into account both the Wasserstein and Gromov-Wasserstein distances on the target representation space: discarding the former (α ≤ .1) or the latter (α ≥ .99) significantly degrades the performance, and the performance is stable in the [.3, .7] region.

heading: 4.4 TOWARD UNDERSTANDING THE DATASET LANDSCAPE
text: A first original result is to provide a principled estimate of the intrinsic dimension of the dataset space w.r.t. the considered ML algorithms. As detailed in Appendix G.1 with a stability analysis, the intrinsic dimension d of the OpenML benchmark is circa 6 for AutoSkLearn, 8 for Adaboost, 9 for RandomForest and 14 for Support Vector Machines. As d reflects by construction how diverse the datasets are w.r.t. the ML algorithm, it is interesting to see that the most flexible AutoSkLearn ML pipeline corresponds to the lowest intrinsic dimension. METABU also delivers some insights into what matters in the dataset landscape, and why a given algorithm should behave better than another on a particular dataset, as follows. The images ψ(xi) of datasets according to the
METABU meta-features learned in the context of an algorithm A are processed using PCA, and the importance of a manually designed meta-feature is measured from the norm of its projection iA(mf) on the first PCA axis.
Two ML algorithms or pipelines A and B can thus be visually compared, by plotting each metafeature as a 2D point with coordinates (iA(mf), iB(mf)). As shown on Fig. 5, with respectively A set to RandomForest and B to Adaboost, one sees that actually few features matter for both RandomForest and Adaboost (the features nearest to the upper right corner), mostly the Dunn index (Dunn, 1973) and the features importance. Some findings reassuringly confirm the practitioner’s expertise: the percentage of instances with missing values matters much more for Adaboost than for RandomForest; the class imbalance (ClassProbabilityMax and ClassProbabilityMin) matters for Adaboost. Complementary results (Appendix G.2) show that the sparsity of the data matters for Support Vector Machines. Some other findings are less expected, e.g. the importance of the data density, minimal skewness and kurtosis for AutoSkLearn; these findings are tentatively explained from the fact that AutoSkLearn includes classifiers such as Linear Discriminant or Logistic Regression.

heading: 5 CONCLUSION AND PERSPECTIVES
text: METABU provides an algorithm-dependent way to achieve AutoML, through learning meta-features as linear combinations of the manually designed meta-features of the literature, optimized to capture both the top configurations for the datasets and their topology, via preserving their Wasserstein and Gromov-Wasserstein distances. The efficiency of the approach is empirically demonstrated as the METABU meta-features contribute to outperform strong baselines, including AutoSkLearn (Feurer et al., 2014) and PMF (Fusi et al., 2018).
An interesting side-product of the approach is to shed some light on the complexity of the AutoML problem, by estimating the intrinsic dimension of the dataset landscape. Surprisingly, this intrinsic dimension is relatively modest (< 14). While this result is comforting when considering the small number of datasets in the AutoML benchmarks, it should however be taken with a grain of salt: the intrinsic dimension might merely reflect the specifics of the OpenML benchmark, as the datasets might have been selected over the years to provide evidence for the merits of mainstream ML algorithms while discarding too hard datasets.
A perspective for further research is to assess the validity of the proposed meta-features and the stability of intrinsic dimensions on other AutoML benchmarks: the underlying question is to which extent AutoML, too, is prone to overfitting.
Another perspective is to exploit METABU to conduct a comprehensive empirical assessment of a new algorithm A on a time budget, by alternatively learning the meta-features relative to A, and selecting the datasets most diverse according to these meta-features, in the spirit of experiment design.
ETHICS STATEMENT
The approach is not concerned with privacy and confidentiality of the data. The AutoML goal aims to reduce the computational resources needed to get the peak performance from an ML portfolio of algorithms or pipelines.

heading: A THE AUGMENTED OPENML BENCHMARK SUITE
text: The visualisation of the augmented benchmark (Fig. 6, projected using tSNE (van der Maaten & Hinton, 2008) on the basic representation), shows that the datasets built by bootstrapping of some initial dataset E form a cluster close to E (as could have been expected as the manually designed meta-features are stable under small stochastic variations), and separated from the clusters generated from other datasets, suggesting that the initial benchmark suite only sparsely paves the basic metafeature space. Complementary experiments (omitted) with perplexity ranging in [5, 10, 15, 25, 30, 40, 50] show that clusters generated by augmentation of different OpenML datasets keep staying far apart from one another.

heading: B PSEUDO CODE OF METABU
text: The learning procedure of METABU is described in Alg. .1, detailing the description presented in Section 3 of the main paper. The density on the hyper-parameter space, used to sample hyperparameter configurations for a given dataset depending on the considered meta-features (involved in Tasks 2 and 3) is presented in Alg. .2.
Algorithm .1: Learning METABU meta-features Data: Set of n training datasets, each represented with its basic representation (meta-feature
vector) xi and its target representation (set of top 20 hyper-parameters) zi for i = 1 . . . n.
Result: Embedding layer ψ∗
// Build projected target representation 1 Ci,j ← d2W(zi, zj) for i = 1 . . . n, j = 1 . . . n; /* Pairwise Wass. Dist. */ 2 Estimate intrinsic dimension d from matrix C using (Facco et al., 2017); 3 u←MDS(C, d) ; /* Multidimensional Scaling */ // Learn ψ 4 ψ ← Linear(135, d) ; /* 135 basic meta-features. */ 5 x← 1p ∑n i=1 δxi ; 6 L ← FGW as defined in Eq. 1; 7 ψ∗ ← ADAM(L, ψ]x,u);
Algorithm .2: Fit_density Data: Set of n training datasets, each represented with its meta-feature vector mf i and its set of
top 20 hyper-parameters Θi for i = 1 . . . n. Test dataset represented with its meta-feature vector mf .
Result: Distribution of configurations zmf . 1 Ordering training datasets with `: ||mf −mf`|| < ||mf −mf`+1|| for ` = 1 . . . n; 2 zmf = 1Z ∑10 i=` exp(−`) ∑ θ∈Θ` θ;

heading: C MEASURING PERFORMANCE INDICATORS
text: As said, the OpenML benchmark includes 72 datasets, with only 64 of them having a target representation. The other 8 datasets are too heavy (e.g. ImageNet) to launch the many runs required to estimate their target representation.
For Task 1, the performance indicator is measured along a Leave-One-Out procedure, with 64 folds: in each fold, all datasets but one are used to train the METABU meta-features; the NDCG@k is measured on the remaining dataset. Eventually, the NDCG@k are averaged over all 64 folds.
For Tasks 2 and 3, the performance indicator is likewise measured using a Leave-One-Out procedure with 64 folds. The difference is that besides the remaining dataset, the 8 datasets with no target representation at all are also used as test datasets.
In Tasks 2 and 3, the performance associated with a hyper-parameter configuration for a dataset is computed after training the model on 1 CPU with time budget of 15 mn, with memory less than 8Gb, using the train/validation/test splits given by OpenML; the validation score is estimated using a 5-CV strategy.
In Task 2, for each test dataset and set of meta-features:
• The distribution
zmf = 1
Z 10∑ i=` exp(−`)z`
is defined, with z` the target representation of the `-th neighbor of the considered dataset, among the training datasets, according to the Euclidean distance based on the meta-features.
• For 1 ≤ t ≤ T , a hyper-parameter configuration is independently drawn from zmf , and a model is learned using this configuration;
• The performance of this model is measured on a validation dataset;
• The model with best validation performance up to iteration t is retained for each meta-feature set;
• The rank r(t,mf) is determined by comparing the performance on the test set, of the models retained for each meta-feature set.
• The performance curve reports r(t,mf), averaged over test datasets.
In Task 3, the meta-features are used to initialize the performance model:
• In AutoSkLearn, the performance model for AutoSkLearn is initialized as follows. The best configurations for the top-10 neighbors of the current dataset are retained and run on the current dataset; their performance is used to initialize the Bayesian Optimisation search using the SMAC BO implementation Hutter et al. (2011). These top-10 neighbors are computed using the Euclidean distance on the meta-feature set. Note that AutoSkLearn meta-features have been crafted to achieve automatic configuration selection in the context of the AutoSkLearn pipeline (Pedregosa et al., 2011), thus constituting a most strong baseline on Task 3.
• For PMF, the best configurations for the top-5 neighbors of the current dataset are likewise selected; their performance is computed to fill the row of the collaborative matrix associated to the current dataset, and determine the latent representation of the current dataset. The probabilistic model learned from the matrix is used to select further hyper-parameter configurations; their performances are computed and used to refine the latent representation of the dataset.

heading: D THE HYPER-PARAMETER CONFIGURATION SPACES
text: The hyper-parameters used for Adaboost, Random Forest and SVM and their range are detailed in Tables 1 and 2. For AutoSkLearn, we only included the list of considered hyper-parameters; their ranges are detailed in AutoSkLearn (Feurer et al., 2015). The hyper-parameter space used in PMF is the same as in AutoSkLearn. The METABU implementation uses the ConfigSpace library (Lindauer et al., 2019) to manage the hyper-parameters.

heading: E LIST OF META-FEATURES
text: The list of meta-features used in the experiments is detailed in Tables 3 and 4. Meta-features are extracted with PyMFE (Alcobaça et al., 2020) except for AutoSkLearn, SCOT and Landmark meta-features which are computed from the AutoSkLearn library.

heading: F COMPUTATIONAL EFFORT
text: Fig. 7 indicates the runtime7 for pre-processing (extracting the 135 meta-features, leftmost), and for training METABU (middle). The average training time for learning one model is indicated for comparison.
7On Intel(R) Xeon(R) CPU E5-2660 v2 @ 2.20GHz.

heading: G TOWARD UNDERSTANDING THE DATASET LANDSCAPE
text: G.1 THE STABILITY OF THE INTRINSIC DIMENSION
In Table 5, we investigate how the intrinsic dimension varies when considering various numbers of datasets in OpenML. It is observed that the intrinsic dimension tends to increase with the number of considered datasets, particularly so for SVM. This suggests that the hyper-parameter configurations investigated in the OpenML benchmark are not sufficiently representative of the (good regions of the) configuration space.
G.2 INTERPRETATION: IMPACT OF THE HC META-FEATURES ON THE PERFORMANCE OF THE LEARNING ALGORITHM
METABU meta-features are built from the initial meta-features using the trained linear mapping ψ, depending on the current learning algorithm A. Accordingly, the importance of the initial, humanly defined and interpretable meta-features w.r.t. A can be estimated, shedding some light on which specifics of a dataset matter in order to give a good/bad performance with A. The importance of a meta-feature w.r.t. A is estimated as follows. Let U = {ui,j} denote the matrix made of the multi-dimensional scaling representation of the secondary representation over all datasets (section 3.2). Let v denote the first principal component of U and let j∗ be the index of the H column most contributing to v (j∗ = argmaxj |〈v, h.,j〉|). Then the importance iA(k) of the k-th initial meta-feature for the A algorithm is defined as the absolute value of ψj∗,k, that is, the weight of the k-th initial meta-feature to build the most important METABU meta-feature.
This estimate is used to visually appreciate the meta-feature importance w.r.t. two learning algorithms A and B, by depicting each k-th meta-feature in the 2D plane as the point with coordinate (iA(k), iB(k)). Intuitively, meta-features on the diagonal have the same importance for both algorithms. Meta-features far from the diagonal are much more important for one algorithm than for the other. The visualization of the meta-feature importance w.r.t. AutoSkLearn and Random Forest is displayed in Fig. 8, left. Meta-features such as KurtosisMin, LogNumberOfInstances, InverseDatasetRatio − all retained as AutoSkLearn meta-features − are critical for AutoSkLearn whereas they have no impact for RandomForest. Inversely, some features like "pb" (average Pearson correlation between class and features) matter significantly more for RandomForest than for AutoSkLearn.
Likewise, the meta-feature importance w.r.t. Support Vector Machines and Random Forest is displayed in Fig. 8, right. The skewness (mean and std over all attributes) matter significantly more for Support Vector Machines than for RandomForest. In retrospect, there is little surprise that the meta-features related to the potential difficulties of inverting the Gram matrix matter for SVM.
Overall, the impact of some meta-features for some learning algorithms is intuitive; it confirms the practitioner expertise, which is comforting.

heading: H DETAILED RESULTS
text: Detailed results of Task 2 are presented in Table 6 for Random Forest, Table 7 for Adaboost and Table 8 for SVM. We consider the Mann Whitney Wilcoxon test to assess the significance of the rankings.

heading: I PAIRWISE COMPARISONS
text: Figs. 9-11 highlight a side-by-side comparison of METABU with each baseline set of meta-features. These comparisons establish the relative improvement over each baseline, that may be lost in the general comparison, Fig. 3.
On Random Forest pipeline, METABU performs on par with SCOT meta-features. Whereas its improvement over Landmark MF is only significant between the (approximately) 8th and 23rd iteration, METABU consistently outperforms Random and AutoSkLearn meta-features along the iterations.
On Adaboost, METABU performs similarly as Landmark meta-features. Interestingly, METABU always has a better average rank than the baselines except for the first two iterations of the AutoSkLearn baseline. It is seen that the p-value is most generally below the threshold .05, establishing the statistical significance of the rank performance.
Lastly, the gaps in performance for SVM are striking. METABU consistently outperforms all the baselines meta-features with high confidence.
J SENSITIVITY ANALYSIS OF d
Table 9 reports the NDCG@k performance of METABU on Task 1 for varying values of d, showing that: i) the best results are obtained for the intrinsic dimension in the vast majority of cases; ii) the sensitivity w.r.t. d is very moderate.
The intrinsic dimension d of the OpenML benchmark is circa 6 for AutoSkLearn, 8 for Adaboost, 9 for RandomForest and 14 for Support Vector Machines.

heading: K PERFORMANCE CURVES
text: These curves, in addition to the rank results displayed in Fig. 3b, display the performance values on 10 representative datasets from OpenML CC-18, in the context of Task 2 for respectively Random Forest (Fig. 12), Adaboost (Fig. 13), and SVM (Fig. 14). At each iteration, the curve reports the average performance value with its the standard deviation (on 3 runs).

Review summaries:
The paper presents an approach, called MetaBu, for learning a meta-feature embedding from an existing meta-feature space into a latent space, which is aims at being rank preserving regarding different hyper-parameter configurations. The special kind of embedding and its property of aiming at being performance preserving in the context of AutoML is the main contribution of the paper, in my opinion. The quality of the learned meta-features is assessed through different experiments such as capturing to what degree the embedding is indeed performance preserving and how well AutoML tools perform when initialized with the corresponding meta-features. Moreover, the authors provide a sensitivity analysis of relevant hyper-parameters of MetaBu and demonstrate how to gain insights from the learned embeddings.

In this paper, the authors address the AutoML problem, which aims to automatically select the best ML algorithm and its hyperparameter configuration for a dataset, and propose an approach to this problem that learns meta-features of the dataset. The proposed method, MetaBu, learns new meta-features by optimal transport according to the space of distributions of hyperparameter configurations. Meta-features in MetaBu is known only once and induce a topology in a set of data sets. Experiments on the OpenML CC-18 benchmark have shown that MetaBu meta-features can improve the performance of the state-of-the-art AutoML systems AutoSklearn and Probabilistic Matrix Factorization. Furthermore, the examination of MetaBu meta-features provides hints on when an ML algorithm will work. Finally, a topology based on MetaBu meta-features can estimate the intrinsic dimension of the OpenML benchmark for a given ML algorithm or pipeline. 

This paper tackles the AutoML problem. It proposes to learn a linear combination of manually designed meta-features, which aligns meta-features with the space of hyper-parameter configurations via an Optimal Transport procedure. Experiments on OpenML benchmark demonstrate the power of the proposed method on boosting AutoML systems.

This paper focuses on the AutoML problem for tabular data and proposes a meta-learning based novel solution. They consider the optimal transport to define distances between two datasets, utilizing the Wasserstein-Gromov distance between the distribution of the top performing hyperparameters for the respective datasets. Given this distance, they propose learning a linear transformation of existing dataset meta-features such that the Euclidean distance between a pair of datasets in this transformed space is proportional to their Wasserstein-Gromov distance. This method is termed Metabu.  The empirical evaluation compares Metabu to existing meta-learning schemes on (i) their ability to capture the desired Wasserstein-Gromov distance, (ii) their ability to find better hyperparameters via sampling without an underlying optimizer, and (iii) their ability to find better seed hyperparameters for hyperparameter optimizers. The results on the OpenML CC-18 suite with 3 machine learning models indicate that Metabu significantly improves upon existing meta-learning schemes. The paper also demonstrates how the learned linear transformation of existing dataset meta-features allow us understand the importance of different existing dataset meta-features and how these vary between machine learning models.