Instance-Based Uncertainty Estimation for Gradient-Boosted Regression Trees
Authors: Jonathan Brophy
Daniel Lowd
Venue: NeurIPS 2022 Accept (2022)
Keywords: uncertainty estimation
gradient-boosted regression trees
ibug
probabilistic regression
instance-based learning
tree-ensemble kernel

Abstract: Gradient-boosted regression trees (GBRTs) are hugely popular for solving tabular regression problems, but provide no estimate of uncertainty. We propose Instance-Based Uncertainty estimation for Gradient-boosted regression trees (IBUG), a simple method for extending any GBRT point predictor to produce probabilistic predictions. IBUG computes a non-parametric distribution around a prediction using the $k$-nearest training instances, where distance is measured with a tree-ensemble kernel. The runtime of IBUG depends on the number of training examples at each leaf in the ensemble, and can be improved by sampling trees or training instances. Empirically, we find that IBUG achieves similar or better performance than the previous state-of-the-art across 22 benchmark regression datasets. We also find that IBUG can achieve improved probabilistic performance by using different base GBRT models, and can more flexibly model the posterior distribution of a prediction than competing methods. We also find that previous methods suffer from poor probabilistic calibration on some datasets, which can be mitigated using a scalar factor tuned on the validation data. Source code is available at https://github.com/jjbrophy47/ibug.

Instance-Based Uncertainty Estimation for Gradient-Boosted Regression Trees
Jonathan Brophy" University of Oregon j brophy@es. uoregon edu
Daniel Lowd University of Oregon lowd0cs, uoregon edu
Abstract
Gradient-booste regression trees (GBRTs) are hugely popular for solving tabular regression problems, but provide no estimate of uncertainty. We propose Instance- Based Uncertainty estimation for Gradient-boosted regression trees (IBUG), a simple method for extending any GBRT point predictor to produce probabilistic predictions. IBUG computes a non-parametric distribution around a prediction using the k-nearest training instances, where distance is measured with tree- ensemble kernel. The runtime IBUG depends on the number of training examples at each leaf in the ensemble, and can be improved by sampling trees training instances. Empirically, we find that IBUG achieves similar or better performance than the previous state-of-the the-ttte-tt across 22 benchmark regression datasets. We also find that IBUG can achieve improved probabilistic performance by using different base GBRT models, and more flexibly model the posterior distribution of prediction than competing methods. We also find that previous methods suffer from poor probabilistic calibration on some datasets, which can be mitigated using a scalar factor tuned on the validation data. Source code is available at https; //gi cttphhuu.oommjjjjij//j/ //tpttthtc.c//////rrpr////////b/ /tt.o////ooooo//////////gg
Introduction
Despite the impressive success of deep learning models on unstructured data (e.g., images, audio, text), gradient-boosted trees (26) remain the preferred choice for tabular structured data [52]. In fact, Kaggle CEO Anthony Goldbloom recently described gradient- boossed trees as the most "glaring difference" between what is used Kaggle and what "fashionable in academia" [34).
Our focus on tabular data for regression tasks, which vary widely from financial M and retail- product forecasting 43 to weather 29 28) and clinic-mortality prediction [6] Gradient-boosted
regression trees (GBRTs) are known to make accurate point predictions [42] but provide no estimate of the prediction uncertainty, which is desirable for both forecasting practitioners [9 68 and the
explainable AI (XAI) community 225 69 2 in general. Recently. Duan et al. [22], Sprangers et al.
[64]. and Malinin al. [44] introduced NGBoost, PGBM, and CBU (CatBoost [52 with uncertainty),
respectively, new gradient boosting algorithms that provide state-of-the-arr probabilistic predictions. point-predictor, and PGBM and CBU are limited in
However, NGBoost tends underperform
the types of distributions they can use to model the output.
We introduce simple yet effective method for enabling any GBRT point-prediction model to produce probabilistic predictions. Our proposed approach, Instance- Uncertainty estimation for Gradient-boosee regression trees (IBUG), has two key components: 1) We leverage the fact that GBRTs accurately model the conditional mean and use this point prediction as the mean in a probabilistic forecast; and 2) We identify the & training examples with the greatest affinity to the
https::/www.jonattaaitt
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

