Leveraging Uncertainty Estimates To Improve Classifier Performance
Authors: Gundeep Arora
Srujana Merugu
Anoop Saladi
Rajeev Rastogi
Venue: ICLR 2024 poster (2024)
Keywords: Uncertainty estimation
binary classification
imbalanced classification
score recalibration
uncertainty based decision making
classification decision boundary
bin packing
estimation bias
posterior networks
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: 2D decision boundary on model score & uncertainty space boosts binary classification performance

Abstract: Binary classification typically involves predicting the label of an instance based on whether the model score for the positive class exceeds a threshold chosen based on the application requirements (e.g., maximizing recall for a precision bound). However, model scores are often not aligned with true positivity rate. This is especially true when the training involves a differential sampling of classes or there is distributional drift between train and test settings. In this paper, we provide theoretical analysis and empirical evidence of the dependence of estimation bias on both uncertainty and model score. Further, we  formulate the decision boundary selection using both model score and uncertainty, prove that it is NP-hard, and present  algorithms  based on dynamic programming and isotonic regression.  Evaluation of the proposed algorithms on three real-world datasets yield  25\%-40\%  improvement in recall at high precision bounds over the traditional approach of using model score alone, highlighting the benefits of leveraging uncertainty.

Published as a conference paper at ICLR 2024
LEVERAGING UNCERTAINTY ESTIMATES TO IMPROVE CLASSIFIER PERFORMANCE
Gundeep Arora, Srujana Merugu, Anoop Saladi, Rajeev Rastogi Amazon
gundeepa@ ama zon. com
ABSTRACT
Binary classification involves predicting the label of an instance based on whether the model score for the positive class exceeds a threshold chosen as per application needs (e.g., maximizing recall at a precision bound). However, model scores are often not aligned with the true conditional probability of the positive class. This is especially true when the training involves differential sampling across classes or there is distributional drift between train and test settings. In this paper, pro- vide theoretical analysis and empirical evidence of the dependence of model score estimation bias on both uncertainty and score. Further, formulate the decision boundary selection in terms of both model score and uncertainty, prove that it is NP-hard, and present algorithms based dynamic programming and isotonic re- gression. Evaluation of the proposed algorithms on three real-world datasets yield 25%-40% gain in recall high precision bounds over the traditional approach of using model score alone, highlighting the benefits of leveraging uncertainty.
INTRODUCTION
Many real-world applications such as fraud detection and medical diagnosis can be framed as bi- nary classification problems, with the positive class instances corresponding to fraudulent cases and disease prevalence, respectively. When the predicted labels from the classification models are used to drive strict actions, e.g., blocking fraudulent orders and risky treatments, the impact of erroneous predictions. This warrants careful selection of the class decision boundary using the model output while managing the precision- recall trade-off as per application needs.
critical to minimize
Typically, one learns classification model from training dataset. The class posterior distribution from the model is then used to obtain the precision-recats (PR) curve on a hold-out dataset with distribution similar to the deployment setting. Depending the application need, e.g.. maximiz- ing recall subject to a precision bound, a suitable operating point on the PR curve is identified to construct the decision boundary. The calibration plications with severe class imbalance, since it is a common practice to downsample the majority"] class during model training. This approach of downsampling followed by calibration on hold-out set is known to both improve model accuracy and reduce computational effort (Arjovsky et al. 2022).
the hold-out set is especially important for ap-
A key limitation of the above widely used approach is that the decision boundary is based solely on the classification model score and does not account for the prediction uncertainty. which has been the subject of active research (Zhou et al.] [022]] Sensoy et al.) 2018). natural question that emerges is whether two regions with similar scores but different uncertainty estimates should be treated identically when constructing the decision boundary. Recent work points to potential bene- fits of combining model score with estimates of uncertainty (Kendall & Gall 2017) for specialized settings (Dolezal et al. (2022) or via heuristic approaches (Pocevivciûté et al. (022). ) However, there does not exist an in-depth analysis why incorporating uncertainty leads to better classification, and how it can be adapted to any generic model in a post-hoe setting.
In this paper, we focus on binary classification with emphasis the case where class imbal- ance requires differential sampling during training. For brevity, we refer to the conditional prob-
Without loss of generality, assume that the downsampling is performed the class (label=0) and the model score refers to +ve class (label=1) probability.

---

Published as a conference paper at ICLR 2024
ability of the positive class as the positivity rate. Cognizant of the differences between the un- derlying distribution, train, and test sets, we refer to the corresponding positive class probabil- ities true, train and test positivity respectively. We investigate four questions: RQ1: Does model score estimation bias (deviation from test positivity) depend on uncertainty? RQ2: If so, how can construct optimal 2D decision boundary using both model score and un- certainty and what is their relative efficacy? RQ3: Under what settings of undersampling of negative class and precision range do we gain the most in recall from incorporating uncer- tainty? RQ4: Do uncertainty estimates also aid in better calibration of class probabilities?
Intuitively, choosing the decision boundary based on test positivity rate is likely to yield the best per- formance. However, the test positivity rate is not available beforehand and tends to differ from the model score as shown in Fig. Ta). Our exami- nation of RQ1 indicates that the score estimation bias, i.c., difference between test positivity rate and the model score often varies with uncertainty in a systemic fashion. Specifically, for a represen- tative setting with Beta priors, using Bayes rule, we observe that for input regions with a certain empirical train positivity rate, the "true positivity" (and hence test positivity rate) is shifted towards the global prior, with the shift being stronger for regions with low evidence. While Bayesian mod- els try to adjust for this effect by combining the evidence, i.e., the observed train positivity with "model priors", there is still significant bias when there is mismatch between the model priors and true prior in regions of weak evidence (high un- certainty). Differential sampling across classes during training further contributes to this bias. This finding that the same model score can map to different test positivity rates based on uncertainty lev- els indicates that the decision boundary chosen using score alone is likely to be suboptimal relative to the one optimized using uncertainty and model score. Fig. [b)) depicts maximum recall bound- aries for specified precision bound using score alone (yellow) and with both score and uncertainty estimates (red) validating this observation, which motivates the subsequent questions RQ2-RQ4.
03/5
Levets
15.0%
1ap modium bow
90.0%
0333
Test Soaatti
0225
0813
0825
0223
50.0%
0.15
0
Model Score
Model Score
(a)
(h)
Figure 1: (a) Test positivity rate vs. model score for different uncertainty levels on Criteo with 33% undersampling of negatives during training. (b) Heatmap of test positivity for different score and un- certainty ranges. Proposed method(red) yields better recall over vanilla score- based threshold (yellow).
Contributions. Below we summarize our contributions leveraging the relationship between score estimation bias and uncertainty to improve classifier performance.
1. To motivate the need for incorporating uncertainty into decision making, we consider a repre- sentative Bayesian setting with Beta priors and Posterior Network (Charpentier et al.] 2020) as an exemplary uncertainty estimation method, and demonstrate that the test positivity rate depends on both score and uncertainty, and monotonically increases with score for a fixed uncertainty. There is also a dependence on the downsampling rate in case of differential sampling during training 2. We introduce the 2D decision boundary optimization problem in terms of maximizing recall for a target precision (or vice versa) using both uncertainty and model score. Keeping in view com- putational efficiency, we partition the model score x uncertainty space into bins, demonstrate that the 2D decision boundary optimization problem is connected to bin-packing, and prove that it is Na-hard (for variable bin sizes) via reduction from the subset-sum problem (Caprara et al.) 2000). This formulation is independent of the choice of modeling and uncertainty estimation method.
3. We present multiple algorithms for solving the 2D binned decision boundary problem defined over score and uncertainty derived from any blackbox classification model. We propose an equi-weight bin construction by considering uncertainty quantiles that are further split into score quantiles. For this case, we present polynomial time DP algorithm with optimality guarantees. Additionally, we propose greedy algorithm that first performs isotonic regression (Stout 2013) independently for each uncertainty level, and selects a global threshold on calibrated probabilities.
We present results on three real-world datasets to demonstrate that our proposed 2D decision boundary algorithms yield 25%-40% gain in recall @ precision over vanilla score-thresholding.
2 RELATED WORK
Uncertainty Modeling, Existing approaches for estimating uncertainty can be broadly categorized
as Bayesian methods (Xu & Akella 2008 Blundell al., 2015b; Kendall Gal 2017). Monte
2

---

Published as a conference paper at ICLR 2024
Carlo methods (Gal & Ghahramani 2016) and ensembles (Lakshminarayaman et al. 2017). Dropout
and ensemble methods estimate uncertainty by sampling probability predictions from different sub- models during inference, and compute intensive. Recently, Charpennter et al. (2200) proposed Posterior Network to directly learn the posterior distribution over predicted probabilities, enabling fast uncertainty estimation for input samples in single forward pass and providing analytical framework for estimating both alcatoric and epistemic uncertainty, which makes it amenable for our analysis of score estimation bias. While [enngs al. (022) provides detailed discussion on Pos- terior Networks highlighting the gaps in using learning with uncertain cross-entrope loss function to accurately estimate epistemic uncertainty, this aspect is orthogonal to our results since we only employ Posterior Network as an exemplar of uncertainty estimation. Uncertainty-basee
Decision Making. (Blundell et al., (205a)) use uncertainty along with model score to drive explore-exploit style online-learning. but leveraging uncertainty to improve precision and recall has not been rigorously explored in the literature. Approaches in the digital pathology domain either use heuristics to define 2D decision boundary using model score and estimated un- certainty (Pocevivciûté et al. 2022), or use static uncertainty thresholds to withhold predictions for low-confidence samples from the test dataset, to boost model accuracy (Dolezal et al.) [0022] [Zhou iet al., (022). Troffaes| (2007) and Denceux (2019) focus on decision-making using a risk-adjusted utility function that incorporates uncertainty modeled via belief functions and is determined by ax- iomatic criteria such as minmax and Hurwicz criterion without any data-bau based calibration.
Model Score Recalibration. These methods transform the model score into a well-calibrated prob- ability using empirical observations on hold-out set. Earlier approaches include histogram bin- ning (Zadrozny & Elkan 2001), isotonic regression (Stout, 2013), and temperature scaling (Guo et al. (017), all of which consider the model score alone during recalibration. Uncertainty Tool- box (Chung et al. (02I)) implements recalibration methods taking into account both uncertainty and model score but is currently limited to regression. In our work, we propose an algorithm (MIST 3) that first performs ID-isotonic regression on samples within an uncertainty level to calibrate prob- abilities and then selects global threshold. In addition to achieving a superior decision boundary, this results in lower calibration error compared to using score alone.
3 RELATIONSHIP BETWEEN SCORE ESTIMATION BIAS AND UNCERTAINTY
To demonstrate the dependence of score estimation bias on uncertainty, we consider a representative data generation scenario and a common uncertainty modeling method Posterior Network ?
Notation. Let x denote an input point and y the corresponding target label that takes values from the set of class labels C = {0, 1) with c denoting the index over the labels. See Appendix [ We use P..) denote probability and wb to denote an index iterating over integers in (1b, .ub).
3.1 Background: Posterior Network Posterior Network (Charpentier et al. 2020) estimates a closed-form posterior distribution over predicted class probabilities for any new imput sample via density estimation as described in Appendix D For binary classification, the posterior distribution x is a Beta distribution with parameters estimated by combining the model prior with pseudo- counts generated based on the learned normalized densities and observed class counts. Denoting the model prior and observed counts for the class e E C by 8. and No. the posterior distribution of pre- dicted class probabilities at is given by g(x) = Beta (or (x), (x(()) where (x(x) 3 + (x) and (x)= = NzP(2(x)) (x) c; d), Ve C. Here, x(x) is the penultimate layer representation of x and & denotes parameters of a normalizing flow. Model score 5model (x)) for positive class is given by
8 + (x()
a1 (x)
smadel
(x) ExeclE + Bx(]]
(I)
ai (x) + (x)
Uncertainty u(x) for x is given by differential entropy of distribution H (q (xx) Since (xx) is Beta distribution, for same score,(i.e.. on (x)), uncertainty is higher when Leec (x.(x) is lower.
3.2 Analysis of Score Estimation Bias: For input point x. let Strue (x), Strain (x), Stest (x), and Smodel (x) denote the true positivity, empirical positivity in the train and test sets, and the model
2 Theorem 3.1 a) connecting train, true, and test positivity is independent of the uncertainty modeling. 3 (x())) log B(Ou, a1)-aaaa -av function and B ( -) is the Beta function.
+a - aa1) - (a. - 1a.()a)) where wo-)) is the digamma
3

---

