Uncertainty in Gradient Boosting via Ensembles
Authors: Andrey Malinin
Liudmila Prokhorenkova
Aleksei Ustimenko
Venue: ICLR 2021 Poster (2021)
Keywords: uncertainty
ensembles
gradient boosting
decision trees
knowledge uncertainty

Abstract: For many practical, high-risk applications, it is essential to quantify uncertainty in a model's predictions to avoid costly mistakes. While predictive uncertainty is widely studied for neural networks, the topic seems to be under-explored for models based on gradient boosting. However, gradient boosting often achieves state-of-the-art results on tabular data. This work examines a probabilistic ensemble-based framework for deriving uncertainty estimates in the predictions of gradient boosting classification and regression models. We conducted experiments on a range of synthetic and real datasets and investigated the applicability of ensemble approaches to gradient boosting models that are themselves ensembles of decision trees. Our analysis shows that ensembles of gradient boosting models successfully detect anomalous inputs while having limited ability to improve the predicted total uncertainty. Importantly, we also propose a concept of a virtual ensemble to get the benefits of an ensemble via only one gradient boosting model, which significantly reduces complexity. 

Published as a conference paper at ICLR 2021
UNCERTAINTY IN GRADIENT BOOSTING VIA ENSEMBLES
Andrey Malinin" Yandex; HSE University Moscow, Russia am969@yandex-teem. rv
Liudmila Prokhorenkova'
Yandex; HSE University;
Moscow Institute of Physics and Technology
Moscow, Russia
ost verrroooolllaaandeaee
Aleksei Ustimenko"
Yandex
Moscow, Russia aust meekkmmyadddeeeteeaaaa ru
ABSTRACT
For many practical, high-risk upplications, it is essential to quantify uncertainty in a model's predictions to avoid costly mistakes. While predictive uncertainty is widely studied for neural networks, the topie seems to under-explored for mod- els based gradient boosting. However, gradient boosting often achieves state- of-the-art results on tabular data. This work examines a probabilistic ensemble- based framework for deriving uncertainty estimates in the predictions of gradient boosting classification and regression models. We conducted experiments on a range of synthetic and real datasets and investigated the applicability of ensemble approaches to gradient boosting models that are themselves ensembles of decision trees. Our analysis shows that ensembles of gradient boosting models successfully detect anomalous inputs while having limited ability to improve the predicted total uncertainty. Importantly, we also propose a concept of a virtual ensemble get the benefits of an ensemble via only one gradient boosting model, which signifi- cantly reduces complexity.
INTRODUCTION
Gradient boosting (riedman 2001) a widely used machine learning algorithm that achieves state-
of-the-art results on tasks containing heterogeneous features, complex dependencies, and noisy data: web search, recommendation systems, weather forecasting, and many others (Burges, 2011 Care
ana Niculescu-Mrzil, 2006; Kıchardson et all 2001: Roe all 2003: Wu et all 2010: Zhang
& Haghani, 2015). Gradient boosting based on decision trees (GBDT) underlies such well-known libraries like XGBoost, LightGBM, and CatBoost. In this paper, we investigate the estimation of pre- dictive uncertainty in GBDT models. Uncertainty estimation is crucial for avoiding costly mistakes high-risk applications, such as autonomous driving, medical diagnostics, and financial forecasting. For example, in self-driving cars, it is necessary to know when the Al-pilot is confident in its ability to drive and when it is not to avoid a fatal collision. In financial forecasting and medical diagnostics, diagnostic system could either lead large financial
mistakes the part of an AI forecasting or reputational loss or to the loss of life. Crucially, both financial and medical data are often repre- sented in heterogeneous tabular form data which GBDTs are typically applied, highlighting the relevance of our work on obtaining uncertainty estimates for GBDT models.
Approximate Bayesian approaches for uncertainty estimation have been extensively studied for neu- ral network models (Gal, 2016 Malinin, 2019). Bayesian methods for tree-based models (Chipman all 2010: Linerd 201 have also been widely studied the literature. However, this research did not explicitly focus on studying uncertainty estimation and its applications. Some related work was
'll authors contributed equally and are listed in alphabetical order.

---

Published as a conference paper at ICLR 2021
done by Coulston al (2016); Shaker & Hillermeiet (202)) who examined quantifying predic- tive uncertainty for random forests. However, the area has been otherwise relatively under-explored, especially for GBDT models that are widely used in practice and known to outperform other ap- proaches based on tree ensembles.
While for classification problems GDBT models already return distribution over class labels, for regression tasks they typically yield only point predictions. Recently, this problem was addressed in the NGBoost algorithm (Duan all 2021), where GBDT model trained to return the mean and variance of a normal distribution over the target variable for given feature vector. However, such models only capture data uncertainty (Gal, 2016; Mahnin 2019), also known as aleatoric un- certainty, which arises due to inherent class overlap or noise in the data. However, this does not quantify uncertainty due to the model's 's inherent lack of knowledge about inputs from regions either far from the training data or sparsely covered by it, known as knowledge uncertainty, or epistemic un- certainty Laa 20TG. Malnn 2012). One class of approaches for capturing knowledge uncertainty are Bayesian ensemble methods, which have recently become popular for estimating predictive un- certainty in neural networks (Depeweg et al., 2017: Gal & Ghahramani, 2016; KKndaal et all, 2018: Lakshmmnarayana et all 20L2; Maddox et all 2019 Smith & Gal, 2018). A key feature of ensem- ble approaches is that they allow overall uncertainty to be decomposed into data uncertainty and knowledge uncertainty within interpretable probabilistic framework (Dpewee et all 2017; Gal, 2016; Malinin, 2019). Ensembles are also known to yield improvements in predictive performance.
This work examines ensemble-based uncertainty-esiimation for GBDT models. The contributions are as follows. First, we consider generating ensembles using both classical Stochastic Gra- dient Boosting (SGB) as well as the recently proposed Stochastic Gradient Langevin Boosting (SGLB) (Ustumenko & Prokhorenkova. (020). Importantly, SGLB allows us to guarantee that the models are asymptotically sampled from a true Bayesian posterior. Second, we show that using SGLB we can construct virtual ensemble using only one gradient boosting model, significantly re- ducing the computational complexity. Third, to understand the attributes of using ensembles- uncertainty estimation in GBDT models, we conduct extensive analysis on several synthetic datasets. Finally, we evaluate the proposed approach on a range of real regression and classification datasets. Our results show that this approach successfully enables the detection of anomalous out-of-domain inputs. Importantly, our solution is easy to combine with any implementation of GBDT. Our meth- ods have been implemented within the open-source CatBoost library. The code of our experiments is publicly
rew.eeereeeahhhhee -tt. at ota.aaatt.aaaaaaoooooooooaaaaaar
2 PRELIMINARIES
Uncertainty Estimation via Bayesian Ensembles In this work we consider uncertainty estima- tion within the standard Bayesian ensemble-based framework (Gal, 2016; Iaaini, 2019). Here, model parameters are considered random variables and prior p(0) is placed over them to com- pute posterior DD) via Bayes' rule:
P(O P(D)0))(() P(D)
J ) is the training dataset. Each set of parameters can be considered hypothesis or explanation about how the world works. Samples from the posterior should yield explanations consistent with the observations of the world contained within the training data D. However, on data far from 'D each set of parameters can yield different predictions. Therefore, estimates of knowledge uncertainty can be obtained by examining the diversity of predictions.
where D - (1)
Consider an ensemble of probabilistic models {P(y]æ;; )(m)) M- sampled from the posterior D). Each model P(y) ar, ((m)) yields different estimate of data uncertainty, represented by the entropy of its predictive distribution (Malnun, 2019). Uncertainty in predictions due to knowl- edge uncertainty expressed as the level of spread, or "disagreement", of models in the ensem- ble (Malinin, 2019). Note that exact Bayesian inference is often intractable, and it is common to consider either an explicit or implicit approximation (0)) to the true posterior p(O(D). While a range of approximations has been explored for neural network models (Gal & Ghahramant, 2016: Lakshmmnaayanan el all POLZ: Maddox et all 2019) !|
to the best of our knowledge, limited work
A full overview is available in AAsukka atall X020 Ovadia ctall 201))
2

