TL;DR
This paper introduces a novel "Three Part Coding" (TPC) approach to feature selection that explicitly accounts for the existence of feature classes within data. By intelligently penalizing the coding of features based on their class membership, TPC significantly improves predictive accuracy over standard methods, especially when beneficial features are concentrated in a few classes.
What Problem Does This Paper Address?
In many real-world datasets, features are not independent entities but naturally fall into groups or "classes." For instance, in gene expression data, genes might be grouped by families, or in text analysis, words can be categorized by their part of speech, surrounding words, or document topic. Traditional feature selection methods, like Lasso or stepwise regression, treat all features as if they belong to a single, undifferentiated pool. This "obliviousness" to inherent data structure can lead to suboptimal feature selection, as it doesn't leverage the information that some feature classes are more likely to contain predictive signals than others. The challenge is to develop a feature selection method that can efficiently exploit this hierarchical structure to improve model performance.
Methods
The core contribution is the Three Part Coding (TPC) scheme, which frames feature selection as an information-theoretic problem based on the Minimum Description Length (MDL) principle. TPC aims to minimize the total description length (TDL) of a model, which is the sum of the bits needed to encode the model itself and the bits needed to encode the errors.
The novelty lies in how TPC encodes the model (SM). When considering adding a new feature, TPC breaks down the cost into three parts:
- Coding the feature class index (
lc): This is where TPC shines. If the feature's class is already represented in the model, TPC uses a much smaller cost (based on the number of currently selected classes,Q) than if the class is new (cost based on the total number of classes,K). This avoids redundant coding for classes that have already proven useful. - Coding the feature index within its class (
l1): This uses a standard approach, costinglog(pk)bits, wherepkis the number of features in that specific class. - Coding the feature's coefficient (
le): This is a fixed cost, similar to AIC.
This "intelligent" coding scheme allows TPC to preferentially select features from classes that have already demonstrated predictive power, leading to more efficient and accurate feature selection.
Datasets
The paper evaluates TPC on both synthetic and real-world datasets:
- Synthetic Datasets: Two datasets were generated with 1000 features and 100 observations, where a subset of 7 features were beneficial.
- Set A: Featured 4 feature classes of unequal sizes, with all beneficial features concentrated in a small class of size 12.
- Set B: Featured 100 feature classes of equal size (10 features each), with all beneficial features in a single class.
- Real-World Datasets:
- Word Sense Disambiguation (WSD): A dataset involving six ambiguous verbs, with hundreds of observations, thousands of features, and dozens of classes. Features were derived from syntactic relations, word co-occurrences, and document topics.
- Gene Set Enrichment Analysis (GSEA): Five gene expression datasets were used, with varying numbers of observations, features, and classes. Genes were grouped into positional and pathway-based classes.
Key Insights and Ideas
- Structure Matters: The paper strongly argues that ignoring inherent feature class structure leads to suboptimal feature selection. TPC's success demonstrates the power of exploiting this hierarchy.
- Efficient Coding for Classes: The core innovation is the variable cost of coding feature classes. By penalizing new classes more heavily than existing ones, TPC naturally favors features from established, promising classes.
- TPC Outperforms Standard Methods: The theoretical advantage translates into practical gains, with TPC consistently outperforming standard RIC, Lasso, and Elastic Nets, especially when beneficial features are concentrated.
- Fewer Features, Better Performance: Interestingly, TPC often selected fewer features than other methods while achieving superior predictive accuracy, highlighting its efficiency.
Key Results
- Synthetic Data: TPC showed substantial improvements in predictive accuracy on both synthetic datasets, particularly Set A where beneficial features were concentrated in a small class.
- Real Data (WSD & GSEA): TPC consistently outperformed standard methods (Stepwise RIC, Streamwise, Lasso, Elastic Nets) in terms of 10-fold Cross-Validation RMS error. For example, in the WSD dataset, TPC variants achieved significantly lower errors than their standard counterparts. In GSEA datasets, TPC methods also showed superior performance and often selected fewer features.
- Table 2 Summary: TPC versions of both stepwise and streamwise regression consistently selected more correct features and fewer spurious features, leading to lower CV errors compared to their standard counterparts and Lasso/Elastic Nets, across both uniform and unequal class size scenarios.
Limitations and Future Work
- Assumptions: The TPC scheme relies on the assumption that beneficial features are indeed concentrated in a small number of feature classes. If beneficial features are uniformly distributed, the gains might be less pronounced.
- Future Work: The paper suggests that TPC is applicable to a wide range of problems where feature classes exist, including image analysis (features grouped by scale or generation method) and metadata-driven feature engineering. The authors also highlight that TPC can handle features derived from transformations of a single original feature set, such as principal components or interaction terms, where class sizes can be highly divergent.
Summary updated