Rashomon Capacity: A Metric for Predictive Multiplicity in Classification
Authors: Hsiang Hsu
Flavio Calmon
Venue: NeurIPS 2022 Accept (2022)
Keywords: Rashomon effect
Rashomon set
predictive multiplicity
channel capacity
Rashomon capacity
probabilistic classifier.

Abstract: Predictive multiplicity occurs when classification models with statistically indistinguishable performances assign conflicting predictions to individual samples. When used for decision-making in applications of consequence (e.g., lending, education, criminal justice), models developed without regard for predictive multiplicity may result in unjustified and arbitrary decisions for specific individuals. We introduce a new metric, called Rashomon Capacity, to measure predictive multiplicity in probabilistic classification. Prior metrics for predictive multiplicity focus on classifiers that output thresholded (i.e., 0-1) predicted classes. In contrast, Rashomon Capacity applies to probabilistic classifiers, capturing more nuanced score variations for individual samples. We provide a rigorous derivation for Rashomon Capacity, argue its intuitive appeal, and demonstrate how to estimate it in practice. We show that Rashomon Capacity yields principled strategies for disclosing conflicting models to stakeholders. Our numerical experiments illustrate how Rashomon Capacity captures predictive multiplicity in various datasets and learning models, including neural networks. The tools introduced in this paper can help data scientists measure and report predictive multiplicity prior to model deployment.

Rashomon Capacity: A Metric for Predictive Multiplicity in Classification
Hsiang Hsu and Flavio Calmon
John A. Paulson School of Engineering and Applied Sciences, Harvard University hsianghsußg. harard. edu, flavio@seas hww.arr..e........... edu
Abstract
Predictive multiplicity occurs when classification models with statistically indistin- guishable performances assign conflicting predictions to individual samples. When used for aeriisionmmainng applications of consequence (e.g., lending, education, criminal justice), models developed without regard for predictive multiplicity may result in unjustified and arbitrary decisions for specific individuals. We introduce a new metric, called Rashomon Capacity, to measure predictive multiplicity in prob- abilistic classification. Prior metrics for predictive multiplicity focus on classifiers that output thresholded (i.e., 0-1) predicted classes. In contrast, Rashomon Capacity applies to probabilistic classifiers, capturing more nuanced score variations for in- dividual samples. We provide rigorous derivation for Rashomon Capacity, argue its intuitive appeal, and demonstrate how to estimate it in practice. We show that Rashomon Capacity yields principled strategies for disclosing conflicting models to stakeholders. Our numerical experiments illustrate how Rashomon Capacity captures predictive multiplicity in various datasets and learning models, including neural networks. The tools introduced in this paper can help data scientists measure and report predictive multiplicity prior to model deployment.
Introduction
Rashomon effect, introduced by Breiman [1], describes the phenomenon where multitude of distinct predictive models achieve similar training or test loss. Breiman reported observing the Rashomon effect in several model classes, including linear regression, decision trees, and small neural networks. In a foresighted experiment, Breiman noted that, when retraining a neural network 100 times on three-dimensional data with different random initializations, he "found 32 distinct minima, each of which gave a different picture, and having about equal test set error" [1, Section 8). The set of almost-equally performing models for given learning problem is called the Rashomon set [2,3].
We focus on a facet of the Rashomon effect in classification problems called predictive multiplicity. Predictive multiplicity occurs when competing models in the Rashomon set assign conflicting predictions to individual samples [4]. Fig. presents an updated version of Breiman's 's neural network experiment and illustrates predictive multiplicity in three classification tasks with different data domains and neural network architectures. Here, models that achieve statistically statistically-iidistnnggiii indistinguishable performance
test set assign wildly different predictions to an input sample. If predictive multiplicity is not accounted for, the output for this sample may ultimately depend on arbitrary choices made during training (e.g., parameter initialization).
Predictive multiplicity captures the potential individual-level harm introduced by an arbitrary choice of single model in the Rashomon set. When such model is used to support automated decision- Algorithmic Leviathans
making in sectors dominated by a few companies or Governeent-labell in [5, Section 3] preprccie multiplicity can lead to unjustified and systemic exclusion of individuals from critical opportunities. For example, an algorithm used for lending may deny a loan to a specific
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

