{'fraction_non_alphanumeric': 0.034242324681487975, 'fraction_numerical': 0.008213777242361187, 'mean_word_length': 4.98775956284153, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uncertainty in Gradient Boosting via Ensembles

Gradient boosting is a powerful machine learning technique that is particularly successful for tasks containing heterogeneous features and noisy data. While gradient boosting classification models return a distribution over class labels, regressions models typically yield only point predictions. However, for many practical, high-risk applications, it is also important to be able to quantify uncertainty in the predictions to avoid costly mistakes. In this work, we examine a probabilistic ensemble-based framework for deriving uncertainty estimates in the predictions of gradient boosting classification and regression models. Crucially, the proposed approach allows the total uncertainty to be decomposed into \textit{data uncertainty}, which comes from the complexity and noise in data distribution, and \textit{knowledge uncertainty}, coming from the lack of information about a given region of the feature space. Two approaches for generating ensembles are considered: Stochastic Gradient Boosting (SGB) and Stochastic Gradient Langevin Boosting (SGLB). Notably, SGLB also enables the generation of a \emph{virtual} ensemble via only one gradient boosting model, which significantly reduces complexity. Experiments on a range of regression and classification datasets show that ensembles of gradient boosting models yield improved predictive performance, and measures of uncertainty successfully enable detection of out-of-domain inputs.


Introduction
Gradient boosting [1] is a widely used machine learning algorithm which 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 [2,3,4,5,6,7]. It iteratively combines weak models, such as decision trees, to obtain more accurate predictions.
While gradient boosting classification models return a distribution over class labels, gradient boosting regressions models typically yield only point predictions for a given feature vector. However, for many practical, high-risk applications, it is important to be able to quantify uncertainty in the predictions to avoid costly mistakes. For example, the cost of a mistake is extremely high for self-driving vehicles and in medical as well as financial applications. Recently, this problem was addressed in the NGBoost algorithm [8], where gradient boosted decision trees (GBDT) are trained to return the mean and variance of a normal distribution over the target variable y for a given feature input. However, such models only capture data uncertainty [9,10], a.k.a. aleatoric uncertainty, which arises due to inherent class overlap or noise in the data. However, this doesn't capture 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, called knowledge or epistemic uncertainty [9,10]. One class of approaches for capturing knowledge uncertainty are Bayesian ensemble methods, which have recently become popular for estimating predictive uncertainty in neural networks [11,12,13,14,15,16]. 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 [11,9,10].
This work examines ensemble-based uncertainty-estimation for GBDT models. We consider generating ensembles using both classical Stochastic Gradient Boosting (SGB) as well as the recently proposed Stochastic Gradient Langevin Boosting (SGLB) [17]. Importantly, SGLB allows us to guarantee that asymptotically the models are sampled from the true Bayesian posterior. Moreover, with SGLB we can construct a virtual ensemble using only one gradient boosting model, significantly reducing the computational complexity. Properties of ensembles of GBDT models are examined both on a synthetic dataset and on a range of regression and classification datasets. Our results show that ensembles of gradient boosting models yield improved predictive performance, and, most importantly, enable detection of errors and out-of-domain inputs.
2 Background and related work 2

.1 Uncertainty Estimation via Bayesian Ensembles
This work describes ensemble-based uncertainty estimation within a Bayesian framework. Here, model parameters θ are considered random variables and a prior p(θ) is placed over them to compute a posterior p(θ|D) via Bayes' rule: 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) )} M m=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 [10]. Uncertainty in predictions due to knowledge uncertainty is expressed as the level of spread, or "disagreement", of models in the ensemble [10]. 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 [12,14,15] 1 , to the best of our knowledge, limited work has explored Bayesian inference for gradient-boosted trees. Given the model posterior p(θ|D), the predictive posterior of the ensemble is obtained by taking the expectation with respect to the models in the ensemble: The entropy of the predictive posterior estimates total uncertainty in predictions: Total uncertainty in the predictions is due to both data uncertainty and knowledge uncertainty. In applications like active learning [20] and out-of-distribution 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 [11]: 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) )} M m=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: This is conceptually similar to the decomposition (4) obtained via mutual information. 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.

Gradient boosting
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 : R 2 → R, the gradient boosting algorithm [1] iteratively constructs a model F : X → R to minimize the empirical risk At each iteration t the model is updated in an additive manner: 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 functions H and is the learning rate. The weak learner h (t) is usually chosen : A weak learner h (t) is associated with a vector of parameters φ (t) ∈ R d . We write h(x, φ (t) ) to reflect this dependence. The set of weak learners H is often formed by shallow decision trees, which are models built by a recursive partition of the feature space into disjoint regions called leaves. Each leaf of the tree is assigned to a value, which is an estimate of the response y in the corresponding region. If we denote by R j the disjoint regions corresponding to the leaves of the tree, we can write h(x, φ (t) ) = The final GBDT model F is a sum of decision trees obtained according to (6). Thus, it is a linear model of leaf values. The parameters of the full GBDT model are denoted by θ. Formally, to obtain the vector θ, we take · φ (t) for all t, remove duplicates by summing the vectors corresponding to trees with the same leaf regions R j , and concatenate the obtained vectors. The parameters of the model F (t) obtained at t-th iteration are denoted by θ (t) . Thus, we have θ (t) = t i=1 · φ (i) (formally, here we extend the dimensionality of φ (t) by placing zeros for non-present leaves).
Traditionally, GBDT regression models yield point predictions, and there has been little research devoted to estimating predictive uncertainty. Recently, this issue was addressed via an algorithm called NGBoost (Natural Gradient Boosting) [8], 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. While typically a normal distribution over y is assumed and negative log-likelihood is taken as a scoring rule, it is possible to consider alternative distributions and scoring rules. Formally, given a vector of features x, the model F now 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 Note that θ denotes the concatenation of two parameter vectors used to predict µ and log σ. To make gradient steps invariant to reparametrization, NGBoost adopts natural gradients. At each iteration, two new base learners predicting the components of the gradient (see (7)) are added to the model.
Finally, note that for classification tasks using a standard logistic loss allows to optimize negative log-likelihood and provides a distribution over class labels.
3 Generating ensembles of GDBT models While methods like NGBoost are able to capture data uncertainty, they do not provide estimates of knowledge uncertainty. As discussed in Section 2.1, a natural approach to estimate knowledge uncertainty is to consider an ensemble of models {p(y|x; θ (m) )} M m=1 sampled from the posterior p(θ|D). The level of "disagreement" between the models would estimate the knowledge uncertainty. The only question is how to sample an appropriate ensemble from p(θ|D). In this section, a range of approaches to generating an ensemble of GDBT models is explored. We emphasize that this section discusses ensembles of GBDT models, where a single GBDT model is itself an ensemble of trees.

SGB ensembles
A straightforward way to generate an ensemble is to consider several independent models generated by the standard SGB procedure. Stochasticity is added to GBDT models via random subsampling of the data at every iteration [21]. Specifically, at each iteration of (7) 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. However, there are no guarantees on how well this distribution estimates the true posterior p(θ|D). Thus, an SGB ensemble is an ensemble of independent models {θ (m) } M m=1 built according to stochastic NGBoost algorithm using different random seeds for sub-sampling data.

SGLB ensembles
Remarkably, there is a way to sample GBDT models from the true posterior p(θ|D) via recently proposed Stochastic Gradient Langevin Boosting (SGLB) algorithm [17]. SGLB combines gradient boosting with stochastic gradient Langevin dynamics [22] in order to achieve convergence to the global optimum even for non-convex loss functions. The algorithm is quite simple, it has two differences compared with SGB. Firstly, Gaussian noise is excplicitly injected into the gradients (7): 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. The diffusion temperature controls the amount of noise and reflects the level of exploration. Secondly, the update (6) is modified as: 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 for Markov chain which weakly converges to the stationary distribution, also called the invariant measure: where Γ = Γ T > 0 is an implicitly defined regularization matrix which depends on a particular tree construction algorithm [17].
In [17], this property was used to show that for large β, the invariant measure p * β (θ) concentrates around the global optimum of L(θ|D). In this work, we use the weak convergence to (12) to enable sampling from the true posterior. For this purpose, we set β = |D| and γ = 1 2|D| . For the negative log-likelihood loss function (9) the invariant measure (12) can be expressed as: 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) } M m=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 SGL ensembles yield estimates of knowledge uncertainty via approaches discussed in section 2.1, they require M times larger time and space complexity than a single model, which is a significant overhead. Consequently, to estimate knowledge uncertainty one has to either significantly increase complexity or sacrifice the quality by reducing the number of training iterations. Thus, we introduce virtual ensembles as an approach to generate an ensemble using only one SGLB model.
As the parameters θ (t) at each iteration of the SGLB algorithm form a Markov chain which weakly convergences to the stationary distribution, 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 with each other, which adversely affects the quality of the ensemble. This 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 2 ≤ 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. Furthermore, we do not consider models with t < T /2 as (13) holds only asymptotically. The set of models Θ T,K is called a virtual ensemble. Choosing larger values of K allows us to reduce the correlation between samples from the SGLB Markov chain. Note that in the limit (for large K and T ) virtual ensembles behave similarly to true ensembles. Thus, a virtual ensemble can be considered as an ensemble of M = T 2K models. Moreover, we can compute Θ T,K with the same computation time as one θ (T ) . According to (11), for SGLB we have T −i appears due to shrinkage. While computing θ (T ) we store the partial sums θ Then, any model θ (t) from Θ T,K can easily be obtained from the stored values:

