1

ToPs: Ensemble Learning with Trees of Predictors

arXiv:1706.01396v2 [] 13 Feb 2018

Jinsung Yoon, William R. Zame, and Mihaela van der Schaar, Fellow, IEEE

Abstract—We present a new approach to ensemble learning.
Our approach differs from previous approaches in that it
constructs and applies different predictive models to different
subsets of the feature space. It does this by constructing a tree of
subsets of the feature space and associating a predictor (predictive
model) to each node of the tree; we call the resulting object a tree
of predictors. The (locally) optimal tree of predictors is derived
recursively; each step involves jointly optimizing the split of the
terminal nodes of the previous tree and the choice of learner
(from among a given set of base learners) and training set –
hence predictor – for each set in the split. The features of a new
instance determine a unique path through the optimal tree of
predictors; the final prediction aggregates the predictions of the
predictors along this path. Thus, our approach uses base learners
to create complex learners that are matched to the characteristics
of the data set while avoiding overfitting. We establish loss bounds
for the final predictor in terms of the Rademacher complexity
of the base learners. We report the results of a number of
experiments on a variety of datasets, showing that our approach
provides statistically significant improvements over a wide variety
of state-of-the-art machine learning algorithms, including various
ensemble learning methods.
Index Terms—Ensemble learning, Model tree, Personalized
predictive models

I. I NTRODUCTION
NSEMBLE methods [1], [2], [3], [4] are general techniques in machine learning that combine several learners;
these techniques include bagging [5], [6], [7], boosting [8],
[9] and stacking [10]. Ensemble methods frequently improve
predictive performance. We describe a novel approach to
ensemble learning that chooses the learners to be used, the way
in which these learners should be trained to create predictors
(predictive models), and the way in which the predictions of
these predictors should be combined according to the features
of a new instance for which a prediction is desired. By jointly
deciding which learners and training sets to be used, we provide
a novel method to grow complex predictors; by deciding how
to aggregate these predictors we control overfitting. As a result,
we obtain substantially improved predictive performance.
Our proposed model, ToPs (Trees of Predictors), differs
from existing methods in that it constructs and applies different
predictive models to different subsets of the feature space. Our
approach has something in common with tree-based approaches
(e.g. Random forest, Tree-bagging, CART, etc.) in that we

E

J. Yoon is with the Department of Electrical Engineering, University of
California, Los Angeles, CA, 90095 USA e-mail: jsyoon0823@ucla.edu.
W. R. Zame is with the Departments of Mathematics and Economics, University of California, Los Angeles, CA, 90095 USA e-mail: zame@econ.ucla.edu.
M. van der Schaar is with the Department of Engineering Science, University
of Oxford, OX1 3PJ UK e-mail: mihaela.vanderschaar@oxford-man.ox.ac.uk.
This paper has supplementary downloadable material available at http:
//ieeexplore.ieee.org, provided by the author. The material includes additional
experiment results, other related works and the details of experimental settings.
This material is 1.0MB in size.

Objective: Minimize impurities

19/40
High-risk
Patients (19)

Diabetic

Entire
Patients (40)

NonDiabetic

Age
(20-29)

1/5

0/5

Age
(30-39)

2/5

2/5

Age
(40-49)

4/5

2/5

Age
(50+)

4/5

Age ≥ 40

Age < 40
Age
(20-29)

1/5 0/5

4/5 2/5

Age
(40-49)

Age
(30-39)

2/5 2/5

4/5 4/5

Age
(50+)

Diabetic

Diabetic NonDiabetic

5 Errors

NonDiabetic

6 Errors

(b) Classification tree (11 Errors)
Objective: Minimize Prediction Error

19/40

4/5

(a) Dataset

NonDiabetic

Diabetic

1/5 2/5 4/5 4/5
Age
(20-29)

Age
Age
(30-39) (40-49)

Age
(50+)

0/5 2/5 2/5 4/5
Age
(20-29)

Age
Age
(30-39) (40-49)

Predictive Model 1:
Linear Regression

Predictive Model 2:
Linear Regression

5 Errors

5 Errors

Age
(50+)

(c) ToPs (10 Errors)
Fig. 1. Toy example. (a) Dataset, (b) Classification tree, (c) ToPs

successively split the feature space. However, while tree-based
approaches create successive splits of the feature space in order
to maximize homogeneity of each split with respect to labels,
ToPs creates successive splits of the feature space in order
to maximize predictive accuracy of each split with respect to
a constructed predictive model. To this end, ToPs creates a
tree of subsets of the feature space and associates a predictive
model to each such subset – i.e., to each node of the tree. To
decide whether to split a given node, ToPs uses a feature to
create a tentative split, then chooses a learner and a training
set to create a predictive model for each set in the split, and
searches for the feature, the learner and the training set that
maximizes the predictive accuracy (minimizes the prediction
error). ToPs continues this process recursively until no further
improvement is possible.
A simple toy example, illustrated in Fig. 1, may help to
illustrate how ToPs works and why it improves on other treebased methods. We consider a classification problem: making
binary predictions of hypertension in a patient population. We
assume two features: Diabetic or Non-diabetic and Age Range
20-29, 30-39, 40-49, 50+, so that there are 8 categories of
patients. We assume the data is as shown in Fig. 1 (a): there
are 5 patients in each category; 1 patient who is Diabetic
and in the Age Range 20-29 has hypertension, etc. We first
consider a simple classification tree. Such a tree first selects
a single feature and threshold to split the population into two

2

groups so as to maximize the purity of labels. In this case
the best split uses Age Range as the splitting feature and
partitions patients into those in the Age Ranges 20-29 or 3039 and those in the Age Ranges 40-49 or 50+. No further
splitting improves the purity of labels so we are left with
the tree shown in Fig. 1 (b). The resulting predictive model
predicts that those in the Age Ranges 20-29 or 30-39 will
not have hypertension and those in the Age Ranges 40-49 or
50+ will have hypertension; this model makes 11 prediction
errors. We now consider an instantiation of ToPs which uses
as base learner a linear regression (to produce a probability
of hypertension) followed by thresholding at 0.5. (Recall that
we are treating this as a classification problem.) The best split
for this instantiation of ToPs uses Diabetic/Non-diabetic as the
splitting feature (leading to the split shown in Fig. 1 (c)) but
creates different predictive models in the two halves of the
split: in the Non-diabetic half of the split, the model predicts
that patients in the Age Ranges 20-29, 30-39 and 40-49 will
not have hypertension and that patients in the Age Range 50+
will have hypertension; in the Diabetic half of the split the
model predicts that patients in the Age Ranges 20-29 and
30-39 will not have hypertension and that patients in the Age
Ranges 40-49 and 50+ will have hypertension. (After this split,
no further splits using this single base learner improve the
prediction accuracy.) This model makes only 10 errors (less
than the number of errors made by the classification tree). Note
that the tree produced by ToPs is completely different from the
classification tree, that the predictive models and predictions
produced by ToPs are different from those produced by the
classification tree, and that the predictions produced by ToPs
within a single terminal node are not uniform. In this case,
ToPs performs better than the classification tree because it
"understands" that the effect of age on the risk of hypertension
is different for patients who are Diabetic and for patients who
are Non-diabetic.
Although this toy example may seem artificial, it exemplifies
what happens when we apply ToPs to a real dataset. For
example, one of our experiments is survival prediction of
patients who are wait-listed for a heart transplant. (For more
discussion, see Section V and VI.) In that setting features X are
patient characteristics and labels Y are survival times. The data
set D consists of records of actual patients; a single data point
(xt , y t ) records that a patient with features xt survived for time
y t . The construction of our algorithm demonstrates that the
best predictor of survival for males is different from the best
predictor of survival for females. As a result, predictions of
survival for a male and a female with otherwise similar features
may be quite different - because the features that influence
survival have different importance and interact differently for
males and females. Using a gender-specific predictor leads to
significant improvement in prediction accuracy.
In what follows, Section II highlights the differences between
our method and related machine learning methods. Section
III provides a full description of our method. Section IV
derives loss bounds. Section V compares the performance
of our method with that of many other methods on a variety
of datasets, demonstrating that our method provides substantial
and statistically significant improvement. Section VI details

Single predictor
(a) ToPs

Single prediction
(b) Regression trees

Fig. 2. The main differences between ToPs and regression trees. (a) ToPs, (b)
regression trees

the operation of our algorithm for one of the datasets to
further illustrate how why our method works. Section VII
concludes. Proofs are in the Appendix (at the end of the
manuscript); parameters of the experiments and additional
figures and discussion can be found in the Supplementary
Materials.
II. M ETHODOLOGICAL C OMPARISONS
ToPs is most naturally compared with four previous bodies
of work: model trees, other tree-based methods, ensemble
methods, and non-parametric regression. Table I summarizes the
comparisons with existing methods. The optimization equations
of existing works are also compared in the Appendix Table V.
A. Model trees
There are similarities between ToPs and model trees but
also very substantial differences. The initial papers on model
trees [11], [12] construct a tree using a splitting criterion that
depends on labels but not on predictions, then prunes the tree,
using linear regression at a node to replace subtrees from that
node. [13] constructs the tree in the same way but allows for
more general learners when replacing subtrees from a node.
[14], [15] split the tree by jointly optimizing a linear predictive
model and the splits that minimize the loss or maximize the
statistical differences between two splits.
ToPs operates differently from all of these: it constructs the
tree using a splitting criterion that depends both on labels and
on predictions of its base learners, it does not prune its tree
nor does it replace any subtree with a predictive model.
In ToPs, the potential split of a node is evaluated by training
each base learner on the current node and on all parent nodes
(not just the current node, as in [14], [15]) and choosing the
split and the predictor that yield the best overall performance.
(Keep in mind that ToPs is a general framework that allows for
an arbitrary set of base learners.) This approach is important for
several reasons: (1) It avoids the problem of small training sets
and reduces overfitting. (2) It allows splits even when only one

3

TABLE I
C OMPARISON WITH EXISTING METHODS
Methods

Sub-categories

Ensemble
Methods

Bagging,
Boosting,
Stacking

Tree-based
Methods

Nonparametric
Regression

Model trees

Decision Tree,
Regression
tree

Gaussian
Process,
Kernel
Regression

[12], [13], [14],
[15], [16]

Approach of existing methods

Approach of ToPs

Construct multiple predictive models (with single
learning algorithm) using randomly selected training
sets.

Construct multiple predictive models using multiple
learning algorithms and optimal training sets.

Only the predictive models are optimized to minimize
the loss.

Training sets and the assigned predictive model for
each training set are jointly optimized to minimize the
loss

Grow a tree by choosing the split that minimizes the
impurities of labels in each node.

Grow a tree by choosing the split that minimizes the
prediction error of the best predictive models.

Within a single terminal node all the predictions are
uniform (identical) .

Within a single terminal node, the final predictive model
is uniform but the predictions can be different.

Construct a non-parametric predictive model with predetermined kernels using the entire training set.

Construct non-parametric predictive models by jointly
optimizing the training sets and the best predictive
models.

Similarities between data points are fixed functions of
the features.

Similarities between data points are determined by the
prediction errors.

Construct the tree by jointly optimizing a (single)
learning algorithm and the splits

Construct the tree by jointly optimizing multiple
learning algorithms and the splits

Only convex loss functions are allowed.

Arbitrary loss functions such as AUC are allowed.

The final prediction for a new instance depends only on
the terminal node to which the feature of the instance
belongs.

The final prediction is a weighted average of the
predictions along all the nodes to which the feature of
the instance belong (the path to the terminal node).

side of the split yields an improved performance. (3) It allows multiple partitions and aggregate the predictions arising from
for choosing the base learner among multiple learners that best each partition. Our method also follows a recursive procedure,
capture the importance of features and the interactions among growing a tree by using features to create tentative splits, but
features. ToPs constructs the final prediction as a weighted we then use features and labels and predictors to choose the
average of predictions along the path (with weights determined optimal split and associated predictors. Eventually, we produce
by linear regression). Weighted averaging is important because a (locally) optimal tree of predictors. The final prediction for a
it smooths the prediction, from the least biased model to given new instance is computed by aggregating the predictions
the most biased model. Determining the weights by linear along a path in this tree of predictors. A crucial difference
regression is important because it is an optimizing procedure, between other tree-based methods and ToPs is the treatment of
and so the weights depend on the data and on the accuracy instances that give rise to the same paths: in other tree-based
of the predictors constructed. ([15] also smooths by weighted methods, such instances will be assigned the same prediction;
averaging but chooses the weights according to the number of in ToPs, such instances will be assigned the same predictor but
samples and number of features. This makes sense only with may be assigned very different predictions. Other tree-based
a single base learner and hence a single model complexity. models have the property that within a single terminal node
With multiple models of different model complexities, it is all the predictions are uniform; ToPs has the property that
impossible to find the appropriate aggregation weights using within a single terminal node the predictor is uniform but the
only the number of features and number of samples). Finally, predictions can be different. See again the illustrative example
the construction of ToPs allows for arbitrary loss functions, above and Fig. 2. (ToPs also has something - but less - in
including loss functions such as AUC that are not sample common with hierarchical logistic regression and hierarchical
means. This is important because loss functions such as AUC trees; in view of space constraints we defer the discussion to
are especially appropriate for certain applications; e.g. survival the Supplementary Materials.)
in the heart transplant dataset.
C. Ensemble methods
B. Other tree-based methods
Bagging [17], boosting [9], [18], [19], [20], stacking [10],
Decisions trees, regression trees [16], tree bagging, and
random forest [5] follow a recursive procedure, growing a tree
by using features to create tentative splits and labels to choose
among the tentative splits. Eventually, these methods create
a final partition (the terminal nodes of the tree) and make
a single uniform prediction within each set of this partition.
Some of these methods construct multiple trees and hence

[21] construct multiple predictive models using different
training sets and then aggregate the predictions of these models according to endogenously determined weights. Bagging
methods use a single base learner and choose random training
sets (ignoring both features and labels). Boosting methods use
a single base learner and choose a sequence of training sets to
create a sequence of predictive models; the sequence of training

4

sets is created recursively according to random draws from the
entire training set but weighted by the errors of the previous
predictive model. Stacking uses multiple base learners with
a single training set to construct multiple predictive models
and then aggregates the predictions of these multiple predictive
models. Our method uses a recursive construction to construct
a locally optimal tree of predictors, using both multiple base
learners and multiple training sets and constructs optimal
weights to aggregate the predictions of these predictors.
D. Non-parametric regressions

TABLE II
N OMENCLATURE TABLE
Symbol

Explanation

A
A
C
C↑
C̄(x)
C+, C−
D
D
hC
H(x)
L(h, Z)
M
N
Π(x)
S
τ
T
T̄
V 1, V 2
w∗ (C, Π)
X
(xt , y t )
xi
Y
Z

A set of algorithms
An algorithm (∈ A)
A node
Set consisting of node C and all its predecessors
The unique terminal node that contains x
Divided subsets (Similarly for h, A, S and V )
Dataset = {(xt , y t )}
True distribution
Predictive model assigned to C
Overall prediction assigned to x by the overall predictor H
The loss with a predictor h and the set Z
Number of algorithms
Number of samples
Path from the initial node to the terminal node with x
Training set
Threshold to divide nodes
A tree
Set of terminal nodes
Two validation sets
Weights of C on the path Π
Feature space
Instance. xt : feature, y t : label
i-th feature
Label set
Subspace of the feature space