True label dog
Street
Frequency (Hz)
True label World
20k
Fujimori List Blocking Entry U.S.
Former Presidert Alberta Fujimari is on
watch barring his entry to the allepations corruption during decade-fore authontarian regime, a U.S. diplomatic official sald.
2 Time [c]
Hon
Ger shat
2a00
fro
12b
Deiling
Street Music
Cross- Entropy Less
Cross Entropy Loss 0.301
Cross Entropy Loss
0.502
0.519
0.508
0.519 0.517
0.297
0.295 0.300
0.300
1.981
2,083
1.956
1.930
1.964
1.0
1.0
1.0
0.9
0.8
0.8
Outgut Scores
0.7
1 0.7
0.7
0.6
0.6
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
0.1
0.0
0.0
0.0
Model
Model
Model
(a) CIFAR-10 dataset
(b) AG News dataset
(c) UrbanSound8k dataset.
Figure 1: The scores (bottom) of sample (top) generated by competing models. Predictive multiplicity occurs on different data domains and learning models, including an image dataset (CIFAR-10 [8]) trained with VGGI6 [9], natural language dataset (AG News [10]) trained with simple neural networks after tokenization, and an audio dataset (UrbanSoundSk [I1] trained with LSTM [12].
applicant. However, during model development, there may have been a competing model which performs equally well on average, yet would have approved the loan for this individual. As another example, Governments are increasingly turning to algorithms for grading exams that grant access to higher-level education (see, e.g., UK [6] and Brazil [7]). Here, again, accounting for predictive multiplicity is critical: an arbitrary choice of a single model in the Rashomon set may lead to an unwarranted restriction of educational opportunities to an individual student.
We introduce new methods for measuring and reporting predictive multiplicity in probabilistic classification. First, we postulate several properties that a predictive multiplicity metric must satisfy to simplify its interpretation by stakeholders. We then provide a new predictive multiplicity metric called Rashomon Capacity. Rashomon Capacity quantifies score variations among models in the Rashomon set for a given imput sample. Unlike prior metrics restricted thresholded scores (i.e., decisions), Rashomon Capacity can be applied to probabilistic classifiers that output probability distribution over a set of classes (e.g., neural networks with soft-max output layers). Communicating such score disagreements helps stakeholders understand whether a given prediction is arbitrary, e.g.. depending on randomness during training rather than patterns in the data.
We show that Rashomon Capacity of an input sample can be entirely captured by at most models in the Rashomon set, where e is the number of predicted classes, regardless of the size of the Rashomon ser. Remarkably, the computation of Rashomon Capacity also sheds light on strategy for resolving predictive multiplicity. Instead of releasing a single model, we provide a greedy algorithm for identifying a subset of models in the Rashomon set that captures most of the score variations across a dataset. These models can be communicated to a stakeholder, empowering them to decide how to resolve conflicting scores via, e.g., randomization [5] and bagging [1]. In summary, our main contributions include:
1. We postulate desirable properties that any predictive multiplicity metric must satisfy. These properties motivate definition of Rashomon Capacity and provide guidelines for the creation of new multiplicity metrics in future research. We also outline computational challenges in estimating predictive multiplicity in practice.
2. We introduce new bosre- metric for quantifying predictive multiplicity called Rashomon Capacity. Rashomon Capacity can be applied to measure score variations across competing classifiers that output either raw or thresholded (i.c. 0-1) scores.

---

3. We describe a methodology for reporting predictive multiplicity in probabilistic classification using Rashomon Capacity. with examples on different datasets and models. We advocate that predictive multiplicity must be reported to stakeholders in, for example, model cards [13].
4. We propose a procedure for resolving predictive multiplicity in probabilistic classifiers. Even though the Rashomon set may span large (potentially uncountable) number of models, we show that the score variation for a sample is fully captured by small subset of models in the Rashomon set. Communicating these predictions to stakeholders can empower them to decide how to resolve predictive multiplicity.
Omitted proofs, additional explanations and discussions, details experiment setups and training, and additional experiments are included in Supplementary Materials (SM). Code to reproduce our experiments is available at http://hw....o///aoo/////////ooo
2 Background and related work
Notation. We consider dataset D = {(x;, yt) e.g., a training or test set, for a classification task with claasess/aaels.. Each sample pair (x,, Y+) drawn i.i.d. from Px,y with support X' x Ac- Here, A. & {(r1,-'. ,re) E [o. Ei=
= 1} denotes the c-dimensional probability simplex. Let cg be a length-c indicator vector with one in the Athh position and zero elsewhere, i.e., [ca]R 1, Vj * k. where I- denotes the jth entry of a vector. Each y; is one-hot encoded, i.c.. y: E ) 1()) denotes the indicator function.
and [ex],
We denote by H. hypothesis space, i.e., set of candidate probabilistic classifier is parameterized by A ④ C Rd that approximate Py|x=x; i.e., H. A [ho X A. A θ). The loss function used to evaluate model performance is denoted by é Ae x A. + R+ (c.g., cross-entropy) and L(ho) & Exx.y (X(ho(X), Y)] the population risk. As usual, the population risk is approximated by the empirical risk (hh) & 1 E E(ha (x.)
Rashomon set, Rashomon ratio, and pattern Rashomon ratio. We define the Rashomon set as the set of all models in the hypothesis space that yield similar average loss. Formally, given Rashomon parameter 2 the Rashomon set is defined as an e-level set [3]:
R(H, e) & {he E H: L(h)) Sc).
(1)
Note that the Rashomon set is determined by the hypothesis space H. the Rashomon parameter 6, and also implicitly by the data distribution due to the evaluation of L(ha). The cardinality |R(H, e)] or the volume' vol e)) of the Rashomon set (depending on whether the Rashomon set has finite elements) can be used to quantify the size of the Rashomon set. Given R(H, e). the Rashomon ratio [3, Defn. 2] is defined as R(H, e) A vol()((.e))
vol(H) R(H, <) represents the fraction of models in the hypothesis space that fit the data about equally well. A large Rashomon ratio indicates high multiplicity. Moreover, models with various desirable properties, such as better generalizability, can often exist inside a large Rashomon set. Similar to the Rashomon ratio, pattern Rashomon ratio [3. Defn. 12] is defined as the ratio of the count of all possible binary predicted classes given by the functions in the Rashomon set to that given by the functions in the hypothesis space. The complexity of computing pattern Rashomon ratio grows exponentially with the number of samples, yielding an "expensive" metric for predictive multiplicity when applied to large datasets.
Ambiguity and discrepancy. Instead of characterizing multiplicity in the hypothesis/ parameter space. Marx et al. [4] measure multiplicity in terms of the thresholded outputs (i.e., predicted classes) of a classifier, and propose two metries: ambiguity and discrepancy. Ambiguity is the proportion of samples in dataset that can be assigned conflicting predictions by competing classifiers in the Rashomon set. Discrepancy is the maximum number of predictions that could change a dataset we were to switch between models within the Rashomon set. More precisely, given a base model h.
Since H is parameterized, the volume of R(H,e) c) {0 θ; (hh)) S <) can be directly computed in Rd.
3

---