target instance and use these examples to estimate the uncertainty of the target prediction. We define the affinity between two instances as the number of times both instances appear the same leaf throughout the ensemble. Thus, our method acts as wrapper around any given GBRT model.
In experiments on 21 regression benchmark datasets and one synthetic dataset, demonstrate the effectiveness of IBUG to deliver on par or improved probabilistic performance as compared to existing state-of-the-arr methods while maintaining state-of- -ft---rrtt We also show that probabilistic predictions can be improved by applying IBUG to different GBRT models, something that NGBoost and PGBM cannot do. Additionally, IBUG can use the training instances closest to the target example to directly model the output distribution using any parametric or non paraamemttiic distribution, something NGBoost, PGBM, and CBU cannot do. Finally, we show that sampling trees dramatically improves runtime efficiency for computing training example affinities without having a significant detrimental impact on the resulting probabilistic predictions, allowing IBUG to scale to larger datasets.
performance.
training-example
2 Notation & Background
We assume an instance space X' S R2 and target space Y C R. Let D = {(I;; yi) B/ be a training dataset in which each instance x; E X is a p-dimensional vector (x²)²=1 and y/: E y
2.1 Gradient-Boosted Regression Trees
Gradient-boosting [26] is a powerful machine-leaminn algorithm that iteratively adds weak learners to construct model f X' - IR that minimizes some empirical risk L R R R. The model is defined by a recursive relationship: fo(x) = ...... f((z) = f(-1(z) + n mz(x) in which fu is the base learner, 7 is initial estimate, f. is the model at iteration t. m, is the weak learner added during iteration / to improve the model, and is the learning rate.
Gradient-boosted regression trees (GBRTs) typically choose E to be the mean squared error (MSE), as J. > 84 (mean output of the training instances), and regression trees as weak learn- ers. Each weak learner is typically chosen to approximate the negative gradient [44]: m, arg minm. 1 E (-g m²x;))² in which of = olgg( is the functional gradient of the ith training instance at iteration / with respect to y, = fc)(())
The weak learner at iteration recursively partitions the instance space into M, disjoint regions {r() ) Each region is called a leaf, and the parameter value for leaf j at tred"] t is typi- cally determined (given fixed structure) using one-step Newton-estimation method [36] of - -Eee g ( hi + A) in which T/- = {(.,, 3.) | x E r/ the instance set of leaf j for tree 4, ht is the second derivative of the ith training instance w.r.t. ft. and À is regularization constant. Thus, the output of m, can be written as follows: (x)
Me 1 0: 1 [xr E r!] in which 1 is the indicator function. The final GBRT model generates prediction for target example Ite by summing the values of the leaves Tte traverses across all T' iterations: tie ΣT mx(e)).
2.2 Probabilistic Regression
Our focus is on probabilistic regression-estimatie the conditional probability distribution P(ylar) for some target variable y given some input vector x E X. Unfortunately, traditional GBRT models only output scalar values. Under squared-error loss function, these scalar values can be interpreted as the conditional mean in a Gaussian distribution with some (unknown) constant variance. However, homoscedastieity a strong assumption and unknown constant variance has little value in a probabilistic prediction; thus, in order to allow heteroscedasticity, the predicted distribution needs at least two parameters to convey both the magnitude and uncertainty of the prediction 22
Natural Gradient Boosting (NGBoost) is a recent method by Duan et al. (2 that tackles the aforementioned problems by estimating the parameters of desired distribution using a multi- parameter boosting approach that trains a separate ensemble for each parameter of the distribution. NGBoost employs the natural gradient to be invariant to parameterization, but requires the inversion
We use the terms free and iteration interchangeably.

---

of many small matrices (each the size of the number of parameters) to do so. Empirically, NGBoost generates state-of-the-art probabilistic predictions, but tends to underperform as a point predictor.
More recently, Sprangers et al. (64] introduced Probabilistic Gradient Boosting Machines (PGBM), single model that optimizes for point performance, but also generate accurate probabilistic predictions. PGBM treats leaf values as stochastic random variables, using sample statistics to model the mean and variance of each leaf value. PGBM estimates the output mean and variance of target example using the estimated parameters of each leaf it is assigned to. The predicted mean and variance are then used as parameters in a specified distribution to generate a probabílistic prediction. PGBM has been shown to produce state-of-theear probabilistic predictions; however, computing the necessary leaf statistics during training can be computationally expensive, especially as the number of leaves in the ensemble increases (see $5.6). Also, since only the mean and variance are predicted for a given target example, PGBM is limited to distributions using only location and scale to model the output.
Finally, Malinin et al. [44] introduce CatBoost with uncertainty (CBU), method that estimates uncertainty using ensembles of GBRT models. Similar to NGBoost, multiple ensembles are learned to output the mean and variance. However, CBU also constructs a virtual ensemble-a set of overlapping partitions of the learned GBRT trees-to estimate the uncertainty of a prediction by taking the mean of the variances output from the virtual ensemble. Their approach uses recently proposed stochastic gradient Langevin boosting algorithm [72] to sample from the true posterior via the virtual ensmble (in the limit); however, their formulation of uncertainty limited only to the first and second moments, similar to PGBM.
To address the shortcomings of existing approaches, introduce simple method that performs well on both point and probabilistic performance, and can more flexibly model the output than previous approaches. Our method can also be applied any GBRT model, adding additional flexibility.
3 Instance-Based Uncertainty
Instance-based methods such as k-nearest neighbors have been around for decades and have been useful for many different machine learning tasks (50). However, defining neighbors based fixed metric like Euclidean distance may lead to suboptimal performance, especially as the dimensionality of the dataset increases. More recently, it has been shown that random forests can be used as an adaptive nearest neighbors method [18] 40) which identifies the most similar examples to a given instance using the learned model structure. This supervised tree kernel can more effectively measure the similarity between examples, and has been used for clustering [46) and local linear modeling [8]
as well as instance- and feature-based attribution explanations [5I), for example.
In this work, we apply the idea of a supervised tree kernel to help model the uncertainty of a given GBRT prediction. Our approach, -Bssed Uncertainty estimation for regression trees (IBUG), identifies the neighborhood of similar training examples to a target example using the structure of the GBRT, and then uses those instances generate a probabilistic prediction. IBUG works for any GBRT, and can more flexibly model the output than competing methods.
3.1 Identification of High-Affinity Neighbors
At its core. IBUG uses the k training examples with the largest affinity to the target example to model the conditional output distribution. Given a GBRT model f, we define the affinity between two examples simply as the number of times each instance appears in the same leaf across all trees in f. Thus, the affinity of the ith training example x; to a target example Ite can be written as:
T
A(r;, Tie)
Σ I[Ra(x:) Rx(xe))), 1=1
(1)
in which R2 (2x) is the leaf x; is assigned to for tree t. Alg. [summarizes the procedure for computing affinity scores for all training examples. This metric clusters similar examples together based on the
learned model representation (i.e., the tree structures). Intuitively, if two examples appear in the same leaf in every tree throughout the ensemble, then both examples are predicted in an identical manner. One may also view Eq. (T) as an indication of which training examples most often affect the leaf values The is assigned to and thus implicitly which examples are likely to have big effect on the
3

---

prediction Ite. This similarity metric is similar to the random forest kernel [18]. however, unlike random forests, GBRTs are typically constructed shallower depth, resulting in more training examples assigned to the same leaf (see $C.5 for additional details about leaf density in GBRTs).
Algorithm 1 IBUG affinity computation.
Algorithm 2 IBUG probabilistic prediction.
Input:
Input instance X, GBRT model f.
Input:
Input E X, GBRT model f. k highest-afinity neighbors A A min. variance p. variance calibra- tion parameters and ó, target distribution D.
I: procedure COMPUTEAFINITEESE:
2:
A 4
b- Init. train affinities Visit each tree
3:
fo..=l...Tdl do
1: procedure PROBPREDICT(2, f. A p. 7. 6, D)
4: Get instance set 7i for leaf 1 Rx)
2:
Pg < f(x)
D GBRT scalar output
5: for i E 11 do
> Increment affinities
o (1( p) Ensure o² >
6:
A - A 1
4:
dj 7-j +
Var. calibration, Eq.
7:
return A
5:
return ((AAW))gg
Eq.
3.2
Modeling the Output Distribution
IBUG has a multitude of choices when modeling the conditional output distribution. The simplest and most common approach is to model the output assuming Gaussian distribution (22 [4]. We the scalar output of Par l' to model the conditional mean since GBRTs already produce accurate point predictions. Then, we use the training instances with the largest affinity to Ite-Wo we denote this set ( to compute the variance "ice
Calibrating prediction variance. The k-nearest neighbors generally do a good of determining the relative uncertainty of different predictions, but on some datasets, the resulting variance is systematically too large too small. To correct for this, we apply an additional affine transformation before making the prediction:
Dcc
70 Sie + +
+
where and d are tuned on validation data after k has been selected. Instead of exhaustively searching over all values of 7 or we use either the multiplicative factor (tuning with 0) or the additive factor (tuning 8 with
1), and choose between them using their performance on validation data.
We find this simple calibration step consistently improves probabilistic performance for not only IBUG, but competing methods as well, and at relatively small cost compared to training the model.
Flexible posterior modeling. In general, we can generate probabilistic prediction us- ing Ma.. and o²... for any distribution that uses location and scale (note PGBM and CBU can only model these types of distributions). However, IBUG can additionally use A(k) to directly fit any continuous distribution D, including those with high-order moments:
Dic = D(A(k) |.g... ....)
(3)
Eq. (3) is defined such that D can be fit directly with (A) using MLE (maximum likelihood estimation) [47], may be fit using Picee & as fixed parameter values with A fitting any other parameters of the distribution. Overall, directly fitting all or some additional parameters in D-for example, the shape parameter in Weibull distribution-is benefit over PGBM and CBU, which can only optimize for a global shape value using a gridsearch-like approach with extra validation data.
Note that NGBoost can model any parameterized distribution, but must specify this choice before training; in contrast, IBUG can optimize this choice after training. Additionally, IBUG may choose D to be a non- non-paarmettic density estimator such as KDE (kernel density estimation) 62), which PGBM, CBU, and NGBoost cannot do.
3.3 Summary
In summary, Alg. provides pseudocode for generating probabilistic prediction with IBUG. Note Algs. Tand 2 work for any GBRT model, allowing practitioners to employ IBUG to adapt multiple different point predictors into probabilistic estimators and select the model with the best performance.

---

Empirically, we show using different base models for IBUG can result in improved probabilistic performance than using just one ($5.)
IBUG is a nearest neighbors approach and thus seems well-suited to estimating aleatoric uncertainty- remaining uncertainty due to irreducible error or the inherent stochasticity in the system 3 since it can quantify the range of outcomes to be expected given the observed features. However, we use predictions held-out data tune the number of nearest neighbors and the variance calibration hyperparameters: thus, we effectively optimize prediction uncertainty encompassing both aleatoric uncertainty and epistemic uncertainty error due to the imperfections of the model and the training data 20 44.
The evaluation measures in our experiments thus also focus on predictive uncertainty.
4 Computational Efficiency
Training efficiency. Since IBUG works with standard GBRT models, it inherits the training effi- ciency of modern GBRT implementations such as XGBoost [2]. LightGBM [36), and CatBoost [52]
Prediction efficiency. If there are T trees in the ensemble and each leaf has at most ny training instances assigned to it, then IBUG's prediction time is ([T),,, since it considers each instance in each leaf. Note training instances that do not appear in leaf with the target instance do not increase prediction time; what matters most is thus the number of instances at each leaf. We find LightGBM often induces regression trees with large leaves-ine in some cases, over half the dataset is assigned to a single leaf (see $C.3 for details). Thus, prediction time still grows with the size of the dataset, as is typical for instance-basee methods. This higher prediction time is the price IBUG pays for greater flexibility.
Prediction efficiency can be increased at training time by using deeper GBRTs with fewer instances in each leaf. after training by subsampling the instances considered for predictions, or at prediction time by sampling the trees used compute affinities. We explore this last option in the next subsection.
4.1 Sampling Trees
The most expensive operation when generating probabilistic prediction with IBUG is computing the affinity vector (Eq. [ In order to increase prediction efficiency, we can instead work with a subset of the trees T in the ensemble. We build this subset by sampling trees uniformly random, taking the first trees learned (representing the largest gradient steps), or the last trees learned (representing the fine-tuning steps).
By sampling trees, the runtime complexity reduces to O(Tr)), which provides significant speedups when 7 < T. In our empirical evaluation, we find that taking a subset of the first trees learned gener- ally works best, significantly increasing prediction efficiency while maintaining accurate probabilistic predictions ($.6)).
4.2 Accelerated k Tuning
Choosing appropriate value of k is critical for generating accurate probabilistic predictions in IBUG. Thus, we aim to tune using a held-out validation dataset Deat C D and an appropriate probabilistic scoring metric such as negative log likelihood (NLL). Unfortunately, typical tuning procedures would result the same affinity vectors being computed-an an expensive operation each candidate value of k. To mitigate this issue, we perform custom tuning procedure that reuses computed affinity vectors for all values k. More specifically, IBUG computes an affinity vector A for given validation example Tral and then sorts A in descending order (i.e., largest affinity first). Then, IBUG takes the top training instances, and generates and scores the resulting probabilistic prediction. For each subsequent value of k. the same sorted affinity list can be used, avoiding duplicate computation. We summarize this procedure in Alg.
Once & is chosen, we may encounter new unseen target instance in which the variance of the k- highest affinity training examples for that target example is zero or extremely small. In this case, we set the predicted target variance to which is set during tuning to the minimum (nonzero) variance computed over all predictions the validation set for the chosen In practice, we find instances of abnormally low variance to be rare with appropriately chosen values of k.
5

---

Algorithm 3 IBUG accelerated tuning of k.
Input: Validation dataset Deat C DD GBRT model f. list of candidates K, target distribution D, probabilistic scoring metric V, minimum variance p = 15.15.
1: procedure FASTTUNEK(Dooo) cot. f. K, D, P.
2: for (z,, Deal do
3:
A < COMPUTEAFFINITIESS
D Algorithm
4:
A Argsort in descending order
5:
for k E K do
D Use same ordering for each k:
6:
A (k) + Take first & training instances(A, k)
7:
De < PROBPREDICT(E,, A D)
D Algorithm >i Save validation score
5J + Vujj D
8:
9:
- Select best & from S
10:
p Select minimum d² from D
11:
return k, /
5
Experiments
In this section, we demonstrate IBUG's ability to produce competitive probabilistic and point predic- tions as compared current state-of-the-arr methods on large set of regression datasets ($5.1 $5.)
Then, we show that IBUG can use different base models to improve probabilistic performance ($5.3) flexibly model the posterior distribution ($5.4), and use approximations to speed up probabilistic predictions while maintaining competitive performance ($5.6).
Implementation and Reproducibility. We implement IBUG in Python, using Cython Python package allowing the development of C extensions to store a unified representation of the model structure. IBUG supports all modern gradient boosting frameworks including XGBoost [12]. Light- GBM (36], and CatBoost [52]. Experiments are run publicly available datasets using an Intel(R) Re) CPU E5- 26-2 v4 2.66 2.6GHz with 60GB of RAM 2.4GHz. Links to all data sources as well as the code for IBUG and all experiments is available at wuthttps:/// thub. com/ http.tb.b.o///////oy/////// JJbroph44//hbbbbgggg
5.1
Methodology
We now compare IBUG's probabilistic and point predictions NGBoost PGBM 64 and CBU 44 on 21 benchmark regression datasets and one synthetic dataset. Additional dataset details are in B.
Metrics. We compute the average continuous ranked probability score (CRPS L) and negative log likelihood (NLL 4) 29 over the test set evaluate probabilistic performance. To evaluate point performance, we use root mean squared error (RMSE J). For all metrics, lower is better. See $ for detailed deseriptions.
Protocol. We follow a similar protocol to Sprangers et al. [64] and Duan et al. [22]. We use 10-fold cross-validation to create 10 90/10 train/test folds for each dataset. For each fold, the 90% training set is randomly split into an 80/20 train/validation set to tune any hyperparameters. Once the hyperparameters are tuned, the model retrained using the entire 90% training set. For probabilistic predictions, a normal distribution is used to model the output.
Significance Testing. We report counts of the number of datasets in which a given method per- formed better ("Win"), worse ("Loss"), or not statistically different ("Tie")) relative to comparator using a two-sided paired t-test over the 10 random folds with significance level of 0.05.
Hyperparameters. We tune NGBoost the same way as in Duan et al. 22 Since PGBM, CBU, and IBUG optimize point prediction metric, we tune their hyperparameters similarly. We also tune variance cal valittatoon parameters and for each method ($3.2). Exact hyperparameter values evaluated and selected are in B.2 Unless specified otherwise, we use CatBoost 52 as the base model for IBUG.