Experiments on Synthetic Data
In this section, we analyse all ensemble algorithms discussed in section 3 on synthetic data. The aim is to understand the specifics of ensembles of GBDT models for estimating data and knowledge uncertainty in a simple setting. We consider two one-dimensional datasets -one where variance grows with |x|, and one where variance decreases with |x|, as shown in Figures 1(a) and 1(d). The inputs are distributed as x ∼ N (0, 25) in the interval [-15,15], such that the density of elements is high at the center of the interval and small at the boundary. SGB and SGLB ensembles consist of 10 models of 1K trees each. The vSGLB ensemble is obtained from one SGLB model with T = 10K trees and K = 500 interval, which has the same time and space complexity as the true SGLB ensemble.
First, we analyze data uncertainty. We consider the expected variance of the models in an ensemble, a measure of data uncertainty given by (5), in the interval x ∈ [− 25,25]. We want to see how the predicted variance agrees with the true variance both in the region where training data is available ([−15, 15]) and outside of it. 3 We expect that this estimate of data uncertainty will capture the true variance of the data distribution well in-domain, and no particular behavior is expected out-of-domain. Figure 1(b) illustrates that when variance grows with |x|, all models predict data uncertainty well in the interval [−15, 15] (in-domain). Out-of-domain, all models predict a constant variance, which slightly differs among the models. Due to the nature of GBDT for such simple one-dimensional data, if a feature value is smaller or larger than ones in the training dataset, then the predicted value will be the same as for the closest training example. Due to this property, the predicted out-of-domain data uncertainty is high. If variance decreases with |x|, one may expect the opposite effect. However, as Figure 1(e) shows, the predicted data uncertainty follows the data distribution in the interval [−10, 10], but then becomes large near the boundary of [− 15,15]. This happens because the density of training points is small in that interval and so the variance becomes overestimated. As a result, even in this case we get large out-of-domain data uncertainty. This experiment gives us an intuition why in GBDT models yield large estimates of data uncertainty far from the training data. On

