Source-linked AI summary
High-Dimensional Feature Selection by Feature-Wise Kernelized Lasso
Makoto Yamada, Wittawat Jitkrittum, Leonid Sigal, Eric P. Xing, Masashi Sugiyama
TL;DR
Supervised feature selection must identify predictive features in high-dimensional data while capturing nonlinear input-output relationships. The paper introduces feature-wise kernelized Lasso methods using kernel transformations and convex optimization, and reports favorable performance on synthetic, image, and biological feature-selection tasks. The methods provide a scalable way to select non-redundant features with strong statistical dependence on outputs.
Problem
Supervised feature selection seeks predictive subsets of input features, while standard Lasso is based on linear input-output dependency and existing nonlinear feature-selection methods have important limitations.
Method
HSIC Lasso and NOCCO Lasso apply feature-wise kernel transformations and solve a nonnegative Lasso optimization problem in the primal space.
Results
The proposed methods find non-redundant features with strong statistical dependence on outputs and compare favorably with existing methods across synthetic, image, and biological feature-selection experiments.
Takeaways & Limitations
Efficient global optimization and kernel-based statistical interpretation make the methods promising for high-dimensional nonlinear feature selection.
Takeaways & Limitations
HSFS requires multiple restarts because it is non-convex and has O(d4) computational complexity, while SpAM is restricted to additive models and real-valued outputs.
Abstract
from arXiv · showhide
The goal of supervised feature selection is to find a subset of input features that are responsible for predicting output values. The least absolute shrinkage and selection operator (Lasso) allows computationally efficient feature selection based on linear dependency between input features and output values. In this paper, we consider a feature-wise kernelized Lasso for capturing non-linear input-output dependency. We first show that, with particular choices of kernel functions, non-redundant features with strong statistical dependence on output values can be found in terms of kernel-based independence measures. We then show that the globally optimal solution can be efficiently computed; this makes the approach scalable to high-dimensional problems. The effectiveness of the proposed method is demonstrated through feature selection experiments with thousands of features.
1 Introduction
Supervised feature selection seeks predictive subsets in high-dimensional data, but existing linear and nonlinear approaches face limitations in modeling flexibility, feature-level sparsity, convexity, or scalability. The paper proposes a feature-wise kernelized Lasso that addresses these issues through convex optimization and kernel-based dependence measures.
- Problem setting: Supervised feature selection seeks m features from d-dimensional inputs that are responsible for predicting outputs.Applications include gene selection, document categorization, and prosthesis control.
- Existing approaches: Linear Lasso provides efficient feature selection through sparse coefficients but assumes linear dependency between inputs and outputs.Its ℓ1 regularizer tends to set coefficients of irrelevant features to zero, making it useful when features outnumber samples.
- Existing approaches: Instance-wise nonlinear Lasso produces sparsity over training instances rather than features, so it cannot directly perform feature selection.Feature-wise nonlinear Lasso was introduced to obtain feature-level sparsity.
- Existing approaches: The original feature vector machine has non-convexity, singularity, output-transformation, and statistical-interpretation limitations in high-dimensional settings.Its d × d Hessian is especially problematic when the number of features exceeds the number of samples.
- Proposed approach: The proposed feature-wise nonlinear Lasso uses universal reproducing kernels as feature and output transformations and solves the problem in the primal space.The formulation supports global optimization, high-dimensional scalability, and statistical interpretation through HSIC and NOCCO-based independence measures.
- Evaluation: Experiments show that the proposed methods compare favorably with existing feature selection methods on real-world problems.The paper also relates the approach to mRMR, HSIC-based selection, QPFS, KTA, HSFS, and SpAM.
2 Proposed Methods
The paper proposes feature-wise kernelized Lasso methods that capture nonlinear dependencies while selecting non-redundant, output-dependent features. HSIC Lasso and its NOCCO variant support efficient optimization and computational strategies for high-dimensional settings.
- HSIC Lasso: HSIC Lasso regresses the centered output Gram matrix on centered feature-wise input Gram matrices with non-negative coefficients.The non-negativity constraint supports more interpretable feature selection, while different input and output kernels accommodate structured outputs.
- HSIC Lasso interpretation: HSIC Lasso favors features strongly dependent on outputs and suppresses redundant features through kernel-based dependence terms.Large HSIC with the output encourages a feature’s coefficient, whereas large HSIC between features tends to drive one redundant coefficient toward zero.
- Kernel selection: Gaussian input kernels are used generally; Gaussian output kernels serve regression, while delta output kernels serve classification.The paper reports that delta kernels clearly outperform Gaussian kernels for classification in Figure 4, making kernel choice important in that setting.
- Computational properties: The optimization can be rewritten in the form of plain Lasso with n^2 samples and d features, enabling DAL when d > n^2 and alternative formulations when n^2 ≥ d.This reformulation supports efficient computation in high-dimensional feature selection, particularly when the number of features exceeds the number of samples squared.
- Computational properties: A table-lookup approximation reduces required memory from O(dn^2) to O(dn + B) while reducing Gaussian-kernel computation costs.The method discretizes pairwise differences into B values and uses a precomputed lookup table; the implementation uses B = 4096.
- NOCCO Lasso: NOCCO Lasso replaces centered Gram matrices with regularized normalized operators and uses DNOCCO as its kernel-based dependence measure.Because DNOCCO is asymptotically independent of kernel choice, NOCCO Lasso is expected to be less sensitive to kernel parameters, although ε still requires tuning.
- Extensions: The proposed framework can incorporate popular regularizers such as group-lasso and elastic-net and can address other feature-selection problems.The paper also reports that the method is more suited than cKTA for high-dimensional feature selection, whereas cKTA is more suited to small d and large n.
3 Existing Methods
Existing feature-selection methods use dependency measures, sparsity, additive models, or quadratic optimization, but face trade-offs in scalability, optimality, assumptions, or output types.
- mRMR: mRMR selects features with strong output dependence while penalizing redundancy among selected features.Its criterion is based on mutual information and can be implemented quickly for high-dimensional selection.
- mRMR: mRMR’s brute-force optimization is intractable over 2^d subsets, so greedy search typically yields a locally optimal feature set.Its mutual-information estimate can also be unreliable when training samples are few.
- HSIC-based feature selection: HSIC-based feature selection measures dependence through centered Gram matrices and is simple to implement, but its NP-hard optimization requires greedy local search.The criterion uses kernel functions to construct Gram matrices.
- HSFS: HSFS continuously relaxes HSIC-based selection and can be optimized with L-BFGS, but its non-convex d^2-parameter optimization has O(d^4) complexity.Reducing the transformation matrix to d × q for q ≪ d adds a tuning parameter that cannot be chosen objectively.
- QPFS: QPFS performs feature selection through quadratic programming and is efficient for large n and small d, but its Hessian may be singular in high-dimensional settings.When HSIC replaces its dependency measure and the sum-to-one constraint is removed, QPFS becomes equivalent to centered KTA.
- SpAM: SpAM is convex and efficiently optimized by back-fitting, but assumes additive models, optimizes nd variables, and supports only real-valued outputs.Consequently, it may perform poorly for non-additive data and cannot handle structured outputs such as multi-label or graph data.
4 Experiments
Experiments on synthetic and real-world datasets evaluate feature-selection accuracy, computation time, classification, regression, redundancy, and kernel sensitivity. HSIC Lasso and NOCCO Lasso generally perform favorably while remaining computationally efficient, though kernel choices require manual selection.
- 4.2 Synthetic Datasets: HSIC Lasso and NOCCO Lasso select good features in both additive and non-additive synthetic models, unlike SpAM on the non-additive model.QPFS and FVM tend to be outperformed by the proposed methods.
- 4.2 Synthetic Datasets: HSIC Lasso and NOCCO Lasso computation time increases mildly with feature count compared with SpAM, FVM, and QPFS.The comparison varies Data2's feature count from d = 100 to 1000 with n = 100 over 30 runs.
- 4.3.1 Multi-Class Classification: HSIC Lasso and NOCCO Lasso compare favorably with existing methods on image-dataset classification and are comparable on microarray datasets.Classification accuracy is measured over 100 runs as the number of selected features varies; FVM is omitted for large-feature datasets because its computation cost is too high.
- 4.3.1 Multi-Class Classification: HSIC Lasso and NOCCO Lasso tend to select less redundant features, reflected by smaller redundancy-rate values.RED measures correlation among selected features, with smaller values preferred.
- Role of the Gaussian Width and the Output Kernel: The proposed methods require manual choices of Gaussian width and output kernel, motivating sensitivity experiments.The paper specifically investigates sensitivity to Gaussian width and output-kernel selection.
- Role of the Gaussian Width and the Output Kernel: HSIC Lasso is not very sensitive to Gaussian width, but its delta output kernel clearly outperforms its Gaussian output kernel in classification.These comparisons evaluate mean classification accuracy as the number of selected features varies.
- 4.3.2 High-Dimensional Regression: In high-dimensional regression on rat gene-expression data, HSIC Lasso and NOCCO Lasso compare favorably with existing methods.The dataset contains 120 subjects and 31,098 genes; evaluation uses mean squared error and mean correlation over 100 runs.
5 Conclusion
The paper proposes HSIC Lasso and NOCCO Lasso for non-linear feature selection, combining statistical interpretability with efficient global optimization. Experiments on image and biological tasks show promise, while broader applications and theoretical properties remain future work.
- HSIC Lasso and NOCCO Lasso select non-redundant features with strong statistical dependence on outputs through kernel-based independence measures.
- Global optima are efficiently computed using a nonnegative Lasso optimization problem solved by a dual augmented Lagrangian algorithm.
- Experiments on real-world image and biological feature-selection tasks found the proposed methods promising.
- Future work includes broader real-world applications, multi-task learning and prediction, and theoretical analysis of the formulation.