A Gradient-Based Split Criterion for Highly Accurate and Transparent Model Trees

1 Introduction

With recent advances in Machine Learning and increasing computational power, automated predictive and decision making systems become widely used and influence peoples lives in many aspects. Applications include personal assistance, advertisement, scoring solutions, fraud prevention and recommendation systems.

Predictive models are influencing our daily lives more and more, thus creating an increasing interest in understandable and transparent predictive models. This interest is opposed by the interest in highly accurate systems. Complex systems, such as neural networks or ensemble models, have shown superior predictive power for a wide range of applications and datasets. This high predictive power comes at the costs of transparency:

"The best explanation of a simple model is the model itself; it perfectly represents itself and is easy to understand. For complex models, such as ensemble methods or deep networks, we cannot use the original model as its own best explanation because it is not easy to understand." [Lundberg and Lee, 2017]

As a consequence, the choice of a predictive model for a specific task includes a trade-off between simplicity and transparency on one side and complexity and higher predictive power on the other side. If the task is mainly driven by the quality of the prediction, complex state-of-the-art models are best suited. Yet, many applications require a certain level of transparency. This can be driven by regulatory constraints, but also by the user's wish for transparency. A recent study shows that model developers often feel the pressure to use transparent models [Veale et al., 2018], even if more accurate models are available. This leads to simple models, such as linear or logistic regression, where more complex models would have much higher predictive power. In other cases, transparency is not required, but optional. An economic pressure towards models with higher accuracy may lead to low transparency in many important applications. For all these reasons, improving the accuracy of simple models can help to preserve transparency and improve predictions.

In this work, we present shallow model trees as a way to gain high predictive power with a highly transparent model. A model tree is similar to a decision tree. It consists of a set of rules that form a tree structure. Each leaf contains a simple predictive model. Thus, a model tree is a collection of simple models combined with a set of rules to select a model for each input sample. Shallow model trees consist only of few models and rules. Our experiments show that even a model stump, which uses two simple models, can significantly improve the predictive power, when compared to using only a singe simple model.

Figure 1 shows a schematic explanation of a model stump. The strength of the influence of features is used to explain a simple linear model. The model stump consists of two such models. Both are connected by single rule in the root node.

1.1 Our Contribution

The main contributions of this work are:

1. Shallow model trees as a way to combine transparency with high predictive power.
2. A novel split criterion for model trees that allows for significantly higher accuracy when compared to stateof-the-art model trees.
3. The theoretical foundation of the split criterion.

4. Themechanismof renormalization that further improves predictive power of the presented model trees.

The rest of the paper is organized as follows: In Section 2, we give a brief overview of related work. Section 3 introduces our novel method for creating model trees and gives the theoretical background. Section 4 extends this method to further improve the predictive power. In Section 5, we show the effectiveness of our method on various datasets for classification and regression problems. Finally, Section 6 summarizes this works and gives an outlook and further research.

2 RelatedWork

2.1 Transparency and Explainability

The recent developments of more and more complex predictive models causes an increasing interest in transparency and explainability of predictions. Du et al. present a survey of different explainability approaches [Du et al., 2018]. They distinguish between model-wise and prediction-wise explainability. The former one aims at interpreting a predictive model as a whole, while the latter one explains single preditions. In their comprehensive survey on black box explanation methods, Guidotti et al. distinguish between four different explanation problems [Guidotti et al., 2018]: model explanation aims at model-wise explanation and outcome explanation aims at prediction-wise explanation (analogous to Du et al.). Additionally, they identify the black box inspection, aiming at gaining insides about the unknown interna of a blck box model, and the transparent design problem, aiming at finding predictive methods that are explainable by themselves. In this setting, our work mainly addresses the transparent design problem.

Mimic learning is one way to explain a predictive model as a whole. The idea is to approximate a complex model by a simpler, transparent model. Earlier works include approaches that use decision trees as simple models for mimic learning [Bastani et al., 2017; Vandewiele et al., 2016; Craven and Shavlik, 1996; Schmitz et al., 1999]. Dancey et al. used logistic model trees for mimic learning [Dancey et al., 2007] of neural networks. Although our algorithm can be used in the same way for mimic learning of complex models, this is out of scope for this work and not covered by our experiments. Another approach for model-wise explainability is to measure the feature importance [Altmann et al., 2010; Hastie et al., 2009].