Experiments on classification and regression datasets
In this section, we compare performance of single GBDT models and their ensembles on a range of classification and regression tasks: we compare their predictive performance in terms of negative log-likelihood and error-rate/RMSE as well as their ability to detect errors and out-of-domain inputs.
Our implementation of all GBDT models is based on the CatBoost library which is known to achieve state-of-the art results in a variety of tasks [23]. Classification models yield a probability distribution over binary class labels, while the regression models yield the mean and variance of the normal distribution, as discussed in Section 2.2. All models are trained by optimizing the negative loglikelihood. 4 We consider both SGB and SGBL single models as the baseline and examine all ensemble methods defined in Section 3. Ensembles of SGB and SGLB models consist of 10 independent (with different seeds) models with 1K trees each. The virtual ensemble vSGLB is obtained from one model with 1K trees, where each 50th model from the interval [500, 1000] is added to the ensemble. Thus, vSGLB has the same computational and space complexity as just one SGB or SGLB model. Hypter-parameters are tuned by random-search, for details see Appendix A.2. 5 We compare the algorithms on several classification and regression tasks [12,23], the description of which is available in appendix together with additional experimental results. In Tables 1 and 2, we highlight the approaches that are insignificantly different from the best one (p-value > 0.05). Details of how statistical significance is computed are provided in Appendix A.4. In Table 1, 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 many 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 similar conclusion from the results for RMSE and error rate: there is ensembling yields an advantage, but it is not so significant. Surprisingly, for NLL optimization virtual ensembling performed better than single models indicating that SGLB can benefit from using a proper re-weighting of trees which simulates an ensemble.
Having established that ensemble yields marginal improvements in predictive performance, we analyze whether measures of total and knowledge uncertainty can be used to detect errors and out-of-domain inputs. Error detection and rejection based on measures of uncertainty is assessed via the Prediction-Rejection Ratio (PRR) [10,24], which measures how well uncertainty estimates correlate with errors and rank-order them. Best value is 100, random is 0. Out-of-domain (OOD) detection is assessed via area under the ROC curve (AUR-ROC) [25]. For OOD detection we need an OOD test-set. However, obtain a 'real' OOD dataset 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 Naval dataset to get out-of-domain (OOD) ones. For the Naval dataset itself, we sample OOD from the horizontally stacked Kin8nm and Protein datasets. Categorical features are sampled from a uniform distribution.
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).
Test errors can occur due to both data and knowledge uncertainty, so we expect that ranking elements by total uncertainty would give better values of PRR. Table 2 shows that measures of total uncertainty consistently yield better PPR results across all classification and regression datasets. This is consistent with results obtained for ensembles of neural networks models [14,10,26,24]. However, ensembles do not outperform single models. We believe this occurs for two reasons. Firstly, due to the additive nature of boosting (GDBT models are already ensembles), as is discussed above. Secondly, as discussed in Section 4: for GBDT models, data uncertainty is overestimated in regions of small density of data-points, which naturally leads to larger uncertainty on outliers. Table 2 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 [10,26,24]. 6 The results also show that SGB and SGLB ensembles performed almost equally well, with SGLB having marginally better results. At the same time, virtual ensembling (vSGLB) performed consistently worse (with one exception) than SGB/SGLB ensembles, which is explained by the presence of auto-correlations between the models in a virtual ensemble. However, in all classification tasks, estimates of knowledge uncertainty provided by vSGLB nevertheless outperform uncertainty estimates derived from single SGB and SGLB models. This shows that for classification tasks 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.

