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.
Introduction
In traditional machine learning, feature selection is typically a global process. A fixed subset of features is chosen to represent the entire dataset, assuming that all data points require the same information for accurate classification. However, this "one-size-fits-all" approach is often inefficient. Some instances are inherently easier to classify and may only require a few salient features, while more ambiguous "hard" cases necessitate a deeper examination of the available attributes.
This paper introduces Datum-Wise Classification (DWC), a framework that shifts the focus from global sparsity to individual-level sparsity. By treating classification as a sequential decision process, DWC allows a model to dynamically decide which features to acquire for each specific input, stopping once it has sufficient information to make a confident prediction.
Methodology: Classification as an MDP
The core of DWC is modeling the classification task as a Markov Decision Process (MDP). In this framework, an agent interacts with an environment (the data point) to maximize a cumulative reward.
The Sequential Process
For a given input, the agent starts in an initial state with zero information. At each step, the agent can take one of two types of actions:
- Feature Acquisition: The agent chooses to observe a specific feature $f_i$. This action incurs a cost of $-\lambda$, representing the "price" of information.
- Classification: The agent decides to stop and assign a class label $y_j$. The reward for this action is positive for a correct classification and negative for an error.
State Representation and Policy
The state is represented by a binary vector $z$, where $z_i = 1$ if feature $i$ has been observed and $0$ otherwise. The agent's policy—the mapping from states to actions—is learned using Approximate Policy Iteration (API) with rollouts. This reinforcement learning approach enables the agent to evaluate the long-term "value" of acquiring a feature based on the information already present in the current state.
The Constrained Model
To mitigate overfitting on smaller datasets and reduce computational overhead, the authors propose a Constrained Model (DWSM-Con). In this variant, features are acquired in a fixed global order, but the model retains the critical ability to decide when to stop for each individual datum. This version achieves inference complexity equivalent to a standard linear classifier.
Experimental Evaluation
The authors evaluated DWC against traditional $L_1$-regularized models (such as $L_1$-SVM and LARS) across 14 datasets from the LibSVM repository, including 10 binary and 4 multi-class tasks.
Key Results
- Sparsity-Accuracy Trade-off: DWC consistently outperformed $L_1$-SVM at high levels of sparsity. On 7 out of 10 binary datasets, DWC achieved higher accuracy while using the same average number 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.
- Multi-class Efficiency: Unlike $L_1$-SVMs, which often require separate "one-vs-all" models, DWC handles multi-class problems within a single sequential process, optimizing sparsity across all classes simultaneously.
- Dynamic Budgeting: Qualitative analysis revealed that the model naturally allocates more "feature budget" to difficult samples. Errors typically occurred after the model had exhausted most available features, indicating that it "recognized" the difficulty of the instance.
Discussion and Future Work
While DWC offers significant advantages in efficiency and adaptive representation, it faces challenges regarding training complexity, which is currently $O(n^2)$ relative to the number of features. This limits its immediate application to extremely high-dimensional data.
Future research directions include:
- Non-linear Scoring Functions: Extending the framework to incorporate non-linear models like neural networks.
- Active Feature Creation: Using the model's ability to identify "hard" cases to trigger the generation of new, more informative features on the fly.
Conclusion
Datum-Wise Classification provides a flexible and efficient alternative to global feature selection. By tailoring the representation to each individual data point, DWC achieves a superior balance between sparsity and predictive performance, particularly in resource-constrained environments.
Summary updated