Predictive learning via rule ensembles

Jerome H. Friedman; Bogdan E. Popescu

Source-linked AI summary

Predictive learning via rule ensembles

Jerome H. Friedman, Bogdan E. Popescu

arXiv:0811.1679v1Nov 11, 2008stat.AP

TL;DR

The paper addresses how to build predictive models that remain interpretable while retaining strong accuracy. It constructs regression and classification ensembles from simple conjunctive rules, evaluates them against tree ensembles, and develops interpretation and interaction-analysis tools. Rule-based ensembles achieve accuracy comparable to the best tree-based methods, while their rule structure supports localized and global interpretation.

Problem
The paper seeks predictive models that combine accurate regression and classification with interpretable effects of rules and variables.
Method
The paper constructs linear predictive ensembles from simple conjunctive rules extracted from decision trees and analyzes main effects, variable importance, and interactions.
Results
Rule-based ensembles achieve accuracy comparable to the best tree-based ensembles across the evaluated regression and classification problems.
Takeaways & Limitations
Simple rule structure makes individual rule contributions and variable relevance assessable globally, locally, and at individual prediction points.
Takeaways & Limitations
Interaction analysis can identify spurious interactions in accurate models, especially when predictor variables are highly collinear.

Abstract

from arXiv · show

General regression and classification models are constructed as linear combinations of simple rules derived from the data. Each rule consists of a conjunction of a small number of simple statements concerning the values of individual input variables. These rule ensembles are shown to produce predictive accuracy comparable to the best methods. However, their principal advantage lies in interpretation. Because of its simple form, each rule is easy to understand, as is its influence on individual predictions, selected subsets of predictions, or globally over the entire space of joint input variable values. Similarly, the degree of relevance of the respective input variables can be assessed globally, locally in different regions of the input space, or at individual prediction points. Techniques are presented for automatically identifying those variables that are involved in interactions with other variables, the strength and degree of those interactions, as well as the identities of the other variables with which they interact. Graphical representations are used to visualize both main and interaction effects.

1. Introduction.

Predictive learning estimates an unknown output from known input variables by learning a mapping that minimizes expected prediction loss. The paper frames accurate approximation of the target function as the central goal.

Predictive learning maps joint input values x to a predicted output ŷ through a function F(x).The output is an approximation to an unknown attribute y.
Prediction risk measures the loss or cost incurred when predicted and actual outcomes differ.The expected loss is taken over the joint distribution of inputs and outputs.
A training sample of previously solved cases provides the data for learning an approximation F(x) to the optimal target function F*(x).

2. Ensemble learning.

Ensemble learning constructs predictions from multiple data-derived base learners, with methods differing in learner type, generation procedure, and combination strategy. The paper uses an ISLE-based procedure with subsampling, shrinkage, and regularized linear combination.

Ensemble predictions are linear combinations of multiple base learners derived from the input variables and training data.Each base learner is a function of x, and the ensemble combines their predictions.
Ensemble methods differ in their base learners, how learners are generated, and how combination coefficients are obtained.
The paper's approach uses ISLE to generate base learners and regularized linear regression to estimate their combination parameters.
The lasso penalty shrinks coefficients and often sets many to zero, with λ selected using estimated future risk or cross-validation.
At each iteration, the procedure selects a learner on a random subsample, adds it to the current memory function, and applies shrinkage ν.The learner minimizes loss relative to the preceding ensemble state.
Smaller subsamples reduce computation by N/η and encourage less correlation among ensemble members.

3. Rule based ensembles.

Rule-based ensembles use simple conjunctive rules as base learners and combine rules extracted from decision trees. Tree size controls rule complexity, while regularization and rule scaling affect the fitted predictive model.