Rashomon Set
Predicted Class
Predicted Ciiaa
Class
Class
0.0
Probabilistic Classifier
Thresholding Scores
Class
Modal
Model
Class
0.2
Class
Class
roddddeed Class 2
Predicted
Class 2
Class
Class 3
Class
Class
Model.3
Model
Hypothesis Space
3-Dimensional Simplex
Predicted Classes
Figure 2: Left: 4 models output similar scores for classes, but the predicted classes produced via thresholding very different. This may Icad to high ambiguity and/or discrepancy (cf. (2)). Right: Given sample, the scores obtained from different models (colored dots) in the Rashomon set lead different predicted classes by thresholding the scores (based on decision boundaries, i.e. dashed lines in the simplex). Prior work either measure multiplicity on the hypothesis set, c.g., the Rashomon ratio, or in terms of predicted classes, e.g., pattern Rashomon ratio and ambiguiyyllisrrpannyy In this work, we measure predictive multiplicity directly in terms of scores on the probability simplex, i.e., either thresholded raw scores.
the ambiguity (h) and the discrepancy (h) respectively defined
a, (h)
max 1 (E)(H,
arg max h(x;; * arg max h(x:)
(2)
5. (h)
Σ ==1
arg max h(x;) * arg max h(x;))
max (ER(H,,)
For linear classifiers, both quantities in (2) can be estimated by mixed integer programming [4, Section 3]. small e could still lead to a large ambiguity, see Section SM. 2.2 for a discussion.
Measuring predictive multiplicity of probabilistic classifiers
The metrics in (2) for predictive multiplicity are based on predicted classes. Thus, they require finding the arg max or thresholding the scores the output classifier. In probabilistic classification, thresholding may mask similar predictions produced by competing models and artificially increase multiplicity: output scores can be almost equal across different classes, yet the (thresholded) predicted classes can be very different. For example, two scores [0.49, 0.51] and [0.51, 0.49] for binary classification problem can lead to entirely different predicted classes after thresholding-11 and O, respectively- and ultimately overestimate predictive multiplicity (see Fig. (Left) for another multi-class example). In fact, predictive multiplicity metrics based on predicted classes may yield multiplicity even for single fixed model when, for example, the threshold criteria for output scores changed. This subtle, yet important difference motivates us to reconsider existing metrics and introduce predictive multiplicity metric that is applicable both output scores and decisions (cf. Fig. 2 (Right) for an overview).
We begin this section by first outlining desirable properties of predictive multiplicity metrics for probabilistic classifiers. Motivated by the potential individual-level harm incurred by an arbitrary choice of model in the Rashomon set, we focus on per-sample multiplicity metrics. We formally define Rashomon Capacity in terms of the KL-divergence between the output scores of classifiers in the Rashomon set. We then use Rashomon Capacity to define predictive multiplicity metric for individual samples in a dataset. We present these definitions in the ideal case where the population loss can be computed exactly, and discuss empirical approximation in Section 4.
3.1 Properties of multiplicity metrics for probabilistic classifiers
Consider a fixed data distribution Px.y and a corresponding Rashomon set R(H, c) for classification problem with e classes. For given sample x, D. we collect all possible output scores produced by models in RH,, c), and define the e-mulriplicity set as
(x,,) A (h(x)); R(H, S A..
(3)

---

Let m(-) be measure of predictive multiplicity, and m(M,(x,)) be the predictive multiplicity of sample x,, Which properties should m².) have? Ideally, we expect m(M,(x;)) be bounded value in [1, c). since at least one class is assigned to sample x,, and at most different classes could be assigned to x,. Moreover, if m(M mx;)(xx)) = (i.e., a predictive multiplicity of 1), then one would expect that only one score is produced for x; and, thus, all predictions in (x,) are exactly the same. Similarly, if mmM.(x.)) = c (i.e., predictive multiplicity equal to the number of classes), then there must exist models (fu,.... hhe C R(H, e) such that hy (x,) = =j. In other words, each of the classes can be assigned to the sample, yielding a predictive multiplicity of c. Finally, ra(M, rx(M.((.)) should be monotonic in Mx,),,, i.., if M. (x,) S MM,x,,,, then m(M,(xx)) S m(M'(xx))) We summarize these desirable properties of predictive multiplicity metrics in the following definition.
Definition 1. Let Pe be the power set of the probability simplex De. The function m Pe \ 1 - R a predictive multiplicity metric for any A,B E Pe
1. 1 1 m(A) S c;
2. m(A) = 1 if and only if A S 1:
3. m(A) = c. if and only if E A k [c]. i.e., A contains the corner points of Aoi
4. m(A) S m(B)ifASE
We introduce next predictive multiplicity metric called Rashomon Capacity that satisfies all properties above. In the rest of the paper, when the c-multiplicity set M,(-) is clear from context, we use m(x;) as shorthand for mxM)(x:)).
3.2 Rashomon Capacity
Our goal is quantify predictive multiplicity in terms of the score variations assigned to each sample X; in dataset D, given Rashomon set R(H,, c) and the corresponding c-multiplicity set M. (x;). Note that an element in Mx,)) is a probability distribution over e classes. Thus, it is natural to adopt divergence measures for distributions to capture the "variation" of scores in MM(x.). From geometric viewpoint, a larger spread in scores indicates a greater amount of predictive multiplicity for given sample x;.
Assume a probability measure (or "weight") PM across models in R(H, e) (and therefore each score in Mx)x)),. where M denotes the random variable of selecting/sampling the models in the Rashomon set. Intuitively, if PM assigns mass to single model and 0 to all other models in the Rashomon set, then the output of only one model is considered. Alternatively, if Par is the uniform distribution, then the outputs of every model in the set are equally weighed. Given divergence measure between distributions d(-ll-), we quantify the spread of the scores in MM(x)) by
p(Me(x.), PMr)
inf En-P,, dl (x(xx))))))
(4)
qea.
Here, the minimizing q acts as a "center of gravity" or "centroid" for the outputs of the classifiers in the Rashomon set for chosen distribution Pas across models. Analogously, the quantity (x,,, PM)
can be understood as a measure of "spread" or "inertia" across model outputs. We select the distribution Pas that results in the largest spread in scores:
(x:)
A sup pl (x), PMr) = sup inf En- Pan d(hx)))lq)) Pxe qEa.
(5)
PM
The missing element is the choice of divergence measure d(-ll-). A natural candidate is cross- entropy (or log-loss) d((((x))lqq) -h(x;)) T log q, since this is the standard loss used for training and evaluating probabilistic classifiers. Alas, the minimal cross-entropy m log q hxx)) log f(xx)) is not O and depends on h(x;). Consequently, if one were to choose d(-ll-) to be cross-entropy, the minimum value of (5) would not be consistent and would depend on x; even when the outputs across all models in the Rashomon set match! Thus, we shift cross-entropy by its minimum -ix log h(x;). This results in KL--diergence as our divergence measure of choice: -h(x)) log q + h(xx)) T log h(x;). Putting all together, we next formally define the spread in scores measured using KL-divergence as Rashomon Capacity.
DRL (h(x:)llq)
2 We exclude the empty set 0 from Pe, since the multiplicity of an empty scores set is not well-defined.
We use the term "metric" loosely, not in the sense of defining metric space over
5

---