---

Table Probabilistic (CRPS) performance for each method on each dataset. Lower is better. Normal distributions are used for all probabilistic predictions. Results are averaged over 10 folds, and standard errors are shown in subscripted parentheses. The best method for each dataset bolded, as well as those with standard errors that overlap the best method. Bottom row: Head-to-head comparison between IBUG/BUG+CBU and each method showing the number of wins, ties, and losses (W-T-L. across all datasets. On average, IBUG+CBU provides the most accurate probabilistic predictions.
Dataset
NGBoost
PGBM
CBU
IBUG
IBUG+CBU
Ames
(847)
(0552
(1300
(0434(367)
10194 (368)
Bike
(0.55)
1.183 (0.041)
0.833 (0.060)
0.974 (0.048)
0.766(0.032)
California
lell (1e11)
0.222
0.217 (.217(0.001) (0.001)
0.213 (0.001)
0.207 (o.001)
Communities
0.068(0.002)
0,068 (0.002)
0.067 (0.002)
0.065 (0.002)
(0005(0.002))
Concrete
3.410 (0.182)
1.927 (0.086)
1.788 (0.077)
1.849 (0.098)
1.741 (0.082)
Energy
(.519(0.043) (0.043)
0.147 (0.006)
(0.90))
0.143 (0.009)
0.157
Facebook
4.022(0.090)
3.554 (..54(00095))
3.211 (0.059)
3.073 3.073 (0.066)
2.977 2.977 (0.070)
Kin8nm
0.095 (0.05) (0.001)
0,06 (0.001)
0.057 (0.001)
0.051 (a.001)
0.051 0.051 (0.001)
Life
2.897 (1.465)
0.815(0.027)
0.772 0.772 (0.024)
(.794(0.023)
0.731 0.731 (0.022)
MEPS
5,527 (0.196)
6,448 (0.092)
6.050 6.050 (0.109)
6. 6.150
6.016 (0.118)
MSD
4.524 (0.005)
(0.76().005)
4.363 (0.004)
(0.10(0.005)
4.347 (0.004)
Naval
0.003 (0.000)
0.000 (0.000)
0.000 (0.000)
0.000
0.000 (0.000)
0.000
News
2191 (47.5)
236 (52.6)
(346
2545(41.0)
(380
Obesity
3.208 (0.028)
(866((0002)
1.740 (o.00)
(.866)00021)
1.771 1.771(0.019) (0.019)
Power
2. 2.105 2.105 (0.023)
1.531 (0.019)
1.473
1.473 (0.022)
1.542 (0.020)
1.471 1.471 (0.021)
Protein
5427 (3409)
1.823 (0.011)
1.788 (0.009)
1.784 (0.008)
1.742
STAR
(1.80)
(31((.380)
(30(1.280)
(1.144)
129 (1.198)
Superconductor
2.405 (0.028)
0.126 (0.004)
0.150
0. 0.153 (0.006)
0.128 (0.004)
Synthetic
5.779 (0.042)
5.737 (0.039)
5.739 (0.040)
5.731 (0.040)
5.730 (0.040)
Wave
571020 (883)
3891 (73.9)
2349 (10.3)
2679 (16.0)
2026 2026 (9.538)
Wine
0.385 (0.005)
0.323 (0.005)
0.337 (0.006)
0.322 (0.006)
0.321 (0.006)
Yacht
1.177 (0.158)
0.292 (0.042)
0.281 (0.048)
0.276 0.276 (0.048)
0.255 0.255 (0.046)
IBUG W-T-L
17-3-2
11-9-2
9-5-8
1-6-15
IBUG+CBU W-T-L
17-3-2
15-6-1
18-2-2
15-6-1
5.2
Probabilistic and Point Performance
We first compare IBUG's s probabilistic and point predictions each baseline each dataset. See Table for detailed CRPS results; due to space constraints, results for additional probabilistic metrics (e.g., NLL) as well point performance results are in [B.3 Our main findings
follows:
On probabilistic performance, IBUG performs equally well or better than NGBoost and PGBM, winning on 17 and 11 (out of 22) datasets respectively, while losing on only 2 and (respectively). Since CBU and IBUG performance is similar, we combine the two approaches, averaging their outputs; we denote this simple ensemble IBUG+CBU Surprisingly, IBUG+CBU works very well, losing on only a maximum of 2 datasets when faced head-to-head against any other method; these results suggest IBUG and CBU are complimentary approaches.
On point performance, PGBM, CBU, and IBUG performed significantly better than NG- Boost; this is consistent with previous work and is perhaps unsurprising since NGBoost is optimized for probabilistic performance, not point performance. However, IBUG generally performed better than PGBM, winning on 13 datasets and losing only I dataset; and performed slightly better than CBU, winning on datasets with no losses.
We also compare IBUG with two additional baselines-KNY and BART 13 shown in due to space constraints. We find IBUG generally outperforms these methods in both probabilistic and point performance. Overall, the results this section suggest IBUG generates both competitive probabilistic and point predictions compared to cxisting methods.
7

---

Table 2: Probabilistic (CRPS, NLL) performance on the test set for IBUG using different base models. Results are averaged over 10 folds, and standard errors are shown in subscripted parentheses; lower better. On 6 and datasets, respectively, either IBUG-LightCIM or IBUG-XGBoosI significantly outperforms IBUG-Cat on the validation set and subsequently on the test set, demonstrating the potential for improved probabilistic performance by using IBUG with different base models.
CRPS (4)
Test NIL (p)
Dataset
CatBoost
LightGBB
XGBoost
Dataset
CatBoust
LighaGBM
XGBoost
Protein
News
Power
Bike
4.410
0.974go o48)
1.784(a.00m (0.00)
(.542(0.020)
2545 (41.0)
000) 0053
16683 009)
4_37220.000 005)
0.819 co. 024)
1.536ga
2436;50.5)
1,518 (1.0))
0.849 (1.012)
1.788 008)
4.418(0.005)
255 (56.0)
MSD
Naval
Obesity
Bike
6.208 (o. 0.010)
2.646
(886)
(0-15
66.281 o01)
2.593 (0.06)
3.409 (0-00))
(0.00)
3,402 (0.002)
2.624 (0.00)
(.853
1.662 (0.024)
Supercon.
0,783(o.181)
-0.4%6 169)
(2.4(23.2)
Supercon.
0. 006)
0.090 005)
0.010 003)
IMLPS kmag1)
Ktmin deaety
Teat Index: 799
Test Indor 34
0.2
Test Indes 1301
Teat Index 1487
Test Indox 739
Ang. Performance
0.05
0.00
200
6.00
0.0g
50
0.0
25
0.0
Normal Webboll
Test Index 201
Test Index 274
Test Iadex 177
Test Indux 538
Test Indes 962
Aug. Performance
(Wine, k-611
kirwat Quasity
0.5
0.4
0.2
0.5
0.25
0.5
1.0
Thet NLL
5.0 7.5 put
0.5
7.5
0.00
5.0
7.5
0.0
Narmal KDF
Outgut
Outgsct
Octpot
Output
Figure 1: Left: Distribution of the k-nearest training examples for randomly-selected test instances from the MEPS (top) and Wine (bottom) datasets. Right: Test NLL (with standard error) when modeling the posterior using two different distributions (lower is better). IBUG can model parametric and non-parametric distributions that better fit the underlying data than assuming normality.
5.3 Different Base Models
Here we experiment using different base models for IBUG besides CatBoost [2]; specifically. we use LightGBM (36) and XGBoost [12,, two popular gradient boosting frameworks. Table shows that using a different base model can result in improved probabilistic performance. This highlights IBUG's s agnosticism to GBRT type, enabling practitioners to apply IBUG to future models with improved point prediction performance.
5.4 Posterior Modeling
One of the unique benefits of IBUG is the ability to directly model the output using empirical samples (Fi giving practitioners a better sense of the output distribution for specific predictions. IBUG can optimize a distribution after training, and has more flexibility in the types of distributions it can model from distributions using just location and scale to those with high-order moments as well as non-parametric density estimators. To test this flexibility, we model each probabilistic prediction using the following distributions: normal, skewnormal, lognormal, Laplace, student t, logistic, Gumbel, Weibull, and KDE; we then select the distribution with the best average NL.L on the validation set, and evaluate its probabilistic performance on the test set.
Figure I demonstrates that the selected distributions for the MEPS and Wine datasets achieve better probabilistic performance than assuming normality. Qualitatively, the empirical densities of A for randomly sampled set of test instances reaffirms the selected distributions. As an additional comparison, we report CBU achieves a test NLL of 10.09 and 1. 1.025 for the MEPS and wine datasets (respectively) using a normal distribution, while IBUG achieves - -6.887+0 .60 and 0. 0.785200.22 using Weibull and KDE estimation (respectively). For the MEPS dataset, the selected Weibull distribution takes a shape parameter, which IBUG estimates directly on a per prediction basis using and MIL, contrast, PGBM or CBU would need to optimize a global shape value using a validation set, which is likely to be suboptimal for individual predictions.
8

---

Table Probabilistic performance comparison of each method with vs, without variance calibration.
In all cases, calibration maintains or improves performance; it is especially helpful for CBU.
CRPS
NLL
Method
Wins
ties
Losses
Wins
Ties
Losses
NGBoost
9
13
21
0
PGBM
13
11
11
0
CBU
17
11
0
IBUG
13
103
Total Train Time (s)
10s
Avg. Predict Time (ms)
10a
104
10
8
100
10a
10-1
10a
10-2
NGBoost
PGBM
CBU
IBUG
NGBoost PGBM
CBU
IBUG
Figure 2: Runtime comparison. Left: Total train time (including tuning). Right: Average prediction
time per test example. Results are shown for all datasets, averaged over 10 folds (exact values in $B.4 Tables 12 and [3). On average, IBUG has comparable training times to PGBM and CBU,
but is relatively slow for prediction.
5.5 Variance Calibration
Table shows probabilistic performance comparisons of each method against itself with and without variance calibration. In all cases, variance calibration (+3.2) either maintains or improves performance for all methods, especially CBU. Overall, these results suggest that variance calibration should be standard procedure for probabilistic prediction, unless using method that has particularly well- calibrated predictions to begin with. We therefore use variance calibration in all of our results.
Additionally, $ C shows performance results for all methods without variance calibration. Overall, we observe similar relative performance trends as when applying calibration (Table I)
Amsos
-0
2,2
3.0
-5
1.0
2.0
1.8
product
16
10
101
10a
10P
100
10-1
10
10-1
25 50 75 100
25 50
75
100
25 50
75
160
25 50 75
100
25 50 75 100 Trees sampled
25 50 75 100
5 Trees sampled
Trees sampled
56 Irees sampled
Trees sampled
% Trees sampled
Figure 3: Change in probabilistic (NLL) performance (top) and average prediction time (in seconds) per test example (bottom) as function of r for six datasets with trees sampled first-to-last; lower is better. NGBoost, PGBM, and CBU are added for additional context. The shaded regions represent the standard error. Overall, average prediction time decreases significantly as r decreases while test NLL often remains relatively stable, enabling IBUG to generate probabilistic predictions with significant increased efficiency.

---

5.6 Sampling Trees
Figure 2 shows the runtime for each method broken down into total training time (including tuning) and prediction time per test example. On average, IBUG has similar training times to PGBM and CBU, but on some datasets, IBUG is roughly an order of magnitude faster than PGBM. For predictions, IBUG is similar to PGBM but relatively slow compared to NGBoost and CBU.
However, by sampling < trees when computing the affinity vector, IBUG can significantly reduce prediction time. Figure 3 shows results when sampling trees first-to-last, which typically works best over all tree-sampling strategies (alternate sampling strategies are evaluated in $ As decreases, we observe average prediction time decreases roughly 1-2 orders of magnitude while probabilistic performance remains relatively stable until T r/T reaches roughly 1-5%, at which point probabilistic performance sometimes starts to decrease more rapidly. Note for the Ames and Life datasets, IBUG can reach the same average prediction time as NGBoost while maintaining the same or better probabilistic performance than NGBoost, PGBM, and CBU. These results demonstrate that speed is a concern, IBUG can approximate the affinity computation to speed up prediction times while maintaining competitive probabilistic performance.
Additonal Related Work
Traditional approaches to probabilistic regression include generalized additive models for location, scale, and shape (GAMLSS), which allow for flexible choice of distribution for the target variable but are restricted pre-specified model forms [56]. Prophet [68] also produces probabilistic estimates for generalized additive models, but has been shown to underperform as compared to more recent approaches [60] 3] Bayesian methods 48 30 naturally generate uncertainty estimates by integrating over the posterior; however, exact solutions are limited to simple models, and more complex models such as Bayesian Additive Regression Trees (BART) [3 require computationally expensive sampling techniques (e.g., MCMC [4] to provide approximate solutions.
Other approaches probabilistic regression tasks include conformal predictions 61 67 which
produce confidence intervals via empirical errors obtained in the past, and quantile regression [32]
37 45 (7). Similar to PGBM, distributional forests (DFs) [59] estimate distributional parameters
in each leaf, and average these estimates over all trees in the forest. Deep learning approaches
for probabilistic regression [54]]]]]]]]]]] 74 3] have increased recently, with notable approaches such as
DeepAR (58) and methods based on transformer architectures 38 39
7
Conclusion
IBUG uses ideas from instance-based learning to enable probabilistic predictions for any GBRT point predictor. IBUG generates probabilistic predictions by using the k-nearest training instances to the test instance found using the structure of the trees in the ensemble. Our results on 22 regression datasets demonstrate this simple wrapper produces competitive probabilistic and point predictions to current ofte-of-thhear methods, most notably NGBoost (22). PGBM [64], and CBU [44]. We also show that IBUG can more flexibly model the posterior distribution of a prediction using any parametric non- parammeett density estimator. IBUG's 's one limitation is relatively slow prediction time. However, we show that approximations in the search for the k-nearest training instances can significantly speed up prediction time; predictions work, we plan to investigate other approximations to the affinity vector such as subsampling or even reweighting training instances, which may lead to significant speed ups of IBUG.
also easily parallelizable in IBUG. For future
Acknowledgments and Disclosure of Funding
We would like to thank Zayd Hammoudeh for useful discussions and feedback and the reviewers for their constructive comments that improved this paper. This work was supported by grant from the Air Force Research Laboratory and the Defense Advanced Research Projects Agency (DARPA)- agreement number FA8750- 16-C-0166 subcontract K00189) 10008882-0--55 as well as a second grant from DARPA, agreement number HR0011209011 12090135. This work benefited from access to the University of Oregon perforerform computer, Talapas.
10

