Abstract
Feature selection is a fundamental problem for machine learning and statistics, and it has been widely studied over the past decades. However, the majority of feature selection algorithms are based on linear assumptions or simple correlation rankings. This paper introduces Sparse Hilbert-Schmidt Independence Criterion (SpHSIC) regression, a framework that transforms the "minimum redundancy maximum relevance" (mRMR) approach into a continuous optimization problem, enabling effective nonlinear feature selection with theoretical guarantees.
Introduction
Identifying relevant variables in high-dimensional datasets is critical for both interpretability and predictive performance. While linear methods like the Lasso are standard, they often fail when relationships between features and outputs are nonlinear, such as multiplicative effects or complex biological pathways. Furthermore, many nonlinear alternatives either assume additive independence (like Sparse Additive Models) or fail to account for feature redundancy, leading to the selection of "copycat" variables that provide no new information. The mRMR algorithm was designed to address redundancy but historically lacked a continuous optimization framework and a rigorous theoretical foundation. SpHSIC regression bridges this gap.
Methodology
The authors propose SpHSIC, which treats feature selection as a regression problem within a "kernelized" space.
The Loss Function and Optimization
The algorithm utilizes the Hilbert-Schmidt Independence Criterion (HSIC) to measure independence between variables using kernels. By minimizing the difference between the similarity matrix of the output and a weighted sum of the similarity matrices of the features, the method naturally identifies features that are highly relevant to the output while minimizing redundancy among selected features. Unlike traditional discrete mRMR, SpHSIC is a continuous problem, allowing for the use of efficient gradient-based solvers.
Regularization and Penalties
To induce sparsity and ensure the selection of only the most relevant features, the framework incorporates several regularization terms:
- Lasso: The standard linear L1 penalty.
- Non-convex penalties (MCP, SCAD, Bridge): These penalties avoid over-shrinking large coefficients. The authors demonstrate that using these penalties allows the model to satisfy the "oracle property," meaning it can perfectly recover the true underlying features as the sample size grows.
Theoretical Foundations
A significant contribution of this work is re-casting the loss function as a "U-statistic of degree four." This sophisticated statistical tool allows the authors to derive the asymptotic behavior of the estimator, providing a much-needed theoretical justification for mRMR-style selection. This proves that the heuristic mRMR algorithm can be viewed as a specific type of V-statistic-based M-estimation.
Empirical Results
The authors evaluated SpHSIC on both synthetic and real-world data, demonstrating its superiority in feature recovery and predictive accuracy.
Synthetic Data Performance
In simulations with high-dimensional data ($d=400$ and $d=800$), non-convex SpHSIC (using MCP or SCAD) almost perfectly recovered the true number of zero and non-zero coefficients, whereas standard Lasso selected many redundant "false positive" features.
Real-World Applications
The method was tested on datasets from the UCI Machine Learning Repository, including speech recognition (Isolet), image recognition (Coil), and medical diagnosis (ILPD).
As shown in the table above, SpHSIC variants consistently achieved lower MSE than non-penalized or standard Lasso versions. For example, on the Isolet dataset, the MCP penalty reduced the error from 2.085 to 1.829. The method remained effective even when the number of features significantly exceeded the number of observations.
Conclusion and Future Work
SpHSIC regression provides a robust, theoretically grounded approach to nonlinear feature selection. While the current method optimizes memory usage to $O(dn^2)$, future work may focus on further reducing computational complexity for extremely large-scale datasets and developing automated methods for kernel parameter selection. The authors also suggest extending the theory to "double-asymptotic" settings where the number of parameters grows faster relative to the sample size.
Summary updated