Conclusion
This work examines principled, ensemble-based uncertainty-estimation for Gradient Boosted Decision Tree (GDBT) models. Three approaches to generating ensembles of GDBT models, where each model is itself an ensemble of trees, are considered -SGB, SGLB, and virtual SGLB. Properties of the estimates of total, data and knowledge uncertainty derived from these ensembles are first analyzed on a synthetic dataset, where it is shown that due to the nature of decision trees and the additive nature of boosting, estimates of data uncertainty derived from a single GDBT model may already be estimates of total uncertainty. Further experiments on a wide range of classification and regression datasets show that while ensembles of GDBT models do not offer much advantage in terms of improved predictive performance or error detection as each model is already an ensemble of trees. However, they do yield useful measures of knowledge uncertainty, which enables out-of-domain detection both in regression and classification tasks. It is also shown that while there is little practical difference between SGB and SGLB ensembles, vSGLB performs noticeably worse. However, for classification tasks vSGLB still yields useful measures of knowledge uncertainty, using only a single SGLB model. Notably, these measures of knowledge uncertainty achieve far better OOD detection performance than measures of total uncertainty obtained from a single model. Thus, vSGLB allows us to derive the full benefits of an ensemble at the computational and memory cost of a single model.

Broader Impact
Uncertainty estimation enables safer and more reliable machine learning models. This is especially important in applications associated with a high degree of risk. Notably, in many applications, especially those associated with heterogeneous and noisy data, Gradient Boosted Decision Tree models outperform neural networks at a fraction of the computational cost. Despite their usefulness, most work in uncertainty estimation has avoided GDBT models. Thus, this work represents an important step forward in improving the safety of applications that rely on GDBT models by providing principled, ensemble-based uncertainty estimations. Clearly, this benefits the ML community at large and does not disadvantage anyone. However, costly mistakes can still occur if the provided estimates of uncertainty are poor, which highlights the necessity for further research in this area.
At each step of the gradient boosting procedure, we construct one tree predicting both the components of g t , similarly to the MultiRMSE regime of CatBoost. 7 Recall that for classification we optimize the logistic loss.
In Table 3, we compare our implementation with NGBoots [8] and Deep Ensembles [14] on regression datasets. The best results are highlighted.

A.4 Statistical significance
For regression, we use standard train/validation/test splits [33] and 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).
For classification (and the Years regression dataset) we split the datasets in proportion 65/15/20 in train, validation, and test sets. In this case, we measure statistical significance for NLL and error/RMSE on the test test and in the corresponding tables the approaches that are insignificantly different from the best one are highlighted. For PRR and AUC-ROC results (for classification and Years) we highlight the best value. Tables 5 and 6 extend the corresponding tables from the main text to all considered datasets.