Published as a conference paper at ICLR 2024
score respectively. Assuming the train and test sets are drawn from the same underlying distribution with possible differential sampling across the classes, these variables are dependent on each other as shown in Fig. 2 We consider the following generation mechanism (Appendix E where the true positivity rate is sampled from a global beta prior, i.e., Strue (x) ~ Beta ($1 ,,8% The labels y(x) in the test set are generated from Bemoulli distribution centered at Strue (x). In the case of training
set, we assume that the negative class is sampled at rate - compared to positive class. Note that indicates undersampling, and т < 1 indicates oversampling of the negative class. We define
8f + (x)+ i.e., the ratio of combined priors to the combined likelihood evidence.
7x)
Using Bayes' rule, one can estimate the expected true and test positivity rates conditioned on train positivity in terms of available evidence. For Posterior Networks, one could further use the relationship between the train positivity rate and the model score to obtain the expected score estimation bias. For ease of presentation, we show the result for t in Theorem 3.I below with the gen- eral case (Theorem E.4 and proof details in Appendix E
eegaloms by
sardirg
Theorem 3.1. For data generated as per Fig. 2 but no
differential sampling (T = 1), the below results hold: (a) The expected test and true positivity rate conditioned
Figure Dependencies among various positivity rates and the model score.
on the train positivity are equal and given by
Strain (x) + EX(x)
Elstrue (x))stra) (x)] ElStest (x) (x) strrittaxx(x (x)]
X(x)
B² where ç PT is the positive global prior, and X(x) B7 +
Do(xx is its ratio to evidence.
(b) For Posterior Networks, test and true positivity rate conditioned on model score Smodel (x) can be obtained using Strain = 5model (x) - (w Smodel (x)))(x). Hence, the estimation bias,
i.e, difference between model score and lest positivity is given by (Smadel (x)(v Eu)r(x)) where 1407(x)
and v
Mx) 7(x)
of + is the ratio of global and model modeopriors.
of +B6
Relationship of 7xx) and u(z): Note that E.axx)
1E + )(3) For
a fixed score, E. (x(x)
varies inversely with uncertainty u(x) = H (q(x)). mak-
ing the latter positively correlated with (x). Further details in Appendix E.2
No differential sampling (T = 1). Since the
model scores estimated by combining the model priors and the evidence, Smmdel (x) = s(x) differs from the train positivity rate in the direction of the model prior ratio w. On the other hand, expected true and test positivity rate dif- fer from train positivity rate in the direction of true class prior ratio &. When the model prior matches true class prior both on positive class ra- tio and magnitude, i.e., v = 1,5 = w, there no estimation bias. In practice, model priors are often chosen to have low magnitude and estima- tion bias is primarily influenced by global prior ratio with overestimation (i.e., expected test pos- itivity < model score) in the higher score range (S < s(x)) and the opposite is true when (5 > s(x)). The extent of bias depends on relative strengths of priors w.r.t evidence denoted by 7(x), which is correlated with uncertainty. For this case, the expected test positivity is linear and monotonically increasing in model score. The trend Ev).
Test Positivity Rate
1.0
Jan inceratry encerrary
1.0
8.8
0.
Toss 1 Positivity
6.6
0.6
3.4
64
0.2
3.0
Model Score
Model Score (b)
Figure 3: Test positivity vs. model score curves for (a) few choices of 7xx) with w = 0.5, + = 3. and (b) few values of 7 with w = 0.5 and medium uncer- tainty using data simulation per Fig.
with respect to uncertainty depends on sign of (s(x)(1 1)
General case (r > 1, Theorem E.4) Here, the expected behavior is affected not only by the inter- play of the model prior, true class prior and evidence as in case of 7 1. but also the differential sampling. While the first aspect is similar to the case T = 1, the second aspect results in overes- timation across the entire score range with the extent of bias increasing with r. Fig. 3(a) shows
4

---

Published as a conference paper at ICLR 2024
the expected positivity rate for a few different choices of (xx) and fixed choice of w 0.5 and r = 10 while Fig. ()) shows the variation with different choices of т. We validate this behavior by comparison with empirical observations in Sec. 6
The primary takeaway from Theorems 3.I and E.4 is that the score estimation bias depends on both score and uncertainty for common scenarios. For given model score, different samples can corre- spond to different true positivity rates based on uncertainty level, opening an opportunity to improve the quality of the decision boundary by considering both score and uncertainty. However, direct adjustment of model score based on Theorems J.T and i. not feasible or effective since the actual prior and precise nature of distributional difference between test and train settings might not follow Fig. 2 or even be known (see Appendix H). Further, even when there is information on differential sampling rate used in training, class-conditional densities learned from sampled distributions tend to be different from original distribution especially over sparse regions.
4 2-D DECISION BOUNDARY PROBLEM
Given an input space X' and binary labels C, binary classification typically involves finding a map- ping v/b X + C that optimizes application-specifi performance. Fig. 4 depicts a typical super- vised learning setting where labeled training data Dtrain. created via differential sampling along classes, is used to learn a model. A hold-out labeled set Dhold, disjoint from training and similar in distribution to deployment setting is used to construct a labeling function t/,, based on model output.
Traditionally, we use the labeling function th [[s(x) 2 bj with boundary b = [b] defined in terms of score threshold opti- mized based on the hold-out set Dhold- When the model outputs both score and uncertainty (s(x), u(x),, we have a 2D space to be par- titioned into positive and negative regions. In Sec. 3 we observed that the true positivity rate is monotonic with respect to score for a fixed uncertainty. Hence, we consider a boundary of the form (x)) = [[x 2 b(u(x))] where b(u) is the score threshold for uncertainty
Woadio bort od
Debioon Exanaay
Dast:
Lopping
Figure 4: Binary classification with model training fol- lowed by decision boundary selection on hold-out set.
To ensure tractability of decision boundary se- lection, natural approach is to either limit b to a specific parametric family or discretize the uncertainty levels. We prefer the latter option as it allows generalization to multiple uncertainty estimation methods. Specifically, we partition the 2D) score-uncertainty space into bins forming grid such that the binning preserves the ordering over the space. (i.e., lower values go to lower level bins). This binning could be via independent splitting on both dimensions, or by partitioning on one dimension followed by nested splitting on the other.
Let and U4 denote the possible range of score and un- certainty values, respectively. Assuming K and L de- note the desired number of uncertainty and score bins, let p : U x S > {1,... K} {1..... , I.} denote partitioning such that any score-uncertainty pair (u, 8)
argmax s... precissio((h)220 0Sb
recall (1/b)
(2)
is mapped to a unique bin (i.j) (o" (u), (u),p((s) in the K x L grid. We capture relevant infor- mation from the hold-out set via two K x L matrices j)] and [n(i,j]] where p(i,j) and n(i, denote the positive and the total number of samples in the hold-out set mapped to the bin (i.j) in the grid. Using this grid representation, we now define the 2D Binned Decision Boundary problem. For concreteness, focus on maximizing recall subject to a precision bound though our results can be generalized to other settings where the optimal operating point can be derived from the PR curve.
2D Binned Decision Boundary Problem (2D-BDB): Given K L grid of bins with positive sample counts (p(i,j) and total sample counts jn( corresponding to the hold-out set Dhold and a desired precision bound o, find the optimal boundary b = [b()] that maximizes recall subject to the precision bound as shown in Eqn. 2 Here recall((b)) and precision( denote the recall and precision of the labeling function (x) = 1 (sxx)) > b((((x(x)) with
5

---

Published as a conference paper at ICLR 2024
respect to true labels in Dhold- While Dhoid is used to determine the optimal boundary, actual efficacy is determined by performance on unseen test data.
Connection to Knapsack Problem. Note that the 2D decision boundary problem has similarities to the knapsack problem in the sense that given a set of items (i.c., bins), we are interested in choosing subset that maximizes certain "profit" aspect while adhering to bound on specific "cost" aspect. However, there are two key differences 1) the knapsack problem has notions of cost and profit, while in our case we have precision and recall. On the other hand, our cost aspect is the false discovery rate (i.e., I- precision) which is not additíve, and the change in precision due to selection of a bin depends on previously selected bins, and our problem setting has more structure since bins are arranged in 2D-space with constraints on how these are selected.
2-D DECISION BOUNDARY ALGORIHTMMS
We provide results of computational complexity of 2D-BDB problem along with various solutions.
5.1 NP-hardness Result: It turns out the problem of computing optimal decision boundary over a
2D grid of bins (2D-BDB) is intractable for general case where bins have different sizes. We use reduction from NP-hard subset-sum problem (Garey & Johnson 1990) for the proof (Appendix FF).
Theorem 5.1. The problem of computing an optimal 2D-binned decision boundary is NP-hard. O
5.2 Equi- weight Binning Case A primary rea- son for the intractability of 2D-BDB problem is that one cannot ascertain the relative "good- ness" (i.e., recall subject precision bound) of a pair of bins based on their positivity rates alone. For instance, it is possible that a bin A with lower positivity rate might be prefer- able to a bin B with higher positivity rate since the choice would be based on the overall posi- tivity accounting for the current selected bins. Specifically, for current selection, bin A, bin with total samples and positives given by (N,P), P), (nA, and (nB.PB), we could have PA/nA= > Pa PB/NB ng and (P + pP)p PB)B(N + nB) > (P+Pa)/(N +nA) for n # nB). To address this, we propose a binning policy that preserves the partial ordering along score and uncertainty yielding equal-sized bins. We design an opti- mal algorithm for this special case using the fact that a bin with higher positivity is prefer- able among two bins of the same size.
Algorithm 1 Optimal Equi-weight DP-based [EW-DPMT]
Input:
Equi-sized K L grid with positive sample counts [p(i,j)]xxx total count N, precision level
Output:
maximum (unnormalized) recall R" and corre- sponding optimal boundary b' for precision 2 // Initialization
R(i, m)
D0;
b(i,
1;
V|i [TK,, [m]6"
// Pre-computation of cumulative sums of positives (1, 0) = 0. [:1
((.j) = ビド= p(i,j') [0, bli
// Base Case: First Uncertainty Level
R(1, m) [11,m) b(1, m. 1) = L-m, m, [m]
// Decomposition: Higher Uncertainty Levels for = to K do for m = to iL do
j = argmax (rtinax(T(iij)) + R(i - 1, m j)]
OSi5L
R(i, m) = [(tjj" ) + R(i - 1, jr)
b(i, m, :) = b(i - 1, m - j:
b(i, m, i) L -
Binning strategy: To construct an equi-weight K x I. grid, we first partition the samples in Drote into K quantiles along the uncertainty dimension and then split each of these into I. quantiles along the score. The bin indexed by (i,j) contains samples from 7th global uncer- tainty quantile and the 5th score quantile local to tth uncertainty quantile. This mapping pre- serves the partial ordering that for any score level, the uncertainty bin indices are monotonic with respect to its actual values. Note that while this yields equal-sized bins on Dhota, using same bound- aries on the similarly distributed test set will only yield approximately equal bins.
end for end for // Maximum Recall for Precision m
argmax OSmgKL s.t. mN R(K,m)2
[R(K)
R' = R(K, m(); b = b(K,m².) return (R",b")
Dynamic Programming (DP) Algorithm: For equi-weight binning, we propose a DP algorithm (Algorithm [ for the 2D-BDB problem that identifies maximum recall decision boundary for given precision bound by constructing possible boundaries over increasing uncertainty levels. For 1 S < K, 0 < m & K L, let R(i, m) denote the maximum true positives for any boundary over

---

Published as a conference paper at ICLR 2024
the sub-grid with uncertainty levels up to the 1th uncertainty level such that the boundary has exactly m bins in its positive region. Further, let b(i, m, denote the optimal boundary that achieves this maximum with b(i, m,,') denoting the boundary position for the uncertainty level i' i i). Since bins are equi-sized, for a fixed positive bin count, the set with most positives yields the highest precision and recall. For the base case = 1, feasible solution exists only for 0 I m I L. and corresponds to picking exactly m bins, i.c., score threshold index 6(1, m, 1) = L m. For i > 1, we can decompose the estimation of maximum recall as follows. Let j be the number of positive region bins from the tth uncertainty level. Then the budget available for the lower (i
uncertainty levels is exactly m j. Hence, we have, R(i, m) max [T. + R(i 1, m -)),
OS7ST.
where π (i. ΣS -. 5'), i.e. the count of positives in the j highest score bins, The optimal boundary b(é, m.:) is obtained by setting b(i, m. i) = L -- and the remaining thresholds to that of 1(1 m - ;:) where je is the optimal choice of j in the above recursion. Performing this computation progressively for all uncertainty levels and positive bin budgets yields maximum recall over the entire grid for each choice of bin budget. This is equivalent to obtaining the entire PR curve and permits choosing the optimal solution for given precision bound. From R K, m), we can choose the largest m that meets the desired input precision bound to achieve optimal recall. The overall computation time complexity is O(K²L3). More details in Appendix G
5.3 Other Algorithms Even though the 2D-BDB problem with variable sized bins is NP-hard, it permits an optimal peeudo-oolyoomial time DP solution similar to the presented above. VARIABLEE- WEIGHT DP BASED MULTI- WIL.TI-TRREHOOLDS (VW-DPMT)) (4) tracks best recall at sample level instead of bin-level in EW-DPMT (I.. We also consider two greedy algorithms with lower computational complexity than the DP solution that are applicable to both variable and (GMT), computes score thresholds that maximize recall at precision bound independently for each uncertainty level. The second, MULTI- SSIGLL THRESHOLD (MIST) is based on recalibrating scores within each uncertainty level independently using 1-D isotonic regression. We identify global threshold on calibrated prob- abilities that maximizes recall over the entire grid so that the precision bound is satisfied. Since the recalibrated scores are monotonic with respect to model score, the global threshold maps to distinct score quantile indices for each uncertainty level. This has a time complexity of O(K (KL)),
equal-size bins. The first, SEGEDY-MUUTT--TRRESIII
6 EMPIRICAL EVALUATION
6.1 EXPERIMENTAL SETUP
Datasets:
For evaluation, we use three binary classification datasets: (i) Criteo: An online ad- vertising dataset consisting of 445 MM ad impressions with click outcomes, each with 13 contin- uous and 26 categorical features. We use the split of 72% 18% 10% for nain-validation-tes from the benchmark, (ii) Avazu: Another CTR prediction dataset comprising 440 MM samples each with 22 features describing user and ad attributes. We use the train-validation-tesl splits of 70% : 10% : 20%, from the benchmark (iii) E G-Com: A proprietary e-commerce dataset with -4 MM samples where the positive class indicates rare user action. We create rain-validation-tes sets in the proportion 50% 12% : 38% from different time periods. In all cases, we train with varying degrees of undersampling of negative class with test set as in the original distribution.
Training: For Criteo and Avazu, we use the SAM architecture (Cheng & Xue 2021 as the backbone with 1 fully-connected layer and 6 radial flow layers for class distribution estimation. For E-Com, we trained a Transforfrr (Gorishnly et al., (021) backbone with 8 radial flow layers. Binning strategies: We consider two options: (i) ranges are divided into equal sized K and L intervals, respectively. Samples with uncertainty in the 7thh uncertainty interval, and score in the jth score interval are mapped to bin (i. (ii) Equi-weight where we first partition along uncertainty and then score as described in Sec. [ Algorithms: We compare our proposed decision boundary selection methods against (i) the baseline of using only score, SINGL.F THRESHOLD (ST) disregarding uncertainty, and (ii) state-of-the-an art 2D decision boundary detection method for medical diagnosis (Pocevivciúté et al., 2022),, which we call HEURISTIC RECALIBRATION (HR). The greedy algorithms (GMT, MIST), variable weight DP algorithm (VW-DPMT) are evaluated on both Equi -weight and Equi span settings, and the equi-weight DP algorithm (EW-DPMT) only on the former. All results are on the test sets.
where the uncertainty and score
7

---

Published as a conference paper at ICLR 2024
Critec, 90% Precision
Avazu, 70% Precision
E-Com, 70% Precision
T=3, Pos:Neg= = 1:3
r=5, Nos:Neg = 1:5
r=5, Pos:Neg Neg = 1:24
Algorithm
Equi-Span
Equi-weight
Equi-Span Equi-weight
Equi-Span
Equi-
Score only
ST
40.5% 2n
1.92%
1.92%+-.6%%
17.6%
17.6%
Score and Uncertainty baxed
HR GMT MIST EW-DPMT VW-DPMT
1.2%
0.8%
0.4% 1..4%
0.4%
11.5%.49.8%
11.5% 49.8%
2.4%
2.6%.4..3%
2.6% 0.33%.
2.6%
17. 17.8%64..7%
20.3% r%
2.5%
4.7%
2. +0.3%
2. 2.7% 477440.000 +..3%
18. 18.7%649.2%
21.6%
2.7%40.3%
2. 2.7%
22.3%
2.7%=_033%
2.7%+0.3%%
2.4% +0.3%
2.4%++0.3%
20.0%%48.7%
22.3%
Table 1: R PrecisionBound of various decision boundary methods on Criteo, Avazu E-Com data.
6.2
RESULTS AND DISCUSSION
RQI: Estimation Bias Dependence on Score & Uncertainty. From Sec. 3 we observe that the estimation bias and thus the test positivity rate is dependent on both uncertainty and the model score. Fig. and Fig. show the empirically observed behavior on the Critec dataset and synthetic data generated as per Fig. [ respectively with w 0.5, F == 3, E 0.25 in both cases. The observed empirical trends are broadly aligned with the theoretical expectations in Sec. 3 even though the assumption of a global Beta prior might not be perfectly valid. In particular, the separation be- tween uncertainty levels is more prominent for the higher score range in these imbalanced datasets, pointing to the criticality of considering uncertainty for applications where high precision is desir- able. To validate this further, examine subsets of data where the algorithms EW-DPMT and ST differ on the decision boundary for 90% precision (with #score-bins bins = 500, #uncertainty- =3) on Criteo dataset. We observe that the bin [xx(x), u(x)) (0.984, 0)] with positivity rate 0.91 is labeled as positive by EW-DPMT but negative by ST, while the reverse is true for the bin [(s(x), u(x))= = (0.996, 0.667)] with a positivity rate 0.87. Note that ((s(x), u(x)) are percentiles here. This variation of positivity with uncertainty for the same score substantiates the benefits of flexible 2D decision boundary estimation. More analysis of these bins in Appendix [.I]
RQ2: Relative Efficacy of Decision boundary Algorithms. Table shows the recall at high pre- cision bounds for various decision boundary algorithms on three large-scale datasets with 500 score and 3 uncertainty bins, averaged over 5 runs with different seeds. Since Avazu and E-com did not have feasible operating points at 90% precision, we measured 7e%% precision. Across all the datasets, we observe a significant benefit when incorporating uncertainty in the decision boundary selection (paired t-test significance p-values in T At 90% precision, EW-DPMT on Criteo is able to achieve 22% higher recall (2.7% vs 2.2%) over ST. Similar behavior is observed on Avazu and E com datasets where the relative recall lift is 42% and 26% respectively. Further, the Equi-we i ght binning results in more generalizable boundaries with the best performance coming from the DP algorithms (EW-DPMT, heuristic baseline HR (Pocevivciaté et al., 2022) performs poorly since it implicitly assumes that positivity rate monotonically increases with uncertainty for a fixed score. While both EW-DPMT and MIST took similar time (~ 100s) for 500 score bins and uncertainty bins, the run- time of the former increases significantly with increase in the bin count. Considering the excessive computation required for VW-DPMT, isotonie regression-baxee based algorithm MIST and EW-DPMT seem to be efficient practical solutions. Results on statistical statistical significance and runtime comparison are in Appendix C33 and Appendix CC4) Fig. ((a) and Table [
-PDDPMT) and the isotonic regression based MIST. The
show the gain in recall for uncertainty- based 2D-decision boundary algorithms relative to the baseline algorithm ST highlighting that the increase is larger for high precision range and decreases as the precision level is reduced. Experi- ments with other uncertainty methods such as MC-Dropout (Gal & Ghahramani 2016) (see Table 5 ) also point to some but not consistent potential benefits possibly because Posterior networks capture both epistemic and aleatoric uncertainty while MC-Dropout is restricted to the former.
RQ3: Dependence on choice of bins and undersampling ratio.: Binning configuration. Fig. 5(a) and 5jbb) show how performance (Recall @ (rencssionBound) of EW-DPMT varies with the number of uncertainty and score bins for Criteo and Avazu datasets. We observe a dataset dependent sweet-spot (marked by star) for the choice of bins. Too many bins can lead to overfitting of the decision boundary on the hold-out set that does not generalize well to test setting, while under- binning leads to low recall improvements on both hold-out and test sets.
8

---

Published as conference paper at ICLR 2024
R90% Precision
Recall@770% Precision
2.7%
2.0%
Puunc #uncertainty-bon 15
17 13
Recall @770% Precision
3.5
EW-OPMT
3.0
2.0
1.5
150 250 500 1000 1500
# #ccore bins
Under-sampling Ratio
(a)
(c)
Figure 5: Impact of # bins along uncertainty and score for EW-DPMT (a) Criteo (T = Recall 990%
Precision) and (b) Avazu (T 5, Recall@ PrePreciio. (c) Impact of undersampling level (r) during training on Recall PrePrccioo for ST and EW-DPMT on Avazu.
Percentage lift Recall
EWAOPHT
MIST
800
1ST MIST
0.03
Precision bound
Model Score Percentile
(a)
(b)
Figure 6: (a) Relative gain in recall on uncertainty-baat 2-D decision boundary algorithms over the base-
line ST on Criteo dataset (r 3) for different precision bounds. (b) Cumulative Expected Calibration
Error(ECE) between MIST and IST baseline Avazu dataset (T 5).
Undersampling Ratio. Fig. 5Jc) captures the Recall @ 70% Precision performance of EW-DPMT and ST for different levels of undersampling (7) of the negative class on the Avazu dataset averaged over 5 seeds. For both the algorithms, observe
improvement in recall performance initially (till 5 2.5) which disappears for higher levels of downsampling in accordance with prior stud- ies (Arjovsky al. 2022). We observe that EW-DPMT consistently improves the Recall 70% precision over ST with more pronounced downsampling (i.c.. higher values of T).
RQ4: Impact of leveraging uncertainty for probability calibration. To investigate the potential benefits of incorporating uncertainty in improving probability calibration, we compared the proba- bilities output from MIST algorithm with those from a vanilla isotonic regression (IST) baseline on Expected Calibration Error (ECE) for every score-bin, bine averaged across different uncertainty levels. Fig. (b) demonstrates that the difference between ECE for MIST and IST increases as we move towards higher score range. Thus, the benefit of leveraging uncertainty estimates in calibration is more pronounced in high score range (i.e. high precision levels). More details in Appendix C.6
CONCLUSION
Leveraging uncertainty estimates for ML-driven decision-making is key research area. In this pa- per, we examined potential benefits utilizing uncertainty along with model score for binary clas- sification. We provided theoretical analysis that points to the discriminating ability of uncertainty and formulated a novel 2-D decision boundary estimation problem based on score and uncertainty that is NP-hard. We also proposed practical solutions based on dynamic programming and isotonic regression. Empirical evaluation on real-world datasets point to the efficacy of utilizing uncertainty in improving classification performance. Future research directions include (a) designing efficient algorithms for joint optimization of binning configuration and boundary detection, (b) utilizing un- certainty for improving ranking performance and explore-exploit strategies in applications such as recommendations where the relative ranking matters and addressing data bias is critical, and (c) extensions to regression and multi-class classification settings (see Appendix H).

---

Published as a conference paper at ICLR 2024
REFERENCES
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021. URL http:: httppp/t///ptteeeeee....... wtt..eeeooouuooeeeaiaaa........
Martin Arjovsky, Kamalika Chaudhuri, and David Lopez-Paz. Throwing away data improves worst- class enror in imbalanced classification, 2022. URL httpss:/aaxx...orr//bbb///
11672
R. E. Barlow and H. D. Brunk. The isotonic regression problem and its dual. Journal the American Statistical Association, 67(337):140-144 147, 1972. ISSN 01621459. http::/://ww jstor.
Dtq/stabbe/222411
Viktor Bengs, Eyke Hüllermeier, and Willem Waegeman. Pitfalls of epistemic uncertainty quan- tification through loss minimisation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL attps://oppereviie net.eewweeeeeeeeeeeeeeeeeeeeeeee wtwp://wwwweee//omiieeeeeeee wtrrrrorrumnndpperer AR2W5
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. In Proceedings of the 32nd International Conference on International Confer- ence on Machine Learning- Volume 37, ICMI1'1,, pp. 1613-1622. JMLR.org, 2015a.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks, 2015b. URL httpp:/tts////iii org. abs 1505 05424
Alberto Caprara, Hans Kellerer, and UIrich Pferschy. The multiple subset sum problem. SIAM Journal on Optimization, 1 11(2):308-319 2000. doi: 10.11377510552224984448833 URL
https://doi.
Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Posterior network: Uncertainty estimation without ood samples via density-based pseudo-counts. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Yuan Cheng and Yanbo Xue. Looking at CTR prediction again: Is attention all you need? In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '21, pp. 1279-1287, New York, NY. USA, 2021. Association for Computing Machinery. ISBN 97814908383 450380337.
doi: 10. 241145//404435344622888 URL https:
//doi.org/11 11w....1111/34401 0110833334448299 3462936
Youngseog Chung, Ian Char, Han Guo, Jeff Schneider, and Willie Neiswanger. Uncertainty toolbox: an open-source library for assessing, visualizing, and improving uncertainty quantification. arXiv preprint arXiv:2 109. 10254, 2021.
Thierry Dencexx. Decision-making with belief functions: review. International Journal of Ap- proximate Reasoning, 109:87-110, 2019. ISSN 0888-613X. doi: http::/ddoi.rrg/11100//// ijjar 2019.03.009. URL https:// wwtp///wwwww/.mmm sciencedi rect. com/ /ttps//ennce/aaicee/p...p/
S088861 00138663318305555
James Dolezal, Andrew Srisuwananukorn, Dmitry Karpeyev, Siddhi Ramesh, Sara Kochanny, Brittany Cody, Aaron Mansfield, Sagar Rakshit, Radhika Bansal, Melanic Bois, Aaron Bungum, Jefree Schulte, Everett Vokes, Marina Garassino, Aliya Husain, and Alexander Pear- son. Uncertainty-infooen deep learning models enable high-confidence predictions for digital histopathology. Nature Communications, 13, 11 2022. doi: 10.10888441447--223440555-
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model un- certainty in deep learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, pp. 1050-1059. JMLR.org, 2016.
Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of JP-CCompeteeness W. Freeman Co., USA, 1990. ISBN 0716710455.
10

---

Published as a conference paper at ICLR 2024
Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Revisiting deep learning models for tabular data. In NeurIPS, 2021.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICMC' 17, pp. 1321-1330. JoLR.org, 2017.
Alex Kendall and Yarin Gal. What uncertainties do we need in Bayesian deep learning for computer vision? Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, pp. 5580-5590, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6405-6416, Red Hook, NY, USA, 2017.
Curran Associates Inc. ISBN 9781510860964.
Thomas Mortier, Marek Wydmuch, Krzysztof Dembezyúski, Eyke Hüllermeier, and Willem Waege- man. Efficient set- valued prediction in multi-class classification. Data Min. Knowl. Discov,, doi: 10. 1000000/111118-210000755 0221000551-
35(4):1435-1469 jul 2021. ISSN 1384-5810.
URL
https://doi.oot .rg. /10. /000/>10000
Milda Pocevivciûte, Gabriel Eilertsen, Sofia Jarkman, and Claes Lundström. Generalisation effects of predictive uncertainty estimation deep learning for digital pathology. Scientific Reports, 12,
05 2022. doi: (00038/41119-022-11133
Murat Sensoy, Lance Kaplan, and Melih Kandemir. Evidential deep learning quantify classifi- cation uncertainty. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- BiaacBinnchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL http:: /tpppppe///oooocediigg......s http://prrooeediinn.e.eeerr.pppp neurips cassscc//ee wttppppppppp////////.... 4 222a pdf
Q. Stout. Isotonic regression via partitioning. Algorithmica, 66, 05 2013. doi: 10.1007/ -00453-012-90 012-9628-4
Matthias C.M. Troffaes. Decision making under uncertainty using imprecise probabilities. Interna- tional Journal of Approximate Reasoning, 45(1))17-29, 2007. ISSN 0888-613X. doi: https://doi.
org/10 1016/j (0000666..jar.22006000000 001. URL https: httpp::/www...
/www www.eseiecceeiret.cooo cotpstticemscceeee///eec
article/pi1/S08B6t 0000 0000000033000000000003
Zuobing Xu and Ram Akella. A bayesian logistic regression model for active relevance feedback. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Devel-
opment in Information Retrieval, SIGIR '08, pp. 227-234, New York, NY, USA, 2008. Associ- ation for Computing Machinery. ISBN 9781605581644, doi: 10.1145/1390334.115 1390377 URL
/tttps://do... www.:o.org/11... 1ww..e11111111 1390377
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML '01, pp. 609 016,1 San Francisco, CA, USA, 2001, Morgan Kaufmann Publishers Inc. ISBN 1558607781.
Xinlei Zhou, Han Liu, Farhad Pourpanah, Ticyong Zeng, and Xizhao Wang. A survey epis- temic (model) uncertainty in supervised learning: Recent advances and applications. Neu- rocomputing, 489:449-466 2022. ISSN 2925-2312. doi: https:/dbi..ogg//0111/////eee
2021.10.119. URL https: http:///wweeceedeeeeeeeeeeeeeeee www.a//wwwceeeeetceeeeeooeeeeeee www.://cweeeceteetccccc//aaaaaaa S0925223 9068
11

---

Published as a conference paper at ICLR 2024
A REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our experiments, we provide details of hyperparameters used for training posterior network model with details of model (backbone used and flow parameters) in Sec. All models were trained NVIDIA 16GB V V000 GPU. We provide the pseudo code of binning Sec All binning and decision boundary related operations were performed 4-core machine using Intel Xeon processor 2.3 GHz (Broadwell E5 E5-2686 v4) running Linux. Moreover, we will publicly open-source our code later after we cleanup our code package and add proper documentation for it.
6.1
and algorithms implemented in Sec. 5 and Appendix [ with details of bin-configuration
6.2
B
ETHICS STATEMENT
Our work is in accordance with the recommended ethical guidelines. Our experiments are performed on three datasets, two of which are well-known click prediction Datasets (Crites Avazu) datasets in public domain. The third one is a proprietary dataset related to customer actions but collected with explicit consent of the customers while adhering to strict customer data confidentiality and security guidelines. The data we use is anonmyized by one-way hashing. Our proposed methods are targeted towards classification performance for any generic classifier and carry the risks common all AI techniques.
C ADDITIONAL EXPERIMENTAL RESULTS
C.1 BENEFITS OF 2D-DECISION BOUNDARY ESTIMATION
To anecdotally validate the benefits of 2D decision boundary estimation, run the algorithms EW-
DPMT and ST on Criteo dataset and examine bins where the algorithms differ on the decision boundary for 90% precision. As mentioned earlier, the bin (bin A) with [(s(x), u(x)) (0.984, 0)] and positivity rate 0.91 is included in the positive region by EW-DPMT but excluded by ST while the reverse is true for the bin (bin B) with [[s(x), u(x)) (0.996, 0.667) and positivity rate 0.87.
Note that ((s(x), u(x)) are the score and uncertainty percentiles and not the actual values. We further characterise these bins using informative categorical features. Fig. depicts pie-charts the feature distribution of one of these features "C19" for both these bins as well as the corresponding score bins across all uncertainty levels and the entire positive region as identified by EW-DPMT. From the plots, we observe that the distribution of C19 for the positive region of EW-DPMT (Fig. (a)) is similar to that of the bin A (Fig. 7 (b)) which labeled positive by EW-DPMT and negative by ST and different from that of bin B (Fig. (c)) that is labeled negative by EW- EW-DPMT but positive by ST in terms of feature value VI being more prevalent in the latter. We also observe that bins A and B diverge from the corresponding entire score bins across uncertainty-levels, i.e., Fig. (c) and Fig. (e) respectively. This variation of both feature distribution and positivity with uncertainty for the same score range highlights the need for flexible 2D decision boundary estimation beyond vanilla thresholding based on score alone.
C.2 RECALL IMPROVEMENT AT DIFFERENT PRECISION LEVELS
To identify the precision regime where the 2D-dccision boundary algorithms are beneficial, we mea- sure the recall from the various algorithms for different precision bounds. 2 the results on CRITEO dataset (r = 3) highlighting that the relative improvement by leveraging uncertainty estimation in decision boundary estimation increases with precision bound. This empirically ties to the observation that the separation between different uncertainty levels is more prominent for higher score range, as this separation is used by 2D-decision boundary algorithms for improving recall.
C.3 STATISTICAL SIGNIFICANCE OF VARIOUS ALGORITHMS VS ST
captures the significance levels in the form of p-values on paired t-test (one-sided) com- paring the different algorithms against the single-threshoid (ST). It is evident that algorithms that leverage both score and uncertainty such as EW-DPMT, MIST, VW-DPMT and GMT signifi- cantly outperform ST. improving recall fixed precision for all datasets.
Table 3
12

---

Published as a conference paper at ICLR 2024
(a) Pos 990% Precision
(b) A: Pos(EW-DPNT] NegiST)
[c] FullScore Bin A
(d) 8: Neg[EW-DPMT]] Pas(ST]
(e) FullScore Bin B
14%
2%
3%
16%
24%
19%
2%
3%
Other
OtheY
Other
V2
V2
Other
V2
33%
50%
31%
V3
V3
V3
22%
V3
39%
33%
V1
40%
47%
50%
Figure 7: Distribution of subsets of data from Cri teo with 7 = 3 across key categorical feature (C19): (a) All positive samples as per the 90% precision decision boundary by EW-DPMT, (b) Bin A included by EW-DPMT in the positive region but excluded by ST, (c) Score bin corresponding to the bin A across all uncertainty levels, (d) Bin B excluded by EW-DPMT in the positive region but included by ST, and (e) Score bin corresponding to the bin B across all uncertainty levels. Here, VI refers to C19 with value 1533924, V2 with 1533929, V3 with 1533925.
Algorithm
Recall 60% % Prrcissin
Recall
Recall @ 80 % Precision
Recall
70 % Precision
90 % Precision
Score only
ST
46.6%
27.7%o21.1%
12.0%o+0.8%
2.2%,4..2 2%
Score and Uncertainty based
GMT
46.8%
40.9%
(+0.4%)
18.0%++1.0g
(+1.0%)
12.5% (+3.5%)
2.6%040.3%
(+18.2%
MIST
46.7 46.7% 40.
(+0.1% 1%)
27.8%+1.org
(+0.4%)
12. 12.4% 40.6%
(+2.7%)
2.7% 20.%%
(+22.7%
EW-DPMT
+v.8% (+0.6%)
28. 28.2% (+1.6%)
12.6%+p.8% (+4.8%)
2. 2.7% 20.%% (+22.7%)
Recall@ different precision levels for Criteo dataset (r 3) for various decision boundary algo- rithms along with relative gains for each uncertainty level (in brackets) relative to the ST algorithm.
Table
Criteo Precision
Avazu
E-Com
903
70% Precision
70% Precision
7=3, Pos:Neg 1:3
7=5, Pos:Neg =:5
7=5, Pos: 1:24
Algorithm
Equi-Span
Equi-weight
Equi-Span Equi- Score and Uncertainty based
Equi-Span
Equi-weight
ST vs.
0.99
0.98
0.99
0.99
ST vs. GMT
0.08
0.03
0.03
0.42
0.07
ST vs. MIST
0.05
0.03
0.02
0.02
0.1
0.03
ST vs. EW-DPMT
0.03
0.02
0.01
ST vs. VW-DPMT
0.03
0.03
0.02
0.02
0.02
0.01
Table Significance level (p-values) Paired (-test Recall PrenisionBound different decision bound- ary algos on Criteo, Avazu and E- Com test datasets with #bins chosen same as per Table
13

---

Published as a conference paper at ICLR 2024
C.4 RUNTIME OF VARIOUS ALGORITHMS
Table shows the run-times (in seconds) for the best performing algorithms: MIST (Multi Isotonic regression Single score Threshold) and EW-DPMT (Equi-Weight Dynamic Programming based Multi threshold on Criteo (T 3) dataset for different bin sizes with 64-core machine using Intel Xeon processor 2.3 GHz (Broadwell E5-2686 v4) running Linux. The runtimes are averaged for each setting. The run-times do not include the binning time since this
over 5 experiment-secce the same for all the algorithms for given binning configuration. It only includes the time taken to fit the decision boundary algorithm and obtain Recall @ BrecisionBound.
Table 4: Wallclock runtime (in seconds) of various algorithms on Criteo Dataset (T = 3).
Score-bins
100
500
1000
Uncertainty-bing
EW-DPMT
MIST
EW-DPMT
MIST
EW-DPMT
MIST
92
98
99
530
80
7
42
154
830
146
3434
99
106
233
1976
162
I1335
99
From the theoretical analysis, we expect the runtime of decision boundary estimation for MIST to be OKK log(KL)), However, in practice there is a strong dependence only on K i... the number of uncertainty bins since we invoke an optimized implementation of isotonic regression K times. Furthermore, we perform the isotonic regression over the samples directly instead of the aggregates over the score bins which reduces the dependence on L. The final sorting that contributes to the L (og(KL) term is also optimized and does not dominate the run-time. For EW- DPMT, we expect a runtime complexity of O(K² i... quadratic the number of bins. From decision-boundan algorithm fitting perspective, the observed run-times show faster than linear yet sub-quadratic growth due to fixed costs and python optimizations. Overall, MIST performs at par with EW-DPMT the decision quality but takes considerably less time.
C.5 RESULTS USING MC-DROPOUT
To understand the impact of choice of uncertainty estimation method, we report experiments on MC-Dropout (Gal Ghahramani 2016) algorithm in Table [ MC-Drooouut estimates epistemic uncertainty of model by evaluating the variance in output from multiple forward passes of the model for every input sample. Resuts in Table [5 are from models trained for each dataset without any normalizing flow. While we observe substantial relative improvement when the recall is already low as in the case Avazu, the magnitude improvement is much smaller than the case of Posterior Network possibly because the MC-Dropout uncertainty estimation does not account for aleatoric uncertainty.
Cri teo, 90% Precision
Avazu, 70% Precision
E-Com, 70% Precision
y=3, Pos:Neg= 1:3
7=5, Pos:Neg 1:5
r=5, Pos:Neg 1:24 Equi-weight
Algorithm
Equi-weight
Equi-weight
Score only
ST
4.2% +0.1%
1.28%+oo.%
22.8%
Score and Uncertainty based
MIST EW-DPMT
4.3% (+2.4%)
|
1.8%+ (+40%)
23.1% 43.4%..%%%% (+1.3%) 23.7% 7% (+3.9%
4.3% 15 (+2.4%)
1.9% 2% (+48%)
Table 5: Performance different decision boundary algorithms as measured Recall Precision on Criteo, Avazu and E-Com test datasets with MC- MC--ropout as uncertainty estimation method.
C.6 IMPACT OF USING UNCERTAINTY ESTIMATION ON CALIBRATION ERROR
For applications such advertising, it is desirable have well-calibrated probabilities and not just a decision boundary. To investigate the potential benefits of incorporating uncertainty in improving probability calibration, we compared the calibrated scores from MIST algorithm with those from vanilla isotonic regression (IST) baseline. MIST fits a separate isotonic regression for each uncer- tainty level while IST fits single vanilla isotonic regression on the model score. We evaluate the
14

---

Published as a conference paper at ICLR 2024
Expected Calibration Error in the jth score-bin, ECE@j
n(i.j) ECE = K [E[1,K]
(score|x) label [x|]
xE)in(L.)
where for each bin (). calibration error (CE) is evaluated on samples from the bin. CE is the absolute value of the average difference between the score and label for each sample Bin(i,j), where j E [1, L.J i E [1, K] n(i,j) is the number of samples in the Bi)( For both MIST and IST. we use the respective isotonic score for CE calculation. In Fig. (a) and (c), we plot ECE@) for all score bins for MIST and IST decision boundary algorithms on Criteo and Avazu datasets respectively, averaged over different experiment seeds. The difference between ECE@j MIST vs IST is pronounced at high-score levels, aligning with our primary observation that leveraging uncertainty estimates in decision boundary estimation helps improve recall high precision levels.
We also define the cumulative- ECE as the averaged calibration enror for all bins with model- score percentile greater than j. The sumulative-FCC FCER results in smoothened plot and the dif- ference between the Cumulative-FCC for IST with that of MIST increases with model-score.
MSST
MST
Cumulative-CCC
N.ST
MST
Av www.e
Model Score Percentle
Model Score Percentile
Model Score Percentle
Model Score Percentile
(a)
(b)
(c)
(d)
Figure 8: Impact of leveraging uncertainty in calibration by comparing MIST vs 1ST (a) ECF3i Cri Criteo
(T 3) (b) Jumulative-FCC.... for Criteo (r = 3) (c) FCF for Avazu (T 5) (d) Cumulative-
ECFĀj for Avazu (T = 5).
C.7 IMPACT OF UNCERTAINTY BASED MONOTONIC CONSTRAINTS
In the Weight DP (EW-DPMT)) formulation, there a separate threshold b, for each uncertainty level In other words, assume monotonicity of the true conditional probability of the positive class with respect to the model score for a fixed uncertainty but not with respect to uncertainty for fixed model score. This is because monotonicity with respect uncertainty does not hold true across the entire score range. Fig. Bla) shows the behavior (flipped trends for different score ranges) for the of Beta priors with uncertainty estimated using Posterior Networks.
To empirically validate this observation, we consider EW-DPMT-MONO, a variant of the EW- DPMT algorithm where the decision boundary is constrained such that the true conditional prob- ability is monotonically decreasing in uncertainty (i.c., 6, 2 by for i > j so that the boundary function looks like a staircase). This variant has higher computational complexity O(3²I.3) than EW-DPMT where K and L are the number of uncertainty and score bins. Ta compar- ison of the performance of the two algorithms for the same bin configuration. We observe that for high precision bound (as in Crit Cro), the monotoncity assumption does hold, but that is not true for lower precision bounds with the unconstrained version resulting in better performance. This aligns with the expected behavior in Fig. a).
C.8 IMPACT OF BINNING ALONG SCORE BEFORE UNCERTAINTY
In Sec. 5] we introduced the equi-weight nested binning strategy where samples in Dhold are first partitioned into K quantiles along the uncertainty dimension with each of these K quantiles fur- ther split into L quantiles along the score dimension. It is also possible to adopt an alternative binning strategy based on partitioning first the score followed by uncertainty. Table 7 captures the Recal @ Precision bound using the two equi-weight binning strategies for various 2-D decision boundary algorithms indicating that both the strategies yield similar results.
15

---

Published as a conference paper at ICLR 2024
Critec, T=3, 90% Precision
Avazu, 7=5, 70% Precision
Score only
2.2 2227020.22
19%640.6%
Score and Uncertainty based 2. 2.0.%%0.3%
EW-DPMT EW-DPMT MONO
2.6%o20.3% 1.9%
2.6%.4..6%
Table 6:
Performance with different unconstrained and monotonic variants of EW-DPMT with uncertainty bins = 100 and score bins = Note that here we used a smaller number uncertainty bins instead of 500 (in the paper) to reduce computational effort.
Critao, r=3, 90% Precision
Avazu, 7=5, 70% Precision
Algorithm
Score-Une (500.3) Unc-Score (3,500)
Score-Unc (500,3
Unc-Score (3,500)
Score only
ST
2.270+0.25
2.2%
1.900
1.9%
Score and Uncertainty based
MIST
2.6%o...22
2.6%
2.9%
2.6%
GMT
2.6% 4..4%
2.7%
2.9%
2.7%
EW-DPMT
2.7%
2.7 3.7% 2.7.%%0.3%
2.9%=
2.7%
Table 7: Performance with different equi-weight binning strategies. Score-Une involves splitting quantiles followed by that uncertainty while the opposite Unc-Score. Same number of score and uncertainty bins were used for both experiments.
D POSTERIOR NETWORKS
Posterior Network (PostNet) (Charpentier et al. 2020 builds on the idea of training a model to predict the parameters of the posterior distribution for each input sample. For classification, the posterior distribution (assuming conjugacy with exponential family distribution) would be Dirichlet distribution, and PostNet estimates the parameters of this distribution using Normalising Flows.
They model this by dividing the network into two components:
Encoder: For every input x, encoder (fa) computes = [x(), a low-dimensional latent representation of the input sample in high-dimensional space, capturing relevant features for classification. The encoder also yields sufficient statistics of the likelihood distribution in the form of transforr of 2 2(x) followed by application of log-softmax. Instead of learning a single-point classical softmax output, it learns a posterior distribution over them, characterized by Dirichlet distribution.
Normalizing flow (NF): This models normalized probability density p(z/c, Φ) per class on the latent space intuitively acting as class conditionals in the latent space. The ground truth label counts along with normalized densities are used to compute the final pseudo counts. Thus, the component yields the likelihood evidence that is then combined with the prior obtain the posterior for each sample.
The model is trained using uncertainty aware formulation of cross-entropy. Here 0 and are the parameters of the encoder and the NF respectively. Since both the encoder network fa and the normalizing flow parameterized by & are fully differentiable, we can learn their parameters jointly in an end-to-end fashion. q(x) is the estimated posterior distribution over p(y(x). The model's final classification prediction the expected sufficient statistic and the uncertainty the differential entropy of the posterior distribution. The model is optimised using stochastic gradient descent using loss function that combines cross entropy with respect to true labels and the entropy of (xx).
E ESTIMATION BIAS ANALYSIS: PROOFS OF THEOREMS
E. DATA GENERATION PROCESS
The true positivity rate Strue(x) is generated from global Beta prior with parameters B7 and 8T i.e.
strue BB
16

---

Published as a conference paper at ICLR 2024
The train and test samples at input region (modeled in discrete fashion) generated from the true positivity rate following a Bernoulli distribution with the negative train samples being un- dersampled by factor Let Nirain (x) and N denote the number of train and test samples at x. Let Nerain (x) and Ngeet( (x), c E {0, } denote the class-wise counts. The positive counts for the train and test count given by
Niest (x) Binomiall (x), (x)wa(x))
(x)rue(())
Nitrsn (x) ~ (Atran (x), (r 1)Sttrue(ss
The train and test positivity rates are given by Strain (x) Nxraas(
[x) and (xea((x) N (x)
N (x) The
model score Smodel (x) is obtained by fitting model on the train with additional dependence
on the test and true positivity rates. Fig. 2 shows the dependencies among the different variables.
Lemma E.1. The relationship between train positivity Strain and model score for positive class Smodel (x) from Posterior Network is given by
Strain (x) = SSmddel (x) - (w - S
where
8P 3/" +P6
+ Po)))
(x)
Proof. Using the notation Sec. 3 the pseudo-count 3x(x), C {0, correspond to the observed positive and negative counts x. Hence, the train positivity given by
(1)x
gtrain B1(x) Bo(x)
This gives us 30(x) = (x) gtrain Strasn(x)
Using the definitions of and 7(x). the model score Smmodel (x) from Posterior Network (Eqn. can now be expressed in terms of w, (ttaim(x) and y(x) as follows:
Smodel (x) 8f + (x)
w7(x) + Strain (x)
13 + +x]]
1 1+>(x)
Hence, Strain (x) Smadel (x) (w Smodel (x))
Theorem E.2. For the case where data is generated as per Fig. and negative class is undersam-
pled at the rate 1. the following results hold: (a) The expected true positivity rate conditioned on the train positivity is given by the expectation of the distribution.
C Beta(n((A(x)) + Stroin (x)), ())xx) + -Strain (x))).
Q(r) (1 (T- 1)rja
ST
n (x) + (o(x) denotes evidence, C is a normalizing constant, 5 +8T positive global prior, and X(x) Bo(x) is the ratio of global priors to evidence.
B +og the
(b) When there is differential sampling, i.e., the expectation has a closed form and is given by
Strain (x) (x)+55 +X(x)
Elstrue (astrue()))saaa
1 1 x(x)
17

---

Published as a conference paper at ICLR 2024
Proof. Let Nitaain (x)and [x) denote the number of train samples and positive samples asso- ciated with any input region x. Then the train positivity Strain Nota (x)
Niram
Since [itran(xx corresponds to the probability mass and pseudo counts at x, we consider re- gions with fixed size [x)aai(xx) n. The expected true positivity rate for all x with size Ntrrai (x) =
n. conditioned on (xrain(x) = is given by [
= k/n]
ElStrac [x)
k].
For brevity, we omit the explicit mention of the dependence on x for variables Smodel (x), Strain (x). Stest (x)) and Strue (x).
The conditional probability p(Struel |N = k) is given by the Bayes rule. Specifically, we have p(Strue = =r| k) p(Strue = r)p(Afrain = kkStrue = =))
p(N (Nirriin k)
Here Strue follows a global Beta prior and Nirain a Binomial distribution with downsampling of negative examples at the rate }. For Strue r, the success probability of the Binomial distribution (probability of obtaining a sample with = 1) is given by
Tr r+ (1+(T-1)))* Hence,
p(Strue= =r)p(Nrram k|gtrue= =))
Beta( .
(7)
(T 1)r -)))
1 >
I 1)r
Cork
(1 + (T 1)r)" Beta + k. k. n2 +n-
where Co is a normalizing constant independent of and T. While the integral J, p(Struc r)p(N (p(Nroiin = k|.ttrue r)dr over [0, 1] does not have closed form, we do observe that the desired conditioned distribution will have a similar form with different normalizing constant C since the denominator is independent of
plStrue p( k|Strue r)
p(Strue = r|/Nfrann =k) k))
J p(Strue = (aarrue=)pppp (rrpp(((rraa)) = =k|Strue = =r)dr
C (1 (T- 1)r)"" Beta( + ke 3 n k).
The expected true positivity rate conditioned on Nirain = k is the mean of this new distribution, which does not have a closed form but can be numerically computed and will be similar to the simulation results in Fig. 3).
Using the definitions of & of +88 and A(x) = (x)) we can rewrite ST = n (x)(() and 3o = n21 (xx). Further, observing that Strain(x) = k/ n, we can express this distribution as ((r) = (1 + (T 1)r)a
18] +.00"
C Beta(n({A(x)) + Straan (x)ratnx)))) xx)), -))xx((((x)) + -Strain (x))),
which yields the desired result.
Part b. For the case where 7 = 1, the term (1=(r-1)r) 1)r) = 1 and the distribution Q(r) reduces to just the Beta distribution (eta(n(E (xx) + Strain (x)), na(1 - <)((x) + Strain (x))). Note
the normalizing constant C = 1 since the Beta distribution itself integrates to 1. The expected true positivity is the just the mean of this Beta distribution, i.e..
n({((x) Strain (train(x))
Elstrue (xstru(x))((taaiin (x))strain(x))
m(EA(x) + Strain ()) + n((1 - {)((x) +1 1 Strain (x))
Strain (x) + EX(x)
1 + X(x)
18

---

Published as a conference paper at ICLR 2024
Theorem E.3. For the case where data is generated as per Sec. E.1 the expected test and true positivity rate conditioned either on the train positivity rate or model score for positive class are equal, i.e.
Elstest (x)) (x)) Stroin (x)) Elstrue (x)) (x)) Strrstt (x))]
FilStest (x)) Smmdeel (x) = Fs gttueeegee (x) Smodel (x))
Proof. From the data generation process in Sec. E. we observe that the test label samples generated by Bernoulli distribution centered around (x)
Yxest(x) at the input region ie., Ytes(()) ~ Bernoulli (trollissssee())) (x)) and Stest is the mean of ytest over the test samples.
Hence, the test labels ylest (x) and test positivity rate Stest (x) are independent of the model score Smodel (x) and 5tras"(x) (x) given the 5true(x), For brevity, we omit the explicit mention of the dependence for variables yteat (x), Smoddel (x), Strain (tea((x). (xx, and (true( (x).
As ylest is conditionally independent Strain given Strue, we observe that
E|y gtrain] = |gtrree [E[ytest sttru]]]
However, since Yest Bernoulli(Strve Strrlllliitttttttt (x)). have Eyy Strue]] Strue Therefore,
| strain] = Strainn gtrue]] Elstrue e[struepgtroiny gtrain]
Since Steat is itself the expectation over Ytest, by the law of iterated expectations, we have,
|gtrain], which is the desired result. The same result holds ||strue|gtrain]
E| = E|ytest| [gtraim = ElStrue
when conditioning the model score Smodel since ylest and Srest are also conditionally independent of gmodel given Strue
Theorem E.4. For the case where data is generated as per Fig. and negative class is undersam- pled at the rate 1: (a) The expected test and true positivity conditioned the train positivity are equal and corre- spond to the expectation of the distribution,
C
Q(r) = (1 (
Beta(n((X(x)) + Strain (x)), n2(1 - {))(x + -Strain (x)))-
When there is no differential sampling, i.e., T = 1, the expectation has a closed and is given by
Straen (x) + [A(x)
ElStrue (x)) (x))
(x)) ElStest (x)) (x))ssrai
X())
n (x) + Bo(x) denotes evidence,
C. is a normalizing constant, E
is the +fg
o7
o7 +8T is the ratio of global priors to evidence. positive global prior, and X(x) (Dxx))
(b) For Posterior Networks, the test and true positivity rate conditioned on the model score Smodee (x) can be obtained using (xrain(x) Smodel (w ((model(x))) For 1, the estimation bias, i.e., difference between model score and test positivity is given by (Smaded (x) 1)+==(v)x()))
1+27(x)
of and Mx)
is the ratio of global and model priors.
3 +05
7(3T
8 +05
19

---

Published as a conference paper at ICLR 2024
Proof. Part
From Theorem we directly obtain the result on the expectation true positivity rate in terms of the train positivity both for the general case where o 1 and for the special case of 1. Further, from Theorem F.3 we observe that the expected true positivity also the same as the expected test positivity conditioned on the train positivity, which yields the desired result.
Part b:
From Lemma we obtain the relationship between the train positivity and the model score, i.e.,
Strain (x) S Smmoded (x) (w Smodell (x)) which can be used to expression the expected train and test positivity directly in terms of the model score.
For the case in particular, since (x)ain(x)) is deterministic function of gimodel for fixed (x), we observe that
E[Stest (x)) Strrtin (xt) Strain (x) {A(x)
+xx)
Expressing this in terms of gmodel (x) and 7(x) X(x)/v/ gives us
FllStest (x)] [x)] Smodel (x) + (Stmadel (x) + Ev w))
+ v7(x)
Thus, the estimation bias given by
(x)) (Smodel (x) - - (x))(x))
Smodel (x) ElStest (x) (x))sSmadell
1 1x))(x)
Theorem E.5. [Restatement of Theorem 3.1 For data generated as per Fig. but no differential
sampling (i.e, T = 1), the following results hold:
(a) The expected test and true positivity rate conditioned on the train positivity equal and given by
= ElStest / ( (x)rai(())] Strrin (x) + EX(x)
Elgtrue E)strue(x)))ttriiii (xr)straii
1 1 x(x)
ST+ (1(5))
where & = + is the positive global prior, and X(x)
is the ratio of global priors
evidence.
(b) For Posterior Networks, test and true positivity rate conditioned on model score Smodel (x) can be obtained using Strain (x) Smodel (x) (w -w- Smodeel (x)) Hence, the estimation bias,
i.e. difference between model score and test positivity is given by (x)())))
where 1+v7(x)
a and v
A(x) 2 +87 7(x)
is the ratio of global and model priors.
8 +86
8f +
Proof. Current claims are a special case of Theorem E.4 when 7
E.2 RELATIONSHIP OF (xx) AND u(x)
From Theorem 3.1 of Sec. 3 we find that the model score estimation bias, (i.e., difference between model score and positivity) for the case of no differential sampling (r 1) is given by
(Smodel (x) 1) + t (x)
1 (x
of of +
Here, the bias depends on the model score, multiple constants E BT +
X(x) = + and a variable quantity 7(x) = s² ta 7(x +88
3,x)) which is the ratio of model's prior evidence to the combined likelihood evidence for sample x.
20