Definition 2. Given a sample x.. a Rashomon set R(H,e), c), and the corresponding e-multiplicity set M,(x;), the Rashomon Capacity* defined as mc(x,) a 2C(MM(xx)) where C(Mc(x))) = sup inf EA (xx((())))))))
(6)
Par qeèc
where the supremum in the right-hand side is taken over all probability measures Pas over R(H,,) e).
The exponent (x)) ) is ubiquitous in information theory; in fact, (xM((x.) is the channel capacity [14] of a channel Py whose rows are the entries of (x(x)). This connection motivates the name "Rashomon Capacity" and is useful for proving that (x(x;) is indeed a predictive multiplicity metric, as stated in the next proposition.
The function mc(-)- 20(M.0) X + [1, c] satisfies all properties of a predictive multiplicity metric in Definition 1.
Proposition 1.
In contrast, ambiguity and discrepancy in (2) do not satisfy the properties of a predictive multiplicity metric outlined in Definition 1. An interesting connection between ambiguity and Rashomon Capacity is that ambiguity measures the fraction of samples in a dataset with non-zero Rashomon Capacity. In addition, Rashomon Capacity is fundamentally different from the size of Rashomon set, in the sense that a larger Rashomon set does not necessarily lead to a larger Rashomon Capacity. Using a binary classification problem as an example, consider two Rashomon sets with scores
R1 (H, c) = (h1, h2, ha), hy (xx) = [0.45, 0.55], (x,) = [0.50, 0.50), hx(x,) = [0.60, 0.40), R2(H.,) e) (h1, h2); (x,) [0.85, 0.15], (xx))) [0.10, 0.90).
R2 (2H, c) has larger Rashomon Capacity than R1,,, albeit (R2(H, = (Ra(H, (7)
3.3 Rashomon Capacity in score and decision domains
Rashomon Capacity is defined in terms of the raw outputs in A, of a probabilistic classifier; therefore it can also be evaluated with decisions, since decision, after one-hot encoding, still lies in the probability simplex (at a vertex). This allows Rashomon Capacity to provide a more nuanced view of score variation, and can be used to identify the number of "confficting" classes in the predictions produced by models in the Rashomon set (i.c., Rashomon Capacity is between 1 and c).
Taking ternary classification as example, for three score vectors [0.49, 0.51, 0] and [0.51, 0.49, 0]. the Rashomon Capacity of the raw scores for these samples is close to For the thresholded scores ([O, 1. 0] and [1, 0, 0l) the Rashomon Capacity is now 2. Since Rashomon Capacity is between I and 3. this indicates that the confusion is between classes instead of contrast, prior metrics that also operate thresholded scores, such as ambiguity and discrepancy (2), only capture agreement among predictions. In this sense, score-level metrics could potentially provide a finer characterization of predictive multiplicity. This does not mean that multiplicity should only be reported in the score domain. On the contrary, our suggestion is that multiplicity should be measured at both the score and threshold levels and reported to stakeholders, scores and decisions paint different pictures on how models conflict.
Computational challenges of multiplicity metrics
The computation of any multiplicity metric requires approximate characterization of the Rashomon set-even for simple hypothesis spaces such as logistic regression. For instance, the computation of the Rashomon ratio involves estimating vol(R c)), which is level set estimation problem [15], and is computationally infeasible" when the hypothesis space H is large [16]. For a logistic regression, the exact form of the pattern Rashomon ratio is not tractable due to the non-linearit of the maximum requires solving an
likelihood ratio [17]. Similarly, the computation of ambiguity/dissrepane optimization over the Rashomon set and can be computationally burdensome since 0-1 loss is not differentiable.
'We consider logarithums in base 2, and the unit of C(M, (x.)) is bit. We include further discussions and geometric interpretation of Rashomon Capacity Sections SM. 2.3 and SM. 2.4 respectively.
"An exact computation of vol(R <)) in special case, e.g., ridge regression where the Rashomon set forms ellipsoid, is provided in [3, Section 5.1].

---

Given a dataset and hypothesis space, there are two core challenges in computing any predictive multiplicity metric (see Definition 1). The first challenge is selecting an uppropriate Rashomon parameter since the smallest achievable test loss [hhh)) is unknown and only empirically approx- imated using a dataset with finite samples. The second challenge approximating the Rashomon set without exhaustively searching the hypothesis space". Next, we discuss strategies for addressing these two challenges.
Selection of the Rashomon parameter e. The value of can be set relative to the performance of a reference model. natural choice of the reference model the empirical risk minimizer, i.e., hg., where 0 E arg mingge (hg) (see Section 2 for notation). Here, we can set E = (( + é' with é' 2 O, i.e. the Rashomon parameter depends on the minimum empirical loss. The parameter é', in turn, can be selected in terms of the upper boundary of a confidence interval around the empirical minimum. For example, the confidence interval can be estimated via bootstrapping (see Fig. SM. 4.6 for bootstrapped loss intervals). Naturally, e' depends on the size of the test set used for evaluating hg wheh the dataset has samples, usually e' will be of the order O (()//n) [19]. If more samples are available to evaluate model performance (rendering narrower confidence intervals), this parameter's value will decrease.
The discussion above motivates the one-sided definition for the Rashomon set in (1). one were able to find the unique classifier that outperforms all others in terms of population loss, then it is justified to use this classifier in practice. In fact, this point is eloquently made in [5], which argues that there is no (moral) harm in using the most accurate classifier, i.e., selecting classifier that has a provable smaller average loss (or higher accuracy) than another. Existing works on multiplicity, e.g., [3] and [4]. also adopt one-sided Rashomon set definition.
The Rashomon subset. With limited computational power and memory, exploring the Rashomon set, i.e., searching the hypothesis space H to find all models with test losses smaller than e, is challenging. For several hypothesis spaces (e.g., neural networks), we are only able to acquire a small number of models in the Rashomon set. We denote the collection of these models as a Rashomon subset c).
The Rashomon subset can be used to approximate the "true" Rashomon set R(H, e) in the evaluation of multiplicity metrics. We can construct Rashomon subset with K models by choosing the Rashomon parameter in terms of reference model hgg i.e.,
(8) For example, the Rashomon ratio can be approximated as (H). Similarly, we can optimize for ambiguity/dissrepancy in (2) over he, E &R(H, c'). Finally, we can approximate the c'-multiplicity subset (x,) e (x,); E e) in (3) for Rashomon Capacity.
R(H, c') A (ha, E H; L(ho)) S ((ha=) ) + + C RRH, ((ha)) e').
In this sense, evaluating multiplicity metrics boils down to finding Rashomon subset R(H, e') and computing the metric for that set. This is an approximation of the true multiplicity, yet becomes more accurate with an increasing K. Next, we provide an algorithm based on model weight perturbation to find a Rashomon subset for estimating Rashomon Capacity for any differentiable model.
Note that, unless the Rashomon set can be fully characterized, all estimates of multiplicity metrics are underestimates based approximating the true Rashomon set by Rashomon subset. We emphasize that identifying and disclosing predictive multiplicity - even if an underestimate - is still critical for models deployed in applications of individual-level consequence (e.g.. healthcare, education, lending), and is better than the current practice reporting no multiplicity at all.
Computing Rashomon Capacity. The definition of Rashomon Capacity in (6) does not assume a finite cardinality of the Rashomon set. Remarkably, even when the Rashomon set has infinite cardinality, the value of Rashomon Capacity of sample can be recovered by considering only small number of models in the Rashomon set. In fact, for each sample x;, there exists a e-multiplicity subset of at most models that fully captures the variation in scores. This statement is formalized by the next proposition, which can be proven by applying Carathéodory's 's theorem [20].
'In neural networks, for example, the size of the Rashomon set is determined by the number of local minima, which grows exponentially many with the number of parameters [18].
7

---

Proposition 2. For each sample x, E D, there exists a e-multiplicity subset M.(x,) S MM(xx) with (x.)x S that fully captures the spread in scores for x; across the Rashomon set, i.e. (xM((x)) = (xM)(x)). In particular, there are at most с models in Rashomon subset R(H, E) whose output scores yield the same Rashomon Capacity for x; as the entire Rashomon set.
Proposition 2 implies that, for each sample, there exists a Rashomon subset with models that captures all score variation. In other words, the value of Rashomon Capacity remains the same regardless if we measure multiplicity on this subset or on the entire Rashomon set. This allows us to circumvent the task of characterizing the entire Rashomon set (which has potentially infinite models), and focus on identifying models per sample that maximize score variations while still satisfying target loss constraint. We describe next method (described in detail in Algorithm S.M. 2) based on weight perturbation that obtains e models in the Rashomon subset for each sample.
Given sample x,, obtain models with output predictions P& by approximately solving the following optimization problem which maximizes the output score for class k:
Pk hx(x;), where θ
arg max (x:(x))k Ak 1,2, cc
he (R,,(H,)))
To solve (9), for each k we set the objective to be minøge - (x; update the parameter f until [(hg) > c. Given a pre-trained model in the Rashomon set, (9) can be viewed as an adversarial weight perturbations (AWP) technique explore the Rashomon set (21,22) (see Section SM. 2.6 for exact weight perturbation on logistic regression).
ks compute the gradients, and
With the discrete e-multiplicity subset obtained by solving (9), Rashomon Capacity can be computed by standard procedures such as the Blahut-Arimott (BA) algorithm [23, 24]. The BA algorithm is class of iterative algorithms for numerically computing discrete channel capacity (or more generally. the ante-distortion function), see Section SM. 2.5 for more details. Note that AWP may still underestimate the true Rashomon Capacity, yet it greatly improves the estimates compared to prior work and is less computationally intensive than sampling, as shown in the next section.
The procedure in (9) reveals a desirable property of Rashomon subset: it should include models with significant score variations. Similarly, a desirable Rashomon subset for accurately evaluating ambiguity'discrppacyy is one with models that have most score disagreement. This property also ex- plains why collecting a Rashomon subset by straightforwardly sampling models [3] in the Rashomon set could be inefficient (ef. Algorithm SM. 1) since the randomly sampled models would not neces- sarily have a significant score disagreement/variation significant amount of models; see for example in [3, Section 6]. a Rashomon subset consisting of 250k decision trees.
In fact, the sampling strategy could require a
5 Empirical study
We illustrate how to measure, report, and potentially resolve predictive multiplicity of probabilistic classifiers using Rashomon Capacity on UCI Adult [25], COMPAS [26]. HSLS [27], and CIFAR-10 datasets [8]. UCI Adult and COMPAS are two binary classification datasets on income and recidivism prediction, respectively, and are widely used in fairness research [28]. The HSLS is an education dataset, collected from high school students in the USA, whose features include student and parent information (see Section SM. 3.1 for details). We created a binary label Y from students' 9th -rl-gr math test scores (i.e., top 50% vs. bottom 50%). We select the first three datasets to illustrate the effect of predictive multiplicity on individuals. Finally, we include the CIFAR- 10 dataset demonstrate how to report Rashomon Capacity in multi-class classification.
For the classifiers, we adopt feed-forward neural networks for the first three datasets, and convo- lutional neural network VGG16 [9] for CIFAR- 10. For more information on the datasets, neural network architectures, and training details, see Section SM. 3.2. All numbers reported evaluated on the test set.
Measuring and reporting predictive multiplicity via Rashomon Capacity. We evaluate two meth- ods, sampling with different weight initialization seeds [3] and AWP (9), and report the Rashomon Capacity in Fig. 3. For sampling, we construct a Rashomon subset R(H, e') with 100 models by different random initialization (cf. (8) with K 100). For AWP, the e'-multiplicity subsets Me (xx)
8

---

2.0
2.0
10
Sempling 10% 1
Semplnng mn k
Semp bng 15% (x
Rashaman Coascity
1.8
JWMh 15% tall
Rashoran Capacity
18
Kish 15%
Rashoman Coascity
2.8
Aac 15% talt)
JAP 12% talh
ApP 13% tall)
Ape 13% tall)
3.6
3.6
3.6
2.4
2.4
2.4
3.2
1.2
3.0
1.0
3.0
Cumulative Ditribution
0.01
Rashoman parameter p
0.02
0.05
0.20
Cunulativn Dist-bbut ibution
0.01
Rachoman parameter p"
0.02
0.05
0.10
Camulatvv Ditributtoon
0.01
Rachoman parameter p
6.02
0.05
0.30
Curndllivv nieritation
Rashamon parameter
0.02
0.05
1.00
1.00
1.00
200
0.75
0.75
C.75
0.50
0.50
6.50
0.23
0.25
0.55
0.25
0.00.5
C.25
- 0.08
0.00
0.00
0.00
0.00
1.5
1.5
2.5
5.0
Rashomon Capacty
Rashomon Capacty
Rashoman Capacity
Reshomon Capecity
(a) UCI Adult (80.28%)
(b) COMPAS (66.22%)
(c) HSLS (70.39%)
(d) CIFAR-IO 10 (81.6%%
Figure 3: For each dataset (percentage is test accuracy). the top figure shows the mean and standard error of the largest 1% and 5% (1% tail and 5% tail in the legend) Rashomon Capacity among all the samples with difference Rashomon parameter e. Two methods are used to obtain models from the Rashomon set, AWP (9) and random sampling The bottom figure shows the cumulative distribution of the Rashomon Capacity of all the samples obtained by AWP. Each point is generated with 5 repeated splits of the dataset.
of each sample x; is constructed by the Pi.-.. Pe obtained from (9). For example, when e' = 0.01, the models in the Rashomon set RH. 0.01) achieves small and statistically indistinguishable test losses from each other; however, the Rashomon Capacity is non-zero for significant fraction of samples. In particular, we showcase the average top 1 % and top 5% of the Rashomon Capacity from all samples for different é', and the cumulative distribution of the Rashomon Capacity across the samples. As the Rashomon parameter increases, both samp1 ing and AWP lead to higher Rashomon Capacity since the Rashomon set gets larger. Observe that the increase of Rashomon Capacity when varies from 0.01 to 0.02 is different for UCI Adult and COMPAS datasets, since the choice of is data-dependent. The AWP (9) achieves higher Rashomon Capacity than random sampling as AWP intentionally explores the Rashomon set that maximizes the scores variations. It is important to keep in perspective that each sample in the RashoRa Capacity tail displayed in Fig. corresponds to an individual who receives conflicting predictions. In applications such as criminal justice and education, conflicting predictions for even one individual should be reported in, e.g., model cards [13].
For the experiments in Figure 3, the estimated Rashomon ratio almost all zeros since the hypothesis space, parameterized by millions of parameters, is always significantly larger. In SM, we further report (i) other strategies to explore the Rashomon set in Section SM. 4.2, (ii) Rashomon Capacity evaluated with decisions instead of scores in Section SM. 4.3, and (iii) other metrics of multiplicity such ambiguity/discrepanncy in Section SM. 4.4.
Resolving predictive multiplicity by greedy model selection. Predictive multiplicity could be resolved by, for example, selecting subset of models (potentially of size one in the ideal case) and releasing the scores to a stakcholder. We propose a greedy model selection procedure to select a subset of competing classifiers for resolving predictive multiplicity. Given R competing classifiers, the goal is to select r models (r < R) that result in distributions of the Rashomon Capacity similar to that of the original R models. Starting from a dataset 'D and a Rashomon subset R é'), this can be implemented by (i) initializing a set A of models by randomly selecting a model in R(H, e'), (ii) growing AA by adding one model from R(H, E') that maximizes the average Rashomon Capacity across D, and (iii) stopping until there are r models in A. This greedy model selection is inspired by Property 4 (monotonicity) in Definition 1, since including the models to the set A does not reduce capacity. In Fig. 4, we models from the Rashomon sets for UCI Adult, COMPAS, HSLS and CIFAR-10 datasets respectively. Here, the hypothesis space are feed-forward neural networks (see details in Section SM. 3.2). Observe that only a small subset of the sampled models, selected by the greedy model selection procedure, is required to recover the distribution of the Rashomon Capacity. On COMPAS dataset, the 10 models obtained by the greedy model selection procedure capture the Rashomon Capacity computed with the original 163 models, i.e., these 10 models display most of the score variations.

---

(& (.50) 14
1R00,033 -2 Greedy modab)
pitr o 031) 20
Count
Groedy (28 model
Counte
Counts
102
Crosid C2S matubb)
10
LO
10
1.00
1.75 Rashoman Copocity
1.25
1.50
2.00
1.00
1.25
1550
1:75
2.00
1.0
3.6 1.6 Rashomon Capacity
1.2
14
B
10
Rashomon Capacity
Roshommon Capacity
(a) UCI Adult (83.47%) (b) COMPAS (67.35%)
(c) HSLS (69.91%)
(d) CIFAR-I0 (80.33%)
Figure 4: The distributions of the Rashomon Capacity for UCI Adult, COMPAS, HSLS and CIFAR- 10 datasets is percentage of mean accuracy) obtained by sampling models from the Rashomon subset and applying greedy model selection procedure (Greedy the legend) on the sampled models.
In Section SM. 4.1, we provide worked-out example with the COMPAS dataset on how Rashomon Capacity can be used to identify high-multiplicity samples. We observe patterns in sex and prior convictions leading strategies, e.g., ensemble methods, model calibration and weight regularization to resolve multiplicity, in Sections SM. 4.5 and SM. 4.6. We observe that the ensemble method could lead to a smaller Rashomon Capacity, and is a viable strategy for resolving multiplicity in small models, but may be infeasible for large, computationally expensive models. In addition, weight regularization for logistic regression (e.g., LASSO or ridge penalties) could also reduce Rashomon Capacity. On the other hand, a perfectly calibrated classifier does not necessarily resolve multiplicity- a classifier whose predicted classes matches the true classes "on average" across samples does not necessarily translate consistent of predictions for a single target sample across equally calibrated classifiers.
samples having high Rashomon Capacity. We further discuss promising
6 Final remarks
Limitations. The AWP (9). despite being more efficient than random sampling, still requires re- re-training/pertubbingg a significant amount of models, and is computationally burdensome when scaling up large datasets with millions of samples. Rashomon Capacity in certain cases may seem small for already significant score variations across classes, due to the convexity of KL-divergence. Indeed, this issue will occur for any strictly convex measure of divergence in (4). We provide further discussion of how to interpret the numerical values of Rashomon Capacity in Section SM. 2.7.
Future directions. First, overcoming the computational bottleneck to efficiently explore the Rashomon set is impactful direction for optimization techniques. Second, Rashomon Capacity could be generalized to other probability divergences, e.g., f-divergences [29], Rényi divergence [30], or Wasserstein distance [31]. This generalization could potentially provide further operational signifi- cance and tunability for measuring multiplicity, as long as the conditions in Definition are satisfied. Third, ensemble methods could be promising strategy reduce predictive multiplicity that worth
studying.
Broader impacts. The Rashomon effect impacts model selection [32-35], explainability [36]. and fairness [37]. Rudin et al. [32] suggested that, given the choice of competing models, machine learning practitioners should select interpretable models a priori, rather than selecting a black-box model with conjectural explanations post-training. Hancox-Li [33] and D' Amour al. [34] argued that epistemic patterns, e.g., causality, should be reflected when selecting models the Rashomon set. Black et al. [35] further studied multiplicity in the context of the conventional bias-variance trade-off analysis. Competing models in the Rashomon set may not only render conflicting explanations for predictions [36] and measures of feature importance [2], but also have inconsistent performance across population sub-groups. Consequently, the arbitrary choice of a single model may result in unnecessary and discriminatory bias against vulnerable population groups [37]. See Section SM. 2.1 for further discussion, including connections with individual fairness [38].
Acknowledgement
This material based upon work supported by the National Science Foundation under grants CAREER 1845852, IIS 1926925, and FAI 2040880, and by Meta Ph.D. fellowship.
10

---

References
[1] L. Breiman, "Statistical modeling: The two cultures," Statistical science, vol. 16, no. 3, pp. 199-231, 2001.
[2] A. Fisher, C. Rudin, and F. Dominici, "All models wrong, but many are useful: Learning variable's s importance by studying an entire class of prediction models simultancously." Journal of Machine Learning Research (JMLR), vol. 20, no. 177, pp. 1-81, 2019.
[3] I.. Semenova, C. Rudin, and R. Parr, "A study in rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning," arXiv preprint 1908./990../1/1
2019.
[4] C. Marx, F. Calmon, and B. Ustun, "Predictive multiplicity in classification," in Proceedings of International Conference on Machine Learning (ICML). PMLR, 2020.
[5] K. Creel and D. Hellman, "The algorithmic leviathan: Arbitrariness, fairness, and opportu- nity in algorithmic decision making systems." " in Proceedings of the Conference on Fairness, Accountability, and Transparency (FAceT). ACM, 2021.
[6] H. Smith, "Algorithmic bias: should students pay the price?" Al & society, vol. 35, no. 4, PP. 1077-1078, 2020.
[7] INEP, "Instituto nacional de estudos e pesquisas educaionais anísio teixeira, microdados do ENEM," o-novo-enem, 2020.
[8] A. Krizhevsky, G. Hinton et al., "Learning multiple layers of features from tiny images (technical report)," University of Toronto, 2009.
[9] K. Simonyan and A. Zisserman, "Very deep convolutional networks for large-scale image recognition," arviv preprint arXiv: 1556, 2014.
[10] X. Zhang, J. Zhao, and Y. LeCun, "Charrcter-Ievel convolutional networks for text classificatton, in Advances in Neural Information Processing Systems (NeurIPS), 2015.
[11] Salamon, C. Jacoby, and J. P. Bello, "A dataset and taxonomy for urban sound research," in Proceedings of the 22nd International Conference on Multimedia. ACM, 2014.
[12] K. Greff, R. K. Srivastava, J. Koutník, B. R. Steunebrink, and J. Schmidhuber, "LSTM: A search space odyssey," IEEE Transactions on Neural Networks and Learning Systems, vol. 28, no. 10, pp. 22222222222222222 2222,, 2016.
[13] M. Mitchell, S. Wu, A. Zaldivar, P. Barnes, L. Vasserman, B. Hutchinson, E. Spitzer, I. D. Raji, and T. Gebru, "Model cards for model reporting," " in Proceedings of the Conference on Fairness, Accountability, and Transparency (FAccT). ACM, 2019.
[14] T. M. Cover, Elements of information theory. John Wiley & Sons, 1999.
[15] B. Mason, R. Camilleri, S. Mukherjee, K. Jamieson, R. Nowak, and L. Jain, "Nearly optimal algorithms for level set estimation," arXiv preprint arXiv:2111.01768, 2021.
[16] F. Bachoc, T. Cesari, and S. Gerchinovitz. "The sample complexity of level set approximation." in Proceedings of International Conference on Artificial Intelligence and Statisties (AISTATS). PMLR, 2021.
[17] T. Hastie, R. Tibshirani, J. H. Friedman, and J. H. Friedman, The elements of statistical learning: data mining, inference, and prediction. Springer, 2009, vol. 2.
[18] Auer, M. Herbster, and M. K. Warmuth, "Exponentially many local minima for single neurons," in Advances in Neural Information Processing Systems (NeurIPS), 1995.
[19] S. Shalev-Shwariz and S. Ben-Davine Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
[20] C. Carathéodory, "Über den variabilitätsbereichh der fourier'schar konstanten von positiven harmonischen funktionen," Rendiconti Del Circolo Mutematico di Palermo (1884-1940), vol. 32, no. pp. 193-217, 1911.
[21] D. Wu, S.-T. Xia, and Wang, "Adversarial weight perturbation helps robust generalization," in Advances in Neural Information Processing Systems (NeurIPS), 2020.

---

[22] Y.-L. Tsai, C.-Y. Hsu, C.-M. Yu, and P.-.. Chen, "Formalizing generalization and adversarial robustness of neural networks weight perturbations." in Advances in Neural Information Processing Systems (NeurIPS), 2021.
[23] R. Blahut, "Computation of channel capacity and rate-distortion functions," IEEE Transactions on Information Theory, vol. 18, no. 4, pp. 460-473, 1972.
[24] S. Arimoto, "An algorithm for computing the capacity of arbitrary discrete memoryless channels," IEEE Transactions on Information Theory, vol. 18, no. I, pp. 14-20, 1972.
[25] M. Lichman, "UCI machine learning repository," 2013. [Online]. Available: http: Varchive.ics.ui.eddu/m
[26] J. Angwin, J. Larson, S. Mattu, and L. Kirchner, "Machine bias," ProPublica, 2016.
[27] S. J. Ingels, D. Pratt, D. R. Herget, L. J. Burns, J. A. Dever, R. Ottem, J. E. Rogers, Y. Jin, and S. Leinwand, "High school longitudinal study of 2009 (hsls: 09): Base-year data file documentation. nees 2011-328." National Center for Education Statistics, 2011.
[28] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, "A survey on bias and fairness in machine learning," ACM Computing Surveys (CSUR), vol. 54, no. 6, pp. 1-35, 2021.
[29] I. Csiszár, "Generalized projections for non-negative functions," in Proceedings of IEEE Inter- national Symposium on Information Theory (ISIT). 1995.
[30] A. Rényi, "On measures of entropy and information"" in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume Contributions to the Theory of Statistics. University of California Press, 1961.
[31] L. N. Vaserstein, "Markov processes over denumerable products of spaces, describing large systems of automata," " Problemy Peredachi Informatsüi vol. 5, no. 3, pp. 64-72, 1969.
[32] C. Rudin, "Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead." Nature Machine Intelligence, vol. 1, no. 5, pp. 206-215, 2019.
[33] I.. Hancox-Li, "Robustness in machine learning explanations: does it matter?" in Proceedings of the Conference on Fairness, Accountability, and Transparency (FAceT). ACM, 2020.
[34] A. D' A'Amuur, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, Deaton, J. Eisenstein, M. D. Hoffman el al., "Underspecification presents challenges for credibility in modern machine learning," arXiv preprint arXiv:2011.03399 2020.
[35] E. Black, M. Raghavan, and S. Barocas, "Model multiplicity: Opportunities, concerns, and solutions," in Proceedings of the Conference on Fairness, Accountability, and Transparency (FAceT). ACM, 2022.
[36] M. Pawelezyk, K. Broelemann, and G. Kasneci, "On counterfactual explanations under predic- tive multiplicity." in Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI). PMLR, 2020.
[37] A. Coston, A. Rambachan, and A. Chouldechova, "Characterizing fairness over the set of good models under selective labels," in Proceedings of International Conference on Machine Learning (ICML). PMLR, 2021.
[38] C. Dwork and C. Ilvento, "Individual fairness under composition," in Workshop on Fairness, Accountability, Transparency in Machine Learning (FAT/ML), 2018.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section and Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space limit, we provide the complete proofs and extra explanations in the SM.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] We include all
the code, data, and experimental details in the SM, along with GitHub repository.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] All provided in the SM.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Experiments are repeated times to compute the error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Provided in the SM.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cite thoroughly as we can.
(b) Did you mention the license of the assets? [Yes] Datasets, code, and models are publicly available.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We do use more datasets, but include more metrics on predictive multiplicity in the SM.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] Datasets are publicly available.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] The datasets do not contain any personally identifiable information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [No] Not applicable.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [No] Not applicable.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [No] Not applicable.
13


