求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

doi:10.15960/j.cnki.issn.1007-6093.2019.02.008

运筹学学报 ›› 2019, Vol. 23 ›› Issue (2): 86-94.doi: 10.15960/j.cnki.issn.1007-6093.2019.02.008

求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

梁仁莉, 白延琴^*

上海大学理学院数学系, 上海 200444

收稿日期:2016-04-27 出版日期:2019-06-15 发布日期:2019-06-15
通讯作者: 白延琴 E-mail:yqbai@shu.edu.cn
基金资助:
国家自然科学基金（No.11371242）

A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem

LIANG Renli, BAI Yanqin^*

Department of Mathematics, Collage of Sciences, Shanghai University, Shanghai 200444, China

Received:2016-04-27 Online:2019-06-15 Published:2019-06-15

摘要/Abstract

摘要： 逻辑回归是经典的分类方法，广泛应用于数据挖掘、机器学习和计算机视觉.现研究带有l₀模约束的逻辑回归问题.这类问题广泛用于分类问题中的特征提取，且一般是NP-难的.为了求解这类问题，提出了嵌套BB（Barzilai and Borwein）算法的分裂增广拉格朗日算法（SALM-BB）.该算法在迭代中交替地求解一个无约束凸优化问题和一个带l₀模约束的二次优化问题.然后借助BB算法求解无约束凸优化问题.通过简单的等价变形直接得到带l₀模约束二次优化问题的精确解，并且给出了算法的收敛性定理.最后通过数值实验来测试SALM-BB算法对稀疏逻辑回归问题的计算精确性.数据来源包括真实的UCI数据和模拟数据.数值实验表明，相对于一阶算法SLEP，SALM-BB能够得到更低的平均逻辑损失和错分率.

关键词: 稀疏逻辑回归, 分裂增广拉格朗日算法, 特征提取

Abstract: Logistic regression is a promising method that has been used widely in many applications of data mining, machine learning, computer vision. In this paper, we study on the l₀ sparse logistic regression problem. This problem has been proposed as a promising method for feature selection in classification problems, and it is in general NP-hard. In order to solve this problem, we develop a splitting augmented Lagrange method with embedding BB (Barzilai and Borwein) method (SALM-BB). At each iteration, SALM-BB solves an unconstrained convex subproblem and a quadratic programming with l₀ constraint. We use BB method to solve the unconstrained convex subproblem. For the quadratic programming subproblem, we obtain its exact optimal solution directly. Furthermore, we prove the convergence of SALM-BB, under certain assumptions. Finally, we implement SALM-BB on the l₀ sparse logistic regression problem based on the simulation data and the data of University of California, Irvine, Machine Learning Repository. Numerical results show that SALM-BB outperforms the well-known first-order solver SLEP in terms of lower average logistic loss and lower misclassification error rate.

Key words: sparse logistic regression, splitting augmented Lagrange method, feature selection

中图分类号:

O221.2

梁仁莉, 白延琴. 求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法[J]. 运筹学学报, 2019, 23(2): 86-94.

LIANG Renli, BAI Yanqin. A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem[J]. Operations Research Transactions, 2019, 23(2): 86-94.

参考文献 22

[1]	Maghbouleh A. A logistic regression model for detecting prominences[C]//Proceedings of the Fourth International Conference on Spoken Language. Philadelphia:IEEE, 1996:2443-2445.
[2]	Brzezinski J R, Knafl G J. Logistic regression modeling for context-based classification[C]//Proceedings of the Tenth International Workshop on Database and Expert Systems Applications. Florence:IEEE, 1999:755-759.
[3]	Friedman J, Hastie T, Tibshirani R. Additive logistic regression:a statistical view of boosting[J]. The Annals of Statistics, 2000, 28(2):337-407.
[4]	Asgary M P, Jahandideh S, Abdolmaleki P, et al. Analysis and identification of β-turn types using multinomial logistic regression and artificial neural network[J]. Bioinformatics, 2007, 23(23):3125-3130.
[5]	Liao J G, Chin K V. Logistic regression for disease classification using microarray data:model selection in a large p and small n case[J]. Bioinformatics, 2007, 23(15):1945-1951.
[6]	Sartor M A, Leikauf G D, Medvedovic M, et al. LRpath:a logistic regression approach for identifying enriched biological groups in gene expression data[J]. Bioinformatics, 2009, 25(2):211-217.
[7]	Zhu J, Hastie T. Classification of gene microarrays by penalized logistic regression[J]. Biostatistics, 2004, 5(3):427-443.
[8]	Liang Y, Liu C, Luan X Z, et al. Sparse logistic regression with a l1/2 penalty for gene selection in cancer classification[J]. BMC Bioinformatics, 2013, 14(1):1-12.
[9]	Lee S I, Lee H, Abbeel P, et al. Efficient l1 regularized logistic regression[C]//Proceedings of the National Conference on Artificial Intelligence. Massachusetts:AAAI Press, 2006:401-408.
[10]	Shi J, Yin W, Osher S, et al. A fast hybrid algorithm for large-scale l1-regularized logistic regression[J]. The Journal of Machine Learning Research, 2008, 1(1):713-741.
[11]	Efron B, Hastie T, Johnstone I, et al. Least angle regression[J]. The Annals of Statistics, 2004, 32(2):407-499.
[12]	Candès E J, Wakin M B, Boyd S P. Enhancing sparsity by reweighted l1 minimization[J]. Journal of Fourier Analysis and Applications, 2007, 14(5):877-905.
[13]	Bai Y Q, Shen Y J, Shen K J. Consensus proximal support vector machine for classification problems with sparse solutions[J]. Journal of the Operations Research Society of China, 2014, 2(1):57-74.
[14]	Bagarinao E, Kurita T, Higashikubo M, et al. Adapting SVM image classifiers to changes in imaging conditions using incremental SVM:an application to car detection[C]//Proceedings of the Asian Conference on Computer Vision. Berlin:Springer-Verlag, 2009:363-372.
[15]	Kim S J, Koh K, Lustig M, et al. An interior-point method for large-scale l1-regularized least squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4):606-617.
[16]	Liu J, Ji S, Ye J. SLEP:Sparse learning with efficient projections[EB/OL].[2016-04-20]. http://www.yelab.net/software/SLEP.
[17]	Bai Y Q, Liang R L, Yang Z W. Splitting augmented lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables[J]. Optimization Methods and Software, 2016, 31(5):1089-1109.
[18]	Raydan M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem[J]. SIAM Journal on Optimization, 1997, 7(1):26-33.
[19]	Birgin E G, Martinez J M, Raydan M, et al. Nonmonotone spectral projected gradient methods on convex sets[J]. SIAM Journal on Optimization, 1999, 10(4):1196-1211.
[20]	Lu Z, Zhang Y. Sparse approximation via penalty decomposition methods[J]. SIAM Journal on Optimization, 2013, 23(4):2448-2478.
[21]	Blake C, Merz C J. UCI Repository of machine learning databases[EB/OL].[2016-04-20]. http://www.ics.uci.edu/~mlearn/MLRepository.html
[22]	Ng A Y. Feature selection, l1 vs. l2 regularization, and rotational invariance[C]//Proceedings of the International Conference on Machine Learning, 2004, 19(5):379-387.

求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 22

相关文章 1

编辑推荐

Metrics

本文评价