nips nips2009 nips2009-105 nips2009-105-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Grzegorz Swirszcz, Naoki Abe, Aurelie C. Lozano
Abstract: We consider the problem of variable group selection for least squares regression, namely, that of selecting groups of variables for best regression performance, leveraging and adhering to a natural grouping structure within the explanatory variables. We show that this problem can be efficiently addressed by using a certain greedy style algorithm. More precisely, we propose the Group Orthogonal Matching Pursuit algorithm (Group-OMP), which extends the standard OMP procedure (also referred to as “forward greedy feature selection algorithm” for least squares regression) to perform stage-wise group variable selection. We prove that under certain conditions Group-OMP can identify the correct (groups of) variables. We also provide an upperbound on the l∞ norm of the difference between the estimated regression coefficients and the true coefficients. Experimental results on simulated and real world datasets indicate that Group-OMP compares favorably to Group Lasso, OMP and Lasso, both in terms of variable selection and prediction accuracy. 1
[1] BACH , F.R., Consistency of the Group Lasso and Multiple Kernel Learning, J. Mach. Learn. Res., 9, 1179-1225, 2008.
[2] BAI D., Y IN Y.Q., Limit of the smallest eigenvalue of a large dimensional sample covariance matrix, Ann. Probab. 21, 1275-1294, 1993.
[3] C HEN J., H UO X., Sparse representations for multiple measurement vectors (MMV) in an overcomplete dictionary, in Proc. of the 2005 IEEE Int. Conf. on Acoustics, Speech, and Signal Proc., 2005.
[4] H UANG J., Z HANG T., M ETAXAS D., Learning with Structured Sparsity, in ICML’09, 2009.
[5] M ALLAT S., Z HANG Z., Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing, 41, 3397-3415, 1993.
[6] M OORE , E.H, On the reciprocal of the general algebraic matrix, Bulletin of the American Mathematical Society 26, 394-395, 1920.
[7] P ENROSE , R., A generalized inverse for matrices, Proceedings of the Cambridge Philosophical Society 51, 406-413, 1955.
[8] T IBSHIRANI , R., Regression shrinkage and selection via the lasso, J. Royal. Statist. Soc B., 58(1), 267-288, 1996.
[9] T ROPP J.A., Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Info. Theory, 50(10), 2231-2242, 2004.
[10] T ROPP J.A., G ILBERT A.C. , S TRAUSS M.J., Algorithms for simultaneous sparse approximation, Part I: greedy pursuit, Signal Proc. 86 (3), 572-588, 2006.
[11] P EOTTA L., VANDERGHEYNST P., Matching Pursuit with Block Incoherent Dictionaries, Signal Proc. 55 (9), 2007.
[12] Y UAN , M., L IN , Y., Model selection and estimation in regression with grouped variables, J. R. Statist. Soc. B, 68, 4967, 2006.
[13] Z HANG , T., On the consistency of feature selection using greedy least squares regression, J. Machine Learning Research, 2008.
[14] Z HANG , T., Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models, in NIPS08, 2008.
[15] Z HAO , P, ROCHA , G. AND Y U , B., Grouped and hierarchical model selection through composite absolute penalties, Manuscript, 2006.
[16] Z OU , H., H ASTIE T., Regularization and variable selection via the Elastic Net., J. R. Statist. Soc. B, 67(2) 301-320, 2005. 9