TL;DR
This paper introduces a novel "Feature Generating Machine" (FGM) for ultrahigh-dimensional feature selection on Big Data. FGM tackles the challenge of selecting relevant features from datasets with billions of data points and trillions of features by reformulating the problem as a convex semi-infinite programming problem and iteratively identifying informative features to solve smaller subproblems.
What Problem Does This Paper Address?
The paper addresses the critical challenge of feature selection in the era of "Big Data," characterized by massive volumes and ultrahigh dimensionality. Traditional feature selection methods struggle with datasets containing millions of data points and trillions of features due to computational intractability and memory limitations. This "curse of dimensionality" not only increases training costs but also degrades model performance. Furthermore, existing methods often suffer from feature selection bias, where the chosen features are not truly representative, and struggle with complex feature structures or nonlinear relationships. The authors aim to develop a scalable and effective feature selection method that can handle these ultrahigh-dimensional datasets while mitigating bias and addressing complex feature scenarios.
Methods
The core contribution is the Feature Generating Machine (FGM), an adaptive feature scaling (AFS) scheme. FGM reformulates feature selection as a convex semi-infinite programming (SIP) problem. Instead of optimizing over all features simultaneously, FGM iteratively:
- Identifies informative features: It uses a "worst-case analysis" to pinpoint features that most violate optimality conditions.
- Solves reduced subproblems: It then solves a sequence of smaller Multiple Kernel Learning (MKL) subproblems using only the identified informative features.
- Primal optimization: To accelerate training, FGM solves the MKL subproblems in their primal form using a modified accelerated proximal gradient (APG) approach.
- Cache techniques: Efficient cache mechanisms are employed to further speed up computation.
FGM is extended to handle:
- Group feature selection: Where features are organized into groups.
- Complex group structures: Including overlapping features and tree-structured groups.
- Nonlinear feature selection: Using explicit feature mappings (e.g., polynomial kernels).
The method is designed to control feature selection bias separately from model complexity and to be scalable to ultrahigh dimensions.
Datasets
The paper evaluates FGM on a variety of datasets, including:
- Synthetic datasets: Used to test linear feature selection, ultrahigh-dimensional nonlinear feature selection, and group feature selection.
- Real-world datasets:
- Linear Feature Selection: epsilon, aut-avn, real-sim, rcv1, astro-ph, news20, kddb.
- Nonlinear Feature Selection (Polynomial Mappings): mnist38, real-sim, kddb.
- Group Feature Selection: aut-avn, rcv1.
The paper notes that some datasets are split into training and testing sets, and for others, random splits are performed.
Key Insights and Ideas
- Iterative Feature Generation: The core idea of FGM is to avoid processing all features at once. By iteratively identifying and focusing on a subset of informative features, it drastically reduces computational burden.
- Decoupling Sparsity and Bias: FGM's adaptive feature scaling and separate control over sparsity (via parameter B) and model complexity (via parameter C) allow for better control over feature selection bias compared to traditional L1-regularization methods.
- SIP Formulation for Scalability: Reformulating the problem as a Semi-Infinite Programming (SIP) problem, and then solving it with a Feature Generating Machine, is key to handling ultrahigh dimensionality.
- Primal MKL for Efficiency: Solving the MKL subproblems in their primal form, rather than the dual, significantly speeds up computation, especially for large datasets.
- De-biasing Effect: FGM inherently performs a de-biasing process, leading to more relevant feature subsets and improved performance compared to methods that suffer from L1-regularization bias.
Key Results
- Scalability: FGM demonstrates competitive performance on datasets with millions of data points and up to $O(10^{14})$ features, outperforming state-of-the-art methods in terms of training efficiency.
- Accuracy: FGM-based methods generally achieve better testing accuracy than L1-regularized methods, especially when selecting a sufficient number of features.
- Bias Reduction: Experiments show that FGM effectively reduces feature selection bias, leading to improved performance compared to de-biased L1-methods.
- Efficiency: FGM is significantly faster than some baseline methods, particularly for large-scale problems, due to its iterative approach and efficient subproblem solving. For instance, PROX-FGM is reported to be up to 1,000 times faster than MKL-FGM.
- Handling Complex Structures: FGM successfully extends to group feature selection and nonlinear feature selection with explicit mappings, demonstrating its versatility.
Limitations and Future Work
- Parameter Tuning: While FGM offers better control, careful selection of parameters B (number of features to select) and C (regularization parameter) is still important for optimal performance. The paper suggests practical ranges and notes that FGM is convenient for model selection.
- Subproblem Optimization for SGD: The authors suggest that the subproblem of FGM could potentially be solved using Stochastic Gradient Descent (SGD) methods. This could further improve training efficiency for even larger datasets where n is in the billions or trillions.
- Linear Convergence for Logistic Loss: While linear convergence is achieved for the logistic loss under certain conditions (Restricted Eigenvalue Condition), further exploration of convergence rates for other loss functions or under more general conditions might be beneficial.
Summary updated