abess (Adaptive Best Subset Selection, also ABESS) is a machine learning method designed to address the problem of best subset selection. It aims to determine which features or variables are crucial for optimal model performance when provided with a dataset and a prediction task. abess was introduced by Zhu in 2020 [1] and it 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.[1][2] abess can also be applied in biostatistics.[3][4][5][6]

Basic Form

edit

The basic form of abess [1] is employed to address the optimal subset selection problem in general linear regression. abess is an   method, it is characterized by its polynomial time complexity and the property of providing both unbiased and consistent estimates.

In the context of linear regression, assuming we have knowledge of   independent samples  , where   and  , we define   and  . The following equation represents the general linear regression model:

 

To obtain appropriate parameters  , one can consider the loss function for linear regression:

 

In abess, the initial focus is on optimizing the loss function under the   constraint. That is, we consider the following problem:

 

where   represents the desired size of the support set, and   is the   norm of the vector.

To address the optimization problem described above, 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 as follows:

  • For j in the active set ( ):

 

  • For j in the inactive set ( ):

 

Here are the key elements in the above equations:

  •  : This represents the estimate of   obtained in the previous iteration.
  •  : It denotes the estimated active set from the previous iteration.
  •  : This is a vector where the j-th element is set to 0, while the other elements are the same as  .
  •  : Here,   represents a vector where all elements are 0 except the j-th element.
  •  : This is calculated based on the equation mentioned.

The iterative process involves exchanging variables, with the aim of minimizing the sacrifices in the active set while maximizing the sacrifices in the inactive set during each iteration. This approach allows abess to efficiently search for the optimal feature subset.

In abess, select an appropriate   and optimize the above problem for active sets size   using the information criterion   to adaptively choose the appropriate active set size   and obtain its corresponding abess estimator.

Generalizations

edit

The splicing algorithm in abess can be employed for subset selection in other models.

Distribution-Free Location-Scale Regression

edit

In 2023, Siegfried extends abess to the case of Distribution-Free and Location-Scale.[7] Specifically, it considers the optimization problem

 

subject to   where   is a loss function,   is a parameter vector,   and   are vectors, and   is a data vector.

This approach, demonstrated across various applications, enables parsimonious regression modeling for arbitrary outcomes while maintaining interpretability through innovative subset selection procedures.

Groups Selection

edit

In 2023, Zhang applied the splicing algorithm to group selection,[8] optimizing the following model:

 

Here are the symbols involved:

  •  : Total number of feature groups, representing the existence of   non-overlapping feature groups in the dataset.
  •  : Index set for the  -th feature group, where   ranges from 1 to  , representing the feature grouping structure in the data.
  •  : Model size, a positive integer determined from the data, limiting the number of selected feature groups.

Regression with Corrupted Data

edit

Zhang applied the splicing algorithm to handle corrupted data.[9] Corrupted data refers to information that has been disrupted or contains errors during the data collection or recording process. This interference may include sensor inaccuracies, recording errors, communication issues, or other external disturbances, leading to inaccurate or distorted observations within the dataset.

Single Index Models

edit

In 2023, Tang applied the splicing algorithm to optimal subset selection in the Single-index model.[2]

The form of the Single Index Model (SIM) is given by  

where   is the parameter vector,   is the error term.

The corresponding loss function is defined as  

where   is the rank vector,   is the rank of   in  .

The Estimation Problem addressed by this algorithm is  

Eographically Weighted Regression Model

edit

In 2023, Wu [10] applied the splicing algorithm to geographically weighted regression (GWR). GWR is a spatial analysis method, and Wu's research focuses on improving GWR performance in handling geographical data regression modeling. This is achieved through the application of an l0-norm variable adaptive selection method, which simultaneously performs model selection and coefficient optimization, enhancing the accuracy of regression modeling for geographic spatial data.

Distributed Systems

edit

In 2023, Chen [11] introduced an innovative method addressing challenges in high-dimensional distributed systems, proposing an efficient algorithm for abess.

A distributed system is a computational model that distributes computing tasks across multiple independent nodes to achieve more efficient, reliable, and scalable data processing. In a distributed system, individual computing nodes can work simultaneously, collaboratively completing the overall tasks, thereby enhancing system performance and processing capabilities.

However, within distributed systems, there is a lack of efficient algorithms for optimal subset selection. To address this gap, Chen introduces a novel communication-efficient approach for handling optimal subset selection in distributed systems.

Software Package

edit

The abess library.[12] (version 0.4.5) is an R package and python package based on C++ algorithms. It is open-source on GitHub. The library can be used for optimal subset selection in linear regression, (multi-)classification, and censored-response modeling models. The abess package allows for parameters to be chosen in a grouped format. Information and tutorials are available on the abess homepage.[13]

Application

edit

abess can be applied in biostatistics, such as assessing the robust severity of COVID-19 patients,[3] conducting antibiotic resistance in Mycobacterium tuberculosis,[4] exploring prognostic factors in neck pain,[5] and developing prediction models for severe pain in patients after percutaneous nephrolithotomy.[6] abess can also be applied to gene selection.[14] In the field of data-driven partial differential equation (PDE) discovery, Thanasutives [15] applied abess to automatically identify parsimonious governing PDEs.

