Datum-Wise Classification: A Sequential Approach to Sparsity

Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, Patrick Gallinari

TL;DR

Standard feature selection picks a fixed set of attributes for an entire dataset, but not every data point needs the same information to be classified correctly. This paper introduces Datum-Wise Classification (DWC), a reinforcement learning approach that sequentially selects features for each individual data point, allowing the model to "stop looking" once it has enough information to make a confident prediction.

What Problem Does This Paper Address?

In machine learning, "sparsity" usually refers to global feature selection: finding a small subset of features that works best for the entire dataset. However, this approach is inherently inefficient. Some data points are "easy" and could be classified using just one or two obvious features, while "hard" or ambiguous points might require a deep dive into many attributes.

Traditional methods like the LASSO ($L_1$ regularization) force a one-size-fits-all representation. This can lead to two issues:

  1. Efficiency: Computing unnecessary features for easy cases wastes time and resources.
  2. Overfitting: Global models might include specific features that help classify a few outliers but degrade performance on the rest of the data.

The authors propose a shift from global sparsity to datum-wise sparsity, where the model dynamically decides which features to acquire for each specific input.

Methods

The authors model classification as a Markov Decision Process (MDP).

  • The Process: For a given input, the "agent" starts with no information. At each step, it can choose to either:
  • Acquire a specific feature (at a cost of $-\lambda$).
  • Stop and assign a class label (rewarding correct guesses and penalizing wrong ones).
  • The Policy: The agent uses a scoring function (approximated by a linear model) to decide the best next action based on the features it has already seen.
  • Learning: The model is trained using Approximate Policy Iteration (API) with rollouts, a reinforcement learning technique. This allows the agent to learn the "value" of a feature in the context of the features it already knows.
  • The Constrained Variant: To prevent overfitting on small datasets, the authors introduce a "Constrained Model" (DWSM-Con). In this version, the model is forced to pick features in a specific global order, but it still retains the power to decide when to stop for each individual datum.

Datasets

The researchers evaluated their approach on 14 datasets from the LibSVM repository:

  • Binary Tasks (10): Australian, Breast Cancer, Diabetes, German Numer, Heart, Ionosphere, Liver Disorders, Sonar, Splice, and Svm Guide 3.
  • Multi-class Tasks (4): Segment (7 classes), Vehicle (4 classes), Vowel (11 classes), and Wine (3 classes).

Key Insights and Ideas

  • Classification as Sequential Logic: The "aha moment" here is treating classification not as a static formula, but as a path-finding exercise. The model builds a custom representation for every input.
  • Dynamic Budgeting: The model naturally allocates more "feature budget" to difficult samples. Qualitative analysis showed that when the model makes a mistake, it has usually exhausted almost all available features first—it "knows" the sample is hard, even if it eventually gets it wrong.
  • Handling Multi-class Naturally: Unlike $L_1$-SVMs, which often require training separate "one-vs-all" models (each with its own sparse set), DWC handles multi-class problems in a single sequential process, optimizing sparsity across all classes simultaneously.

Key Results

  • Superior Sparsity-Accuracy Trade-off: On 7 out of 10 binary datasets, DWC outperformed the baseline $L_1$-SVM at high sparsity levels (e.g., using only 20% of features).
  • The "Splice" Success: On the Splice dataset, the DWC model achieved better accuracy than a standard non-sparse SVM while using less than 20% of the features on average.
  • Efficiency: While the unconstrained model is slightly slower at inference than a standard linear classifier, the Constrained Model has equivalent inference complexity to a traditional classifier while maintaining the benefits of datum-wise stopping.

Limitations and Future Work

  • Training Complexity: The current learning algorithm is quadratic with respect to the number of features ($O(n^2)$). This makes it impractical for high-dimensional datasets with thousands of features (like gene expression or raw text).
  • Linearity: The authors restricted themselves to linear scoring functions to ensure a fair comparison with $L_1$-SVMs. Exploring non-linear models (like neural networks) within this MDP framework is a logical next step.
  • Feature Discovery: The authors suggest that this behavior—identifying when current features are insufficient—could lead to research into "active feature creation," where a model requests the generation of new types of data when it hits a dead end.

Summary updated

Abstract

We propose a novel classification technique whose aim is to select an appropriate representation for each datapoint, in contrast to the usual approach of selecting a representation encompassing the whole dataset. This datum-wise representation is found by using a sparsity inducing empirical risk, which is a relaxation of the standard L 0 regularized risk. The classification problem is modeled as a sequential decision process that sequentially chooses, for each datapoint, which features to use before classifying. Datum-Wise Classification extends naturally to multi-class tasks, and we describe a specific case where our inference has equivalent complexity to a traditional linear classifier, while still using a variable number of features. We compare our classifier to classical L 1 regularized linear models (L 1-SVM and LARS) on a set of common binary and multi-class datasets and show that for an equal average number of features used we can get improved performance using our method.
BibTeX
@inproceedings{dulacarnold2011datum,
  author = {Gabriel Dulac-Arnold and Ludovic Denoyer and Philippe Preux and Patrick Gallinari},
  title = {{Datum-Wise Classification: A Sequential Approach to Sparsity}},
  booktitle = {ECML/PKDD},
  year = {2011},
  url = {https://openreview.net/forum?id=-Tbz3HIT7WK},
}

Loading related content...

Figure