You are an expert at summarizing long articles. Proceed to summarize the following text: 
when considering regression with a large number of predictors , variable selection becomes important . numerous methods have been proposed in the literature for the purpose of variable selection , ranging from the classical information criteria such as aic and bic to regularization based modern techniques such as the nonnegative garrote [ breiman ( @xcite ) ] , the lasso [ tibshirani ( @xcite ) ] and the scad [ fan and li ( @xcite ) ] , among many others . although these methods enjoy excellent performance in many applications , they do not take the hierarchical or structural relationship among predictors into account and therefore can lead to models that are hard to interpret . consider , for example , multiple linear regression with both main effects and two - way interactions where a dependent variable @xmath0 and @xmath1 explanatory variables @xmath2 are related through @xmath3 where @xmath4 . commonly used general purpose variable selection techniques , including those mentioned above , do not distinguish interactions @xmath5 from main effects @xmath6 and can select a model with an interaction but neither of its main effects , that is , @xmath7 and @xmath8 . it is therefore useful to invoke the so - called effect heredity principle [ hamada and wu ( @xcite ) ] in this situation . there are two popular versions of the heredity principle [ chipman ( @xcite ) ] . under _ strong heredity _ , for a two - factor interaction effect @xmath5 to be active both its parent effects , @xmath6 and @xmath9 , should be active ; whereas under _ weak heredity _ only one of its parent effects needs to be active . likewise , one may also require that @xmath10 can be active only if @xmath6 is also active . the strong heredity principle is closely related to the notion of marginality [ nelder ( @xcite ) , mccullagh and nelder ( @xcite ) , nelder ( @xcite ) ] which ensures that the response surface is invariant under scaling and translation of the explanatory variables in the model . interested readers are also referred to mccullagh ( @xcite ) for a rigorous discussion about what criteria a sensible statistical model should obey . li , sudarsanam and frey ( @xcite ) recently conducted a meta - analysis of 113 data sets from published factorial experiments and concluded that an overwhelming majority of these real studies conform with the heredity principles . this clearly shows the importance of using these principles in practice . these two heredity concepts can be extended to describe more general hierarchical structure among predictors . with slight abuse of notation , write a general multiple linear regression as @xmath11 where @xmath12 and @xmath13 . throughout this paper , we center each variable so that the observed mean is zero and , therefore , the regression equation has no intercept . in its most general form , the hierarchical relationship among predictors can be represented by sets @xmath14 , where @xmath15 contains the parent effects of the @xmath16th predictor . for example , the dependence set of @xmath5 is @xmath17 in the quadratic model  ( [ 2way ] ) . in order that the @xmath16th variable can be considered for inclusion , all elements of @xmath15 must be included under the strong heredity principle , and at least one element of @xmath15 should be included under the weak heredity principle . other types of heredity principles , such as the partial heredity principle [ nelder ( @xcite ) ] , can also be incorporated in this framework . the readers are referred to yuan , joseph and lin ( @xcite ) for further details . as pointed out by turlach ( @xcite ) , it could be very challenging to conform with the hierarchical structure in the popular variable selection methods . in this paper we specifically address this issue and consider how to effectively impose such hierarchical structures among the predictors in variable selection and coefficient estimation , which we refer to as _ structured variable selection and estimation_.    despite its great practical importance , structured variable selection and estimation has received only scant attention in the literature . earlier interests in structured variable selection come from the analysis of designed experiments where heredity principles have proven to be powerful tools in resolving complex aliasing patterns . hamada and wu ( @xcite ) introduced a modified stepwise variable selection procedure that can enforce effect heredity principles . later , chipman ( @xcite ) and chipman , hamada and wu ( @xcite ) discussed how the effect heredity can be accommodated in the stochastic search variable selection method developed by george and mcculloch ( @xcite ) . see also joseph and delaney ( @xcite ) for another bayesian approach . despite its elegance , the bayesian approach can be computationally demanding for large scale problems . recently , yuan , joseph and lin ( @xcite ) proposed generalized lars algorithms [ osborne , presnell and turlach ( @xcite ) , efron et al . ( @xcite ) ] to incorporate heredity principles into model selection . efron et al . ( @xcite ) and turlach ( @xcite ) also considered alternative strategies to enforce the strong heredity principle in the lars algorithm . compared with earlier proposals , the generalized lars procedures enjoy tremendous computational advantages , which make them particularly suitable for problems of moderate or large dimensions . however , yuan and lin ( @xcite ) recently showed that lars may not be consistent in variable selection . moreover , the generalized lars approach is not flexible enough to incorporate many of the hierarchical structures among predictors . more recently , zhao , rocha and yu ( @xcite ) and choi , li and zhu ( @xcite ) proposed penalization methods to enforce the strong heredity principle in fitting a linear regression model . however , it is not clear how to generalize them to handle more general heredity structures and their theoretical properties remain unknown .    in this paper we propose a new framework for structured variable selection and estimation that complements and improves over the existing approaches . we introduce a family of shrinkage estimator that is similar in spirit to the nonnegative garrote , which yuan and lin ( @xcite ) recently showed to enjoy great computational advantages , nice asymptotic properties and excellent finite sample performance . we propose to incorporate structural relationships among predictors as linear inequality constraints on the corresponding shrinkage factors . the resulting estimates can be obtained as the solution of a quadratic program and very efficiently solved using the standard quadratic programming techniques . we show that , unlike lars , it is consistent in both variable selection and estimation provided that the true model has such structures . moreover , the linear inequality constraints can be easily modified to adapt to any situation arising in practical problems and therefore is much more flexible than the existing approaches . we also extend the original nonnegative garrote as well as the proposed structured variable selection and estimation methods to deal with the generalized linear models . the proposed approach is much more flexible than the generalized lars approach in yuan , joseph and lin ( @xcite ) . for example , suppose a group of variables is expected to follow strong heredity and another group weak heredity , then in the proposed approach we only need to use the corresponding constraints for strong and weak heredity in solving the quadratic program , whereas the approach of yuan , joseph and lin ( @xcite ) is algorithmic and therefore requires a considerable amount of expertise with the generalized lars code to implement these special needs . however , there is a price to be paid for this added flexibility : it is not as fast as the generalized lars . the rest of the paper is organized as follows . we introduce the methodology and study its asymptotic properties in the next section . in section  [ sec3 ] we extend the methodology to generalized linear models . section  [ sec4 ] discusses the computational issues involved in the estimation . simulations and real data examples are presented in sections  [ sec5 ] and [ sec6 ] to illustrate the proposed methods . we conclude with some discussions in section  [ sec7 ] . the original nonnegative garrote estimator introduced by breiman ( @xcite ) is a scaled version of the least square estimate . given @xmath18 independent copies @xmath19 of @xmath20 where  @xmath21 is a @xmath22-dimensional covariate and @xmath0 is a response variable , the shrinkage factor @xmath23 is given as the minimizer to @xmath24 where , with slight abuse of notation , @xmath25 , @xmath26 , and  @xmath27 is a @xmath22 dimensional vector whose @xmath28th element is @xmath29 and @xmath30 is the least square estimate based on  ( [ 1.1 ] ) . here @xmath31 is a tuning parameter . the nonnegative garrote estimate of the regression coefficient is subsequently defined as @xmath32 , @xmath33 . with an appropriately chosen tuning parameter @xmath34 , some of the scaling factors could be estimated by exact zero and , therefore , the corresponding predictors are eliminated from the selected model . following yuan , joseph and lin ( @xcite ) , let  @xmath15 contain the parent effects of the @xmath16th predictor . under the strong heredity principle , we need to impose the constraint that @xmath35 for any @xmath36 if @xmath37 . a naive approach to incorporating effect heredity is therefore to minimize  ( [ shrink ] ) under this additional constraint . however , in doing so , we lose the convexity of the optimization problem and generally will end up with problems such as multiple local optima and potentially np hardness . recall that the nonnegative garrote estimate of @xmath38 is @xmath39 . since @xmath40 with probability one , @xmath6 will be selected if and only if scaling factor @xmath41 , in which case @xmath42 behaves more or less like an indicator of the inclusion of @xmath6 in the selected model . therefore , the strong heredity principles can be enforced by requiring @xmath43 note that if @xmath41 , ( [ strong ] ) will force the scaling factor for all its parents to be positive and consequently active . since these constraints are linear in terms of the scaling factor , minimizing  ( [ shrink ] ) under  ( [ strong ] ) remains a quadratic program . figure  [ fig : strong ] illustrates the feasible region of the nonnegative garrote with such constraints in contrast with the original nonnegative garrote where no heredity rules are enforced . we consider two effects and their interaction with the corresponding shrinking factors denoted by @xmath44 , @xmath45 and @xmath46 , respectively . in both situations the feasible region is a convex polyhedron in the three dimensional space . ( left ) and the relaxed constraint @xmath47 ( right ) . ]      similarly , when considering weak heredity principles , we can require that @xmath48 however , the feasible region under such constraints is no longer convex as demonstrated in the left panel of figure  [ fig : weak ] . subsequently , minimizing  ( [ shrink ] ) subject to  ( [ weaknon ] ) is not feasible . to overcome this problem , we suggest using the convex envelop of these constraints for the weak heredity principles : @xmath49 again , these constraints are linear in terms of the scaling factor and minimizing ( [ shrink ] ) under ( [ weak ] ) remains a quadratic program . note that @xmath41 implies that @xmath50 and , therefore , ( [ weak ] ) will require at least one of its parents to be included in the model . in other words , constraint ( [ weak ] ) can be employed in place of ( [ weaknon ] ) to enforce the weak heredity principle . the small difference between the feasible regions of ( [ weaknon ] ) and ( [ weak ] ) also suggests that the selected model may only differ slightly between the two constraints . we opt for ( [ weak ] ) because of the great computational advantage it brings about . to gain further insight to the proposed structured variable selection and estimation methods , we study their asymptotic properties . we show here that the proposed methods estimate the zero coefficients by zero with probability tending to one , and at the same time give root-@xmath18 consistent estimate to the nonzero coefficients provided that the true data generating mechanism satisfies such heredity principles . denote by @xmath51 the indices of the predictors in the true model , that is , @xmath52 . write @xmath53 as the estimate obtained from the proposed structured variable selection procedure .    under strong heredity , the shrinkage factors @xmath54 can be equivalently written in the lagrange form [ boyd and vandenberghe ( @xcite ) ] @xmath55 subject to @xmath56 for some lagrange parameter @xmath57 . for the weak heredity principle , we replace the constraints @xmath58 with @xmath59 . [ thm1 ] assume that @xmath60 and @xmath61 is positive definite . if the true model satisfies the strong / weak heredity principles , and @xmath62 in a fashion such that @xmath63 as @xmath18 goes to @xmath64 , then the structured estimate with the corresponding heredity principle satisfies @xmath65 for any @xmath66 , and @xmath67 if @xmath68 . all the proofs can be accessed as the supplement materials . note that when @xmath69 , there is no penalty and the proposed estimates reduce to the least squares estimate which is consistent in estimation . the theorems suggest that if instead the tuning parameter @xmath70 escapes to infinity at a rate slower than @xmath71 , the resulting estimates not only achieve root-@xmath18 consistency in terms of estimation but also are consistent in variable selection , whereas the ordinary least squares estimator does not possess such model selection ability . the nonnegative garrote was originally introduced for variable selection in multiple linear regression . but the idea can be extended to more general regression settings where @xmath0 depends on @xmath21 through a scalar parameter @xmath72 where @xmath73 is a @xmath74-dimensional unknown coefficient vector . it is worth pointing out that such extensions have not been proposed in literature so far .    a common approach to estimating @xmath75 is by means of the maximum likelihood . let @xmath76 be a negative log conditional likelihood function of @xmath77 . the maximum likelihood estimate is given as the minimizer of @xmath78 for example , in logistic regression , @xmath79 more generally , @xmath80 can be replaced with any loss functions such that its expectation @xmath81 with respect to the joint distribution of @xmath20 is minimized at @xmath82 .    to perform variable selection , we propose the following extension of the original nonnegative garrote . we use the maximum likelihood estimate @xmath83 as a preliminary estimate of @xmath84 . similar to the original nonnegative garrote , define @xmath85 . next we estimate the shrinkage factors by @xmath86 subject to @xmath87 and @xmath88 for any @xmath33 . in the case of normal linear regression , @xmath89 becomes the least squares and it is not hard to see that the solution of  ( [ gnng ] ) always satisfies @xmath90 because all variables are centered . therefore , without loss of generality , we could assume that there is no intercept in the normal linear regression . the same , however , is not true for more general @xmath89 and , therefore , @xmath91 is included in ( [ gnng ] ) . our final estimate of @xmath92 is then given as @xmath93 for @xmath33 . to impose the strong or weak heredity principle , we add additional constraints @xmath94 or @xmath95 , respectively . theorem  [ thm1 ] can also be extended to more general regression settings . similar to before , under strong heredity , @xmath96 subject to @xmath56 for some @xmath57 . under weak heredity principles , we use the constraints @xmath97 instead of @xmath98 . we shall assume that the following regularity conditions hold :    @xmath99 is a strictly convex function of the second argument ;    the maximum likelihood estimate @xmath83 is root-@xmath18 consistent ;    the observed information matrix converges to a positive definite matrix , that is , @xmath100 where @xmath101 is a positive definite matrix . [ thm2 ] under regularity conditions , if @xmath62 in a fashion such that @xmath102 as @xmath18 goes to @xmath103 , then @xmath65 for any @xmath104 , and @xmath105 if @xmath68 provided that the true model satisfies the same heredity principles . similar to the original nonnegative garrote , the proposed structured variable selection and estimation procedure proceeds in two steps . first the solution path indexed by the tuning parameter @xmath34 is constructed . the second step , oftentimes referred to as tuning , selects the final estimate on the solution path . we begin with linear regression . for both types of heredity principles , the shrinkage factors for a given @xmath34 can be obtained from solving a quadratic program of the following form : @xmath106 where @xmath107 is a @xmath108 matrix determined by the type of heredity principles , @xmath109 is a vector of zeros , and @xmath110 means `` greater than or equal to '' in an element - wise manner . equation  ( [ qpsvs ] ) can be solved efficiently using standard quadratic programming techniques , and the solution path of the proposed structured variable selection and estimation procedure can be approximated by solving ( [ qpsvs ] ) for a fine grid of @xmath34 s . recently , yuan and lin ( @xcite ) showed that the solution path of the original nonnegative garrote is piecewise linear , and used this to construct an efficient algorithm for building its whole solution path . the original nonnegative garrote corresponds to the situation where the matrix @xmath107 of ( [ qpsvs ] ) is a @xmath111 identity matrix . similar results can be expected for more general scenarios including the proposed procedures , but the algorithm will become considerably more complicated and running quadratic programming for a grid of tuning parameter tends to be a computationally more efficient alternative . . the objective function of ( [ qpsvs ] ) can be expressed as @xmath113 because @xmath114 does not depend on @xmath115s , ( [ qpsvs ] ) is equivalent to @xmath116\\[-8pt ] & & \qquad \mbox{subject to } \sum _ { j=1}^p \theta_j\le m \mbox { and } h\theta\succeq{\mathbf0},\nonumber\end{aligned}\ ] ] which depends on the sample size @xmath18 only through @xmath117 and the gram matrix @xmath118 . both quantities are already computed in evaluating the least squares . therefore , when compared with the ordinary least squares estimator , the additional computational cost of the proposed estimating procedures is free of sample size @xmath18 . once the solution path is constructed , our final estimate is chosen on the path according to certain criterion . such criterion often reflects the prediction accuracy , which depends on the unknown parameters and needs to be estimated . a commonly used criterion is the multifold cross validation ( cv ) . multifold cv can be used to estimate the prediction error of an estimator . the data @xmath119 are first equally split into @xmath120 subsets @xmath121 . using the proposed method , and data @xmath122 , construct estimate @xmath123 . the cv estimate of the prediction error is @xmath124 we select the tuning parameter @xmath34 by minimizing @xmath125 . it is often suggested to use @xmath126 in practice [ breiman ( @xcite ) ] . it is not hard to see that @xmath127 estimates @xmath128 since the first term is the inherent prediction error due to the noise , one often measures the goodness of an estimator using only the second term , referred to as the model error : @xmath129 clearly , we can estimate the model error as @xmath130 , where @xmath131 is the noise variance estimate obtained from the ordinary least squares estimate using all predictors . similarly for more general regression settings , we solve @xmath132 for some matrix @xmath107 . this can be done in an iterative fashion provided that the loss function @xmath89 is strictly convex in its second argument . at each iteration , denote @xmath133}_0,\theta^{[0]})$ ] the estimate from the previous iteration . we now approximate the objective function using a quadratic function around @xmath133}_0,\theta ^{[0]})$ ] and update the estimate by minimizing @xmath134}+\theta ^{[0]}_0\bigr ) \bigl[\mathbf{z}_i\bigl(\theta-\theta^{[0]}\bigr)+\bigl(\theta_0- \theta^{[0]}_0\bigr ) \bigr ] \\ & & \qquad{}+{\frac{1}{2 } } \ell''\bigl(y_i,\mathbf{z}_i\theta^{[0]}+\theta ^{[0]}_0\bigr ) \bigl[\mathbf{z}_i\bigl(\theta-\theta^{[0]}\bigr)+\bigl(\theta_0- \theta^{[0]}_0\bigr ) \bigr]^2 \biggr ) , \end{aligned}\ ] ] subject to @xmath87 and @xmath135 , where the derivatives are taken with respect to the second argument of @xmath136 . now it becomes a quadratic program . we repeat this until a certain convergence criterion is met .    in choosing the optimal tuning parameter @xmath34 for general regression , we again use the multifold cross - validation . it proceeds in the same fashion as before except that we use a loss - dependent cross - validation score : @xmath137 in this section we investigate the finite sample properties of the proposed estimators . to fix ideas , we focus our attention on the usual normal linear regression . we first consider a couple of models that represent different scenarios that may affect the performance of the proposed methods . in each of the following models , we consider three explanatory variables @xmath138 that follow a multivariate normal distribution with @xmath139 with three different values for @xmath140 : @xmath141 and @xmath142 . a quadratic model with nine terms @xmath143 is considered . therefore , we have a total of nine predictors , including three main effects , three quadratic terms and three two - way interactions . to demonstrate the importance of accounting for potential hierarchical structure among the predictor variables , we apply the nonnegative garrote estimator that recognizes strong heredity , weak heredity and without heredity constraints . in particular , we enforce the strong heredity principle by imposing the following constraints : @xmath144 to enforce the weak heredity , we require that @xmath145    we consider two data - generating models , one follows the strong heredity principles and the other follows the weak heredity principles :    the first model follows the strong heredity principle : @xmath146    the second model is similar to model i except that the true data generating mechanism now follows the weak heredity principle : @xmath147    for both models , the regression noise @xmath148 .    for each model , 50 independent observations of @xmath149 are collected , and a quadratic model with nine terms is analyzed . we choose the tuning parameter by ten - fold cross - validation as described in the last section . following breiman ( @xcite ) , we use the model error ( [ me ] ) as the gold standard in comparing different methods . we repeat the experiment for 1000 times for each model and the results are summarized in table  [ tab : ex1 ] . the numbers in the parentheses are the standard errors . we can see that the model errors are smaller for both weak and strong heredity models compared to the model that does not incorporate any of the heredity principles . paired @xmath150-tests confirmed that most of the observed reductions in model error are significant at the 5% level . = 9.2 cm    9.2cm@lccc@ & * no heredity * & * weak heredity * & * strong heredity * +   + @xmath151 & 1.79 & 1.70 & 1.59 + & ( 0.05 ) & ( 0.05 ) & ( 0.04 ) + @xmath152 & 1.57 & 1.56 & 1.43 + & ( 0.04 ) & ( 0.04 ) & ( 0.04 ) + @xmath153 & 1.78 & 1.69 & 1.54 + & ( 0.05 ) & ( 0.04 ) & ( 0.04 ) +   + @xmath151 & 1.77 & 1.61 & 1.72 + & ( 0.05 ) & ( 0.05 ) & ( 0.04 ) + @xmath152 & 1.79 & 1.53 & 1.70 + & ( 0.05 ) & ( 0.04 ) & ( 0.04 ) + @xmath153 & 1.79 & 1.68 & 1.76 + & ( 0.04 ) & ( 0.04 ) & ( 0.04 ) +    for model i , the nonnegative garrote that respects the strong heredity principles enjoys the best performance , followed by the one with weak heredity principles . this example demonstrates the benefit of recognizing the effect heredity . note that the model considered here also follows the weak heredity principle , which explains why the nonnegative garrote estimator with weak heredity outperforms the one that does not enforce any heredity constraints . for model ii , the nonnegative garrote with weak heredity performs the best . interestingly , the nonnegative garrote with strong heredity performs better than the original nonnegative garrote . one possible explanation is that the reduced feasible region with strong heredity , although introducing bias , at the same time makes tuning easier .    to gain further insight , we look into the model selection ability of the structured variable selection . to separate the strength of a method and effect of tuning , for each of the simulated data , we check whether or not there is any tuning parameter such that the corresponding estimate conforms with the true model . the frequency for each method to select the right model is given in table  [ tab : ex1f ] , which clearly shows that the proposed structured variable selection methods pick the right models more often than the original nonnegative garrote . note that the strong heredity version of the method can never pick model ii correctly as it violates the strong heredity principle . we also want to point out that such comparison , although useful , needs to be understood with caution . in practice , no model is perfect and selecting an additional main effect @xmath154 so that model ii can satisfy strong heredity may be a much more preferable alternative to many . @lccc@ & * no heredity * & * weak heredity * & * strong heredity * +   + @xmath151 & 65.5% & 71.5% & 82.0% + @xmath152 & 85.0% & 86.5% & 90.5% + @xmath153 & 66.5% & 73.5% & 81.5% +   + @xmath151 & 65.5% & 75.5% & 0.00% + @xmath152 & 83.0% & 90.0% & 0.00% + @xmath153 & 56.5% & 72.5% & 0.00% +        we also checked how effective the ten - fold cross - validation is in picking the right model when it does not follow any of the heredity principles . we generated the data from the model @xmath155 where the set up for simulation remains the same as before . note that this model does not follow any of the heredity principles . for each run , we ran the nonnegative garrote with weak heredity , strong heredity and no heredity . we chose the best among these three estimators using ten - fold cross - validation . note that the three estimators may take different values of the tuning parameter . among 1000 runs , 64.1% of the time , nonnegative garrote with no heredity principle was elected . in contrast , for either model i or model ii with a similar setup , less than 10% of the time nonnegative garrote with no heredity principle was elected . this is quite a satisfactory performance . the next example is designed to illustrate the effect of the magnitude of the interaction on the proposed methods . we use a similar setup as before but now with four main effects @xmath156 , four quadratic terms and six two - way interactions . the true data generating mechanism is given by @xmath157 where @xmath158 and @xmath159 with @xmath160 chosen so that the signal - to - noise ratio is always @xmath161 . similar to before , the sample size @xmath162 . figure  [ fig : revsim1 ] shows the mean model error estimated over 1000 runs . we can see that the strong and weak heredity models perform better than the no heredity model and the improvement becomes more significant as the strength of the interaction effect increases . to fix the idea , we have focused on using the least squares estimator as our initial estimator . the least squares estimators are known to perform poorly when the number of predictors is large when compared with the sample size . in particular , it is not applicable when the number of predictors exceeds the sample size . however , as shown in yuan and lin ( @xcite ) , other initial estimators can also be used . in particular , they suggested ridge regression as one of the alternatives to the least squares estimator . to demonstrate such an extension , we consider again the regression model ( [ eq : effectsize ] ) but with ten main effects @xmath163 and ten quadratic terms , as well as 45 interactions . the total number of effects ( @xmath164 ) exceeds the number of observations ( @xmath162 ) and , therefore , the ridge regression tuned with gcv was used as the initial estimator . figure [ fig : aoasrevsim ] shows the solution path of the nonnegative garrote with strong heredity , weak heredity and without any heredity for a typical simulated data with @xmath165 .    : solution for different versions of the nonnegative garrote . ] it is interesting to notice from figure [ fig : aoasrevsim ] that the appropriate heredity principle , in this case strong heredity , is extremely valuable in distinguishing the true effect  @xmath166 from other spurious effects . this further confirms the importance of heredity principles . in this section we apply the methods from section  [ sec2 ] to several real data examples . the first is the prostate data , previously used in tibshirani ( @xcite ) . the data consist of the medical records of @xmath167 male patients who were about to receive a radical prostatectomy . the response is the level of prostate specific antigen , and there are 8 explanatory variables . the explanatory variables are eight clinical measures : log(cancer volume ) ( lcavol ) , log(prostate weight ) ( lweight ) , age , log(benign prostatic hyperplasia amount ) ( lbph ) , seminal vesicle invasion ( svi ) , log(capsular penetration ) ( lcp ) , gleason score ( gleason ) and percentage gleason scores 4 or 5 ( pgg45 ) . we consider model  ( [ 2way ] ) with main effects , quadratic terms and two way interactions , which gives us a total of 44 predictors . figure  [ fig : prostate ] gives the solution path of the nonnegative garrote with strong heredity , weak heredity and without any heredity constraints . the vertical grey lines represent the models that are selected by the ten - fold cross - validation .        to determine which type of heredity principle to use for the analysis , we calculated the ten - fold cross - validation scores for each method . the cross - validation scores as functions of the tuning parameter @xmath34 are given in the right panel of figure  [ fig : prostate - cv ] . cross - validation suggests the validity of heredity principles . the strong heredity is particularly favored with the smallest score . using ten - fold cross - validation , the original nonnegative garrote that neglects the effect heredity chooses a six variable model : _ lcavol , lweight , lbph , gleason@xmath168 , lbph : svi _ and _ svi : pgg45_. note that this model does not satisfy heredity principle , because _ gleason@xmath168 _ and _ svi : pgg45 _ are included without any of its parent factors . in contrast , the nonnegative garrote with strong heredity selects a model with seven variables : _ lcavol , lweight , lbph , svi , gleason , gleason@xmath168 _ and _ lbph : svi_. the model selected by the weak heredity , although comparable in terms of cross validation score , is considerably bigger with 16 variables . the estimated model errors for the strong heredity , weak heredity and no heredity nonnegative garrote are @xmath169 , @xmath170 and @xmath171 , respectively , which clearly favors the methods that account for the effect heredity . to further assess the variability of the ten - fold cross - validation , we also ran the leave - one - out cross - validation on the data . the leave - one - out scores are given in the right panel of figure  [ fig : prostate - cv ] . it shows a similar pattern as the ten - fold cross - validation . in what follows , we shall continue to use the ten - fold cross - validation because of the tremendous computational advantage it brings about .      to illustrate the strategy in more general regression settings , we consider a logistic regression for the south african heart disease data previously used in hastie , tibshirani and friedman ( @xcite ) . the data consist of 9 different measures of 462 subjects and the responses indicating the presence of heart disease . we again consider a quadratic model . there is one binary predictor which leaves a total of 53 terms . nonnegative garrote with strong heredity , weak heredity and without heredity were applied to the data set . the solution paths are given in figure  [ fig : heart - path ] . the cross - validation scores for the three different methods are given in figure  [ fig : heart - cv ] . as we can see from the figure , nonnegative garrote with strong heredity principles achieves the lowest cross - validation score , followed by the one without heredity principles .      to gain further insight on the merits of the proposed structured variable selection and estimation techniques , we apply them to seven benchmark data sets , including the previous two examples . the ozone data , originally used in breiman and friedman ( @xcite ) , consist of the daily maximum one - hour - average ozone reading and eight meteorological variables in the los angeles basin for 330 days in 1976 . the goal is to predict the daily maximum one - hour - average ozone reading using the other eight variables . the boston housing data include statistics for 506 census tracts of boston from the 1970 census [ harrison and rubinfeld ( @xcite ) ] . the problem is to predict the median value of owner - occupied homes based on 13 demographic and geological measures . the diabetes data , previously analyzed by efron et al . ( @xcite ) , consist of eleven clinical measurements for a total of 442 diabetes patients . the goal is to predict a quantitative measure of disease progression one year after the baseline using the other ten measures that were collected at the baseline . along with the prostate data , these data sets are used to demonstrate our methods in the usual normal linear regression setting .    to illustrate the performance of the structured variable selection and estimation in more general regression settings , we include two other logistic regression examples along with the south african heart data . the pima indians diabetes data have 392 observations on nine variables . the purpose is to predict whether or not a particular subject has diabetes using eight remaining variables . the bupa liver disorder data include eight variables and the goal is to relate a binary response with seven clinical measurements . both data sets are available from the uci repository of machine learning databases [ newman et al . ( @xcite ) ] . we consider methods that do not incorporate heredity principles or respect weak or strong heredity principles . for each method , we estimate the prediction error using ten - fold cross - validation , that is , the mean squared error in the case of the four linear regression examples , and the misclassification rate in the case of the three classification examples . table [ tab : real ] documents the findings . similar to the heart data we discussed earlier , the total number of effects ( @xmath22 ) can be different for the same number of main effects ( @xmath1 ) due to the existence of binary variables . as the results from table  [ tab : real ] suggest , incorporating the heredity principles leads to improved prediction for all seven data sets . note that for the four regression data sets , the prediction error depends on the scale of the response and therefore should not be compared across data sets . for example , the response variable of the diabetes data ranges from 25 to 346 with a variance of 5943.331 . in contrast , the response variable of the prostate data ranges from @xmath172 to 5.48 with a variance of 1.46 . @ld3.0d2.0d3.0d4.3cc@ * data * & & & & & & + boston & 506 & 13 & 103 & 12.609 & & 12.661 + diabetes & 442 & 10 & 64 & 3077.471 & & 3116.989 + ozone & 203 & 9 & 54 & 16.558 & & 15.397 + prostate & 97 & 8 & 44 & 0.624 & 0.632 & * 0.584 * + bupa & 345 & 6 & 27 & 0.287 & 0.279 & * 0.267 * + heart & 462 & 9 & 53 & 0.286 & 0.275 & * 0.262 * + pima & 392 & 8 & 44 & 0.199 & 0.214 & * 0.196 * + when a large number of variables are entertained , variable selection becomes important . with a number of competing models that are virtually indistinguishable in fitting the data , it is often advocated to select a model with the smaller number of variables . but this principle alone may lead to models that are not interpretable . in this paper we proposed structured variable selection and estimation methods that can effectively incorporate the hierarchical structure among the predictors in variable selection and regression coefficient estimation . the proposed methods select models that satisfy the heredity principle and are much more interpretable in practice . the proposed methods adopt the idea of the nonnegative garrote and inherit its advantages . they are easy to compute and enjoy good theoretical properties . similar to the original nonnegative garrote , the proposed method involves the choice of a tuning parameter which also amounts to the selection of a final model . throughout the paper , we have focused on using the cross - validation for such a purpose . other tuning methods could also be used . in particular , it is known that prediction - based tuning may result in unnecessarily large models . several heuristic methods are often adopted in practice to alleviate such problems . one of the most popular choices is the so - called one standard error rule [ breiman et al . ( @xcite ) ] , where instead of choosing the model that minimizes the cross - validation score , one chooses the simplest model with a cross - validation score within one standard error from the smallest . our experience also suggests that a visual examination of the solution path and the cross - validation scores often leads to further insights . the proposed method can also be used in other statistical problems whenever the structures among predictors should be respected in model building . in some applications , certain predictor variables may be known apriori to be more important than the others . this may happen , for example , in time series prediction where more recent observations generally should be more predictive of future observations . boyd , s. and vandenberghe , l. ( 2004 ) . _ convex optimization_. cambridge univ . press , cambridge . breiman , l. ( 1995 ) . better subset regression using the nonnegative garrote . _ technometrics _ * 37 * 373384 . breiman , l. and friedman , j. ( 1985 ) . estimating optimal transformations for multiple regression and correlation . _ j. amer . assoc . _ * 80 * 580598 . breiman , l. , friedman , j. , stone , c. and olshen , r. ( 1984 ) . _ classifcation and regression trees_. chapman & hall / crc , new york . chipman , h. ( 1996 ) . bayesian variable selection with related predictors . j. statist . _ * 24 * 1736 . chipman , h. , hamada , m. and wu , c. f. j. ( 1997 ) . a bayesian variable selection approach for analyzing designed experiments with complex aliasing . _ technometrics _ * 39 * 372381 . choi , n. , li , w. and zhu , j. ( 2006 ) . variable selection with the strong heredity constraint and its oracle property . technical report . efron , b. , johnstone , i. , hastie , t. and tibshirani , r. ( 2004 ) . least angle regression ( with discussion ) . statist . _ * 32 * 407499 . fan , j. and li , r. ( 2001 ) . variable selection via nonconcave penalized likelihood and its oracle properties . _ j. amer . assoc . _ * 96 * 13481360 . george , e. i. and mcculloch , r. e. ( 1993 ) . variable selection via gibbs sampling . _ j. amer . statist . assoc . _ * 88 * 881889 . hamada , m. and wu , c. f. j. ( 1992 ) . analysis of designed experiments with complex aliasing . _ journal of quality technology _ * 24 * 130137 . harrison , d. and rubinfeld , d. ( 1978 ) . hedonic prices and the demand for clean air . _ journal of environmental economics and management _ * 5 * 81102 . hastie , t. , tibshirani , r. and friedman , j. ( 2003 ) . _ the elements of statistical learning : data mining , inference , and prediction_. springer , new york . joseph , v. r. and delaney , j. d. ( 2007 ) . functionally induced priors for the analysis of experiments . _ technometrics _ * 49 * 111 . li , x. , sundarsanam , n. and frey , d. ( 2006 ) . regularities in data from factorial experiments . _ complexity _ * 11 * 3245 . mccullagh , p. ( 2002 ) . what is a statistical model ( with discussion ) . _ * 30 * 12251310 . mccullagh , p. and nelder , j. ( 1989 ) . _ generalized linear models _ , 2nd ed chapman & hall , london . nelder , j. ( 1977 ) . a reformulation of linear models . a _ * 140 * 4877 . nelder , j. ( 1994 ) . the statistics of linear models . _ statist . comput . _ * 4 * 221234 . nelder , j. ( 1998 ) . the selection of terms in response - surface models  how strong is the weak - heredity principle ? _ statist . _ * 52 * 315318 . newman , d. , hettich , s. , blake , c. and merz , c. ( 1998 ) . uci repository of machine learning databases . information and computer science , univ . california , irvine , ca . available at http://www.ics.uci.edu/\textasciitilde mlearn / mlrepository.html[http://www.ics.uci.edu/\textasciitilde mlearn / mlrepository.html ] . osborne , m. , presnell , b. and turlach , b. ( 2000 ) . a new approach to variable selection in least squares problems . _ i m a j. numer . * 20 * 389403 . tibshirani , r. ( 1996 ) . regression shrinkage and selection via the lasso . b _ * 58 * 267288 . turlach , b. ( 2004 ) . discussion of `` least angle regression . '' _ ann . statist . _ * 32 * 481490 . yuan , m. , joseph , v. r. and lin , y. ( 2007 ) . an efficient variable selection approach for analyzing designed experiments . _ technometrics _ * 49 * 430439 . yuan , m. and lin , y. ( 2006 ) . model selection and estimation in regression with grouped variables . b _ * 68 * 4967 . yuan , m. and lin , y. ( 2007 ) . on the the nonnegative garrote estimator . b _ * 69 * 143161 .
in linear regression problems with related predictors , it is desirable to do variable selection and estimation by maintaining the hierarchical or structural relationships among predictors . in this paper 
 we propose non - negative garrote methods that can naturally incorporate such relationships defined through effect heredity principles or marginality principles . 
 we show that the methods are very easy to compute and enjoy nice theoretical properties . 
 we also show that the methods can be easily extended to deal with more general regression problems such as generalized linear models . 
 simulations and real examples are used to illustrate the merits of the proposed methods .    ,    .