Algorithm for selecting interactions without very many degrees of freedom (mgcv, gam)

I've got a semi-parametric model that I'm fitting with GAM's (mgcv in R). It is of the form

$$y = \theta + X'\beta + f(Z) + \text{Interactions!} + \epsilon$$

I've got 289 observations.

Many of the interactions that I'd like to specify are tensor (or Kronecker) product interactions. Unpenalized, each interaction takes up $k^n$ degrees of freedom, where k is the number of knots and n is the number of continuous variables in the interaction. Of course, penalization reduces the effective degrees of freedom, but GAM won't fit a model with more to-be-penalized parameters than degrees of freedom.

I've already coerced the models to specify 4 knots per Z variable and specified their location based on subject knowledge -- this isn't optimal in the sense that Simon Wood's thin plate regression splines are optimal, but it seems like a not-bad compromise in order to keep k down.

Anyway, I have a long candidate list of interactions that might be important. The problem is that a model that specifies all of them has >1000 degrees of freedom. I can't use a model selection algorithm that starts saturated and eliminates. I need to use one that starts with only the main effects (all of which I knot that I want to include a priori), and then adds terms.

The problem is that adding one interaction might change the relevance of others, or of a set of others. There are probably hundreds of combinations of interactions that are accessible given my df constraints.

I'm looking for ideas for model selection besides trial and error.

(I'm comparing models by "lowest AIC wins")

Anybody have any ideas or experience with this sort of problem?

• Edit: my background is in econometrics, so I'm not accustomed to the sorts of problems where k>n that are common in biostats. If the answer is obvious, then recommendations for good basic reading material are welcome as well. – generic_user Jan 18 '13 at 17:27