Reviews:
[{"review_id": "KNnb0vbaNrW", "reviewer": "Reviewer_9SyE", "summary": "The paper proposes ways to quantify “predictive multiplicity” (the extent to which equally accurate models disagree on individual predictions) for probabilistic classifiers. Specifically, it introduces a quantity called Rashomon Capacity and demonstrates its usage to report predictive multiplicity on different datasets and models.\n", "questions": "- I would like to see the authors strengthen the claim that we need to model predictive multiplicity at the score level (as opposed to the decision level).  \n- Some questions/comments regarding the definition of the Rashomon set: first, I would distinguish the true Rashomon set (computed w.r.t the true risk) and the empirical Rashomon set (computed w.r.t the empirical risk). E.g. I would denote them $R(H,\\epsilon)$ and $\\hat{R}(H, \\epsilon)$, respectively. More importantly, I don’t understand why the $\\epsilon$-level set is one sided - i.e., consists of all the classifiers in $H$ that have loss at most $\\epsilon$ as opposed to loss approximately $\\epsilon$ . I understand that for a specific choice of $\\epsilon$  (close to the loss of the ERM, as mentioned in the footnote) the two notions coincide, but (a) on a definitional level, it’s not clear to me why this is the definition, (b) in the experiments, a range of values of $\\epsilon$  is considered. I find this weird because if the best loss achievable in $H$ is 0.1 (e.g. by $h1$) then the Rashomon set w.r.t $\\epsilon = 0.2$ will naturally will have different predictions for some inputs (when $h1$ disagrees with the predictions of $h2$, a classifier with loss $0.2$), but it’s not clear to me that this falls under the “predictive multiplicity” phenomena (because $h1$ and $h2$ are clearly distinguishable). \n- In the definition of desirable properties for a metric $m(\\cdot)$, is it important that there is a classifier that assigns the one-hot vector $e_j$ as opposed to that the argmax is $j$?\n", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The problem of predictive multiplicity is important and timely.\n- The paper is written quite clearly.\n- The notion of Rashomon capacity is natural & well motivated.\n\nWeakenesses:\n\n- In terms of significance, I found the main argument for extending existing notions for binary classifiers to probabilistic classifiers not completely clear/satisfying. For example, it is mentioned that two scores can be very close (e.g. one example has score 0.49 for class 1, the other 0.51), and the existing methods would report multiplicity when there isn’t “really” any multiplicity. But doesn’t this depend on how the probabilistic classifier ends up being used? E.g. if the probabilistic classifier is the extracted probabilities from a Logistic regression model that will then be used to make binary decisions by thresholding the scores at 0.5, then I *should* treat 0.49 different from 0.51, no? I think this approach would make sense if binary decisions are obtained by randomizing according to the scores (e.g. classifying someone as 1 w.p 0.49), but I don’t think anyone uses ML models this way. \n- In terms of clarity: (1) The paper makes some bold claims which I felt were unjustified, since the claims themselves were not really made formal. For example, it is mentioned in several places that the proposed methodology “resolves” predictive multiplicity. But what does “resolve” even mean in this context? (2) In many places I felt like important details were omitted from the main text. For example, it is mentioned somewhat in passing, “Rashomon Capacity can be computed by standard procedures such as the Blahut-Arimoto algorithm”. The details of the algorithms are fine to omit, but a description of the assumptions is important - for example, it’s not clear to me if this assumes the Rashomon Set itself is already known, and what’s the computational complexity of this procedure. Similarly for the following result (Proposition 2): the statement claims the existence of at most c models, but can they also be found efficiently?\n- Finally, in terms of quality: The connection between the definitions and theoretical results to the experimental section was often unclear or lacking. For example, if I understand correctly, the proposed methods (e.g. sampling and AWP) are heuristics, and do not compute “the Rashomon capacity” but some approximation of it. I couldn’t really understand if sampling is a baseline and AWP is the “proposed” approach and whether the claim is that it is better (because the capacities are larger). Also I would have liked to see some semi-synthetic experiments (where the “real” Rashomon capacity is known or can be computed efficiently) so that the performance of the heuristics could be evaluated. E.g., for all we know, the Rashomon capacity is large for every input and we only observe it’s small on some inputs because of optimization issues. \n\nOverall I think the paper could have high impact, but at its current form I'm left with more questions than answers regarding many of the concepts used and the claims made, hence my current score.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HsSW6_4Mtg4", "reviewer": "Reviewer_1Yaa", "summary": "\nThis paper proposes a new metric to measure predictive multiplicity, called Rashomon Capacity (RC).  Unlike previous metrics, RC depends on the probability prediction instead of the discrete predictions. To compute RC, the authors propose to perform AWP, which is more efficient and random initializations.", "questions": "1. How is this paper related to model calibration? If the predicted probability is not calibrated, it seems pointless to use it in the definition/computation of RC.\n\n2. How to choose $\\epsilon$ in practice, or how to interpret it? Obviously, the value of RC is critically dependent on $\\epsilon$, but it seems like a quantity that's hard to interpret and it's thus not clear to me how to incorporate RC in the decision making process. This is not related to Section 2.3 in the Appendix. (I should mention I'm not generally familiar with how people use Rashomon sets either.)\n\n3. It is not clear whether this paper actually computes a good RC or not. There is a huge gap between AWP and sampling in Fig 3., but does AWP measures RC well or is it still underestimating? Can (and if so how) we tell?\n\n\n4. Following 1, why avoiding discrete/binary predictions and measuring Rashomon effect in a continuous space is a good thing? Let's say 1000 models all agree a sample $x_i$ has $0.5\\pm\\epsilon$ probability of being a cat (i.e. a hard example). If we consider the thresholded prediction, then maybe we get high predictive multiplicity due to the high variance around $0.5$. RC will say there is no divergence here really. It seems to me in practice this $x_i$, when used with any of these 1000 models, is still worth a lot of attention from the decision maker, so it should be considered as a high multiplicity input?", "limitations": "\nSee Weaknesses above. In general I think the motivation is the major limitation.\n\n\nMinor issues:\n1. typo @L145: \"Given\" -> \"given\"", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n\nThe problem of predictive multiplicity seems important. Proposition 2 makes reporting RC possible in practice. This paper is well-written and easy to follow. The introduction lays a good background of this area.\n\nWeaknesses:\n\n1. RC seems very expensive. Computing RC for one data point requires performing $c$ optimizations. While random initializations can be shared for different data samples and save time, from Fig 3 it is clearly (greatly) underestimating RC.\n\n2. The motivation seems weak, given the cost of computation and the unclear message it conveys without as specific $\\epsilon$. It could probably be used to measure model robustness, but I think that's just [31]? Can the authors briefly explain how RC will be used in a decision marking process? My question 4 is also related to motivation.\n\n3. As an evaluation metric, RC (AWP) requires running multiple optimizations. It seems like unlike metrics like accuracy, it is unclear how to compare RC across different $\\mathcal{H}$ (or even within the same $\\mathcal{H}$ but with different optimization methods) if the optimization is not finding global optima. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2eNEKn9_JzE", "reviewer": "Reviewer_hCae", "summary": "The paper is focused on predictive multiplicity. Predictive multiplicity is when all the models in the Rashomon set (set of models with similar performance statistics on the test set) have different predictions for the same input. The goal is to define a new metric (Rashomon Capacity) for predictive multiplicity that considers the soft probabilistic outputs of the classifier models rather than the one-hot class predictions. This helps to distinguish Rashomon sets where different predictions are a result of highly different predicted probabilities vs  sets where the predictions are different but the come from similar soft outputs. The general idea is to find a prior distribution over members of the Rashomon set such that the divergence from the \"center of gravity\" of predictions is maximize. The paper continues by computing and approximating the Rashomon capacity metric on various real-world datasets using a several algorithms. ", "questions": "- What is the theoretical guarantee for the upper bound on errors of the two AWP and sampling algorithms?\n- One approach to address the issue seems to be using an ensemble of models. How does the cardinality of Rashomon set scale vs the number of models in the ensembles?\n- Another approach to address the issue is to use several metrics rather than cross-entropy loss (fairness metrics, etc). How does the cardinality of Rashomon set change with this approach?", "limitations": "* The main algorithm the results in the finding the largest Rashomon Capacity (AWP) is computationally expensive.\n\n------After rebuttal-----\n\nI thank the authors for providing a comprehensive rebuttal. I will take their response to my review and other reviews into consideration throughout the decision process.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* The target problem of the paper is important and well-motivated.\n* The paper is well-organized and the writing is smooth. The paper would be easier to understand with a step-by-step algorithm box either in the main text rather than referring to the algorithm's name and the provided code.\n* The experimental section focuses on useful data set examples but no case study has been discussed to have a better understanding of how Rashomon capacity can be crucial in real-world scenarios. It would be very useful to have an example.\n* The paper seems to be an extension of existing work. In order to prove its contribution, there needs to be an either empirical or theoretical comparison with existing work. in the experimental section no comparative analysis is performed to empirically showcase the advantage of using Rashomon capacity versus ambiguity and discrepancy.\n* It would be more comprehensive if the greedy algorithm's performance is compared for the other two datasets (CIFAR10 and adult income).\n* All in all, the paper does a decent job in motivating and explaining the Rashomon Capacity but does not provide enough empirical evidence on its advantage and utility in order to satisfy the paper's motivation.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept