A LASSO FOR HIERARCHICAL INTERACTIONS

Abstract

We add a set of convex constraints to the lasso to produce sparse interaction models that honor the hierarchy restriction that an interaction only be included in a model if one or both variables are marginally important. We give a precise characterization of the effect of this hierarchy constraint, prove that hierarchy holds with probability one and derive an unbiased estimate for the degrees of freedom of our estimator. A bound on this estimate reveals the amount of fitting "saved" by the hierarchy constraint. We distinguish between parameter sparsity-the number of nonzero coefficients-and practical sparsity-the number of raw variables one must measure to make a new prediction. Hierarchy focuses on the latter, which is more closely tied to important data collection concerns such as cost, time and effort. We develop an algorithm, available in the R package hierNet, and perform an empirical study of our method.

Keywords: Regularized regression; convexity; hierarchical sparsity; interactions; lasso.

Fig. 1

Olive oil data: (Top left) Parameter sparsity is the number of nonzero coefficients while practical sparsity is the number of measured variables in the model. Results from all 100 random train-test splits are shown as points; lines show the average performance over all 100 runs. (Top right) Misclassification error on test set versus practical sparsity. (Bottom) Wheel plots showing the sparsity pattern at 6 values of λ for the strong hierarchical lasso. Filled nodes correspond to nonzero main effects, and edges correspond to nonzero interactions.

Fig. 2

Numerical evaluation of how well ${\widehat{df}}_{\lambda }$ estimates df_λ. Monte Carlo estimates of $E[{\widehat{df}}_{\lambda }]$ (y-axis) versus Monte Carlo estimates of df_λ (x-axis) for a sequence of λ values (circular) are shown. One-standard-error bars are drawn and are hardly visible. Our bound on the unbiased estimate is plotted with diamonds.

Fig. 3

Prediction error: Dashed line shows Bayes error (i.e., σ²), and the base rate refers to the prediction error of ȳ_train. Green, red and blue colors indicate hierarchy, all-pairs, and main effect only, respectively; solid and striped indicate lasso and forward stepwise, respectively.

Fig. 4

Plots show the ability of various methods to correctly recover the nonzero interactions. This is the sensitivity (i.e., proportion of Θ_jk ≠ 0 for which Θ●_jk ≠ 0) and specificity (i.e., proportion of Θ_jk ≠ 0 for which Θ●_jk ≠ 0) corresponding to the lowest prediction error model of each method.

Fig. 5

HIV drug data: Test-set RMSE versus practical sparsity (i.e., number of measured variables required for prediction) for six different drugs. For each method, the data from all 20 runs are displayed in faint colors; the thick lines are averages over these runs.