Kernel regression [22], [23] and Gaussian process regression
[24] have in common that given a feature x, they choose a
training set and use that set to determine the coefficients of a
linear learner/model to predict the label y. Kernel regression
begins with a parametric family of kernels {Kθ }. For a specific
vector θ of parameters and a specific bandwidth b, the regression
considers the set B of data points (xt , y t ) whose feature xt are
within the specified bandwidth b of x; the predicted
P value of the
corresponding label y is the weighted sum B Kθ (x, xt ) y t .
The optimal parameter θ∗ and bandwidth b∗ can be set by
training, typically using least squared error as the optimization
criterion. Gaussian process regression begins by assuming a
Gaussian form for the kernel but with unknown mean and
variance. It first uses a maximum likelihood estimator based as including the parameters of that algorithm (if any); thus
on the entire data set to determine the mean and variance (and Random Forest with 100 trees is a different algorithm than
perhaps a bandwidth), and then uses that the Gaussian kernel Random Forest with 200 trees. Given an algorithm A ∈ A
to carry out a kernel regression. In both kernel regression and and a set E ⊂ D to be used to train A, we write A(E) for
Gaussian process regression, the prediction for a new instance is the resulting predictor. If E is a family of subsets of D then
formed by aggregating the labels associated to nearby features. we write A(E) = {A(E) : A ∈ A, E ∈ E} for the set of
In our method, the prediction for a new instance is formed by predictors that can arise from training some algorithm in A
carefully aggregating the predictions of a carefully constructed on some set in E.
family of predictors.
A tree of predictors is a pair (T , {hC }) consisting of a
(finite) family T of non-empty subsets of X together with an
III. T O P S
assignment C 7→ hC of a predictor hC on C to each element
We work in a supervised setting so data is presented as a pair C ∈ T such that:
(i) X ∈ T .
(x, y) consisting of a feature and a label. We are presented with
(ii) With respect to the ordering induced by set inclusion,
a (finite) dataset D = {(xt , y t )}, assumed to be drawn iid from
T forms a tree; i.e., T is partially ordered in such a
the true distribution D, and seek to learn a model that predicts,
way that each C ∈ T , C 6= X has a unique immediate
for a new instance drawn from D and for which we observe
predecessor. As usual, we refer to the elements of T as
the feature vector x, the true label y. We assume the space
nodes. Note that X is the initial node.
of features is X = X1 × · · · Xd ; if x ∈ X then xi is the i-th
feature. Some features are categorical, others are continuous. (iii) If C ∈ T is not a terminal node then the set C succ of
immediate successors of C is a partition of C.
For convenience (and without much loss of generality) we
assume categorical features are binary and represented as 0, 1 (iv) For each node C ∈ T there is an algorithm AC ∈ A
and a node C ∗ ∈ T such that C ⊂ C ∗ (so that either
and that continuous features are normalized between 0, 1; hence
d
C = C ∗ or C ∗ precedes C in T ) and hC = AC (C ∗ ) is
Xi ⊂ [0, 1] for every i and X ⊂ [0, 1] . We also take as given
the predictor formed by training the algorithm AC on the
a set Y ⊂ R of labels. For Z ⊂ X, a predictor (predictive
training set C ∗ . 1
model) on Z is a map h : Z → Y or h : Z → R; we interpret
h(z) as the predicted label or the expectation of the predicted It follows from these requirements that for any two nodes
label, given the feature z. (We often suppress Z when Z = X C1 , C2 ∈ T exactly one of the following must hold: C1 ⊂ C2
or when Z is understood.) If h1 : Z1 → Y, h2 : Z2 → Y are or C2 ⊂ C1 or C1 ∩ C2 = ∅. It also follows that the set of
predictors and Z1 ∩Z2 = ∅ we define h1 ∨h2 : Z1 ∪Z2 → Y by terminal nodes forms a partition of X. For any node C we
h1 ∨h2 (z) = hi (z) if z ∈ Zi . All the notations are summarized
1 In principle, the predictive model h
C and/or the algorithm AC and the
in the nomenclature table (Table II).
node C ∗ might not be unique. In that case, we can choose randomly among
We take as given a finite family A = {A1 , . . . , AM } the possibilities. Because this seems an unusual situation, we shall ignore it
of algorithms or base learners. We interpret an algorithm and similar indeterminacies that may occur at other points of the construction.

5

Algorithm 1 Growing the Optimal Tree of Predictors
Input: Feature space X, a set of algorithms A, training set
S, the first validation set V 1
First step:
Initial tree of predictors = (X, hX ),
𝒘(𝑪𝟏 , 𝜫)
𝐶
where hX = arg minA∈A L(A(S), V 1 )
𝑪
Recursive step:
𝒘(𝑪𝟐 , 𝜫)
Input: Current tree of predictors ((T , {hC })
𝑥 >𝜏
𝑥 ≤𝜏
𝐶
For each terminal node C ∈ T
Maximize
For a feature i and a threshold τi ∈ [0, 1].
𝑪
𝒘(𝑪𝟑 , 𝜫)
accuracy 𝑪
Set C − (τi ) = {x ∈ C : xi < τi }
C + (τi ) = {x ∈ C : xi ≥ τi }
𝐶
Predictive
𝒉
𝒉
Then,
models
{i∗ , τi∗ , hC− (τi∗ ) , hC + (τi∗ ) } =
𝑯𝒘 =
𝒘 𝑪, 𝜫 × 𝒉𝑪


−
+
1
−
1
+
{𝒊, 𝝉𝒊 , 𝒉 , 𝒉 }
𝑪∈𝚷
arg
min
L
h
∨
h
,
V
C
(τ
)
∪
V
C
(τ
)
i
i
𝑾∗ = argmax 𝑨𝑼𝑪(𝑯𝒘 , 𝑽𝟐 (𝚾))
= 𝐚𝐫𝐠𝐦𝐚𝐱{𝑨𝑼𝑪(𝒉 ⋁𝒉 , 𝑽𝟏 (𝑿))}
where h− ∈ A(C − (τi )↑ ), h+ ∈ A(C − (τi )↑ )
End For
(a) Growing the tree
(b) Weight optimization
End For
Stopping criterion:
L(hC ,V 1 (C)) ≤
Fig. 3. Illustrations of ToPs (a) growing the tree, (b) weight optimization


min L h− ∨ h+ , V 1 C − (τi ) ∪ V 1 C + (τi )
Output: Locally optimal tree of predictors (T , {hC })
write C ↑ for the set consisting of C and all its predecessors.
For ∈ X we write C(x) for the unique terminal node that
contains x and Π(x) = Π(C(x)) for the unique path in T
from the initial node X to the terminal node C(x). We write For continuous variables, the thresholds are set to delineate
percentile boundaries at 10% and 90%, with increments of
T for the set of all terminal nodes.
10%.)
Write
1
2
We fix a partition of the given dataset D = S ∪ V ∪ V ;
1
2
we view S as the (global) training set and V , V as (global)
C − (τi ) = {x ∈ C : xi < τi }
validation sets. In practice, the partition of D into training and
C + (τi ) = {x ∈ C : xi ≥ τi }
validation sets will be chosen randomly. Given a set C ⊂ X of
feature vectors and a subset Z ⊂ D, write Z(C) = {(xt , y t ) ∈
Evidently C − (τi ), C + (τi ) are disjoint and C = C − (τi ) ∪
Z : xt ∈ C}.
C + (τi ), so we are splitting C according to the feature i and
We express performance in terms of loss. For many problems,
the threshold τi . Note that C − (τi ) = ∅ if τi = 0; in this case
an appropriate measure of performance is the Area Under
we are not properly splitting C. For each of C − (τi ), C + (τi )
the (receiver operating characteristic) Curve (AUC); for a
we choose predictors h− ∈ A(C − (τi )↑ ), h+ ∈ A(C + (τi )↑ ).
given set of data Z ⊂ D and predictor h : Z(X) → Y
(That is, we choose predictors that arise from one of the learners
the loss is L(h, Z) = 1 − AU C. For other problems,
A ∈ A, trained on some node that (weakly) precedes the given
an appropriate P
measure of loss is the sample mean error
node.) We then choose the feature i∗ , the threshold τi∗ , and
1
L(h, Z) = |Z| (x,y)∈Z |h(x) − y|. For our general model,
the predictors hC − (τi∗ ) , hC + (τi∗ ) to minimize the total loss on
we allow for an arbitrary loss function. Given disjoint sets
V 1 ; i.e. we choose them to solve the minimization problem
Z1 , . . . , ZN and Wpredictors
h
on
Z
,
we
measure
the
total
n
n
S



