2
$\begingroup$

I have a measured experimental dataset which is well approximated by the sum of several basis functions in linear combinations. Linear least squares of course gives me the optimal weight for each basis function. These basis functions are all unrelated and may or may not be correlated (or even repeated). That still doesn't cause any problem when fitting.. least squares is well defined and I always get optimal weights.

My question is about choosing the best subset of these basis functions to represent my data. If I'm allowed to use say only up to 7 of the 20 basis functions I have, how should I pick the 7? I realize I can just use the covariance matrix and cut out rows and columns to solve the fit for any set of 7 I like, but is there an optimal strategy for choosing the best 7 to fit my data? Enumerating all sets of 7 would be expensive (20 choose 7 = 77520) and what happens if I have 100 or 1000 input base functions?

My first thought is to find the one basis function (out of 20) that best approximates the data, and greedily "accept" that one. I then look at the remaining 19 contributors, and take the one that best helps. Repeat 7 times. This seems like a reasonable strategy, but I don't know if it finds the best set of choices, or even if it's efficient.

I haven't found discussion of choosing subsets in such a fit in my linear algebra or multivariate statistics texts, nor Google. This must be a common question, I can think of many examples where you'd use it. (Pick the best 3 weather stations to query to mix to find your local conditions. Or have a table you want to interpolate with several built in functions, and you want to pick at most 5 of them to keep evaluation speed fast. Or have multiple different sources of stock recommendations, and you only have the budget to query a limited set of them...)

Thanks!

$\endgroup$
3
  • $\begingroup$ There is such a thing as stepwise least squares, where you can monitor the coefficient of determination (as well as a bunch of other parameters whose names I'm forgetting) as you keep adding/removing basis functions. $\endgroup$
    – J. M. ain't a mathematician
    Aug 4, 2011 at 6:07
  • $\begingroup$ You might want to look at this for instance... $\endgroup$
    – J. M. ain't a mathematician
    Aug 4, 2011 at 7:02
  • $\begingroup$ You mention that your basis functions may even be repeated, but that this poses no problem for you since least-squares is well defined even in this case. Is that actually true? Are you also doing an $\ell_1$ or $\ell_2$ penalization on the weights? $\endgroup$
    – Gus
    Aug 7, 2011 at 5:56

2 Answers 2

Reset to default
1
$\begingroup$

These basis functions are all unrelated and may or may not be correlated (or even repeated). That still doesn't cause any problem when fitting.. least squares is well defined and I always get optimal weights.

The optimal least-squares approximation of the target is uniquely defined, but if you have repeated or redundant functions in the basis, the coefficients of the model will not be uniquely defined. This is called "multicollinearity" in the statistics literature.

Parsimonious selection of submodels, even for linear least squares, is an NP-complete problem.

$\endgroup$
0
$\begingroup$

There is a lot of literature on model selection of this nature; I'm somewhat surprised you haven't found anything on google. The Stepwise method you came up with yourself is among them. Obviously, though, there is probably too much on this topic to contain in this post, so a reference should be more useful. There is a free book available here that includes, among other things, a discussion of model selection. To anyone interested in machine learning, it's probably worth snatching up - can't beat free and it's a good book.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .