TL;DR
This paper introduces Mosaic, a novel AutoML platform that leverages Monte Carlo Tree Search (MCTS) to efficiently explore the complex search space of machine learning pipelines. Mosaic demonstrates competitive performance against established AutoML systems like Auto-Sklearn, offering a promising new approach to automating the machine learning workflow.
What Problem Does This Paper Address?
The field of machine learning (ML) has seen an explosion of applications, but the sheer diversity of algorithms and their sensitivity to hyper-parameters make finding the optimal configuration for a given task a significant challenge. This difficulty, coupled with an anticipated shortage of ML experts, has fueled the development of Automated Machine Learning (AutoML) systems. Existing AutoML approaches often rely on Bayesian optimization or bandit-based strategies, but the authors argue that these can be computationally expensive or struggle with the high dimensionality and complex structure of the ML pipeline search space. This paper aims to tackle this challenge by framing AutoML as a one-player game and adapting MCTS to navigate this intricate decision space.
Methods
The core innovation of this paper is the Mosaic approach, which adapts Monte Carlo Tree Search (MCTS) for the AutoML problem. MCTS is a search algorithm that excels in exploring large, complex decision spaces, typically used in games. Here's how it's applied:
- AutoML as a Markov Decision Process (MDP): The AutoML problem is formalized as an MDP, where the goal is to find the optimal combination of pre-processing methods, learning algorithms, and their respective hyper-parameter settings.
- Structured Search Space: Mosaic exploits the inherent structure of ML pipelines. The search proceeds in a defined order: first, a pre-processing method is chosen, then its hyper-parameters, followed by a learning algorithm, and finally its hyper-parameters. This hierarchical structure is naturally represented as a tree.
- MCTS Phases: Mosaic follows the standard MCTS phases:
- Selection: Uses a UCT (Upper Confidence bound applied to Trees) variant to balance exploration and exploitation when choosing the next step in the search tree.
- Expansion: Adds new nodes to the tree when an unexplored path is encountered.
- Playout: Performs a random roll-out to a terminal node to estimate a reward.
- Backpropagation: Propagates the reward back up the tree to update node values, guiding future searches.
- Handling Continuous Hyper-parameters: A key challenge is dealing with continuous hyper-parameter values. Mosaic employs a Progressive Widening strategy, which gradually increases the number of considered values for a continuous hyper-parameter as the search progresses, making the approach scalable.
- Scikit-learn Integration: The implementation leverages the scikit-learn library, incorporating 13 data preprocessing methods and 17 classifiers.
Datasets
The paper evaluates Mosaic on 133 datasets from the OpenML repository. The authors note that they were unable to obtain 7 of these datasets, leading to an evaluation on 102 datasets where the performance of Mosaic and Auto-Sklearn differed statistically. No new benchmarks were introduced; instead, the focus was on comparing against existing benchmarks used in prior AutoML research.
Key Insights and Ideas
- MCTS for Structured Optimization: Applying MCTS, traditionally used for games, to the structured and combinatorial problem of AutoML is a novel and effective strategy. It allows for a more principled exploration of the vast search space compared to purely random or grid-based methods.
- Progressive Widening for Scalability: The Progressive Widening strategy is crucial for handling continuous hyper-parameters. It prevents the exponential blow-up in search space size that would occur with a full grid search, making the approach more practical.
- Exploiting Domain Knowledge: By structuring the search space based on the typical order of ML pipeline construction (pre-processing then algorithm), Mosaic effectively incorporates domain knowledge into the search process.
- Competitive Performance: The results suggest that MCTS-based approaches can achieve performance comparable to well-established AutoML systems, indicating the potential of this method.
Key Results
- Mosaic achieved performance that matched that of Auto-Sklearn on the evaluated datasets.
- When comparing Mosaic and vanilla Auto-Sklearn (without ensembling and meta-learning), the average rank across 102 statistically different datasets showed that Auto-Sklearn initially outperformed Mosaic, likely due to Mosaic's Progressive Widening strategy. However, Mosaic gained performance as the tree search deepened, ultimately achieving a slightly better performance than Auto-Sklearn.
- The experiments were conducted on a CPU model (Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz) with a memory limit of 3GB per run. Each run had a one-hour time budget with a six-minute timeout for individual hyper-parameter evaluations.
Limitations and Future Work
- Non-Smooth Performance Landscape: The authors acknowledge that MCTS for AutoML faces challenges due to the non-smoothness of the performance landscape. This can lead to pre-processing algorithms being unfairly penalized if initially evaluated with a poor subsequent algorithm.
- Future Work - Sampling Continuous Hyper-parameters: The paper suggests improving the sampling of continuous hyper-parameter values by drawing inspiration from approaches like AlphaGo.
- Future Work - Meta-features: A longer-term research direction is to leverage meta-features of the current dataset to inform the search process, potentially leading to smarter initialization of the dataset-dependent hyper-parameter optimization, similar to Auto-Sklearn's meta-learning components.
- Alternative Playout Policies: The paper mentions that using specific policies based on extreme value estimates for playouts is a direction for future work.
Summary updated