TL;DR
This paper tackles the challenge of classifying data when acquiring features incurs a cost, aiming to balance classification accuracy with feature acquisition expenses. They propose a novel two-stage approach combining Advantage Actor-Critic (A2C) for stable policy learning with Monte Carlo Tree Search (MCTS) for enhanced policy refinement and explainability, demonstrating superior performance on both balanced and imbalanced datasets.
What Problem Does This Paper Address?
In many real-world classification tasks, features aren't free. Acquiring them can involve costs like computation time, energy, human resources, or even patient discomfort in medical diagnoses. Traditional machine learning often assumes all features are readily available, ignoring this crucial aspect. This paper addresses the "costly features classification" problem, where the goal is to select an optimal subset of features that minimizes both classification error and the total cost of acquiring those features. This is particularly challenging because different samples might benefit from different feature subsets, making a one-size-fits-all approach suboptimal. The problem is further complicated by imbalanced datasets, where standard classification metrics can be misleading.
Methods
The authors propose a two-stage approach:
- Advantage Actor-Critic (A2C) Pretraining: They first frame the problem as a Markov Decision Process (MDP) and use the A2C algorithm. A2C is an actor-critic reinforcement learning method that uses an actor network to learn a policy (which features to select) and a critic network to evaluate the actor's actions. This provides a stable learning foundation. They also introduce a specific reward function designed to handle imbalanced datasets, penalizing misclassifications of minority classes more heavily.
- Monte Carlo Tree Search (MCTS) Improvement: To further refine the policy learned by A2C and make it more explainable, they integrate MCTS. MCTS is a model-based search algorithm, famously used in games like AlphaGo. In this context, MCTS iteratively explores potential feature acquisition sequences, guided by the A2C-learned policy. It estimates the potential reward of acquiring a feature and uses this to adjust the policy, encouraging the selection of more "economic" feature sets. MCTS also provides a tree-like structure that can offer insights into the decision-making process.
Datasets
The authors evaluated their method on several publicly available datasets from the UCI Machine Learning Repository:
- Wine
- Yeast
- Aba
- Bld
- Cir
- Pid
- Rng
They also generated imbalanced versions of the "Cir" and "Rng" datasets to specifically test performance on imbalanced data.
Key Insights and Ideas
- The Cost of Features is Crucial: The paper highlights that ignoring feature costs can lead to suboptimal or inefficient solutions in practical applications.
- A2C for Stability, MCTS for Refinement: Combining a model-free (A2C) and a model-based (MCTS) approach offers a powerful synergy. A2C provides a robust initial policy, while MCTS, with its planning capabilities, can fine-tune this policy for better cost-accuracy trade-offs and explainability.
- MCTS Enhances Explainability: The tree-like structure generated by MCTS can offer a more interpretable view of how feature selection decisions are made, which is critical in domains like healthcare.
- Tailored Reward for Imbalance: Designing a reward function that specifically accounts for class imbalance is essential for achieving good performance on such datasets.
Key Results
- Superior Performance: The proposed A2C+MCTS method consistently outperformed existing costly feature classification algorithms (Adapt-Gbrt, BudgetPrune, RADIN, DWSM, DQN, ROS, CSM) in terms of accuracy (on balanced data) and G-mean score (on imbalanced data), while achieving a moderate cost.
- Cost Efficiency: The method achieved similar or higher accuracy than full-data models (DNN, RF) but with a significantly smaller subset of features.
- Imbalanced Data Handling: On imbalanced datasets, A2C+MCTS showed a significant advantage, maintaining better performance as the imbalance ratio increased, unlike methods like DQN and Adapt-Gbrt.
- Speedup: Embedding MCTS with an A2C-pretrained model resulted in orders of magnitude faster search times compared to using MCTS alone.
- Reward Tuning: The optimal reward parameter for imbalanced data was found to be close to the imbalance ratio itself, suggesting a slight increase in the influence of minority samples is beneficial.
Limitations and Future Work
- Explainability of MCTS Tree: While MCTS offers explainability, the authors suggest further research into more efficient algorithms to extract the decision rules directly from the Monte Carlo tree.
- Generalization of Reward Function: The paper explored reward tuning for imbalanced data. Further work could investigate more generalized reward functions that adapt to various cost structures and data distributions.
- Computational Cost of MCTS: Although MCTS is faster with A2C, it still adds computational overhead. Future work might focus on further optimizing the MCTS search or exploring alternative search strategies.
Summary updated