Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
The 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.

Weaknesses:
I have some concerns about the technical issues. Please see the list in the question section.
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?

2. 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.

3. 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.

4. In calibrating variance, tuning $\gamma$ and $\delta$ on validation data is not a good solution. Can they be learned with a gradient descent?

5. 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$.

6. 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?

7. The writing can be improved, especially the mathematical expressions.
In Equation (1), the sum starts from $t=1$, not $i=1$.
Equation (3) and Equation (4) need to be modified.
limitations: No potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- The method can work with any GBDT model and can be applied to any trained model at inference time.
- The reported results show that the proposed approach outperforms existing methods (NGBoost and PGBM) in terms of both RMSE and probabilistic evaluation measures.

Weaknesses
- The inference time can increase significantly.
- The paper does not compare with the existing probabilistic prediction for GBDT implemented in CatBoost (see details below in Questions).
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.

2. 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?

3. There are some important questions that are not addressed in the main text, but the corresponding experiments are in the supplementary materials. For instance:
    - 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.
    - 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.

Minor:
- 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.

The paper is, in general, well written, and I noticed only minor typos in the text:
- Line 87: “mean and variance is” (should be “are”), the same for lines 141 and 189
- Caption of Figure 2: “means” -> “mean”
- Line 252: “Table” -> “Figure"

limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 

In the experiments, the new method is compared to two specific baselines on 20 tabular datasets, using NLL and CRPS as performance measures. 
strengths_and_weaknesses: Strengths:
- The paper is well written and easy to follow.
- Uncertainty estimation for gradient-boosted regression trees is an important research problem, because boosted trees usually yield SOTA performance on tabular datasets. 
- The experimental evaluation is quite extensive. 

Weaknesses:
- The proposed method comes without any theoretical justification. The method is in essence a heuristic. 
- I would have liked to see a comparison with nearest neighbor methods that use other similarity 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. 

The 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. 

To 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. 

The 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. 

In 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.  

NLL 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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.
strengths_and_weaknesses: ORIGINALITY

"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.

However, "originality" is often overrated in research: the authors seem to have made a substantial engineering contribution.

Although 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.

QUALITY

The 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.

CLARITY

The 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.

SIGNIFICANCE

The 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.

My concerns about significance are two-fold:

(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.

(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.

Although 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.

MINOR

Line 99: euclidean --> Euclidean

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.

Would the authors please mention any comparisons they have done between IBUG and the more intricate approaches they mention in Section 6?

Are the authors happy to tone down the claims of "better" with respect to other competing methods?

What is the sensitivity of IBUG to the parameter k? This is the number of nearest neighbors.
limitations: This is fine.
review_title: null

Meta-review: metareview: This paper presents a method  for extending any GBRT point predictor to produce probabilistic predictions such that the aleatoric uncertainty can be quantified. It computes a nonparametric distribution around a prediction using the k NNs where the distance is measured by a kernel that is similar to the random forest kernel. The paper is well written and easy to read. All of reviewers agree that it is a simple practical method that is well engineered. But all the techniques used in this system are existing ones, so that its technical novelty is limited. During the discussion period, I had more than a few communications with reviewers. One one hand, there were some concerns on the limited novelty, which I also agree with. In fact, this concern became more notable in the discussion. On the other hand, a strength is in its simplicity, practicability, and its excellence in engineering and design, how to critically evaluate alternative approaches, and how to design experiments that evaluate those approaches”. A few things that I would like the authors to consider in their future submissions include: (1) the method is applied to quantify only aleatoric uncertainty, which should be clearly mentioned in an earlier place in the paper, since these days we observe a few interesting methods for quantifying the predictive uncertainty (that is both aleatoric and episdemic uncertainty); (2) a kernel which is similar to the random forest kernel is used as a distance metric. Unlike RF, GBRT construct trees with small depth, so that it is expected that many instances fall in the same leaf. The behavior might be different from the case of RF. Despite a concern on the limited novelty, most of reviewers feel that this work can be accepted, so I recommend it for acceptance. 

confidence: Less certain
Decision: Accept