---

Published as a conference paper at ICLR 2021
has explored Bayesian inference for gradient- boosstd trees. Given p(0 the predictive posterior of the ensemble is obtained by taking the expectation with respect to the models the ensemble:
M
P(yla æ. D) = p) P(ul 0)]
~
Σ m==
(lyl=00m))
0 ((m)) p(0DD).
(2)
M
The entropy of the predictive posterior estimates total uncertainty in predictions:
H( D)] Bp(yla,D) In P(yla,, D)J
Total uncertainty is due to both data uncertainty and knowledge uncertainty. However, in applica- tions like active learning (Karsch et all 20T9) and out-of-domain detection is desirable to estimate knowledge uncertainty separately. The sources of uncertainty be decomposed by considering the mutual information between the parameters 0 and the prediction y (Depeweg et all 2017):
I [ 0 x D = [[ D)] - Ep(ol D)) HH[P(v) (y/ x 0)]
Knowlodge Uncertainty
Total Uncertainty
Expected Uncertainty
(4)
H
P (())) M
(())
1
(
M
m=1
This is expressed as the difference between the entropy of the predictive posterior, a measure of total uncertainty, and the expected entropy of each model in the ensemble, a measure of expected data uncertainty. Their difference is a measure of ensemble diversity and estimates knowledge uncertainty.
Unfortunately, when considering ensembles of probabilistic regression models {p(u) x: ((m))) } over continuous-valus target y I. it is no longer possible to obtain tractable estimates of the (differential) entropy of the predictive posterior, and, by extension, mutual information. In this cases uncertainty estimates can instead derived via the law of total variation:
Jmm=
P) Total Uncertainty
(((D Ep(y) [y]] + Ep(o D) [V my]lvl]
(5)
Knowledge Uneertainty
Expected Data Uncertainty
This is conceptually similar to the decomposition (8) obtained via mutual information. For an en- semble of probabilistic regression models which parameterize the normal distribution, and where each models yields mean and standard-deviaaioo,, the total variance can be computed as follows:
M
M
M
V Weiule,D)) by
pmm
+
(pm, Jm = f(x; ((m)).
M
M
Uncertainty
Knowledge Uncertainty
Expected Data Unvertainty
However, while these measures are tractable, they are based on only first and second moments, and may therefore miss high-order details in the uncertainty. They are also not scale-invarians which can cause issues is the scale prediction on in-domain and out-of-domain data is very different.
Gradient boosting is a powerful machine learning technique especially useful tasks containing heterogeneous features. It iteratively combines weak models, such as decision trees, to obtain more accurate predictions. Formally, given dataset D and loss function L IR2 IR, the gradient boosting algorithm (Friedman, 2001) iteratively constructs a model F X + to minimize the empirical risk C(F)D) (LIL(((())) (z), v)]. At each iteration the model is updated as:
F(1) (x) = (t-1)) (x) + ch (1) (x))
where (t-1)) is a model constructed at the previous iteration, h (x))))) E 7/ is a weak learner chosen from some family functionds H. and is learning rate. The weak learner (t)) is usually chosen to approximate the negative gradient (t) (x. y) == al(y.s)
(t) arg min Ep [ (x) - f(xx))
(8)
3

---

