Online Feature Selection with Group Structure Analysis

Jing Wang, Meng Wang, Pei-Pei Li, Luoqi Liu, Zhongqiu Zhao, Xuegang Hu, Xindong WuIEEE TKDE 2015 · DOI · OpenReview

TL;DR

This paper introduces OGFS, a novel online feature selection method that leverages the inherent group structure of streaming features, a crucial aspect often overlooked by existing methods. By employing a two-stage approach of intra-group spectral analysis and inter-group sparse regression, OGFS effectively selects discriminative and non-redundant features, achieving superior performance in image classification and face verification tasks.

What Problem Does This Paper Address?

In many real-world applications, data arrives as a dynamic stream, and features are often generated in groups that represent different aspects of the data (e.g., color, texture in images). Traditional online feature selection methods, which process features one by one, tend to ignore these group structures. This can lead to suboptimal performance because features within a group might be correlated or collectively more informative than individual features. The challenge is to develop an online feature selection method that can efficiently exploit this group structure as features arrive, without requiring the entire dataset upfront.

Methods

The proposed method, Online Group Feature Selection (OGFS), tackles this problem with a two-stage approach:

  • Online Intra-Group Selection: When a new group of features arrives, this stage evaluates each feature within the group individually. It uses a novel criterion based on spectral analysis, which leverages within-class and between-class affinity graphs to identify discriminative features. This stage aims to select features that improve the discriminative ability of the current feature space.
  • Online Inter-Group Selection: After intra-group selection, this stage re-evaluates the selected features to remove redundancy and select an optimal subset. It employs a sparse linear regression model (Lasso) to achieve this, effectively considering the global group information.

This two-stage process is iterated until predefined stopping conditions are met.

Datasets

The paper evaluates OGFS on the following datasets:

  • Image Classification:
    • Cifar-10
    • Caltech-101
  • Face Verification:
    • Labeled Faces in the Wild (LFW) dataset
  • UCI Benchmark Datasets:
    • Wdbc
    • Ionosphere
    • Spectf
    • Spambase
    • Colon
    • Prostate
    • Leukemia
    • Lungcancer

For datasets without natural group structures, the feature space was randomly divided into groups.

Key Insights and Ideas

  • Group Structure is Crucial for Online Feature Selection: The paper strongly advocates that ignoring feature group structures in online settings leads to performance degradation. Exploiting these relationships is key to achieving better results.
  • Spectral Analysis for Intra-Group Discrimination: Using spectral graph theory to analyze within-class and between-class relationships within a feature group provides an effective criterion for identifying discriminative features in an online fashion.
  • Lasso for Inter-Group Redundancy Reduction: Applying Lasso in the inter-group selection stage is a novel way to efficiently reduce redundancy among selected features from different groups, leading to a more compact and effective feature set.
  • Re-evaluation of Features is Necessary: Unlike some online methods that permanently select features upon arrival, OGFS's inter-group selection allows for re-evaluation, which is shown to be critical for achieving higher accuracy, especially in face verification.

Key Results

  • Superior Accuracy: OGFS consistently outperforms state-of-the-art online feature selection methods (Alpha-investing, OSFS, Grafting) in terms of classification accuracy on image classification and face verification tasks. For example, on Caltech-101, OGFS achieved up to 30% higher accuracy than Alpha-investing.
  • Competitive Compactness: While not always achieving the absolute smallest feature set, OGFS offers a good trade-off between accuracy and compactness, often selecting fewer features than methods that achieve similar accuracy.
  • Efficient Time Complexity: OGFS-Intra is particularly efficient, with a time complexity linear to the number of features. The overall OGFS method is shown to be computationally feasible for real-world applications.
  • Robustness to Group Order: Experiments on Cifar-10 demonstrated that the order of feature groups has a limited influence on OGFS's performance, indicating its stability.
  • Outperforms Offline Methods on Some Tasks: On the LFW dataset, OGFS achieved better accuracy than several offline feature selection methods, highlighting the benefits of its online, group-aware approach.

Limitations and Future Work

  • Influence of Group Order: While the paper shows OGFS is stable, it acknowledges that the order of feature groups can have some influence on the method's performance.
  • Feature Extraction Cost: The paper notes that feature extraction itself can be expensive and time-consuming, and suggests that if a model reaches a predefined performance level, further feature extraction might not be necessary.
  • Future Work: The paper does not explicitly detail future work directions, but the success of the group structure analysis suggests exploring more sophisticated ways to model and exploit these relationships in online learning scenarios.

Summary updated

Abstract

Online selection of dynamic features has attracted intensive interest in recent years. However, existing online feature selection methods evaluate features individually and ignore the underlying structure of feature stream. For instance, in image analysis, features are generated in groups which represent color, texture and other visual information. Simply breaking the group structure in feature selection may degrade performance. Motivated by this fact, we formulate the problem as an online group feature selection. The problem assumes that features are generated individually but there are group structure in the feature stream. To the best of our knowledge, this is the first time that the correlation among feature stream has been considered in the online feature selection process. To solve this problem, we develop a novel online group feature selection method named OGFS. Our proposed approach consists of two stages: online intra-group selection and online inter-group selection. In the intra-group selection, we design a criterion based on spectral analysis to select discriminative features in each group. In the inter-group selection, we utilize a linear regression model to select an optimal subset. This two-stage procedure continues until there are no more features arriving or some predefined stopping conditions are met. %Our method has been applied Finally, we apply our method to multiple tasks including image classification %, face verification and face verification. Extensive empirical studies performed on real-world and benchmark data sets demonstrate that our method outperforms other state-of-the-art online feature selection %method methods.
BibTeX
@article{wang2015online,
  author = {Jing Wang and Meng Wang and Pei-Pei Li and Luoqi Liu and Zhongqiu Zhao and Xuegang Hu and Xindong Wu},
  title = {{Online Feature Selection with Group Structure Analysis}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2015},
  doi = {10.1109/tkde.2015.2441716},
}
Figure