With the rapid growth of data and computing power, machine learning (ML) has been gaining a lot of new applications in areas not imagined before. The more ubiquitous ML systems become, it is inevitable to see applications in very sensitive and high-risk fields. This expands to a numerous areas like criminal recidivism [1], medical follow-ups [2] and autonomous-systems [3]. While these systems might be very broad, they share a common need, and that is to have a certain degree of confidence on ML predictions. A proven successful way to build confidence in critical systems is uncertainty estimation. Research has shown that humans are more likely to agree with a system if they get access to the corresponding uncertainty, and this holds true regardless of shape and variance as the approach itself is model and task agnostic [4]. Since the most common data type in real-world ML applications is tabular [5], our work in this paper focuses specifically on uncertainty quantification for the state-of-the-art gradient boosting decision trees (GBDTs) [6,7], which are known to outperform deep learning (DL) methods on tabular data, both in accuracy and tuning requirements [5]. Measuring uncertainty effectively and efficiently on GBDT predictions can therefore not only improve model interpretability in production but also ensure a safer deployment of ML systems, especially for high-risk applications.
Uncertainty quantification (UQ) has been widely studied for neural networks under the Bayesian framework [8], however, it is relatively under-explored for tree-based models. Although calibrated probability estimation trees [9,10] can be used for UQ, they have not been studied from a Bayesian perspective. Recently, Bayesian ensemble methods were extended to measure uncertainty in GBDTs by leveraging a new algorithm called stochastic gradient Langevin boosting (SGLB) [11]. Specifically, two SGLB-based approaches were introduced for UQ [12]: (1) SGLB ensemble, which trains multiple SGLB models in parallel, and (2) SGLB virtual ensemble, which constructs a virtual ensemble using only a single SGLB model where each member in the ensemble is a "truncated" sub-model [12]. Although both approaches are theoretically sound, there is clearly a trade-off between quality and efficiency in practice. SGLB (real) ensemble is believed to be accurate as it can characterize the Bayesian posterior well by running independent models in parallel. However, it is almost infeasible to deploy such an ensemble in real-world production due to its high computational and maintenance costs. SGLB virtual ensemble greatly improves the efficiency, however, it often gets stuck on a single mode of the Bayesian posterior and can produce downgraded uncertainty estimates [13,14]. To better balance between quality and efficiency and to facilitate the usage of uncertainty-enabled ML systems, an important question remains: how can we make a single SGLB explore effectively different modes of a posterior given a limited computational budget?
In this paper, we address the question above by combining SGLB virtual ensemble with advanced sampling techniques from Bayesian DL [14,13,15,16]. Inspired by the ideas in [13], we propose to use a scaler (or scaling factor) on gradients that follows a cyclical schedule during the course of SGLB training. The cyclical schedule is illustrated in Figure 1, and consequently, we name the resulting algorithm Cyclical SGLB (cSGLB). Similar to [13], each cycle in cSGLB contains two stages: (1) Exploration: when the scaler is large, we treat this stage as a warm restart from the previous cycle, enabling the model/sampler to follow the gradients closely and to escape from the current local mode. (2) Sampling: when the gradient scaler is small, the scale of injected Gaussian noise in the SGLB procedure becomes relatively large, encouraging the sampler to fully characterize one local mode. We collect one sample (or truncated sub-model) to build the virtual ensemble at the end of each cycle. The cyclical gradient schedule therefore helps cSGLB effectively explore different modes of a posterior while maintaining the same level of efficiency of a virtual ensemble. Moreover, inspired by a recent study [16] showing that "diversified" posterior may provide a tighter generalization bound, we present another simple approach to encourage diversity in samples obtained from running cSGLB via data bootstrapping. We name this variant Cyclical Bootstrapped SGLB (cbSGLB).
We extensively experiment with our proposed algorithms and compare the performance against SGLB ensemble and the original SGLB virtual ensemble. Particularly, we show that our cyclical gradient schedule can help explore effectively multimodal distributions, cSGLB is capable of producing uncertainty estimates that are better aligned with SGLB real ensemble, and cSGLB/cbS-GLB outperforms the SGLB baseline with a large margin on out-of-domain (OOD) data detection, indicating a su-perior performance in detecting distributional/domain shifts in real-world tabular data streams.
Bayesian ML and approximate Bayesian inference provide a principled representation of uncertainty. One popular family of approaches to inference in Bayesian ML are stochastic gradient Markov Chain Monte Carlo (SG-MCMC) methods [17,18,19,20,13], which are used to effectively sample models (or model parameters) from the Bayesian posterior. Uncertainty then comes naturally by measuring the "discrepancy" in predictions from the sampled models which are regarded as posterior samples. Recently, stochastic gradient Langevin boosting (SGLB) [11] was proposed by combining gradient boosting with SG-MCMC. As its name suggests, the Markov chain generated by SGLB obeys a special form of the stochastic gradient Langevin dynamics (SGLD) [11,17], which implies that SGLB is able to generate samples from the true Bayesian posterior asymptotically. Leveraging this property, Malinin et al. [12] proposed to use (1) SGLB ensemble or (2) SGLB virtual ensemble to measure uncertainty in GBDTs. Essentially, SGLB ensemble corresponds to running multiple SG-MCMCs in parallel and each chain (or SGLB) is initialized independently with a different random seed. Since SGLB allows us to sample from the true posterior, the ensemble with multiple samples gives a high-fidelity approximation to the Bayesian posterior. In contrast, SGLB virtual ensemble only trains a single SGLB model and it uses multiple truncated sub-models to form a (virtual) ensemble. The key idea is essentially extracting multiple samples from a single-chain SG-MCMC instead of running multiple chains in parallel.
In theory, SGLB or single-chain SG-MCMC converges asymptotically to the target distribution and should behave similarly to the multi-chain SGLB ensemble in the limit, but it can suffer from a bounded estimation error in limited time [21]. Moreover, it is often believed that the posterior is highly multimodal in the parametric space of modern ML models [13], since there are potentially many different sets of parameters that can describe the training data equally well. The real ensemble can explore different modes of the posterior by running in parallel independent chains, providing a complete picture of the distribution as the number of chains increases. However, a single-chain SG-MCMC often gets stuck easily on a single mode of the posterior [13,14], failing to cover the full spectrum of the distribution.
In this paper, we extend the ideas behind Cyclical SG-MCMC (cSG-MCMC) in DL [13] to sampling from a treebased SGLB model, which promotes new mode discovery during training. Different from cSG-MCMC that puts a cyclical schedule on step size, we propose to use a cyclical schedule on gradient scale. We also point out and justify the difference and our design choice in Appendix A. In addition, we propose a simple strategy to further encourage diversity in samples obtained from a single chain by data bootstrapping. At the beginning of each cycle (see Fig. 1), we construct a bootstrapped dataset that is a random subset of the training, and use that bootstrapped data consistently during the exploration stage to update the GBDT model. The "bias" induced by data bootstrapping also amounts to posterior tempering [14,15,22,23,13].
Given a set of π training data points sampled from an unknown distribution π on π³ Γ π΄, i.e., (π₯1, π¦1), . . . , (π₯π , π¦π ) βΌ π denoted as ππ , and a loss function πΏ(π§, π¦) : π΅ Γ π΄ β R where π΅ denotes the space of predictions, our goal is to minimize the empirical loss β(π |ππ ) := 1 π βοΈ π π=1 πΏ(π (π₯π), π¦π)) over functions π belonging to some family β± β {π : π³ β π΅}. In this paper, we only consider β± corresponding to additive ensemble of decision trees β := {β π (π₯, π π ) : π³ Γ R ππ β R, π β π}, where π is an index set and β π has parameters π π . Decision trees are built by partitioning recursively the feature space into disjoint regions (called leaves). Each region is assigned a value that is used to estimate the response of π¦ in the corresponding feature subspace. Let's denote these regions by π π's, then we have β(π₯, π) = βοΈ π ππ1{π₯ β π π}, where 1{β’} denotes indicator function. Therefore, given the tree structure, decision tree β π is a linear function of its parameters π π . It is often assumed that the set π is finite because the training data is finite [11,12], e.g., there exists only a finite number of ways to partition the training data. Owing to the linear dependence of β π on π π and the finite assumption of π, we can represent any ensemble of models from β as a linear model πΞ(π₯) = π(π₯) π Ξ for some feature map π(π₯) : π³ β R π and Ξ β R π denotes the parameters of the entire ensemble [11]. Hence, in the subsequent discussion, we will simply denote the parameters of the GBDT model obtained at iteration π as Ξ Λπ , and additionally define a linear mapping π»π : R ππ β R π that converts π π to predictions (β π (π₯π, π π )) π π=1 .
SGLB combines stochastic gradient boosting (SGB) [7] with stochastic gradient Langevin dynamics (SGLD) [17]. Following notations used in the original paper [11], we characterize the SGB procedure by a tuple β¬ := {β, π}, where β again is the set of base learners and π(π |π) is a distribution over indices π β π conditioned on a gradient vector π β R π . Simply put, π(π |π) defines a distribution over tree structures.
As with other GBDT algorithms, SGLB constructs an ensemble of decision trees iteratively. At each iteration π , we compute unbiased gradient estimates π Λπ such that E[π Λπ ] = ( π ππ πΏ(π Ξ ^π (π₯π), π¦π)) π π=1 β R π using the current model π Ξ ^π , and sample independently two normal vectors π, π β² βΌ π© (0π , πΌπ ), where 0π , πΌπ denote zero vector and identity matrix in R π , respectively. Then, a base learner (or tree structure) π π is picked by drawing one sample from π(π |π Λπ + βοΈ 2π ππ½ π β² ), where π > 0 is a learning rate (or step size) and π½ > 0 is a parameter often referred as inverse diffusion temperature. Next, we estimate the parameters π π π * (at tree leaves) of the sampled base learner by solving the following optimization:
which returns the minimum norm solution that fits best to the perturbed "noisy" version of negative gradients. The optimization above has a closed form so-
, where Ξ¦π π := (π» π π π π»π π ) + π» π π π , + denotes pseudo-inverse. For decision trees, Ξ¦π π π essentially corresponds to averaging the gradient estimates π in each leaf node of the tree. Lastly, SGLB algorithm updates the ensemble model by
where πΎ is a regularization parameter that "shrinks" the currently built model when updating the ensemble. At a high-level, SGLB is a stochastic GB algorithm with Gaussian noise injected into gradient estimates, which encourages the algorithm to explore a larger area in the functional space to find a better fit for the given data. The independence between noise π (used for parameter learning) and π β² (used for tree sampling), and the model shrinking by πΎ in Eqn.(2) are technical details needed for establishing theoretical results and rigorous analysis of SGLB [11]. All the procedures of SGLB are also present in our proposed cSGLB in Algo. 1 (with our additional modifications highlighted in blue).
One can show that the parameters of SGLB Ξ Λπ at each iteration form a Markov chain that weakly converges to the following stationary distribution:
where Ξ = Ξ π > 0 is a regularization matrix which depends on a particular tree construction algorithm or the choice of tuple β¬ := {β, π(π |π)} [11]. Note that since the GBDT model is linear and can be fully determined by parameters Ξ, we simply use notation β(π |ππ ) and β(Ξ|ππ ) interchangeably.
We consider here a standard Bayesian learning framework [8] that treats parameters Ξ as random variables and places a prior π(Ξ) over Ξ. In addition, we consider the GBDT model πΞ as a probabilistic model and explicitly denote the model by π (π¦|π₯; Ξ) with parameters Ξ. This is valid naturally for classification as GBDT models by construction return a distribution over class labels. For regression, one can leverage NGBoost algorithm [24] to return the mean and variance of a Gaussian distribution over the target π¦ for a given input π₯.
For the purpose of uncertainty estimation, we aim to estimate or obtain an approximation to the Bayesian posterior π(Ξ|ππ ). To that end, we can choose π½ = π and πΎ =1 2π and use the negative log-likelihood as the loss function
Then, the limiting distribution of SGLB can be explicitly expressed as:
which is proportional to the true posterior π(Ξ|ππ ) under Gaussian prior π(Ξ) = π© (0π, Ξ) [11]. Now, consider a Bayesian ensemble of probabilistic models {π (π¦|π₯; Ξ (π) )} πΎ π=1 where each model is trained independently by running SGLB. Since each Ξ (π) is guaranteed to be sampled from π(Ξ|ππ ) by Eqn.( 4), the ensemble {Ξ (π) } πΎ π=1 with πΎ samples yields a "discrete" approximation to the posterior π(Ξ|ππ ). This is exactly the idea behind SGLB ensemble [12], which learns πΎ independent SGLB models in parallel with different random seeds. Although the approximation improves as πΎ increases, the computational cost also increases linearly with πΎ. To alleviate the computational burden, SGLB virtual ensemble [12] builds a Bayesian virtual ensemble by sampling multiple times from a singlechain SGLB model. Because samples from the same chain are highly correlated, SGLB virtual ensemble proposes to sample one member Ξ (π) every πΆ > 1 iterations. More specifically, the parameters are sampled by
e., appending one member to the ensemble every πΆ iterations while constructing one SGLB model using π― iterations of gradient boosting. Notice that no sampling is performed during the first half of iterations (π < π― /2) since Eqn.(4) holds only asymptotically. For large πΆ and πΎ, the virtual ensemble should behave similarly to the SGLB real ensemble in the limit theoretically.
predictions can be made by taking an average over the ensemble, often known as predictive posterior or Bayesian model average (BMA):
(5) The entropy of the predictive posterior estimates total uncertainty (TU) in predictions, which can be further decomposed into two distinct types of uncertainty: knowledge uncertainty and data uncertainty. 1 (a) Knowledge uncertainty (KU) arises due to the lack of knowledge about the data generation process (or the unknown distribution π). KU is expected to be large in regions (in the feature space) where we do not have sufficient training data. (b) Data uncertainty (DU) arises due to the inherent stochasticity within the data generation process, and it is high in regions with class overlaps. In applications like active learning [25], reinforcement learning (RL) [26], and OOD detection, it is desirable to measure KU separately from DU (or TU), and the following equation can be used in practice to compute and connect them via mutual information [27]:
where I(π΄; π΅) denotes the mutual information between random variables A and B, and H(β’) denotes entropy. The difference between TU and DU measures the disagreement among members in the ensemble and estimates the knowledge uncertainty.2
Langevin Boosting (cSGLB)
Instead of building a cumbersome true ensemble of SGLB models, the virtual ensemble of SGLB greatly improves the efficiency by training only a single model. However, similar to other types of SG-MCMC in Bayesian DL [13,14,15], single-chain SGLB gets trapped easily on a particular single mode of the posterior. To efficiently explore different modes of the multimodal posterior and effectively measure uncertainty in GBDT predictions with a single chain, we propose a simple remedy that places a cyclical cosine schedule on gradient scale during training, as illustrated in Fig. 1. Specifically, the scaling factor at iteration π is defined as:
where πΌmax β₯ 1 is the maximum of the scaler or the initial value of πΌ0, πΆ is the user-defined cycle length, and πΌmin defines the minimum of the scaler, e.g., πΌmin = 1 or 0.5, since decaying the gradients to arbitrarily small could be harmful for performance. Putting together, this amounts to sampling the tree structure and learning the tree leaf parameters with the (re)scaled gradients: π π βΌ
ππ½ π). Similar to Cyclical SG-MCMC [13], we define two stages within each cycle: (1) Exploration when the completed portion of a cycle π(π ) = mod (π,πΆ) πΆ is smaller than a given threshold: π(π ) < π, and (2) Sampling when π(π ) β₯ π, and π β (0, 1) balances the portion between exploration and sampling. We obtain one sample from the chain at the end of each cycle, i.e., the virtual ensemble is built by
πΆ β}. Large gradients at the beginning of a cycle provide enough perturbation and encourage the model to escape from the current mode, while decreasing the gradient scale inside one cycle makes the sampler better characterize the density of the local mode. Moreover, many prior works in Bayesian NNs proposed to apply a certain form of preconditioning to compensate sampling noises from mini-batch training [15,14]. Tree-based models can usually digest the full-batch (full dataset ππ ) per iteration by leveraging modern multi-core processors and multi-threading. Therefore, we directly use the fullbatch GB in all sampling stages, while leaving the option of random data subsampling in exploration stages to the users if training time is a concern.
Combining cyclical gradient scaling with SGLB, we expect that our new Cyclical SGLB (cSGLB) algorithm could inherit most (if not all) theoretical properties of the original SGLB algorithm. Conceptually, with a proper choice of πΌmax, πΌmin and cycle length πΆ, the sample obtained at π = πΆ β 1 from the Markov chain π Ξ ^π generated by Algo. 1 (w/o bootstrap) can be approximately seen as a random draw from the limiting distribution with small bounded errors. Also, each next cycle can be viewed as a warm restart from its previous cycle, and thus no errors shall be accumulated into the subsequent cycles (at sampling time π = πΆπ β 1). We left rigorous analysis and proofs of our propositions for future work. Empirically, we show in our experiments that the cyclical gradient scaling achieves similar effects in exploring a multimodal distribution when compared with cSG-MCMC which places a similar cyclical schedule on step size within the context of Bayesian DL. In fact, cS-GLB extends the idea behind cSG-MCMC to tree-based GBDT models. We also summarize key differences between our design of cSGLB and cSG-MCMC in Appendix A.
Recent work [16] provided a compelling analysis that the Bayesian posterior is not optimal under model misspecification 3 , where the performance of the true posterior is dominated by an alternative non-Bayesian posterior that explicitly encourages diversity among ensemble member predictions. Inspired by these results, we propose a simple strategy that promotes diversity among samples obtained from cSGLB by data bootstrapping. At the beginning of each cycle, we sample randomly a Bernoulli mask of size π , i.e., π := {π[π] βΌ π΅πππππ’πππ(π ππ )} π π=1 β {0, 1} π , and π ππ β (0, 1) defines the percentage of data being used. In the following exploration stage, we mask out gradients π Λπ by taking an element-wise product with π, i.e., π Λπ β π. The mask π and the mask-out operation are used consistently throughout the exploration stage π(π ) < π, and π only gets updated until the end of the cycle. This design amounts to learning with a bootstrapped subsample of the data in each cycle. Since the model would observe consistently less data than the original ππ , it also amounts to posterior tempering (π(ππ |Ξ)π(Ξ)) 1/π with some temperature π > 1, resulting in a warm posterior that is softer than the Bayesian posterior. By increasing the temperature π , we expect to see increased density on the paths/corridors connecting different modes of the posterior [28,29], further facilitating the sampler to escape from the current local mode. By using a relatively large π β (0.8, 1), the tempering effects would carry over into the sampling stage. Therefore, the bootstrapping mechanism helps improve the sample diversity from cSGLB, and we name this variant Cyclical Bootstrapped SGLB (cbSGLB).
Lastly, we summarize our proposed cSGLB (plus bootstrap option) in Algo. 1 and highlight our modifications on top of SGLB in blue.
We validate and qualitatively evaluate the proposed gradient scheduling and our cSGLB algorithm on two synthetic problems: (1) a synthetic multimodal dataset in [13]
Update GBDT model:
(2) a multi-class Spiral dataset in [12]. Due to limited space, we include experimental details in Appendix B.
We first demonstrate the ability of cyclical gradient scaling for sampling from a multimodal distribution on a 2D mixture of 25 Gaussians. Specifically, we compare (i) the original SG-MCMC with SGLD (denoted as SGLD) and two SGLD variants: (ii) SGLD with Cyclical schedule on Learning Rate (denoted as clr-SGLD) [13] and (iii) SGLD with Cyclical schedule on Gradient scale (denoted as cg-SGLD (ours)). We reproduced the results for SGLD and clr-SGLD in paper [13] with code released by the authors, and built our cg-SGLD on top of it. In addition, we experimented with a "noisy" version of SGLD with a fixed lr and increased 10Γ noise scale (denoted as NoisySGLD/N-SGLD). For a fair comparison, each chain runs for 50π iterations and both clr-SGLD and cg-SGLD have 30 cycles. Fig. 2 shows the estimated density using different sampling strategies. SGLD gets trapped in local modes depending on the random initial position, and increasing the noise scale does not solve the problem. In contrast, clr-SGLD and cg-SGLD can explore and locate roughly 7 β 8 different modes of the distribution, showing that our cg-SGLD can achieve the state-of-the-art performance in exploring multimodal distributions. Moreover, cg-SGLD has benefits in implementation over clr-SGLD when combined with SGLB. The SGLB algorithm was made available in the CatBoost library [30], which only supports a fixed lr. All our proposed enhancements can be implemented with a "user-defined loss function" available in CatBoost without touching the source code, making it straightforward to reproduce our algorithms.
After validating the efficacy of cyclical gradient scheduling on sampling from multimodal distributions, we are now ready to experiment with cSGLB. Specifically, we compare the following algorithms on a 3-class classification task called "Spiral" in [12]: (i) SGLB ensemble, where we denote by ensπΎ with πΎ models, (ii) SGLB virtual ensemble, simply denoted by SGLB, and (iii) cSGLB virtual ensemble, denoted by cSGLB (ours). We again reproduced the results in [12] with code released by the authors, and Fig. 3 shows the estimated KU on Spiral test set. As noted in [12], we see that knowledge uncertainty due to decision-boundary "jitter" exists in both ens20 and cSGLB, and the "jitter" affects cSGLB more as the estimated KU is "noisy" at the decision boundary. Nevertheless, cSGLB (with only a single model) is significantly more efficient than ens20 and is able to greatly improve upon SGLB in capturing high KU in regions with no training data.
Lastly, we evaluate our proposed methods on the public Shifts Weather Prediction dataset [31]. We select the classification task where the ML model is asked to predict the precipitation class at a particular geolocation and timestamp, given heterogeneous tabular features derived from weather station measurements and forecast models. The full dataset is partitioned in a canonical fashion and contains in-domain (ID) training, development and evaluation datasets as well as out-of-domain (OOD) development and evaluation datasets. Importantly, the ID data and the OOD data are separated in time and consist of non-overlapping climate types (ID: Tropical, Dry, Mild; OOD: Snow, Polar), making the Shifts dataset an ideal testbed for gauging the robustness of ML model and the quality of uncertainty estimation. To further facilitate our experimentation, we conducted the following (3) random data sampling to keep 200πΎ (medium-sized) data in the final training set. Again, the purpose of our data preprocessing is for speeding up experimentation, and we believe that the observations and findings in this study are generalizable to the original full dataset. For model building, 30 independent SGLB models (each of 1πΎ trees) were trained and used to construct real ensembles πππ πΎ for πΎ β {3, 5, 10, 30}. SGLB/cSGLB/cbSGLB virtual ensembles were built by sampling 10 members from a single-chain with 2πΎ trees. Hence, πππ 10 is 5Γ more expensive in computation and memory than a virtual ensemble. Additional details regarding our data and models are included in Appendix C. We compare various methods on their predictive performance and on uncertainty quantification following [31], and the results are summarized in Table 1. For predictive performance, we report the classification accuracy and macro F1 using BMA on both the ID and the OOD evaluation datasets. We can see the following effects: (1) Virtual ensembles with a longer chain slightly outperform the real ensembles on the ID data. (2) Our proposed cSGLB and cbSGLB perform slightly worse than the rest of methods on the OOD data. However, this usually is not a concern in practice since the model is not trained with data from OOD domains and would not be used to solve the OOD prediction tasks in a practical scenario. As long as the domain shifts can be reliably detected (via uncertainty), proactive decisions can be made to avoid costly mistakes due to model errors. (3) Our proposed data bootstrapping mechanism is capable of improving the performance on the OOD data (cbSGLB > cSGLB). In addition, we include the F1-AUC metric (on the combined ID&OOD evaluation sets) introduced in [31] to jointly assess the predictive power and uncertainty quality. The F1-AUC can be increased by either having a stronger predictive model or by improving the correlation between uncertainty and error. Consistent with the findings in [31], total uncertainty (TU) correlates more with errors than knowledge uncertainty (KU) as shown by the F1-AUC scores. More specifically, we see that the F1-AUC is quite similar across the board when measured by TU, although cSGLB/cbSGLB has slightly worse predictive power on the OOD segment. When F1-AUC is measured by KU, our cSGLB/cbSGLB is capable of producing KU estimates that relate more closely to model errors than KU from the SGLB baseline.
At last, we present the OOD detection ROC-AUC performance on the evaluation data by using KU estimates. Our cSGLB/cbSGLB outperforms the SGLB baseline with a large margin on the OOD detection task, and even achieves a comparable performance to the real ensemble πππ 10, which is 5Γ more expensive. This highlights that our cSGLB/cbSGLB can produce high-fidelity KU estimates to detect domain (or distributional) shifts with a single model, and that our proposed cyclical gradient scheduling is effective in exploring different modes of a posterior. In real-world industrial applications, detecting OOD data or domain shifts in an efficient way is often crucial to ensure a safe deployment and operation of ML systems. Observing consistently high uncertainty (especially KU) from model predictions indicates that the patterns of new incoming data have deviated from the training. This often provides a strong signal for model refresh, ensuring that the ML system can be updated in time to avoid errors and operate safely in its "comfort zone" (with relatively low predictive uncertainty).
We present cyclical gradient scheduling and Cyclical SGLB for efficiently and effectively quantifying uncertainty in gradient boosting with a single model, and propose a data bootstrapping scheme to enhance diversity in posterior samples. We show empirically that our algorithms have superior performance over the state-ofthe-art SGLB, especially in quantifying knowledge uncertainty and for OOD detection. Accurately quantifying uncertainty in ML predictions can yield many benefits in real-world applications. Uncertainty directly measures the confidence in model predictions, not only improving interpretability, but also ensuring that costly mistakes can be avoided proactively. Consistently observing high uncertainty in predictions on incoming data stream often provides a reliable signal for data distributional shifts and/or model being obsolete. Uncertainty is also a key concept in optimal control and decision making, where it can be leveraged to experiment with different actions/decisions with controllable costs in search for the best operating point of an ML system. We believe that our work on efficient uncertainty quantification for GBDTs facilitates the adoption of uncertainty-enabled and uncertainty-aware ML systems, and more broadly promotes ML safety and a safe and trustworthy deployment of ML model in production.
The proposed Cyclical SGLB algorithm combines SGLB with cSG-MCMC [13] to effectively explore different modes of a highly multimodal posterior distribution. In this section, we summarize some key differences between our design and the original cSG-MCMC algorithm.
(1) cSG-MCMC is a sampling algorithm designed for Bayesian NNs, while cSGLB is built for GBDT models. In deep learning, full-batch gradient descent is usually not feasible, and techniques have been developed to explicitly compensate mini-batch noises, such as preconditioning [14]. Some also suggested applying an additional correction step called Metropolis-Hastings [15]. Treebased GB models can easily scale up to large industrial datasets and digest the full training set at each iteration. Therefore, our cSGLB uses full-batch GB in the sampling stage of each cycle to ensure high-quality samples being generated. (2) cSGLB puts a cyclical schedule on gradient scale while cSG-MCMC puts a schedule on step size. In addition, the original cSG-MCMC completely removed the injected Gaussian noises in the exploration stage, and cSG-MCMC reduced to regular stochastic gradient descent (SGD) during the period of exploration. Although the authors claimed that this amounts to posterior temping which is commonly used in DL domain, the implementation of cSG-MCMC algorithm does not follow closely/strictly the dynamics of SGLD during the exploration stage. In contract, we keep the injected noise term unchanged during the course of learning. Our design achieved similar effects compared with the step-size scheduling on a synthetic experiment, and we also ensure that cSGLB follows the dynamics of SGLD (more or less) at every iteration step. (3) Lastly, the gradient scaling (instead of step-size scheduling) has implementation benefits. The SGLB algorithm is made available in the CatBoost library [30], which only supports a constant step size (or learning rate). Our proposed cyclical gradient scaling (and data bootstrapping) can be implemented easily with the "user-defined loss function" available in the CatBoost package, without modifying a single line of the source code.
The ground truth density of the distribution is . We used the code released by the authors [13] to generate our results. Specifically, the SGLD was trained with a decaying lr ππ = 0.05(π + 1) β0.55 , and clr-SGLD was learned with a cyclical lr schedule with initial value π0 = 0.09 and exploration proportion π = 0.25. For our cg-SGLD, we fixed lr π = 0.01 and Gaussian noise scale as 0.4, and set πΌmax = 10, πΌmin = 1. The "noisy" version of SGLD (or NoisySGLD/N-SGLD) was trained with a fixed lr π = 0.02 and noise scale 5.0 (roughly 10Γ larger than the noise scale used in the other methods). Each chain was trained for 50π iterations and both clr-SGLD and cg-SGLD had 30 cycles. The results and findings are robust to random seeds, and similar results were observed with different seeds. We refer the interested readers to the original paper [13] for results of SGLD and clr-SGLD in parallel (or multi-chain) settings.
All experiments were conducted using CatBoost [30], one of the-state-of-the-art libraries for GBDTs. The ensemble of SGLB (ens20) contains 20 independent (with different random seeds) models with 1K trees each. The learning rate is π = 0.1, tree depth is 6, and random_strength = 100 and border_count = 128. The SGLB virtual ensemble and cSGLB virtual ensemble are trained with the same parameters except that we increase the number of trees to 2K and lower the lr for cSGLB to π = 0.05. Thus, the virtual ensemble is 10Γ more efficient in computation and memory than the actual SGLB ensemble.
For SGLB virtual ensemble, each 50th model from interval [1000, 2000] is added to the ensemble, making it a virtual ensemble of 20 members. For cSGLB virtual ensemble, we set π = 0.05, cycle length πΆ = 200, πΌmax = 10, πΌmin = 1, making it a virtual ensemble of 2000/200 = 10 members. For cbSGLB with bootstrapping, we additionally set exploration proportion π = 0.9 and mask probability π ππ = 0.66.
Data Summary A detailed summary of our final partitioning of the Weather Prediction dataset is included in Table 2.
Experimental Details We used default parameter settings for SGLB models as suggested in the original paper [12] for uncertainty quantification except that we set the subsample rate to 0.8 for stochastic gradient boosting. The real SGLB ensemble consists of (up to) 30 SGLB models trained with different seeds, each of 1K trees. In order to get more samples from a single chain, the virtual ensembles of SGLB and our cSGLB/cbSGLB were learned with a single model of 2K trees. We set learning rate for all models to π = 0.05, and tree depth to 6. For SGLB virtual ensemble, each 100th model from interval [1000,2000] was added to the ensemble, making it a virtual ensemble of 10 members. cSGLB and cbSGLB shared the same parameters with the SGLB counterpart. In addition, for cSGLB/cbSGLB virtual ensemble, we set cycle length πΆ = 200, πΌmax = 10.0, πΌmin = 1.0, making it a virtual ensemble of 2000/200 = 10 members. For simplicity, cSGLB used full-batch gradient boosting at each iteration step. In contrast, for cbSGLB with bootstrapping, we set exploration proportion π = 0.8, i.e., 80% of a cycle was treated as exploration, and set mask probability π ππ = 0.6 in the exploration stage. For model and parameter selection, we only used the in-domain (ID) development set and did not use the out-of-domain (OOD) development set. Although this may potentially lower our reported performance on the OOD evaluation set, we believe that it reflects better a real-world learning scenario where the shifted data is often unobserved and unavailable at training time.