Each rule is a conjunction of indicator conditions and is nonzero only when all specified variable-value conditions hold simultaneously.Rules use contiguous intervals for ordered variables and enumerated subsets for categorical variables.
A rule is defined by the variables whose allowed subsets exclude the variables' full value sets.
Rule generation: Decision trees provide a practical source of rules because each node rule is the product of factors along its root-to-node path.The root itself has no corresponding rule.
The rules extracted from all trees form the ensemble, whose predictive model combines the resulting rule functions.The number of available rules depends on the number of terminal nodes across trees.
Tree size directly controls maximum rule complexity: stumps produce one-factor rules, while an L-terminal-node tree can produce rules with up to L −1 factors.
Capturing interactions among l variables requires rules with at least l factors, so higher-order interactions call for larger trees.
The average tree size L̄ controls rule-complexity distribution and can be chosen using prior beliefs, predictive validation, or inspection of selected rules.

4. Accuracy.

Across simulated regression and classification problems, RuleFit ensembles achieved accuracy comparable to strong tree-based ensembles, with RuleFit 500 often among the best-performing methods. The comparison used 100 varied data sets and included sparse rule models.

100 simulated data sets with N = 10000 observations and n = 40 input variables were used to compare four ensemble methods.The target functions were randomly generated to span varied dependence structures and difficulty.
The comparison included MART, ISLE, RuleFit, and RuleFit 200, with RuleFit using 5000 rules and RuleFit 200 using 2000 rules.
Approximately 10% of the fitted rules typically had nonzero coefficients and were needed for prediction.
Regression: RuleFit provided slightly better average regression performance, while RuleFit 200 remained competitive with 500-tree MART but was inferior to 500-tree ISLE.
Regression: RuleFit based on 500 trees was best or nearly best on almost all regression data sets.The comparative error was calibrated against the best method for each data set.
Classification: Both rule-based methods had slightly superior average classification performance, and RuleFit 200 substantially outperformed both 500-tree tree ensembles.
Overall, rule-based ensembles achieved accuracy comparable to the best tree-based ensembles in these regression and classification simulations.

5. Linear basis functions.

Rule ensembles can be complemented with original linear variables to represent both nonlinear and approximately linear dependencies. In the simulation, combining rules and linear terms produced the highest accuracy, although the benefit depends on the target and data characteristics.

Basis-function motivation: Rule ensembles can include additional basis functions beyond their original parametric family to complement functions the other basis functions approximate poorly.The paper emphasizes complementary basis-function families for improving accuracy while retaining interpretability.
Basis-function motivation: Linear targets can require many rules for accurate approximation, making models less reliable with limited data and harder to interpret.This motivates adding original variables as linear basis functions.
Model construction: The combined model uses Winsorized original variables as additional basis functions alongside rules.Winsorization is used for robustness against input-variable outliers, with β chosen according to prior beliefs about outliers.
Simulation illustration: 100 linear variables, 2000 rules, and their union were compared across 100 simulated data sets; the combined ensemble achieved the highest accuracy.The simulation used 10,000 observations and 100 inputs, including nonlinear and linear signal components.
Simulation illustration: The advantage of adding linear functions is greatest with many relevant numeric variables having many distinct values and approximate linear effects.For highly nonlinear targets or variables with few distinct values, improvement may be small, while lasso selection seldom makes inclusion harmful.

6. Rule based interpretation.

The rule-based interpretation framework quantifies the influence of rules and linear predictors globally, locally, and within selected prediction regions. These measures support examining which predictors drive individual or grouped predictions while accounting for the fitted ensemble.

