#  On subbagging Boosted Probit Model Trees

Tian Qin
Department of Mathematics
Lehigh University
Bethlehem, PA 18015
<EMAIL_ADDRESS>
& Wei-Min Huang
Department of Mathematics
Lehigh University
Bethlehem, PA 18015
<EMAIL_ADDRESS>

###### Abstract

With the insight of variance-bias decomposition, we design a new hybrid
bagging-boosting algorithm named SBPMT for classification problems. For the
boosting part of SBPMT, we propose a new tree model called Probit Model Tree
(PMT) as base classifiers in AdaBoost procedure. For the bagging part, instead
of subsampling from the dataset at each step of boosting, we perform boosted
PMTs on each subagged dataset and combine them into a powerful "committee",
which can be viewed an incomplete U-statistic. Our theoretical analysis shows
that (1) SBPMT is consistent under certain assumptions, (2) Increase the
subagging times can reduce the generalization error of SBPMT to some extent
and (3) Large number of ProbitBoost iterations in PMT can benefit the
performance of SBPMT with fewer steps in the AdaBoost part. Those three
properties are verified by a famous simulation designed by Mease and Wyner
(2008). The last two points also provide a useful guidance in model tuning. A
comparison of performance with other state-of-the-art classification methods
illustrates that the proposed SBPMT algorithm has competitive prediction power
in general and performs significantly better in some cases.

_Keywords_ Subagging $\cdot$ ProbitBoost $\cdot$ Weak consistency $\cdot$
Incomplete U-statistic $\cdot$ Generalization error bound

##  1 Introduction

Bagging has been a critical ensemble learning model for data classification or
regression in past few decades. As an ensambling method, bootstrap bagging
(Breiman (2004)) ensembles the results of base tree learners so that the
variance of the model is decreased without increasing the bias. As a variant
of bagging, Random Forests (RFs) further utilize a random subset of features
at each possible split when constructing a single tree learner. Ho (1995)
analyzed how bagging and random subset of features can contribute to the
accuracy gain under different conditions by decorrelating bootstrapped trees.
Breiman (2004) suggested that bagging unstable (i.e high variance) classifiers
usually generates a better result.

Instead of creating a strong learner by combining weak learners fitted
simultaneously, we can actually merge weak classifiers into a strong
classifier by sequentially revising them and adding them up with optimal
weights, which gives rise to the idea of boosting. Freund and Schapire (1997)
developed AdaBoost.M1 algorithm which outputs a weighted sum of a sequence of
weak learners. The weights are tweaked in favor of those instances
misclassified by previous learners. Nowadays, we have many other popular
ensemble methods based on the idea of gradient boosting, which generalizes the
boosting in functional spaces. For example, Chen and Guestrin (2016) followed
the idea of gradient boosting and employed a different design of functional
optimization and weak classifier learning algorithm. As a result, they
proposed one of the most successful ensemble learning algorithms called
XGBoost.

Empirically, if we iterate the boosting for a large number of steps, the
training error of boosted classifier will be close to zero, which implies that
boosting can somehow reduce the bias of original model. On the other hand,
bagging can alleviate overfitting by averaging the outputs of base classifiers
to reduce the variance of ensemble model. Observing the variance-bias
decomposition in $L_{2}$ loss function, it’s natural to combine bagging and
boosting together to achieve smaller prediction error.

Breiman (2001) proposed a hybrid bagging-boosting procedure for least-squared
regression of additive expansion. Friedman (2002) incorporated randomness in
gradient boosting where a subsample of training set is drawn without
replacement at each iteration of gradient boosting. Mishina et al. (2014)
introduced a boosting algorithm into Random Forest learning method to achieve
high accuracy with the smaller size of forest. Ghosal and Hooker (2021)
proposed One-Step Boosted Forest for regression problem. They also gave a
variance estimate of Boosted Forest which makes the statistical inference of
ensemble model possible.

However, for "boosting-type" method, we typically need hundreds of iteration
times to turn a weak learner into a stronger one. Similarly, for "bagging-
type", such as Random Forests, hundreds or thousands of weak learners are
required to achieve a decent prediction accuracy. It’s hard for practitioners
to follow the performance of each weak learner when they analyze the model and
try to interpret the results. Mishina et al. (2014) illustrated that combining
boosting and random forest is helpful in reducing the number of base learners
required for boosted random forest. Following these clues, we introduce a
model based bagging-boosting procedure whose simple but efficient structure
could achieve high prediction accuracy with small number of base learners.

As to the interpretability of the classifier, if the base structure of a
classifier is decision tree, which is commonly used in many ensemble methods,
employing generalized linear models (GLM) at terminal nodes could be a good
choice because of its flexibility. The fitting process of a GLM is to maximize
its corresponding sample log-likelihood function by an iteratively re-weighted
least-squares(IRWLS) approach:

$\mathcal{\beta}^{(t+1)}=\mathcal{\beta}^{(t)}+\mathcal{J}^{-1}(\mathcal{\beta}^{(t)})u(\mathcal{\beta}^{(t)})$
(1)

where $\mathcal{\beta}^{(t+1)}$ is updated vector of parameters at step $t$,
$\mathcal{J}^{-1}(\mathcal{\beta}^{(t)})$ is the observed information matrix
and $u(\mathcal{\beta}^{(t)})$ is the score function. However, if we fit a GLM
by all features at each terminal node of tree, it’s highly likely that the
information matrix will have ill-posed condition as the number of observations
at a terminal node is typically small. As a result, matrix inversion during
fitting procedure is unavailable. To avoid those drawbacks, we can assume an
additive form of GLMs. Friedman et al. (2000a) proposed LogitBoost algorithm
by employing the additive model into logistic regression problem. If the
weighted least square regression is taken as the weak learner, LogitBoost will
add one feature at a time in boosting iteration, which avoids matrix
inversion. Logitboost also keeps the interpretability since it models the half
log-odds by a linear combination of selected features. Landwehr et al. (2005)
first combined LogitBoost and decision tree together and designed a tree model
called Logistic Tree Model(LMT). Similarly, Zheng and Liu (2012) proposed
ProbitBoost which fits the GLM with Probit link. In practice, GLM with probit
link and logistic link have similar performance under most contexts. While in
the theoretical point of view, Zheng and Liu (2012) pointed out that the re-
weighting function of LogitBoost will give a wrongly classified example a
small weight making it difficult to correct the error in the later iterations.
In ProbitBoost, the re-weighting step will assign larger weight for mis-
classified examples, which implies ProbitBoost has better self-correction
ability. In addition, Friedman et al. (2000a) required cross-validation to
determine optimal LogitBoost iteration steps at each inner and terminal node
when constructing a LMT. Due to the nature of cross-validation, we will
sacrifice part of training data in order to determine a hyperparameter. When
data size is relatively small, the benefit of cross-validation may be
overturned by the loss of effective data. Based on those observations, we’d
like to introduce our novel base tree learner named Probit Model Tree(PMT)
which combines ProbitBoost and decision tree together. By employing PMT as
base learner in our bagging-boosting structure, we can further show that there
is no need to control the iteration times in ProbitBoost part. That implies
hyperparameter tuning can be more straightforward and efficient since cross-
validation will be avoided in fitting process of our proposed model.

The remaining sections of this paper are organized as following schema. In
section 2, we introduce some related works for some hybrid bagging-boosting
methods. In section 3, we illustrate the idea of Probit model tree(PMT). After
that our new bagging-boosting method named SBPMT will be proposed in section
4, along with some theoretical analysis in section 5. We also compare the
performance of SBPMT in real datasets in section 6. An experiment with
simulation data will be demonstrated as well. Section 7 discusses few
characteristics of SBPMT and proposes future directions. The R codes for the
implementation of SBPMT, selected real datasets experiments and the simulation
are available on Github.111https://github.com/BBojack/SBPMT

##  2 Related works for bagging-boosting methods

Many popular boosting algorithms such as Stochastic Gradient Boosting
(Friedman (2002)), CatBoost (Ostroumova et al. (2017)), LightGBM (Ke et al.
(2017)) and XGBoost (Chen and Guestrin (2016)) can actually incorporate
bagging during the iteration in their implementation. That is, drawing a
subsample of training set based on the weights calculated at each iteration of
boosting to reduce the computation cost and avoid noise in data. In that way,
the bagging procedure is dependent upon boosting procedure and performed
sequentially. As a result, not whole training set will be utilized during the
iteration. It can be dangerous to ignore or pay less attention to part of the
training data when we have relatively small size of dataset. And in practice,
dosing randomness at each step of boosting forces practitioner to set large
number of iteration times to make sure the generated classifier is stable and
strong enough. As a result, the final model involves extremely large number of
weak learners and the model interpretation becomes nearly impossible.

Mishina et al. (2014) proposed Boosted Random Forest which introduces boosting
into random forest. More specifically, they sequentially added a decision tree
in the forest by AdaBoost. As a result, less number of trees are required to
maintain discrimination performance. They constructed a decision tree by
random sampling of features and splitting value to achieve the high generality
of the boosted random forest. But the price paid is the loss of
interpretation. It becomes even harder to measure the variance importance due
to these two layers of randomness.

Recently, Ghosal and Hooker (2021) proposed One-Step Boosted Forest for
regression problem. They also gave a variance estimate of Boosted Forest which
makes the statistical inference of ensemble models possible. Their empirical
results imply that taking independent subsamples to construct ensemble model
will generate better prediction than repeating the same subsamples. Although
their work is mainly about regression problem, that observation motivates us
to build a classifier by taking different possible subsamples, which is
exactly what subagging means.

##  3 Probit Model Tree

In this section, we will give a brief introduction of the idea of ProbitBoost
(Zheng and Liu (2012)) which is the core part of our algorithm. Next, the
whole procedure of PMT algorithm will be presented, which combines the
ordinary classification decision tree with ProbitBoost model at each node of a
decision tree.

###  3.1 ProbitBoost for Binary class

Suppose we have a training set with $n$ observations
$\\{(\mathbf{x}_{i},Y_{i})_{i=1,...,n}\\}$ where each item is associated with
class $Y_{i}\in\\{-1,1\\}$. $\mathbf{x}_{i}$ is the feature vector of $i$-th
observation and we assume that each observation has dimension $p$.

In ordinary probit regression model (binary classification problem), we model
the posterior class probability $P(Y=1|X=\mathbf{x}_{i})$ of $i$-th
observation by linking additive linear combination of features with the normal
cdf (cumulative distribution function) as follows:

$P(Y=1|X=x_{i})=\Phi(\sum_{j=1}^{p}\beta_{j}x_{ij})=\Phi(\beta^{T}\mathbf{x}_{i}),\quad
j=1,...,p$ (2)

where $p$ is the dimension of feature space , $\Phi(\cdot)$ is the cdf of
normal distribution and $x_{ij}$ represents the $j$-th feature of $i$-th
observation. The main assumption is the linear form of features at the right
hand side of (2). More generally, we can take any functional forms of the
input feature space to capture complicated patterns in a given dataset.

As a result, the generalized additive form can be written as

$F_{M}(\mathbf{x})=\sum_{m=1}^{M}f_{m}(\mathbf{x})$ (3)

for each m, $f_{m}(\mathbf{x})$ is a $R^{p}\to R$ function and the capital $M$
is the total number components of the general additive model, which makes it
possible to view the boosting procedure as a forward stagewise fitting
algorithm of additive models. In many contexts, functions $f_{m}(\mathbf{x})$
are taken to be some simple basis functions (mostly linear) so that the
fitting process is tractable and easy to interpret.

We now propose population probit risk function as following:

$P(f(\mathbf{x}))=-E[log(\Phi(Yf(\mathbf{x})))]$

and the empirical version is:

$\quad
P_{n}(f(\mathbf{x}))=-\frac{\sum_{i=1}^{n}log(\Phi(Y_{i}f(\mathbf{x_{i}}))}{n}$

, where $Y_{i}$ takes the value in $\\{-1,1\\}$.

Like other risk functions such as exponential risk and Logit risk, Probit risk
function is convex and second-order differentiable.

Following the structure of ProbitBoost proposed by Zheng and Liu (2012), we
give a brief derivation of ProbitBoost algorithm under Newton-Raphson
framework and Probit risk function. Reader can find similar details in their
work.

Suppose we are minimizing the populational probit risk function
$P(f(\mathbf{x}))=-E[log(\Phi(Yf(\mathbf{x})))]$, then the fitting process
proceeds by the Newton-Raphson iterative equation as follows:

$f^{(m+1)}(\mathbf{x})=f^{(m)}(\mathbf{x})-H^{-1}(f^{(m)}(\mathbf{x}))D(f^{(m)}(\mathbf{x}))$
(4)

where $f^{(m)}(\mathbf{x})$ is the fitted function at $m$-th step. This
setting coincides with the idea of forward stagewise additive model which
makes the implementation of algorithm convenient. Denote $D(),H()$ be the
first and second order derivative of expected log-likelihood function ,
respectively.

Under appropriate conditions, we can find out the gradient (first order
derivative) of $P(f(\mathbf{x}))$ w.r.t $f(\mathbf{x}))$ is :

$\begin{split}D(f)=-E\bigg{[}\frac{Y\phi(f)}{\Phi(Yf)}\bigg{|}\mathbf{x}\bigg{]}\end{split}$
(5)

Similarly, the Hessian( second order derivative) of $P(f(\mathbf{x}))$ is
calculated as

$\begin{split}H(f)=E\bigg{[}\frac{\phi(f)G_{Y}(f)}{\Phi^{2}(Yf)}\bigg{|}\mathbf{x}\bigg{]}=E[h(f)|\mathbf{x}]\end{split}$
(6)

