Counterfactual Inference of Second Opinions

Automated decision support systems that are able to infer second opinions from experts can potentially facilitate a more efficient allocation of resources; they can help decide when and from whom to seek a second opinion. In this paper, we look at the design of this type of support systems from the perspective of counterfactual inference. We focus on a multiclass classification setting and first show that, if experts make predictions on their own, the underlying causal mechanism generating their predictions needs to satisfy a desirable set invariant property. Further, we show that, for any causal mechanism satisfying this property, there exists an equivalent mechanism where the predictions by each expert are generated by independent sub-mechanisms governed by a common noise. This motivates the design of a set invariant Gumbel-Max structural causal model where the structure of the noise governing the sub-mechanisms underpinning the model depends on an intuitive notion of similarity between experts which can be estimated from data. Experiments on both synthetic and real data show that our model can be used to infer second opinions more accurately than its non-causal counterpart.


Introduction
In decision making under uncertainty, seeking opinions from multiple human experts tends to improve the overall quality of the decisions. For example, in medicine, second opinions have been shown valuable for establishing diagnoses and initiating treatment [Burger et al., 2020] as well as reducing the number of unnecessary procedures [Leape, 1989, Althabe et al., 2004. In machine learning, ground truth labels are determined by carefully aggregating multiple noisy labels provided by different experts [Zhang et al., 2016] and inconsistencies between these noisy labels help developing more robust models [Peterson et al., 2019]. Unfortunately, the timeliness and quality of the decisions is often compromised due to a shortage of experts, which prevents each decision to be informed by multiple experts' opinions.
In this context, we argue that the development of automated decision support systems that, given an expert's opinion on a decision instance and a set of features, are able to infer other experts' opinions will enable a more efficient allocation of resources. On the one hand, these systems could prevent (prioritize) seeking other experts' opinions when they are unlikely (likely) to bring new perspectives. On the other hand, these systems could also help identify those experts whose opinion is most likely to disagree with that of the expert sought first. Here, it is worth noting that several studies have also argued that decision support systems that identify disagreement between experts may help identify when a decision instance would benefit most from a second opinion [Raghu et al., 2019, Lim et al., 2021. However, these studies do not focus on inferring other experts' opinions given an expert's opinion on a decision instance and a set of features, as we do in our work.
More specifically, we consider a multiclass classification setting where, for each instance, experts form their opinions on their own (i.e., without communicating). 1 In this setting, each expert's opinion reduces to a label prediction. Then, our goal is to design decision support systems that, given an expert's prediction on 1. Second Opinions "severe concussion" 2. Consensus (e.g. majority) (b) Use case Figure 1: An example of a training dataset and use case of our decision support system on a medical application. In panel (a), for each patient, multiple doctors assess the severity of a concussion on the basis of a set of features. In panel (b), given a doctor's assessment of the severity of a concussion and a set of features, our decision support system infers other fellow doctors' assessment of the severity of the concussion.
an instance with a set of features, are able to infer other experts' predictions about the same instance, as illustrated in Figure 1. To this end, one could resort to standard supervised learning. Under this perspective, for each instance, the given expert's prediction would be just an additional feature about the instance. Unfortunately, this would limit the applicability of the resulting supervised learning model to the unrealistic scenario where, for each possible pair of experts, we observe a sizeable number of instances where both experts made a prediction. To circumvent this limitation, we look at the design of the above systems from the perspective of counterfactual inference.
Our contributions. We first show that, if experts form their opinions for each instance on their own, the underlying causal mechanism generating the experts' predictions needs to satisfy a certain set invariant property. Moreover, we further show that any structural causal model satisfying the above set invariant property (in short, any SI-SCM) also satisfies two additional desirable properties: (i) there exists an equivalent SI-SCM where each expert's predictions are generated by independent sub-mechanisms governed by a common (multidimensional) noise; (ii) given an expert's prediction on an instance with a set of features, the conditional interventional distribution and the counterfactual distribution of another expert's predictions entailed by the SI-SCM are identical 2 . These properties suggest the following natural strategy to design and train SI-SCM based decision support systems. In a first step, we can use interventional data about each expert-her predictions on a set of instances-to determine the structure of each sub-mechanism separately. One can view this step as multiple independent supervised learning problems, one per expert. In a second step, we can use a small amount of interventional data about multiple experts making predictions about a joint set of instances to characterize similarity across experts and factorize the noise governing the sub-mechanisms into a set of noise components. In a way, in this second step, we are adding a wrapper to the supervised learning models characterizing each expert's sub-mechanism to be able to make counterfactual predictions about second opinions.
To implement the above strategy, we introduce a specific class of SI-SCMs based on the Gumbel-Max structural causal model [Oberst and Sontag, 2019] (in short, Gumbel-Max SI-SCM) and characterize similarity across pairs of experts using the concept of counterfactual stability 3 . In the Gumbel-Max SI-SCM, each expert's submechanism is governed by a Gumbel-Max noise variable and submechanisms of similar experts may be governed by the same noise variable. Further, we show that the problem of uniquely associating each of these noise variables with disjoint sets of mutually similar experts given data can be formulated as a known clique partioning problem, an NP-hard problem [Grötschel andWakabayashi, 1989, 1990], and propose a simple randomized greedy algorithm with good performance.
Finally, we experiment with synthetic and real data comprising of 20,426 expert predictions over 1,560 natural images. The results on synthetic data show that our randomized greedy algorithm can successfully recover the disjoint sets of mutually similar experts underpinning a specific Gumbel-Max SI-SCM from data. The results on real data show that the (counterfactual) predictions provided by the Gumbel-Max SI-SCM are more accurate than those provided by its non-causal counterpart.
Further related work. Predictions by different experts have been typically studied separately, i.e., without conditioning on an observed prediction by a given expert [Dawid and Skene, 1979, Welinder and Perona, 2010, Guan et al., 2018, Kerrigan et al., 2021, Straitouri et al., 2022. One could think of the observed prediction just as an additional feature when inferring other experts' predictions, however, this would limit the applicability of existing inference methods to scenarios where, for each pair of experts, we observe a sizeable number of instances where both experts made a prediction, as discussed previously. More broadly, our work is not the first to use counterfactual reasoning in expert prediction [Bica et al., 2020]. However, previous work has used counterfactual reasoning to quantify an expert's preference over counterfactual outcomes rather than to infer other experts' predictions conditioning on a given expert's prediction.
Counterfactual inference has a long and rich history [Imbens and Rubin, 2015]. However, it has mostly focused on estimating quantities related to the interventional distribution of interest such as, e.g., the conditional average treatment effect (CATE). A few notable exceptions are by Oberst and Sontag [2019] and Tsirtsis et al. [2021], which use the Gumbel-Max SCM to reason about counterfactual distributions in Markov decision processes (MDPs), and by Lorberbom et al. [2021], which introduces a parameterized family of causal mechanisms that generalize the Gumbel-Max SCM and are specifically-tuned to a distribution of observations and interventions of interest. However, the Gumbel-Max structural causal model has not been used previously to reason about counterfactual expert predictions.

Preliminaries
Given a set of random variables 4 X = {X 1 , . . . X n }, a structural causal model (SCM) M defines a complete data-generating process via a collection of assignments where PA i ⊆ X \ X i are the direct causes of X i , F = {f 1 , . . . , f n } are deterministic causal mechanisms, U = {U 1 , . . . , U n } are jointly independent noise random variables, and P (U) denotes the (prior) distribution of the noise variables. Here, note that the noise variables U are the only source of stochasticity and, given an observational distribution P (X), there always exists a distribution P (U) and mechanisms F so that P = P M , where P M is the distribution entailed by M.
Two SCMs M andM over variables X and U, with noise distribution P (U) and mechanisms F andF respectively, are equivalent if, for all i ∈ [n], it holds that for any realization PA i = pa i and P (U)-almost every u i . 5 3 Counterfactual stability is, in general, an axiomatic requirement imposed to counterfactual distributions [Oberst and Sontag, 2019]. However, in SI-SCMs, it is verifiable from interventional data due to (ii), as shown in Theorem 7. 4 We denote random variables with capital letters and realizations of random variables with lower case letters. 5 P (U)-almost everywhere means that the set of noise realizations U for which the property does not hold has probability zero under the distribution P (U), i.e., P (U ∈ U ) = 0. Given a SCM M, an atomic intervention I corresponds to assigning a fixed value to a variable. For example, let I = do[X i = x] be the intervention that assigns value x to variable X i , then the intervened SCM M I does not assign the value of X i according to f i (PA i , U i ) but assign it to a fixed value x. The interventional distribution entailed by the intervened SCM is denoted P M ; I . Furthermore, given the (possibly partial) observation X = x, we can also define a modified SCM M X=x where the noise variables U are distributed according to the posterior distribution P (U | X = x). Then, we can view a counterfactual statement as an intervention I in the SCM M X=x and denote the counterfactual distribution entailed by the counterfactual SCM M I X=x as P M | X=x ; I . The Gumbel-Max SCM is a specific class of SCM in which the causal mechanism for a random categorical variable V is defined as and each noise variable U j ∼ Gumbel(0, 1). Here, note that the interventional distribution P M ; do[PA=pa] (V ) entailed by a Gumbel-Max SCM M is exactly P (V | PA = pa).

Counterfactual Inference of Second Opinions
We consider a multi-class classification task where, for each instance, a human expert h ⊆ H makes a label prediction y h ∈ Y = {1, . . . , k} based on multiple sources of information, which are (imperfectly) summarized by a feature vector x ∈ X . Here, we assume that experts make predictions on their own (i.e., without communicating with each other) and the assignment of experts to instances is independent of the identity of the instances and their feature vectors. Then, our goal is to design an automated decision support system that, given a prediction y h from an expert h about an instance summarized by a feature vector x, is able to infer what prediction y h another expert h = h would have made about the same instance if she had been asked. Here, note that two different instances may be (imperfectly) summarized by the same feature vector x, however, we are interested in a counterfactual prediction about the same instance. Our starting point is to view the above counterfactual statement as an intervention in a particular counterfactual SCM. More specifically, let M be a SCM defined by the assignments where U , V and W are (multidimensional) independent noise variables, f Y , f Z and f X are given deterministic causal mechanisms (or functions), and Y = (Y h ) h∈Z are the predictions by a set of human experts Z ⊆ H. Then, we can express the above counterfactual statement as an intervention I = do[Z = {h }] in the counterfactual SCM M X=x,Z={h},Y =y h and, to infer the label prediction y h , we just need to resort to the counterfactual distribution P M | X=x,Z={h},Y =y h ; do[Z={h }] (Y ). At this point, one may argue that, even if we find a noise distribution P (U ) and a function f Y under which the conditional distribution P M (Y | X) is a good fit for observed historical predictions by experts, we would be unable to validate how accurate our counterfactual label predictions are using data. In general, this is true since counterfactual reasoning lies within level three in the "ladder of causation" [Pearl, 2009]. In this context, previous work resorts instead to axiomatic assumptions about the causal mechanism of the world [Oberst and Sontag, 2019, Tsirtsis et al., 2021, Noorbakhsh and Rodriguez, 2021. In our setting, this would reduce to specifying how differences across experts may have lead to a different prediction while holding "everything else" fixed. However, in what follows, we will show that, if experts do not communicate with each other, the above SCM satisfies a set invariance property that surprisingly implies that the above counterfactual distribution coincides with an interventional conditional distribution. This enables a data-driven design and validation of our SCM based decision support system.

Relating the Counterfactual and Interventional Worlds
To build some intuition on the reasons why, if experts do not communicate, certain type of counterfactual and interventional distributions are identical, we start with a simple example. Let h, h ∈ H be two different experts and consider the following two questions: 1. Both experts have made a label prediction about an instance (i.e., Z = {h, h }) but we only observe the prediction Y h = c made by h, what is the prediction made by h ? 2. One of the experts has made a label prediction Y h = c about an instance (i.e., Z = {h}) and we observe it, what would the prediction made by h be if she had made a prediction?
The first question is of conditional nature while the second is a counterfactual one. In general, the answer to both questions may differ, for example, if experts influence each other's predictions by sharing and discussing their opinions in the first case. However, if experts do not communicate, the answer to both questions should be identical. More formally, the following conditional interventional distribution and counterfactual distribution of the expert should be equal: More generally, we will now show that, if each expert forms their opinion on their own, the above equality is a direct consequence of a set invariance property satisfied by the SCM defined in Eq. (2).
Set Invariant SCMs (SI-SCMs). If experts do not communicate before making a prediction and hence are unaware and unaffected of other experts' opinions, the mechanism f Y has a set invariant value over expansions (supersets) of Z. For example, consider one single expert h has made a prediction f Y (x, {h}, u) = c about a specific instance. Then, one can conclude that, if instead of a single expert, a set of experts ζ ⊆ H such that h ∈ ζ would have made predictions about the same instance (i.e., x and u does not change), expert h would have made the same prediction, i.e., (f Y (x, ζ, u)) h = c. More formally, we define the set invariance property as follows: A SCM M with such a mechanism is set invariant for Y.
A set-invariant SCM (SI-SCM) for Y can be constructed by expressing the causal mechanism f Y with submechanisms f Y h governed by a common noise variable: 6 In fact, the following theorem shows that the class of SCMs with separate submechanisms for Y h and a shared noise variable U is not only a subclass but completely defines the class of SI-SCMs for Y. Thus, any correlation between experts' predictions is caused by the common noise and features but not the causal mechanism.
Theorem 3. For any SI-SCM M, there exists an equivalent SI- Here, we would like to emphasize that, if the mechanism f Y of an SCM is not explicitly decoupled into submechanisms governed by the same noise, it may be challenging to check whether an arbitrary SCM is set invariant. For arbitrary SCMs, Theorem 2 can not be applied directly and Theorem 3 does not tell us how to verify that an equivalent SCM exists. However, it tells us that the mechanism of a set invariant SCM can be decoupled and simplified. It would be interesting to develop methods to check for set invariance for arbitrary SCMs in future work.
6 All proofs can be found in Appendix A Equality between the counterfactual distribution and the conditional interventional distribution. Returning to our simple motivational example, note that, if a SCM is set invariant, the answers to the counterfactual and the conditional questions 1 and 2 are the same as long as the noise u ∼ P (U | X = x, Y h = c) is the same. In particular, for question 1, the answer is u), and since f Y is set invariant, both answers are equal. More generally, for arbitrary sets of experts, we can easily conclude that equality holds if and only if f Y is set invariant.
Next, to show that, if a SCM is set invariant, then the equality of distributions in Eq.
(3) holds, we first present a more general theorem that states that, if we expand the set of experts who make predictions, the corresponding interventional distribution of Y does not change: Theorem 4. Let SCM M be set invariant for Y. Then, for any ζ, ζ ∈ H such that ζ ⊆ ζ , it holds that for any y ∈ Y |ζ| where (Y) ζ denotes the predictions by the experts in the subset ζ ⊆ ζ .
The above theorem is straight forward to show using that, due to the set invariance property, the prediction values of mechanism f Y for (x, ζ, u) are equal to the values for (x, ζ , u) for experts in ζ and, due to the independence between the noise and the intervention, the noise distribution does not change. A direct conclusion is that, no matter how many experts make predictions, the conditional interventional distribution of a single expert's prediction does not change, as formalized by the following corollary: Similarly, we can derive the desired equality between the counterfactual distribution and the conditional interventional distribution by using the set invariance of mechanism f Y and the fact that the noise distribution changes equally in both scenarios. More formally, we have the following corollary: Corollary 2. Let SCM M be set invariant for Y. Then, for any h, h ∈ H and ζ ⊆ H such that h, h ∈ ζ, it holds that for any x ∈ X and c ∈ Y.
Remark. While we have introduced the notion of set invariance for SCMs in the context of inferring second opinions, we believe it may be of independent interest since, generally speaking, it allows us to identify counterfactual distributions from interventional data.

Characterizing Mutually Similar Experts
Given a SI-SCM model M where each expert's predictions Y h are generated by a sub-mechanism f Y h , our goal in this section is to characterize mutually similar experts. Later on, this will help us factorize the noise U governing the sub-mechanisms f Y h underpinning the model into a set of independent noise components and uniquely associate each of these noise components with disjoint sets of mutually similar experts given data.
To this end, we first start by characterizing similarity between a pair of experts h, h ∈ H. To this end, we resort to the recently introduced notion of counterfactual stability [Oberst and Sontag, 2019]. More specifically, we argue that two experts h and h are similar if M satisfies counterfactual stability for h, h with respect to Y.
Definition 5 (Counterfactual stability). A SCM M satisfies counterfactual stability for h, h with respect to Y if, for all ζ, ζ ⊆ H such that h ∈ ζ and h ∈ ζ and for all c = c, the condition For example, consider a scenario where a doctor needs to decide what treatment option-surgery (Y = 0), radiation (Y = 1) or chemotherapy (Y = 2)-will be more beneficial for a patient with a tumor, imperfectly summarized by a feature vector x. Assume doctor h decides the most beneficial option is surgery, i.e., Y h = 0, and we know that, for patients with similar x, doctor h is generally more likely to operate and less likely to resort to therapy than doctor h. Then, if doctors h and h are similar, as defined in Definition 5, we expect doctor h would have also decided the most beneficial option is surgery for the given patient, if consulted, i.e., Y h = 0. Here, whenever two doctors h and h are not similar, one could argue that it is because they weigh any (hidden) factor specific to the patient at hand differently 7 .
Unfortunately, in general, we cannot use data to verify if two experts h and h are similar. This is because our notion of similarity relies on a counterfactual distribution, P M | Y h =c ; do [Z=ζ ] , and counterfactual reasoning lies within level three in the "ladder of causation" [Pearl, 2009]. However, we will now define a notion of conditional stability that is verifiable using interventional data and, in the case of SI-SCMs, is both a sufficient and necessary condition for counterfactual stability-if conditional stability holds, we can conclude that two experts are similar.
Definition 6 (Conditional stability). A SCM M satisfies conditional stability for two experts h, h ∈ H with respect to Y if, for all ζ ⊆ H such that h, h ∈ ζ and for all c = c, the condition Here, note that, for SI-SCMs, we only need to verify the condition in Eq. (4) for the sets ζ = {h} and ζ = {h } because no matter how many experts make predictions, the conditional interventional distributions in Eq. (4) do not change, as shown in Corollary 1. Then, the following Theorem formalizes the equivalence between conditional and counterfactual stability: Theorem 7. Let SCM M be set invariant for Y. Then, M satisfies counterfactual stability for h, h ∈ H with respect to Y iff it satisfies conditional stability.
Once we have a notion of similarity between pairs of experts that we can verify from data, we can characterize groups of mutually similar experts. In this context, it will be useful to introduce the following notion of pairwise counterfactual stability (in short, PCS), which extends counterfactual stability to groups of experts ζ ⊆ H of arbitrary size.
Definition 8 (Pairwise Counterfactual Stability). A SCM M satisfies pairwise counterfactual stability for a group of experts ζ ⊆ H with respect to Y if it satisfies counterfactual stability for any h, h ∈ ζ.
Similarly as in the case with a pair of experts, one can also define pairwise conditional stability and it immediately follows from Theorem 7 that, for SI-SCM, pairwise conditional and counterfactual stability are equivalent, as formalized by the following Corollary.  Given a set of experts H, the Gumbel-Max SI-SCM partitions H into disjoint sets of experts Ψ = {ψ} ψ∈Ψ , as defined in Section 5, and associate all experts within each set to the same multidimensional noise variable. More formally, the Gumbel-Max SI-SCM is defined as follows: Definition 9 (Gumbel-Max SI-SCM). The Gumbel-Max SI-SCM M(Ψ) is a specific class of SCM in which the causal mechanism for Y is defined as where ψ(h) ∈ Ψ denotes the subgroup expert h belongs to and each noise variable U ψ(h),c ∼ Gumbel(0, 1). By definition, the Gumbel-Max SI-SCM M(Ψ) is set invariant for Y and, for any ζ ⊆ H and h ∈ ζ, it holds that P M(Ψ);do [Z=ζ] (Y h | X) = P (Y h | X). Moreover, all experts within each group ψ ∈ Ψ are mutually similar, as formalized by the following Theorem: Theorem 10. The Gumbel-Max SI-SCM M(Ψ) satisfies pairwise counterfactual stability (PCS) for each group ψ ∈ Ψ with respect to Y.
Finally, note that, for Ψ = H, the Gumbel-Max SI-SCM reduces to the original Gumbel-Max SCM defined in Eq. 1. Therefore, one can view the Gumbel-Max SI-SCM as a generalization of the original Gumbel-Max SCM where, instead of a single multidimensional noise variable U for all h ∈ H, one has several noise variables U ψ , one per group.
Estimating counterfactual distributions. Given a prediction Y h = c by an expert h, we can compute an unbiased finite sample Monte-Carlo estimator of the counterfactual distribution for the prediction Y h of another expert h = h, i.e., P M(Ψ) | X=x,Z={h},Y =y h ; do[Z={h }] (Y ), as follows: where u 1 , . . . , u T are samples from the posterior distribution P M(Ψ) | X=x,Z={h},Y =y h ; do[Z={h }] (U ψ(h ) ) of the noise variable U ψ(h ) . Here, we can use an efficient procedure to sample from the above noise posterior distribution, described elsewhere Sontag, 2019, Maddison et al., 2015]. Moreover, note that, if h / ∈ ψ(h ), the posterior distribution coincides with the prior P M(Ψ) (U ψ(h ) ). We summarized the sampling procedure is depicted in Figure 2.
Partitioning experts into mutually similar groups. In the Gumbel-Max SI-SCM M(Ψ), for each expert h ∈ H, we can estimate the conditional distribution P (Y h | X) using any machine learning model trained using historical predictions made by the expert h. However, to fully define M(Ψ), we need to partition the set of experts H into disjoint sets of experts Ψ given a small amount of historical data about multiple experts making predictions about a joint set of instances. To this end, we proceed as follows.
First, we look for violations of the conditional stability condition throughout the historical data. Whenever there exists a sample for which the predictions by two different experts h and h violate conditional stability 8 , we conclude that h and h cannot belong to the same group ψ. Further, we also conclude that any pair of experts whose predictions did not violate conditional stability and were at least once observed for the same sample can be similar. However, since conditional stability is not a transitive property, there may be multiple valid partitions P = {Ψ} of the experts into disjoint sets that are consistent with the above conclusions. To decide among them, we would like to pick the partition Ψ ∈ P under which the counterfactual distributions P M(Ψ) | X=x,Z={h},Y =y h ; do[Z={h }] (Y ) provide the best goodness of fit. More formally, we would like to solve the following minimization problem: where L(M(·), h , h) denotes an average (empirical) loss whenever we observe Y h and infer the label prediction Y h using the counterfactual distribution P M(·) | X=x,Z={h},Y =y h ; do[Z={h }] (Y ). Here, we measure goodness of fit in terms of average loss reduction with respect to the counterfactual distributions entailed by the causal model M(H) because this will allow us to reduce the number of pairs (h, h ) we need to consider. The step-wise approach for obtaining Ψ is summarized in Figure 3. Next, we formulate the above problem as a known clique partitioning problem [Grötschel andWakabayashi, 1989, 1990]. More specifically, let G = (H, E) be an undirected graph where, if {h, h } ∈ E, then h and h can be similar, as concluded from the data. Then, it readily follows that finding a partition Ψ of H is equivalent to finding a clique cover for G 9 . Now, let the weight w(h, h ) of each edge {h, h } ∈ E be given by: Then, we can rewrite the minimization problem defined in Eq. 6 as: subject to Ψ is a clique cover for G, where note that we only need to consider pairs of experts h, h ∈ ψ because, otherwise, w(h, h ) = 0 since the corresponding counterfactual distributions entailed by M(Ψ) and M(H) coincide. The minimization problem given by Eq. (7) is a known clique partitioning problem (CPP) 10 , for which the decision problem of CPP for arbitrary weights is NP-Hard [Grötschel andWakabayashi, 1989, 1990]. However, we found that a simple randomized greedy algorithm works well in our setting, as shown in Figure 6 in Appendix C. Refer to Appendix B for more details about the algorithm. 9 Ψ is a clique cover for G iff Ψ is a partition of H, i.e., ψ∈Ψ ψ = H and ψ ∩ ψ = ∅ for all ψ, ψ ∈ Ψ, and vertices in ψ ∈ Ψ form a clique in G.
10 In most of the literature, the problem is defined for complete graphs. However, for arbitrary graphs, one can simply include the missing edges and assign positive infinite weights so that they are not included in a solution [Brimberg et al., 2017]

Experiments on Real Data
In this section, we compare the performance of the proposed Gumbel-Max SI-SCM at inferring second opinions against several competitive baselines using a dataset with real expert predictions over natural images. Appendix C contains additional experiments on synthetic data where we assess the performance of Algorithm 1 at recovering groups of mutually similar experts on synthetic data. 11 Data description and experimental setup. We experiment with the dataset CIFAR-10H [Peterson et al., 2019], which contains 10,000 images taken from the test set of the standard dataset CIFAR-10 [Krizhevsky et al., 2009]. Each of these images belongs to n = 10 classes and contains label predictions from approximately 50 human annotators. In total, the images are annotated by 2,571 different human annotators (from now on, experts). 12 Since the classification task is relatively easy for humans, there are many images (∼35%) in which there is full agreement between experts-all experts make the same label prediction. Here, motivated by the empirical observation that, in medical diagnosis, there is typically a 20% per-instance disagreement among experts [Van Such et al., 2017, Elmore et al., 2015, we filter out the above mentioned images in which there is full agreement. Moreover, we split the remaining images into two disjoint sets at random-a training set and a test set-and filter out data from any expert who made less than 130 and 20 predictions in training and test set, respectively, and whose predicted labels in the training data do not cover all class labels. After these preprocessing steps, the resulting training and test sets contain 1,257 and 303 images, respectively, annotated by |H| = 114 experts, where each image in the training and test set is annotated by at least two experts. To find the groups of mutually similar experts underpinning our Gumbel-Max SI-SCM, we run Algorithm 1 on the training set. Within the Gumbel-Max SI-SCM, we estimate the conditional distribution P M ; do [Z={h}] (Y h | X) for each expert h using a Gaussian Naive Bayes model (GNB) trained using also the training set (one GNB per expert) 13 . Each GNB model uses 20 dimensional feature vectors computed by running PCA on a 512 dimensional normalized feature vector extracted using VGG19 [Simonyan and Zisserman, 2014]. Both during training and test, given an observed label prediction Y h by an expert h, we infer the prediction Y h by another expert h using the most likely label under (an estimate of) the corresponding counterfactual distribution. To estimate each counterfactual distribution, we use T = 1,000 samples from the noise posterior distribution.
Baselines and evaluation metrics. We compare the performance of our trained Gumbel-Max SI-SCM with two baselines (see also Figure 7 in Appendix D): -The "GNB " baseline uses only the same Gaussian Naive Bayes models (GNB), one per expert, used by our trained Gumbel-Max SI-SCM. More specifically, given an observed label prediction Y h by an expert h, it infers the prediction Y h by another expert h using the most likely label under the estimate of the conditional distribution P M ; do[Z={h }] (Y h | X) given by the corresponding GNB.
-The "GNB + CNB " baseline uses the same Gaussian Naive Bayes models (GNB), one per expert, used by our trained Gumbel-Max SI-SCM and a Categorical Naive Bayes (CNB) model, one per expert, that estimates 11 To facilitate research in this area, we release an open-source implementation of our code at https://github.com/Networks-Learning/cfact-inference-second-opinions. 12 The dataset CIFAR-10H is one of the only publicly available datasets containing a relatively large number of samples with multiple label predictions by different experts per sample, necessary to train the proposed Gumbel-Max SI-SCM. However, since our methodology and theoretical results are rather general, our model may also be useful in other applications. 13 In the CIFAR-10H dataset, experts are assigned to images (presumably) at random. Therefore, it holds that P M ; do [Z={h}] (Y h | X) = P (Y h | X, Z = {h}) and we can use observational data to estimate the interventional conditional distribution P M ; do [Z={h}] (Y h | X).  Figure 4: Per-expert test accuracy achieved by our model and both baselines on the CIFAR-10H dataset. In each panel, the y-axis always measures the per-expert test accuracy achieved by our method and the x-axis measures the per-expert accuracy achieved by one of the baselines. For each cell, the darkness is proportional to the number of experts with the corresponding test accuracies.
. 14 More specifically, given an observed label prediction Y h by an expert h, it infers the prediction Y h by another expert h using the most likely label under the product of distributions , as estimated by the corresponding GNB (first term) and CNB (second term).
To compare the performance of our trained Gumbel-Max SI-SCM and both baselines, for each sample in the test set, we pick each of the corresponding expert label predictions Y h as the observed prediction in turn and infer the value of the other predictions Y h . Here, we compute the overall accuracy as well as the per-expert accuracy and distinguish among three scenarios: (i) h, h ∈ H; (ii) h, h ∈ ψ; and, (iii) h ∈ ψ, h ∈ ψ , ψ = ψ .

Results.
We start by reporting that, during the training of our Gumbel-Max SI-SCM, Algorithm 1 found 352 violations of the conditional stability condition between pairs of experts and partitioned the experts into fifteen disjoint groups of mutually similar experts, where seven of these groups were singletons. Refer to Appendix D for more details regarding the groups identified by Algorithm 1.
Next, we report the overall accuracy achieved by our model and the baselines in Table 1. We find that, in general (h, h ∈ H), our model infers the expert predictions more accurately than both baselines and this competitive advantage comes from instances in which the observed prediction is by an expert h who belongs to the same group of mutually similar experts as the expert h whose prediction we infer (h, h ∈ ψ). In fact, the GNB+CNB baseline is more accurate whenever both experts h and h do not belong to the same group (h ∈ ψ, h ∈ ψ , ψ = ψ ). Moreover, we also find that the GNB+CNB baseline infers the expert predictions more accurately whenever both experts belong to the same group of mutually similar experts identified by Algorithm 1. In Appendix D, we report the confusion matrix of the above counterfactual predictions.
Finally, we report the per-expert h accuracy achieved by our model and both baselines in Figure 4. 15 The results show that, in general (h, h ∈ H), our model infers the expert predictions more accurately than the baselines for a majority of the experts (103 and 89, out of 114, compared to GNB and GNB+CNB, respectively). Moreover, if we restrict our attention to observed label predictions by experts h belonging to the same group of mutually similar experts as the expert h whose prediction we infer (h, h ∈ ψ), our model infers the expert prediction more accurately for almost all experts h (100 and 101, out of 103, compared to GNB and GNB+CNB, respectively). Additionally, Figure 5 shows that, for most experts (87 out of 103), the GNB+CNB baseline infers the expert predictions Y h more accurately if the observed prediction Y h is by an expert h belonging to the same group of mutually similar experts as the expert h (h, h ∈ ψ) than if it is by an expert h belonging to a different group (h ∈ ψ, h ∈ ψ , ψ = ψ ).

Conclusion
In this work, we have addressed the problem of inferring second opinions by experts from the perspective of counterfactual inference. We have focused on a multiclass classification setting and showed that, if experts make predictions on their own, the underlying causal mechanism generating their predictions needs to satisfy a desirable set invariant property. Moreover, we have introduced the set invariant Gumbel-Max structural causal model, a new class of structural causal model whose structure and counterfactual predictions about second opinions by experts can be validated using interventional data.
Our work opens up many interesting avenues for future work. For example, we assume experts do not communicate before forming their opinion. Although this assumption may be satisfied in some real-world applications, it would be interesting to relax it. Moreover, we have validated our model using a single real dataset. It would be valuable to validate our model using additional datasets from other applications. Finally, it would be important to carry out user studies in which the inferred second opinions provided by our model are shared with domain experts (e.g., medical doctors).

A Proofs
Proof of Theorem 2. Let ζ ⊆ ζ ⊆ H and both non-empty. Then, for any x ∈ X , u ∈ U, we have that (f (x, ζ , u) Proof of Theorem 3. Let M be constructed from M by changing causal mechanism f with f . To prove equivalence of M and M , we only need to show that, for any u ∈ U, x ∈ X , ζ ∈ P(H) \ ∅, it holds that as only the causal mechanism was altered in the construction of M . Let h ∈ ζ be an arbitrary expert, then where the last equality holds because f is set invariant. Thus, f (x, ζ, u) = f (x, ζ, u) for all x ∈ X , ζ ∈ H, u ∈ U.
Proof of Theorem 4. For clarity, we explicitly write Y Z={h } and Y Z=ζ to better distinguish the two interventional outcomes. For discrete probability distribution P (U ) the right probability is given by whereas the left is given by Because f is a set invariant mechanism over Z, (f (x, ζ , u)) ζ = f (x, ζ, u), thus, The proof is analogous for the continuous probability distributions P (U ).
Proof of Corollary 1. Choose ζ = {h} in Theorem 4 and note that abusing notation Y Z=ζ is in this case equivalent to Y h .
Proof of Corollary 2. Using the definition of counterfactual distributions, the proof is analogous to the proof of Theorem 4 but using the posterior distribution P ( For all c ∈ Y, by definition, we have that Using that M is set invariant we get that Thus, Eq. (9) is equal to process on the remaining graph until no vertices are left. For the current clique ψ the set of vertices that can be added, called candidate set, consists of vertices that have edges to all the vertices in ψ so that the sum these edge weights is non-positive. The expert with minimum sum is added next to the clique, and the candidate set is updated. The updated candidate set is a subset of the previous set, thus, the sum of edge weights of a vertex connected to the updated clique can be computed in constant time by considering the previous value and the weight of the edge to the newly added vertex. If no edge exists, the vertex can be removed from the candidate set. Algorithm 1 can thus be implemented in O(|E|).
Algorithm 1 Greedy Algorithm for the Clique Partitioning Problem, N (ψ) denotes the set of vertices not in ψ with edges to all vertices in ψ We note that, since the algorithm minimizes the sum of weights for each clique sequentially, it's performance in recovering a partition minimizing the overall sum depends on the sequence of sampled vertices which we start each clique from. To stabilize the algorithm's performance, one can rerun the algorithm a few times and choose among the returned partitions the one minimizing the overall sum of edge weights between vertices in the same set (see objective function in optimization problem 7). In the experiments on real (synthetic) data, we run Algorithm 1 10 (5) times.

C Experiments on Synthetic Data
In this section, we assess the performance of Algorithm 1 at recovering the groups of mutually similar experts underpinning our Gumbel-Max SI-SCM using synthetic data.
Experimental setup. We consider a synthetic prediction task with k = 5 labels and 20 features per sample, whose values we sample uniformly at random from the interval [0, 1], and a set H of 48 synthetic experts. These synthetic experts make label predictions according to a Gumbel-Max SI-SCM with five disjoint groups of mutually similar experts Ψ, i.e., each expert within a group ψ ∈ Ψ use the same Gumbel noise within the model 16 . Moreover, for each expert, the probability P (Y h = c | X = x) is given by a multinomial logit model with random weight coefficients w = (w 1 , . . . , w 5 ), which we also sample uniformly at random from 16 The groups in the partition Ψ contain 6, 7, 11, 11 and 13 experts.
We measure the performance of Algorithm 1 at recovering the partition Ψ given the true probabilities P (Y h = c | X = x) under different amounts of training data m and sparsity levels s ∈ (0, 1). The sparsity level s controls the average number of observed expert predictions per sample, i.e., for each sample, all experts make a prediction but we only observe max{2, (1 − s)|H|}, picked at random. Here, note that, as the sparsity level s decreases (increases) and the amount of training data increases (decreases), it is easier (harder) to recover the partition Ψ.
As a measure of the difficulty of each inference problem, we will use the edge ratio r, defined as the fraction of pair of experts who belong to the same group ψ ∈ Ψ, among all pairs whose predictions did not violate conditional stability and were at least once observed for the same sample. As performance metrics, we will use: • The adjusted random index (ARI), which measures similarity between the partitionΨ returned by Algorithm 1 and the true partition Ψ. Its value lies in the interval [0, 1] where 1.0 means full recovery and 0.0 means a completely random partition was recovered with no similarity to the true one.
• The average 0/1-loss on a held-out set (with 1000 samples) of a predictor that, given an observed label Y h , returns the most likely label Y h under P M(Ψ) | X=x,Z={h},Y=y h ; do(Z={h })(Y) , i.e., the inferred counterfactual distribution, estimated using 500 samples.
As a point of comparison, for the second performance metric, we also compute the average 0/1-loss over the same held-out set of two other predictors that, given an observed label Y h , return the most likely label Y h under the true counterfactual distributions P M(Ψ) | X=x,Z={h}Y=y h ;do(Z={h })(Y) and the counterfactual distribution P M(H) | X=x,Z={h}Y=y h ;do(Z={h })(Y) , respectively.
Results. Figure 6 summarizes the results, which show that, as long as the edge ratio r > 0.3, the inferred partitionΨ is very similar to the true partition Ψ (i.e., the value of ARI is very close to 1) and the 0/1-losses of the predictors that use M(Ψ) and M(Ψ) respectively are very similar. Here, note however that, even the predictor that uses the true model M(Ψ) has a non zero 0/1-loss is not error free because, given an observed expert prediction Y h and feature vector x, the expert prediction Y h is not deterministic.