---

Published as a conference paper at ICLR 2024
As mentioned earlier in Sec. 7(x) is inversely correlated to the sum of the parameters
(x1(x), Oig (x) of the epistemic Beta distribution ((x) of the Posterior Network. Specifically,
(x) E>, (1 + 7(x) Increasing 7(2)) corresponds decreasing ax(),, which in
turn results in higher entropy H (g(=)) for the epistemic distribution, i.e., higher uncertainty u(x). Fig. 9 depicts the monotonic relationship between uncertainty u(x) (g((z) E and 7(x) for various fixed values of model score and varying amount of evidence computed using a numerical simulation. Here, the global prior parameters are chosen as (3f ( = (5, 10) and the total evi- dence (30(x) + 31 (x)) varies in the range (1,40). Note that the entropy computation is performed using an approximation series summation and for extreme values of the model score, the compu- lation of entropy and thus, uncertainty estimation does become unstable. The primary takeaway is that the score estimation bias depends on relative strengths of priors and evidence, i.e., 7(x), which as shown is positively correlated with uncertainty. This observation holds even for the general case where there differential sampling T > 1.
Uncertainty u6x) HHobe))
-1.2
-1.4
Score
score 0.8
-1.8
score
yix)
Figure 9: Relation between uncertainty u=x)(= H({(x))) and y(x) for a fixed score. Here, global prior parameters(B3 (8.)- and total evidence (x) B1 (x)) varies in the range (1, 10).
F COMPUTATIONAL COMPLEXITY OF DECISION BOUNDARY ALGORIHTMM
Lemma F.1. Given a K x L grid with positive sample counts (p(i,j) KXL and total sample counts ()K and any boundary b [(i)) that satisfies precision(b) Z a and recall(b) т) let (i) denote the minimum score threshold j such that p(a.f") 2 a for all j' 2 j. i.e. contiguous high precision region. Then, then the new boundary b' defined as (i) = min (b(i), (ch)())), Vilk also satisfies precision(b) and recall(b) 2 17.
m(t.'")
Proof. Let B denote the positive region for the new boundary b' and Behp the contiguous high precision bins for each uncertainty level, i.e., Behp = {(i,))) behp Vilk bi6.)
By definition, we have, 3*+ = jii > b()), V[J bib) B U Behp, Given a set of bins B. let P(B) and (B) denote the net positive and total samples within this set of bins. Since precision(h (b) 2 a, we have P(B+) 2 oBB+).. Since pliji 2 a, v(i,j) E Behp, we also note that P(B) 2 (B) for any set C Bohp.
m(t.]]
Now, the precision for the new boundary is given by
EONEr p(i,j)
EONEB p(i,j) + Easse p(i,5) E(SSEE m(i,j) + Easee n(i,g)
precision(b))
EoseE n((,g)
P(B+) + P(Behp) \ B+)
N(Bt) + N(Boh B+)
< N(B+) + N(Bche \ B+))
{since (Behp) \ B+) C Behp]
+ & B+)
(H(()x)) = log B(au, -1)- 2))(auua))aatta -E 1000-110x(ee 1))((a)) where wb-) is the digamma function and B(.,)) is the Beta function.
21