where $G_{Y}(f)=Yf\Phi[Yf]-\phi(Yf)$.

Then the Newton-Rahpson iteration process can be written as

$\begin{split}f^{(m+1)}(\mathbf{x})&=f^{(m)}(\mathbf{x})-H^{-1}(f^{(m)}(\mathbf{x}))D(f^{(m)}(\mathbf{x}))\\\
&=f^{(m)}(\mathbf{x})-\frac{1}{E[h(f^{(m)})|\mathbf{x}]}\bigg{(}-E\bigg{[}\frac{Y\phi(f^{m})}{\Phi(Yf^{m})}\bigg{|}\mathbf{x}\bigg{]}\bigg{)}\\\
&=f^{(m)}(\mathbf{x})+E_{h}\bigg{[}\frac{Y\Phi(Yf^{(m)})}{G_{Y}(f^{(m)})}\bigg{|}\mathbf{x}\bigg{]}\end{split}$
(7)

where $E_{W}(\cdot|\mathbf{x})$ is the notation for weighted conditional
expectation defined in Friedman et al. (2000b), which means

$E_{w}[g(\mathbf{x},y)|\mathbf{x}]=\frac{E[w(\mathbf{x},y)g(\mathbf{x},y)|\mathbf{x}]}{E[w(\mathbf{x},y)|\mathbf{x}]}\quad\text{with}\quad
w(\mathbf{x},y)>0\quad\forall x\forall y.$ (8)

where $g(\mathbf{x},y)$ is an appropriate function with finite weighted
conditional expectation as defined in (8). In the last equation of (7), the
weight is $h(f)$. We can show that $h(f)$ is positive all the time so it makes
sense to use $h(f)$ as the weight function.

The the sample version of ProbitBoost is illustrated in Algorithm 1 below:

Initialization: Total iteration number $M$; training data
$\\{(\mathbf{x_{i}},Y_{i}),i=1,...,n\\};Y_{i}\in\\{-1,1\\}$;

Start with weights $w_{i}=1/n,i=1,2,...,n$, $f^{0}(\mathbf{x})=0$ and class
probability $p(\mathbf{x_{i}})=\frac{1}{2}$;

for  _$m=1,2,...,M$_ do

(a) Compute the working response $\mathbf{z}=(z_{1},...,z_{n})$ as

$z_{i}=\frac{(Y_{i}\Phi(f^{m-1}(x_{i})))}{G_{Y_{i}}(f^{m-1}(x_{i}))}$

for $i=1,2,...,n$;

(b) Compute the weights $w$ as

$w_{i}=\frac{\phi(f^{m-1}(x_{i}))G_{Y_{i}}(f^{m-1}(x_{i}))}{\Phi^{2}[Y_{i}f^{m-1}(x_{i})]}$

for $i=1,2,...,n$;

(c) Fit the current working response $\mathbf{z}$ by a weak learner
$g^{m}(\mathbf{x})$ with weights $w_{i}$, $i=1,2,...,n$.;

(d) Update $f^{m}(\mathbf{x})=f^{m-1}(\mathbf{x})+g^{m}(\mathbf{x})$

end for

Result: Output the classifier $sign[f^{M}(\mathbf{x})]$

Algorithm 1 ProbitBoost (Binary classification)

In next section we will give a specific example of weak learner
$g^{m}(\mathbf{x})$.

###  3.2 Weighted least square regressor as weak learner

In step (c) of Algorithm 1, we need to find a optimal weak learner so that the
probit risk function decreases the most. This idea is a kind of coordinate
descent method in optimization. Weighted least square regression or weighted
decision tree are two main options for the weak learner. Dettling and Bühlmann
(2003) applied regression stump in boosting. Similarly, Zheng and Liu (2012)
used regression stump in their ProbitBoost model and found that regression
stump performs better in many cancer and gene expression classification
datasets. However, in tabular datasets we found that regression stump has its
own pitfalls in tree models. The criterion of choosing best feature also
deserves discussing. Schmid et al. (2013) selected the attribute by the
largest increment of sample log-likelihood function.

Of course the weak learner can be non-linear. For instance, we can select
feature by kernel regression. However, one main drawback of using non-linear
weak learner as weak learner is, we may lose the interpretability of the
boosted classifier by introducing complicated structure. Meanwhile, especially
for kernel regression, the relationship between transform map and kernel is
not bijective. Despite the flexibility of choosing a particular kernel, it’s
hard to find the true transform map which makes interpretation more difficult.

We decide to apply weighted least square (WLS) regression as weak learner in
our ProbitBoost setting which makes interpretation possible and the time
efficiency is guaranteed by the formula of simple WLS without involving matrix
inversion. Note that the final fitted function $f^{M}(\mathbf{x})$ will have
the form of linear combination of features. We now summarize details in
step(c) at $m$-th iteration:

  * •

c(1) Perform weighted least square regression for each feature with weights
$w_{i}$ to obtain:

$(\hat{a}_{j},\hat{b}_{j})=\operatorname*{arg\,min}_{a,b}\sum_{i=1}^{n}w_{i}(z_{i}-ax_{j,i}-b)^{2}\quad\text{for
$j\in\\{1,...,p\\}$}$

  * •

c(2) Obtain the index $s(m)$ of optimal weak learner (optimal
direction/feature) which has the smallest weighted square error:

$s(m)=\operatorname*{arg\,min}_{j\in\\{1,...,p\\}}\sum_{i=1}^{n}w_{i}(z_{i}-\hat{a}_{j}x_{j,i}-\hat{b}_{j})^{2}$

  * •

c(3) Set $g^{m}(\mathbf{x})=\hat{a}_{s(m)}\mathbf{x}+\hat{b}_{s(m)}$

where vector
$\mathbf{w}=\frac{\phi(Yf^{m-1})[Yf^{m-1}\Phi(Yf^{m-1})+\phi(Yf^{m-1})]}{\Phi^{2}(Yf^{m-1})},\mathbf{z}=\frac{\phi(Yf^{m-1})}{Yf^{m-1}\Phi(Yf^{m-1})+\phi(Yf^{m-1})}$
and $\tilde{\mathbf{x}}=(1,\mathbf{x})$.

Eventually, the fitted additive probit regression function after $M$
iterations can now be represented as
$f^{M}(\mathbf{x})=\tilde{\mathbf{x}}^{T}(\sum_{i=1}^{M}\beta_{i})=\tilde{\mathbf{x}}^{T}\mathbf{\beta}$
where $\beta_{i}\in R^{p+1}$ and
$\beta_{i,1}=b_{s(i)},\beta_{i,s(i)+1}=a_{s(i)},\beta_{i,j}=0$ for $j\neq
1,s(i)+1$.

###  3.3 Growing the probit model tree

For simplicity and efficiency, we follow the spirit of CART algorithm to build
a decision tree first and and fit a probit model with ProbitBoost algorithm
described in section 3.1 at each terminal node for a tree. We don’t take
specific regularizations to control the complexity of models as in section 5
we will see there is actually no need to control the iteration times for
ProbitBoost. More specifically, regardless of time costing, large number of
iterations for ProbitBoost not only benefits the empirical probit risk but
also the prediction accuracy. The stopping rules includes min_leaf_size,
max_depth and max_iterations of ProbitBoost. In reality, user can set those
parameters by themselves based on the specific condition of experiments.

###  3.4 The model

As specified in section 3.1-3.3, a probit model tree consists of two parts.
The global structure is a decision tree with CART type. And the local
structure, which means a model at each terminal node of such a s tree, is a
probit regression model fitted by ProbitBoost.

Suppose $\\{S_{a}\\}_{a\in A}$ is a set of partitions determined by the CART
decision tree structure, where $A$ is the total number of partitions. Each
partition $S_{a}$ has an associated additive ProbitBoost model $G_{a}$
generated by Algorithm 1. Then the whole probit model tree is represented by

$G(\mathbf{x})=\sum_{a\in A}sign[G_{a}(\mathbf{x})]\cdot I(\mathbf{x}\in
S_{a})$ (9)

where $I(\mathbf{x}\in S_{a})=1$ if $\mathbf{x}\in S_{a}$ and 0 otherwise,
$\mathbf{x}$ is a data point.

As we take the weighted least square regressor as the weak learner, we can
further expand each $G_{a}(\mathbf{x})$ as following:

$G_{a}(\mathbf{x})=\mathbf{x}^{T}\beta^{a}$

where $\beta^{a}$ is the vector of coefficients fitted in accordance with the
procedure described in section 3.2.

Now the most detailed form of a probit model tree is written as

$\begin{split}G(\mathbf{x})&=\sum_{a\in A}sign[\mathbf{x}^{T}\beta^{a}]\cdot
I(\mathbf{x}\in S_{a})\\\ &=sign[\sum_{a\in A}\mathbf{x}^{T}\beta^{a}\cdot
I(\mathbf{x}\in S_{a})]\end{split}$ (10)

The second equality holds because of the fact that partitions
$\\{S_{a}\\}_{a\in A}$ are disjoint with each other.

Algorithm 2 summarizes the whole procedure for fitting a PMT.

Initialization: Number of ProbitBoost iteration $B$ ; Depth of PMT $l$;
training data $\mathcal{D}_{X}=\\{(\mathbf{x}_{i},Y_{i}),i=1,...,n\\}$ with
$\mathbf{x}_{i}\in\mathbb{R}^{p}$ and $Y_{i}\in\\{-1,1\\}$.

($a$) Fit a CART tree $T$ with maximal depth $l$ and obtain the corresponding
partition $\\{S_{a}\\}_{a\in A}$

($b$) for  _$a\in A$_ do

Perform ProbitBoost with iteration number $B$ for data points lying in the
partition $S_{a}$ and obtain the classifier
$G_{a}(\mathbf{x})=\mathbf{x}^{T}\beta^{a}$.

end for

Result: Output the final classifier $G(\mathbf{x})=sign[\sum_{a\in
A}\mathbf{x}^{T}\beta^{a}\cdot I(\mathbf{x}\in S_{a})]$

Algorithm 2 Probit Model Trees (PMT)

##  4 Subagging Boosted Probit Model Trees (SBPMT)

Having introducing the idea of Probit Model Tree, in this section, we will
give a new hybrid bagging-boosting algorithm based on PMTs. We consider the
binary case first. As mentioned before, intuitively, bagging-boosting
algorithm could improve the mean squared error simultaneously in two
directions. Instead of trading off variance and bias by regularization,
bagging-boosting type algorithm could reduce both of them at the same time.
For classification problems, such observation encourages us to implement
bagging-boosting type classifiers to reduce the misclassification error.

We first give a brief introduction of subagging. As a variant of the bagging
procedure, subagging, which is first proposed by Büchlmann and Yu (2002), is a
sobriquet for "subsample aggregating" where the bootstrap resampling is
replaced with subsampling. A learner or predictor $F_{n,m}(\mathbf{x})$ with
subsampling size $m$ is aggregated as follows:

$F_{n,m}(\mathbf{x})=\frac{1}{\binom{n}{m}}\sum_{(i_{1},...,i_{m})\in
l}h_{m}(L_{i_{1}},...,L_{i_{m}})(\mathbf{x})$ (11)

where $l$ is the set of all $m$-tuples whose elements in $\\{1,2,...,n\\}$ are
all distinct and $h_{m}(L_{i_{1}},...,L_{i_{m}})$ is a predictor based on a
subsampling with indices $(i_{1},...,i_{m})$. But in practice, it’s time
consuming to evaluate all $\binom{n}{m}$ subagged predictors. One way to avoid
heavy computation burden is to approximate (11) by random sampling . That is,
we randomly sample without replacement from original dataset for $M$ times and
averaging over the predictors based on random samplings. The subagged
predictor becomes:

$F_{n,m,M}(\mathbf{x})=\frac{1}{M}\sum_{i}^{M}h_{m}(L_{i_{1}},...,L_{i_{m}})(\mathbf{x})=\frac{1}{M}\sum_{i}^{M}h_{m}(L_{D_{i}})(\mathbf{x})$
(12)

where $(L_{i_{1}},...,L_{i_{m}})=L_{D_{i}}$. We will take this type of
subagging in our algorithm. Note that
$\mathcal{D}=(D_{1},...,D_{M})\in\\{D\subset[n]:|D|=m\\}^{M}$ is a sequence of
$M$ subsets of $\\{1,2,...,n\\}$ with cardinality $m$ and this sequence
$\mathcal{D}$ is called the design Kong and Zheng (2021). It’s easy to see
$F_{n,m,M}(\mathbf{x})$ is an incomplete $U$-statistic with order $m$ for most
learning algorithms. For simplicity, we take subsampling size $m=\lfloor\alpha
n\rfloor$ with $0<\alpha<1$.

Figure 1: Working flow of the SBPMT algorithm

The main idea of SBPMT is to perform AdaBoost at each subagged sampling. PMTs
will be used as base learner in Adaboost. Note that the individual weights
generated in AdaBoost are employed in both CART algorithm and ProbitBoost for
fitting a PMT. Figure 1 illustrates the working flow of SBPMT.

Algorithm 3 summarizes the details of the SBPMT algorithm. At step ($b$) we
relabel the indices of subsampled dataset from 1 to $\lfloor\alpha n\rfloor$
for the sake of simplicity.

Initialization: Number of subagging $M$; Number of AdaBoost iteration $T$
;Number of ProbitBoost iteration $B$ ;subagging ratio $\alpha$; Depth of PMT
$l$; training data
$\mathcal{D}_{X}=\\{(\mathbf{x}_{i},Y_{i}),i=1,...,n\\};Y_{i}\in\\{-1,1\\}$;

for  _$k=1,2,...,M$_ do

