abess (Adaptive Best Subset Selection, also ABESS) is a Machine learning method designed to address the problem of best subset selection in statistical modeling. Given a dataset and a prediction task, it determines which features or variables are crucial for optimal model performance. The method was introduced by Zhu in 2020 and dynamically selects the appropriate model size adaptively, eliminating the need for selecting regularization parameters. abess is applicable in various statistical and machine learning tasks, including linear regression, the single-index model, and other common predictive models, and it can also be applied in biostatistics.
The core innovation of abess lies in its ability to perform best subset selection under an L0 norm constraint with polynomial time complexity, while providing unbiased and consistent estimates. Unlike traditional regularization methods that require tuning penalty parameters, abess adaptively determines the support set size through an iterative exchange algorithm, making it particularly attractive for high-dimensional data analysis.
Basic Form
The basic form of abess addresses the optimal subset selection problem in general linear regression. It is an L0 method characterized by polynomial time complexity and the property of providing both unbiased and consistent estimates. In the context of linear regression, assume we have knowledge of n independent samples (x_i, y_i), i = 1, ..., n, where x_i is a p-dimensional vector and y_i is a scalar response. Define X as the n by p design matrix and y as the n-dimensional response vector. The general linear regression model is expressed as y = Xβ + ε, where β is the coefficient vector and ε is the error term.
To obtain appropriate parameters β, one considers the loss function for linear regression: L_n^LR(β; X, y) = (1/(2n)) ||y - Xβ||_2^2. In abess, the initial focus is on optimizing this loss function under the L0 constraint, solving the problem: minimize L_n^LR(β; X, y) subject to ||β||_0 ≤ s, where s represents the desired size of the support set, and ||β||_0 = sum of indicators (β_i ≠0) is the L0 norm of the vector.
Algorithm and Sacrifice Concept
To address the optimization problem, abess iteratively exchanges an equal number of variables between the active set and the inactive set. In each iteration, the concept of sacrifice is introduced. For each variable j in the active set, the sacrifice ξ_j is defined as the increase in the loss function when variable j is removed from the active set: ξ_j = L_n^LR(β_hat_{A \ {j}}) - L_n^LR(β_hat_A), where A is the current active set and β_hat_A is the estimated coefficient vector restricted to A.
The algorithm proceeds by computing sacrifices for all variables in the active set, then identifying the variables with the smallest sacrifices (those that can be removed with minimal loss increase). Simultaneously, it evaluates candidate variables from the inactive set that could be added. The exchange step replaces the least important active variables with the most promising inactive candidates, maintaining the support size s. This process continues until convergence, typically measured by the change in the loss function or the stability of the active set.
Adaptive Model Size Selection
A distinctive feature of abess is its adaptive selection of the model size s, which eliminates the need for cross-validation or information criteria to choose the number of variables. The method starts with a small support size and gradually increases it while monitoring the improvement in the loss function. It uses a criterion based on the trade-off between goodness-of-fit and model complexity, often employing a modified Bayesian information criterion (BIC) or a similar penalty that adapts to the data.
This adaptive approach is computationally efficient because it avoids fitting models for a grid of s values. Instead, abess exploits the path of solutions as s increases, reusing computations from previous iterations. The final model size is chosen when the marginal improvement in fit falls below a threshold, or when the information criterion reaches a minimum.
Theoretical Properties
abess provides several theoretical guarantees that distinguish it from other variable selection methods. Under standard regularity conditions, the method achieves estimation consistency and variable selection consistency, meaning that the estimated coefficients converge to the true values and the selected support set matches the true active set with probability tending to one as the sample size grows. The polynomial time complexity is a significant advantage over exhaustive best subset selection, which is NP-hard in general.
The unbiasedness property arises because the L0 penalty does not shrink the coefficients of selected variables, unlike L1-based methods such as the lasso, which introduce bias through shrinkage. This makes abess particularly appealing when unbiased coefficient estimates are important for interpretation or downstream inference.
Applications in Regression and Beyond
abess is applicable to a wide range of statistical models beyond linear regression. In the context of the single-index model, abess can be extended to select relevant covariates while estimating the unknown link function. The method has been adapted for generalized linear models, including logistic and Poisson regression, where the loss function is modified accordingly. In biostatistics, abess has been used for biomarker discovery, where identifying a small set of predictive genes or clinical variables is crucial.
The method also handles high-dimensional settings where the number of predictors p can greatly exceed the sample size n. In such scenarios, the adaptive selection mechanism and the exchange algorithm maintain computational feasibility while providing reliable variable selection.
Software Implementation
The abess method is implemented in an open-source R package, also named abess, which provides functions for linear regression, logistic regression, and other models. The package includes efficient C++ code for the core algorithm, making it suitable for large-scale datasets. Users can specify the maximum support size or let the adaptive procedure determine it automatically. The package also offers visualization tools for the solution path and diagnostic plots.
Comparison with Other Methods
Compared to regularization-based approaches like the lasso and elastic net, abess offers the advantage of unbiased estimates and automatic model size selection without tuning parameters. However, it may be computationally more intensive than the lasso for very large p, although the polynomial time complexity mitigates this concern. Compared to greedy algorithms like orthogonal matching pursuit, abess provides a more principled exchange mechanism that can escape local optima.
Limitations and Extensions
While abess is powerful, it assumes the linear model or its extensions hold and that the L0 constraint is appropriate for the problem. For highly nonlinear relationships, extensions using basis expansions or kernel methods may be needed. Research continues on extending abess to more complex models, including Deep learning architectures and Neural network settings, where feature selection is integrated into the training process.
See Also
References
Zhu, J. (2020). abess: Adaptive Best Subset Selection. (Original introduction paper)
External Links
- R package abess on CRAN (not linked here per guidelines)