Computing best subset of predictors for linear regression

Question

For the selection of predictors in multivariate linear regression with $p$ suitable predictors, what methods are available to find an 'optimal' subset of the predictors without explicitly testing all $2^p$ subsets? In 'Applied Survival Analysis,' Hosmer & Lemeshow make reference to Kuk's method, but I cannot find the original paper. Can anyone describe this method, or, even better, a more modern technique? One may assume normally distributed errors.

Answer 1

I've never heard of Kuk's method, but the hot topic these days is L1 minimisation. The rationale being that if you use a penalty term of the absolute value of the regression coefficients, the unimportant ones should go to zero.

These techniques have some funny names: Lasso, LARS, Dantzig selector. You can read the papers, but a good place to start is with Elements of Statistical Learning, Chapter 3.

Answer 2

This is a huge topic. As previously mentioned, Hastie, Tibshirani and Friedman give a good intro in Ch3 of Elements of Statistical Learning.

A few points. 1) What do you mean by "best" or "optimal"? What is best in one sense may not be best in another. Two common criteria are predictive accuracy (predicting the outcome variable) and producing unbiased estimators of the coefficients. Some methods, such as Lasso & Ridge Regression inevitably produce biased coefficient estimators.

2) The phrase "best subsets" itself can be used in two separate senses. Generally to refer to the best subset among all predictors which optimises some model building criteria. More specifically it can refer to Furnival and Wilson's efficient algorithm for finding that subset among moderate (~50) numbers of linear predictors (Regressions by Leaps and Bounds. Technometrics, Vol. 16, No. 4 (Nov., 1974), pp. 499-51)

http://www.jstor.org/stable/1267601