Towards ultrahigh dimensional feature selection for big data

Mingkui Tan, Ivor W. Tsang, Li WangJMLR 2014 · OpenReview

TL;DR

This paper introduces an Adaptive Feature Scaling (AFS) method for ultrahigh-dimensional feature selection on Big Data. It tackles the challenge of selecting relevant features efficiently by reformulating the problem as a Semi-Infinite Programming (SIP) problem and proposing a novel Feature Generating Machine (FGM) that iteratively identifies informative features and solves smaller subproblems, leading to improved performance and reduced bias.

What Problem Does This Paper Address?

The paper addresses the critical challenge of feature selection in ultrahigh-dimensional Big Data. As datasets grow in volume and dimensionality (reaching $O(10^{14})$ features), traditional machine learning methods struggle due to:

  • Computational Cost: Processing millions of features is computationally prohibitive, requiring vast memory and time.
  • Curse of Dimensionality: High dimensionality can lead to poor generalization performance and overfitting.
  • Feature Selection Bias: Existing methods, particularly those using $l_1$-regularization, can introduce bias in feature selection, leading to suboptimal results.
  • Nonlinearity and Complex Structures: Many real-world problems involve nonlinear relationships and complex feature structures (e.g., groups of features) that are difficult to handle with standard linear methods.

The authors aim to develop a method that is efficient, scalable, and capable of handling these complexities while mitigating feature selection bias.

Methods

The core of the proposed solution is the Adaptive Feature Scaling (AFS) scheme combined with a Feature Generating Machine (FGM).

  • Adaptive Feature Scaling (AFS): This approach introduces a feature scaling vector $d \in [0,1]^m$ to scale the importance of features. The key innovation is an explicit constraint on the $l_1$-norm of $d$, $||d||_1 \leq B$, which directly controls the number of selected features ($B$). This is a departure from previous AFS methods where $d$ was not upper-bounded.
  • Convex Semi-Infinite Programming (SIP) Formulation: The AFS problem is reformulated as a convex SIP problem. This allows for the development of efficient optimization strategies.
  • Feature Generating Machine (FGM): FGM is designed to solve the SIP problem. It operates in two main steps:
  • Worst-Case Analysis (Feature Inference): This step iteratively identifies the most "violated" constraints (i.e., features that are most informative) based on the current solution. This is done by solving a maximization problem.
  • Subproblem Optimization: Based on the identified features, a smaller Multiple Kernel Learning (MKL) subproblem is solved. To further enhance efficiency, this subproblem is solved in its primal form using a modified Accelerated Proximal Gradient (APG) approach.
  • Cache Techniques: To further speed up training, efficient cache techniques are employed to store and reuse selected features and intermediate computations.
  • Extensions: The FGM framework is extended to handle:
  • Group Feature Selection: Features are organized into groups, and the method selects informative groups.
  • Nonlinear Feature Selection: This is achieved by using explicit feature mappings (e.g., polynomial kernels) and extending the FGM to these higher-dimensional spaces.

Datasets

The paper evaluates the proposed methods on a variety of datasets:

  • Synthetic Datasets: Used to demonstrate convergence properties and compare performance under controlled conditions.
  • Real-World Datasets:
    • Linear Feature Selection: epsilon, real-sim, rcv1, aut-avn, news20, kddb.
  • Nonlinear Feature Selection (Polynomial Mappings): mnist38, real-sim, kddb.
  • Group Feature Selection: Synthetic dataset, aut-avn, rcv1.

The paper highlights the use of datasets with ultrahigh dimensionality, reaching up to $O(10^{14})$ features.

Key Insights and Ideas

  • Explicit Sparsity Control: The introduction of the $||d||_1 \leq B$ constraint is a novel way to directly control the number of selected features, offering more fine-grained control than traditional $l_1$-regularization.
  • De-biasing Feature Selection: The FGM approach, by iteratively selecting features and solving subproblems, inherently reduces the feature selection bias often found in $l_1$-methods. This is demonstrated by comparing FGM with its de-biased counterparts.
  • Scalability through Iterative Subproblem Solving: Instead of optimizing over all features at once, FGM breaks down the problem into a sequence of smaller, manageable MKL subproblems. This is crucial for ultrahigh-dimensional data.
  • Feature Generating Machine (FGM) as a Paradigm: FGM is presented not just as an algorithm but as a general paradigm for tackling complex optimization problems by iteratively generating informative components (features/groups) and solving reduced subproblems.
  • Efficiency of Primal MKL Solution: Solving MKL subproblems in their primal form using APG significantly reduces computational burden, especially for large datasets.

Key Results

  • Competitive Performance: FGM-based methods (PROX-FGM, PROX-SLR, MKL-FGM) consistently achieve comparable or better testing accuracy than state-of-the-art $l_1$-regularization methods (e.g., $l_1$-SVM, $l_1$-LR, SGD-SLR) on various datasets.
  • Improved Training Efficiency: FGM demonstrates significantly better training efficiency, especially on large-scale and dense datasets, often outperforming $l_1$-methods by orders of magnitude. For instance, PROX-FGM is up to 1,000 times faster than MKL-FGM.
  • Reduced Feature Selection Bias: Experiments show that FGM reduces feature selection bias, leading to better generalization performance compared to standard $l_1$-methods.
  • Scalability: The method is shown to be effective on datasets with ultrahigh dimensionality ($O(10^{14})$ features), where other methods become infeasible due to memory constraints.
  • Handling Complex Structures: FGM successfully handles group feature selection and nonlinear feature selection with explicit feature mappings.

Limitations and Future Work

  • Parameter Tuning: While FGM offers advantages in controlling sparsity, parameters like $C$ and $B$ still require careful selection. The paper provides sensitivity studies and practical recommendations (e.g., $C \in [1, 100]$).
  • Stopping Conditions: The choice of stopping conditions for both outer and inner iterations is important for balancing efficiency and accuracy.
  • Future Work: The authors suggest exploring Stochastic Gradient Descent (SGD) methods to further improve training efficiency for even larger datasets where the number of training examples ($n$) is in the billions or trillions. They also plan to investigate SGD methods for better efficiency on ultra-large scale data.

Summary updated

Abstract

In this paper, we present a new adaptive feature scaling scheme for ultrahigh-dimensional feature selection on Big Data, and then reformulate it as a convex semi-infinite programming (SIP) problem. To address the SIP, we propose an efficient feature generating paradigm. Different from traditional gradient-based approaches that conduct optimization on all input features, the proposed paradigm iteratively activates a group of features, and solves a sequence of multiple kernel learning (MKL) subproblems. To further speed up the training, we propose to solve the MKL subproblems in their primal forms through a modified accelerated proximal gradient approach. Due to such optimization scheme, some efficient cache techniques are also developed. The feature generating paradigm is guaranteed to converge globally under mild conditions, and can achieve lower feature selection bias. Moreover, the proposed method can tackle two challenging tasks in feature selection: 1) group-based feature selection with complex structures, and 2) nonlinear feature selection with explicit feature mappings. Comprehensive experiments on a wide range of synthetic and real-world data sets of tens of million data points with O(1014) features demonstrate the competitive performance of the proposed method over state-of-the-art feature selection methods in terms of generalization performance and training effciency.
BibTeX
@article{tan2014towards,
  author = {Mingkui Tan and Ivor W. Tsang and Li Wang},
  title = {{Towards ultrahigh dimensional feature selection for big data}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=7N_sSG96b11},
}

Loading related content...

Figure