Prediction-wise explainability does not provide an overall explanation, but concentrates on single samples. One approach towards that goal is to use gradients or Taylor approximations at the given sample point [Kasneci and Gottron, 2016; Bach et al., 2015]. Other approaches distort the input to measure the effects of different features on the input [Fong and Vedaldi, 2017; Robnik-ˇSikonja and Kononenko, 2008; Zintgraf et al., 2017]

While most of the above work explains existing models, there is also a body of research on explainability by model design. One can argue that mimic learning falls into this category, depending on whether the newly created simple model is used for explanation purposes only or whether it serves as a replacement for the more complex model. Other approaches include constraints to derive simple models [Freitas, 2014] and regularized representations [Zhang et al., 2018]. By using shallow model trees, this work also deals with explainability by model design. In difference to other approaches, our approach does not add constraints and restrictions to a complex model (except the preference of shallow trees), but rather uses a simple model, which is already highly explainable, and increases its predictive power to make it more attractive for real-world applications.

For a more comprehensive survey on explainability and transparency, we refer to [Guidotti et al., 2018; Du et al., 2018].

2.2 Tree-Based Prediction

Tree-Based models are a widely used class of predictors. A basic form are decision trees [Safavian and Landgrebe, 1991; Quinlan, 1993; Hastie et al., 2009], which can be used for both, regression and classification. Decision trees are highly transparent and explainable as long as they are restricted in depth.

A way to increase the predictive power of decision trees is to use ensembles of trees, such as random forests [Breiman, 2001] or gradient boosted trees [Chen and Guestrin, 2016]. Again, the increase of predictive power comes at the costs of explainability.

Another class of tree-based predictors are model trees. These are similar to decision trees with the difference that each node contains a simple predictive model instead of a fixed value. The M5 model tree algorithm [Quinlan and others, 1992; Wang and Witten, 1997] for regression is constructed by using decision tree construction rules and is followed by the training of linear models in the nodes. The logistic model tree [Landwehr et al., 2005] warm-starts the training of child-nodes, using the trained model of the parent nodes.

Another approach for training model trees is to train for each potential split a model in each child node [Potts and Sammut, 2005] and to compute for each potential split the loss on the training set. This allows finding the split with respect to the node-models by using the loss as split criterion.

On the downside, we see high computational costs that allow to test only a small number of potential split points (such as five per feature dimension in case of [Potts and Sammut, 2005]). In difference to existing model tree approaches, our approach does not use existing decision tree constructions methods, but uses a method that is optimized for model trees, which results in improved predictive power. Unlike [Potts and Sammut, 2005], our criterion can be computed much more efficiently and allows testing considerably more split points.

Hierarchical mixtures of experts [Jordan and Jacobs, 1994] are a similar concept with probabilistic splits. As a consequence, the final prediction is a probabilistic mixture of all leaf models. Originally, each split depends on a combination of all features, which reduces the explainability. Wang et al. [Wang et al., 2015] present an extension that aims at sparse representations to increases explainability. In difference to our approach, the split criterion depends on multiple features, which results in more complex and less transparent splits. Furthermore, the larger search space in combination with the EM algorithm leads to much higher computational costs. Another approach by Sokolovska et al. [Sokolovska et al., 2018] avoids hierarchical structures by splitting features independently of each other. This leads to ∏mi=1 (ni + 1) regions / linear models (here, ni is the number of split points along feature dimension i), which is potentially much higher than in tree structures.

3 Model Tree Construction

The idea of model trees has already been around for several years. In this section, we introduce a novel way to construct model trees. This allows for significantly higher predictive power than state-of-the-art model trees without increasing the number of nodes.

In the following, we briefly introduce current model tree algorithms (in 3.1). We then introduce the idea of our method (in 3.2). Subsequently, we present the theoretical background of our method (in 3.3). In the end of this section, we present an efficient way to compute the novel split criterion (in 3.4).

3.1 Model Tree Algorithms

Model trees have many aspects in common with decision trees, with the major difference that leaf nodes do not contain prediction values, but predictive models instead. Analogously to ensemble methods, we refer to these predictive models as weak models.

Typically, a model tree is constructed by creating a decision tree and training weak models in the leafs [Quinlan and others, 1992]. Algorithm 1 shows a basic version of recursively constructing a model tree. Approaches that train one weak model for each split [Potts and Sammut, 2005] also fit into the framework of Algorithm 1, but provide a different (and computationally expensive) way to compute the gain. We refer to the literature [Hastie et al., 2009] for further details, such as the definition of candidate splits and the gain computation, as well as improvements, such as pruning, smoothing or handling missing data.