($a$) Randomly sample from the original training data $\mathcal{D}_{X}$
without replacement. The size $m$ of random sampled dataset
$\mathcal{D}_{X}^{k}$ is set to $\lfloor\alpha n\rfloor$. Initialize weights
$w_{1}(i)=1/m,i=1,2,...,m$

($b$) On $\mathcal{D}_{X}^{k}$, for  _$t=1,2,...,T$_ do

($b_{1}$) Fit a PMT classifier $G_{t}(\mathbf{x})$ to the subagged dataset
$\mathcal{D}_{X}^{k}$ using weights $w_{t}(i)$.

($b_{2}$) Compute $\alpha_{t}=\frac{1}{2}ln\frac{1-err_{t}}{err_{t}}$ where
$err_{t}=\sum_{i=1}^{m}w_{t}(i)I(Y_{i}\neq G_{t}(\mathbf{x}_{i}))$

($b_{3}$) Update weights: $w_{t+1}(i)=\frac{w_{t}(i)\cdot e^{\alpha_{t}\cdot
I(Y_{i}\neq G_{t}(\mathbf{x}_{i})}}{Z_{t}}$ where $Z_{t}$ is a normalization
factor so that $w_{t+1}(i)$ becomes a distribution, $i=1,2,...,m$.

end for

($c$)Output $f_{Z_{k},\lfloor\alpha
n\rfloor,T}(\mathbf{x})=sign[\sum_{t=1}^{T}\alpha_{t}G_{t}(\mathbf{x})]$,
where $f_{Z_{k},\lfloor\alpha n\rfloor,T}$ be fitted the AdaBoosted PMT with
$T$ iterations fitted by $k$ randome sampled dataset $\mathcal{D}_{X}^{k}$.

end for

Result: Output the final classifier
$F(\mathbf{x})=sign[\frac{1}{M}\sum_{k=1}^{M}f_{Z_{k},\lfloor\alpha
n\rfloor,T}(\mathbf{x})]$

Algorithm 3 Subagging Boosted Probit Model Trees (SBPMT)

###  4.1 Multi-class version

SBPMT can be generalized to multi-class problems by using multi-class versions
of AdaBoost and Probit Model Tree. Zheng and Liu (2012) proposed Multi-class
gradient ProbitBoost by maximizing the multiclass log-likelihood function for
probit regression. They also sketched one-versus-all approach to fit a multi-
class ProbitBoost classifier. The idea is to reduce a multi-class problem into
$J$ binary classification problems where $J$ is the number of classes. Due to
the simplicity of one-versus-all strategy, we will fit a PMT by one-versus-all
strategy instead of fitting multi-class ProbitBoost at each terminal node of a
CART tree.

Having a multi-class version of PMT, we incorporate it in a multi-class
version AdaBoost named SAMME which is proposed by Hastie et al. (2009). SAMME
extends the AdaBoost to the multi-class case without reducing it to multiple
binary problems. It is equivalent to forward stagewise additive modeling with
a multi-class exponential loss function. We choose this multi-class version of
AdaBoost because of its clean implementation. In practice, people can try many
other variants of multi-class AdaBoost.

We now sketch the multi-class version of SBPMT as following:

Initialization: Number of ProbitBoost iteration $B$ ; Depth of PMT $l$;
training data $\mathcal{D}_{X}=\\{(\mathbf{x}_{i},Y_{i}),i=1,...,n\\}$ with
$\mathbf{x}_{i}\in\mathbb{R}^{p}$ and $Y_{i}\in\\{1,2,...,J\\}$; Define
$y_{ij}=I(Y_{i}=J)$ for $i=1,2,...,n$ and $j=1,2,...,J$.

for  _$k=1,2,...,M$_ do

($a$) Randomly sample from the original training data $\mathcal{D}_{X}$
without replacement. The size $m$ of random sampled dataset
$\mathcal{D}_{X}^{k}$ is set to $\lfloor\alpha n\rfloor$. Initialize weights
$w_{1}(i)=1/m,i=1,2,...,m$.

($b$) On $\mathcal{D}_{X}^{k}$, for  _$t=1,2,...,T$_ do

($b_{1}$) Fit a multi-class PMT classifier $G_{t}(\mathbf{x})$ by Algorithm 2
using weights $w_{t}(i)$.

($b_{2}$) Compute $\alpha_{t}=\frac{1}{2}ln\frac{1-err_{t}}{err_{t}}+log(J-1)$
where $err_{t}=\sum_{i=1}^{m}w_{t}(i)I(Y_{i}\neq G_{t}(\mathbf{x}_{i}))$

($b_{3}$)Update weights: $w_{t+1}(i)=\frac{w_{t}(i)\cdot e^{\alpha_{t}\cdot
I(Y_{i}\neq G_{t}(\mathbf{x}_{i})}}{Z_{t}}$ where $Z_{t}$ is a normalization
factor so that $w_{t+1}(i)$ becomes a distribution, $i=1,2,...,m$

end for

($c$)Output $f_{Z_{k},\lfloor\alpha
n\rfloor,T}(\mathbf{x})=\underset{j\in\\{1,2,...,J\\}}{\mathrm{argmax}}\sum_{t=1}^{T}\alpha_{t}I(G_{t}(\mathbf{x})=j)$.

end for

Result: Output the final classifier
$F(\mathbf{x})=\underset{j\in\\{1,2,...,J\\}}{\mathrm{argmax}}(\sum_{k=1}^{M}I(f_{Z_{k},\lfloor\alpha
n\rfloor,T}(\mathbf{x})=J))$

Algorithm 4 Multi-class SBPMT

##  5 Theoretical analysis of SBPMT

In this section, we will show the Bayesian (weak) consistency w.r.t SBPMT
under some reasonable assumptions. A simple but useful fact that the
consistency of individual classifier is preserved by majority voting, which is
applied in the ensembling step of SBPMT, has been shown in Gao et al. (2022)
and Scornet et al. (2015). For completeness of our work, we gave a more
elementary proof. After that, we proved the consistency of AdaBoosted PMT
using the results from Bartlett and Traskin (2007).

In order to achieve decent performance of SBPMT in real datasets, we derived
an upper bound for the generalization error of SBPMT in section 5.3, which
illustrates the impact of each hyperparameter on the generalization error of
SBPMT.

###  5.1 Setup and notation

Again, for simplicity, we consider a binary classification problem. Let
$\mathcal{X}$ be the feature(measurable) space and $\mathcal{Y}=\\{-1,1\\}$ be
the set of labels. Suppose we observe a training data
$S_{n}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ of i.i.d observations from an unknown
distribution $\mathcal{P}$. We now construct a classifier
$g_{n}:\mathcal{X}\to\mathcal{Y}$ based on this training set. Then the
probability of error of $g_{n}$ is given by

$L_{n}=L(g_{n})=P(g_{n}(X)\neq Y|S_{n})$

which is also called empirical risk.

In theory Devroye et al. (1996), the expected risk of a given classifier
$g:\mathcal{X}\to\mathcal{Y}$ is defined as

$L(g)=E[I(g(X)\neq Y)]$

The optimal expected risk (or Bayes risk) $L^{*}$ is the infimum over all
possible classifiers g:

$L^{*}=\inf_{g}L(g)=E[min(\eta(X),1-\eta(X))]$

where $\eta(\cdot)$ is a conditional probability $\eta(x)=P(Y=1|X=x)$.

It’s well known that the infimum above can be achieved by the Bayes classifier
$g^{*}(x)=g(2\eta(x)-1)$:

$g(x)=\begin{cases}1,&x>0\\\ -1,&x\leq 0\end{cases}$

Note that $g^{*}$ relies on the distribution $\mathcal{P}$ of $(X,Y)$ and
expectation is taken over that unknown distribution $\mathcal{P}$. When the
sample size increases, we can have a sequence of classifiers $\\{g_{n},n\geq
1\\}$, which is denoted as a rule. Intuitively, we want a classifier have
small empirical risk and be close to the Bayes risk if we have enough data.
Statistically speaking, a rule is consistent under a certain distribution
$\mathcal{P}$ if:

$\lim_{n\to\infty}E[L(g_{n})]=L^{*}$

######  Remark.

Since $L_{n}$ is a random variable which is bounded, convergence of the
expected value is equivalent to the convergence in probability, which means
that

$\lim_{n\to\infty}P(|L(g_{n})-L^{*}|>\epsilon)=0$

for all $\epsilon>0$.

For the subagging classifier which takes a majority vote over classifiers
built upon $M$ random subsamples with subsampling ratio $\alpha$, we can
define $f_{M,n,T}(\mathbf{x})$ as following:

$f_{M,n,T}(\mathbf{x})=\begin{cases}1,&\frac{1}{M}\sum_{i=1}^{M}f_{Z_{i},\lfloor\alpha
n\rfloor,T}(\mathbf{x})>0\\\ -1,&\text{otherwise}\end{cases}$ (13)

where $(Z_{1},...,Z_{M})$ are i.i.d random variables (let $\mathcal{Z}$ be
their common distribution) representing the randomization introduced by
subsampling. In our case, $f_{Z_{i},\lfloor\alpha n\rfloor,T}$ is the
AdaBoosted PMT with $T$ iterations, which is constructed by $i$-th subagged
sample.

Next, we follow the settings in Bartlett and Traskin (2007).

Denote $\mathcal{H}=\\{h|h:\mathcal{X}\to\mathcal{Y}=\\{-1,1\\}\\}$ as the
hypothesis space and $d_{VC}(\mathcal{H})$ as VC (Vapnik-Chervonenkis)
dimension.

The convex hull of $\mathcal{H}$ scaled by $\lambda\geq 0$ is

$\mathcal{F}_{\lambda}=\bigg{\\{}f\bigg{|}f=\sum_{i=1}^{n}\lambda_{i}h_{i},n\in\mathcal{N}\cup\\{0\\},\lambda_{i}\geq
0,\sum_{i=1}^{n}\lambda_{i}=\lambda,h_{i}\in\mathcal{H}\bigg{\\}}$

.

Define

$R_{n}(f)=-\frac{1}{n}\sum_{i=1}^{n}e^{-Y_{i}f(X_{i})}\quad\text{and}\quad
R(f)=E[e^{-Yf(X)}].$

Then the Adaboost procedure can be summarized as follows.

  * •

1\. Set $f_{0}\equiv 0$, the number of iterations t and weights
$w_{1}(i)=1/n,i=1,2,...,n$.

  * •

2\. For $k=0,...,t$, the updating equation is

$f_{k+1}=f_{k}+\alpha_{k}h_{k}$

where $f_{k}$ satisfies
$R_{n}(f_{k})=\displaystyle\inf_{h\in\mathcal{H},\alpha\in\mathbb{R}}R_{n}(f_{k-1}+\alpha
h)$. More specifically,

    * –

2(a). Fit a classifier to the training data with weights $w_{i}$ to obtain
optimal base learner $h_{k}$

    * –

2(b). Compute $\varepsilon_{k}=\sum_{i=1}^{n}w_{k}(i)I(y_{i}\neq
f_{k}(x_{i})$.

    * –

2(c). Compute step size
$\alpha_{k}=\frac{1}{2}ln\bigg{(}\frac{1-\varepsilon_{k}}{\varepsilon_{k}}\bigg{)}$.

    * –

2(d). Update weights: $w_{k+1}(i)=\frac{w_{k}(i)\cdot e^{\alpha_{k}\cdot
I(y_{i}\neq f_{k}(x_{i})}}{Z_{k}}$ where $Z_{k}$ is a normalization factor so
that $w_{k+1}(i)$ becomes a distribution.

  * •

3\. Return $g\circ f_{t}$ as a final classifier.

######  Remark.

Note that step 2 is very general in theory. In practice, people typically
choose decision tree as the base learner. In our case, we use PMT as the base
learner.

In the end, we give a definition of Gateaux derivative of functions between
Banach spaces $\mathcal{A}$ and $\mathcal{B}$. Let $U\subset\mathcal{A}$ be
open, and $F:U\to\mathcal{B}$. The Gateaux differential $F^{\prime}(f;h)$ of
$F$ at $f\in U$ in the direction $h\in\mathcal{A}$ is defined as:

$F^{\prime}(f;h)=\frac{\partial F(f+\lambda
h)}{\partial\lambda}\bigg{|}_{\lambda=0}=\lim_{\lambda\to 0}\frac{F(f+\lambda
h)-F(f)}{\lambda}$

The second derivative $F^{\prime\prime}(f;h)$ is defined similarly. For
example, let $f,\mathbf{x}$ be vectors in an inner product space
$\mathcal{V}$. Denote $F(f)=x^{T}f$, then

$F^{\prime}(f;h)=\lim_{\lambda\to
0}\frac{\mathbf{x}^{T}f+\lambda\mathbf{x}^{T}h-\mathbf{x}^{T}f}{\lambda}=\mathbf{x}^{T}h$

###  5.2 Consistency of SBPMT

We first give a lemma showing the connection of consistency of individual
classifier and the voting classifier. Similar results have been proved in
Scornet et al. (2015), Gao et al. (2022).

######  Lemma 1.

Suppose the number of subbagged classifiers is $M$ and the sequence of each of
them is consistent for the same distribution $\mathcal{P}$, i.e
$\\{f_{Z_{i},\lfloor\alpha n\rfloor,T}(\mathbf{x})\\}_{n=1}^{\infty}$ is
consistent for each $i\in\\{1,2,...,m\\}$, then the voting classifier
$f_{M,n,T}(\mathbf{x})$ defined in (13) is also consistent.

If the iteration times in Adaboost depends on sample size, Bartlett and
Traskin (2007) have shown that Adaboost is consistent if it is stopped at
certain step. We restate their result in Theorem 1:

######  Theorem 1 (Bartlett and Traskin (2007)).

Assume $d_{VC}(\mathcal{H})$ is finite and $L^{*}>0$,

$\lim_{\lambda\to\infty}\inf_{f\in\mathcal{F}_{\lambda}R(f)}=R^{*}$

, where $\mathcal{H}$ is the base classifier space, $R^{*}=\inf R(f)$ over all
measureable functions, $t_{n}\to\infty$, and $t_{n}=O(n^{\nu})$ for $\nu<1$.
Then AdaBoost stopped at step $t_{n}$ returns a sequence of classifiers almost
surely satisfying $L(g(f_{t_{n}}))\to L^{*}$.

If we can show that the hypothsis space $\mathcal{H}$ in SBPMT has finite VC-
dimension, consistency of SBPMT follows directly from Lemma 1 and Theorem 1 as
long as we stopped adaboost procedure at the step required by Bartlett and
Traskin (2007). This gives rise to one of our main theorems:

######  Theorem 2 (Consistency of SBPMT).

Let $\mathcal{H}$ be the hypothesis space consists of Probit Model Trees, then
$d_{VC}(\mathcal{H})<\infty$ and $E[L(g(f_{M,n,T_{n}}))]\to L^{*}$, where $M$
is the number of subagging classifiers, $n$ is the sample size,
$T_{n}=O(n^{\nu})$ for $\nu<1$, i.e the final classifier returned by SBPMT is
consistent.

###### Proof.

Note that $\mathcal{H}$ in SBPMT consists of PMTs which are decision tress
composed with Probit boosting functions, by intuition, the VC-dimension should
be finite as well.

Denote the hypothesis space $\mathcal{H}_{1}$ be the set consists of decision
trees (with partition structure). And let $\mathcal{H}_{2}$ consist of
classifiers in the form of linear indicator functions generated from
ProbitBoost procedure in Algorithm 1 with weighted least square regressors
being weak learners. More specifically,
$\mathcal{H}_{2}=\\{f|f(\mathbf{x})=sign(\mathbf{\beta}^{T}\mathbf{x}+b),\mathbf{\beta}\in\mathbb{R}^{p},b\in\mathbb{R}\\}$
when the dimension of input data is $p$. Then it’s easy to check that

$d_{VC}(\mathcal{H}_{2})=p+1<\infty$

Note that $\mathcal{H}$ in SBPMT consists of PMTs. We have

$d_{VC}(\mathcal{H})\leq d_{VC}(\mathcal{H}_{1}\cup\mathcal{H}_{2})\leq
d_{VC}(\mathcal{H}_{1})+d_{VC}(\mathcal{H}_{2})+1$

Leboeuf et al. (2020) has shown that the VC-dimension of a binary tree
structure is of order $O(Nlog(Nl))$ where $N$ is the number of internal nodes
and $l$ is the number of real-valued features. Once we fix the depth of
decision trees $d$, $d_{VC}(\mathcal{H}_{1})$ will be finite. The consistency
of SBPMT follows from Theorem 1. ∎

###  5.3 Generalization error bound

Derived from Lemma 1 and Theorem 1, Theorem 2 implies that the consistency of
SBPMT mainly results from the consistency of AdaBoost, which is true only when
we connects stopping rule with sample size in a certain way. However, the
proof ignores the effect of subagging which can be more useful in real cases.
In this section, we will give an explicit expression of the finite sample
upper bound of generalization error of SBPMT which demonstrates the effect of
each hyperparameter in SBPMT hence guides us how to improve the performance of
SBPMT in practice. We will set the boosting iteration be independent of the
sample size since the requirement for consistency proved in Theorem 2 is not
realistic in most real cases

######  Theorem 3.

Suppose the number of subagged classifiers is $M$ and $M>ln^{2}n$ , then over
the random sampling in subagging step, with $\delta(>0)$ and probability at
least $1-\delta$ we have the following upper bound of generalization error of
voting classifier $f_{M,n,T}$ defined in equation 13:

$P_{\mathcal{P}}(g(f_{M,n,T}(\mathbf{X}))\neq Y)\leq
exp\bigg{(}\frac{-(\frac{\lceil
M/2\rceil-M/2}{M}+1-2p_{sub})^{2}}{2Q_{A}^{2}\sigma_{1}^{2}+Q_{B}^{2}\beta/2+(\sqrt{Q_{B}\gamma}+4Q_{C}^{2}/3)(\frac{\lceil
M/2\rceil-M/2}{M}+1-2p_{sub})}\bigg{)}$ (14)

,where:

$\displaystyle\begin{split}p_{sub}&=P_{\mathcal{P}}(f_{Z_{i},m,T}(X)\cdot
Y\leq 0),i=1,2,...,M.\\\ m&=\lfloor\alpha n\rfloor,0<\alpha\leq 1\\\
\sigma_{1}^{2}&=Var(\mathbb{E}(f_{Z_{i},m,T}(X_{1},...,X_{m})|X_{1}))\\\
Q_{A}&=\sqrt{\frac{m^{2}}{n}}+\bigg{(}1+4\sqrt{ln(3/\delta)}\bigg{)}\sqrt{\frac{m}{M}}\\\
Q_{B}&=\frac{m^{2}}{n}+\bigg{(}1+4\sqrt{ln(3/\delta)}\bigg{)}\frac{m}{\sqrt{M}}\\\
Q_{C}&=\frac{m}{n}+\frac{\sqrt{2m}+3}{\sqrt{M}}ln(3/\delta)\end{split}$ (15)

The subscript $\mathcal{P}$ means that random samples in a given dataset are
all generated from the unknown distribution $\mathcal{P}$.

######  Remark.

  1. 1.

Note that the RHS of the inequality above is a monotonic increasing function
w.r.t the value of $p_{sub}$. This enables us to replace $p_{sub}$ by some
upper bounds so that we can make the inequality for the generalization error
upper bound more flexible.

  2. 2.

We have two layers of randomness in SBPMT. The outer layer is the random
sampling from from the unknown distribution $\mathcal{P}$. The inner
randomness, which is measured by the positive number $\delta$, comes from the
subagging step.

Theorem 3 tells us that the number of subaggingg times plays a role in
controlling the generalization error bound of SBPMT. When we increase $M$, the
RHS of the inequality above will decrease accordingly. However, quantities
$Q_{A},Q_{B}$ and $Q_{C}$ won’t vanish even when $M\to\infty$, which implies
that the large number of $M$ doesn’t necessarily give a better performance of
the ensemble classifier. Such observation motivates us to improve time
efficiency in practice by not setting $M$ too large. The requirement that
subagging numbers should be larger than $ln^{2}n$ is not too strict in
practice. Suppose we have 20000 observations, Theorem 3 suggests that we need
to set $M$ be larger than $ln^{2}(20000)\approx 98.08$.

On the other hand, the RHS of inequality (14) is a decreasing function w.r.t
$p_{sub}$. That means, hyperparameters benefiting the performance of boosted
classifiers also improve the generalization error bound. Based on this
property, we recall two useful theorems in the margin theory of AdaBoost.

######  Theorem 4 (Schapire and Freund (2012)).

Suppose we run AdaBoost for T rounds on $n$ random samples, using base
classifiers from a hypothesis space $\mathcal{H}$ with finite VC-dimension
$d$. Assume $n\geq max\\{d,T\\}$, then the boosted classifier $F$ satisfies

$P_{\mathcal{P}}(YF(X)\leq 0)\leq P_{S}(YF(X)\leq
0)+\sqrt{\frac{32[T(ln(en/T))+d(ln(em/d))+ln(8/\delta)]}{m}}$

, with probability at least $1-\delta$ (over the choice of random sample from
distribution $\mathcal{P}$). $P_{S}(YF(X)\leq 0)$ is the empirical error rate
of boosted classifier $F$.

######  Remark.

If we replace $F$ in the LHS of the inequality with a subagging classifier,
$P_{\mathcal{P}}(YF(X)\leq 0)$ can be written as $p_{sub}$.

######  Theorem 5 (Schapire et al. (1998)).

Given a training set $S$, suppose AdaBoost generates classifiers with weighted
training errors $\varepsilon_{1},...,\varepsilon_{T}$ and final weighted
classifier is $f$. Then for any $\theta$, we have

$P_{S}(Yf(X)\leq\theta)\leq
2^{T}\prod_{t=1}^{T}\sqrt{\varepsilon_{t}^{1-\theta}(1-\varepsilon_{t})^{1+\theta}}$

Now let $\theta=0$, we have

$P_{S}(Yf(X)\leq 0)\leq
2^{T}\prod_{t=1}^{T}\sqrt{\varepsilon_{t}(1-\varepsilon_{t})}$

Let $\varepsilon_{t}=1/2-\gamma_{t}$, we can further obtain the following
inequality (Schapire and Freund (2012)):

$P_{S}(Yf(X)\leq 0)\leq\prod_{t}^{T}\sqrt{1-4\gamma_{t}^{2}}\leq
exp\bigg{(}-2\sum_{t=1}^{T}\gamma_{t}^{2}\bigg{)}$ (16)

if $0<\gamma_{t}\leq\frac{1}{2}$ for $t=1,2,...,T$.

Inequality (16) shows that the training error of AdaBoost decreases
exponentially fast. However, the second term in the RHS of the inequality in
Theorem 4 might increase as well when $T$ becomes large. This observation
implies that there might be an optimal iteration time $T^{*}$ for AdaBoost
which gives the smallest generalization error upper bound.

On the other hand, when $T$ gets even larger, the upper bound in Theorem 4
becomes useless. Schapire et al. (1998) gave an example showing that the
boosting can have even smaller testing error when the training error becomes
zero already. Although they also proposed the margin theory to qualitatively
explain the shape of the observed learning curves and Gao and Zhou (2013)
proved a sharper upper bound of generalization error of AdaBoost based on
margin theory, it’s still unclear how these results provide practical guidance
in controlling the prediction error.

Fortunately, we are able to give a specific upper bound like Theorem 4 by
properties of ProbitBoost, which is useful in controlling the generalization
error by not setting $T$ too large. Lemma 2 and Lemma 3 are the two most
critical properties of ProbitBoost we will use.

######  Lemma 2.

Let $Q(x)=-log(\Phi(x))$ where $x$ is any real number and $\Phi$ is the
cumulative probability function for standard normal distribution. Then
$Q^{\prime\prime}(x)>0$ and $Q^{\prime\prime\prime}(x)<0$.

######  Lemma 3.

Let $P_{n}$ be the empirical probit risk function defined in section 3.1. A
sequence of functions $\\{f^{t}\\}_{t\geq 0}$ is generated by ProbitBoost
described in section 3.1-3.2, i.e $f^{t+1}=f^{t}+g^{t}$ where $g^{t}$ is the
base learner fitted at $t$-th iteration of ProbitBoost. Then for a given
dataset and each $t\geq 0$,

$P_{n}(f^{t})-P_{n}(f^{t+1})\geq\frac{1}{2}\gamma||g^{t}||_{2}^{2}$

. In particular, $P_{n}(f^{t})\downarrow\inf_{k}P_{n}(f^{k})$ as $t\to\infty$,
$\sum_{t=1}^{\infty}||g^{t}||_{2}^{2}<\infty$, and
$\lim_{t\to\infty}||g^{t}||_{2}=0$, where
$||g^{t}||_{2}=\sqrt{\sum_{i=1}^{n}g^{t}(x_{i})^{2}/n}$ and
$\gamma=\inf\\{P_{n}^{\prime\prime}(f),f\in\mathcal{H}\\}$ ( which is positive
for a given data set)

In Lemma 3, we assume that each observation is equally weighted when we
calculate empirical probit risk function. As we can see in the proof of Lemma
3, the non-increasing property of empirical probit risk function in
ProbitBoost is still true for arbitrary weighted distribution of sample points
due to the definition of Gateaux derivative. This observation is critical in
seeing the importance of Theorem 6. We now give Corollary 1 without proof to
emphasize this point:

######  Corollary 1.

The non-increasing property still holds when we apply the ProbitBoost to
minimize the weighted probit risk function $P_{n,\mathbf{w}}$, where
$\mathbf{w}$ is the weight vector assigned to sample points.

Lemma 3 implies that increasing the number of iterations in ProbitBoost will
always reduce the value of empirical probit risk function. Note that for
$\forall z\in R$:

$I(z\leq 0)\leq\frac{Q(z)}{ln2}$ (17)

It follows that large number of iterations in ProbitBoost at each terminal
node of PMT will generate a smaller upper bound of weighted training error. As
a result, we can iterate Adaboost procedure in SBPMT for a few times to
achieve good performance with the price of relatively large number of
iterations in ProbitBoost. As we pointed out in section 3.2, generating a
simple linear combination of features makes a ProbitBoost classifier maintain
the interpretability even after a long time iteration. Thus the final model
won’t be too complicated. Theorem 6 then gives the upper bound of
generalization error of AdaBoost when PMTs are base learners:

######  Theorem 6.

Suppose we run AdaBoost for T rounds on $n$ random samples, using base
classifiers from a hypothesis space consisting of PMTs. Let
$\varepsilon_{t}^{P}(B)$ be the weighted probit risk of a PMT at $t$-th
iteration of AdaBoost. Integer number $B$ represents the ProbitBoost iteration
times at each terminal node of a PMT. Let $d$ be the upper bound of VC-
dimension of the hypothesis space consisting of PMTs. Assume $n\geq
max\\{d,T\\},0\leq\varepsilon_{t}^{P}(B)/ln(2)<\frac{1}{2}$, then the boosted
classifier $F$ satisfies

$P_{\mathcal{P}}(YF(X)\leq 0)\leq
exp\bigg{(}-2\sum_{t=1}^{T}\gamma_{t}^{2}(B)\bigg{)}+\sqrt{\frac{32[T(ln(en/T))+d(ln(en/d))+ln(8/\delta)]}{n}}$
(18)

, with probability at least $1-\delta$ (over the choice of random sample from
distribution $\mathcal{P}$). $\gamma_{t}(B)$ is defined to be:

$\gamma_{t}(B)=\frac{1}{2}-\frac{\varepsilon_{t}^{P}(B)}{ln(2)}$

.

According to Corollary 1, for fixed $T$, if we fit weighted probit risk
function at each partitioned space, $\varepsilon_{t}(B)$ will decrease as we
increase the ProbitBoost iteration time $B$, which in fact lowers down the
value of $exp(-2\sum_{t=1}^{T}\gamma_{t}^{2}(B))$ as long as we set $B$ large
enough. That means the assumption of $\varepsilon_{t}^{P}(B)$ in Theorem 6
makes sense in practice.

The main message conveyed by Theorem 6 is that employing PMTs as base learner
in AdaBoost can not only lead to a smaller prediction error without setting
running time $T$ of AdaBoost large but also make the second term in the upper
bound (18) meaningful when $T$ is small. The cost is we need to set large
number of ProbitBoost iterations at each terminal node of trees to achieve
smaller (weighted) training error for each partition. Combining these facts
with Theorem 3, we anticipate that SBPMT with less AdaBoost iterations steps
and subagging times could have even better performance than ensemble methods
using ordinary (CART) trees (no model included) as base learner. In section 6,
the performance of SBPMT will be compared with other popular ensemble learning
algorithms.

##  6 Experiments

###  6.1 Simulation

To verify the conjecture in section 5, we created an artificial dataset which
is in the spirit to the work of Mease and Wyner (2008). More specifically, we
will generate data point from the following model:

$P(Y=1|\mathbf{x})=q+(1-2q)\mathbf{1}\bigg{(}\sum_{e=1}^{E}\mathbf{x}^{(e)}>E/2\bigg{)}$

where $\mathbf{x}^{e}$ is the $e$-th dimension of an observation $\mathbf{x}$.
The response $\mathbf{Y}\in\\{-1,1\\}$ and random sample $X$ will be i.i.d and
uniformly distributed on the $d$-dimension unit cube $[0,1]^{d}$. According to
Mease and Wyner (2008), $q$ is the Bayes error and $E\leq d$ is the effective
dimension. For time efficiency, we only set $d=10$ and effective dimension
$E=5$. There are 2000 training cases and 10000 test observations. Each subplot
in Figure 2 illustrates test error rate for SBPMT, as a function of a single
hyperparameter. The benchmark setting for SBPMT is $M=5,B=5,T=5$ and
$\alpha=0.7$. And each CART tree has depth $d=3$ with min_leaf_size 20. To
obtain, for example the test error as a function of subagging times, we set
$M=1,2,...,100$ while other parameters remain the same with benchmark setting.
Similar strategy was applied to the other three hyperparameters we are
interested.

(a)

(b)

(c)

(d)

Figure 2: Test errors for SBPMT. (a) Test error rate as a function of
Subbagging Times, (b) Test error rate as a function of AdaBoost iterations,
(c) Test error rate as a function of ProbitBoost iterations, (d) Test error
rate as a function of Subagging ratio.

As we can see in Figure 2, as subagging times increase the test error rate
will in general decreases. When the subagging time is large, the improvement
of test prediction is negligible which obeys the anticipation from inequality
(14). On the other hand, when boosting iterations for AdaBoost part proceed,
the error rate decreases as well. Similar observation can be made for boosting
iterations for ProbitBoost part. Nevertheless, it can be seen in subplots that
test error w.r.t ProbitBoost iterations decreases more steadily which implies
a smaller variance while it shows a relatively large volatility in AdaBoost
iterations. Such difference can be inferred from fact that the empirical
probit risk function is tigher than exponential risk w.r.t the indicator
function, which favors the non-increasing property in Lemma 3. What’s more,
test error function of ProbitBoost iterations has the lowest long run test
error. This is a clue showing that ProbitBoost can dominate the effect from
subagging and AdaBoost. In other words, local structure can indeed capture
data patterns which may be ignored by global structure of the ensemble method.
It’s hard to see any pattern for test error and subagging ratio. This
observation can also expected from the generalization error bound in Theorem 3
as $\alpha$ appears in not only three quantities $Q_{A},Q_{B}$ and $Q_{C}$ but
also $p_{sub}$ which is far more complicated. The only thing we can clearly
see is, when we set $\alpha=1$, i.e the full dataset is utilized, we will end
with relatively high test error as SBPMT will reduce to a single boosted
classifier which might learn noise from the whole dataset.

###  6.2 Performance with real datasets

Table 1:  Real datasets used for the experiments,sorted by size Dataset | Instances | Numerical attributes | Categorical attributes | Classes
---|---|---|---|---
Iris | 150 | 4 | 0 | 3
Glass | 214 | 9 | 0 | 6
Ionosphere | 351 | 33 | 0 | 2
Diabetes | 520 | 0 | 17 | 2
Breast-Cancer | 569 | 30 | 0 | 2
Balance-scale | 625 | 4 | 0 | 3
Australian | 690 | 6 | 8 | 2
Pima-indians | 768 | 8 | 0 | 2
Vehicle | 846 | 18 | 0 | 4
Raisin | 900 | 7 | 0 | 2
Tic-tac-toe | 958 | 0 | 9 | 2
German | 1000 | 6 | 14 | 2
Biodegradation | 1051 | 38 | 3 | 2
BHP | 1075 | 20 | 1 | 4
Diabetic | 1151 | 16 | 3 | 2
Banknote | 1372 | 4 | 0 | 2
Contraceptive | 1473 | 2 | 7 | 3
Obesity | 2111 | 3 | 13 | 7
Segments | 2310 | 19 | 0 | 7
Waveform+noise | 5000 | 40 | 0 | 3
Pendigits | 10000 | 16 | 0 | 10
Letter | 20000 | 16 | 0 | 26
Table 2:  Mean classification accuracy and standard deviation for SBPMT
vs.RandomForest,GradientBoost(100)
AdaBoost.M1(100),XGBoost(10),XGBoost(100)

Dataset | SBPMT | RandomForest | GradientBoost(100) | AdaBoost.M1(100) | XGBoost(10) | XGBoost(100)
---|---|---|---|---|---|---
Iris | 96.00 $\pm$ 5.62 | 94.67$\pm$ 5.26 | 94.67$\pm$6.13 | 94.00$\pm$ 7.34 | 95.33 $\pm$ 5.49 | 95.33$\pm$5.49
Glass | 75.67 $\pm$ 8.97 | 77.09$\pm$ 9.57 | 75.27$\pm$9.55 | 73.26$\pm$9.60 | 75.62 $\pm$ 8.78 | 77.53 $\pm$9.35
Ionosphere | 92.87 $\pm$ 2.75 | 93.68$\pm$ 3.84 | 92.00 $\pm$ 3.77 | 93.68$\pm$ 3.39 | 92.86 $\pm$ 2.79 | 92.85 $\pm$2.10
Diabetes | 95.96 $\pm$ 1.42 | 97.69$\pm$ 1.52 | 91.35$\pm$3.04 | 97.5$\pm$2.04 | 95.38$\pm$ 2.26 | 95.38 $\pm$2.26
Breast-Cancer | 97.03 $\pm$ 2.45 | 96.34 $\pm$ 4.27 | 95.82 $\pm$4.62 | 96.16 $\pm$ 3.62 | 93.89 $\pm$5.72 | 95.64 $\pm$ 4.96
Balance-scale | 95.19 $\pm$ 2.62 | 83.53 $\pm$ 4.08 | 90.88 $\pm$1.52 | 85.46$\pm$ 3.86 | 86.56$\pm$ 2.73 | 87.84 $\pm$3.22
Australian | 86.39 $\pm$ 1.97 | 87.41$\pm$ 3.69 | 86.25$\pm$ 3.11 | 85.26$\pm$ 4.90 | 85.53$\pm$ 3.81 | 86.97 $\pm$3.03
Pima-indians | 77.73 $\pm$ 6.24 | 76.57$\pm$ 6.12 | 75.78 $\pm$ 5.30 | 73.31$\pm$ 6.03 | 75.26 $\pm$ 7.07 | 75.65 $\pm$6.76
Vehicle | 82.97 $\pm$ 4.92 | 75.30 $\pm$ 3.95 | 72.81 $\pm$3.43 | 78.49 $\pm$ 3.43 | 76.35 $\pm$ 4.36 | 78.25 $\pm$ 3.90
Raisin | 86.44 $\pm$ 3.70 | 86.44 $\pm$ 4.02 | 86.56 $\pm$3.65 | 86.89 $\pm$ 4.68 | 84.67$\pm$ 6.01 | 84.33 $\pm$ 4.04
Tic-tac-toe | 97.91 $\pm$1.56 | 99.16 $\pm$ 1.08 | 74.23 $\pm$3.76 | 99.58 $\pm$ 0.73 | 98.22 $\pm$ 1.72 | 98.33 $\pm$1.50
German | 74.80 $\pm$ 3.39 | 76.20$\pm$ 3.74 | 75.20 $\pm$ 2.78 | 74.60$\pm$3.17 | 74.30 $\pm$ 3.34 | 75.7 $\pm$2.41
Biodegradation | 87.59$\pm$ 1.92 | 87.20 $\pm$ 2.47 | 84.16 $\pm$3.73 | 86.54 $\pm$1.64 | 86.16 $\pm$ 2.67 | 86.63 $\pm$ 1.84
BHP | 100 $\pm$ 0 | 100$\pm$ 0.00 | 86.90$\pm$3.79 | 100$\pm$0.00 | 98.97 $\pm$ 1.36 | 100 $\pm$0.00
Diabetic | 74.02 $\pm$ 4.96 | 67.95$\pm$ 5.68 | 65.86 $\pm$ 4.56 | 67.95$\pm$ 4.12 | 68.98 $\pm$ 4.89 | 67.86 $\pm$5.33
Banknote | 99.78 $\pm$ 0.35 | 99.34$\pm$ 0.94 | 96.72 $\pm$2.02 | 99.64 $\pm$ 0.52 | 98.61 $\pm$ 1.44 | 98.69 $\pm$ 1.32
Contraceptive | 55.93 $\pm$ 4.42 | 54.16$\pm$ 3.33 | 55.46$\pm$2.56 | 55.73$\pm$3.33 | 54.44 $\pm$ 3.34 | 52.00 $\pm$3.93
Obesity | 97.39 $\pm$1.10 | 95.03$\pm$ 1.12 | 82.19$\pm$2.18 | 97.44 $\pm$ 1.03 | 95.08$\pm$ 1.45 | 97.49 $\pm$0.92
Segments | 98.31 $\pm$ 1.18 | 97.79$\pm$ 1.84 | 94.76$\pm$2.04 | 98.53$\pm$1.24 | 97.71 $\pm$ 1.61 | 98.48 $\pm$1.25
Waveform+noise | 86.16 $\pm$ 1.39 | 85.36$\pm$ 2.08 | 84.78$\pm$1.93 | 84.56$\pm$2.02 | 84.26$\pm$ 1.74 | 85.38 $\pm$1.93
Pendigits | 99.38 $\pm$ 0.24 | 99.21$\pm$ 0.25 | 90.63$\pm$1.17 | 98.57$\pm$0.25 | 98.20 $\pm$ 0.49 | 99.18 $\pm$0.33
Letter | 95.50 $\pm$ 0.31 | 96.85$\pm$ 0.24 | 73.17$\pm$0.64 | 96.12$\pm$0.36 | 90.14 $\pm$ 0.90 | 96.60 $\pm$0.27

  * *

*The best performing values are highlighted in bold

We used 22 benchmark datasets from the UCI repository (Kelly et al.) to
evaluate the performance of SBPMT and compare against with other state-of-the-
art boosting learning algorithms. The details of those dataset are included in
Table 1. For simplicity, we didn’t use datasets with missing values but there
are many methods to deal with this issue in practice. The size of datasets
ranges from one hundred to twenty thousand observations. They contain varying
number of numerical attributes and categorical attributes. We also deal with
some multi-class problems.

Ten fold stratified cross-valiation was performed for each dataset and
algorithm. For each algorithm, they shared the same training and testing
splitting. Mean classification accuracy and standard deviation are reported in
Table 2222The default subsampling ratio in GradientBoost and XGBoost is set to
be 0.7 for the sake of comparison. All algorithms are implemented by
corresponding R packages.333We employed ”rpart” package for RandomForest;R
package ”adabag” and ”RWeka“ are used for AdaBoost; ”xgboost” is used for
XGBoost algorithm; ”gbm” is used for GradientBoost. R markdown files for
experiments and figures can be found in https://github.com/BBojack/SBPMT

In practice, people can apply cross-validations to determine the best value of
hyperparameters. In theory, for instance, theorem 3 suggests that the
subagging number $M$ be larger than $ln^{2}(n)$. Lemma 2 and Theorem 5
encourage small number iterations in AdaBoost but large number of iterations
in ProbitBoost when using PMTs as base learners. For simplicity and time
efficiency, we used same hyperparametes in SBPMT for all datasets. More
specifically, number of subagging $M=21$, number of AdaBoost iteration $T=5$,
number of ProbitBoost iteration $B=100$, subagging ratio $\alpha=0.7$, depth
of CART tree $l=6$ and min_leaf_size is 20. We set relatively small subagging
times in order to speed up the training part. It turns out that small value of
$M$ is enough for SBPMT achieving decent accuracy in many real cases. If time
efficiency is not a priority, we recommend that the value of $M$ should
satisfy the theoretical inequality in Theorem 3. Otherwise, a small value of
$M$ is enough. The number of AdaBoost iteration and the number of ProbitBoost
iteration are set in accordance with analysis in section 5 and simulation
results.

From Table 2 we see that SBPMT reaches almost the same mean classification
accuracy as XGBoost(with 100 iterations) and many other popular ensemble
algorithms. It outperforms all selected algorithms on 11 datasets which
consist of small, medium and large-sized datasets. That implies SBPMT is
competitive with any size of datasets. Compared with Random Forest which
typically needs 500 subtrees, SBPMT in our experiments only uses 21 subagged
samples. More over, the AdaBoost iteration times in SBPMT is only 5 which is
much smaller than that of normal AdaBoost using hundreds of CART trees as base
learners. Based on these points, SBPMT makes the final model potentially
easier for practitioner to understand without digging into too many subtrees.
The linear form of PMT at terminal nodes of trees enables people to interpret
the effect of features at each partitioned space.

In Figure 3, we first sorted the datasets by their size. and plotted the
accuracy of SBPMT, RF and XGboost(100). When the size of a dataset is small of
medium, we observe that SBPMT outperforms RF and XGboost(100). When we have
large number of observations, these three algorithm have similar performance.
This phenomenon provides an evidence that SBPMT is generally good and might be
especially powerful in smaller datasets.

In Figure 4, we sorted the datasets by the ratio of the number of numerical
attributes and the total number of attributese. If some datasets have a same
ratio, they were sorted by the size. Accuracies of SBPMT, RF and XGboost(100)
were given in y-axis. We observe that when features in a dataset are all
numerical, SBPMT is likely to outperform than other methods. One possible
explanation is, we fit a linear model by ProbitBoost at each terminal node of
a CART tree, which would favor numerical attributes. Despite of the complexity
of real world datasets, our results provide an empirical clue that SBPMT may
perform better in datasets with more numerical attributes.

Figure 3: Accuracy of SBPMT,RF and XGboost(100). Datasets are sorted by size
in ascending order (left to right) Figure 4: Accuracy of SBPMT,RF and
XGboost(100) w.r.t the ratio of the number of numerical attributes and the
total number of attributes. Datasets are sorted by size in ascending order if
they have a same ratio.

##  7 Discussion

For now, we have shown the consistency of SBPMT when the iteration number in
AdaBoost part is a function of sample size. Nevertheless, this condition is
not realistic in many cases. For large sample size, it’s time consuming to run
too many rounds of AdaBoost. It’s possible to think about a more general
condition for the consistency of SBPMT. That might be one of future
directions. At the same time, we provides a useful upper bound of the
generalization error of SBPMT by using a latest exponential inequality of
incomplete U-statistics (Maurer (2022)). Inequality in Theorem 3 explains how
subagging helps to improve the performance of ensemble methods. Non-increasing
property of the empirical probit risk function under ProbitBoost suggests us
use large number of boosting iteration for ProbitBoost in PMT. Combining this
result with properties of AdaBoost, we only need to use a relative small
number of AdaBoost iterations in practice to achieve a good performance of
SBPMT. In section 6 we compared the performance of SBPMT with real datasets.
The results demonstrate that SBPMT is competitive with many popular ensemble
learning algorithms, especially for datasets with small and medium sample
size. For datasets whose features are all numerical, there is evidence that
SBPMT outperforms other methods. That would be an interesting direction for
furture research.

Because of the flexity of bagging-boosting type algorithm, we can propose many
other variants of SBPMT. In this paper, we construct a PMT based CART
structure which is simple but sufficient. In literature, there are other
methods to build a decision tree. For example, it’s not necessary to split a
feature space by axis-parallel method. The other way is oblique splitting,
which means we cut the feature space by the linear combination of features.In
the groundwork of Classification And Regression Trees(CART) (Breiman et al.
(1984)), Breiman has already pointed out the idea of splitting the dataset by
the combination of variables. However, the implementation of the algorithm in
finding the optimal hyperplane in feature space has been the real issue for
many years especially for cases involved large dataset. For high-dimensional
case, Breiman et al. (1984) provided a heuristic algorithm CART-LC to find the
relatively good hyperplane. In brief, his method weeds out the unnecessary
variable by a backward deletion process. The least important variable is the
one whose deletion gives the minimal decrease in impurity.

Since the traditional search of optimal hyperplane is likely to stuck in local
optimal points , many stochastic optimization goes to the stage. Heath (1993)
introduced Simulated Annealing Decision Tree (SADT) which uses randomization
to avoid getting trapped in local optimal value of change of impurity
function. The drawback is, the algorithm may evaluate tens of candidates in
order to find the global solution. The use of statistic models hasalso been
explored. Truong (2009) used logistic regression to build oblique trees.
López-Chau et al. (2013) induced oblique trees by Fisher’s linear discriminant
method. Wickramarachchi et al. (2015) applied a geometric method in linear
algebra called Householder transformation in finding optimal oblique
splitting.

Recently, many other strategies have been taken to find optimal oblique
splitting. For example, Bertsimas and Dunn (2017) formulated an integer
programming method to optimize decision trees with fixed depth. Blanquero et
al. (2020) proposed a continuous optimization approach to build sparse optimal
oblique trees. How to employ oblique decision trees with our proposed
subagging-boosting type algorithm is another potential direction of future
research.

Acknowledgments

This work was supported by Lee fellowship in Lehigh University.

## Appendix A. Lemma 1 proof

###### Proof.

Note that

$L(f_{m,n})=1-E[\eta(X)I(f_{m}(X)=1)+(1-\eta(X))I(f_{m}(X)=-1)]$ (19)

$L(g)=1-E[\eta(X)I(g(X)=1)+(1-\eta(X))I(g(X)=-1)]$ (20)

where $I(\cdot)$ is the indicator function.

Let equation (19) minus equation (20), and we obtain

$\begin{split}E[L(f_{m,n})]-L(g^{*})&=L(f_{m,n})-L^{*}=E\bigg{[}(2\eta(X)-1)(I(f_{m}(X)=-1)-I(g^{*}(X)=-1))\bigg{]}\\\
&=E_{(X,Y)\sim\mathcal{P}}\bigg{[}E_{\mathcal{Z}}\bigg{[}\bigg{|}2\eta(X)-1\bigg{|}\bigg{(}I(f_{m}(X)\neq
g^{*}(X)\bigg{)}\bigg{]}\bigg{]}\\\
&=E_{(X,Y)\sim\mathcal{P}}\bigg{[}(1-2\eta(x))I(\eta(x)<1/2)P_{\mathcal{Z}}(f_{m,n}(x)=1)\\\
&+(2\eta(x)-1)I(\eta(x)>1/2)P_{\mathcal{Z}}(f_{m,n}(x)=-1)\bigg{]}\end{split}$
(21)

WLOG, we can assume $\eta(x)>\frac{1}{2}$ for $\mu$-almost all $x$ where $\mu$
is the probability measure w.r.t distribution $\mathcal{P}$. Now equation (21)
becomes

$E[L(f_{m,n})]-L(g^{*})=E_{(X,Y)\sim\mathcal{P}}\bigg{[}(2\eta(X)-1)P_{\mathcal{Z}}(f_{m,n}(X)=-1)\bigg{]}$
(22)

Similarly, we have

$E[L(f_{S_{n},Z_{i}})]-L(g^{*})=E_{(X,Y)\sim\mathcal{P}}\bigg{[}(2\eta(X)-1)P_{\mathcal{Z}}(f_{S_{n},Z_{i}}(X)=-1)\bigg{]}$
(23)

By assumption, $EL(f_{S_{n},Z_{i}})\to L(g^{*})$. Thus we must have
$P_{\mathcal{Z}}(f_{S_{n},Z_{i}}(X)=-1)\to 0$.

For given $x$ s.t $\eta(x)>\frac{1}{2}$, we have

$\begin{split}P_{Z}(f_{m,n}(X)=-1)&=P_{\mathcal{Z}}\bigg{(}\sum_{i=1}^{m}I(f_{S_{n},Z_{i}}(X)=-1)\geq\frac{m}{2}\bigg{)}\\\
&\leq\frac{m}{2}\sum_{i=1}^{m}E_{Z_{i}}[I(f_{S_{n},Z_{i}}(X)=-1)]\\\
&=2P_{\mathcal{Z}}(f_{S_{n},Z_{i}}(X)=-1)\to 0\end{split}$ (24)

It follows that $EL(f_{m,n})\to L(g^{*})$ as well, i.e the voting classifier
is consistent.

∎

## Appendix B. Lemma 2 proof

###### Proof.

To show $Q^{\prime\prime}(x)>0$, we need to perform some calculations
directly. Note that

$Q^{\prime\prime}(x)=\frac{\phi(x)[x\Phi(x)+\phi(x)]}{\Phi^{2}(x)}$ (25)

where $\phi(x)$ is the normal density function.

Recall the fact that $x\Phi(x)+\phi(x)>max(0,x)$ (a simple calculus exercise).
It follows that $Q^{\prime\prime}(x)>0$.

On the other hand, we have:

$Q^{\prime\prime\prime}(x)=\frac{\phi(x)[-(x\Phi(x)+2\phi(x))(x\Phi(x)+\phi(x))+\Phi^{2}(x)]}{\Phi^{3}(x)}$
(26)

It suffices to show
$-(x\Phi(x)+2\phi(x))(x\Phi(x)+\phi(x))+\Phi^{2}(x)<0,\forall x\in R$.

Now denote $-(x\Phi(x)+2\phi(x))(x\Phi(x)+\phi(x))+\Phi^{2}(x)$ as $M(x)$.
When $x\geq 0$, we have

$M^{\prime}(x)=-x^{2}\phi(x)\Phi(x)-2x\Phi^{2}(x)-x\phi^{2}(x)-\phi(x)\Phi(x)\leq
0\quad\text{when $x\geq 0$}$ (27)

But $M(0)=-2+\frac{1}{4}=-\frac{7}{4}<0$, we conclude that $M(x)<0$ when
$x\geq 0$.

When $x$ is positive, we will resort to few useful tail inequalities of normal
distribution functions. By Sampford (1953) and Szarek and Werner (1999), we
have

$1-\Phi(x)<\frac{4\phi(x)}{\sqrt{8+x^{2}}+3x},\quad\text{for $x\geq 0$}$ (28)

When $x<0$, we can replace $x$ in (24) by $-x$, which gives us:

$\Phi(x)<\frac{4\phi(x)}{\sqrt{8+x^{2}}-3x}$ (29)

Next, (29) also implies

$x\Phi(x)+\phi(x)>\phi(x)\bigg{(}\frac{4x}{\sqrt{8+x^{2}}-3x}+1\bigg{)}=\phi(x)\bigg{(}\frac{x+\sqrt{8+x^{2}}}{\sqrt{8+x^{2}}-3x}\bigg{)}$

and

$x\Phi(x)+2\phi(x)>\phi(x)\bigg{(}\frac{4x}{\sqrt{8+x^{2}}-3x}+2\bigg{)}=\phi(x)\bigg{(}\frac{-2x+2\sqrt{8+x^{2}}}{\sqrt{8+x^{2}}-3x}\bigg{)}$

It follows that

$\begin{split}-\bigg{(}x\Phi(x)+2\phi(x)\bigg{)}\bigg{(}x\Phi(x)+\phi(x)\bigg{)}+\Phi^{2}(x)&<-\phi^{2}(x)\bigg{(}\frac{2(x+\sqrt{x^{2}+8})(\sqrt{x^{2}+8}-x)}{(\sqrt{2+x^{2}}-x)^{2}}\bigg{)}\\\
&+\frac{16\phi^{2}(x)}{(\sqrt{8+x^{2}}-3x)^{2}}\\\
&=-\phi^{2}(x)\bigg{(}\frac{2(x^{2}+8-x^{2})-16}{(\sqrt{2+x^{2}}-x)^{2}}\bigg{)}=0,\quad\text{for
$x<0$}\end{split}$ (30)

Thus $Q^{\prime\prime\prime}(x)<0,\forall x\in R$.

∎

## Appendix C. Lemma 3 proof

###### Proof.

By Taylor expansion of $P_{n}(f^{t})$ in direction of $g^{t}$, we have

$\begin{split}P_{n}(f^{t})&=P_{n}(f^{t}+g^{t})-P_{n}^{\prime}(f^{t}+g^{t});g^{t})+\frac{1}{2}P_{n}^{\prime\prime}(\tilde{f}^{t+1};g^{t})\quad\text{(where
$\tilde{f}^{t+1}=f^{t}+\alpha_{t}g^{t}$, $\alpha_{t}\in(0,1)$ )}\\\
&=P_{n}(f^{t+1})-P_{n}^{\prime}(f^{t}+g^{t})\cdot
g^{t}+\frac{1}{2}P_{n}^{\prime\prime}(\tilde{f}^{t})\cdot(g^{t})^{2}\quad\text{(where
"$\cdot$" represents inner product)}\\\
&=P_{n}(f^{t+1})-\bigg{(}P_{n}^{\prime}(f^{t}+g^{t})-P_{n}^{\prime}(f^{t})+P_{n}^{\prime}(f^{t})\bigg{)}\cdot
g^{t}+\frac{1}{2}P_{n}^{\prime\prime}(\tilde{f}^{t})\cdot(g^{t})^{2}\end{split}$
(31)

Perform Taylor expansion of $P_{n}^{\prime}(F_{t}+f_{t})$ one more time, and
we obtain

$\begin{split}P_{n}^{\prime}(f^{t}+g^{t})&=P_{n}^{\prime}(f^{t})+P_{n}^{\prime\prime}(f^{t})\cdot
g^{t}+\frac{1}{2}P_{n}^{\prime\prime\prime}(\hat{f}^{t+1})\cdot(g^{t})^{2}\quad\text{(where
$\hat{f}^{t+1}=f^{t}+\alpha_{t}^{\prime}g^{t}$, $\alpha_{t}^{\prime}\in(0,1)$
)}\\\ \end{split}$ (32)

By Lemma 2, we have

$P_{n}^{\prime}(f^{t+1})<P_{n}^{\prime}(f^{t})+P_{n}^{\prime\prime}(f^{t})\cdot
g^{t}$

Under the notations of WLS in section 3.2, we can derive the following
equation by the property of WLS:

$\sum_{i=1}^{n}w_{i}(\hat{a}_{s(t)}x_{s(t),i}+\hat{b}_{s(t)})(z_{i}-\hat{a}_{s(t)}x_{s(t),i}-\hat{b}_{s(t)})=0$

which is equivalent to the following useful identity

$-P_{n}^{\prime}(f^{t})\cdot
g^{t}=P_{n}^{\prime\prime}(f^{t})\cdot(g^{t})^{2}$

It follows that

$\begin{split}P_{n}(f^{t})&>P_{n}(f^{t+1})-\bigg{(}P_{n}^{\prime\prime}(f^{t})\cdot(g^{t})^{2}+P_{n}^{\prime}(f^{t})\cdot
g^{t}\bigg{)}+\frac{1}{2}P_{n}^{\prime\prime}(\tilde{f}^{t})\cdot(g^{t})^{2}\\\
&>P_{n}(f^{t+1})-\bigg{(}P_{n}^{\prime\prime}(f^{t})\cdot(g^{t})^{2}+P_{n}^{\prime}(f^{t})\cdot
g^{t}\bigg{)}+\frac{1}{2}\gamma||g^{t}||^{2}\\\
&=P_{n}(f^{t+1})+\frac{1}{2}\gamma||g^{t}||^{2}\end{split}$ (33)

All other conclusions can be derived from inequality (33). ∎

## Appendix D. Theorem 3 proof

###### Proof.

Note that

$\begin{split}P(g(f_{M,n,t}(X))\neq
Y)&=P\bigg{(}\bigg{(}\frac{1}{M}\sum_{i=1}^{M}f_{Z_{i},\lfloor\alpha
n\rfloor,t}(X)\bigg{)}\cdot Y\bigg{)}\leq 0)\\\
&=P\bigg{(}\sum_{i=1}^{M}T_{i}\geq\lceil\frac{M}{2}\rceil\bigg{)}\\\
&=P\bigg{(}\frac{\sum_{i=1}^{M}K_{i}}{M}\geq\frac{\lceil\frac{M}{2}\rceil-\frac{M}{2}}{M}\bigg{)}\end{split}$
(34)

where $T_{i}=I(f_{Z_{i},\lfloor\alpha n\rfloor,t}(X)\cdot Y\leq
0),K_{i}=2T_{i}-1$ for $i=1,2,...,M$. Note that $T_{i}$ are dependent with
each other by the natural of subagging. And it’s easy to see that
$\frac{\sum_{i=1}^{M}K_{i}}{M}$ is actually an incomplete U-statistic whose
range is $\\{-1,1\\}$.

In addition, $P(f_{Z_{i},\lfloor\alpha n\rfloor,t}(X)\cdot Y\leq 0)$ are the
same for all $i=1,2,...,m$ because that the original $n$ observations are
i.i.d by assumption. Thus we can set $P(f_{Z_{i},\lfloor\alpha
n\rfloor,t}(X)\cdot Y\leq 0)=p_{sub}$ for $i=1,2,...,M$. It follows that
$\theta=E[\frac{\sum_{i=1}^{M}K_{i}}{M}]=E[K_{i}]=2p_{sub}-1$ and (17) can be
further written as

$P(g(f_{M,n,t}(X))\neq
Y)=P\bigg{(}\frac{\sum_{i=1}^{M}K_{i}}{M}-(2p_{sub}-1)\geq\frac{\lceil\frac{M}{2}\rceil-\frac{M}{2}}{M}-(2p_{sub}-1)\bigg{)}$
(35)

Because of the dependency among $K_{i}$, many bounding inequalities such as
Hoeffding inquality can’t be applied directly. Eventhough Pelekis and Ramon
(2017) and Impagliazzo and Kabanets (2010) provided a Hoeffding’ inequality
for the sum of dependent random variables, the conditions required by their
results are hard to check in our case. Fortunately, Maurer (2022) gave a
useful concentration bound for the incomplete U-statistic with finite sample
size. Before we use that, we borrow few notations and conventions in Maurer’s
work.

Let $K:\mathcal{X}^{m}\to\mathbb{R}$ be a measurable, symmetric,bounded kernel
where the integer $m$ is called degree of kernel $K$.
$\theta=\theta(\mu)=E[K(X_{1},...,X_{m})]$ from a sample
$\mathbf{X}=(X_{1},...,X_{n})\sim\mu^{n}$, where $n$ is the number of
independent observations.
$\mathcal{D}=(D_{1},...,D_{M})\in\\{D\subset[n]:|D|=m\\}^{M}$ is a sequence of
$M$ subsets of $\\{1,2,...,n\\}$ with cardinality $m$ and this sequence
$\mathcal{D}$ is called the design (Kong and Zheng (2021)). Then the
incomplete $U$-statistic is defined as

$U_{\mathcal{D}}(\mathbf{X})=\frac{1}{M}\sum_{i=1}^{M}K(\mathbf{X}^{D_{i}})$

where $K(\mathbf{X}^{D_{i}})=K(X_{i_{1}},...,X_{i_{m}})$.

Under subagging, sequence $\mathcal{D}=(D_{1},...,D_{M})$ is actually sampled
with replacement from the uniform distribution on $\\{D\subset[n]:|D|=m\\}$
and number $M$ is the subagging times or the number of subaged classifier we
use.

Given a design $\mathcal{D}=(D_{1},...,D_{M})\in\\{D\subset[n]:|D|=m\\}^{M}$
and $k,l\in\\{1,2,...,n\\},k\neq l$, we define

$\displaystyle\begin{split}R_{k}(\mathcal{D})&=|\\{i:k\in D_{i}\\}|,\quad
R_{kl}=|\\{i:k,l\in D_{i}\\}|\quad\text{where $i\in\\{1,2,...,m\\}$}.\\\
A(\mathcal{D})&=\sum_{k=1}^{n}\frac{R_{k}^{2}(\mathcal{D})}{M^{2}},\quad
B(\mathcal{D})=\sum_{k\neq l}^{n}\frac{R_{kl}^{2}(\mathcal{D})}{M^{2}}\\\
C(\mathcal{D})&=\max_{k}\frac{R_{k}}{M}\end{split}$ (36)

One the other hand, for a bounded kernel $K:\mathcal{X}^{m}\to[-1,1]$ and
$X_{1},...,X_{m},X_{1}^{\prime},X_{2}^{\prime}$ i.i.d with domain
$\mathcal{X}$, we define

$\displaystyle\begin{split}\beta(K)&=E\bigg{[}\bigg{(}V^{1}_{X_{1},X_{1}^{\prime}}V^{2}_{X_{2},X_{2}^{\prime}}K(X_{1},,...,X_{m})^{2}\bigg{)}\bigg{]}\\\
\gamma(K)&=\sup_{\mathbf{x}\in\mathcal{X}^{m},y,y^{\prime}\in\mathcal{X}}E\bigg{[}\bigg{(}V^{1}_{y,y^{\prime}}V^{2}_{X_{2},X_{2}^{\prime}}K(x_{1},,...,x_{m})^{2}\bigg{)}\bigg{]}\\\
\alpha(K)&=\bigg{(}\sqrt{\beta(K)/2}+\sqrt{\gamma(K)}\bigg{)}\end{split}$ (37)

We will omit the dependency of design $\mathcal{D}$ and kernel $K$ when there
is no ambiguity.

Then we are ready to give the concentration bound w.r.t incomplete
$U$-statistics.

######  Bernstein-type inequality for incomplete U-statistics (Maurer (2022)).

For fixed kernel $K$ with values in $[-1,1]$, design $\mathcal{D}$ and $t>0$,

$P\bigg{(}U_{\mathcal{D}}(\mathbf{X})-\theta>t\bigg{)}\leq
exp\bigg{(}\frac{-t^{2}}{2A\sigma_{1}^{2}+B\beta/2+(\sqrt{B\gamma}+4C/3)t}\bigg{)}$
(38)

Notice that in our case, we have
$U_{\mathcal{D}}(\mathbf{X})=\frac{1}{M}\sum_{i=1}^{M}K(\mathbf{X}^{D_{i}})=\frac{1}{M}\sum_{i=1}^{M}K_{i},\theta=2p_{sub}-1$.
We can assume $p_{sub}<\frac{1}{2}$ which means we require that the error
probability of subbagged classifier is not higher than $\frac{1}{2}$. In
generally this assumption makes sense since each of them are Adaboosted
classifier which should have better performance.

Given fixed subbagged samplings (or desgin) $\mathcal{D}$, we now have

$P(g(f_{M,n,t}(X))\neq Y|\mathcal{D})\leq exp\bigg{(}\frac{-(\frac{\lceil
M/2\rceil-M/2}{M}+1-2p_{sub})^{2}}{2A\sigma_{1}^{2}+B\beta/2+(\sqrt{B\gamma}+4C/3)(\frac{\lceil
M/2\rceil-M/2}{M}+1-2p_{sub})}\bigg{)}$ (39)

If the design becomes random, i.e $\mathcal{D}=(D_{1},...,D_{M})$ is sampled
with replacement from the uniform distribution of $\\{D\subset[n]:|D|=m\\}$
and is independent of original dataset $\mathbf{X}$, then quantities in (36)
are all random variables.

Denote the events $E_{A},E_{B},E_{C}$ as following:

$\displaystyle\begin{split}E_{A}&=\bigg{\\{}\mathcal{D}\in\\{D\subset[n]:|D|=m\\}^{M}:\sqrt{A(\mathcal{D})}>\sqrt{\frac{m^{2}}{n}}+(1+4\sqrt{ln(3/\delta)}\sqrt{\frac{m}{M}}\bigg{\\}}\\\
E_{B}&=\bigg{\\{}\mathcal{D}\in\\{D\subset[n]:|D|=m\\}^{M}:\sqrt{B(\mathcal{D})}>\frac{m^{2}}{n}+(1+4\sqrt{ln(3/\delta)}\frac{m}{\sqrt{M}}\bigg{\\}}\\\
E_{C}&=\bigg{\\{}\mathcal{D}\in\\{D\subset[n]:|D|=m\\}^{M}:C(\mathcal{D})>\frac{m}{n}+\frac{\sqrt{2m}+3}{\sqrt{M}}ln(3/\delta)\bigg{\\}}\\\
\end{split}$ (40)

According to Lemma 4.5 and Lemma 4.9 in (Maurer (2022)), for $\delta>0$ and
$\sqrt{M}>ln(n)$, we have

$P(E_{A})\leq\frac{\delta}{3},P(E_{B})\leq\frac{\delta}{3},\quad\text{and}\quad
P(E_{C})\leq\frac{\delta}{3}$

It follows that with probability (where randomness comes from the subagging
process) at least $1-\delta$ we have:

$P_{\mathcal{P}}(g(f_{M,n,T}(\mathbf{X}))\neq Y)\leq
exp\bigg{(}\frac{-(\frac{\lceil
M/2\rceil-M/2}{M}+1-2p_{\text{sub}})^{2}}{2Q_{A}^{2}\sigma_{1}^{2}+Q_{B}^{2}\beta/2+(\sqrt{Q_{B}\gamma}+4Q_{C}^{2}/3)(\frac{\lceil
M/2\rceil-M/2}{M}+1-2p_{\text{sub}})}\bigg{)}$ (41)

∎

## Appendix E. Theorem 6 proof

###### Proof.

The proof simply combines Lemma 3, Theorem 4, Theorem 5 and the fact that
hypothesis space consisting of PMTs has finite VC-dimension. According to
Theorem 4, it suffices to show

$P_{S}(YF(X)\leq 0)\leq exp\bigg{(}-2\sum_{t=1}^{T}\gamma_{t}^{2}(B)\bigg{)}$

Suppose the given training set is $\\{(\mathbf{x}_{i},y_{i})_{i=1}^{n}\\}$ and
the fitted classifier after $T$ rounds of AdaBoost is

$F(\mathbf{x})=\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{x})$

Suppose $f_{t}$ is a PMT fitted at $t$-th step of AdaBoost, we can rewrite
$f_{t}$ as defined in section 3.5:

$f_{t}(\mathbf{x}_{i})=\sum_{a\in A^{t}}sign[G_{a}^{t,B}(\mathbf{x}_{i})]\cdot
I(\mathbf{x}_{i}\in S_{a}^{t}))$

where $\\{S_{a}^{t}\\}_{a\in A^{t}}$ is a set of partitioned feature space
determined by the CART decision tree structure at $t$-th step of AdaBoost and
$A^{t}$ is the corresponding index set of partitioned space. $G_{a}^{t,B}$ is
an fitted ProbitBoost model associated with the partition $S_{a}^{t}$ where
$B$ represents the iteration times of ProbitBoost .

With the definition of weighted training error $\varepsilon_{t}$, we can
derive the following inequality:

$\begin{split}\varepsilon_{t}&=\sum_{i=1}^{n}w_{t}(i)\mathbf{1}\\{f_{t}(\mathbf{x}_{i})\neq
y_{i}\\}\\\ &=\sum_{i=1}^{n}w_{t}(i)\mathbf{1}\\{y_{i}\cdot\sum_{a\in
A^{t}}sign[G_{a}^{t,B}(\mathbf{x}_{i})]\cdot\mathbf{1}\\{\mathbf{x}_{i}\in
S_{a}^{t}\\}\leq 0\\}\\\ &=\sum_{a\in
A^{t}}\sum_{i=1}^{n}w_{t}(i)\mathbf{1}\\{\mathbf{x}_{i}\in
S_{a}^{t}\\}\mathbf{1}\\{y_{i}G_{a}^{t,B}(\mathbf{x}_{i})\leq 0\\}\\\
&\leq\sum_{a\in A^{t}}\sum_{i=1}^{n}w_{t}(i)\mathbf{1}\\{\mathbf{x}_{i}\in
S_{a}^{t}\\}\frac{-ln(y_{i}G_{a}^{t,B}(\mathbf{x}_{i}))}{ln2}\\\ &=\sum_{a\in
A^{t}}\sum_{\mathbf{x}_{i}\in
S_{a}^{t}}w_{t}(i)\frac{-ln(y_{i}G_{a}^{t,B}(\mathbf{x}_{i}))}{ln2}\overset{\mathrm{def}}{=\joinrel=}\frac{\varepsilon_{t}^{P}(B)}{ln(2)}\end{split}$
(42)

By assumption, we have $\frac{\varepsilon_{t}^{P}(B)}{ln(2)}<\frac{1}{2}$ for
$t=1,2,...,T$. By Theorem 5, it follows that

$\begin{split}P_{S}(YF(X)\leq 0)&\leq
2^{T}\prod_{t=1}^{T}\sqrt{\varepsilon_{t}(1-\varepsilon_{t})}\leq
2^{T}\prod_{t=1}^{T}\sqrt{\frac{\varepsilon_{t}^{P}(B)}{ln(2)}\bigg{(}1-\frac{\varepsilon_{t}^{P}(B)}{ln(2)}\bigg{)}}\\\
&=\prod_{t=1}^{T}\sqrt{1-4(\gamma_{t}^{P}(B))^{2}}\\\ &\leq
exp\bigg{(}-2\sum_{t=1}^{T}(\gamma_{t}^{P}(B))^{2}\bigg{)}\end{split}$ (43)

where $\gamma_{t}^{P}(B)=\frac{1}{2}-\frac{\varepsilon_{t}^{P}(B)}{ln(2)}$. ∎

## References

  * Mease and Wyner [2008] David Mease and Abraham Wyner.  Evidence contrary to the statistical view of boosting.  _J. Mach. Learn. Res._ , 9:131–156, jun 2008.  ISSN 1532-4435.
  * Breiman [2004] L. Breiman.  Bagging predictors.  _Machine Learning_ , 24:123–140, 2004.
  * Ho [1995] Tin Kam Ho.  Random decision forests.  In _Proceedings of 3rd International Conference on Document Analysis and Recognition_ , volume 1, pages 278–282 vol.1, 1995.  doi:10.1109/ICDAR.1995.598994.
  * Freund and Schapire [1997] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of Computer and System Sciences_ , 55(1):119–139, 1997.  ISSN 0022-0000.  doi:https://doi.org/10.1006/jcss.1997.1504.  URL https://www.sciencedirect.com/science/article/pii/S002200009791504X.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, page 785–794, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450342322.  doi:10.1145/2939672.2939785.  URL https://doi.org/10.1145/2939672.2939785.
  * Breiman [2001] Leo Breiman.  Using iterated bagging to debias regressions.  _Machine Learning_ , 45:261–277, 12 2001.  doi:10.1023/A:1017934522171.
  * Friedman [2002] Jerome H. Friedman.  Stochastic gradient boosting.  _Comput. Stat. Data Anal._ , 38(4):367–378, feb 2002.  ISSN 0167-9473.  doi:10.1016/S0167-9473(01)00065-2.  URL https://doi.org/10.1016/S0167-9473(01)00065-2.
  * Mishina et al. [2014] Yohei Mishina, Masamitsu Tsuchiya, and Hironobu Fujiyoshi.  Boosted random forest.  In _2014 International Conference on Computer Vision Theory and Applications (VISAPP)_ , volume 2, pages 594–598, 2014.
  * Ghosal and Hooker [2021] Indrayudh Ghosal and Giles Hooker.  Boosting random forests to reduce bias; one-step boosted forest and its variance estimate.  _Journal of Computational and Graphical Statistics_ , 30(2):493–502, 2021.  doi:10.1080/10618600.2020.1820345.  URL https://doi.org/10.1080/10618600.2020.1820345.
  * Friedman et al. [2000a] Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  Additive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors).  _The Annals of Statistics_ , 28(2):337 – 407, 2000a.  doi:10.1214/aos/1016218223.  URL https://doi.org/10.1214/aos/1016218223.
  * Landwehr et al. [2005] Niels Landwehr, Mark Hall, and Eibe Frank.  Logistic model trees.  _Machine Learning_ , 59(1):161–205, 2005.  ISSN 1573-0565.  doi:10.1007/s10994-005-0466-3.  URL https://doi.org/10.1007/s10994-005-0466-3.
  * Zheng and Liu [2012] Songfeng Zheng and Weixiang Liu.  Functional gradient ascent for probit regression.  _Pattern Recognition_ , 45(12):4428–4437, 2012.  ISSN 0031-3203.  doi:https://doi.org/10.1016/j.patcog.2012.06.006.  URL https://www.sciencedirect.com/science/article/pii/S0031320312002762.
  * Ostroumova et al. [2017] Liudmila Ostroumova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin.  Catboost: unbiased boosting with categorical features.  In _Neural Information Processing Systems_ , 2017.
  * Ke et al. [2017] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu.  Lightgbm: A highly efficient gradient boosting decision tree.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf.
  * Friedman et al. [2000b] Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  Additive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors).  _The Annals of Statistics_ , 28(2):337 – 407, 2000b.  doi:10.1214/aos/1016218223.  URL https://doi.org/10.1214/aos/1016218223.
  * Dettling and Bühlmann [2003] Marcel Dettling and Peter Bühlmann.  Boosting for tumor classification with gene expression data.  _Bioinformatics (Oxford, England)_ , 19:1061–9, 07 2003.  doi:10.1093/bioinformatics/btf867.
  * Schmid et al. [2013] Matthias Schmid, Florian Wickler, Kelly O. Maloney, Richard Mitchell, Nora Fenske, and Andreas Mayr.  Boosted beta regression.  _PLOS ONE_ , 8(4):1–15, 04 2013.  doi:10.1371/journal.pone.0061623.  URL https://doi.org/10.1371/journal.pone.0061623.
  * Büchlmann and Yu [2002] Peter Büchlmann and Bin Yu.  Analyzing bagging.  _The Annals of Statistics_ , 30(4):927–961, 2002.  ISSN 00905364.  URL http://www.jstor.org/stable/1558692.
  * Kong and Zheng [2021] Xiangshun Kong and Wei Zheng.  Design based incomplete u-statistics.  _Statistica Sinica_ , 31(3):pp. 1593–1618, 2021.  ISSN 10170405, 19968507.  URL https://www.jstor.org/stable/27034832.
  * Hastie et al. [2009] Trevor J. Hastie, Saharon Rosset, Ji Zhu, and Hui Zou.  Multi-class adaboost.  _Statistics and Its Interface_ , 2:349–360, 2009.
  * Gao et al. [2022] Wei Gao, Fan Xu, and Zhi-Hua Zhou.  Towards convergence rate analysis of random forests for classification.  _Artificial Intelligence_ , 313:103788, 2022.  ISSN 0004-3702.  doi:https://doi.org/10.1016/j.artint.2022.103788.  URL https://www.sciencedirect.com/science/article/pii/S000437022200128X.
  * Scornet et al. [2015] Erwan Scornet, Gérard Biau, and Jean-Philippe Vert.  Consistency of random forests.  _The Annals of Statistics_ , 43(4):1716 – 1741, 2015.  doi:10.1214/15-AOS1321.  URL https://doi.org/10.1214/15-AOS1321.
  * Bartlett and Traskin [2007] Peter L. Bartlett and Mikhail Traskin.  Adaboost is consistent.  _Journal of Machine Learning Research_ , 8(78):2347–2368, 2007.  URL http://jmlr.org/papers/v8/bartlett07b.html.
  * Devroye et al. [1996] Luc Devroye, László Györfi, and Gábor Lugosi.  A probabilistic theory of pattern recognition.  In _Stochastic Modelling and Applied Probability_ , 1996.
  * Leboeuf et al. [2020] Jean-Samuel Leboeuf, Frédéric LeBlanc, and Mario Marchand.  Decision trees as partitioning machines to characterize their generalization properties.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 18135–18145. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/d2a10b0bd670e442b1d3caa3fbf9e695-Paper.pdf.
  * Schapire and Freund [2012] Robert E. Schapire and Yoav Freund.  _Boosting: Foundations and Algorithms_.  The MIT Press, 05 2012.  ISBN 9780262301183.  doi:10.7551/mitpress/8291.001.0001.  URL https://doi.org/10.7551/mitpress/8291.001.0001.
  * Schapire et al. [1998] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee.  Boosting the margin: A new explanation for the effectiveness of voting methods.  _The Annals of Statistics_ , 26(5):1651–1686, 1998.  ISSN 00905364.  URL http://www.jstor.org/stable/120016.
  * Gao and Zhou [2013] Wei Gao and Zhi-Hua Zhou.  On the doubt about margin explanation of boosting.  _Artificial Intelligence_ , 203:1–18, 2013.  ISSN 0004-3702.  doi:https://doi.org/10.1016/j.artint.2013.07.002.  URL https://www.sciencedirect.com/science/article/pii/S0004370213000684.
  * [29] Markelle Kelly, Rachel Longjohn, and Kolby Nottingham.  The uci machine learning repository.  https://archive.ics.uci.edu.
  * Maurer [2022] Andreas Maurer.  Exponential finite sample bounds for incomplete u-statistics.  _arXiv preprint arXiv:2207.03136_ , 2022.
  * Breiman et al. [1984] L. Breiman, Jerome H. Friedman, Richard A. Olshen, and C. J. Stone.  Classification and regression trees.  1984\.
  * Heath [1993] David George Heath.  _A Geometric Framework for Machine Learning_.  PhD thesis, Johns Hopkins University, USA, 1993.  UMI Order No. GAX93-13375.
  * Truong [2009] Alfred Kar Yin Truong.  Fast growing and interpretable oblique trees via logistic regression models.  2009\.
  * López-Chau et al. [2013] Asdrúbal López-Chau, Jair Cervantes, Lourdes López-García, and Farid García Lamont.  Fisher’s decision tree.  _Expert Systems with Applications_ , 40(16):6283–6291, 2013.  ISSN 0957-4174.  doi:https://doi.org/10.1016/j.eswa.2013.05.044.  URL https://www.sciencedirect.com/science/article/pii/S0957417413003424.
  * Wickramarachchi et al. [2015] Darshana Chitraka Wickramarachchi, Blair Lennon Robertson, Marco Reale, Christopher John Price, and J. Brown.  Hhcart: An oblique decision tree.  _Comput. Stat. Data Anal._ , 96:12–23, 2015.  URL https://api.semanticscholar.org/CorpusID:16947789.
  * Bertsimas and Dunn [2017] Dimitris Bertsimas and Jack Dunn.  Optimal classification trees.  _Machine Learning_ , 106(7):1039–1082, 2017.  ISSN 1573-0565.  doi:10.1007/s10994-017-5633-9.  URL https://doi.org/10.1007/s10994-017-5633-9.
  * Blanquero et al. [2020] Rafael Blanquero, Emilio Carrizosa, Cristina Molero-Río, and Dolores Romero Morales.  Sparsity in optimal randomized classification trees.  _European Journal of Operational Research_ , 284(1):255–272, 2020.  ISSN 0377-2217.  doi:https://doi.org/10.1016/j.ejor.2019.12.002.  URL https://www.sciencedirect.com/science/article/pii/S0377221719309865.
  * Sampford [1953] M. R. Sampford.  Some Inequalities on Mill’s Ratio and Related Functions.  _The Annals of Mathematical Statistics_ , 24(1):130 – 132, 1953.  doi:10.1214/aoms/1177729093.  URL https://doi.org/10.1214/aoms/1177729093.
  * Szarek and Werner [1999] Stanislaw J. Szarek and Elisabeth Werner.  A nonsymmetric correlation inequality for gaussian measure.  _Journal of Multivariate Analysis_ , 68(2):193–211, 1999.  ISSN 0047-259X.  doi:https://doi.org/10.1006/jmva.1998.1784.  URL https://www.sciencedirect.com/science/article/pii/S0047259X98917845.
  * Pelekis and Ramon [2017] Christos Pelekis and Jan Ramon.  Hoeffding’s inequality for sums of dependent random variables.  _Mediterranean Journal of Mathematics_ , 14(6):243, 2017.  ISSN 1660-5454.  doi:10.1007/s00009-017-1043-2.  URL https://doi.org/10.1007/s00009-017-1043-2.
  * Impagliazzo and Kabanets [2010] Russell Impagliazzo and Valentine Kabanets.  Constructive proofs of concentration bounds.  In Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim, editors, _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ , pages 617–631, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.  ISBN 978-3-642-15369-3.