Year: 2021

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 stateof-the-art results on tabular data. This work examines a probabilistic ensemblebased 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.

heading: 1 INTRODUCTION
text: Gradient boosting (Friedman, 2001) is a widely used machine learning algorithm that achieves stateof-the-art results on tasks containing heterogeneous features, complex dependencies, and noisy data: web search, recommendation systems, weather forecasting, and many others (Burges, 2010; Caruana & Niculescu-Mizil, 2006; Richardson et al., 2007; Roe et al., 2005; Wu et al., 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 predictive uncertainty in GBDT models. Uncertainty estimation is crucial for avoiding costly mistakes in 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 AI-pilot is confident in its ability to drive and when it is not to avoid a fatal collision. In financial forecasting and medical diagnostics, mistakes on the part of an AI forecasting or diagnostic system could either lead to large financial or reputational loss or to the loss of life. Crucially, both financial and medical data are often represented in heterogeneous tabular form — data on 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 neural network models (Gal, 2016; Malinin, 2019). Bayesian methods for tree-based models (Chipman et al., 2010; Linero, 2017) have also been widely studied in the literature. However, this research did not explicitly focus on studying uncertainty estimation and its applications. Some related work was
∗All authors contributed equally and are listed in alphabetical order.
done by Coulston et al. (2016); Shaker & Hüllermeier (2020), who examined quantifying predictive 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 approaches based on tree ensembles.
While for classification problems GDBT models already return a distribution over class labels, for regression tasks they typically yield only point predictions. Recently, this problem was addressed in the NGBoost algorithm (Duan et al., 2020), where a GBDT model is trained to return the mean and variance of a normal distribution over the target variable y for a given feature vector. However, such models only capture data uncertainty (Gal, 2016; Malinin, 2019), also known as aleatoric uncertainty, which arises due to inherent class overlap or noise in the data. However, this does not quantify uncertainty due to the model’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 uncertainty (Gal, 2016; Malinin, 2019). One class of approaches for capturing knowledge uncertainty are Bayesian ensemble methods, which have recently become popular for estimating predictive uncertainty in neural networks (Depeweg et al., 2017; Gal & Ghahramani, 2016; Kendall et al., 2018; Lakshminarayanan et al., 2017; Maddox et al., 2019; Smith & Gal, 2018). A key feature of ensemble approaches is that they allow overall uncertainty to be decomposed into data uncertainty and knowledge uncertainty within an interpretable probabilistic framework (Depeweg et al., 2017; Gal, 2016; Malinin, 2019). Ensembles are also known to yield improvements in predictive performance.
This work examines ensemble-based uncertainty-estimation for GBDT models. The contributions are as follows. First, we consider generating ensembles using both classical Stochastic Gradient Boosting (SGB) as well as the recently proposed Stochastic Gradient Langevin Boosting (SGLB) (Ustimenko & Prokhorenkova, 2020). 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 a virtual ensemble using only one gradient boosting model, significantly reducing the computational complexity. Third, to understand the attributes of using ensembles-based 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 methods have been implemented within the open-source CatBoost library. The code of our experiments is publicly available at https://github.com/yandex-research/GBDT-uncertainty.

heading: 2 PRELIMINARIES
text: Uncertainty Estimation via Bayesian Ensembles In this work we consider uncertainty estimation within the standard Bayesian ensemble-based framework (Gal, 2016; Malinin, 2019). Here, model parameters θ are considered random variables and a prior p(θ) is placed over them to compute a posterior p(θ|D) via Bayes’ rule:
p(θ|D) = p(D|θ)p(θ) p(D) . (1)
where D = {x(i), y(i)}Ni=1 is the training dataset. Each set of parameters can be considered a 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.
Consider an ensemble of probabilistic models {P(y|x;θ(m))}Mm=1 sampled from the posterior p(θ|D). Each model P(y|x,θ(m)) yields a different estimate of data uncertainty, represented by the entropy of its predictive distribution (Malinin, 2019). Uncertainty in predictions due to knowledge uncertainty is expressed as the level of spread, or “disagreement”, of models in the ensemble (Malinin, 2019). Note that exact Bayesian inference is often intractable, and it is common to consider either an explicit or implicit approximation q(θ) to the true posterior p(θ|D). While a range of approximations has been explored for neural network models (Gal & Ghahramani, 2016; Lakshminarayanan et al., 2017; Maddox et al., 2019)1, to the best of our knowledge, limited work
1A full overview is available in (Ashukha et al., 2020; Ovadia et al., 2019).
has explored Bayesian inference for gradient-boosted trees. Given p(θ|D), the predictive posterior of the ensemble is obtained by taking the expectation with respect to the models in the ensemble:
P(y|x,D) = Ep(θ|D) [ P(y|x;θ) ] ≈ 1
M M∑ m=1 P(y|x;θ(m)), θ(m) ∼ p(θ|D) . (2)
The entropy of the predictive posterior estimates total uncertainty in predictions: H [ P(y|x,D) ] = EP(y|x,D) [ − ln P(y|x,D) ] . (3)
Total uncertainty is due to both data uncertainty and knowledge uncertainty. However, in applications like active learning (Kirsch et al., 2019) and out-of-domain detection it is desirable to estimate knowledge uncertainty separately. The sources of uncertainty can be decomposed by considering the mutual information between the parameters θ and the prediction y (Depeweg et al., 2017):
I [ y,θ|x,D ]︸ ︷︷ ︸ Knowledge Uncertainty = H [ P(y|x,D) ]︸ ︷︷ ︸ Total Uncertainty −Ep(θ|D) [ H[P(y|x;θ)] ]︸ ︷︷ ︸ Expected Data Uncertainty
≈ H [ 1 M M∑ m=1 P(y|x;θ(m)) ] − 1 M M∑ m=1 H[P(y|x;θ(m))] . (4)
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(y|x;θ(m))}Mm=1 over continuous-valued target y ∈ R, 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:
Vp(y|x,D)[y]︸ ︷︷ ︸ Total Uncertainty
= Vp(θ|D) [ Ep(y|x,θ)[y] ]︸ ︷︷ ︸ Knowledge Uncertainty +Ep(θ|D) [ Vp(y|x,θ)[y] ]︸ ︷︷ ︸ Expected Data Uncertainty . (5)
This is conceptually similar to the decomposition (4) obtained via mutual information. For an ensemble of probabilistic regression models which parameterize the normal distribution, and where each models yields a mean and standard-deviation, the total variance can be computed as follows:
Vp(y|x,D)[y]︸ ︷︷ ︸ Total Uncertainty ≈ 1 M M∑ m=1 [( M∑ m=1 µm M ) − µm ]2 ︸ ︷︷ ︸
Knowledge Uncertainty
+ 1
M M∑ m=1
σ2m︸ ︷︷ ︸ Expected Data Uncertainty , {µm, σm} = f(x;θ(m)). (6)
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-invariant, which can cause issues is the scale of prediction on in-domain and out-of-domain data is very different.
Gradient boosting is a powerful machine learning technique especially useful on tasks containing heterogeneous features. It iteratively combines weak models, such as decision trees, to obtain more accurate predictions. Formally, given a dataset D and a loss function L : R2 → R, the gradient boosting algorithm (Friedman, 2001) iteratively constructs a model F : X → R to minimize the empirical risk L(F |D) = ED[L(F (x), y)]. At each iteration t the model is updated as:
F (t)(x) = F (t−1)(x) + ϵh(t)(x) , (7)
where F (t−1) is a model constructed at the previous iteration, h(t)(x) ∈ H is a weak learner chosen from some family of functionds H, and ϵ is learning rate. The weak learner h(t) is usually chosen to approximate the negative gradient −g(t)(x, y) := −∂L(y,s)∂s ∣∣ s=F (t−1)(x) :
h(t) = argmin h∈H
ED [( − g(t)(x, y)− h(x) )2] . (8)
A weak learner h(t) is associated with parameters ϕ(t) ∈ Rd. We write h(t)(x,ϕ(t)) 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 Rj of the tree is assigned to a value, which is the estimated response y in the corresponding region. We can write h(x,ϕ(t)) = ∑d j=1 ϕ (t) j 1{x∈Rj}, so the decision tree is a linear function of ϕ
(t). The final GBDT model F is a sum of decision trees (7) and the parameters of the full model are denoted by θ.
For classification tasks, a model yields estimates data uncertainty if it is trained via negative loglikelihood and provides a 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 al. (2020) via an algorithm called NGBoost (Natural Gradient Boosting), which allows estimating data uncertainty. NGBoost simultaneously estimates the parameters of a conditional distribution p(y|x,θ) over the target y given the features x, by optimizing a proper scoring rule. Typically, a normal distribution over y is assumed and negative log-likelihood is taken as a scoring rule. Formally, given an input x, the model F predicts two parameters of normal distribution - the mean µ and the logarithm of the standard deviation log σ. The loss function is the expected negative log-likelihood:2
p(y|x,θ(t)) = N (y|µ(t), σ(t)), {µ(t), log σ(t)} = F (t)(x) .
L(θ|D) = ED[− log p(y|x,θ)] = − 1
N N∑ i=1 log p(y(i)|x(i),θ) .
(9)
(10)
Note that θ denotes the concatenation of two parameter vectors used to predict µ and log σ.