Similar to [Landwehr et al., 2005], in the depicted algorithm weak models are trained in all nodes of the tree. This is not required for model trees, but helpful for our novel method.

Algorithm 1 Training Model Trees

1: function BUILDNODE(X ∈ Rn×m, y ∈ Rn , d ≥ 0) 2: node←NewNode() 3: node.model←TrainWeakModel(X, y) 4: if d > 0 then 5: T ←GetCandidateSplits(X) 6: S ← arg maxS′∈T Gain(X, y, S′ ) 7: node.split ← S 8: node.left ← BuildNode(XS , yS , d - 1) 9: node.right ← BuildNode(X ¯ S, y¯ S, d - 1) 10: end if 11: end function

3.2 Toward a Better Split Criterion for Model Trees

Current model tree construction uses the decision tree construction algorithms with the extension that weak models are trained in the nodes. Model trees typically use the same loss/gain measure as decision trees, e.g. squared error for regression and cross entropy / information gain for classification [Quinlan and others, 1992; Landwehr et al., 2005].

These loss/gain measures are optimized for decision trees. Although such decision tree measures have been shown to yield good results for model trees, a model-tree-specific gain/loss measure can significantly improve the predictive power of the resulting trees. An example can be seen in Fig. 2. The cross-entropy measure results in a split that separates both classes in a best-possible way, but gets nearly no improvement frommodels in the leafs (Fig. 2(b)). A better split for model trees would take into account the weak models and makes the classes separable by the weak models instead of directly separating them in the best possible way (Fig. 2(c)).

Based on this observation, the major part of this work is a novel gain/loss measure that results in improved model tree predictions without the need to increase the number of nodes. Hence, our work improves the predictive power without changing the interpretability of a shallowmodel trees.

3.3 Gradient-Based Split Criterion

We greedily construct the model tree, similar to Algorithm 1. The major novelty is the way to measure the gain of a potential split of a node. In the following, we present the theoretical background of our method and derive the split criterion. A list of symbols and terms used can be found in Tab. 1.

Training a Weak Model

Let Mθ be the class of weak models with parameters θ. Our approach handles any weak model that can be trained by (stochastic) gradient descent. Nevertheless, with transparency in mind, we recommend to use simple models such as linear or logistic regression.

Given a sequence (xi, yi)i=1,...,n of training samples, a loss function L : R × R → R and a set I ⊆ {1, . . . , n} of samples that correspond to a certain node 1 , then training a weak model results inMθI with

1 For the root node I = {1, . . . , n}. Each child node only holds a subset of the parent nodes training data.

Gain Approximation

When optimizing for θS, one can warm-start the gradient descent by using θI as an initial value [Landwehr et al., 2005]. This will reduce the number of required gradient descent steps and speed up the learning. A rough estimation of θS is then already given by a single gradient descent step:

This estimation works better for simple models, which typically require less gradient descent steps then complex models.

This approximation can be computed efficiently (as we will describe in 3.4), but we still have to apply for each set S the model MθS to all samples in S in order to compute the loss LθS (S). Doing so would still be computationally intractable. For this reason, we simplify the computation of the loss using a Taylor approximation around θI :

Finally, we get an approximation of the loss:

Using this approximation, the gain of all possible split points can be computed and the split with the maximal approximated gain can be used in the tree construction. Here, λ is just a scaling factor and can w.l.o.g. be set to 1. In the following, we will show an efficient way to this approximation.

Optimal Split

We represent a split of a node by the subset S ⊂ I of samples that go into the left child node ( ¯ S = I\S is the complement that goes into the right child node). Generalizing from decision trees, the gain of the split S can then be defined as the reduction of the loss by using weak models in the child nodes instead of using one model in the parent node:

Using this gain, the optimal split can be found by computing the gain for each possible split and taking the split with the maximal gain. This requires computing θS and θ¯ S that is training weak models for all possible child nodes. This is computationally intractable to do for all potential split points. In [Potts and Sammut, 2005], this is done by limiting the number of candidate-splits to five per feature dimension. To overcome this limitation, we present in the following a method to approximate the gain.

Algorithm 2 Gradient-Based Split Finding

Require: Index Set I, Optimized Parameters θI, Training