(joint) loss as L( hn , Zn ). Note
need
−
+
1
−
1
+
W thatSthe loss function
P
arg min
L
h
∨
h
,
V
C
(τ
C
(τ
i) ∪ V
i)
not be additive, so in general L( hn , Zn ) 6=
L(hn , Zn )
i,τi ,h− ,h+
𝐶

𝒘(𝑪𝟎 , 𝜫)

subject to the requirement that this total loss should be
strictly less than L(hC , V 1 (C)). Note that because choosing
We begin with the (trivial) tree of predictors ({X}, {hX }) the threshold τi = 0 does not properly split C, the loss
where hX is the predictor h ∈ A({S}) that minimizes the loss L(hC , V 1 (C)) can always be achieved by setting τi = 0 and
L(h, V 1 (X)). Note that we train h globally – on the entire h+ = hC . If there is no proper splitting that yields a total loss
training set - and evaluate/validate it globally - on the entire smaller than L(hC , V 1 (C)) we do not split this node. This
(first) validation set - because the initial node consists of the yields a new tree of predictors. We stop the entire process
entire feature space. We now grow the tree of predictors by when no terminal node is further split; we refer to the final
a recursive splitting process, which is illustrated in Fig. 3 object as the locally optimal tree of predictors. (We use the
(a). Fix the tree of predictors (T , {hC }) constructed to this adjective "locally" because we have restricted the splitting to
point. For each terminal node C ∈ T with its associated be by a single feature and a single threshold and because the
predictor hC , choose a feature i and a threshold τi ∈ [0, 1]. optimization process employs a greedy algorithm – it does not
(In practice, for binary variables, the threshold is set at 0.5. look ahead.)
A. Growing the (Locally) Optimal Tree of Predictors

6

Algorithm 2 Weights on the Path
Input: Locally optimal tree of predictors (T , {hC }), second
validation set V 2
For each terminal node C and the corresponding path Π
from X to C
For each weight
Pvector w = (wC ),
Define Hw = C∈ΠwC hC . Then,

w∗ (Π) = w∗ (Π, C) = arg min L Hw , V 2 (C)
End For
Output: Optimized weights w∗ (Π) for each terminal node
C and corresponding path Π

Algorithm 3 Overall Predictor
Input: Locally optimal tree of predictions (T , {hC }), optimized weights {w∗ (Π)}, and testing set T
Given a feature vector x,
Find unique path Π(x) from X to terminal node containing
x;
Then P
H(x) = C∈Π(x) w∗ (Π, C) hC (x)
Output: The final prediction H(x)

the instantiation build on Linear Regression as the sole base
learner. In our experiments, we compare the performance of
two different instantiations of ToPs.

B. Weights on the Path
Fix the locally optimal tree of predictors(T , {hC }) and
a terminal node C; let Π be the path from X to C. We
consider vectors w = w(Π, C) C∈Π of non-negative weights
summing to one;P
for each such weight vector we form the
predictor Hw = C∈Π w(C, Π) hC . We choose the weight
vector w∗ (Π) that minimizes the empirical loss of Hw on the
second validation set V 2 (C); i.e.

w∗ (Π) = arg min L Hw , V 2 (C)
w

By definition, the weights depend on the path and not just on
the node; the weights assigned to a node C along different
paths may be different. This procedure is illustrated in Fig. 3
(b).
C. Overall Predictor
Given the locally optimal tree of predictors (T , {hC }) and
the optimal weights {w∗ (Π)} for each path, we define the
overall predictor H : X → R as follows: Given a feature x,
we define
X
H(x) =
w∗ (Π(x), C) hC (x)
C∈Π(x)

That is, we compute the weighted sum of all predictions along
the path Π(x) from the initial node to the terminal node that
contains x.
Note that we construct predictors by training algorithms on
(subsets of) S but we construct the locally optimal tree by
minimizing losses with respect to (subsets of) the validation
set V 1 ; this avoids overfitting to the training set S. We
then construct the weights, hence the overall predictor, by
minimizing losses with respect to (subsets of) the validation
set V 2 ; this avoids overfitting to the validation set V 1 . Fig. 3
(b) illustrates the procedures. The pseudo-codes of the entire
ToPs algorithms are in Algorithm 1, 2 and 3.
D. Instantiations
It is important to keep in mind that we take as given a family
A of base learners (algorithms). Our method is independent
of the particular family we use, but of course, the final overall
predictor is not. We use ToPs to refer to our general method and
to ToPs/A to refer to a particular instantiation of the method,
built on top of the family A of base learners; e.g., ToPs/LR is

E. Computational Complexity
The computational
of constructing the tree of
PM complexity
2
O(N
D
×
T
(N, D)) where N is the
predictors is
i
i=1
number of instances, D is the number of features, M is
the number of algorithms and Ti (N, D) is the computational
complexity of the i-th algorithm. (The proof is in the Appendix.)
For instance, the computational complexity of ToPs/LR is
O(N 3 D3 ). The computational complexity of finding the
weights is low in comparison with constructing the tree of
predictors because it is just a linear regression. In all our
simulations, the entire training time was less than 13 hours
using an Intel 3.2GHz i7 CPU with 32GB RAM. (Details are in
the Supplementary Materials.) Testing can be done in real-time
without any delay.
IV. L OSS B OUNDS
In this Section, we show how the Rademacher complexity
of the base learners can be used to provide loss bounds for our
overall predictor. The loss bound we establish is an application
to our framework of the Rademacher Complexity Theorem. The
importance of the loss bound we establish is that, even though
we use multiple learning algorithms with multiple clusters
(produced by divisions/splits), the loss can be bounded by the
loss of the most complicated single learner. Hence, the sample
complexity of ToPs is at most the sample complexity of the
most complex single learner.
Throughout this section we assume the loss function
is the
P sample mean of individual losses: L(h, Z) =
1
z∈Z `(h, z)), and that the individual loss is a convex
|Z|
ˆ
function of the difference `(h, z) = `(h(x)
− z) where `ˆ is
convex. Note that mean error and mean squared error satisfy
these assumptions but that other loss functions such as 1−AU C
(which is the natural loss function in the setting of our heart
transplant experiment described in Section IV-D) does not.
Recall that for each node C, AC is the base learner used to
construct the predictor hC associated to the node C and that
for a terminal node C we write Π(C) for the path from X to
C. We first present an error bound for each individual terminal
node and then derive an overall error bound. (Proofs are in
the Appendix.) We write R(AC , S(C̄)) for the Rademacher
complexity of AC with respect to the portion of the training
set S(C) and EDC [L(H)] for the expected loss of the overall

7

predictor H with respect to the true distribution when features
are restricted to lie in C and ED [L(H)] for the expected loss
of the overall predictor H with respect to the true distribution.

samples which represent 4 and 9; we treat 4 as label 0 (42.4%)
and 9 as label 1 (57.6%). Each sample records all 400 features
of a hand-written number image and the label of the image.
There is no missing information. The objective is to classify,
Theorem 1. Let H be the overall predictor and let C be a
from the hand-written image features, whether the image
terminal node of the locally optimal tree. For each δ > 0, with
represents 4 or 9. For ToPs we further divided the training
probability at least 1 − δ we have
samples into a training set S and validation sets V 1 , V 2 in
the proportions 75%-15%-10% (Same with all datasets). For
EDC [L(H)] ≤L(H, S(C)) + 2 max R(AC , S(C))
C∈Π(C)
comparisons, we use the results given in [18] for various
s
instantiations of DeepBoost, AdaBoost and LogitBoost and
2 log(4/δ)
+4
two model trees [14], [15] as benchmarks. To be consistent
|S(C)|
with [18], we use the error rate as the loss function. Table III
Note that the Rademacher complexity term is at most the presents the performance comparisons: the column Gain shows
maximum of the Rademacher complexities of the learners used the performance gain of ToPs/B over all the other algorithms;
along the path from X to C.
the column p-value shows the p-value of the statistical test
(two
sample student t-test) of the gain (improvement) of ToPs/B
Corollary 1.1. Let H be the overall predictor. For each δ > 0,
over
the other algorithms (The table is exactly as in [18] with
with probability at least 1 − δ,
ToPs/B
and ToPs/LR added). ToPs/B and ToPs/LR have 14.1%
1 X
and
5.6%
gains from the best benchmark (DeepBoost with
|S(C̄)|×
ED [L(H)] ≤
n
Stump).
These
improvements are not statistically significant (pC̄∈T
"
value ∼ 0.1) but the improvements over other machine learning
methods are all statistically significant (p-values < 0.05), and
L(H, S(C)) + 2 max R(AC , S(C))
C∈Π(C)
most are highly statistically significant (p-values < 0.001).2
s
#
2 log(4|T̄ |/δ)
+4
B. Bank Marketing
|S(C)|
For this comparison, we use the UCI Bank Marketing dataset
P
[26]. This dataset consists of 41,188 samples with 62 features;
where n = C̄∈T |S(C̄)|.
10 of these features are continuous, and 52 are binary. Each
sample records all 62 features of a particular client and whether
V. E XPERIMENTS
In this Section, we compare the performance of two the client accepted a bank marketing offer (a particular term
instantiations of ToPs – ToPs/LR (built on Linear Regression deposit account). There is no missing information. In this case,
as the single base learner) and ToPs/B (built on the set B = the objective is to predict, from the client features, whether
{AdaBoost, Linear Regression, Logistic Regression, LogitBoost, or not the client would accept the offer. (In the dataset 11.3%
Random Forest} of base learners) – against the performance of of the clients accepted and the remaining 88.7% declined.)
state-of-the-art algorithms on four publicly available datasets; To evaluate performance, we conduct 10 iterations of 5-fold
MNIST, Bank Marketing and Popularity of Online News cross-validation. Because the dataset is unbalanced, we use
datasets from UCI, and a publicly available medical dataset 1 − AUC as the loss function.
Table III shows the overall performance of the our two
(survival while wait listed for a transplant). Considering two
instantiations
of ToPs and 13 comparison machine-learning
instantiations of ToPs allows us to explore the source of the
algorithms:
Model
trees [14], [15], AdaBoost [9], Decision
improvement yielded by our method over other algorithms. In
Trees
(DT),
Deep
Boost
[18], LASSO, Linear Regression (LR),
the following subsections, we describe the datasets and the
Logistic
Regression
(Logit),
LogitBoost [19], Neural Networks
performance comparisons; the exploration of the source of
[27],
Random
Forest
(RF)
[5], Support Vector Machines
improvement is illustrated in Section VI.
(SVM)
and
XGBoost
[20].
Tops/LR
outperforms all of the
We conducted 10 independent experiments with different
benchmarks
by
more
than
10%
and
ToPs/B
outperforms all of
combinations of training and testing sets; we report the mean
the
benchmarks
by
more
than
20%.
(The
improvement
over
and the standard deviations of the performances in these 10
Random
Forest
is
statistically
significant
(p-value
=
0.015);
independent experiments. To evaluate statistical significance
(p-values), we assume that the prediction performances of these the improvements over other methods are highly significant
10 experiments are sampled from Gaussian distributions and (p-values < 0.005). In Section VI we show the locally optimal
we use two sample student t-tests to compute the p-value for trees of predictors for this setting (Fig. 4 and 5) and discuss
the source of performance gain of ToPs.
the improvement of ToPs/B over each benchmark.
A. MNIST
Here we use the MNIST OCR-49 dataset [25]. The entire
MNIST dataset consists of 70,000 samples with 400 continuous
features which represent the image of a hand-written number
from 0 to 9. Among 70,000 samples, we only use the 13,782

2 In a separate experiment, we also compared the performance of ToPs/B
on the entire MNIST dataset with that of a depth 6 CNN (AlexNet with 3
convolution nets and 3 max pooling nets). The loss of ToPs is 0.0081; this
is slightly worse than CNN (0.0068) but much better than the best ensemble
learning benchmark, XgBoost (0.0103). Keep in mind that CNN’s are designed
for spatial tasks such as character recognition, while ToPs is a general-purpose
method; as we shall see in later subsections, ToPs outperforms neural networks
for other tasks.

8

TABLE III
P ERFORMANCE C OMPARISONS FOR THE MNIST OCR-49 DATASET, UCI BANK M ARKETING DATASET, AND UCI O NLINE N EWS P OPULARITY DATASET
Datasets

MNIST OCR-49

UCI Bank Marketing

UCI Online News Popularity

Algorithms
ToPs/B
ToPs/LR

Loss
0.0152
0.0167

Gain
9.0%

p-value
0.187

Algorithms
ToPs/B
ToPs/LR

Loss
0.0428
0.0488

Gain
12.3%

p-value
0.089

Loss
0.2689
0.2801

Gain
4.0%

p-value
0.015

Malerba (2004) [15]
Potts (2005) [14]

0.0212
0.0195

28.3%
22.1%

0.001
0.004

Malerba (2004) [15]
Potts (2005) [14]

0.0608
0.0581

29.5%
26.3%

< 0.001
0.003

0.2994
0.2897

10.2%
7.2%

< 0.001
0.001

0.3147
0.3240
0.2929
0.3209
0.3048
0.3082
0.3172
0.2899
0.3074
0.3081
0.3023

14.6%
17.0%
8.2%
16.2%
11.8%
12.8%
15.2%
7.2%
12.5%
12.7%
11.0%

< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001

AdaBoost
0.0660
35.2%
< 0.001
DTree
0.0785
45.5%
< 0.001
DeepBoost
0.0591
27.6%
0.002
LASSO
0.0671
36.2%
< 0.001
LR
0.0669
36.0%
< 0.001
Logit
0.0666
35.7%
< 0.001
LogitBoost
0.0673
36.4%
< 0.001
NeuralNets
0.0601
28.8%
0.002
Random Forest
0.0548
21.9%
0.015
rbf SVM
0.0671
36.2%
< 0.001
XGBoost
0.0575
25.6%
0.003
DB/TreesE : DeepBoost with trees and exponential loss, DB/TreesL : DeepBoost with trees and logistic loss.
AB-L1/Stump: AdaBoost with stump and L1 norm. We use the same benchmarks for two UCI datasets. Bold: The
DB/Stump
DB/TreesE
DB/TreesL
AB/Stump1
AB/Stump2
AB-L1/Stump
AB/Trees
AB-L1/Trees
LB/Trees
LB-L1/Trees

0.0177
0.0182
0.0201
0.0414
0.0209
0.0200
0.0198
0.0197
0.0211
0.0201

14.1%
16.5%
24.4%
63.3%
27.3%
24.0%
23.2%
22.8%
28.0%
24.4%

0.113
0.114
0.007
< 0.001
0.009
0.008
0.022
0.026
0.002
0.009

best performance.

TABLE IV
C OMPARISON WITH STATE - OF - THE - ART MACHINE LEARNING TECHNIQUES . (UNOS H EART T RANSPLANT DATASET TO PREDICT WAIT- LIST MORTALITY
FOR DIFFERENT TIME HORIZONS (3- MONTH , 1- YEAR , 3- YEAR , AND 10- YEAR ))
3-month mortality

1-year mortality

3-year mortality

10-year mortality

Algorithms

Loss

Gain

p-value

Loss

Gain

p-value

Loss

Gain

p-value

Loss

Gain

p-value

ToPs/B
ToPs/LR

0.207
0.231

10.4%

0.006

0.181
0.207

12.6%

0.014

0.177
0.201

11.9%

0.004

0.175
0.203

13.8%

0.002

< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
0.012
< 0.001
< 0.001

0.239
0.279
0.245
0.281
0.293
0.281
0.233
0.257
0.234
0.243
0.233

24.3%
35.1%
26.1%
35.6%
38.2%
35.6%
22.3%
29.6%
22.6%
25.5%
22.3%

0.002
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
0.002
< 0.001
< 0.001
< 0.001
< 0.001

0.229
0.287
0.219
0.248
0.264
0.249
0.221
0.225
0.217
0.218
0.223

22.7%
38.3%
19.2%
28.6%
33.0%
28.9%
19.9%
21.3%
18.4%
18.8%
20.6%

0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
0.006
< 0.001
0.002
0.001
< 0.001

0.237
0.249
0.213
0.228
0.285
0.236
0.229
0.221
0.225
0.284
0.226

26.2%
29.7%
17.8%
23.2%
38.6%
25.8%
23.6%
20.8%
22.2%
38.4%
22.6%

< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
< 0.001
0.001

AdaBoost
0.262
21.0%
DTree
0.326
36.5%
DeepBoost
0.259
20.1%
LASSO
0.310
33.2%
LR
0.320
35.3%
Logit
0.310
33.2%
LogitBoost
0.267
22.5%
NeuralNets
0.262
21.0%
Random Forest
0.252
17.9%
SVM
0.281
26.3%
XGBoost
0.257
19.5%
Bold: The best performance.

C. Popularity of Online News

D. Heart Transplants

The UNOS (United Network for Organ Transplantation)
dataset (available at https://www.unos.org/data/) provides inforHere we use the UCI Online News Popularity dataset [26]. mation about the entire cohort of 36,329 patients (in the U.S.)
This dataset consists of 39,397 samples with 57 features (43 who were on a waiting list to receive a heart transplant but did
continuous, 14 binary). Each sample records all 57 features of not receive one, during the period 1985-2015. Patients in the
a particular news item and the number of times the item was dataset are described by a total of 334 clinical features, but
shared. There is no missing information. The objective is to much of the feature information is missing, so we discarded
predict, from the news features, whether or not the item would 301 features for which more than 10% of the information
be popular – defined to be "shared more than 5,000 times." (In was missing, leaving us with 33 features – 14 continuous and
the dataset 12.8% of the items are popular; the remaining 87.2% 19 binary. To deal with the missing information, we used 10
are not popular.) To evaluate performance of all algorithms, multiple imputations using Multiple Imputation by Chained
we conduct 10 iterations of 5-fold cross-validation. As it can Equations (MICE) [28]. In this setting, the objective(s) are
be seen in Table III, ToPs/LR and Tops/B both outperform all to predict survival for time horizons of 3 months, 1 year, 3
the other machine learning algorithms: Tops/B achieves a loss years and 10 years. (In the dataset, 68.3% survived for 3
(measured as 1 − AU C) of 0.2689, which is 7.2% lower than months, 49.5% survived for 1 year, 28.3% survived for 3 years,
the loss achieved by the best competing benchmark. All the and 6.9% survived for 10 years.) To evaluate performance,
improvements are highly statistically significant (p-values ≤ we divided the patient data based on the admission year: we
0.001).
took patients admitted to a waiting list in 1985-1999 as the

9

LR
: 0.0626
: 0.0669
∆ = 0.0087
= 0.0513
LR
∆ = 0.0033
= 0.0871
LR
∆ = 0.0211

LR
∆ = 0.0113

LR
∆ = 0.0120

LR
∆ = 0.0010
LR
∆ = 0.0067
= 0.1213

LR
∆ = 0.0237

LR
∆ = 0.0025
= 0.2878

LR (↑)
∆ = 0.0139

LR
∆ = 0.0111
= 0.3312

LR (↑)
∆ = 0.0412
= 0.1213

LR (↑)
∆ = 0.0021

LR (↑↑)
∆ = 0.0142

LR
∆ = −0.0027

LR (↑↑)
∆ = 0.0215

LR
∆ = 0.0209

LR
∆ = 0.0005

LR
∆ = 0.0097

LR
∆ = 0.0077

LR (↑)
∆ = 0.0021

LR (↑)
∆ = 0.0101

LR
∆ = 0.0049

LR
∆ = 0.0412

LR
∆ = 0.0119

LR
∆ = 0.0191

LR (↑)
∆ = 0.0098

LR
∆ = 0.0211

LR
∆ = 0.0101

Fig. 4. The locally optimal tree of predictors for ToPs/LR applied to the Bank Marketing dataset

training sample and patients admitted in 2000-2015 as the
testing sample. We compared the performance of ToPs with
the same machine-learning algorithms as before; the results
are shown in Table IV. Once again, both ToPs/LR and ToPs/B
outperform all the other machine learning algorithms: ToPs/B
achieves losses (measured as 1 − AU C) between 0.175 and
0.207; these improve by 17.9% to 22.3% over the best machine
learning benchmarks. The improvement over Random Forest at
the 3-month horizon is statistically significant (p-value = 0.012);
all other improvements are highly significant (p-values ≤ 0.006).
The Supplementary Materials show the locally optimal trees
of predictors for this dataset.

by using the final predictor rather than the initial predictor.
Finally, for one particular path through the tree (indicated by
heavy blue arrows), we show the weights assigned to the nodes
along that path in computing the overall predictor. Note that
the deeper nodes do not necessarily get greater weight: using
the second validation set to optimize the weights compensates
for overfitting deeper in the tree.
The first key feature of our construction is that it identifies
a family of subsets of the feature space – the nodes of the
locally optimal tree – and optimally matches training sets to
the nodes. Moreover, as Fig. 4 and 5 make clear, the optimal
training set at the node C need not be the node C itself, but
might be one of its predecessor nodes. For ToPs/LR it is this
VI. D ISCUSSION
matching of training sets to nodes that gives our method its
As the experiments show, our method yields significant power: if we were to use the entire training set S at every node,
performance gains over a large variety of existing machine our final predictor would reduce to simple Linear Regression –
learning algorithms. These performance gains come from the but, as Table III shows, because we do match training sets to
concatenation of a number of different factors. To aid in the nodes, the performance of ToPs/LR is 27.1% better than that
discussion, we focus on the Bank Dataset and refer to Fig. 4 of Linear Regression.
The second key feature of our construction is that it also
and 5, which show the locally optimal trees of predictors grown
by ToPs/LR and ToPs/B, respectively. For ToPs/B, which uses optimally matches learners to the nodes. For ToPs/LR, there
multiple learners, we show, in each node, the learner assigned is only a single base learner, so the matching is trivial (LR
to that node; for both ToPs/LR and ToPs/B we indicate the is matched to every node) – but for ToPs/B there are five
training set assigned to that node: For instance, in Fig. 5, base learners and the matching is not trivial. Indeed, as can
Random Forest is the learner assigned to the initial node; be seen in Fig. 5, of the five available base learners, four are
the training set is necessarily the entire feature space X. In actually used in the locally optimal tree. This explains why
subsequent nodes, the training set is either the given node (if ToPs/B improves on ToPs/LR. Of course, the performance of
there is no marker) or the immediately preceding node (if the ToPs/B might be even further improved by enlarging the set of
node is marked with a single up arrow) or the node preceding base learners. (It seems clear that the performance of ToPs/A
that (if the node is marked with two up arrows), and so forth. depends to some extent on the set of base learners A.)
Note that different base learners and/or different training sets
Our recursive construction leads, in every stage, to a
are used in various nodes. In each non-terminal node we also (potential) increase in the complexity of the predictors that
show the loss improvement ∆v (computed with respect to V 1 ) can be used. For example, Linear Regression fits a linear
obtained by splitting this node into the two immediate successor function to the data; ToPs/LR fits a piecewise linear function
nodes. (By construction, we split exactly when improvement to the data. This additional complexity raises the problem of
is possible so ∆v is necessarily strictly positive at every non- overfitting. However, because we train on the training set S
terminal node while ∆v would be 0 at terminal nodes.) At the and evaluate on the first validation set V 1 , we avoid overfitting
terminal nodes (shaded), we show the loss improvement ∆t to the training set. As can be seen from Fig. 4 and 5 this
achieved on that node (that set of features) that is obtained avoidance of overfitting is reflected in the way it limits the

10

RF
: 0.0551
: 0.0548
∆ = 0.0041
= 0.1657
RF
∆ = 0.0052
= 0.2136
RF
∆ = 0.0045
= 0.2414

RF ( ↑ )
∆ = 0.0101

RF
∆ = 0.0072

RF (↑)
∆ = 0.0108
= 0.2414

Ada
∆ = 0.0088

Logit
∆ = 0.0092
= 0.1379

RF (↑)
∆ = 0.0143

Logit
∆ = 0.0110

RF (↑↑)
∆ = 0.0182

Logit
∆ = 0.0119

RF (↑↑)
∆ =0

LR
∆ = 0.0079

Logit
∆ = −0.0021

Logit (↑)
∆ = 0.0068

LR
∆ = 0.0310

LR (↑)
∆ = 0.0110

Logit
∆ = 0.0017

Logit (↑↑)
∆ = 0.0210

LR
∆ = 0.0341

Fig. 5. The locally optimal tree of predictors for ToPs/B applied to the Bank Marketing dataset

depth of the locally optimal tree: the growth of the tree stops
when splitting no longer yields improvement on the validation
set V 1 . Although training on S and evaluating on V 1 avoids
overfitting to S, it leaves open the possibility of overfitting to
V 1 ; we avoid this problem by using the second validation set
V 2 to construct optimal weights to aggregate predictions along
paths.
The contrast with model trees (see again the discussion in
Subsection II-A) is particular worth noting. Even ToPs/LR
performs significantly better than the best model trees because
we assign predictive models to every node, we construct these
models by training on either the current node or some parent
node, we allow for splitting when only one side of the split
improves performance, and we construct the final prediction
as the weighted average of predictions along the path. ToPs/B
performs even better than ToPs/LR because we also allow for
a richer family of base learners.
VII. C ONCLUSION
In this paper, we develop a new approach to ensemble
learning. We construct a locally optimal tree of predictors
that matches learners and training sets to particular subsets of
the feature space and aggregates these individual predictors
according to endogenously determined weights. Experiments on
a variety of datasets show that this approach yields statistically
significant improvements over state-of-the-art methods.

Then,
R(A, S) =

X
1
Eσ={±1}|S| [sup
σi × l(h, z)]
|S|
h∈A
z∈S

=

p
X
X
1
Eσ={±1}|S| [sup
σi × l(
wj hj , z)]
|S|
h∈A
j=1
z∈S

=

p
p
X
X
X
1
Eσ={±1}|S| [sup
σi × l(
wj hj ,
wj z)]
|S|
h∈A
j=1
j=1
z∈S

=

p
X
X
1
Eσ={±1}|S| [sup
σi × ˆl(
wj (hj − z))]
|S|
h∈A
j=1
z∈S

≤

p
X
X
1
Eσ={±1}|S| [sup
σi ×
wj ˆl(hj − z)]
|S|
h∈A
j=1
z∈S

p
X
X
1
Eσ={±1}|S| [sup
σi ×
wj l(hj , z)]
|S|
h∈A z∈S
j=1
X
1
Eσ={±1}|S| [sup
σi × max l(hj , z)]
≤
j
|S|
h∈A

=

z∈S

= max R(Aj , S)
j

Therefore, using the Rademacher Complexity Theorem,
s

A PPENDIX A
P ROOF OF THE THEOREM 1 (B OUNDS FOR THE PREDICTIVE
MODEL OF EACH TERMINAL NODE )
Proof. The definition of R(A, S) is
X
1
R(A, S) =
Eσ={±1}|S| [sup
σi × l(h, zi )]
|S|
h∈A

ED [L(h)] ≤ L(h, S) + 2 max R(Ai , S) + 4
i

2 log(4/δ)
|S|

For
node C̄, the hypothesis class is H =
P each terminal
∗
w
(Π(
C̄),
C) × hC . Therefore, the upper bound of
C∈Π(C̄)
the expected loss for each terminal node C̄ is

z∈S

where P (σi = 1) = P (σi = −1) = 0.5.
Let us define {A1 , ..., Ap } as the set of all hypothesis classes
that ToPs uses.
Then, let us define hypothesis class A as follow.
A = {h =

p
X
i=1

wi × hi |w ∈ simplex, hi ∈ Ai }

EDC̄ [L(H)] ≤L(H, S(C̄)) + 2 max R(AC , S(C̄))
C∈Π(C̄)
r
2 log(4/δ)
+4
m
where m = |S(C̄)|.

11

TABLE V
C OMPARISON OF OPTIMIZATION EQUATIONS WITH EXISTING ENSEMBLE METHODS
Methods

Optimization
k
X

N
h1 X
i
L(hi (xj ), yj )
h ∈H=∪Hl N
{X1 ,...,Xk }
n=1
i=1 i

min

ToPs

min

ToPs uses both multiple training sets ({X1 , X2 , ..., Xk }) and multiple hypothesis classes (H = ∪Hl ) to construct the predictive models
({h1 , h2 , ..., hk }). Both multiple training sets and corresponding predictive models are jointly optimized to minimize the loss function L.
xj is the j-th feature, yj is the j-th label, N is the total number of samples, and k is the number of leaves.
h 1
hi ∈H |S|

Bagging

i
L(hi (xj ), yj )

X

min

(xj ,yj )∈S

Here S is the family of multiple training sets, randomly drawn. Bagging uses multiple training sets (randomly drawn) and a single hypothesis
class to construct multiple predictive models. Only the predictive models are optimized to minimize the loss function (L).
min

hi ∈H

h 1
|S|

Boosting

i
φj L(hi (xj ), yj )

X
(xj ,yj )∈S

Here S is the family of multiple training sets, randomly drawn. Boosting uses multiple training sets (weighted by prediction error (φj ) of
the previous model) and a single hypothesis class to construct the predictive models. Only the predictive models are optimized to minimize
the loss function (L).
h 1
hi ∈H=∪Hl |S|
min

Stacking

i
L(hi (xj ), yj )

X
(xj ,yj )∈S

Stacking uses a single training set with multiple hypothesis classes to construct the predictive models. Only the predictive models are
optimized to minimize the loss function (L) .

A PPENDIX B
P ROOF OF THE COROLLARY 1.1 (B OUNDS FOR THE ENTIRE
PREDICTIVE MODEL )
Proof. Based on the assumption,
1 X
L(h, Z) =
l(h, z)
m
z∈Z

where m = |Z|. Then
ED (L(H)) =

condition is at least ((1 − δ)1/|T̄ | )|T̄ | = (1 − δ)
Therefore, with at least 1 − δ probability,
X |S(C̄)|
ED [L(H)] ≤
L(H, S(C̄))
n
C̄∈T̄

X |S(C̄)|
max R(AC , S(C̄))
n C∈Π(C̄)
C̄∈T̄
s
X |S(C̄)| 2 log[4/(1 − (1 − δ)1/|T̄ | )]
+4
n
|S(C̄)|
+2

C̄∈T̄

X

P (C̄) × EDC̄ [L(H)]

C̄∈T̄

Based on the Theorem 1, with probability at least (1 − δ)1/|T̄ | ,
each terminal node C̄ satisfied the following condition.
EDC̄ [L(H)] ≤L(H, S(C̄)) + 2 max R(AC , S(C̄))
C∈Π(C̄)
s
2 log(4/(1 − (1 − δ)1/|T̄ | ))
+4
m

Furthermore, 1 − (1 − δ)1/|T̄ | ≥
1/|T̄ |

Thus, we can switch

1 − (1 − δ)
to
in this inequality. (Using Binomial
Series Theorem, the inequality is easily proved.) Therefore,
with at least 1 − δ probability,
1 X
ED [L(H)] ≤
|S(C̄)|×
n
C̄∈T
"
L(H, S(C)) + 2 max R(AC , S(C))
C∈Π(C)

s
+4

where m = |S(C̄)|.
Because the definition of the L(h, Z) is the sample mean of
each loss l(h, z), the entire loss is the weighted average of
each terminal node. (weight is the number of samples S(|C̄|)
in each terminal node) .
Furthermore, if each terminal node satisfies the above condition
with probability at least (1 − δ)1/|T̄ | , it means that the
probability that all terminal nodes satisfies the following

δ
.
|T̄ |

δ
|T̄ |

2 log(4|T̄ |/δ)
|S(C)|

#

A PPENDIX C
P ROOF OF THE COMPUTATIONAL COMPLEXITY
A. Proof of computational complexity of one recursive step:
Statement: The computational complexity of one recursive step for constructing tree of predictors grows as

12

PM

i=1

O(N D × Ti (N, D)).

ACKNOWLEDGMENT

Proof. There are two procedures in one recursive steps of
constructing a tree of predictors. (1) Greedy search for the
division point, (2) Construct the predictive model for each
division.
First, the possible combinations of dividing the feature space
into two subspaces using one feature with the threshold are at
most N × D where N is the total number of samples, and D
is the number of dimensions. Because, in each subspace, there
should be at least one sample.
Second, for each division, we need to construct M predictive
models. The computational complexity to construct the M
number of predictive
models for each division is trivially
PM
computed as i=1 O(Ti (N, D)) where O(Ti (N, D)) is the
computational complexity of i-th learner to construct the
predictive model with N samples and D dimensional features.
Therefore, the computational complexity of one recursive
step with M learner can be written as follow.
ND ×

M
X
i=1

O(Ti (N, D)) =

M
X

O(N D × Ti (N, D))

i=1

Because, there are N D possibilities of division
PM and for each
division, the computational complexity is i=1 O(Ti (N, D)).

B. Proof of computational complexity of constructing the entire
tree of predictors
Statement: The computational complexity
PMof construct2
ing the entire tree of predictors is
i=1 O(N D ×
Ti (N, D))
Proof. By the previous statement, we know that the computational complexityP
of one recursive step of constructing the tree
M
of predictors is i=1 O(N D × Ti (N, D)). Therefore, now,
we need to figure out the maximum number of recursive steps
with N samples.
For each recursive step, the number of clusters is stepwise
increased. Furthermore, in each cluster, there should be at
least one sample. Therefore, we can easily figure out that the
maximum number of recursive steps are at most N . (Note that
the recursive steps are much less needed in practice because
ToPs does not divide all the samples into different clusters)
Therefore, the computational complexity of the entire
construction of tree of predictors is as follow.
N×

M
X
i=1

O(N D × Ti (N, D)) =

M
X

O(N 2 D × Ti (N, D))

i=1

For instance, if we only use the linear regression as
the learner of ToPs (ToPs/LR), the computational complexity of ToPs is O(N 3 D3 ). This is because, the computational complexity of linear regression is O(N D2 ). Therefore,
computational complexity of ToPs/LR is
PM the entire
2
O(N
DT
(n,
D)) = O(N 3 D3 )
i
i=1

This work was supported by the Office of Naval Research
(ONR) and the NSF (Grant number: ECCS1462245).
R EFERENCES
[1] D. J. Miller and L. Yan, “Critic-driven ensemble classification,” IEEE
Transactions on Signal Processing, vol. 47, no. 10, pp. 2833–2844, 1999.
[2] C. Tekin, J. Yoon, and M. van der Schaar, “Adaptive ensemble learning
with confidence bounds,” IEEE Transactions on Signal Processing,
vol. 65, no. 4, pp. 888–903, 2016.
[3] N. Asadi, A. Mirzaei, and E. Haghshenas, “Multiple observations hmm
learning by aggregating ensemble models,” IEEE Transactions on Signal
Processing, vol. 61, no. 22, pp. 5767–5776, 2013.
[4] L. Canzian, Y. Zhang, and M. van der Schaar, “Ensemble of distributed
learners for online classification of dynamic data streams,” IEEE
Transactions on Signal and Information Processing over Networks, vol. 1,
no. 3, pp. 180–194, 2015.
[5] L. Breiman, “Random forests,” Machine learning, vol. 45, no. 1, pp.
5–32, 2001.
[6] Y. Freund, Y. Mansour, and R. E. Schapire, “Generalization bounds for
averaged classifiers,” Annals of Statistics, pp. 1698–1722, 2004.
[7] D. J. MacKay, “Bayesian methods for adaptive models,” Ph.D. dissertation, California Institute of Technology, 1992.
[8] V. Y. Tan, S. Sanghavi, J. W. Fisher, and A. S. Willsky, “Learning graphical models for hypothesis testing and classification,” IEEE Transactions
on Signal Processing, vol. 58, no. 11, pp. 5481–5495, 2010.
[9] Y. Freund and R. E. Schapire, “A decision-theoretic generalization of
on-line learning and an application to boosting,” in European conference
on computational learning theory. Springer, 1995, pp. 23–37.
[10] P. Smyth and D. Wolpert, “Linearly combining density estimators via
stacking,” Machine Learning, vol. 36, no. 1-2, pp. 59–83, 1999.
[11] J. R. Quinlan et al., “Learning with continuous classes,” in 5th Australian
joint conference on artificial intelligence, vol. 92. Singapore, 1992, pp.
343–348.
[12] Y. Wang and I. H. Witten, “Induction of model trees for predicting
continuous classes,” 1996.
[13] L. Torgo, “Functional models for regression tree leaves,” in ICML, vol. 97.
Citeseer, 1997, pp. 385–393.
[14] D. Potts and C. Sammut, “Incremental learning of linear model trees,”
Machine Learning, vol. 61, no. 1-3, pp. 5–48, 2005.
[15] D. Malerba, F. Esposito, M. Ceci, and A. Appice, “Top-down induction
of model trees with regression and splitting nodes,” IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol. 26, no. 5, pp. 612–625,
2004.
[16] L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen, Classification
and regression trees. CRC press, 1984.
[17] L. Breiman, “Bagging predictors,” Machine learning, vol. 24, no. 2, pp.
123–140, 1996.
[18] C. Cortes, M. Mohri, and U. Syed, “Deep boosting,” in 31st International
Conference on Machine Learning, ICML 2014. International Machine
Learning Society (IMLS), 2014.
[19] J. Friedman, T. Hastie, R. Tibshirani et al., “Additive logistic regression:
a statistical view of boosting (with discussion and a rejoinder by the
authors),” The annals of statistics, vol. 28, no. 2, pp. 337–407, 2000.
[20] T. Chen and C. Guestrin, “Xgboost: A scalable tree boosting system,”
in Proceedings of the 22Nd ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining. ACM, 2016, pp. 785–794.
[21] P. Smyth and D. Wolpert, “Linearly combining density estimators via
stacking,” Machine Learning, vol. 36, no. 1-2, pp. 59–83, 1999.
[22] E. A. Nadaraya, “On estimating regression,” Theory of Probability & Its
Applications, vol. 9, no. 1, pp. 141–142, 1964.
[23] G. S. Watson, “Smooth regression analysis,” Sankhyā: The Indian Journal
of Statistics, Series A, pp. 359–372, 1964.
[24] C. K. Williams, “Prediction with gaussian processes: From linear
regression to linear prediction and beyond,” in Learning in graphical
models. Springer, 1998, pp. 599–621.
[25] Y. LeCun, “The mnist database,” 2016. [Online]. Available: http:
//yann.lecun.com/exdb/mnist/
[26] M. Lichman, “UCI machine learning repository,” 2013. [Online].
Available: http://archive.ics.uci.edu/ml
[27] S. Fritsch, F. Guenther, and M. F. Guenther, “Package ‘neuralnet’,” 2016.
[28] S. Buuren and K. Groothuis-Oudshoorn, “mice: Multivariate imputation
by chained equations in r,” Journal of statistical software, vol. 45, no. 3,
2011.