heading: 3 GENERATING ENSEMBLES OF GDBT MODELS
text: As discussed in Section 2, knowledge uncertainty can be estimated by considering an ensemble of models {p(y|x;θ(m))}Mm=1 sampled from the posterior p(θ|D). The level of diversity or “disagreement” 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 is to consider several independent models generated via Stochastic Gradient Boosting (SGB). Stochasticity is added to GBDT models via random subsampling of the data at every iteration (Friedman, 2002). 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 fraction of chosen objects is called sample rate. This implicitly injects noise into the learning process, effectively inducing a distribution q(θ) over such models. Thus, an SGB ensemble is an ensemble of independent models {θ(m)}Mm=1 built according to SGB with different random seeds for subsampling data. Unfortunately, there are no guarantees on how well the distribution q(θ) estimates the true posterior p(θ|D). SGLB ensembles Remarkably, there is a way to sample GBDT models from the true posterior p(θ|D) via a recently proposed Stochastic Gradient Langevin Boosting (SGLB) algorithm (Ustimenko & Prokhorenkova, 2020). SGLB combines gradient boosting with stochastic gradient Langevin dynamics (Raginsky et al., 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 (8) is replaced by:
h(t) = argmin h∈H
ED [( −g(t)(x, y)− h(x,ϕ) + ν )2] , ν ∼ N ( 0, 2
βϵ I|D|
) , (11)
where β is the inverse diffusion temperature and I|D| is an 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 (7) is modified as:
F (t)(x) = (1− γϵ)F (t−1)(x) + ϵh(t)(x,ϕ(t)) , (12) 2Since GBDT model is determined by θ, we use notation L(F |D) and L(θ|D) interchangeably.

heading: Last model
text: where γ is regularization parameter. If the number of all possible trees is finite (a natural assumption given that the training dataset is finite), then the SGLB parameters θ(t) at each iteration form a Markov chain that weakly converges to the stationary distribution, also called the invariant measure:
p∗β(θ) ∝ exp(−βL(θ|D)− βγ∥Γθ∥22) , (13)
where Γ = ΓT > 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 (13) to prove the global convergence, we apply this to enable sampling from the true posterior. For this purpose, we set β = |D| and γ = 12|D| . For the negative log-likelihood loss function (10) the invariant measure (13) can be expressed as:
p∗β(θ) ∝ exp ( log p(D|θ)− 1
2 ∥Γθ∥22
) ∝ p(D|θ)p(θ) , (14)
which is proportional to the true posterior distribution p(θ|D) under Gaussian prior p(θ) = N (0,Γ). Thus, an SGLB ensemble is an ensemble of independent models {θ(m)}Mm=1 generated according to the SGLB algorithm using different random seeds. In this case, asymptotically, models are sampled from the true posterior p(θ|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 a 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 is possible since a GBDT model is itself an ensemble of trees. However, in contrast to random forests formed by independent trees (Shaker & Hüllermeier, 2020), the sequential nature of GBDT models implies that all trees are dependent and individual trees cannot be considered as separate models. Hence, we use “truncated” sub-models of a single GBDT model as elements of an ensemble, as illustrated in Figure 1. Notably, a 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 we can guarantee asymptotically sampling from the true posterior p(θ|D).
Each “truncated” model is described by the vector of parameters θ(t). As the parameters θ(t) at each iteration of the SGLB algorithm form a Markov chain that weakly convergences to the stationary distribution (14), we can consider using them as an ensemble of models. However, unlike parameters taken from different SGLB trajectories, these will have a high degree of correlation, which adversely affects the ensemble’s quality. This problem can be overcome by retaining only every K-th set of parameters. Formally, fix K ≥ 1 and consider a set of models ΘT,K = {θ(Kt), [ T 2K ] ≤ t ≤ [ T K ] }, i.e., 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 us to reduce the correlation between samples from the SGLB Markov chain. Furthermore, we do not include to the ensemble the models θ(t) with t < T/2 as (14) holds only asymptotically. The set of M = [ T 2K ] models ΘT,K is called a virtual ensemble. Note that virtual ensembles behave similarly to true ensembles in the limit (for large K and T ).
Importantly, we can compute the prediction of ΘT,K with the same computation time as one θ(T ). Indeed, when computing the prediction of one model, we have to sum up the predictions made by individual trees. To get the virtual ensemble, we only have to store the partial sums. For SGLB, we also have to account for regularization (12). Formally, according to (12), for SGLB we have
θ(T ) = ∑T
i=1 ϵ(1 − γϵ)T−iϕ(i), where (1 − γϵ)T−i appears due to shrinkage. While computing θ(T ) we store the partial sums θ(T )≤t = ∑t i=1 ϵ(1 − γϵ)T−iϕ(i). Then, any model θ(t) from ΘT,K can easily be obtained from the stored values:
θ(t) = t∑ i=1 ϵ(1− γϵ)t−iϕ(i) = (1− γϵ)t−Tθ(T )≤t . (15)

heading: 4 ANALYSIS ON SYNTHETIC DATA
text: In this section, we analyze how ensemble algorithms discussed in Section 3 perform on synthetic data. The aim is to understand the attributes of ensembles of GBDT models for estimating data and knowledge uncertainty in a controllable setting.
GBDT models are usually applied to tabular data, where features are often categorical. Hence, we first generate a dataset with each example described by two categorical features x1, x2 with 9 values each, resulting in 81 possible combinations. The target depends on the features as y = a(x1, x2) + ε(x1, x2), where ε(x1, x2) ∼ N (0, b(x1, x2)) and a(x1, x2), b(x1, x2) are some deterministic functions. The values for a(x1, x2) are randomly generated according to the uniform distribution over [0, 1]. The values for b(x1, x2) are shown on Figure 2(a). We generate a heartshaped dataset with this distribution: inside the heart (white region on Figure 2(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 2(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 no training data constrain the models’ behavior there. Second, Figure 2(c) 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 is perfect, as there is no trace of the original heart border.
To further analyze ensembles of GBDT models, we apply them to a two-dimensional classification task with continuous-valued features. We consider a 3-class spiral dataset shown on Figure 3(a); and this setting is much harder for gradient boosted trees.3 Figure 3(b) shows the total uncertainty estimated with SGLB ensemble, while Figure 3(c) 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 3(c). A possible reason is the fact that for real-valued features, near the class borders, the splitting values may vary across all models in the ensemble, resulting in nonzero estimates of knowledge uncertainty due to decision-boundary ‘jitter’.
3To partially mitigate the difficulties, we use coordinates in rotated axes and radius as additional features.
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 to total uncertainty. Thus, we expect that while knowledge uncertainty is especially useful for detecting anomalous inputs, the proposed approaches will contribute little to error detection on top of estimates of data uncertainty provided by single models.
Finally, on Figure 4, 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.

heading: 5 EXPERIMENTS ON CLASSIFICATION AND REGRESSION DATASETS
text: In this section, we evaluate the performance of ensembles of GBDT models on a range of classification and regression tasks, focusing on their ability to 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-the-art results in a variety of tasks (Prokhorenkova et al., 2018). Classification models yield a probability distribution over binary class labels, while regression models yield the mean and variance of the normal distribution, as discussed in Section 2. All models are trained by optimizing the negative log-likelihood.4 We consider SGB and SGBL single models as the baselines and examine all ensemble methods defined in Section 3. 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
4In Appendix A.1, we compare our implementation with the original NGBoost and Deep Ensembles in terms of NLL (negative log-likelihood) and RMSE. Our implementation has comparable performance to the existing methods.
space complexity as just one SGB or SGLB model. Hyper-parameters are tuned by grid search, for details see Appendix A.2.
We compare the algorithms on several classification and regression tasks (Gal & Ghahramani, 2016; Prokhorenkova et al., 2018), the description of which is available in Appendix A.3.
While not being the focus of the current research, Random Forest (RF) models are 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 Prediction-Rejection Ratio (PRR) (Malinin, 2019; Malinin et al., 2020), which measures 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 (AUCROC) (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 out-of-domain (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 (Graf et al., 2011). 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 at random from the set of all feature’s categories. Total and knowledge uncertainty are estimated via entropy of the predictive posterior (3) and mutual information (4) for classification models and via total variance and variance of the mean (5) for regression ones.
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 1 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 (Lakshminarayanan et al., 2017; Malinin, 2019; Malinin & Gales, 2019; Malinin et al., 2020). 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, as we have discussed in Section 4, for GBDT models, estimates of knowledge uncertainty obtained via the approaches considered here contribute little to estimates of total uncertainty.
In contrast, Table 1 shows that measures of knowledge uncertainty yield superior OOD detection performance compared to total uncertainty in terms of AUC-ROC, which is consistent with results for non-GBDT models (Malinin, 2019; Malinin & Gales, 2019; Malinin et al., 2020).5 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 ensembles, which is explained by the presence of strong correlations between the models in a 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 categorical features may have a noticeable effect on the diversity of vSGLB models, and our classification datasets contain categorical features.

heading: 6 CONCLUSION
text: This work examined principled, ensemble-based uncertainty-estimation for GBDT models. Two main approaches to generating ensembles of GDBT models, where each model is 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-
5Note that single models do not allow distinguishing between the types of uncertainty.
ploiting the ‘ensemble-of-trees’ nature of GBDT models. Properties of the estimates of total, data, and knowledge uncertainty derived from these ensembles were first analyzed on 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 error detection, as each model is already an ensemble of trees, they do yield useful measures of knowledge uncertainty, which enables outof-domain detection in both regression and classification tasks. Notably, measures of knowledge uncertainty, 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 between 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 at no additional computational and memory cost.

heading: ACKNOWLEDGMENTS
text: We would like to thank Ekaterina Ermishkina and Stanislav Kirillov for implementing the proposed methods within the CatBoost library.

heading: A EXPERIMENTAL SETUP

heading: A.1 OUR IMPLEMENTATION OF DATA UNCERTAINTY
text: As discussed in Section 2.2 of the main text, for regression we simultaneously predict the parameters µ and log σ of the Normal distribution. Similarly to NGBoost, we use the natural gradients. For our loss and parameterization, the natural gradient is:
g(t)(x, y) = ( µ(t−1) − y, 1
2 − 1 2
( y − µ(t−1)
σ(t−1)
)2 ) . (16)
At each step of the gradient boosting procedure, we construct one tree predicting both components of g(t), similarly to the MultiRMSE regime of CatBoost.6
Recall that for classification we optimize the logistic loss.
In Table 2, we compare our implementation with NGBoots (Duan et al., 2020) and Deep Ensembles (Lakshminarayanan et al., 2017) 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.

heading: A.2 PARAMETER TUNING
text: For all approaches, we use grid search to tune learning-rate in {0.001, 0.01, 0.1}, tree depth in {3, 4, 5, 6}. We fix subsample to 0.5 for SGB and to 1 for SGLB. This is done to avoid joint randomization effects of SGB sampling and SGLB noise in gradients. We also set diffusion-temperature = N and model-shrink-rate = 12N for SGLB.

heading: A.3 DATASETS
text: The datasets are described in Table 3. For regression, we use standard train/validation/test splits (UCI). For classification, we split the datasets into proportion 65/15/20 in train, validation, and test sets. For more details, see our GitHub repository.7

heading: A.4 STATISTICAL SIGNIFICANCE
text: For regression, we perform cross-validation to estimate statistical significance with paired t-test. In the corresponding tables, we highlight the approaches that are insignificantly different from the best one (p-value > 0.05).
6https://catboost.ai/docs/concepts/loss-functions-multiregression.html 7https://github.com/yandex-research/GBDT-uncertainty
For classification (and Year MSD), we 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.

heading: B ADDITIONAL EXPERIMENTAL RESULTS
text: In Table 4, we compare ensemble approaches with single models in terms of 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 difference is not 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 a similar conclusion from the results for RMSE and error rate.

heading: C COMPARISON WITH RANDOM FOREST
text: 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., 2016; Shaker & Hüllermeier, 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 et al., 2011). 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 are 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. Hence, for knowledge uncertainty we can 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 uncertainty 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 a stronger baseline. However, we expect a small difference between vRF and an ensemble of random forests, as there are, a priori, no correlations between trees both in a single model and across multiple RF models.
In Tables 5 and 6, we compare the predictive performance of random forests (both individual models and explicit ensembles of multiple models) to SGLB individual and ensemble models on classification and regression tasks. The results show that generally GBDT models outperform random forest models in terms of classification error rate and NLL. Note that we 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 to estimate data uncertainty, and therefore we can only obtain estimates of knowledge uncertainty.
Table 7 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, as we expected, for OOD detection vRF and RF give similar results. Thus, we conclude that for random forests, a virtual ensemble is a good and cheap alternative to the true one.

Review summaries:
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.