Data (xi, yi)i∈I 1: jOpt, tOpt, gainOpt ←-1 2: gi ←∇θI L(yi,MθI (xi)) 3: gI ← ∑i∈I gi 4: gS ← (0, 0, . . . , 0)T 5: for feature j = 1, . . . ,m do 6: Sort gi and xi according to feature x·,j 7: for Split Point tk along feature j do 8: U ← {i ∈ I|tk-1 < xi,j ≤ tk} 9: gS ← gS + ∑i∈U gi 10: g ¯ S ← gI - gS 11: gain ← ‖gS‖22 + ‖g ¯ S‖22 12: if gain > gainOpt then 13: jopt ← j; topt ← tk; gainopt ← gain 14: end if 15: end for 16: end for 17: return jOpt, tOpt, gainOpt

3.4 Implementation

The split measure (6) requires to compute the L2 norm of the gradients in both split sets S and ¯ S. This has to be done for every candidate split S. Although feasible, the computation is expensive. The gain-computation for all splits is based on the same sample-wise gradients

These only need to be computed once per node. For continuous features, every split candidate is given by a feature index j and a threshold t, which leads to S = {i ∈ I|xi,j ≤ t}. By sorting along values of feature j, the split measure (6) can efficiently be updated. Algorithm 2 shows an efficient way to compute the split criterion by updating the sum of the gradients. This can then be used as an implementation for lines 5 and 6 in Algorithm 1.

This can even be improved further by using the fact that θI is optimized on I. This means that the gradient gI is approximately zero (otherwise, θI is not optimized). As a consequence, g¯ S = -gS. Due to practical considerations, such as stopping criteria for stopping before reaching gI = 0 or the usage of mini-batches, we do not directly set gI to zero, but compute it as described in line 3 of Algorithm 2.

Note that our algorithm trains exactly one model for each node. It then uses gradients gi of this trained model to approximate the gain and to find the optimal split point. With this split point, we train afterwards exactly one weak model for each child node. The training of child nodes can be warmstarted by the learned parameters θI of the parent node's weak model.

4 Renormalization

The previous section introduced the gradient-based split criterion. Due to the approximations used, the split quality measure directly depends on the gradient. Unfortunately, the gradients are often not translation invariant, i. e. shifting the feature values can change the optimal split point (in terms of criterion (4)). Furthermore, gradient descent often shows low performance and slow convergence when the input data is poorly scaled. Note that each split shrinks / restricts the domain of one feature for the child nodes. As a consequence, data that was normalized on the whole training set might lead to poorly normalized subsets in the leafs.

We renormalize the training data to work with normalized data in each node. We then get an improved, translation invariant version of approximation (4) and also speed up and improve the model training via gradient descent by providing well scaled input features. The renormalization only takes into account the training data from set S. As a consequence, the renormalization is done for each potential split individually.

A basic approach is to renormalize the features for S and ¯ S, compute the gradients on these normalized features and compute the loss according to (5). Computing all gradients anew for each potential split is intractable. In addition, the weak model of the parent node is trained on differently normalized features, which complicates the gradient computation.

In the following, we present the mathematical background of our renormalization approach. The theory leads to a computationally more efficient way to compute the gradients from renormalized features. Subsequently, we present the explicit computation for linear models, such as linear and logistic regression, in combination with linear renormalizations, such as z-normalization and min-max-normalization.

4.1 Theory

Given a potential split S ⊂ I, the corresponding training features xi can be normalized, e.g. by using a z-normalization. In the most general form, the normalization is a transformation TS : xi ↦→ ˜xi from original feature space into a normalized feature space. We further restrict TS to be compatible with the model, i.e. for each parameter θ, there must exist a parameter ˜ θ with

As a consequence, the transformed loss ˜ L can be written as:

Analogously to (5), the loss can be approximated using gradients in the normalized feature space:

Note that there is a functional dependency between θ and ˜ θ, which allows computing the last gradient in (10). For simple models, such as linear or logistic regression, Equation (10) often gives better approximations of the gain than (5). For such models, normalizing the features speeds up the gradient descent convergence and leads to better approximations after one step.

Still, normalizing and computing the gradients for each step individually is computationally infeasible. Rewriting the gradients can help to find a faster computation:

This means that only one computation of the gradient per node is required. It can then be corrected using the derivative ∂θI ∂ ˜ θI . This can be done in Algorithm 2 in line 11 by adding this sample-independent factor. Note that this derivative has to be computed for each potential split set anew. In the linear case, this can be done efficiently:

