This paper addresses a cornerstone of Automated Machine Learning: the problem of rapidly uncovering which machine learning algorithm performs best on a new dataset. Our approach leverages performances of such algorithms on datasets to which they have been previously exposed, i.e., implementing a form of meta-learning. More specifically, the problem is cast as a REVEAL Reinforcement Learning (RL) game: the meta-learning problem is wrapped into a RL environment in which an agent can start, pause, or resume training various machine learning algorithms to progressively “reveal” their learning curves. The learned policy is then applied to quickly uncover the best algorithm on a new dataset. While other similar approaches, such as Freeze-Thaw, were proposed in the past, using Bayesian optimization, our methodology is, to the best of our knowledge, the first that trains a RL agent to do this task on previous datasets. Using real and artificial data, we show that our new RL-based meta-learning paradigm outperforms Free-Thaw and other baseline methods, with respect to the Area under the Learning curve metric, a form of evaluation of Any-time learning (i.e., the capability of interrupting the algorithm at any time while obtaining good performance).
Meta-learning in machine learning refers to learning from prior experience on
other datasets than the current dataset of interest. There are many meta-learning
settings, including learning from Model Evaluations, learning from Task
Properties, and learning from Prior Models [
Supported by ANR Chair of Artificial Intelligence HUMANIA ANR-19-CHIA-00222. © 2021 for this paper by its authors. Use permitted under CC BY 4.0.
Our setting belongs to the family of meta-learning Model Evaluations
methods, which make use of pre-defined performance measures, e.g. test accuracy
and training time. One baseline approach is to select the algorithm performing
best on previous datasets, e.g. according to average rank [
Task Properties (meta-features) describe the characteristics of datasets.
They may include statistical information, information-theoretic measures, or
learned meta-features. In Meta-Regression, regression algorithms are used to
predict the performances of algorithms based on the meta-features of the
problems (and meta-features of the algorithms). One could estimate a classifier’s
performance by exploiting relationships between the dataset properties and the
classifier’s performance [
Learning from Prior Models usually focuses on transfer learning and
fewshot learning applied to deep learning models. While the former uses models
trained on source tasks as starting points to develop models for a new target task,
the latter aims at training a good model given very few training examples. Much
progress has been made in these settings with some state-of-the-art methods,
such as MAML [
The setting considered in this paper is active meta-learning, where an agent
actively requests to train and test algorithms to reveal their performance on a
given dataset. We fuse three ideas: (1) that of “active meta-learning” exploited in
ActivMetal [
Compared to previous approaches, we gain in speed and accuracy: Both
ActivMetal and REVEAL are computationally demanding since they require
fully training and evaluating models. Our new method using partially trained
models (along the learning curve) is thus more effective. Furthermore, ActivMetal
requires multiple computationally expensive matrix factorizations using the
entire meta-dataset of past scores. Our method based on pre-trained policies
does not require storing and using past scores on other datasets at utilization
time. Finally, Freeze-Thaw, which inspired us to use learning curves, relies on
heuristic policies derived from human expertise, not trainable agents performing
meta-learning, which is the setting considered in this paper. Other learning-curve
based methods [
Meta-learning is learning to learn. In this paper, we consider the algorithm recommendation setting of meta-learning: The goal is to find, from a set of algorithms, the algorithm performing best on a new dataset, given the experience of these algorithms on previous datasets. This experience can be embedded in a meta-dataset.
Definition 1. (Meta-dataset). A meta-dataset of m algorithms on n datasets can be expressed as a performance matrix P with a size of (m×n), where column j (for j = 1, ..., n) corresponds to algorithm Aj , row i (for i = 1, ..., m) corresponds to dataset Di, and P (i, j) is the performance score of Aj tested on Di. Definition 2. (1D Meta-Learning Problem). Given a meta-dataset P with a size of ((m − 1) × n), a new dataset Dm, and the partial performance information Im of algorithms on this new dataset Dm (which is progressively revealed at a given cost), the meta-learning problem is to find the best algorithm Aj∗ for Dm such that: j∗ = argmax P (m, j) j=1,...,n (1)
From Definition 1, we concentrate on zero-level meta-learning, as defined
in [
From Definition 2, we concentrate on 1D meta-learning. Meta-learning was
divided into 1D meta-learning and 2D meta-learning in [
In this section, we relate meta-learning problems to REVEAL games, which has
been previously discussed in [
In a REVEAL game, the agent’s action can only influence the amount of
information it can gain, not the underlying data generative process, i.e., the
agent’s actions have no influence over the course of the “world”. Consequently,
a good operational test of whether a MDP is a REVEAL game is to find out
whether it is possible to pre-compute all states and rewards a priori, before the
start of a game episode. A simple metaphor for a REVEAL game is a “game
board” covered with “cards”. Each card is associated with some information.
When the game starts, all cards are placed face down, such that the information
is hidden from game players or agents. The goal of an agent is to move around
the board and reveal the card’s information to maximize rewards received in
an episode. Examples of REVEAL games include Battleship [
Meta-learning problems can be viewed as REVEAL games where a new dataset corresponds to a new board. An action of the agent on the board is a choice of pair {training algorithm, dataset} yielding a reward based on the performance achieved by the chosen algorithm on the chosen dataset. Figure 1 shows an overview of how a meta-learning problem is related to a REVEAL game.
As an additional twist, “cards” in REVEAL games can be partially or progressively revealed. This metaphor portrays well the case in which learning machines are progressively trained, and revealing a card step-by-step corresponds to obtaining the next performance of the algorithm after training one more epoch.
Concerning the meta-datasets, this corresponds to adding one more dimension (time or number of epochs) in the meta-dataset performance matrix to store an entire learning curve as opposed to a single final score, as explained further in the next section. 3
In this section, we introduce RL-based meta-learning from learning curves, which are an essential ingredient for time management in the search for the best performing algorithm. Indeed, training all algorithms fully (to the point of reaching asymptotic training performance) is wasteful, considering that the least promising algorithms can be abandoned early on. Given a limited time budget, it is therefore preferable to probe first the performance of algorithms by training them only a few epochs, then eventually train more certain algorithms, perhaps switching back and forth as more of the learning curve is revealed. The goal of our RL agent is to uncover an optimal strategy, monitoring exploration and exploitation.
We investigate two settings, which have implications in the time management and the exploration-exploitation tradeoff: Fixed-time Learning and Any-time Learning. In the Fixed-time Learning setting, an overall time budget is given, and the goal of the agent is to find the best algorithm before the time is out. The agent can therefore explore freely within this time budget, without the need to find a good solution early on. In contrast, in the Any-time Learning setting, the agent can be stopped and judged for its performance at any time. There is therefore pressure on the agent that it finds a good solution early on and keeps improving it incrementally. Figure 2 shows a concrete example of two algorithms competing to show the difference between Fixed-time learning and Any-time learning settings. We introduce meta-learning environments designed for each setting. In the Fixed-time Learning scenario, an agent is given a total time budget T to be spent on training any algorithm in the algorithm set A. The agent’s goal is to find the best algorithm for a given dataset within the time budget. T may be varied to have the agents exposed to different conditions (e.g., T is drawn uniformly from a pre-defined set of time budgets).
Definition 3. (State). A state st is a matrix of dimensions 2 × n, which consists of two channels represented by two vectors with the same length of n. The first vector T stores the amount of time that has been spent so far for each algorithm and the second vector V represents the current test score of each algorithm (current value on the learning curve) in the current episode:
T = [tj ] f or j = 1, ..., n V = [vj ] f or j = 1, ..., n (2) (3) where n is the number of algorithms. At the beginning of an episode, all values of tj are initialized to 0 and vj to −1, to indicate that performances of algorithms Aj have not been revealed yet.
Definition 4. (Action). An action is to start/continue training an algorithm in a fixed amount of time Δt (pre-defined by the environment creator, e.g., Δt = 10 seconds) and then make predictions on the test data to receive the next test score.5 For simplicity, we define an action by the corresponding algorithm index: at = j, where j is the index of the algorithm Aj which is going to be trained and tested next. Once the action at is done, tj and vj in the state are updated to form the next state.
Definition 5. (Fixed-time Learning Reward Function). A shaping reward function based on performance improvement, which gives rewards more frequently to the agent and lets the agent knows that it is getting better and getting closer to the best algorithm:
r(t) = V ∗(t) − V ∗(t − Δt) , where V ∗(t) and V ∗(t − Δt) are the best algorithm performances found in this step and the previous step respectively: (4) (5) (6) (7) V ∗(t) = max V (k) ,
k≤t
V ∗(0) = 0 , Definition 6. (Termination condition). An episode ends when T is exhausted.
At the end of the episode, the cumulative reward is equal to V ∗(T ) − V ∗(0) = V ∗(T ), the score of the best algorithm found within the time budget T . Our agent therefore implements a meta-algorithm whose (meta)learning curve is given by V ∗(t), but it is judged only by its end result. 3.2
In the Any-time Learning setting, we want to encourage the agent to obtain a meta-learning curve, which is steep at the beginning, i.e., to uncover good algorithms as fast as possible. In this way, even if the agent is stopped early, we will get as good performance as possible, thus obtaining Any-time Learning capabilities.
States, actions, time budgets, and termination conditions are defined similarly as in Fixed-time learning. We designed a specific reward function for this type of learning: 5 Agents’ action are based on the test performance Vj, which is assumed to be accurate and a good approximation of the generalization error (i.e. we assume large test sets and very small error bars). In this work, we focus on meta-learning, hence, the problem of possibly “overfitting/underfitting the test set” is not discussed in this paper and left for future works.
Definition 7. (Any-time Learning Reward Function). This function puts more emphasis on performance improvement at the beginning of an episode. The reward is defined by: r(t) = [V ∗(t) − V ∗(t − Δt)] [(T − t)] (8)
The weight [(T − t)] is the only difference compared to the reward function in Fixed-time Learning. If we scale the x-axis logarithmically then the reward function becomes: with r(t) = [V ∗(t) − V ∗(t − Δt)] [(1 − t˜)] t˜ = log(1 + t/t0) log(1 + T /t0) (9) (10)
The larger t0 is, the more important the beginning of the learning curve is. If T t0, then t˜ → 0 and the reward function becomes equivalent to that of Fixed-time Learning (Equation 5). In our experiments, t0 is set to 50 (seconds).
At the end of the episode, the cumulative reward will be the Area under
the Learning Curve (ALC) within the time budget T . The computation of
the cumulative reward can be carried out by integrating the learning curve using
horizontal rectangles, in the style of Lebesgue integrals (Figure 3). The ALC
metric was used in the AutoDL challenge with the same purpose of emphasizing
Any-time Learning [
In this section, we first describe how the meta-datasets used in our experiments are obtained. Then, we discuss the experimental results and findings from running the implemented RL agents and baselines on the meta-datasets. The code for reproducing the experiments is available on our Github repository 6. 6 https://github.com/hungnm2008/metaREVEAL.git
We use learning curves collected from the AutoDL Challenge [
Learning curves from the AutoDL challenge [
Artificial Learning Curves. We have created an artificial meta-dataset that contains learning curves of 20 algorithms on 100 datasets. The purpose of creating these curves is to have a meta-dataset with a larger size, no missing data, and containing underlying structure indicating some groups of algorithms are good for some groups of datasets. We assume these learning curves have the S-shape-like sigmoid curves, hence, they are monotonically increasing by definition. Each learning curve of algorithm Aj on dataset Di is a sigmoid function defined by three parameters a, b and c as follows: lcij =
a 1 + e−b∗(x−c) (11)
These parameterized functions allow us to experiment with various learning curves, by adjusting their asymptotic performance (specified by a), increasing rate (specified by b), and “warm-up” time (specified by c). Values of each parameter a, b, and c are shown in matrices in Figure 7. Each matrix was constructed from a matrix factorization, which means it was obtained as a product of three matrices U ΣV where U and V are random orthogonal matrices and Σ is a diagonal matrix of “singular values”. The values are then scaled to desired range for each parameter.
(a) Parameter a (a) Parameter b (a) Parameter c Fig. 7: (Artificial meta-dataset) Hierarchically-clustered heatmaps showing values of the three parameters used to build the artificial learning curves. Blocks appear, revealing that some groups of algorithms have correlated parameter values on groups of datasets (e.g. learning curve asymptotic value, controlled by the parameter a). The learning agents are expected to learn such properties and output an effective search strategy. 4.2
In Reinforcement Learning, the goal of an agent is to find a policy that maximizes expected (discounted) rewards. Reinforcement Learning methods can be categorized into value-based, policy-based, and hybrid methods. Value-based methods learn a value function that is used to evaluate a state or a state-action pair. Then the policy is derived directly from the value function. In contrast, policy-based methods explicitly learn a representation of a policy and keep updating it during learning. Many hybrid approaches learn both value function and a policy simultaneously gain great success in RL. Actor-Critic is a well-known architecture used in these hybrid approaches, where the “Critic” computes estimated values and the “Actor” updates the policy according to the values provided by the Critic. We have chosen a diverse group of RL agents due to their characteristics and their strategies to be evaluated in our experiments:
Double Deep Q Networks (DDQN) [
Soft Actor-Critic (SAC) [
Proximal Policy Optimization (PPO) [
We compare the performance of RL agents with established baseline methods, which allow us to select an algorithm that should perform well on a novel dataset.
searching for good model hyper-parameters. It maintains a set of “frozen” models that are partially trained and takes advantage of the partial information to decide which ones to “thaw” and resume training. This avoids spending too much time on bad models, and only promising models should be exploited more. Freeze-Thaw requires hyper-parameters to be able to search for good models. However, we are working on Zero-level meta-learning, hyper-parameters are not considered in choosing an algorithm (model). We made some changes to make the Freeze-Thaw method able to run in our experiments. The performance matrix has been arranged so that similar algorithms are placed together. Then we use the algorithm index as a “hyper-parameter” that describes and represents the locality of the algorithm in the searching space.
Average Rank. Inspired by these works [
PDtrain rankji i=1
Dtrain where D is the number of training datasets, and rankji is the rank of algorithm Aj on the dataset Di. Given a new test dataset, only the algorithm with the highest global rank is selected to run with the entire time budget T . This baseline is very time-consuming in practice since it needs to try all algorithms on all datasets in training.
Best on Samples. This baseline is adapted from [
Random. This baseline performs a random search over the algorithm space. Each action is to randomly choose an algorithm for training and testing within Δt. This baseline has a very large variance. When we report results, we first average results over 5 trials of the random search method, therefore reducing its variance, and report average performance. One needs to bear in mind though that this is just for comparison purposes and in not a realistic setting (because in practice one would not average over several runs, this is impossible because once the performances of algorithms are revealed, one cannot take them back). 4.4
We train the agents in two learning scenarios: Fixed-time Learning and Anytime Learning using two meta-datasets: the AutoDL meta-dataset and the Artificial meta-dataset. Since these meta-datasets are quite small, we use k-Fold Cross-Validation with k = 4 to train and test the agents.7
To compare the agents, we use two metrics: Average Cumulative Reward and Average Switching Frequency (defined in Definition 8). The means of cumulative reward and switching frequency are calculated for each test fold. The final average cumulative reward, average switching frequency, and their corresponding standard deviations are computed over all folds.
Definition 8. (Switching Frequency). We proposed a Switching Frequency (SF) metric for evaluating how frequently an agent switches between algorithms. In an episode, the SF value of an agentk is defined as:
SF (agentk) =
PT t=1 1at6=at−Δt
T /Δt (13) with T is the total time budget, Δt is the amount of time spent for an algorithm in one step. 4.5
We discuss our experimental results in two learning scenarios and focus on two points: (i) the average cumulative reward and (ii) the correlation between average cumulative reward and average switching frequency.
Any-time learning, (Figure 8a, 8c, 10a, 9c). The results indicate that a
good strategy to be successful in Any-time learning is to bet at the beginning
on algorithms that performed well on past datasets and stick to them to climb
the learning curve fast, then start exploring. This is illustrated by the ppo agent,
which obtained the highest cumulative reward, followed by other RL agents.
7 This violates the assumption that we have large test sets made earlier and is a
limitation of this mode of evaluation.
(a) Cumulative reward in Any-time
learning
(a) Cumulative reward in Any-time
learning
They are among the algorithms with the lowest switching frequency. Their low
switching frequency can explain their success at the beginning of the learning
curve, as they favor more exploitation than exploration. In contrast, the policy
of best on samples and f reeze thaw forces agents to try each algorithm at
least once at the beginning (train and test the algorithm in Δt first seconds).
Thus, if they manage to find the best algorithm, this should happen only near
the end of the episode, which makes it less valuable in the Any-time learning
setting. This explains why they performed worst in the Any-time learning setting
in both meta-datasets. We vary the value of t0 to investigate its influence on
agents’ performances. More precisely, the value of t0 is drawn from the set:
[
(a) AutoDL meta-dataset (b) Artificial meta-dataset Fig. 10: Tuning hyperparameter t0 in Any-time learning. We compare the average accumulated reward of RL agents (in blue) and baseline methods (in orange). The x-axis shows the value of t0 on a log scale. In Any-time learning, changing t0 leads to changing the reward function. Thus, the purpose of these figures is not to show that agents achieve higher rewards when t0 increases. The key finding is that the performance difference between RL agents and baseline methods gets larger as t0 increases, indicating that RL agents can learn better when we emphasize more on the any-time learning capability (with a high value of t0). The difference is more obvious in the Artificial meta-dataset, which can be explained by the chosen time budget T . In the AutoDL meta-dataset, the time budget T of 512 is large enough for the baseline methods to maintain the difference with the RL agents when t0 increases, which is not the case in the Artificial meta-dataset.
Fixed-time learning, (Figure 8b, 8d 10b, 9d). In both meta-datasets, the winner is a RL agent. In the AutoDL meta-datasets, RL agents achieved higher cumulative rewards than the baselines. However, in the Artificial meta-dataset, there was no significant difference between all agents. Within the given time budget T , all agents managed to find a good algorithm at the end. This emphasizes the fact that learned policies to manage time budget are mostly beneficial in the Any-time learning setting, where monitoring the exploration-exploitation tradeoff is critical.
Comparison between datasets. The AutoDL meta-dataset has a clear block structure in the vertical (dataset) direction, which means there is some algorithm ranking transferable across datasets in the same group. The fact that RL agents outperform others in both any-time and fixed-time learning indicates that the RL agents successfully meta-learn those rankings, which let them finds the best algorithms for similar datasets with less exploration than other agents that cannot meta-learn (best on samples, freeze-thaw, random or average-rank that uses the same ranking for all datasets), this make RL agents shine even more in any-time learning. The structure of the artificial dataset is more subtle and harder to learn, as it appears. More work needs to be done to fully elucidate this. 5
Meta-learning can be viewed as a sequential decision-making problem where an agent selects and trains algorithms progressively for a given dataset. The goal is to find the algorithm performing best within a fixed amount of time (Fixedtime learning) or at any time (Any-time learning). We have proposed learning environments that allow RL agents to learn policies (as opposed to hard-coding them) using past experiences on similar datasets (meta-learning). Trained agents operate by training algorithms step by step, thus revealing their learning curves. By doing so, they create a meta-learning curve from the performance of the best algorithm revealed so far.
Both knowledge from past dataset experience (captured in the learned agent policy), and current information on the dataset at hand (embedded in the current state) are used by agents to make decisions. By leveraging partial learning curve information, an agent may stop training algorithms that are not promising and concentrate hardware resources on an algorithm that has more potential to be the best-performing one on the given dataset, which would save a huge amount of time. In both Any-time and Fixed-time learning, the RL agents successfully acquired two important skills: (1) Meta-learning, which allows trained RL agents to identify good algorithms with less exploration for new datasets thanks to the previous training, this is more prominent in Any-time learning; (2) Exploration-exploitation trade-off, which explains the different policies they derive in Fixed-time and Any-time settings. In Any-time learning, RL agents obtained a higher cumulative reward (Area under Learning Curve) than the baselines. In contrast, in Fixedtime Learning, all methods obtain a similar cumulative reward (best final score). From a RL perspective, this outlines that the Any-time learning problem offers more possibilities to learn clever policies monitoring the exploration-exploitation trade-off. When the number of algorithms increases, MetaREVEAL with RL agents would show more advantages over the baselines in terms of computational time (e.g. the average rank agent needs to try all algorithms on the training datasets). In addition, if we have numerous sets of hyperparameters of the same model, we can adapt MetaREVEAL to work with continuous action spaces, which would be more efficient in searching for the optimal set of hyperparameters.
Future work includes performing more experiments on the artificial data, varying its parameter settings, to elucidate relationships between data structure and policy learning. Work is also under way to apply our method to other realworld meta-datasets. Systematic experiments must be performed to vary values for the parameters of our meta-learning RL environments: T and t0. Last but not least, it would be interesting to do some theoretical research and propose RL methods more dedicated to the meta-learning REVEAL game setting and investigate the computational complexity of such methods. We would also like to extend this work to the First-level meta-learning, Second-level meta-learning, and 2D meta-learning problems.
A
best on samples 0.38 ± 0.08 random 0.52 ± 0.05
Any-time learning Fixed-time learning (acc reward = ALC(T )) (acc reward = V ∗(T )) AutoDL
We would like to thank Adrien Pavao and Michael Vaccaro for supplying us with the AutoDL meta-dataset.