---

References
[1] Yaser Abu-Mostafa and Amir F Atia.. Introduction to financial forecasting, Applied Intelli- gence, 6(3):205-22) 213, 1996.
[2] Amina Adadi and Mohammed Berrada. Peeking inside the black-box: A survey explainable artificial intelligence (XAI). IEEE Access, 6:52138-52160, 2018.
[3] Alexander Alexandrov, Konstantinos Benidis, Michael Bohlke-Schneiiee Schneider, Valentin Flunkert, Jan Gasthaus, Tim Januschowski, Danielle C Maddix, Syama Sundar Rangapuram, David Salinas, Jasper Schulz, et al. GluonTS:: Probabilistic and neural time series modeling in python. Journal of Machine Learning Research, 21(1 1(116)):166 2020.
[4] Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael Jordan. An introduction to MCMC for machine learning. Machine Learning, 50(1):5 43, 2003.
[5] Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-frig free uncertainty quantification. arXiv preprint arXiv:2107.07511, 2021.
[6] Anand Avati, Kenneth Jung, Stephanie Harman, Lance Downing, Andrew Ng, and Nigam H Shah. Improving palliative care with deep learning. BMC Medical Informatics and Decision Making, 18(4):55-64, 2018.
[7] Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011), 2011.
[8] Adam Bloniarz, Ameet Talwalkar, Bin Yu, and Christopher Wu. Supervised neighborhoods for distributed nonparametric regression. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pages 1450-1459, 2016.
[9] Hons-kendrik Böse, Valentin Flunkert, Jan Gasthaus, Tim Januschowski, Dustin Lange, David Salinas, Scbastian Schelter, Matthias Seeger, and Yuyang Wang. Probabilistic demand forecast- ing at scale. Proceedings of the VLDB Endowment, volume 10, pages 1694-1705. VLDB Endowment, 2017.
[10] Leo Breiman. Bagging predictors. Machine Learning, 24(2): 1996.
[11] Jonathan Brophy and Daniel Lowd. Trex: Tree-ensemble representer ppont explanations. In ICML Workshop on Extending Explainable AI, 2020.
[12] Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
[13] Hugh A Chipman, Edward I George, and Robert E McCulloch. BART: Bayesian additive regression trees. The Annals of Applied Statistics, 4(1):266-298, 2010.
[14] Youngseog Chung, Ian Char, Han Guo, Jeff Schneider, and Willie Neiswanger. Uncertainty tool- box: An open-source library for assessing, visualizing, and improving uncertainty quantification. arXiv preprint arXiv:2109. 10254, 2021.
[15] Joel W Cohen, Steven B Cohen, and Jessica S Banthin. The medical expenditure panel survey: national information resource to support healthcare cost research and inform policy and practice. Medical Care, pages S44-S50, 2009.
[16] Andrea Coraddu, Luca Oneto, Aessandro Ghio, Stefano Savio, Davide Anguita, and Massimo Figari. Machine learning approaches for improving condition-basee maintenance of naval propulsion plants. Journal of Engineering for the Maritime Environment, Part M. 230(1): 136-153, 2016.
[17] Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis. Modeling wine preferences by data mining from physicochemical properties. Decision Support Systems, 4774):547-553, 2009.