4.2 Linear Case

Linear models have the form

with a function f : R → R. For linear regression, f is the identity, while for logistic regression f is the logistic function. Linear normalizations can be written as

where A is a diagonal matrix, e.g. for z-normalization, A contains the inverse standard deviations of all features. Based on (8) and (12) follows:

The partial derivative can then be written as:

For z-normalization, A and c depend on mean and the standard deviation. For min-max normalization, A and c depend on minimum and maximum. Both cases can efficiently be updated when computing the sum of the gradients (see also Algorithm 2 for updating computations).

It is worth noting that once a model with linear weak models is trained, one can create an equivalent model that operates solely on the unnormalized data by applying the inverse normalization steps on split points and model weights. This can be used speed up the predictions done with such a model, e.g. in real-time scenarios where each prediction has to be performed within few milliseconds.

4.3 Example

In order to demonstrate the improvement from renormalizing the data, we computed the split gain along the two axes of the previous example. Figure 3 shows three different methods to compute the gain. It can be seen that cross entropy finds the best split on the y-axis while the presented gradient-based method finds a better point on the x-axis. Still, the ideal point (in terms of the loss of the resulting model tree) can be found using the renormalization technique.

5 Evaluation

The previous sections introduced our novel method to create model trees. In this section, we will evaluate the effectiveness of this novel method on multiple datasets. The experiments cover both classification and regression.

5.1 Datasets

For the experiments, we used the multiple datasets. These datasets include financial and medical datasets, where decisions can have a high impact and, hence, transparent predictions are required. All datasets come from public sources 2 [Yeh and Lien, 2009; Zikeba et al., 2016] and cover both classification and regression tasks. The number of samples and attributes of these datasets are displayed in Tab. 3.

5.2 Methods

We compare the performance of different methods with each other. As a baseline, we use the weak models Lineare and Logistic Regression (Lin) as well as Decision Trees (DT). As a reference complex model, we use XGBoost (XGB) [Chen and Guestrin, 2016]. This model has been shown to be robust towards the choice of hyper parameters. Furthermore, we use model trees with state-of-the-art split criteria od decision trees (MT-DT). These are mean-square-error for regression and the entropy-based information gain for classification.

All these methods are compared with two versions of our model trees. The original version from Section 3 (MT-G)

2 https://archive.ics.uci.edu/ml/datasets/Polish+companies+ bankruptcy+data, https://archive.ics.uci.edu/ml/datasets/Breast+ Cancer+Wisconsin+(Diagnostic), https://archive.ics.uci.edu/ml/ datasets/Census-Income+%28KDD%29, https://archive.ics.uci.edu/ ml/datasets/default+of+credit+card+clients, https://www.kaggle. com/heesoo37/120-years-of-olympic-history-athletes-and-results, https://www.kaggle.com/harlfoxem/housesalesprediction, https://www.kaggle.com/budincsevity/szeged-weather

and the version using renormalization (MT-GR). With transparency and shallow trees in mind, we restrict all model trees to a fixed depth of 1, 2, or 3. In our experiments, we evaluate the effect of using different maximal depth limits.

5.3 Experiments

For our experiments, we performed 4-fold cross validation and averaged the 4 performance measurements.

Classification. We use the area under the roc-curve (auc) as measure for classification. The classification results are shown in Tab. 2 (a). It can be seen that the gradient-based model trees with renormalization provide the best results, often even a model stump (depth = 1) results in significantly higher auc than logistic regression. The exception is the census dataset that can sufficiently be modeled by logistic regression. Additional splits in models trees only create slight overfitting effects. In two cases, model trees even out-perform XGBoost.

Regression. We evaluate the regression experiments using the r2 -measure. The results are shown in Tab. 2 (b). Our results show that the renormalized version of our splitting criterion consistently creates the best results and each new level of depth increases the predictive power.

6 Conclusion

Starting with the motivation to find a transparent model with high predictive power, our work concentrated on shallow model trees. While state-of-the-art model trees are highly transparent, their predictive power bears potential for improvement. In this work, we presented a novel way to create model trees, which has a strong theoretical foundation, is efficient and results in higher predictive power than current model tree algorithms. Given a high requirement of transparency, our gradient-based model trees are powerful method for automated predictive and decision making systems.

Based on this work, we aim at further improvements of this method. This includes ways to enhance the explainability, e.g. through regularization terms that prefer round numbers as split points.