Global predictor influence: Lasso fitting typically sets approximately 80% to 90% of initial rule and linear predictor coefficients to zero.The remaining predictors have varying coefficients according to estimated predictive relevance.
Global predictor influence: Global predictor importance is based on the absolute coefficient of a standardized predictor, with rule importance incorporating rule support.Predictors with the largest importance values are selected for interpretation.
Local predictor influence: Local importance measures estimate the absolute prediction change from removing a rule or linear predictor while adjusting the intercept.Their root-mean-square averages over x equal the corresponding global measures.
Local predictor influence: Local rule importance depends on coefficient magnitude, whether the rule fires at x, and its global support.The complement symmetry assigns equivalent influence when a rule is replaced by 1−r_k(x).
Regional interpretation: Importance measures can be averaged over selected regions, such as cases with high or low predictions or observations belonging to either classification class.This allows interpretation of predictors for individual predictions and targeted subsets.
Regional interpretation: These measures estimate each predictor’s influence after accounting for the other predictors in the ensemble, not necessarily its usefulness alone.Interpretation depends on the accuracy of the coefficient estimates.

7. Input variable importance.

Input-variable relevance is derived from the influence of the rules and linear predictors that contain each variable. The resulting measures can be inspected locally, regionally, or globally.

Variable relevance: An input variable is more relevant when it frequently appears in influential predictors rather than only in weak predictors.Relevant predictors may be rules or linear terms.
Variable relevance: The local importance J_l(x) combines the linear predictor’s importance with the importances of rules containing x_l.Each rule’s importance is divided equally among its defining variables, preventing longer rules from receiving exaggerated influence.
Variable relevance: The distribution of J_l(x) identifies relative variable influence at individual predictions and can be averaged over selected regions or the whole input space.The paper provides data examples illustrating these local, regional, and global summaries.

8. Interaction effects.

The paper detects and interprets interactions through partial-dependence decompositions and variance-based statistics. It identifies interacting variables, interaction order, and strength, while warning that model interactions may be spurious under collinearity.

Interaction definitions: An interaction occurs when changing one variable changes the function differently depending on another variable’s value.The paper defines analogous higher-order interactions and additive behavior when interactions are absent.
Interaction definitions: Rules jointly involving all variables in an interaction subset are necessary but not sufficient for that interaction to appear in the fitted model.Different rules can combine to reduce or eliminate the effect.
Partial dependence: Partial dependence averages over variables outside a specified subset and can be decomposed into lower-order components when interactions are absent.These properties provide the basis for interaction tests.
Interaction statistics: The pairwise statistic measures the fraction of variance in joint partial dependence not captured by separate effects, with zero indicating no modeled interaction.Larger values indicate stronger interaction effects in the predictive model.
Interaction statistics: Statistics for individual variables identify interaction participants, while pairwise statistics identify the variables with which each participant interacts.Only globally relevant variables need be considered, often a small subset of all predictors.
Interaction statistics: Higher-order statistics test whether joint interactions remain after accounting for lower-order effects.The same strategy can be extended to interactions involving more variables.
Interpretive limitations: Interaction statistics detect modeled effects but do not necessarily measure their importance to the overall variation of predictions.An interaction can be statistically strong yet relatively uninfluential.
Interpretive limitations: The method may identify spurious interactions under high predictor collinearity, making low- and higher-order effects difficult to distinguish.Such interactions should not be reported when interpretive value is required.

9. Illustrations.

The paper illustrates its interpretational tools on artificial and real data, using default tree-ensemble settings to generate roughly 2,000 rules.

