PaperlayerView exact revision on arXiv

Source-linked AI summary

Interpreting Tree Ensembles with inTrees

Houtao Deng

arXiv:1408.5456v1cs.LGstat.ML

TL;DR

Tree ensembles are accurate but difficult to understand, debug, and deploy. inTrees extracts and processes interpretable rules, measures their quality, selects compact rule sets, and uses processed rules for prediction; the work demonstrates that these rules can remain accurate.

  • Problem

    Tree ensembles are accurate supervised learners but difficult to understand, debug, and deploy.

  • Method

    inTrees extracts, measures, and processes ensemble rules, applies feature selection to obtain relevant non-redundant conditions, and assigns outcomes for prediction.

  • Results

    Processed tree-ensemble rules can be accurate for prediction, and STEL outperforms rpart significantly on 13 data sets while losing significantly on 5.

  • Takeaways & Limitations

    The framework provides a way to turn tree-ensemble rules into compact, interpretable rule-based predictors.

  • Takeaways & Limitations

    Random-forest rule outcome assignments may be unreliable because each rule is evaluated on a training-data subsample.

Abstract

from arXiv · show

Tree ensembles such as random forests and boosted trees are accurate but difficult to understand, debug and deploy. In this work, we provide the inTrees (interpretable trees) framework that extracts, measures, prunes and selects rules from a tree ensemble, and calculates frequent variable interactions. An rule-based learner, referred to as the simplified tree ensemble learner (STEL), can also be formed and used for future prediction. The inTrees framework can applied to both classification and regression problems, and is applicable to many types of tree ensembles, e.g., random forests, regularized random forests, and boosted trees. We implemented the inTrees algorithms in the "inTrees" R package.

1. Introduction

Tree ensembles are accurate supervised learners but difficult to understand, debug, and deploy. inTrees addresses these challenges by extracting and processing interpretable rules, interactions, and a rule-based learner from ensembles.

  • 1. Introduction: Tree ensembles capture information accurately but can be difficult to understand, debug, and deploy.Deployment is especially difficult when models are trained offline in one language and applied online in another.
  • 1. Introduction: inTrees extracts interpretable information from tree ensembles through algorithms for extracting, measuring, pruning, and selecting rules.The framework also discovers frequent variable interactions.
  • 1. Introduction: Processed ensemble rules can be summarized into a rule-based learner for future predictions.The framework can also process extracted rules without the rule-summarizing step.
  • 1. Introduction: inTrees is independent of the tree-ensemble building process when each tree is transformed into the required format.Its algorithms can be applied to each tree in parallel and implemented in distributed computing environments.

3. Extract Rules

The framework extracts rules from root-to-leaf paths in tree ensembles, representing each rule as a condition of variable-value pairs with an associated outcome. It can instead extract conditions and assign outcomes using all training data.

  • 3. Extract Rules: A rule is extracted from a decision tree’s root-to-leaf path and represented as {C ⇒T}, where C is a conjunction of variable-value pairs and T is the outcome.Rules extracted from an ensemble combine rules extracted from its individual decision trees.
  • 3. Extract Rules: The extraction procedure aggregates variable-value pairs along each path and records the leaf prediction when a leaf is reached.The algorithm tracks the current node, split condition, leaf status, and prediction.
  • 3. Extract Rules: Because tree outcomes may be based on only part of the training data, inTrees can extract conditions and reassign outcomes using all training data.This separates condition extraction from potentially unreliable tree-level outcome assignments.
  • 3. Extract Rules: Extracting conditions without ensemble-assigned outcomes also supports descriptive regression rules by discretizing the target.For example, a continuous outcome can be represented with a descriptive category such as large.

4. Measure rules