---

[18] Alex Davies and Zoubin Ghahramani. The random forest kernel and other kernels for big data from random partitions. arXiv preprint arXiv:1402.42293, 2014.
[19] Dean De Cock. Ames, lowa: Alternative to the Boston housing data as an end of semester regression project. Journal of Statistics Education, 19(3), 2011.
[20] Daniel D'souza, Zach Nussbaum, Chirag Agarwal, and Sara Hooker. A tale of two long tails. arXiv preprint arXi::2107.13098, 2021.
[21] Dheeru Dua and Casey Graff. UCI machine learning repository. http://archive.icss uci edu/ml| 2019. [Online; accessed 2--eptember--2221)
[22] Tony Duan, Avati Anand, Daisy Yi Ding, Khanh K Thai, Sanjay Basu, Andrew Ng. and Alejan- dro Schuler. Ngboost: Natural gradient boosting for probabilistic prediction. In Proceedings of the 37th International Conference on Machine Learning, pages 2690-2700. PMLR, 2020.
[23] Hadi Fanaee-T and Joao Gama. Event labeling combining ensemble detectors and background knowledge. Progress in Artificial Intelligence, pages 1-15, 2013.
[24] Kelwin Fernandes, Pedro Vinagre, and Paulo Cortez. A proactive intelligent decision support system for predicting the popularity of online news. In Proceedings of the 17th Portuguese Conference on Artificial Intelligence, pages 535-546. Springer, 2015.
[25] Juliana J Ferreira and Mateus S Monteiro. What people doing about XAI user experience? survey on Al explainability research and practice. In Proceedings of the 22nd International Conference Human- Human-Computer Interaction, pages 56-73. Springer, 2020.
[26] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive logistic regression: A statistical view of boosting. The Annals of Statistics, 28(2)3337-407, 2000.
[27] Jerome H Friedman. Multivariate adaptive regression splines. The Annals of Statistics, pages 1 1-67, 1991.
[28] Tilmann Gneiting and Matthias Katzfuss. Probabilistic forecasting, Annual Review of Statistics and Its Application, 1:125-151, 2014.
[29] Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-378 2007.
[30] Alex Graves. Practical variational inference for neural networks. In Proceedings of the 25th International Conference on Neural Information Processing Systems, volume 24, 2011.
[31] Kam Hamidieh. A data-driven statistical model for predicting the critical temperature of superconductor. Computational Materials Science, 154:346-35: 2018
[32] Hilaf Hasson, Bernie Wang, Tim Januschowski, and Jan Gasthaus. Probabilistic forecasting: A level-set approach. In Proceedings of the 35th International Conference on Neural Information Processing Systems, volume 34, 2021.
[33] Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning. 110(3):457-566 2021.
[34] Tim Januschowski, Yuyang Wang, Kari Torkkola, Timo Erkkilä. Hilaf Hasson, and Jan Gasthaus. Forecasting with trees. International Journal of Forecasting, 2021.
[35] Heysem Kaya, Pmar Tüfekci, and Fikret S Gürgen. Local and global learning methods for predicting power a combined gas & steam turbine. In Proceedings of the 2nd International Conference Emerging Trends in Computer and Electronics Engineering (ICETCEE), pages 13-18. 2012.
[36] Guolin Ke, Qi Meng, et al. LightGBM: A highly efficient gradient boosting decision tree. In Proceedings of the 3/st International Conference on Neural Information Processing Systems, 2017.
12