The interpretational tools are applied to two data sets: one artificial with known truth and one commonly used prediction benchmark.
333 trees with an average of four terminal nodes produce approximately 2,000 rules for the predictive model.These default settings are illustrative, and selective tuning could improve individual results.
The algorithm uses ν = 0.01 and η = min(N/2,100 + 6 under the stated default settings.

9.1. Artificial data.

On simulated data with eight relevant and 92 noise predictors, RuleFit achieves lower prediction and target-estimation errors while recovering variable importance and interaction structure.

Prediction accuracy: RuleFit’s 351-term model achieves average absolute error 0.49, versus 0.61 for main effects only and 0.69 using only linear basis functions.Including additive nonlinear terms improves accuracy by approximately 12% over the purely linear model, while allowing interactions adds approximately 20% improvement.
Rule importance: The six globally most important terms qualitatively describe the known target function and exclude all noise variables.They capture effects involving x1–x8, including a three-variable pattern among x1, x2, and x3 and linear dependences on x7 and x8.
Input variable importance: None of the 92 noise variables has estimated relative importance greater than 5% of that for the eight relevant variables.
Input variable importance: Variables x1, x2, and x3 dominate the highest predictions, whereas x4–x8 are most influential for the lowest predictions.At a single prediction point, the additive variables x6, x7, and x8 are somewhat more influential.
Interaction effects: Variables x1, x2, and x3 are heavily involved in interactions, x4 and x5 interact somewhat less strongly, and x6–x10 show no evidence of interactions.
Interaction effects: Interaction analysis finds a three-variable interaction among x1, x2, and x3 and a two-variable interaction between x4 and x5, with no evidence of others.The interaction-strength plots compare observed strength with a bootstrap null mean and standard deviation.
Graphical interpretation: Partial-dependence plots visualize selected main and interaction effects identified by the preceding importance analysis.The (x1,x3) and (x2,x3) dependencies resemble the (x1,x2) plot, while x8 resembles x7 with opposite slope.

9.2. Boston housing data.

In the Boston housing data, RuleFit models predict median house values with nonlinear and interaction effects, while variable importance and partial-dependence analyses expose global, local, and pairwise structure.

Data and objective: 506 neighborhoods and 13 predictors are used to predict median house value with RuleFit.The response is measured in thousands of dollars.
Predictive performance: 0.33 average absolute prediction error compares with 0.37 for main effects only and 0.49 for linear terms.The results indicate substantial nonlinearity with some evidence for interaction effects.
Variable importance: LSTAT is the most important global predictor, with a negative linear effect on housing values.AGE has a similar but weaker effect, while a key rule identifies five exceptionally high-value neighborhoods using DIS, PTRATIO, and small LSTAT.
Variable importance: Variable importance changes by prediction region: LSTAT dominates the lowest predicted values, whereas RM leads for the highest predicted values.For Manchester, RM and TAX are relatively more influential while LSTAT is less influential.
Interaction effects: Strong interactions involve NOX, RM, DIS, PTRATIO, and LSTAT, with pairwise effects linking RM and LSTAT to multiple variables.No three-variable interactions involving RM or LSTAT were detected.
Partial dependencies: Partial-dependence plots show that housing values sharply increase when LSTAT and DIS are simultaneously very small.The plots examine the four variable pairs identified as participating in two-variable interactions.

10. Related work.

Related methods use rules, trees, boosting, averaging, or regularized regression for prediction and interpretation. RuleFit differs by fitting an additive, coefficient-weighted ensemble of rules and linear terms rather than selecting one rule per prediction.

Rule induction: Earlier rule methods include pruned terminal-node rules from C4.5, sequential covering, and manually modified C4.5 rules.These approaches construct disjunctive rule sets or use rules as predictors in logistic regression.
RuleFit distinction: RuleFit produces additive models of rules and linear terms with optimized coefficients, unlike methods using one rule from a disjunctive set for each prediction.Its coefficients are fit through regularized regression rather than simple averaging.
Rule ensembles: Related ensembles include stochastic discrimination, SLIPPER, and lightweight rule induction, using random weak learners or sequentially induced boosted rules.The cited literature reports competitiveness or performance advantages under particular rule-set sizes and settings.
Regularized rule models: Regularized regression has also been used to construct weighted rule ensembles for classification from an outcome-independent initial rule set.The procedure adds rules in a predefined order and repeatedly fits a regularized regression.
Interpretation: Variable-importance methods for trees and ensembles include split-based risk improvements and permutation-based increases in prediction risk.These measures describe marginal influence in the presence of other variables and may not reflect usefulness in isolation.
Interaction analysis: Interaction analysis has used functional ANOVA and product measures, whereas RuleFit uses partial-dependence functions without functional ANOVA decomposition.The related work notes product-measure limitations for observational data and proposed alternatives.