Published as a conference paper at ICLR 2021
A weak learner h()) is associated with parameters ((()) R.. We write (x, x(()) to reflect this dependence. The set of weak learners H. often consists of shallow decision trees, which are models that recursively partition the feature space into disjoint regions called leaves. Each leaf R, of the tree is assigned to a value, which is the estimated response y in the corresponding region. We can write h(x ( ΣS
the decision tree is linear function of ()(1) The final GBDT model F is sum of decision trees (74 and the parameters of the full model are denoted by 0.
( 1 (.) ).
For classification tasks, a model yields estimates data uncertainty if it is trained via negative log- likelihood and provides distribution over class labels. However, classic GBDT regression models yield point predictions, and there has been little research devoted to estimating predictive uncertainty. Recently, this issue was addressed by Duan et all (2020) via algorithm called NGBoost (Natural Gradient Boosting), which allows estimating data uncertainty. NGBoost simultaneously estimates the parameters of conditional distribution p(y] (zc 0) over the target y given the features æ, by optimizing a proper scoring rule. Typically, a normal distribution over y is assumed and negative log- lilekkiihood is taken as a scoring rule. Formally, given an input æ, the model F' predicts two parameters of normal distribution the mean and the logarithm of the standard deviation log a. The loss function the expected negative log- ..gliiee
ply|2; (()) = (Vlpdl ,0()),
{u(1), log (ogo (x).
(9)
[(0 = Ep[- x. 0)]
1
log p (z) 0).
(10)
N
Note that 0 denotes the concatenation of two parameter vectors used to predict μ and log
3 GENERATING ENSEMBLES OF GDBT MODELS
As discussed in Section EL knowledge uncertainty can be estimated by considering an ensemble of models {p(y) æ; ((m)) m=1 sampled from the posterior P(O The level of diversity "disagree- ment" between the models is an estimate of knowledge uncertainty. In this section, we consider three approaches to generating an ensemble of GBDT models. We emphasize that this section discusses ensembles of GBDT models, where a each GBDT model is itself an ensemble of trees.
SGB ensembles One way to generate an ensemble to consider several independent models gener- ated via Stochastic Gradient Boosting (SGB). Stochasticity is added to GBDT models via random subsampling of the data at every iteration (Ereedman. MK02). Specifically, at each iteration of (8) we select a subset of training objects D' (via bootstrap or uniformly without replacement), which is smaller than the original training dataset D, and use D' to fit the next tree instead of D. The frac- tion of chosen objects is called sample rate. This implicitly injects noise into the learning process, effectively inducing a distribution q(0) over such models. Thus, an SGB ensemble is an ensemble of independent models (0(m) | built according to SGB with different random seeds for sub- sampling data. Unfortunately, there are guarantees on how well the distribution q()) estimates the true posterior (D).
SGLB ensembles Remarkably, there is a way sample GBDT models from the true posterior D) via a recently proposed Stochastic Gradient Langevin Boosting (SGLB) algorithm (U Iumenko Prokhorenkova. (020). SGLB combines gradient boosting with stochastic gradient Langevin dynamics (Ragınsky et all, 2017) in order to achieve convergence to the global optimum even for non-convex loss functions. The algorithm has two differences compared with SGB. First, Gaussian noise is explicitly injected into the gradients, so (N) is replaced by:
(x) (-
M1 Φ) + +u) , N0, (0.
2 2 Be )
(t) arg min ED hEH
(11)
where B3 is the inverse diffusion temperature and I|D| is identity matrix. This random noise helps to explore the solution space in order to find the global optimum and the diffusion temperature controls the level of exploration. Second, the update (l2) is modified as:
F(t) (z) (1 (() (t (I,, (b(1))
(12)
Since GBDT model is determined by we use notation L(F(D) and L())D) interchangeably.
4

---

Published as a conference paper at ICLR 2021
First model
Second model
model
Figure 1: Virtual ensemble
where y regularization parameter. the number of all possible trees is finite (a natural assumption given that the training dataset is finite), then the SGLB parameters (()) at each iteration form Markov chain that weakly converges to the stationary distribution, also called the invariant measure:
(0( x exp( -3)(-)C(0D)) -
(13)
where I' = 1 > 0 is an implicitly defined regularization matrix which depends on a particular tree construction algorithm (Ustimenko Prokhorenkova 2020)..
While Ustimenko & Prokhorenkova (2020) used the weak convergence to (LE) to prove the global convergence, we apply this enable sampling from the true posterior. For this purpose, we set |D] and TPT For the negative log-likelihood loss function (III) the invariant measure (I3
can be expressed as:
p3 (0) x exp (log)(D10)- - | x pp(()))p(O)
(14)
which is proportional to the true posterior distribution D)) under Gaussian prior p(0) (0, r). Thus, an SGL.B ensemble is an ensemble of independent models (0(m) m== M generated according to the SGLB algorithm using different random seeds. In this case, asymptotically, models are sampled from the true posterior p(0[D).
Virtual SGLB ensembles While SGB and SGLB yield ensembles of independent models, their time and space complexity is M times larger than that of single model, which is a significant overhead. Consequently, generating an ensemble requires either significantly increasing complexity or sacrificing the quality by reducing the number of training iterations. To address this, we introduce the concept of a virtual ensemble that enables generating an ensemble using only one model. This possible since a GBDT model is itself an ensemble of trees. However, in contrast to random forests formed by independent trees (Shaker & Hillenneter, 2020), the sequential nature GBDT models implies that all trees are dependent and individual trees cannot be considered as separate models. Hence, we use "truncated" sub-models of single GBDT model as elements of an ensemble, as illustrated in Figure MI Notably, virtual ensemble can be obtained using any already constructed GBDT model. Below we formally describe this procedure applied to SGLB models since in this case guarantee asymptotically sampling from the true posterior DD.
Each "truncated" model is described by the vector of parameters ((t) As the parameters ((*) each iteration of the SGLB algorithm form a Markov chain that weakly convergences to the stationary ensemble of models. However, unlike parameters
distribution (LE), taken from different SGLB trajectories, these will have a high degree of correlation, which adversely affects the ensemble's 's quality. This problem can be overcome by retaining only every K-th set of parameters. Formally, fix K 2 1 and consider set of models θ (0(k)) T
consider using them
] Itsss [K]]. ie., we add to θT,K every K-th model obtained while constructing one SGLB model using T iterations of gradient boosting. Choosing larger values of K allows to reduce the correlation between samples from the SGLB Markov chain. Furthermore, we do not include to the ensemble the models (1) with < T/2 as (LE) holds only asymptotically. The set of M T models Or, is called virtual ensemble. Note that virtual ensembles behave similarly to ensembles in the limit (for large K and T".
2K
22
Importantly, we can compute the prediction of θr,x with the same computation time as one (T)), Indeed, when computing the prediction of one model, have individual trees. To get the virtual ensemble, we only have to store the partial sums. For SGLB, also have to account for regularization (12). Formally, according to (12), for SGLB have
up the predictions made by
5

---

Published as a conference paper at ICLR 2021
15
(a) True Data Uncertainty
(b) Estimated Data Uncertainty
(c) Knowledge Uncertainty
Figure 2: Uncertainty for synthetic regression dataset with two categorical features. Inside the heart
(white region on the first figure) there no training examples.
0 Ei= ( TT)
where (1 - -e) appears due to shrinkage. While computing
T store the partial sums O77) Ei= e(1 - (c) Ti Then, any model (()) from θr,
can easily be obtained from the stored values:
(+)
c(1 - -1 -1-7e)-7 T
(15)
ANALYSIS ON SYNTHETIC DATA
In this section, we analyze how ensemble algorithms discussed Section B perform on synthetic data. The aim is to understand the attributes of ensembles of GBDT models for estimating data and knowledge uncertainty in controllable setting.
GBDT models are usually applied to tabular data, where features often categorical. Hence, we first generate a dataset with each example described by two categorical features I1, 22 with 9 values each, resulting in 81 possible combinations. The target depends the features as = a 222 + E(x1, X22,, where c(x1, 22) ~ (O,, ((21, #2)) and a(x1, 222), ((x1, are some deterministic functions. The values for a(x1,
randomly generated according to the uniform distribution over [0, 1]. The values for 6(z1, T2) are shown on Figure Ma We generate heart- shaped dataset with this distribution: inside the heart (white region on Figure Z(a there are no training points, for the other cells we have 1000 examples per cell.
We train an ensemble of 10 SGLB models (each model consists of 1000 trees) and observe the following effects. First, Figure [(b] shows the total uncertainty estimated with SGLB ensemble and we see that the models correctly capture this uncertainty in all cells containing training examples. At the same time, arbitrary values can be predicted inside the heart, as training data constrain the models' behavior there. Second, Figure _ shows that estimates of knowledge uncertainty allow us to detect regions that are out-of-domain and are not covered by the training data. Notably, the separation perfect, as there is no trace of the original heart border.
To further analyze ensembles of GBDT models, we apply them to two-dimensional classification features. We consider a 3-class spiral dataset shown on Figure Sa
task with continuous-vall and this setting is much harder for gradient boosted trees. B Figure [Tb] shows the total uncertainty estimated with SGLB ensemble, while Figure [Sc] demonstrates knowledge uncertainty. We observe several effects. First, total uncertainty correctly detects class boundaries and 'sectors' of input space outside the training dataset. Second, looking at these 'sectors' of high uncertainty, we can better understand how GBDT ensembles work: as decision trees are discriminative functions (Bishop, 2006). if features have values outside the training domain, then the prediction is the same as for the "closest" elements in the dataset. In other words, the models' behavior on the boundary of the dataset is further extended to the outer regions. Third, estimates of knowledge uncertainty allow discrimination between out-of-domain regions and class boundaries. However, we still can see traces of the class boundaries in Figure B(c), A possible reason is the fact that for real-valued features, near the class borders, the splitting values may vary across all models the ensemble, resulting in non- zero estimates of knowledge uncertainty due to decision-boundan 'jitter'.
To partially mitigate the difficulties, we use coordinates in rotated axes and radius additional features.

---

Published as a conference paper at ICLR 2021
1000
1000
-500
-5.5
1,00
-100
3.00
-500
-5.00
3.00
-70
1000
-000
-100
(a) Spiral Dataset
(b) Total Uncertainty
(c) Knowledge Uncertainty
Figure 3: Uncertainty for synthetic classification dataset
0300
(a) Heart SGLB KU
(b) Heart vSGLB KU
(c) Spiral SGLB KU
(d) Spiral vSGLB KU
Figure 4: Comparison of SGLB and vSGLB knowledge uncertainty estimates
On both "heart" and "spiral" datasets, we observed that the absolute values of knowledge uncertainty are much smaller than of data uncertainty and therefore contribute very little total uncertainty. Thus, we expect that while knowledge uncertainty is especially useful for detecting anomalous in- puts, the proposed approaches will contribute little to error detection on top of estimates of data uncertainty provided by single models.
Finally, on Figure H. we compare the performance of 'true' SGLB ensembles with the virtual SGLB ensembles (vSGBL) on both the "heart" and "spiral" datasets. The virtual ensemble is ten times cheaper to train and infer, but the ensemble members are strongly correlated. We observe that on the "heart" dataset, vSGLB perfectly detects regions not covered by training data. However, the absolute values of knowledge uncertainty are much smaller than for SGLB, which can be explained by the correlations. The "spiral" dataset is more challenging for both SGLB and vSGLB. While having qualitatively similar behavior, virtual ensembles struggle to detect out-of-domain regions and separate them from class boundaries. In all cases, the absolute values of knowledge uncertainty are far lower than for 'true' SGLB ensembles. This shows that while vSGLB yields very cheap estimates of knowledge uncertainty by exploiting the 'ensemble of trees' structure of GBDT models, the quality of these estimates is inferior to ensembles of independent models.
5 EXPERIMENTS ON CLASSIFICATION AND REGRESSION DATASETS
In this section, we evaluate the performance of ensembles of GBDT models on a range of classifica- tion and regression tasks, focusing on their ability detect errors and out-of-domain inputs.
Experimental setup Our implementation of all GBDT models is based on the CatBoost library that is known to achieve state-of state-of-the-arr results a variety of tasks (Prokhorenkovaa et all 2018). Classification models yield a probability distribution over binary class labels, while regression mod- els yield the mean and variance of the normal distribution, as discussed in Section D All models trained by optimizing the negative log-likelihood. We consider SGB and SGBL single models as the baselines and examine all ensemble methods defined in Section GL Ensembles of SGB and SGLB models consist of 10 independent (with different seeds) models with 1000 trees each. The virtual ensemble vSGLB is obtained from one model with 1000 trees, where each 50th model from the interval [501, 1000] is added to the ensemble. Thus, vSGLB has the same computational and
'In Appendix A we compare our implementation with the original NGBoost and Deep Ensembles in terms of NI.. (negative log-likelihond) and RMSE. Our implementation has comparable performance to the existing methods.
7

---

Published as a conference paper at ICLR 2021
space complexity as just one SGB or SGLB model. Hlyper-paaament are tuned by grid search, for details see Appendix
We compare the algorithms on several classification and regression tasks (Gal & Ghahramant 2016 Prokhorenkova et all 2018), the description of which is available in Appendix A.3
While not being the focus of the current research, Random Forest (RF) models naturally suitable for ensemble approaches. Hence, we conduct additional experiments and analyze the performance of ensemble approaches applied to RF models in Appendix C
Detection of errors and anomalous inputs We analyze whether measures of total and knowledge uncertainty can be used to detect errors and out-of-domain inputs. Error detection can be evaluated via the how well uncertainty estimates correlate with errors and rank-order them. The best value is 100, random is 0. Out-of-domain (OOD) detection is assessed via area under the ROC curve (AUC- ROC) (Hendrycks & Gimpel. 2016). For OOD detection, we need an OOD test-set. However, obtaining 'real' OOD examples for the datasets considered in this work is challenging, so we instead create synthetic OOD data as follows. For each dataset, we take its test set as the in-domain examples and sample an OOD dataset of the same size from the Year MSD dataset to get oft-of-d (OOD) data. The only exceptions are KDD datasets (Appetency, Churn, Upselling) and Year MSD, for which we sample OOD data from the Relative location of CT slices on axial axis Data Set (Graat Z0T... All numerical features in OOD data are normalized by the per-column mean and variance obtained on the in-domain training data. For categorical features, we sample a random category uniformly random from the set of all feature's 's categories. Total and knowledge uncertainty are estimated via entropy of the predictive posterior (E) and mutual information (H) for classification models and via total variance and variance of the mean (55) for regression ones.
Rejection Ratio (PRR) (Malmnn 2019; Malmin all, 2020), which measures
Test errors can occur due to both noise and lack of knowledge, so we expect that ranking elements by total uncertainty would give better values of PRR. Table MI shows that measures of total uncertainty consistently yield better PPR results across all datasets. This is consistent with results obtained for ensembles of neural network models (Lakshmmarrayanan et all 2017: Mainn. 2019 Malmn & Gales, 2010 Malmun al (U2T).. However, ensembles do not outperform single models. We believe this occurs for two reasons. First, due to the additive nature of boosting, GDBT models are already ensembles. Second, we have discussed in Section EI, for GBDT models, estimates of knowledge uncertainty obtained via the approaches considered here contribute little to estimates of total uncertainty.
In contrast, Table II shows that measures of knowledge uncertainty yield superior OOD detection performance compared to lotal uncertuinty in terms of AUC-ROC, which is consistent with results for non-GBDT models (Malinn, 2019; Mamm & Gales 201 Malmn et all 2020) B The results also show that SGB and SGLB ensembles performed almost equally well. At the same time, virtual ensembling (vSGLB) performed consistently worse (with one exception) than SGB/SGLB ensem- bles, which is explained by the presence of strong correlations between the models in virtual ensemble. However, in classification tasks, estimates of knowledge uncertainty provided by vSGLB nevertheless outperform uncertainty estimates derived from single SGB and SGLB models. This shows that useful measures of knowledge uncertainty can be derived from a single SGLB model by interpreting it as a virtual ensemble at no additional computational or memory cost. For vSGLB, the difference between classification and regression tasks can be explained by the presence or absence of categorical features. In our preliminary experiments on synthetic data, we noticed that categori- cal features may have noticeable effect on the diversity of vSGLB models, and our classification datasets contain categorical features.
6 CONCLUSION
This work examined principled, ensemble-base uncertainty uncertainty-estimation for GBDT models. Two main approaches to generating ensembles of GDBT models, where each model itself an ensemble of trees, were considered - Stochastic Gradient Boosting (SGB) and Stochastic Gradient Langevin Boosting (SGLB). Based on SGLB, we propose constructing a virtual ensemble (vSGLB) by ex-
Note that single models do allow distinguishing between the types of uncertainty.
8

---

Published as a conference paper at ICLR 2021
Table 1: Detection of errors and OOD examples for regression and classification tasks
Single
Ensemble SGLB
Single
Ensemble SGLB
Dataset
SGB
SGLB
SGLB
vSGLB
Classification
(1)
Classification AUC-ROC (1)
Adult
TU
72
72
72
72
72
52
51
KU
49
38
89
89.
85
TU
Amazon
KU
64
61
40
88
74
67
TU
43
44
43
44
67
64
64
Click
KU
22
22
11
91
92
90
TU
76
79
77
79
79
67
68
70
69
68
Internet
KU
KDD-Appetency
TU
68
69
69
69
29
48
47
50
KU
14
KDD-Chumn
KU
33
35
28
99
98
92
KDD-Upselling
TU
56
56
57
57
56
51
62
60
KU
45
49
33
97
97
78
TU
44
45
44
44
45
45
37
52
58
38
Kick
KU
20
98
98
89
Dataset
Regression % PRR (1)
Regression % AUC-ROC (1)
BostonH
TU
45
45
44
45
46
70
68
71
69
64
KU
38
80
49
TU
45
41
44
42
41
78
80
79
81
78
Concrete
KU
25
62
Energy
KU
36
31
54
100
100
32
TU
59
59
89
59
58
43
43
Kin8am
KU
18
19
35
45
45
45
Naval-p
TU
75
76
82
82
81
99
99
100
100
99
KU
52
56
69
100
100
87
TU
30
32
31
33
32
48
47
51
49
47
Power.p
Protein
TU
49
48
52
50
48
84
92
91
KU
30
12
99
99
94
TU
33
32
32
Wine-yu
KU
25
19
9
74
72
49
Yacht
TU
89
88
88
88
88
57
57
58
58
55
KU
74
78
66
62
60
40
TU
61
62
62
63
62
59
58
60
60
57
Year
ploiting the 'ensemble-of-trees' nature of GBDT models. Properties of the estimates total, data, and knowledge uncertainty derived from these ensembles were first analyzed synthetic data. It was shown that the proposed approach can successfully detect anomalous inputs and is especially successful on tabular data. On continuous data, detecting knowledge uncertainty is still possible, but it becomes harder to differentiate it with data uncertainty due to decision- -boundary 'jitter'. Further experiments on a wide range of classification and regression datasets showed that while ensembles of GDBT models do not offer much advantage in terms of eтror detection, as each model is already an ensemble of trees, they do yield useful measures of knowledge uncertainty, which enables out- of-domain detection in both regression and classification tasks. Notably, measures of knowledge un- certainty, which can only be obtained via ensembles, achieve far better OOD detection performance than measures of total uncertainty. It is also shown that while there is little practical difference be- tween SGB and SGLB ensembles, vSGLB performs noticeably worse. However, for classification tasks containing categorical features, vSGLB still yields useful measures of knowledge uncertainty at the computational time and space complexity of a single SGLB model. Thus, vSGLB allows us to derive the benefits of an ensemble no additional computational and memory cost.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
We would like to thank Ekaterina Ermishkina and Stanislav Kirillov for implementing the proposed methods within the CatBoost library.
REFERENCES
UCI datasets.
master/Uc Datasets.
Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. In International Conference on Learning Representations, 2020. URL
net Ftte:/ooommdddBB.....
Thierry Bertin-Mahicux, Daniel PW Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Society for Music Information Retrieval Confer- ence (ISMIR 2011), 2011.
Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
Christopher JC Burges. From RankNet to LambdaRank to LambdaMART: An overview. Learning, 11(23-581):11, 2010.
Rich Caruana and Alexandru Niculescu-Mizil. empirical comparison supervised learning
algorithms. In Proceedings of the 23rd international conference on Machine learning, pp. 161- 168. ACM, 2006.
Hugh Chipman, Edward George, Robert E McCulloch, et al. Bart: Bayesian additive regression trees. The Annals of Applied Statistics, 4(1):266-299) 2010.
John W Coulston, Christine Blinn, Valerie Thomas, and Randolph H Wynne. Approximating prediction uncertainty for random forest regression models. Photogrammetric Engineering & Remote Sensing, 82(3):189-197, 2016.
Stefan Depeweg, José Miguel Hrrnández-Lobatee Finale Doshi-Velez, and Steffen Udluft. Decom position of uncertainty for active learning and reliable reinforcement learning in stochastic sys- tems. star, 1050: 2017.
Tony Duan, Anand Avati, Daisy Yi Ding, Sanjay Basu, Andrew Y Ng, and Alejandro Schuler. Ng- boost: Natural gradient boosting for probabilistic prediction. Proc. 37th International Conference Machine Learning (ICMI), 2020.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Jerome H Friedman. Stochastic gradient boosting. Computational Statistics Data Analysis, 38(4): 367-378, 2002.
Yarin Gal. Uncertainty in Deep Learning, PhD thesis, University of Cambridge, 2016.
Yarin Gal and Zoubin Ghahramani. Dropout Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In Proc. 33rd International Conference on Machine Learning (ICML-16), 2016.
Franz Graf, Hans-Peter Kriegel, Matthias Schubert, Sebastian Pölsterl, and Alexander Cavallaro. 2d image registration in et images using radial image descriptors. In International Conference Medical Image Computing and Computer-Assisse Intervention, pp. 607-614. Springer, 2011.
Dan Hendrycks and Kevin Gimpel. A Baseline for Detecting Misclassified and Out-of- Distribution Examples Neural Networks. h.tp:///aall...o/////////......0 2016. arXiv:1610.02136.
Kaggle. "Don't t Get Kicked!". https:: www. www.kkaagllec..o... www.ee.cooccc/oooie
http://w..aoleeeoooooooootttteea 2011.
10

---

Published as a conference paper at ICLR 2021
Kaggle.
Amazon dataset.
Attps: www
amazonrevieva 2017.
KDD. Kdd cup 2009: Customer relationship prediction.
cup/
View kdddd cup 20030000 2009.
KDD. Kdd cup 2012 (track 2): Predict the click rate of ads given the query and user infor- 2012.
mation. httos: /tss::/wwwt www. köd. http://www....ataa////o////aaaaa
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7482-7491, 2018.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. BatchBALD: Efficient and diverse batch acquisition for deep bayesian active learning. In Advances in Neural Information Processing Systems 32 (NeurlPS 2019), 2019.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Proceed- ings of the Second International Conference on Knowledge Discovery and Data Mining, 1996.
B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and Scalable Predictive Uncertainty Es- timation using Deep Ensembles. In Proc. Conference on Neural Information Processing Systems (NIPS), 2017.
Antonio R Linero. A review of tree-based bayesian methods. Communications for Statistical Appli- cations and Methods, 24(6), 2017.
Wesley Maddox, Timur Garipov, Pavel Izmailov, Dmitry Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. arXiv preprint wiXv:1902.022476 2019.
Andrey Malinin. Uncertainty Estimation in Deep Learning with upplication to Spoken Language Assessment. PhD thesis, University of Cambridge, 2019.
Andrey Malinin and Mark JF Gales. Reverse kl-divergence training of prior networks: Improved uncertainty and adversarial robustness. 2019.
Andrey Malinin, Bruno Mlodozenice, and Mark Gales. Ensemble distribution distillation. In International Conference on Learning Representations, 2020. URL
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? Evaluating predictive uncertainty under dataset shift. Advances in Neural Information Processing Systems, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. Catboost: unbiased boosting with categorical features. In Proceedings of the 32nd Interna- tional Conference on Neural Information Processing Systems (NeurIPS), pp. (638-6648 2018.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. CoRR, abs/1702.03849, 2017.
Matthew Richardson, Ewa Dominowska, and Robert Ragno. Predicting clicks: estimating the click- through rate for new ads. In Proceedings of the 16th international conference World Wide Web, pp. 521-530. ACM, 2007.
Byron P Roe, Hai-Jun Yang, Zhu, Yong Liu, Ion Stancu, and Gordon McGregor, Boosted decision trees as alternative artificial neural networks for particle identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associ- ated Equipment, 543(2):577-584, 2005.
11

---

Published as a conference paper at ICLR 2021
Mohammad Hossein Shaker and Eyke Hüllermeier. Aleatoric and epistemic uncertainty with ran- dom forests. In International Symposium on Intelligent Data Analysis, pp. 444 456. Springer, 2020.
Lewis Smith and Yarin Gal. Understanding Measures of Uncertainty for Adversarial Example De- tection. In UAI, 2018.
UCI. KDD internet usage data.
attps: /ttp:://arciivoo/ ies. uci www.su...ed//m.......... mo00/mm///e httpmm/mdaatattst...
Internec-usacetuaa.a 1997.
Alcksei Ustimenko and Liudmila Prokhorenkova. SGLB: Stochastic Gradient Langevin Boosting.
arXiv e-prints, art. arXiv:2001.0f5 .07248, 2020.
Qiang Wu, Christopher JC Burges, Krysta M Svore, and Jianfeng Gao. Adapting boosting for information retrieval measures. Information Retrieval, 13(3):554-77, 2010.
Yanru Zhang and Ali Haghani. A gradient boosting method to improve travel time prediction. Trans- portation Research Purt C: Emerging Technologies, 58:308-324 2015.
12

---

Published as a conference paper at ICLR 2021
A EXPERIMENTAL SETUP
A.1 OUR IMPLEMENTATION OF DATA UNCERTAINTY
As discussed in Section 2.2 of the main text, for regression simultaneously predict the parameters and log a of the Normal distribution. Similarly to NGBoost, we use the natural gradients. For our loss and parameterization, the natural gradient is:
g0 (2. -(1lt-))
( (y- 10-p(t11 (((-1) (((-1)
) )):
y:
(16)
At each step of the gradient boosting procedure, we construct one tree predicting both components of gtt), similarly to the MultiRMSE regime CatBoost. B
Recall that for classification we optimize the logistic loss.
In Table we compare our implementation with NGBoots (Duan el (02() and Deep Ensem- bles (Lakshminarayanall et all 201Z)) on regression datasets. For our implementation, we consider SGB with fixed sample rate (0.5) and perform parameter tuning as described below. The best results are highlighted.
Table 2: Comparison of our implementation with existing methods
RMSE
NLL NGBoost
Dataset
Deep. Ens.
NGBoost
CatBoost
Deep. Ens.
CatBoost
Boston
3.28 1 1.00
2.94 1 0.53
3.06 0.68
2.41 +: 0.25
2.43 1 0.15
2.47 0.20
Concrete
6.03 + 0.58
5.06 1 0.61
5,21 0.53
3.06 0.18
3.04 1 0.17
3.06 1: 0.13
Energy
2.09 + 0.29
0.46 = 0.06
0.57 0.06
1.38 0.22
0.60 + 0.45
1.24 1.28
Kin8nm
0.09 = 0.00
0.16 0.00
-1.20 0.00
-0.49 0.02
0.02
Naval
0.00 0.00 0.00
0.00 0.00
0.00
-5.63
5
0.04
Power
4.11 0.17
3.79 + 0.18
3.55 0.27
2.79 0.04
2.79 0.11
2.72 2.12
Protein
4.71 + 0.06
4.33 0.03
3,92 0.08
2.83
2.81 0.03
0.07
Wine
0.64 + 0.04
0.63 0.04
0.63 0.04
0.94 0.12
0.91 0.06
0.93 + 0.08
Yacht
+
0,50 0.20
0.82 0.40
1.18 0.21
0.26
0.41 0.39
Year MSD
8,89 + NA
8.94 1 NA
8.99 NA
3.35 1 NA
NA
3.43
A.2 PARAMETER TUNING
For all approaches, we use grid search to tune learning-rate in (0.001, 0.01, 0.1). tree depth in {3, 4, 5, 63. We fix subsample to 0.5 for SGB and to for SGLB. This done to avoid joint random- ization effects of SGB sampling and SGLB noise in gradients. We also set diffusioontemppraature and model-sshrnk-rres
2N for SGLB.
A.3 DATASETS
The datasets are described in Table G For regression, we use standard train/ vaainivaliationntesstt splits (UCI) For classification, split the datasets into proportion 65/15/20 in train, validation. and test sets. For more details, see our GitHub repository.
A.4 STATISTICAL SIGNIFICANCE
For regression, perform validation to estimate statistical significance with paired (-test. In corresponding tables, we highlight the approaches that are insignificantly different from the best one (p-value 0.05).
tt htm
13

---

Published as a conference paper at ICLR 2021
Table 3: Datasets description
Dataset
Examples
# Features
Classification
Adult (Kohavi. 1996)
48842
14
Amazon (Kaggle, 201
32769
Click (KD 201
399482
11
Internet (CCL (19970
10108
68
KDD-Appetency (KD 2010))
50000
419
KDD-Churn (KDD) p0(n))
50000
419
KDD-Upselling (KDP. 2009))
50000
419
Kick (Kaggle. 2010
72983
43
Regression
Boston (C(C)
506
13
Concrete [[[W]
1030
Energy (UCI)
768
Kinšnm (T(C))
8192
Naval (((C)
11934
16
Power (UCII
9568
Protcin (UCCI)
45730
Wine (UCI)
1599
11
Yacht (UCI)
308
Year MSD (Beriin-aahieu etall 201
515345
90
Table 4: NLL and RMSE/Error rate for regression and classification
Single
Ensemble SGLB
Single
Ensemble SGLB
Dataset
SGB
SGLB
SGB
vSGLB
SGB
SGLB
SGB
vSGLB
Classification NLL (1)
Classification % Error (L)
Adult
0.276
0.273
0.276
0.271
0.274
12.8
12.7
12.8
12.6
12.7
Amazon
0.141
0.142
0.140
0.142
0.143
4.7
4.6
4.6
4.5
4.5
Click
0.393
0.392
0.392
0.391
0.392
15.6
15.6
15.6
15.6
Internet
0,224
0.218
0.221
0.217
0.218
9.9
10.0
9.7
10.0
10.0
Appetency
0.073
0.073
0.073
0.073
0.073
1.8
1.8
1.8
1.8
1.8
Chum
0.235
0.236
0.233
0.234
0.235
7.3
7.2
7.3
7.2
7.2
Upselling
0.168
0.168
0.168
0.168
0.168
5,0
4.9
5.0
5.0
Kick
0.287
0.286
0.286
0.285
0.286
9.5
9.6
9.5
9.4
9.6
Dataset
Regression
(1)
Regression RMSE (4)
BostonH
2.47
2.52
2.46
2.50
2.50
3.06
3.12
3.04
3.10
3.27
Concrete
3,06
3,06
3.05
3.05
5.21
5.11
5.21
5.10
5.37
Energy
1.24
1.70
1.13
1.52
0.70
0.57
0.54
0.57
0.54
0.64
Kin8nm
-0.63
-0.65
-0.63
-0.65
-0.60
0.14
0.14
0.14
0.14
0.15
Naval-p
-5.39
-5.42
-5.61
-5.65
-5.39
0.00
0.00
0.00
0.00
0.00
Power-p
2.72
2.71
2.66
2.66
2.69
3.55
3.56
3.52
3.54
3.64
Protein
2.73
2.73
2.61
2.64
2.70
3.92
3.96
3.90
3,93
4.02
Wine-qu
0.93
0.99
0.92
0.98
0.96
0.63
0.65
0.63
0.65
0.66
Yacht
0.41
0.38
0.27
0.32
0.51
0.82
0.84
0.83
0.84
0.97
Year
3.43
3.43
3.41
3.40
3.42
8.99
8.96
8.97
8.94
8.98
14

---

Published as a conference paper at ICLR 2021
For classification (and Year MSD), measure statistical significance for NLL and error/RMSE on the test set. In the corresponding tables, the approaches that are insignificantly different from the best one are highlighted. For PRR and AUC-ROC (for classification and Year MSD), we highlight the best value.
B ADDITIONAL EXPERIMENTAL RESULTS
In Table E we compare ensemble approaches with single models in terms NLL and error rate for classification and in terms of NLL and RMSE for regression tasks. Results for NLL demonstrate an advantage of ensembling approaches compared to single models. However, in some cases the significant, which can be explained by the additive nature of boosting: averaging several tree ensembles gives another (larger) tree ensemble. Thus, improved NLL can result from the increased complexity of ensemble models. We can make similar conclusion from the results for RMSE and error rate.
difference
C COMPARISON WITH RANDOM FOREST
Our paper specifically focuses on uncertainty estimation in Gradient Boosted Decision Trees (GBDT) models. However, some related work was done for quantifying uncertainty in random forests (Coulston et al, 20IG: Shaker & Hullermeier, 2020), which are also ensembles of decision trees. Thus, for completeness, we also analyze how ensemble approaches perform in combination with random forests.
In these experiments, we use the scikit-learn implementation of random forests (Pedregosa all I.. We limit the maximum depth to 10 and keep all other parameters default. For categorical features, we use leave-one-out encoding.
Unlike GBDT, where trees added to correct the previous model's mistakes, random forests (RF) consist of decision trees that are independently trained on bootstrapped sub-samples of the dataset. divide RF into several independent parts, each consisting of several trees. Drawing a parallel to virtual SGLB, we call this approach vRF (virtual RF) since it allows estimating knowledge uncertainly using only one trained random forest model. In our experiments with vRF, we divide one RF model into 10 independent parts, each consisting of 100 trees. Similarly, one can also construct an ensemble of several independently trained random forest models, which is expected to be stronger baseline. However, we expect a small difference between vRF and an ensemble of random forests, as there are, priori, no correlations between trees both in single model and across multiple RF models.
Hence, for knowledge uncertainty
In Tables and we compare the predictive performance of random forests (both individual models and explicit ensembles of multiple models) to SGLB individual and ensemble models classifica- tion and regression tasks. The results show that generally GBDT models outperform random forest models in terms of classification error rate and NLL. Note that cannot calculate NLL for RF regression models as they are not naturally probabilistic (do not yield a predicted variance). As a result, they are unable estimate data uncertainty, and therefore can only obtain estimates of knowledge uncertainty.
Table M compares SGLB and RF ensembles in terms of error detection (PRR) and out-of-domain input detection (ROC-AUC). One can see that SGLB usually outperforms RF, especially for OOD detection. Notably, expected, for OOD detection vRF and RF give similar results. Thus, conclude that for random forests, a virtual ensemble is a good and cheap alternative to the true one.
15

---

Published as a conference paper at ICLR 2021
Table 5: Comparison with random forest: NLL and error rate for classification
Single
Ensemble SGLB
Single SGLB
Ensemble
Dataset
SGLB
RF
RF
RF
SGLB
RF
Classification NLL (4)
Classification % Error (1)
Adult
0.273
0.300
0.271
0.300
12.7
13.9
12.6
13.9
Amazon
0.142
0.183
0.142
0.183
4.6
5.6
4.5
5.6
Click
0.392
0.411
0.391
0.411
15.7
16.0
15.6
16.0
Internet
0.218
0.275
0.217
0.274
10.0
11.2
10.0
11.0
KDD-Appetency
0.073
0.083
0.073
0.083
1.8
1.8
1.8
1.8
KDD-CIE EDD-Churn
0.236
0.249
0.234
0.249
7.2
7.3
7.2
7.3
KDD-Upselling
0.168
0.202
0.168
0.202
4.9
7.4
5.0
7.4
Kick
0.286
0.311
0.285
0.311
9.6
10.4
9.4
Table 6: Comparison with random forest: RMSE for regression
Single SGLB
Ensemble SGLB
Dataset
RF
RF
BostonH
3.12
2.98
3.10
2.98
Concrete
5.11
4.96
5.10
4.95
Energy
0.54
0,50
0.54
0,50
Kin8nm
0.14
0.15
0.14
0.15
Naval-p
0.00
0.00
0.00
0.00
Power-p
3.56
3.53
3.54
3.53
Protein
3.96
4.19
3.93
4.19
Wine-qu
0.65
0,58
0.65
0.58
Yacht
0.84
0.84
0.84
0.84
Year
8.96
9.43
8.94
9.43
16

---

Published as a conference paper at ICLR 2021
Table 7: Comparison with random forest: detection of errors and OOD examples for regression and classification (virtual and true ensembles)
Dataset
vSGLB
vRF
SGLB
RF
vSGLB
vRF
SGLB
RF
Classification % PRR (t)
Classification % AUC-ROC (t)
TU
72
70
72
70
51
58
51
58
Adult
KU
85
TU
68
63
68
64
86
48
86
49
Amazon
KU
45
52
TU
36
44
37
68
71
Click
KU
90
TU
69
68
68
Internet
KU
38
72
36
81
TU
56
52
KDD-Appetency
KU
14
34
54
34
93
98
TU
60
KDD-Churn
KU
13
35
92
93
98
94
TU
KDD-Upselling
KU
33
45
49
44
78
90
97
92
TU
38
38
Kick
KU
20
27
34
29
89
89
98
89
Datasct
Regression % PRR (1)
Regression % AUC-ROC (t)
TU
64
BostonH
KU
53
37
55
49
76
TU
78
Concrete
KU
25
43
27
42
56
80
92
80
TU
69
Energy
KU
54
40
31
32
100
100
100
TU
Kin8nm
KU
35
33
19
33
45
48
45
48
TU
33
47
49
Power-p
KU
13
21
22
57
66
73
65
TU
48
50
86
Protein
KU
12
40
29
40
94
91
99
92
TU
32
32
56
56
Wine-qu
KU
35
19
32
49
74
72
74
TU
88
88
55
58
Yacht
KU
66
79
78
81
40
52
60
52
TU
62
63
57
60
Year
KU
25
28
30
27
52
74
57
74
17


Reviews:
[{"review_id": "sP9XM9W3-w", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied the uncertainty estimation in GBDT method. The authors described 3 methods to estimate the uncertainty. With SGB, the estimation is achieved by training multiple models using data sub-samples. With SGLB, the authors derived that we can estimate the posterior distribution of the model parameters. These two methods both have the disadvantage that the training time is multiplicative of the number of trained models. To address this issue, the authors proposed an improvement to SGLB which they call virtual SGLB. The main idea is to use a subset of trees in a GBDT as a model sample, so that we can train a single model but still able to estimate the uncertainty.\n\nI find the paper clearly written and well organized. The theoretical formulation of the proposed methods makes sense and clear to follow. A natural concern of the vSGLB method is the correlation between the sub-trees in GBDT. Indeed, the experiments show that vSGLB is significantly worse in uncertainty estimation in real datasets. Nevertheless, I think the authors make a good case about the trade-off between a fast training time and a good uncertainty estimation.\n\nUncertainty estimation is an increasingly important topic in machine learning application. GBDT method is one of the most commonly used ML method in application. This paper propose a fast approach and a more accurate approach for uncertainty estimation when using GBDT. Thus I think it would be an interesting read to ML practitioners especially.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ff-uh9IKfu6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper explores a strategy of building ensembles of Gradient Boosting Decision Trees (GBDTs) to improve capturing total uncertainty and knowledge uncertainty to better detect errors and out of domain data points. Overall, I vote for accepting. I think while the results are not super impressive, they are encouraging, and I would like to see more research exploring this area.\n\nPros:\n1. I think error detection and OOD detection are an under explored area in the context of tabular data. The problem itself is important in terms of practicality.\n2. The main idea of the paper is to build ensembles of GBDTs with two flavors of gradient descent. The intuition that ensembles should improve uncertainty estimation is natural, and something worth exploring.\n3. The main improvement in terms of results is the improved out-of-domain data detection with SGLBs. Other than that, the results aren’t really better than a single GBDT for error detection.\n4. The number of experiments done is quite comprehensive with a good mix of synthetic and real datasets.\n5. It’s disheartening that even with ensembles of GBDTs, the PRR is quite low in most datasets. This is not the authors’ fault of course. I think this is an important contribution to the literature so that the community is aware it does not work for error detection. \n  \nCons:\n1. The virtual ensemble doesn’t quite give as good performances as SGLBs which the authors were emphasizing quite a bit.\n2. I couldn’t find any description on how the knowledge uncertainty was calculated practically (coding wise). \n3. I think it is important to at least show how Random forests or ExtraTreeForests are performing in terms of Precision-rejection ratio (PRR), and OOD detection. These ensemble methods typically perform well, so even if they perform worse here, that would be a benchmark on how much SGLBs are improving upon.\n\nI would request the authors to address the cons during the rebuttal period.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Eu8RmOSa-JT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work examines a probabilistic ensemble-based framework for deriving uncertainty estimates in the predictions of gradient boosting classification and regression models. As the authors have said, predictive uncertainty is sometimes a must have feature for high-risk application of machine learning techniques.\n\nThe authors conducted a range of experiments on both synthetic and real datasets and investigated the applicability of ensemble approaches to gradient boosting models that are themselves ensembles of decision trees. The results seem to suggest these ensembles were able to detect anomaly input. The authors have also introduced the idea/concept of virtual ensemble by exploiting the ‘ensemble-of-trees’ nature of GBDT models. , which is interesting too.\n\nIn general I think this paper is trying to tackle a significant problem, so it would be good if the authors would give some real world examples of possible applications when uncertainty estimates in the predictions is essential. Another aspect is, as the authors have mentioned, boosting trees itself is an ensemble, I would expect the authors explain a bit more on why we need ensemble of ensembles rather than working out uncertainty estimates just using the trees in a single boosting-tree ensemble?", "extra_scores": {}, "extra_text": {}}, {"review_id": "9nboHuLERPH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors propose to apply the idea of Bayesian ensemble methods to (tree-based) gradient boosting methods so as to be able to measure the knowledge uncertainty (e.g., to detect anomaly or out-of-domains samples) while typically only data uncertainty (e.g. related to noise in the data) is considered.  \n\nOveral comment:\nThe paper is well-written and the amount of experiments is impressive. However, the proposed approach raises several concerns addressed below and regarding the novelty mainly (comment (b)) and the actual performances (comment (d)). I think the paper could be accepted if comments (b) and (d) are addressed. \n\nMajor comments:\n(a) The motivation is well explained and I agree that not knowing when a machine learnt predictor makes a prediction with certainty or not is the key of the trust in such models. \n(b) It is unclear how the approach for estimating uncertainty is novel with respect to what was made with other ensemble approaches as Section II refers to preliminary works but Section III (except virtual ensembles) refers to ensemble of GB models and I am not sure it is an actual contribution of this paper. Please clarify what's new and what already exists in Section III and how much your approach differs / improves / modifies what has already been suggested by the uncertainties estimation via Bayesian Ensembles. \n(c) As suggested by Figure 1, it appears that a virtual ensemble is built recursively by adding the one tree model to the previous ensemble and making hence a new object of the virtual ensemble. This suggests that models are not independent and intrinsically give a much higher weight on the first model for instance. The motivation behind the building of the virtual ensemble (the choice of T/2 in the text for instance) is not very clear either. Please clarify (a) if Figure 1 is not overly simplistic and (b) the motivation of the making of a virtual ensemble (especially the value T/2).\n(d) It would have been interesting  (and more convincing) to have results (of Table 1) for other non-gradient boosting techniques to convince the soundness of the proposed approach and how it compares with other techniques. \n\nMinor comments: \n- typo : \"it's (applications)\" in the first section.\n- Typically, loss functions are defined as function $R^2 \\rightarrow R^+$ justifying the \"negative\" log-likelihood. Please check.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors design a framework to estimate the uncertainties in the predictions of gradient boosting models, for both classification and regression. The framework contains several methods, some that use sub-sampling on data to calculate the estimation, and some that use sub-sampling on the trees within one single gradient boosting model (i.e. virtual ensemble) to calculate the estimation. The different methods reveal the trade-off between faster calculation and good uncertainty estimation. The authors conduct extensive empirical study to demonstrate the validity of the designed framework.

The reviewers agree that the paper is well-written on a very important topic of machine learning in practice. The authors have done a great job addressing the comments from the reviewers, including the comparison to random forest, and adding more motivating examples. The reviewers believe that the work marks a good starting point for addressing this important topic. Nevertheless, the reviewers have some concerns that the results are promising but not impressive yet, and the performance of the virtual ensemble is a bit discouraging. 

Decision: Accept (Poster)