---

[37] Roger Koenker and Kevin F Hallock. Quantile regression. Journal of Economic Perspectives, 15(4):143-155) 156, 2001.
[38] Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, and Xifeng Yan. Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, volume 32, pages 2243,,23,222 2019.
[39] Bryan Lim, Sercan Ô Anı,, Nicolas Loeff, and Tomas Pfister. Temporal fusion transformers for interpretable multi-horizon time series forecasting. International Journal of Forecasting, 2021.
[40] Yi Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Journal of the American Statistical Association, 101(474):578-59)) 2006.
[41] Zhao Tang Luo, Huiyan Sang, and Bani Mallick. BAST: Bayesian additive regression spanning trees for complex constrained domain. In Proceedings of the 35th International Conference on Neural Information Processing Systems, volume 34, 2021.
[42] Spyros Makridakis, Evangelos Spiliotis, Vassilios Assimakopoulos, Zhi Chen, Anil Gaba, Ilia Tsetlin, and Robert Winkler. The M5 uncertainty competition: Results, findings and conclusions. International Journal of Forecasting, 2021.
[43] Spyros Makridakis, Evangelos Spiliotis, and Vassilios Assimakopoulos, M5 accuracy competi- tion: Results, findings, and conclusions. International Journal of Forecasting, 2022.
[44] Andrey Malinin, Liudmila Prokhorenkova, and Aleksei Ustimenko. Uncertainty in gradient boosting via ensembles. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[45] Nicolai Meinshausen and Greg Ridgeway. Quantile regression forests. Journal of Machine Learning Research, 7(6), 2006.
[46] Frank Moosmann, Bill Triggs, and Frederic Jurie. Fast discriminative visual codebooks using randomized clustering forests. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 985-992, 2006.
[47] Jae Myung. Tutorial on maximum likelihood estimation. Journal of Mathematical Psychology, (7()):901100, 2003.
[48] Radford M Neal. Bayesian Learning for Neural Networks. Springer-Verlag 1996.
[49] Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3):291-297, 1997.
[50] Leif E Peterson. K-nearest neighbor. Scholarpedia, 482): 2009.
[51] Gregory Plumb, Denali Molitor, and Ameet S Talwalkar. Model agnostic supervised local explanations. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 2515-2524, 2018.
[52] Liudmila Prokhorenkova, Gleb Gusev, al. CatBoost: Unbiased boosting with categorical features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018
[53] Kumar Rajarshi. Life expectancy (WHO). o http://ww.kgglleccoom/mumrrrrraa life- expectancy- who canooree=aaee hackernoon.. hom.:eeeleetiiieeeeetttttaaaalae csv 2017. [Online; accessed 12- 22-Septemerr222211 2021].
[54] Syama Sundar Rangapuram, Matthias Seeger, Jan Gasthaus, Lorenzo Stella, Yuyang Wang, and Tim Januschowski. Deep state space models for time series forecasting. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, volume 31, pages 7785-7794, 2018.
13

---