---

Published as a conference paper at ICLR 2024
Let Po denote the total number of positive samples. Then the recall for the new boundary is given by
recall(b') E(iee p(i.))
P(B P(Bep B
P(B+)
Po
Pa
Po
1/.
Hence, b' also satisfies the precision and recall bounds.
Theorem F22. [Restatement of Theorem 5.1 The problem of computing the optimal 2D- binned decision boundary (2D-BDB) is NP-hard.
Proof. The result is obtained by demonstrating that any instance of the well-known subset-sum problem defined below can be mapped to a specific instance reformulated 2D-BDB problem such that there exists a solution for the subset-sum problem instance if and only if there exists solution for the equivalent decision boundary problem.
Specifically, we consider the following problems:
Subset-sum problem: Given finite set A = fai,...,a0 of non-negative integers and a target sum T. there subset A' of A such that Ee,eh EA' 0p
Reformulated 2D-BDB problem: Given a K grid with p(i,j) and m(i, denoting the positive and total number samples for bin (i, is there a decision boundary [b(i]] K such that precision(b) and recall(b) 2 7).
Let B+ denote the positive region of the boundary, i.e., B+ {(t,j)] <is Si b(i) and Po denote the total number of positive samples. Then, we require
Eanent p(i.)
precision(b)-
EB.see+ m(13)
20
recall(b) Ex.eent p(1.) Po
1
Note that maximizing recall for precision bound equivalent reformulation in terms of the existence of solution that satisfies the specified precision bound and an arbitrary recall bound.
Given any instance of subset-sum problem with items. we construct the equivalent decision bound- ary problem by mapping it to (t + 1) x 1 grid (i.e., K = + 1, L = 1 with bins set up as follows.
* n(i, 1) = T; p(i, 1) = 2oT,
nii 1,1) a. p(i + 2ea;,
where the parameters a, G, can be chosen to be any set of values that satisfy
0s 0< 2(T ==
2(a+e)T Pb
We prove that the problems are equivalent in the sense that the solution for one can be constructed from that of the other.
Part 1: Solution to subset sum = Solution to decision boundary
Suppose there subset A' such that Ea,eA a, T. Then, consider the boundary b defined as b(1) = 1 and b(1) 1[a & A'), i.e., the positive B = 1(1,)) 1, 1,1) A'). This leads to the following precision and recall estimates.
Eosent p(i,j)
20T + 2c Ea 2(o e)T
precision(b)-
2 0
EGgeen n(i,j)
T T Ea.es 0s
22

---

Published as a conference paper at ICLR 2024
recall(b) = En p(i,j)
20' + 2e
Ba Oj
2( c)T Po = 77.
Po
Po
Since this choice of b is valid boundary satisfying the precision and recall requirements, we have a solution for the decision boundary problem.
Part 2: Solution to decision boundary = Solution to subset sum
Let us assume we have a solution for the decision boundary, i.e., we have a boundary b with precision(b) 2 and (b) 2 respectively. Since the positivity rate of the bin (1,1) is 2rT
T = 2a > from Lemma 1 we observe that the boundary b is such that (1, 1) is in the positive region of the boundary B+
Consider the subset A' (a. E B²}. We will now prove that Ea,ev which makes it valid solution for the subset-sum problem.
Suppose that EMSAs = = T, i.., T 2 since T is an integer. For this case, we have
precision(b) EONDEB p(i,j)
20T + 2e EnSe 2xT + 2CT"
E(t)EB n(i,j)
T EoSEA 44
T T
Since e < 2(T+1)' we have
20T + 2CT"
20T +
20T 2(++1)
(T + T
0 1+ T T T"
precision(b) =
T+I
T+T'
T+7 T
T T
T T
TT T
T(T' -T -TT
σ (1
T+1
S.. {since T' T++1
T T"
(T +)(T++TT))
In other words, precision()) (b) a, which is contradiction since b is valid solution to the decision boundary problem.
Next consider the case where E0,EA = < T' Then, we have,
recall(b)= ELNeEB- p(i,j) 20T + E., as
20T + 2
2nT + 26T
17.
Po
Po
Po
Po
This again leads contradiction since b is solution to the decision boundary problem requiring (ec 2 1). Hence, the only possibility is that E,,es' T, i.e., we have solution for the subset-sum problem. Since the subset-sum problem is NP-hard (Caprara et al. 20000,, from the reduction, it follows that the 2D-BDB problem is also NP-hard.
G DECISION BOUNDARY ALGORITTMS
Here, we provide additional details on the following proposed algorithms from See. 1hht are used in our evaluation. These are applicable for both variable or equi-weight binning scenarios.
Equi Weight DP-based Multi-Threshold algorithm (EW-DPMT) : We detail the EW-DPMT (Algorithm I. presented in Sec. here. Let R(i, m)) [i] [m]]k< denote the maximum true pos- itives for any decision boundary over the sub-grid with uncertainty levels to and entire score range, such that the boundary has exactly m bins in its positive region. Further, let b(i, m,:) denote the optimal boundary that achieves this maximum with b(i, m, i') denoting the boundary position for the (((5 i) uncertainty level. For the base case when i 1, there is feasible solution only for 0 < m < L which is the one corresponding to 6(1, m, 1) L m, since the score threshold index for picking m bins in the positive region will be L m. Now, for the case i > 1, we can decompose the estimation of maximum recall as follows. Let j be the number of bins chosen as part of positive region from the tth uncertainty level, then the budget available for the lower 1) uncertainty
23

---

Published as a conference paper at ICLR 2024
levels is exactly m j. Hence, we have, R(i.)) max (i. + R(i 1,m -]], where 0S3SI.
(i.)) EJ -+1 1- J'), i.e., the sum of the positive points in the j highest score bins. The optimal boundary b(i, m.:) is obtained by setting b(i, m, i) = L - j and the remaining thresholds to that of b(2 1, m ,) where j is the optimal choice of j in the above recursion.
Performing this computation progressively for all uncertainty levels and positive region bin bud- gets yields maximum recall over the entire grid for each choice of bin budget. This is equivalent to obtaining the entire PR curve and permits us to pick the optimal solution for a given precision bound. Since the bin-budget can go up LL and the number of uncertainty levels is K, the number of times the maximum recall optimization is invoked is L The optimization itself explores L choices, each being a O(1) computation since the cumulative sums of positive bins can be computed progressively. Hence, the overall algorithm has O(K² L²) time complexity and K storage com- plexity. Algorithm TTQUII BEEQUI-WEIIGE WEIGHT DP-BASED MULTI-THRESHOLIE
(EW-DPMT) shows steps for computing the optimal 2D-decision boundary. Note that if solution is required for a specific precision bound o, then complexity can be reduced by including all contiguous high score bins with positivity rate 2 since those will definitely be part of the solution (Lemma E.I)
algorithm (V (VW-DPMT) As discussed in Sec. [ the general case of the 2D-BDB problem with variable-sized bins is NP-hard, but it permits pseudo- polynomial solution using a dynamic programming approach. Similar to the equi-weight DP algo- rithm EW-DPMT, we track the maximum recall solutions of sub-grids up to 1th uncertainty level with a budget over the number of positive samples.
Variable Weight DP-based
Let R (i, m) denote the maximum true positives for any decision boundary over the sub-gn with uncertainty levels 1 to and the entire score range such that the boundary has exactly m samples in its positive region. We can then use the decomposition,
Rear (i, = max [T(] + noor 1,m -(])],
OSi5L"
where T (i.j) = - p'i,5") and v(i,j) = EE --++ n'i.j").
Algorithm provides details of the implementation assuming a dense representation for the matrix Rear (Eqn. G) that tracks all the maximum true positive (i.e., unnormalized recall) solutions for sub- grids up to different uncertainty levels and with a budget on the number of samples assigned to the positive region. For experiments, we implemented the algorithm using sparse representation for Hear that only tracks the feasible solutions.
Greedy Turti-Thresholds (GMT) Algorithm 2 provides the details of this greedy approach where we independently choose the score threshold for each uncertainty level. Since all the score bin thresholds are progressively evaluated for each uncertainty level. the computational time complexity is O(KL) L) and the storage complexity is just O(K). However, this approach can even be inferior to the traditional approach of picking single global threshold on the score, which is the case cor- responding to a single uncertainty level. ST algorithm can be viewed as special case of GMT algorithm where only one uncertainty level is considered (i.e. K =).
Multi Isotonic regression Single Threshold (MIST) As mentioned earlier, the isotonic regression-
based approach involves performing isotonic regression (Barlow & Brunk 1972) on each uncertainty level to get calibrated scores that are monotonic with respect to the score bin index. Bins across the entire grid are then sorted based on the calibrated scores and a global threshold on the calibrated score that maximizes recall while satisfying the desired precision bound is picked. In our imple- mentation, we use the isotonic regression implementation is sci -iitleerrt rn, which has linear time in terms of the input size for L2 loss (Stout) 2013). Since the sorting based calibrated scores is the most time consuming part, this algorithm has a time complexity of O(KL log K L)) and a storage complexity of O(K L). For our experiments, we performed isotonic regression for each of the K uncertainty levels directly using the samples instead of the aggregates at L score bins. When the K uncertainty bins are equi-weight, this is essentially the case where L = N/K.
24

---

end for end for Initialization Published as a conference paper at ICLR 2024
Algorithm 2 Greedy Decision Boundary- Multippe Score Thresholds [GMT)
Input: Variable-sized K L grid with positive sample counts j)]i, and total sample counts [)] xxt. overall sample count N, precision bound o. Output: (unnormalized) recall πe and corresponding boundary b" for precision with greedy approach.
Method:
// Pre-computation of cumulative sums of positives
for i K do
(ii 0
v(i, 0) =0
for j to L do
T(..j) = [ - -1,
v(i,j) vii.j - -1 +
R O // Independent Greedy Score Thresholds
for i to K do j =
argmma
[T(E,))
OSiST, s.t. 63
20.) 2
6(1) =j j
R R + (i,
end for
R R, b* b(:)
return (R", b*)
25

---

Published as a conference paper at ICLR 2024
Algorithm 3 Greedy Decision Boundary Global Threshold on Score Recalibrated with Isotonic Regression [MIST]
Input:
Variable-sized K x L grid with positive sample counts [p(i,j)) and total sample counts [n(t,j]] K overall sample count N, precision bound
Output: (unnormalized) recall R and corresponding boundary b" for precision 2 a with greedy approach.
Method:
Recalibrate each row using isotonic regression
ior to K do
borOONCkKERRSSSOOOolli:........ (i.))(
end for
Get global threshold on calibrated score
I/ rank is descending order O maxrank low rank means high positivity
frank(i, (iank(i,,)))) j]] xxL = (ORT([s"*0(,,) (i.)))x
marrank max rank(
[a bif
(00) 0, (0) 0
r= 0
repeat
r= 1
((r) = t(r - 11) +D (t5) (1
((r) = v(r 11) Σ (id) (ank(i.)=r(((((.)))) [n(2,,)
unfil
[(r) < mazrank) ((r)
-r--
Obtain score thresholds for different uncertainty levels
R 0
for i
K do
if [j)rank(i, 1) 2 r*) -0 then =
else
;= argmin [
jlrank(i.j22r
end if
b(i) = j
for R= R + p(i,j)
j 1 to L do
end for
end for
R" R, b* b(:)
return (R", b')
26

---

Published as a conference paper at ICLR 2024
Algorithm 4 Optimal Decision Boundary for Variable-Weight Bins [VW-DPMT]
Variable-sized K L grid with positive sample counts [p(i, and total sample counts [n(i, kx overall sample count N, precision bound a. Output: maximum (unnormalized) recall Rt and corresponding optimal boundary b* for precision 2 a.
Input:
Method:
// Initialization
R(i, m) -oc; b(i,m, -1; [K [M], [ml6")
// Pre-computation of cumulative sums of positives
for
K do
0) 0
v(i, 0
for j = 1 L do
T(..j = - 1) p(
v(i,)) v 1) -(,
end for end for
// Base Case: First Uncertainty Level
for j
L do m vv1.j) R11 m)) = π (1,3) 6(1, m. 1) = 1 --jj
end for // Decomposition: Higher Uncertainty Levels
for i = 2 K do
for 0 to Σ == Noum(i.i) do
j = argmax
T (1. 1)= + R(i - 1, m - v(t,j))
0SJSL
R(i, m) ) + 1,m vii,j"))
b(i, m.:) b(i - 1,, v(i,
b(i, m,, L j
end for end for
Maximum Recall for Precision
m
argmax
[R(K,n) m)]
0Sm5KL s.t. RtK.m) 2a
R(K, m²); mK,m",;)
return (R", b*)
H EXTENSION OF RESULTS TO OTHER SETTINGS
We briefly discuss the possibility of extending our results to broader settings.
H.1 GENERAL PRIORS AND UNCERTAINTY MODELING.
The primary objective of the analysis in Sec. 3 to demonstrate that there is systemic depen- dence of model score estimation bias on uncertainty for common scenarios. our current work, we characterise this relationship (Theorems [nd and E.4 for the case where (i) the data is generated as per Fig. 2 with global Beta distribution prior, and (ii) the estimation of model score and uncertainty performed using Posterior Network.
Note that the first part of the result, i.e., the relationship between the expectation of test and true conditional class probabilities conditioned on the train positive class probability holds true indepen- dent of (ii). The second part of the result, which is the relationship with model score depends on the choice of uncertainty modeling approach (ii).
When the first condition(i) does not hold, i.e., it becomes intractable to obtain an equivalent closed form result. However, for a global unimodal prior (not necessarily Beta distribution), the
27

---

Published as a conference paper at ICLR 2024
expectation of test and true conditional class probabilities conditioned on the train positive class probability still shifted away from the train distribution the direction the global prior since the posterior distribution of the true positivity conditioned on the train positivity combines the effects of the evidence (train positivity) and the global prior.
H.2 MULTI-CLASS CLASSIFICATION,
In our current work, we focused binary classification. However, the analysis in Sec. 3 on the relationship between model score estimation bias and uncertainty (Theorems and [.4 readily generalize to multi-class classification with more than two classes when the data generation in Figure 2 uses a global Dirichlet prior instead of Beta prior with a fixed re-sampling policy. For such derive the expectation of true and test conditional class probabilities conditioned scenario, conditional class probabilities using Bayes law. As before, when the modeling and on the train uncertainty estimation is based on Posterior Networks, the model's conditional class probabilities. Intuitively, the true and test conditional class probability distribution diverges from the corresponding train distribution in the direction of the global prior with the magnitude of divergence determined by the strength of evidence, which correlates with models' epistemic uncertainty.
obtain the relationship with respect to
On the other hand, generalization of the decision- decision-making strategy to more than two classes is some- what non-trivial since the notion of decision boundary becomes more complex in the case of more than two classes and requires characterization of the objective function that the decision boundaries are meant to optimize. One possible formulation that suits many real-world applications the decision boundaries so to maximize micro-average recall with an overall or class-wise pre- cision bounds. Monotone operators over the conditional probability distributions that also combine uncertainty-biat -based discriminating signals is a possible research direction to explore. Previous works based on set predictions (Mortier al, 2021 Angelopoulos et al. (22TI) also attempt to address this problem scenario but without explicit of uncertainty estimates.
define
28

---

Published as a conference paper at ICLR 2024
I
NOTATIONS
Table Notations used within the paper and their definitions.
Symbol
Definition
input instance region target label for an input sample x of class labels {0, 1} index over the labels in C index iterating over integers in fib...., ... (ub)
y
C
c
[0)
Estimation Bias and Posterior Network Related
P())
Probability distribution
((x)
Distribution over class posterior at output by Posterior Network
(g(x))
differential entropy of distribution g(x) Beta distribution with parameters crj dr ax(x)
Beta (kp, 01) Parameters of Beta distribution x(x) for class C
Parameters of Model prior for class C
Parameters of True prior for class C
(x(x)
Pscudo counts for class C observed counts for class penultimate layer representation from the model parameters of normalizing flow in Posterior Net- works
Ne
zxx)
u(x)
Uncertainty for x
Smodde (x), s(x)
Model score for positive class true positivity in input region x
Straa(s (x)
Strain (x)
x empirical positivity in the train set for input region
Sleat (x)
empirical positivity in the test for input region
differential sampling rate for negaatives evidence at input region given by & (x) + (x))
n(x)
E
positive class fraction in global prior
positive class fraction in model prior
X(x)
ratio global priors to evidence ratio of model priors to evidence ratio global priors to model priors distribution of true positivity conditioned on fixed train positivity rate
7xx)
V
2(-)
Decision Boundary Related
Dtrain Dhold Diest
Data split for training the model, calibrating the decision boundary and testing
b
decision boundary defined in terms of score and uncertainty thresholds
(x))))
labeling where samples that satisfy boundary thresholds are positives
buu)
decision boundary specified by score threshold for fixed uncertainty level
s
Range of score values Range of uncertainty values Number of uncertainty bins
K
Number of score bins
= ())())
Partitioning function that maps score and uncer- tainty values to bin-index (i.j) Continued on next page
29

---

Published as a conference paper at ICLR 2024
Table 8 continued from previous page
Symbol R(i, m)
Definition
max. true positives for any boundary upto the gt uncertainty level with exactly m positive bins in EW-DPMT max. recall boundary for the sub-grid upto uncer- tainty level with exactly positive bins count of positives in the (i,j)th bin count of samples in the (i. bin count of positive samples in the j highest score bins for uncertainty level i
b(i, m.:)
p(1,j) ((
T(.5)
30


Reviews:
[{"review_id": "knLSGDaCgF", "reviewer": "Reviewer_ZEGe", "summary": "Paper considers new approach to uncertainty estimation for calibrating the model and improving the classification accuracy in the case of (imbalanced) training set and/or dataset drift. Theoretical and empirical analysis of model output score dependence of uncertainty and the score are evaluated, and based on dynamic programming and isotonic regression an approximation algorithms are formulated for general NP-hard problem of decision boundary selections using both score and uncertainty. Three benchmark datasets, from online advertising and e-commerce domain, are utilised to shown the usefulness of the proposed approach, compared to related algorithms.", "questions": "- Why choosing the particular datasets? (additional data from some other application domains could support the work and findings further)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Paper proposes novel theoretical analysis of combining predictive uncertainty and classification score for decision boundary selection. The findings are supported by empirical analysis and versatile set of tests. It is shown that optimisation problem is NP-hard, and the new practical algorithms to approximate the solution with dynamic programming and isotonic regression based approaches, are presented. To my knowledge, the analysis and proposed algorithms for this particular problem are novel contributions, showing improvements against some related score only and 2D decision boundary selection algorithms on real-world benchmark datasets.", "weaknesses": "The proposed approach is motivated by the applications such as medical diagnosis and fraud detection. However, only advertising and e-commerce datasets are considered in the empirical experiment section. It would strengthen the work, if other additional imbalanced datasets from different application domains could have been experimented, as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "RZa0tMxclj", "reviewer": "Reviewer_i837", "summary": "The submission addresses making decisions under uncertainty. More precisely, it considers the binary classification setting, where an instance must be classified into one of two classes, and where the classifier provides a classification score with an associated level (score) of uncertainty. \n\nAfter a succinct reminder of previous works related to uncertainty modelling and decision-making under uncertainty, the paper first adopts a Bayesian view, and shows that the test positivity rate depends on both the positivity (classification) and uncertainty scores. Then, it proposes to transform the classification problem into picking a class based on both scores, by partitioning the corresponding 2D space (model x uncertainty scores) into bins, thus leading to a 2D decision boundary (instead of a 1D decision threshold for the model score) which maximizes recall for a desired precision level. The paper mentions several strategies for constructing the bins, and then proceeds with an empirical evaluation of the proposed strategy.", "questions": "Why choosing the differential entropy of distribution $H(q(\\mathbf{x}))$ as a measure of uncertainty ? On one hand, this intuitively makes sense, but it also has been criticized by some authors (see e.g. the works of Hüllermeier). \n\nThe interpretation of $\\gamma(\\mathbf{x})$ in Section 3.2 is not really an interpretation. Since the fact that $u(\\mathbf{x})$ is correlated with $\\gamma(\\mathbf{x})$ is central in the score estimation bias depending on score and uncertainty, this part may be further developed and discussed. \n\nCan you provide insights on generalizing the analysis of estimation bias to other settings (as compared to Fig. 2) ? \n\nThe decision-making approach seems debatable. In Section 4: is it reasonable to leave b unconstrained ? Shouldn't a monotonicity assumption be imposed ? Is it reasonable to always keep the decision-making process precise ? Wouldn't it be preferable to abstain in presence of a high (epistemic) uncertainty ? Aleatoric and epistemic uncertainties are here not distinguished from each other, which seems to be an issue: what if $u(\\mathbf{x})$ is maximal ? Is it reasonable to make decisions in this case ? What is the effect of discretizing the Score $\\times$ Uncertainty space ? To this extent, shouldn't the independent splitting on both dimensions avoided ? \n\nThe \"proof\" that the partitioning problem of the Score $\\times$ Uncertainty space is NP-hard (mentioned in the introduction) seems to directly proceed from the bin-packing problem behind. \n\nEqui-weight binning case, \"it is possible that a bin with lower positivity rate might be preferable to one with higher positivity rate due to different number of samples\": can you be a bit more specific ? \n\nBinning strategy: I understand that for any given score level, the uncertainty bin indices are monotonic wrt actual values; however, this does not correspond to the same level of model score. Des this have an impact on the results ? More generally, what is the impact of the binning strategy on the overall procedure ? This latter may be sensitive to the bins computed.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper addresses an interesting and important problem—making decisions under uncertainty. It covers the topic in a rather complete way, by first highlighting the relationship between uncertainty and estimation bias, and then proposing a strategy for improving decision-making by taking the uncertainty level into account. \n\nThe proposal is overall sound, with some theoretical grounding as well as an experimental study so as to support the claims.", "weaknesses": "My main criticism is that the paper ignores a large part of the literature on decision-making under uncertainty. There already exist many works dedicated to this topic, with the purpose of taking uncertainty into account to improve the decision-making process or abstaining to make decisions when uncertainty is too high. Some of these works are rooted in formalisms alternative to probabilities, while others make use of the classical probabilistic framework. It is obviously not possible to mention all of these works here—see e.g. cautious, imprecise or uncertain classification; I'll only mention several of them here: \n\n[1] Mathias C. M. Troffaes. Decision making under uncertainty using imprecise probabilities. International Journal of Approximate Reasoning, Volume 45, Issue 1, May 2007, Pages 17-29. \n\n[2] Thierry Denoeux. Decision-making with belief functions: A review. International Journal of Approximate Reasoning, Volume 109, June 2019, Pages 87-110. \n\n[3] Thomas Mortier, Marek Wydmuch, Krzysztof Dembczyński, Eyke Hüllermeier, Willem Waegeman. Efficient set-valued prediction in multi-class classification. Data Mining and Knowledge Discovery, Volume 35, Issue 4, Jul 2021, Pages 1435-1469. \n\nBesides, it is difficult to see to which extent the analyzes reported in the proposal can be generalized outside of the framework considered here, either regarding the analysis of estimation bias (Section 3.2) or the proposed decision-making strategy (Sections 4 and 5). As stated by the authors, the Bayesian framework considered here may likely not hold for all datasets. The analysis but also the proposed decision-making strategy seem hard to generalize to more than two classes (in the latter case, for computational reasons). It would have been nice to discuss these limitations in the paper. \n\nThe writing should be improved: there are typos; the general structure of the paper might be improved (e.g., Sections 4 \"2-D Decision Boundary Problem\" and 5 \"2-D Decision boundary algorithms\" could be agregated); some parts may be developed for the sake of clarity (e.g., the \"Dynamic Programming (DP) Algorithm\" part in Section 5.2, which is quite verbose but lacks formalization). I do not understand why the numbering of subsections changes from a bold, small-letter font in Section 3 (see e.g. Sections 3.1 and 3.2 page 3) to a capital font in Section 5 (e.g. Sections 5.1, 5.2 and 5.3 pages 6-7). Figures are hard to read (very small); Equation 2 is displayed in an awkward manner; Algorithm 1 is a bit packed and consequently difficult to read. \n\nTypos (non-exhaustive list): \n- \"relative efficacy\" (page 2), \n- \"Under what settings\" (page 2), \n- \"via Bernoulli distribution\" (page 3), \n- \"In the case of train set\" (page 3), \n- \"corresponds to oversampled negative class\" (page 3), \n- \"expected true and test positivity rate\" (page 4), \n- \"$b(u)$ is score threshold\" (page 5), \n- \"upto\" (page 6), \n- \"feasible solution exists\" (page 6), \n- \"bayesian approximation\" (page 10, references), \netc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "Hfx4kCJ24R", "reviewer": "Reviewer_D6i1", "summary": "This paper tries to improve classification performance by leveraging uncertainty estimates. To this end, the authors focus on posterior networks, a novel class of classification models that has been recently introduced as an alternative for Bayesian neural networks in OOD detection. Posterior networks model a second-order distribution that is parameterized by a neural network using specific loss functions. In this paper, the authors focus on binary classification, and the considered second-order distribution is a Beta distribution. \n\nIn addition, the authors assume that the data generation process also has a Beta prior over the Bernoulli parameter of the first-order distribution. Within this framework, the authors analyze model estimation bias and they show that it depends both on the aleatoric and epistemic uncertainty. Furthermore, they formulate decision boundary selection in terms of both types of uncertainty, and they prove that this problem is NP hard.", "questions": "See above.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "Uncertainty quantification is a hot topic in machine learning. The submission also contains material that is novel.", "weaknesses": "This paper is not well written. I have the impression that the authors lack a thorough understanding of the literature. They use unconventional notions, and they don't discuss the problem in a formal way. Let me make this point clear. \n\nIntroduction:\n- the authors write \"benefits of combining model score with estimates of aleatoric and epistemic uncertainty\". This is a very weird reasoning, because the model score corresponds to the estimate of aleatoric uncertainty. (btw, better to use conditional class probabilities instead of model score, because model score is a very generic term)\n- RQ1: Does model score estimation bias (deviation from positivity) depend on uncertainty? This is a really weird sentence that is difficult to understand. I only understood that sentence after reading Section 3. You first have to explain what you mean with model score estimation bias. Is it a bias in the sense of the traditional bias-variance decomposition or is it something else? The same with \"positivity\". That's a term that is never used in the literature. What you mean is the probability of the positive class on population level. After reading Section 3 it became clear to me what you mean with \"uncertainty\". It is the differential entropy of the second-order distribution. I would argue that this is a way to measure epistemic uncertainty with posterior networks, but you have to be more precise in your description. \n- Same comment for \"test positivity rate\". Never heard of this term before. Please define it. \n\nRelated work: \n- The overview of related work is described in a very vague way. What you call \"Uncertainty modelling\" are methods that intend to quantify aleatoric and  epistemic uncertainty, such as Bayesian methods, ensemble methods and evidential deep learning methods. \n- Please also describe methods that only quantify aleatoric uncertainty, such as traditional probabilistic models. In that context, I would argue that \"calibration metrics\" are a way to assess whether standard probabilistic methods quantify aleatoric uncertainty correctly.  \n  \nSection 3:\n- Posterior networks: please motivate why this group of methods is your first choice to improve classification performance by leveraging epistemic uncertainty scores. Recent papers have critisized this group of methods for not quantifying epistemic uncertainty in a correct manner, see e.g. Bengs et al. Pitfalls of epistemic uncertainty quantification through loss minimization, Neurips 2022. So, I would argue that it is weird to consider this group of methods as first choice.  \n- 3.1: the uncertainty score u(x) is a measure of epistemic uncertainty. Please be more precise. \n- 3.2: notions such as \"true positivity\" and \"empirical positivity in the train and test set\" are very weird terms. I assume that you refer to true and estimated conditional class probabilities for the positive class. Please be more precise. \n- 3.2: Why is the true positivity sampled from a Beta distribution? Is this to generate synthetic data, or what is the purpose of this? Since you are presenting a theoretical result in Theorem 3.1, I assume that you have a different purpose of considering a Beta distribution. \n-Theorem 3.1: \"When data is generated according to Figure 2\". Unclear what this means. The figure is not detailed enough. The data generation process has to be described in a formal way. \n\nBecause of the very imprecise write-up, it is difficult to follow what the novelty of this paper is. I have to admit that I was completely lost after Theorem 3.1, even though I am very familiar with posterior networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)