References

edit
  1. ^ a b c Zhu, Junxian; Wen, Canhong; Zhu, Jin; Zhang, Heping; Wang, Xueqin (29 December 2020). "A polynomial algorithm for best-subset selection problem". Proceedings of the National Academy of Sciences. 117 (52): 33117–33123. Bibcode:2020PNAS..11733117Z. doi:10.1073/pnas.2014241117. PMC 7777147. PMID 33328272.
  2. ^ a b Tang, Borui; Zhu, Jin; Zhu, Junxian; Wang, Xueqin; Zhang, Heping (2023). "A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Models". arXiv:2309.06230 [stat.ML].
  3. ^ a b Kong, Weikaixin and Zhu, Jie and Bi, Suzhen and Huang, Liting and Wu, Peng and Zhu, Su-Jie (2023). "Adaptive best subset selection algorithm and genetic algorithm aided ensemble learning method identified a robust severity score of COVID-19 patients". IMeta. 2 (3). Wiley Online Library: e126. doi:10.1002/imt2.126. PMC 10989835. PMID 38867930.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  4. ^ a b Reshetnikov, KO and Bykova, DI and Kuleshov, KV and Chukreev, K and Guguchkin, EP and Akimkin, VG and Neverov, AD and Fedonin, GG (2022). "Feature selection and aggregation for antibiotic resistance GWAS in Mycobacterium tuberculosis: a comparative study". bioRxiv. Cold Spring Harbor Laboratory: 2022–03.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  5. ^ a b Liew, Bernard XW and Kovacs, Francisco M and Rugamer, David and Royuela, Ana (2023). "Automatic Variable Selection Algorithms in Prognostic Factor Research in Neck Pain". Journal of Clinical Medicine. 12 (19). MDPI: 6232. doi:10.3390/jcm12196232. PMC 10573798. PMID 37834877.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  6. ^ a b Wei, Yuzhi and Wu, Haotian and Qi, Ziheng and Feng, Chunyu and Yang, Bo and Yin, Haolin and Wang, Lu and Zhang, Huan (2022). "Clinical Prediction Model for Severe Pain After Percutaneous Nephrolithotomy and Analysis of Associated Factors: A Retrospective Study". Research Square. doi:10.21203/rs.3.rs-2388045/v1.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  7. ^ Siegfried, Sandra; Kook, Lucas; Hothorn, Torsten (2023). "Distribution-free location-scale regression". The American Statistician. 77 (4). Taylor & Francis: 345–356. arXiv:2208.05302. doi:10.1080/00031305.2023.2203177.
  8. ^ Zhang, Yanhang; Zhu, Junxian; Zhu, Jin; Wang, Xueqin (2023). "A splicing approach to best subset of groups selection". INFORMS Journal on Computing. 35 (1). INFORMS: 104–119. arXiv:2104.12576. doi:10.1287/ijoc.2022.1241.
  9. ^ Zhang, Jie; Li, Yang; Zhao, Ni; Zheng, Zemin (2024). "L0-regularization for High-Dimensional Regression with Corrupted Data". Communications in Statistics-Theory and Methods. 53 (1). Taylor & Francis: 215–231. doi:10.1080/03610926.2022.2076125. S2CID 249106625.
  10. ^ Wu, Bo; Yan, Jinbiao; Cao, Kai (2023). "l0-Norm Variable Adaptive Selection for Geographically Weighted Regression Model". Annals of the American Association of Geographers. 113 (5). Taylor & Francis: 1190–1206. Bibcode:2023AAAG..113.1190W. doi:10.1080/24694452.2022.2161988. S2CID 257321841.
  11. ^ Chen, Yan; Dong, Ruipeng; Wen, Canhong (2023). "Communication-efficient estimation for distributed subset selection". Statistics and Computing. 33 (6). Springer: 1–15. doi:10.1007/s11222-023-10302-7. S2CID 264147329.
  12. ^ Zhu, Jin; Wang, Xueqin; Hu, Liyuan; Huang, Junhao; Jiang, Kangkang; Zhang, Yanhang; Lin, Shiyun; Zhu, Junxian (2022). "abess: a fast best-subset selection library in python and R" (PDF). The Journal of Machine Learning Research. 23 (1). JMLRORG: 9206–9212.
  13. ^ "ABESS 0.4.5 documentation".
  14. ^ Miao, Maoxuan; Wu, Jinran; Cai, Fengjing; Wang, You-Gan (2022). "A Modified Memetic Algorithm with an Application to Gene Selection in a Sheep Body Weight Study". Animals. 12 (2). MDPI: 201. doi:10.3390/ani12020201. PMC 8772977. PMID 35049823.
  15. ^ Thanasutives, Pongpisit; Morita, Takashi; Numao, Masayuki; Fukui, Ken-ichi (2023-02-01). "Noise-aware physics-informed machine learning for robust PDE discovery". Machine Learning: Science and Technology. 4 (1): 015009. arXiv:2206.12901. doi:10.1088/2632-2153/acb1f0. ISSN 2632-2153.