[55] Michael Redmond and Alok Baveja. A data-driven software tool for enabling cooperative information sharing among police departments. European Journal of Operational Research, 141 141(3):660-67) 2002.
[56] Robert A Rigby and D Mikis Stasinopoulos. Generalized additive models for location, scale and shape. Journal of the Royal Statistical Society: Seriey C (Applied Statistics), 54(3):007-554, 2005.
[57] Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In Proceedings of the 33rd International Conference Neural Information Processing Systems, volume 32, pages 3543-3553, 2019.
[58] David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. Deepar: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting. 36(3):
1181-1191, 2020.
[59] Lisa Schlosser, Torsten Hothorn, Reto Stauffer, and Achim Zeileis. Distributional regression forests for probabilistic precipitation forecasting in complex terrain. The Annals of Applied Statistics, 13(3):1564-1553 2019.
[60] Rajat Sen, Hs Yu, and Inderjit Dhillon. Think globally, act locally: A deep neural network approach to nigh-dimensiooal time series forecasting. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 4837-4846, 2019.
[61] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3). 2008
[62] Simon J Sheather and Michael C Jones. A reliable data-based bandwidth selection method for kernel density estimation. Journal of the Royal Statistical Sociery: Series B (Methodological), 53(3):683 6600 1991.
[63] Kamaljot Singh, Ranjeet Kaur Sandhu, and Dinesh Kumar. Comment volume prediction using neural networks and decision trees. IEEE UKSim-AMSS 17th International Conference on Computational Modeling and Simulation, UKSim2015, March 2015.
[64] Olivier Sprangers, Sebastian Schelter, and Maarten de Rijke. Probabilistic gradient boosting machines for large-scale probabilistic regression. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
[65] James H Stock, Mark Watson, et Introduction to Econometrics, volume 3. Pearson New York, 2012.
[66] Suzanne. CDC data: Nutrition, physical activity, obesity. https:://tw: kaggle le com/ 0/44//coo cdc- edc-data- htt.:a/wwww...t.o....aaaaaaaaaaa cessed 12-September-2021]
2018. [Online; ac-
[67] Souhaib Ben Taieb, Raphael Huser, Rob Hyndman, Mare Genton, et al. Probabilistic time series forecasting with boosted additive models: An application to smart meter data. Department of Economics and Business Statistics, Monash University, 2015.
[68] Sean J Taylor and Benjamin Letham. Forecasting scale. The American Statistician, 72(1): 37-45, 2018.
[69] Erico Tjoa and Cuntai Guan. A survey on explainable artificial intelligence (XAI): Toward medical XAL. IEEE Transactions on Neural Networks and Learning Systems, 2020.
[70] Athanasios Tsanas and Angeliki Xifara. Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools. Energy and Buildings, 49: 560-567, 2012.
[71] Pinar Tüfekei. Prediction of full load electrical power output of a base load operated combined cycle power plant using machine learning methods. International Journal of Electrical Power & Energy Systems, 60:126- 140, 2014.
14

---

[72] Aleksei Ustimenko and Liudmila Prokhorenkova. SGLB: Stochastic gradient langevin boosting. In International Conference on Machine Learning, pages 10487-10496. PMLR, 2021.
[73] Jan van Rijn. Kin8nm. https://www. http://www.opmmooor////////////a 2014. [Online; accessed 20-
January-2022].
[74] Yuyang Wang, Alex Smola, Danielle Maddix, Jan Gasthaus, Dean Foster, and Tim Januschowski. Deep factors for forecasting. In Proceedings of the 36th International Conference Machine Learning, pages 6607-6617. PMLR, 2019.
[75] I-C Yeh. Modeling strength high-performance concrete using artificial neural networks. Cement and Concrete Research, 28( 28(12):1777-180 1998.
[76] Michaël Zamo and Philippe Naveau. Estimation of the continuous ranked probability score with limited information and applications ensemble weather forecasts. Mathematical Geosciences, 50(2):209-23:) 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See 7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See A
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes] See $5)
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See $5.1
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See $5
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See $B.1
(b) Did you mention the license of the assets? [No] The license of each asset can be found by following its corresponding citation.
(c) Did you include any assets either in the supplemental material URL? [Yes]
See $5
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ZwOOsyQoTEN", "reviewer": "Reviewer_VfPp", "summary": "Starting from gradient boosting trees, the paper develops a new method to estimate the conditional distribution P(y|x) for regression problems. The authors propose to estimate P(y|x) in a nearest neighbor approach, using a specific similarity measure. Two instances are considered similar if they end up in the same leaf in many of the trees. Using the neighborhood, the variance or the full conditional distribution P(y|x) can be estimated. The authors also present a calibration procedure for situations where the variance is wrongly estimated during training. \n\nIn the experiments, the new method is compared to two specific baselines on 20 tabular datasets, using NLL and CRPS as performance measures. ", "questions": "Below I am listing potential limitations. I welcome the authors to comment on my remarks. ", "limitations": "The presented approach is interesting, but I also see some limitations. \n\nThe presented approach is a very simple approach with limited novelty. It is in essence a nearest neighbor method with a specific similarity measure. Estimating the conditional distribution by analyzing the neighborhood of a test instance is a well-known approach in nearest neighbor research, so the only novelty here is the similarity measure, which is quite specific. I would not be surprised if this similarity measure outperforms Euclidean distance, because the presented similarity is computed on those features that matter for prediction. Especially for high-dimensional datasets with many irrelevant features this might be an advantage over Euclidean distance. However, in nearest neighbor research, many alternative similarity scores that also provide a solution for the curse of dimensionality have been proposed. I find it a pity that this literature is completely ignored. \n\nTo my opinion, the proposed similarity measure has at least one obvious shortcoming: it is a non-continuous function that results in many ties. I am wondering whether this performance measure is able to outperform some simple baselines that also overcome the curse of dimensionality, see e.g. select the most important features based on a variable importance criterion, and compute the Euclidean distance in the resulting lower-dimensional space. Overall, I would have liked to see more theoretical and experimental justification that the proposed similarity measure is the way to go. \n\nThe fact that the variance needs to be recalibrated using a validation set lets me conclude that the considered similarity measure leads to a biased estimate of P(y|x). More theoretical insights on what goes wrong would be useful. The experiments show that the new method outperforms some baselines, but that's what 99% of the Neurips submissions claim. These claims are hard to verify, thus some theoretical results would help me to believe that the proposed method is state-of-the-art. \n\nIn the experiments, the assumptions for using a paired t-test are not met. Individual numbers are not independent, because the training datasets overlap. If you want to compute p-values, please use the right type of test. See for example Dietterich \"Approximate statistical tests for comparing supervised learning algorithms\" and follow-up papers on that topic for using the right tests.  \n\nNLL and CRPS are hard to interpret as measures for comparing different approaches. To my opinion, checking the validity of a predefined prediction interval is easier to interpret. This measure is commonly used in the conformal prediction for regression literature. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and easy to follow.\n- Uncertainty estimation for gradient-boosted regression trees is an important research problem, because boosted trees usually yield SOTA performance on tabular datasets. \n- The experimental evaluation is quite extensive. \n\nWeaknesses:\n- The proposed method comes without any theoretical justification. The method is in essence a heuristic. \n- I would have liked to see a comparison with nearest neighbor methods that use other similarity measures. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wy1ll5z7zY-", "reviewer": "Reviewer_E8u6", "summary": "This paper addresses an interesting problem: uncertainty estimation for GBRT. The authors propose a $k$-nearest neighbors approach based on an affinity between the testing sample and training samples. To save computational time, sampling from trees is used. They prove by experiments that the proposed IBUG works better than NGBoost and PGBM, two recent gradient boosting algorithms for tree model uncertainty.", "questions": "1. What's the point prediction of IBUG? Is it the original GBRT prediction, or the $\\mu_y$ obtained from the $k$-nearest neighbors set? If it is $\\mu_y$, then is the prediction as good as the original GBRT prediction?\n\n2. Authors did not compare the proposed method to any other methods beyond NGBoost and PGBM. Although there are very few works on uncertainty estimation for GBRT, one can come up with some naive ideas. For example, how about fixing the point predictions of GBRT as the mean of Gaussian distributions, and using a deep neural network to predict the variances of the Gaussian with maximum likelihood? What's the comparison of this naive solution to yours? I'm not familiar with PGBM, however, comparing only to PGBM (and NGBoost) is somewhat problematic.\n\n3. In probabilistic forecasting, calibration error (with sharpness) is really a popular metric. Can you consider using it in experiments? ECE and sharpness can provide more comprehensive evaluations.\n\n4. In calibrating variance, tuning $\\gamma$ and $\\delta$ on validation data is not a good solution. Can they be learned with a gradient descent?\n\n5. The model performance versus varying $k$ is worthy to be studied. What is the suggested $k$ for the neighbors' set? Can it be fixed for all datasets? It seems $k$ varies greatly across datasets, as shown in the Appendix. This makes me confused, and there may be no guidelines on choosing $k$.\n\n6. The minimum sample size in the leaf nodes is also a hyper-parameter in your model. What are its effects on the affinity calculation and the uncertainty estimation?\n\n7. The writing can be improved, especially the mathematical expressions.\nIn Equation (1), the sum starts from $t=1$, not $i=1$.\nEquation (3) and Equation (4) need to be modified.", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe idea has some similarities to existing works, such as distance-based conformal prediction. The way to calculate the distance (or the affinity) is new. So this paper shows a new idea, and the authors show the usefulness of the model. Comparisons to PGBM verify the benefits of such a GBRT uncertainty model.\n\nWeaknesses:\nI have some concerns about the technical issues. Please see the list in the question section.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H5pQgwokEY", "reviewer": "Reviewer_TLnP", "summary": "The authors develop IBUG, a straightforward approach for producing probabilistic predictions for gradient-boosted regression trees. The approach itself is very simple, but the point the authors are making is that this approach is useful: the authors do a very large amount of computational work showing the potential of their approach. The code the authors provide looks clean and easy-to-use.\n\nThe contributions of this paper are largely in engineering a good solution and then implementing that solution in an excellent way: there is no big methodological contribution.", "questions": "Would the authors please check their work with respect to Davies & Ghahramani (2014) and document the differences? My impression is that, after considering the work of Davies & Ghahramani (2014), IBUG cannot claim anything methodologically new (except perhaps Section 5.4?), but happy to be corrected.\n\nWould the authors please mention any comparisons they have done between IBUG and the more intricate approaches they mention in Section 6?\n\nAre the authors happy to tone down the claims of \"better\" with respect to other competing methods?\n\nWhat is the sensitivity of IBUG to the parameter k? This is the number of nearest neighbors.", "limitations": "This is fine.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "ORIGINALITY\n\n\"Originality\" is the weakest aspect of the paper. The authors don't cite Davies & Ghahramani (2014), but the \"Affinity Score\" in Equation (1) is equivalent to Section 3 in Davies & Ghahramani (2014). Even putting aside Davies & Ghahramani (2014), this paper is not terribly \"new\" or \"novel\": nothing in this paper is very surprising.\n\nHowever, \"originality\" is often overrated in research: the authors seem to have made a substantial engineering contribution.\n\nAlthough the authors may have missed Davies & Ghahramani (2014), they otherwise nicely document the literature. So the authors aren't (with the exception of the one paper) over-claiming the originality.\n\nQUALITY\n\nThe quality of the engineering is high. The authors have clearly done a lot of work in examining, (i) 22 datasets including 21 standard benchmarks, (ii) 3 performance metrics including NLL, CRPS, and RMSE, (iii) 3 different base models including LightGBM, XGBoost, and CatBoost, (iv) several types of output distributions. I checked the code the authors provided and it looks nice.\n\nCLARITY\n\nThe clarity of the paper is good. The paper is well-written and easy to understand. The code is also well-written and easy to understand.\n\nSIGNIFICANCE\n\nThe paper has potential to be significant because of the extensive engineering contributions. The (currently anonymous) code is available under an Apache 2.0 license, so my hope is that lots of others will have the opportunity to use the authors' work. As the authors write, there's a fairly big chasm between the ease-of-use of GBRT and the availability of probabilistic models, so closing that gap in an easy-to-use way is nice.\n\nMy concerns about significance are two-fold:\n\n(i) The authors only compare to other simple, easy-to-implement metrics for calculating probabilistic prediction on trees. On the one hand, the authors are right in saying that Bayesian models and more complex approaches like BART will not scale well and therefore are unlikely to be used very frequently, but on the other hand it would be nice to have comparisons between the authors' simplified approaches and the more intricate approaches.\n\n(ii) The authors claim \"better\" performance of IBUG, but I do have some concerns about this because (with trees) the goal should maybe be \"different\" performance of IBUG to other approaches. Retrofitting GBRT for probabilistic prediction is always going to be a bit of an art since the probabilistic prediction is missing from the beginning and really only added on later.\n\nAlthough I'm hoping that the authors will address these items in the rebuttal, they're not really show-stopping points. The engineering contribution here is rather extensive.\n\nMINOR\n\nLine 99: euclidean --> Euclidean\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0XlCCi70BkI", "reviewer": "Reviewer_gTo6", "summary": "This paper proposes a new method to estimate data uncertainty in GBDT models. The proposed approach uses k nearest training elements to produce probabilistic predictions. Nearest elements are determined using the constructed ensemble: top instances are chosen based on the number of times they are in the same leaf with the test example. The method can be applied to any GBDT model after it is trained.", "questions": "1. Regarding the baselines, note that in CatBoost, there is a loss function called RMSEWithUncertainty, which, similarly to NGBoost, predicts mean and variance. I think that adding a comparison with this implementation is important. In this case, by comparing CatBoost+RMSEWithUncertainty with CatBoost+IBUG, one can see the effect of the proposed method without possible effects caused by differences between GBDT implementations.\n\n2. Some training details are not clear to me. Namely, how exactly were the parameters tuned? Is it true that in Table 1 for NLL the parameters are tuned via NLL, for CRPS via CRPS, etc.? This seems to agree with Tables 5-6 in the supplementary, where we see different parameters for different measures. If this is true, does IBUG for RMSE coincide with the standard LightGBM algorithm?\n\n3. There are some important questions that are not addressed in the main text, but the corresponding experiments are in the supplementary materials. For instance:\n    - To speed up the inference, it is proposed to sample trees uniformly at random. However, for GBDT models, it is known that trees at the beginning of the ensemble and at the end are very different. Namely, the first trees give the most significant contribution, while the tree structures at the end are closer to random. Thus, a particular sampling strategy is important. This problem seems to be addressed in Appendix C.3 (but I am not sure what “in ascending order” means here). I expect a more detailed discussion about this in the main text.\n    - Another important question is whether the proposed approach of computing the similarity is better than a naive KNN applied to the original features? This question is not discussed in the main text but seems to be addressed in Appendix B.3. I expect to see more details on this in the main text. Also, it is not discussed whether feature normalization is performed before applying KNN.\n\nMinor:\n- In line 605 of the supplementary materials, it is written that one-hot encoding is used for categorical variables. This can be suboptimal for some GBDT libraries, e.g., CatBoost has its own way of dealing with categorical variables.\n\nThe paper is, in general, well written, and I noticed only minor typos in the text:\n- Line 87: “mean and variance is” (should be “are”), the same for lines 141 and 189\n- Caption of Figure 2: “means” -> “mean”\n- Line 252: “Table” -> “Figure\"\n", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The method can work with any GBDT model and can be applied to any trained model at inference time.\n- The reported results show that the proposed approach outperforms existing methods (NGBoost and PGBM) in terms of both RMSE and probabilistic evaluation measures.\n\nWeaknesses\n- The inference time can increase significantly.\n- The paper does not compare with the existing probabilistic prediction for GBDT implemented in CatBoost (see details below in Questions).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept