Feature Selection as a One-Player Game

Romaric Gaudel, Michèle SebagICML 2010 · OpenReview

TL;DR

This paper reimagines Feature Selection (FS) not as a simple ranking task, but as a strategic one-player game. By formalizing FS as a Reinforcement Learning problem and applying Monte-Carlo Tree Search (specifically the UCT algorithm), the authors create a method that can navigate the astronomical search space of feature subsets to find optimal combinations that traditional methods often miss.

The Challenge of Feature Selection

In machine learning, "Feature Selection" is the process of picking the most relevant variables from a dataset to improve model accuracy and reduce noise. It is a notoriously difficult combinatorial optimization problem: if you have $N$ features, there are $2^N$ possible subsets to check.

Existing approaches usually fall into three camps:

  1. Filters: Fast but "blind" to how features interact (e.g., they might miss two features that are useless alone but powerful together).
  2. Wrappers: Treat the model as a black box and search through subsets, but they often get stuck in local optima or become computationally impossible as the number of features grows.
  3. Embedded methods: Build selection into the learning algorithm (like Lasso), but these are often tied to specific linear models.

The authors aim to bridge the gap: they want a search strategy that is as robust as a wrapper but smart enough to handle the "combinatorial explosion" of high-dimensional data.

Methods: The FUSE Algorithm

The core innovation is the FUSE (Feature Uct SElection) algorithm. It treats the selection of features as a sequence of moves in a game.

  • MDP Formalization: The authors define Feature Selection as a Markov Decision Process (MDP). A "state" is a subset of features, and an "action" is adding a new feature to that subset.
  • UCT Framework: To solve this MDP, they use the Upper Confidence Tree (UCT) algorithm, a popular Monte-Carlo Tree Search technique used in AI for games like Go. UCT balances exploration (trying new, unknown features) and exploitation (refining subsets that have already shown promise).
One iteration of the FUSE approach showing the bandit-based search phase followed by a random expansion phase.
  • Handling the "Many-Armed Bandit" Problem: Standard UCT fails when there are thousands of possible actions (features). FUSE introduces two key heuristics:
  • RAVE (Rapid Action Value Estimation): This allows the algorithm to learn "global" feature relevance. If a feature is good in one branch of the search tree, RAVE helps the algorithm realize it might be good in others too.
  • Progressive Widening: This limits how many new features the algorithm considers at any given node until it has "spent enough time" evaluating the ones it already knows.
  • Frugal Reward Function: Instead of training a heavy model to evaluate every subset, FUSE uses a fast, k-nearest-neighbor-based estimate of the Area Under the ROC Curve (AUC).

Key Insights and Ideas

  • Context Matters: Unlike "filter" methods that rank features in isolation, FUSE evaluates features within the context of a subset. This allows it to solve "XOR-like" problems where feature interdependencies are crucial.
  • The "Aha" Moment on RAVE: The authors found that the RAVE scores (global relevance) are often more efficient for ranking than the search tree itself. They proposed FUSE$^R$, which uses the search to build a better "filter" score, combining the best of both worlds.
  • Efficiency through Subsampling: By using a "frugal" reward function on a small subsample of data, the algorithm can perform tens of thousands of iterations in minutes, providing a deep look into the feature space that exhaustive wrappers couldn't dream of.

Key Results

The authors evaluated FUSE on three benchmark datasets from the NIPS 2003 Feature Selection Challenge: Madelon (an artificial dataset with 500 features and hidden XOR relationships), Arcene (a mass spectrometry dataset with 10,000 features), and Colon (a smaller microarray dataset with 2,000 features).

FUSE demonstrated strong performance across these different types of data complexity:

  • On Madelon (Non-linear/XOR): FUSE significantly outperformed Lasso and standard filters, which failed to find the hidden XOR relationship.
  • On Arcene (High-dimensional): FUSE and its RAVE-based variant (FUSE$^R$) achieved lower test errors than Gini-Random Forest and CFS (Correlation-based Feature Selection).
Performance comparison across Madelon, Arcene, and Colon datasets. FUSE variants show competitive or superior error rates compared to baselines.

Furthermore, the algorithm reaches its optimum relatively quickly. On the Madelon dataset, the test error drops sharply within the first 1,000 to 10,000 iterations.

Limitations and Future Work

While highly effective, the authors noted a few limitations. FUSE doesn't naturally control the depth of the search tree perfectly; the "best" paths found usually involved only 5 to 15 features. Additionally, while more efficient than exhaustive search, it still requires thousands of iterations, meaning the k-NN reward function might still be a bottleneck for extremely large datasets.

Looking ahead, the authors suggest extending this "game" framework to Feature Construction—where the algorithm doesn't just select features but actually invents new ones by combining existing variables.

Summary updated

Abstract

This paper formalizes Feature Selection as a Reinforcement Learning problem, leading to a provably optimal though intractable selection policy. As a second contribution, this paper presents an approximation thereof, based on a one-player game approach and relying on the Monte-Carlo tree search UCT (Upper Confidence Tree) proposed by Kocsis and Szepesvari (2006). The Feature Uct SElection (FUSE) algorithm extends UCT to deal with i) a finite unknown horizon (the target number of relevant features); ii) the huge branching factor of the search tree, reflecting the size of the feature set. Finally, a frugal reward function is proposed as a rough but unbiased estimate of the relevance of a feature subset. A proof of concept of FUSE is shown on benchmark data sets.
BibTeX
@inproceedings{gaudel2010feature,
  author = {Romaric Gaudel and Michèle Sebag},
  title = {{Feature Selection as a One-Player Game}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=rkNxssWObB},
}
Figure