inTrees measures rule quality using frequency, error, and complexity, then ranks rules with these metrics individually or in combination. Maximum-depth extraction can reduce computation and help avoid overfitting rules.

  • 4. Measure rules: Rule frequency is the proportion of data instances satisfying its condition, measuring the rule’s popularity.Frequency can be used to rank extracted rules.
  • 4. Measure rules: For classification, rule error is the incorrectly classified instances divided by instances satisfying the condition; for regression, it is mean squared error.The regression error uses target values for instances satisfying the rule condition.
  • 4. Measure rules: Rule complexity is the number of variable-value pairs in its condition, and shorter rules may be preferred when frequency and error are similar.Shorter conditions are treated as more interpretable under this comparison.
  • 4. Measure rules: Setting a maximum extraction depth can reduce computations and may avoid extracting overfitting rules because useful splits tend to occur near tree tops.maxDepth=-1 specifies no depth limitation.

5. Prune rules

inTrees prunes rule conditions by removing variable-value pairs whose omission has little effect on a chosen error metric, using sequential leave-one-out testing. This produces shorter rules while retaining pairs judged important under the threshold.

  • Rule conditions may contain irrelevant variable-value pairs, so inTrees provides methods to prune them.
  • The pruning metric E can be training error, validation error, or pessimistic error combining training error and model complexity.Smaller E indicates a better rule, and the method assumes E ≥0.
  • Decay measures the effect of removing pair i as either relative error increase or absolute error increase, with s stabilizing cases where original error is near zero.The R package sets s = 10^-6 for the relative-decay formulation.
  • Pairs with decay below a threshold such as 0.05 may be removed through leave-one-out pruning.Pairs are evaluated sequentially, updating the current rule and its baseline error after each removal.

6. Select Rules

inTrees selects compact, relevant, non-redundant rules by converting rule satisfaction into binary features and applying feature-selection methods. Its complexity-guided extension incorporates condition length into regularized random forest selection, with optional global importance weighting.

  • Because many extracted rules can be redundant, inTrees seeks a compact set of relevant and non-redundant rules.
  • 6.1. Rule selection via feature selection: The method creates binary variables indicating whether each condition is satisfied, combines them with targets, and applies feature selection to choose conditions.Selected conditions can then receive outcomes for prediction.
  • 6.2. Complexity-guided condition selection: Unlike earlier feature selection that ignored condition complexity, the framework uses guided regularized random forest to incorporate condition length.
  • 6.2. Complexity-guided condition selection: Regularized random forest penalizes variables not previously used for splitting, while adding a variable when it contributes enough new predictive information.
  • 6.2. Complexity-guided condition selection: GRRF assigns larger regularization coefficients to variables with greater global importance, increasing their regularized information gain when gains are otherwise similar.
  • 6.2. Complexity-guided condition selection: The complexity-guided extension makes λi smaller for longer conditions, thereby penalizing longer rule conditions more strongly.λ0 is the base coefficient, li is condition length, l* is the maximum condition length, and γ controls the length-regularization weight.
  • 6.2. Complexity-guided condition selection: An optional extension adds normalized ordinary-RF importance through β, which controls the weight assigned to global importance scores.
  • 6.2. Complexity-guided condition selection: GRRF can provide variable scores, but those scores may favor variables entering the selected subset earlier in feature selection.An ordinary RF can be built on selected variables to calculate scores for selected conditions.

7. Variable interaction extraction based on association rule analysis

inTrees uses association rule analysis to discover frequent variable interactions in tree-ensemble rules by treating variable-value and target-value pairs as items.

  • inTrees extracts frequent variable interactions from tree-ensemble rules using association rule analysis.
  • Support measures how often a condition occurs, confidence measures how consistently it co-occurs with an outcome, and length counts rule items.
  • Each variable-value or target-value pair in a tree-ensemble rule is treated as an item.
  • Association rules are restricted so their conditions contain variable-value pairs and their outcomes contain target-value pairs.
  • For numeric variables, treating variables rather than exact variable-value pairs as items can address sparse combinations in extracted rule sets.

8. Simplified tree ensemble learner (STEL)

STEL summarizes extracted tree-ensemble rules into an ordered rule list that predicts with the first satisfied rule, while pruning infrequent rules and selecting rules by error and tie-breaking criteria.

  • The simplified tree ensemble learner (STEL) summarizes tree-ensemble rules into a rule-based learner for future prediction.
  • STEL applies rules from top to bottom and uses the outcome of the first satisfied rule as the new instance’s prediction.
  • Rules below a frequency threshold, such as 0.01, are removed from the candidate set to avoid overfitting.
  • Each iteration selects the minimum-error rule, preferring higher frequency and then shorter conditions to break ties.
  • After selecting a rule, STEL removes matching instances from consideration and updates the default rule and rule metrics.
  • The approach builds on rule summarization ideas while addressing tree-ensemble rules containing numeric or discrete variables.

9. Transform regression rules to classification rules

inTrees transforms regression rules into more descriptive classification rules by discretizing the target after extracting conditions from a regression tree ensemble.

  • Regression rules with numeric outcomes can be less interpretable than classification rules with descriptive outcome labels.
  • The framework extracts conditions from a regression ensemble, discretizes the target, and applies classification-rule methods to those conditions.
  • This transformation avoids rebuilding the tree ensemble after discretizing the target variable.

10. Illustrative Examples

The examples demonstrate inTrees from rule extraction through rule measurement, pruning, selection, ordered classification, and interaction discovery on a team-optimization dataset.

  • Team optimization example: The team-optimization example defines winning as exactly one of players 1 and 2 being selected.
  • Rule extraction: A regularized random forest with 100 trees yielded 1,923 extracted rule conditions and 1,835 unique conditions after deduplication.
  • Rule measurement: inTrees assigns outcomes to conditions and computes rule length, frequency, and error for measurement and ranking.
  • Rule measurement: The original random-forest rule outcomes may be unreliable because each rule is evaluated on only a training-data subsample.
  • Rule selection: Guided regularized random forest is applied to pruned rules to select a compact rule set.
  • STEL classifier: The selected rules form STEL, an ordered classifier whose conditions can be executed directly in R.
  • Variable interactions: The four most frequent variable interactions captured the true patterns, with about 4% support and confidence equal to 1.
  • Variable interactions: High support alone was insufficient: the fifth and sixth interactions exceeded 3% support but had confidence below 70%.

11. Experiments

The experiments evaluate STEL against rpart across 20 UCI data sets and examine the accuracy and frequency of extracted rules. STEL achieves significantly lower error on more data sets than rpart, while most selected rules have zero error.

  • STEL evaluation: STEL was compared with rpart on 20 UCI data sets using random forests with 100 trees and repeated train-test sampling.Each run trained on two-thirds of the data and tested on the remaining one-third; the procedure was repeated 100 times.
  • STEL evaluation: When STEL outperformed rpart, most relative differences exceeded 10%; when it lost, only one relative difference exceeded 10%, at 16.6%.Relative difference was calculated from the larger and lower error rates.
  • Rule analysis: Most accurate rules with frequency greater than 0.1 had error rates of 0.The rule for “led7” exceeded 0.2 error, consistent with that data set’s relatively high error rate.

12. Conclusions

The conclusions present inTrees as a framework for processing tree-ensemble rules and extracting interactions across classification and regression settings. Processed rules can remain accurate for prediction while supporting rule-based analysis across several ensemble types.

  • Framework: inTrees extracts, measures, prunes, selects, and summarizes rules while discovering frequent variable interactions from tree ensembles.Its components can be used sequentially or selectively, including to form a learner for predicting new data.
  • Scope and implementation: The framework applies to classification and regression problems and supports random forests, regularized random forests, and generalized boosted regression models.These capabilities are implemented in the inTrees R package.
  • Implications: Processed rules from tree ensembles can remain accurate, while tree ensembles support mixed categorical and numeric predictors and both classification and regression.The authors contrast this scope with associative classification methods that require discrete predictors.
Loading 1408.5456v1…