Invariant Learning via Probability of Sufficient and Necessary Causes
Authors: Mengyue Yang
Zhen Fang
Yonggang Zhang
Yali Du
Furui Liu
Jean-Francois Ton
Jianhong Wang
Jun Wang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: OOD Generalization
Invariant Representation Learning

Abstract: Out-of-distribution (OOD) generalization is indispensable for learning models in the wild, where testing distribution typically unknown and different from the training. Recent methods derived from causality have shown great potential in achieving OOD generalization. 
However, existing methods mainly focus on the invariance property of causes, while largely overlooking the property of sufficiency and necessity conditions. Namely, a necessary but insufficient cause (feature) is invariant to distribution shift, yet it may not have required accuracy. By contrast, a sufficient yet unnecessary cause (feature) tends to fit specific data well but may have a risk of adapting to a new domain. 
To capture the information of sufficient and necessary causes, we employ a classical concept, the probability of sufficiency and necessary causes (PNS), which indicates the probability of whether one is the necessary and sufficient cause. 
To associate PNS with OOD generalization, we propose PNS risk and formulate an algorithm to learn representation with a high PNS value. We theoretically analyze and prove the generalizability of the PNS risk. Experiments on both synthetic and real-world benchmarks demonstrate the effectiveness of the proposed method. The detailed implementation can be found at the GitHub repository: https://github.com/ymy4323460/CaSN.

Invariant Learning via Probability of Sufficient and Necessary Causes
Mengyue Yang', Zhen Fang², Yonggang Zhang
Yali Du', Furui Liu Jean- Jean-Francol Ton Jianhong Wang", Jun Wang" University College London, UUiieersity of Technology Sydney Hong Kong Baptist University, *King's College London 'Zhejann Lab, BytteDance Research, University of Manchester mengyue. yang www.yyannn...uuuu.m www.2200elcccccm uk, zhen fangen.aaa@uuu fang@uts edu, au, csygzhang@comp hkbu. edu. hk, yali wtw.ll.ddeeccl....oo com, haafuuuuleeiiiiaagg.a......eeaee j jianhong. wangemanchester ac uk, jun. wang@es
com
Abstract
Dut-of-disttiiution (OOD) generalization is indispensable for learning models in the wild, where testing distribution typically unknown and different from the training. Recent methods derived from causality have shown great potential in achieving OOD generalization. However, existing methods mainly focus on the invariance property of causes, while largely overlooking the property of sufficiency and necessity conditions. Namely, necessary but insufficient cause (feature) is invariant to distribution shift, yet may not have required accuracy. By contrast, a sufficient yet unnecessary cause (feature) tends fit specific data well may have risk of adapting to new domain. To capture the information of sufficient and necessary causes, we employ a classical concept, the probability of sufficiency and necessary causes (PNS), which indicates the probability of whether one is the necessary and sufficient cause. To associate PNS with OOD generalization, we propose PNS risk and formulate an algorithm to learn representation with high PNS value. We theoretically analyze and prove the generalizability the PNS risk. Experiments effectiveness of the proposed method. The detailed implementation can be found at the GitHub repository: https: //gpt/gttt/////////////// com/ comm/ymy4330 43344 CACCSN.
both synthetic and real- world benchmarks demonstrate the
Introduction
The traditional supervised learning methods heavily depend on the in-distribution (ID) assumption, where the training data and data are sampled from the same data distribution (Shen al., 2021; Peters et al., 2016). However, the ID assumption may not be satisfied in some practical scenarios like distribution shift (Zhang al., 2013; Sagawa al., 2019), which leads the failure these traditional supervised learning methods. To relax the ID assumption, researchers have recently started to study a different learning setting called out-of out-of-distribbtion (OOD) generalization. OOD generalization aims to train a model using the ID data such that the model generalizes well in the unseen test data that share the same semantics with IDD data (Li al., 2018b; Ahuja al., 2021).
Recent works have proposed to solve the OOD generalization problem through the lens of causality (Peters et al., 2016; Pfister al., 2019; Rothenhäusler et al., 2018: Heinze-Deml al., 2018 Gamella
"Conesponding Author: cxygzhung @omp@ hww..p...bu.d....k... hk; jun wang cs.ucl.c.uk
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

ID
OOD
OOD
X XLYIC
vic
3. V T rrc
train
test
test
V
V
C
NC
pointy ear
True
True True
SF
cat feet
True
False False-
(mara)
SN
short mouth
True
False True-
label
Cat
Fox Cal
Y
X
X
X
(a) Example of 'sufficient' (SF), 'necessary' (NC) and 'sufficient and necessary' (SN) causes
(b) Causal graph
Figure 1: (a) Examples for causal sufficiency and necessity in the cat classification. (b) The causal graph for OOD generalization problem. The arrows denote the causal generative direction and the dashed line connects the spurious correlated variables. Notations are formally defined in Section 2.1. & Heinze-Deml, 2020; Oberst et al., 2021; Chen et al., 2022a). These works focus on learning invariant representation, aiming to capture the cause of the labels. By learning this representation, one can bridge the gap between the training data and unknown OOD test data, and thus mitigate the negative impacts the distribution shift between ID and OOD distributions. Among these works, invariant risk minimization (IRM) (Arjovsky et al., 2019) is the most representative method, targeting to identify invariant representation and classifier using a bi-level optimization algorithm. Following works, many efforts have been devoted to further extending the original invariant learning framework (Chen et al., 2022b; Ahuja et al., 2020a; Lu et al., 2021; Liu al., 202 bb; Lin et al., 2022).
Noticeably, the aforementioned invariant learning methods mainly focus on learning the invariant causal representation, which may contain non-essential information that is not necessary nor sufficient information (Pearl, 2009). In image classification tasks, necessity describes the label not true the features disappear, and sufficiency describes the presence of a feature helps us determine the correctness of the label. If the feature extractor only learns a representation that is invariant but fails to satisfy the sufficiency or necessity, the model's generalisation ability may deteriorate. As an illustrative example (see Figure (aa)), suppose that the training data only contains images of cats with feet and that we are interested in learning model for cat prediction task. If the model captures the invariant information (feature) "cat feet", then the learned model is likely to make a mistake in the OOD data containing cats without "cat feet" features. The example "cat feet" demonstrates the representation contains sufficient but unnecessary causal information because using "cat feet" can predict the label "cat" but cat image might not contain "cat feet". Analogously, there also representations that are necessary but not sufficient (the feature "pointy ear" in Figure (a)). In Section 2.2, present more examples to enhance the understanding of sufficiency and necessity.
This paper proposes achieving OOD generalization using essential causal information, which builds upon the probability of necessarity and sufficiency (PNS) (Pearl, 2009). In this paper, we introduce the PNS risk. A low PNS risk implies that the representation contains both the necessary and sufficient causal information from the observation data with high level of confidence. We provide some theoretical analysis that establishes the approximation of the risk on unseen test domains by the risk on source data. Based on these theoretical results, we discuss PNS risk in the context of semantic separable representation space and propose an algorithm for learning the representation which contains the information of both sufficient and necessary causes from training data (ID data) under different causal assumptions in Figure (bb). The main contributions this paper are as follows:
Firstly, we propose new learning risk-PNS risk-to estimate the sufficiency and necessity of information contained in the learned representation. Secondly, we theoretically analyze the PNS risk under OOD problem and bound the gap between PNS risk on the test domain distribution and the risk on source data. Lastly, we propose an algorithm that captures sufficient and necessary causal representation with low PNS risk on test domains. Experiments benchmarks are conducted to show the effectiveness of the algorithm over state-of of-thc-art methods.
synthetic and real- world
2 Preliminaries
2.1 Learning Setups
Domains. Let X E X' C RD be the observable feature variable and Y E 3' be the label. In this paper, we mainly focus on binary classification task?, i... the label space y = {0, 1). S is a joint
We extend the binary classification to multi classiilaasiiintoionn in experiments.

---

distribution P. (X. Y) defined over X' x 3 in source domain. Equivalently, the unseen test domain is T := P.( We also set Tx= := P. (x) to be the marginal distribution over variable X on test domain. Similarly, Sx == (X) is the marginal distributions on source domain over X.
Assumption and model. We conclude the causal graph in OOD generalization in Figure 1(b), inspired by the content (invariant) features and style (variant) features partition (Zhang et al., 2022). There are the invariant feature C E Edd and domain specific variable (i.e. domain indicator) V E {1,-... .n] A common assumption of OOD generalization is that there exists latent causal variable C E R that maintains the invariance property across domains (see Figure 1(b)), i... P. = c) = P:(YIC- c) (Arjovsky al., 2019). Built upon this assumption, we define an invariant predictor by using simple linear classifier w: R + Y' on the causal features to get label y sign(w" c). Since the causal variable C cannot be directly observed, we infer C from the observational data x ~ X. Then, the invariant predictor with the invariant representation inference model is defined as below.
wT Tcl.
2.2 Probability of Sufficient and Necessary Cause
Existing invariant learning strategies (Rojas- Caraula et al., 2018; Pfister et al., 2019; Arjovsky et al., 2019) only consider the invariant property. However, the invariant representation can be further divided into three parts, each containing the different sufficient and necessary causal information.
(i) Sufficient but unnecessary causes A: The cause A leads to the effect B, but when observing the effect B, it is hard to confirm A is the actual cause (See example in Figure (a)). (ii) Necessary but insufficient causes A: Knowing effect B we confirm the cause is A, but cause might not lead to effect B. "pointy car" in cat prediction is selected as a typical example. Because when the ear shape not pointy, we can confirm "pointy ear" is not a stable feature to predict cats. (iii) Necessary and sufficient causes A: Knowing the effect B confirms the cause A, while observing A leads to In the cat and fox classification task, "short mouth" could be necessary and sufficient cause. It is because the feature "short mouth" allows us to distinguish a cat from a fox, and when know there is cat, "short mouth" " must exist.
not a cat. However, a fox has similar ear shape to a cat. Thus
In order to learn invariant representations C contains both sufficient and necessary causal information, we refer to the concept of Probability of Sufficient and Necessary (PNS) (Chapter in (Pearl, 2009), which is formally defined as below.
Definition 2.1 (Probability of Necessary and Sufficient (PNS) (Pearl, 2009)). Let the specific implementations of causal variable C as с and ट where č +f c. The probability that C is the necessary and sufficiency cause of Y on test domain T is
PNS(c, == I
= C= T, + v) P.(C = +v)
sufficiency
+ Pa(Ydo(C=E) cc = = P.(C = c, Y = y).
nocossity
In the above definition, the notion P(Yáo(C=e)) # yC = y) means that we study the probability of Y * y when we force the manipulable variable C to be a fixed value do = a) (do-operator) given certain factual observation Y and C = c. The first and second terms in PNS correspond to the probabilities of sufficiency and necessity, respectively. Variable C has a high probability to be the sufficient and necessary cause of Y when the PNS value is large. Computing the counterfactual probability is a challenging problem since collecting the counterfactual data is difficult, or even impossible in real-world systems. Fortunately, PNS defined on counterfactual distribution can be directly estimated by the data under proper conditions, i.e., Exogeneity and Monotonicity.
Definition 2.2 (Exogeneity (Pearl, 2009)). Variable C is exogenous relative to variable Y w.r.t. source and test domains S and T, if the intervention probability is identified by conditional probability P. (Ydo(C=e) = y) (Y y/C c) and Pc(Ydo(C=e) y) = Pa(Y y CC (C=c). c).
Definition 2.3 (Monotonicity 3(Paall 2009)). Y is monotonic relative to X if and only if either P(Ydo(C=e) = y, Ydo(C=e) + y) = 0 or P(Yao(C=e) + y, Vao(C=e) = y) = 0
'we rewrite logic expression Ydt(C=a) = y Ydo(==e) y is false or Ydo(C=;; = y A Ydo(C=e) = =yis is false in original Monotonicity by the probabilistic formulation.
3

---

The definition of Exogeineity describes the gap between the intervention and conditional distributions vanishes when C is exogenous relative to Y and the definition of Monotonicity demonstrates the monotonic effective on Y of causal variable C. Based on Definitions 2.2 and 2.3, the identifiability of PNS in Definition 2.1 is described as the following lemma.
Lemma 2.4 (Pearl (2009)). If C is exogenous relative to Y, and Y is monotonic relative to C, then PNS(c, Ł) Pr(Y = y y/C=
Pr(Y = y - C)
suffciency
recessity
According to Lemma 2.4, the computation of PNS is feasible through the observation data under Exogeneity and Monotonicity. This allows us to quantify PNS when counterfactual data is unavailable. The proof of Lemma 2.4 is provided by Pearl (2009). Wang & Jordan (2021) further extend the proof by incorporating probabilistic computation, as opposed to the logical calculation used Pearl (2009).
3 PNS Risk Modeling
This section presents the DNS-based risk for invariant learning in OOD problem. The risk on test domains is a PNS-value evaluator, which is bounded by the tractable risk on the training domain.
3.1 PNS Risk
In this section, we introduce the PNS risk. which is a PNS-value estimator. The risk estimates the PNS value of the representation distribution P. (C = x) inferred from X on unseen test domain T. The risk increases when the representation contains less necessary and sufficient information, which can be caused by data distribution shifts. The PNS risk is based on the definition of PNS(c, c). As represents the intervention value, it is not necessary for it to be a sample from the same distribution as the causal variable C. Thus, define an auxiliary variable C E IR (same as the range of C) and sample è from its distribution P.(C|X = x). In the learning method, we use the notations (C[( x) and ( X = x) to present the estimated distributions, which are parameterized by é and ç. separately. Let I(A) be an indicator function, where I(A) = if A is true; otherwise, I(A) 0. PNS risk based on Definition 2.1 and Lamma 2.4 is formally defined as Eq. (4) below.
(w, 0. )) == (x.g)~ xx [[sign(w w c) + yl
= [[sign( w Tτ) = yl]
As the identifiability result in Lemma 2.4 is based on the Exogeneity 2.2 and Monotonicity 2.3, we modify the original risk equation, Eq. (4), to ensure compliance with these conditions. Below, provide Monotonicity measurement and discuss the satisfaction of Exogeneity in Section 4.3.
Satisfaction of monotonicity. We naturally introduce the measurement of Monotonicity into PNS risk by deriving an upper bound of Eq. (4), which is given below.
Proposition 3.1. Given a test domain T, we define the sufficient and necessary risks as:
SF.(w, Φ)
Exxx,)) (exxa)-TBePPPCCCB (c c) # vl.
sufficiency
NC,( = E(x.))) B on (Cxx=x) Usign wo TT) = vl.
mecessity term
and let the Monotonicity measurement be
Mf (cb. {) = P.. PeN [sign( Tc) =sign(w' To)],
then we have
Re MR (0.E) + (
5 (0, 22SF.(w.)) (M
(5)
The upper bound for PNS risk Eq. (5) consists of two terms: (i) the evaluator of sufficiency SF.(w Φ) and (ii) the Monotonicity measurement M (xb (d. In the upper bound, the necessary term (C,(w,& {) is considered to be absorbed into measurement of Monotonicity M E). The minimization process of Eq. (4) on its upper bound (5) considers the satisfaction of Monotonicity.

---

3.2 OOD Generalization with PNS risk
In OOD generalization tasks, only source data collected from S is provided, while the test domain T is unavailable during the optimization process. As a result, it is not possible to directly evaluate the risk on the test domain, i.c. R, Φ E). To estimate Re (w, Φ {), we have two-step process: (i) Firstly, since the test-domain distribution T is not available during the training process, We aim to establish connection between the risk on the test domain (w, Φ E) and the risk on the source domain R, (w, {) in Theorem 3.2. (ii) Furthermore, in practical scenarios where only a finite number of samples are available, we demonstrate the bound of the gap between the expected risk on the domain distribution and the empirical risk on the source domain data in Theorem 3.3.
Connecting the PNS risks, i.e., Re (w, o, E) and R. (w, do E). We introduce divergence measurement 3 divergence (Ganin et al., 2016) and weigh the (w, Ø, E) term by variational approximation. B
divergence measures the distance between domain T and S, which is formally defined below.
T(x, v)
(x(T[[S)
E
(6)
(x.N)~
8(x, y)
Based on (x(T]) we connect the risks on the source and test domains by Theorem 3.2.
Theorem 3.2. The risk on the test domain is bounded by the risk on the source domain, i.e., Re(w,o, 2, <
lim Be(TT)S)((M) (0,)))=== +ISFF o) +) + Th, (X, Y),
++00
where
no (X, Y) = Px(X x Y & supp(S)) sup
suup Rey (w, d E).
Here Su)p(8) is the support set of source domain distribution Px(X),
Berolw,o,E) == E(x,v) (supp(S)) ( [Iee [sign w c) # y] +IEe- (ssign w Tо) - -y]]-
In Theorem 3.2, eX, (XYY Y) deseribes the expectation of worst risk for unknown area i.e. the data sample (x, y) does not include in the source domain support set supp(S). Theorem 3.2 connects the source-domain risk and the test- test-domain risk. In the ideal case, where C is the invariant representation, i... (Y c)- PC c). the bound is reformed below.
(w 2,
< lim 3u (Tx (6, +) + 2[SF -) + (X,Y).
(7)
+oc
When the observations X in S and T share the same support set, the term Mey M,.. (X, Y) approaches to O. In domain generalization tasks, the term By (Tx is treated hyperparameter, as the test domain Tx is not available during training. However, in domain adaptation tasks where Tx is provided, (Tx (Sx) and the test-domain Monotonicity measurement M (Ø, {) can be directly estimated. Further details of the discussion on domain adaptation are provided in Appendix A.3.
Connecting empirical risk to the expected risk. In most real-world scenarios where distribution S not directly provided, we consider the relationship of expected risk on source domain distribution and empirical risk on source domain data S" == {(x,, [.)
We also define the empirical risks
w.r.t. SF, (w, Φ), M (Ø.E) as follows:
x=x SF (F,(w, (w, Φ) = Es Xxxx Usign( T Tc) + Fy).
M77 (Φ, = Esn B po (C|X=x)) E P (C
U [sign(ww Tc) = sign(w (w TT)]
where (C x) and (C x) describe the estimated distribution on dataset S
Then, we use PAC-learning Shaale--Shwart, & Ben-David, 2014) tools to formulate the upper bound of gap between empirical risk and expected risk as a theorem below.
Theorem 3.3. Civen parameters Φ. &, for any w : Rdd + Y, prior distribution Te == P.(C) and Te == (C) which make KT (Pé (CIX = x)) and K.s x)||=e) both lower than positive constant C, then with probability least 1 over source domain data S,,.
5

---

(1) (SFSF.(W,. - SF.(W. 6)1 is upper bounded by
B (T = =x]{x= + In(n/c)
1(n-1) + C.
(2) MM (6.E) - (M. is upper bounded by
In(n/e) Es KL = x)] + KL =x)]xx=))][a 4(n 1)
+ 2C.
Theorem 3.3 demonstrates that the sample size increases and the terms with KL divergence decrease, the empirical risk on the source domain dataset becomes closer to the expected risk. Combining Theorems 3.2 and 3.3, we can evaluate the expected PNS risk on the test distribution using the empirical risk on the source dataset. In the next section, we present a representation learning objective based on the results of Theorems 3.2 and 3.3 and introduce the satisfaction of Exogeneity.
4 Learning to Minimizing PNS Risk
In this section, we propose a learning objective built upon the PNS risk that is used to capture the essential representation having high PNS value from observational data.
4.1 The Semantic Separability of PNS
In Section 3, we present PNS risk and Monotonicity measurement. Furthermore, to ensure that finding interpretable representations is feasible, we need to make certain assumptions that the representation of the data retains its semantic meaning under minor perturbations. Specifically, we define the variable C as Semantic Separability relative to Y if and only if the following assumption is satisfied:
Assumption 4.1 (ō-Semantic Separability). For any domain index d E {s, t). the variable C is 8- s-semantic separable, if for any Pa(C y) and č Pa(Cly * y), the following inequality holds almost surely: ج| c||2 > 8.
8- Semmnntic Separability refers the semantic meaning being distinguishable between с and when the distance between them is large enough, i.e., | ccl2 > 8. This assumption is widely accepted because, without it, nearly identical values would correspond to entirely different semantic information, leading to inherently unstable and chaotic data. If C satisfies Assumption 4.1, then considering the PNS value in a small intervention, such as ||c - E/|2 < 8, will lead failure in representation learning. Therefore, during the learning process, we add the penalty of ||c E||2 6.
4.2 Overall Objective
Depending on the diverse selections of (C x). there are multiple potential PNS risks. In the learning process, we consider minimizing the risk in the worst-case scenario lead by C, i.c., the maximal PNS risk lead by the selection of P ( x). Minimizing the upper bounds in Theorems 3.2 and 3.3 can be simulated by the following optimization process
min max 6.W E
M (o. SF (w. + ALKL. subject
||c - c||2 >
(8)
where T.I.. == Esn (T, (C x))(=c)) F.s
=)][=e)) The constraint ||c E|l2 >> is set because of the Semantic Separability assumption. We name the algorithm of optimizing
Eq. (8) as CaSN (Causal Representation of Sufficiency and Necessity).
4.3 Satisfaction of Exogeneity
In the previous sections, we introduced an objective to satisfy monotonicity. Identifying PNS values not only needs to satisfy monotonicity but also exogeneity. In this part, we discuss the satisfaction of Exogeneity and provide the solution to find the representation under three causal assumptions below.
Assumption 4.2. The Exogeneity of C holds, if and only if the following invariant conditions are satisfied separately under three causal assumptions in Figure 1(b): (1) X ()) V T Y|C (for assumption in Figure 1(b).1, 2 and 3, respectively).

---

The above three assumptions are commonly accepted by the OOD generalization (Lu et al., 2021; Liu al., 2021a; Ahuja et al., 2021). To satisfy the Exogeneity, we use different objective functions to identify C over three invariant causal assumptions. For Assumption 4.2 (1), we provide the following theorem showing the equivalence between optimizing Eq.8 and identifying invariant representation.
Theorem 4.3. The optimal solution of learned C is obtained by optimizing the following objective (the key part of the objective in Eq. (8)
min SInSFF. (w. 6) + AEg-KL(PS (C|X = x)][=c) G.W
satisfies the conditional independence LYC.
Theorem 4.3, details of the proof are shown in Appendix E, indicates optimizing overall objective Eq (8) implicitly makes C satisfy the property of Exogeneity under causal assumption X I Y Y|C. For Assumption 4.2 (2), to identify the invariant assumption C 1 V (Li et al., 2018b), we introduce the following Maximum Mean Discrepancy (MMD) penalty to the minimization process in Eq. (8),
Lmmd
Σ ΣΣ
||q - -cll2
For Assumption 4.2 (3), to specify the representation of C and allows the Exogeneity when the assumption V Y/C holds, we introduce the IRM-based (Arjovsky al., 2019) penalty into (8).
Lim E(s.)--PXX
| Po (ssinn(w T c) + vi
Noticebly, to address the issue of invariant learning and satisfy the Exogeneity under Assumptions 4.2 (2) and (3), it is necessary to introduce additional domain information, such as domain index.
5 Related Work
In this section, we review the progress of OOD prediction tasks. A research perspective for OOD prediction is from causality viewpoint (Zhou et al., 2021; Shen et al., 2021). Based on the postulate that the causal variables are invariant and less vulnerable to distribution shifts, a bunch of methods identify the invariant causal features behind the observation data by enforcing invariance in the learning process. Different works consider causality across multiple domains in different ways. One series of research called the causal siterence-basete methods model the invariance across domains by causality explanation, which builds a causal graph of data generative process (Pfister et al., 2019; Rothenhäusler et al., 2018; Dienzze-Demll et al., 2018; Gamella & Heinze-Demi 2020; Oberst et al., 2021; Zhang et al., 2015). The other series of methods consider invariant learning from a causality aspect. They formulate the invariant causal mechanisms by representation rather than causal variables. Invariant risk minimization (IRM) methods (Arjovsky et al., 2019) provide a solution for learning invariant variables and functions. Under this viewpoint, some pioneering work (Ahuja et al., 2020a; Chen et al.. 2022b; Krueger et al., 2021; Lu et al., 2021; Abuja et al., 2021; Lin et al.. 2022) further extend the IRM framework by considering game theory, variance penalization, information theory, nonlinear prediction functions, and some recent works apply the IRM framework to large neural networks (Jin et al., 2020; Guirajani& & Lopez-Paz, 2020). In this paper, different from the aforementioned works which consider to learn the invariant information, we think that information satisfying invariance is not enough to most appropriate for the generalization task. We thus focus on learning to extract the most essential information from observations with a ground on the sufficient and necessary causal theorem. the main text, we only provide a review of OOD prediction. We further elaborate on the correlation with other lines of work, such as domain adaptation, causal discovery, representation learning, causal disentanglement, and contrastive learning, in Appendix
Experiments
In this section, we verify the effectiveness of CaSN using synthetic and real- weal-world OOD datasets.
6.1 Setups
Synthetic data. The effectiveness of the proposed method is demonstrated by examining whether can learn the essential information (i.c., sufficient and necessary causes) from source data. To this
7

---

LeuningMethod
0.65
0.67
0.13
0.62
0.65
0.37
Distance Conclation
CsSN
CaSN-m))
0.7-
0.7-
0.33
8
8
0.6
0.4
0.66
0.68
0.10
0.4
0.86
0.66
0.70
0.35
0.5
0.4
0.1-
0.86
0.71
0.68
0.10
0.1
0.85
0.68
0.72
0.35
0.3
SN
SF
NC
Sparious
SN
SF
NC
Spurious
SN
SF
NC
Spurious
(a) Spurious degree a 0.1 (b) Spurious degree # 0.7 (c) Results of CaSN and the CaSN(-m)
Figure 2: The synthetic results for validating the property of learned representation under different spurious degrees in data, 0.1 for (a) and 0.7 for (b), the x-axis shows different causal information y-axis shows the choice of (c) The results the feature identification when 8 = 0.7.
end, based on the causal graph in Figure 1(b). we designed a synthetic data generator that produced
sample set { with corresponding labels {u.}" Four types of information were considered, J'mi
including: (i) SN: Sufficient and Necessary Cause sn, of y/- The value of Yi is directly calculated as y sn, + (0)1 where + represents the XOR operation and BO0.15) is Bernoulli distribution with a probability of 0.15 to generate 1. (ii) SF: sufficient and unnecessary cause sf, of y:- sf, is transformation of sn;- We set sf, B(0.1) when sn; = 0, and sf; sn; when sn; 1. SF is designed to decrease the probability of necessity (i.e. P(Y = O|SN = 0)). (iii) NC: insufficient and necessary cause nc, of y/: We ne; T(sn; 1) B(0.9). NC is designed to decrease the probability of sufficiency (i.e. P(Y = 1 SNN 1)). (iv) Spurious: spurious correlation information sp;- Spurious correlated information generated by sn, 1a + (1 - so, 1). where d denotes dimension and denotes the spurious degree. When gets higher, the spurious correlation becomes stronger in data We select d 5 and {0.11 0.73. in the synthetic generative process and develop non-linear function to generate x from [sn,, sf:, nc, sp... We use Distance Correlation (Jones et al., 1995) as evaluation metries to measure the correlation between the learned representation C and ground information (i.e. SN, SF. NC, SP). We provide an ablation study of CaSN without the Monotonicity evaluator CaSN(-m) comparison results, which evaluates the effectiveness of CaSN.
Performance on OOD prediction task. The proposed method CaSN is implemented based on codebase DomainBed (Gulrajani & Lopez-Paz, 2020). We provide three implementations of method, which are CaSN, CaSN(irm) and CaSN(mmd) with the same architecture but using (8), Eq.(8) +Lim and (8) Lmmdd as their final objective, respectively. We compare CaSN with several common baselines, including ERM(Vapnik, 1999), 1RM (Arjovsky et al., 2019), GroupDRO (Sagawa al., 2019), Mixup (Xu al., 2020), MLDG (Li al., 201 MMD (Li et al., 2018b), DANN (Ganin et al., 2016) and CDANN (Li et al., 201 8c), where the best accuracy scores are directly given by training-domane domain-validdtioon validation Guirajani Lopez-Paz (2020). We test the performance on commonly used ColoredMnist (Ahuja et al., 2020a), PACS (Li et al., 2017), and VL.CS (Fang et al., 2013) datasets. During the experiment process, we adjust the hyperparameters provided by DomainBed and extra hyperparameters 5 and À in CaSN. The results show the mean and standard error of accuracy by executing the experiments randomly times on 40 randomly selected hyperparameters. We also provide the extra experiments on large-scale spurious correlation dataset SpuCo (Joshi et al., 2023). Due to the page limitation, more experiment setups and results are provided in Appendix B.
6.2 Learning Sufficient and Necessary Causal Representations
We conducted experiments on synthetic data to verify the effectiveness of the learned representation. In experiments, we use single domain with different degrees of spurious correlation. The experiments aimed to demonstrate the properties of the learned representation and answer the following question:
Does CaSN capture the sufficient and necessary causes? We present the results in Figure 2 (a) and (b), which show the distance correlation between the learned representation and four ground truths: Sufficient and Necessary cause (SN, SF, NC and Spurious). higher distance correlation indicates a better representation. From both Figure 2 (a) (b), we found that CaSN achieves higher distance correlations with the ground truths (e.g.. SN, SF, and NC) and lower correlations with spurious factors compared to other methods. As an example, we consider Figure 2 (a) with 5 = 1.1. We obtain distance correlations of (0.90, 0.65, 0.67, O. 13) for SN, SE, NC, and spurious factors, respectively. We found that when we set ó as a large value 1.1, CaSN captures more essential information SN.

---

Table 1: Results on PACS and VLCS dataset
PACS
VLCC
Algorithm
A
P
8
Avg
Min
Avg
Min
FRM
84.7 0.4
80X + 0.6
97.2
79.3
1.0
85.5
79.3
97.7 + 0.4
64.3 + 0.9
73.
+ 0.5
746+11
T7.5
64.3
IRM
1.3
76.4
96.
0.6
83.5
76.4
98.6
649 =
73.
0.6
77.3
GRoupDRO
79.1
96.7
$4.4
97.3 0.
89.5
76.7
0.7
Mixup
78.9 0.8
97.6 + 0.1
75.8
1.8
N4.6
78.9
98.1 +06
648 1.0
72.1
0.
74.3 0.8
774
64.8
MLDG
0.
714=008 0.8
97.3 11.3+04
13.5
2.3
83.6
77.4
97.4
66.2
71.0 14
75.3
1,0
77.2
65.2
MMD
1.
7944
96.6
76.5
84.6
79.4
97.7
0.1
640
72.8
1 0.2
75.3
4.3
77.5
64.0
77.4
83.6
77.4
73.1
772
CDANN
81.6 1.8
73.5 0.9
96.8 0.3
73.5 0.6
82.6
75.5
97.1
0.3
65.1
1 1.2
70.7
1 0.8
77.1
1.5
77.5
65.1
CaSN (bane)
87.1 0.6
80.2 1 0.6
96.2 0.8
80.1
0.2
86.0
80.2
97.5
0.6
618
1
1.9
7022
0.5
76.1
1
1.7
77.2
61.8
CaSN (irm)
82.1 1:3
77.9
+ 1.8
0.8
80.6 + 1,0
83.5
77,9
97.8
0.3
65.7
4 0.8
72.3
1 04
77.0
14
78.2
65.7
Ca8N (sonad)
84.7
65.9
71.2
However, the result of CaSN decreases when 8 = 0.1, which suggests that CaSN tends capture the most essential information when 5 is set to a larger value. This phenomenon aligns with Semantic Separability. We then compare Figure (a) and (b). As an example, when 5 1.1, CaSN achieves distance correlations of 0.9 and 0.91 for SN on 8 = 0.1 and 8 0.7, respectively. The distance correlation with spurious information is 0.13 and 0.37 for s = 0.1 and 0.7, respectively, The results show that when more spurious correlations are in data, CaSN tends to capture information from those spurious correlations, but the algorithm is still able to get sufficient and necessary causes.
Ablation study. In Figure 2(c), we provide the comparison results between CaSN and the CaSN(-m) that removes the Monotonicity measurement on synthetic data. The figure demonstrates the distance correlation recorded over 5 experiments. The green bars indicate the distance correlation between learned representation and ground truth by CaSN, CaSN can capture the desired information SN compared to others. As the blue bars show, the CaSN(-m) can better capture the causal information (e.g. SN, SF and NC) rather than spurious correlation. It can stably identify SN, compared to SF. CaSN(-m) can be regarded as the method that only cares Exogeneity. The results support the theoretical results in Theorem 4.3, which show the effectiveness of introducing Monotonicity term.
6.3 Generelization to Unseen Domain
The results of the OOD generalization experiments on PACS and VLCS datasets are presented in Tables 1. Due to page limitation, we provide the results on ColoredMNIST in Table 2. The baseline method results are from Kilbertus et al. (2018). The proposed CaSN method exhibits good OOD generalization capability on both PACS and VLCS datasets. In Table I, CaSN achieves the best average performance
4 domains by 86.0 on PACS. On the VLCS, CaSN(irm) achieves good average performance of 78.2, which is close to the best state-of-the-ee DANN. For worst-domain test accuracies, the proposed method CaSN outperforms all the baseline methods. An intuitive explanation for the good performance of CaSN is that it aims to identify and extract the most essential information from observation data, excluding unnecessary insufficient information from the optimal solution. This enables CaSN to better generalize on the worst domain.
performance achieved by
Conclusion
In this paper, we consider the problem of learning causal representation from observation data for generalization on OOD prediction tasks. We propose a risk based on the probability of sufficient and necessary causes (Pearl, 2009), which is applicable OOD generalization tasks. The learning principle leads to practical learning algorithms for causal representation learning. Theoretical results on the computability of PNS from the source data and the generalization ability of the learned representation are presented. Experimental results demonstrate its effectiveness on OOD generalization.
8 Acknowledgement
We are thankful to Juzheng Miao, Xidong Feng. Kun Lin and Jingsen Zhang for their constructive suggestions and efforts on OOD generalization experiments and for offering computation resources. We also thank Congmin Ji for checking the correctness of the mathematical proof, Pengfei Zheng for his helpful discussions and the anonymous reviewers for their constructive comments on an earlier version of this paper. Furui Liu is supported by the National Key R&D Program of China (2022YFB4501504 2022YFB4501504) Jianhong Wang fully supported by UKRI Turing Al World-Leading Researcher Fellowship. EP/W002973/1.

---

References
Ahuja, K., Shanmugam, K., Varshney, K., and Dhurandhar, A. Invariant risk minimization games. In International Conference Machine Learning, pp. 145-155, PMLR, 2020a.
Ahuja, K., Wang. J., Dhurandhar, A., Shanmugam, K., and Varshney, K. R. Empirical invariant risk minimization? a sample complexity perspective. arXiv preprint arXiv:2010. /64/2, 2020b.
Abuja, K., Caballero, E.. Zhang, D., Gagnon-Auce J.-C., Bengio, Y.. Mitliagkas, I,, and Rish, I. Invariance principle meets information bottleneck for oft-or-diitribuutio generalization. Advances in Neural Information Processing Systems, 34:3438-344 2021.
Alemi, A. A., Fischer, I., Dillon, J. V., and Murphy, K. Deep variational information bottleneck. arXiv preprint 1rXiv:16/2.004 2016.
Arjovsky, M., Bottou, L.. Gulrajani, I., and Lopez-Paz, D. Invariant risk minimization. arXiv preprint arXiv:1907.02893, 2019.
Chen, Y., Zhang. Y., Bian, Y., Yang, H., Kaili, M., Xie, B., Liu, T., Han, B., and Cheng, Learning causally invariant representations for out-of-distribution generalization on graphs. Advances in Neural Information Processing Systems, 15:22131-22145 2022a.
Chen, Y., Zhang. Y., Yang. H., Ma, K., Xie, B., Liu, T., Han, B., and Cheng, Invariance principle meets out-of- -iittridiitiittionnn generalization on graphs. arXiv preprint arXiv:220.004441, 2022b.
Clevert, D.-A., Unterthiner, T., and Hochreiter, S. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.07285 2015.
Cover, T. M. Elements of information theory. John Wiley & Sons, 1999.
Doersch, C. Tutorial on variational autoencoders. arXiv preprint arXiv: 1006005908 2016.
Fang, C., Xu, Y., and Rockmore, D. N. Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias. Proceedings of the IEEE International Conference on Computer Vision, pp. 1657-1664, 2013.
Finn, C., Abbeel, P., and Levine, S. Model-agnostic meta-learning for fast adaptation of deep networks. International conference on machine learning, pp. 1126-1135. PMLR, 2017.
Fisher, R. A. On the mathematical foundations of theoretical statistics. Philosophical transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character, (22(594-00))3399-3
1922.
Gamella, J. L. and Heinze-Deml, C. Active invariant causal prediction: Experiment selection through stability, Advances in Neural Information Processing Systems, 33:15464-15475. 2020.
Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle. H., Laviolette, F., Marchand, M., and Lempitsky, V. Domain-adversane training of neural networks. The journal of machine learning research, 17(1):2096-2033 2030, 2016.
Germain, P., Habrard, A., Laviolette, F., and Morvant, E. new pac-bayesian perspective on domain adaptation. In International conference machine learning, pp. 859-868. PMLR, 2016.
Gong, M., Zhang. K., Liu, T., Tao, D., Glymour, C., and Schölkopf, B. Domain adaptation with conditional transferable components. International conference on machine learning, pp. 2839- 2848. PMLR. 2016.
Gretton, A., Borgwardt, K. M., Rasch, M. Schölkopf, B., and Smola, kernel two-sample test. The Journal of Machine Learning Research, 13(1):733777,, 2012.
Gulrajani, I. and Lopez-Paz, D. In search of lost domain generalization. arXiv preprint 2xXiv:2007.01444 2020.
Heinze-Deml, C., Peters, J., and Meinshausen, N. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.
10

---

Hoyer. P., Janzing, D., Mooij, J. M., Peters, J., and Schölkopf. B. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21. 2008.
Janzing, D. and Schölkopf, B. Causal inference using the algorithmic markov condition. IEEE Transactions on Information Theory, (6(10)5518--1999 2010.
Jin, W., Barzilay, R., and Jaakkola, T. Domain extrapolation via regret minimization. arXiv preprint arXiv:2006. 200000000033,8 2020.
Jones, T., Forrest, S., et al. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In ICGA, volume 95, pp. 184-192, 1995.
Joshi, S., Yang, Y., Xue, Y., Yang. W., and Mirzasoleiman, B. Towards mitigating spurious correlations in the wild: A benchmark & more realistic dataset. arXiv preprint arXiv:2306. 19577, 2023.
Kilbertus, N., Parascandolo, G., and Schölkopf, B. Generalization in anti-causal learning, arXiv preprint arXiv:1812.0055: 2018.
Krueger, D., Caballero, E., Jacobsen, J.-H., Zhang, A., Binas, J., Zhang, D., Le Priol, R., and Courville, A. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning, pp. 5815-5826. PMLR, 2021.
Li, D., Yang, Y., Song. Y.-Z., and Hospedales, T. M. Deeper, broader and artier domain generalization. In Proceedings of the IEEE international conference computer vision, pp. 5542 5550, 2017.
Li, D., Yang. Y., Song, Y.-Z., and Hospedales, T. Learning to generalize: Meta-learning for domain generalization. In Proceedings of the AAAI conference artificial intelligence, 2018a.
Li, H., Pan, J., Wang, S., and Kot, Domain generalization with adversarial feature learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5400-5409, 2018b.
Li, Y., Tian, X., Gong, M., Liu, Y., Liu, T.. Zhang, K., and Tao, D. Deep domain generalization via conditional invariant adversarial networks. Proceedings of the European Conference on Computer Vision (ECCV), pp. 624-639, 2018c.
Lin, Y., Zhu, S., Tan, I.., and Cui, P. Zin: When and how learn invariance without environment partition? In Advances in Neural Information Processing Systems, 2022.
Liu, C., Sun, X., Wang, J., Tang, H., Li, T., Qin, T., Chen, W., and Liu, T.-Y, Learning causal semantic representation for out-of-distributio prediction. Advances in Neural Information Processing Systems, 34:6155-611 61700 2021a.
Liu, J., Hu, 7.,, Cui, P., Li, B., and Shen, Z. Heterogeneous risk minimization. International Conference Machine Learning, pp. 6804-6814. PMLR, 2021b.
Lu, C., Wu, Y., Hernández-Lobato, M., and Schölkopf. Nonlinear invariant risk minimization:
A causal approach. arXiv preprint arXiv: 102. 123.5 2021.
Magliacane, S., van Ommen, T., Claassen, T., Bongers, S., Versteeg, and Mooij, J. M. Domain adaptation by using causal inference to predict invariant conditional distributions. arXiv preprint (iXiv:1707.06422 2017.
Magliacane, S., Van Ommen, T., Claassen, T., Bongers, S., Versteeg, P., and Mooij. J. M. Domain adaptation by using causal inference to predict invariant conditional distributions. Advances in neural information processing systems, 31, 2018
Meinshausen, N. Causality from distributional robustness point of view. In 2018 IEEE Data Science Workshop (DSW), pp. 6-10. IEEE, 2018
Mooij, J. M., Peters, J., Janzing, D., Zscheischler, J., and Schölkopf, B. Distinguishing cause from effect using observational data: methods and benchmarks. The Journal of Machine Learning Research,
2016.

---

Oberst, M., Thams, N., Peters, J., and Sontag, D. Regularizing towards causal invariance: Linear models with proxies. In International Conference on Machine Learning, pp. 8260-8277 PMLR. 2021.
Pan, S., Tsang, I. W. Kwok, J. T., and Yang. Q. Domain adaptation via transfer component analysis. IEEE transactions on neural networks, 22(2):199- 190-21,,,,,,,, 2010.
Parascandolo, G., Kilbertus, N., Rojas-Carulla, M., and Schölkopf, B. Learning independent causal mechanisms. In International Conference on Machine Learning, pp. 4036-4044. PMLR, 2018.
Pearl, Causality, Cambridge university press, 2009.
Peters. J., Büihlaan, P. and Meinshausen, N. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society. Series B (Statistical Methodology), pp. 947-1012, 2016.
Pfister, N., Bühlmann, P., and Peters, J. Invariant causal prediction for sequential data. Journal of the American Statistical Association, 114(527):1244-177) 2019.
Puli, A., Perotte, A., and Ranganath, R. Causal estimation with functional confounders. Advances in neural information processing systems, 33:5115-5125, 2020.
Rojas-Carulla, M., Schölkopf, B., Turner, R., and Peters, J. Invariant models for causal transfer 2018.
learning. The Journal of Machine Learning Research,
Rothenhäusler, D., Meinshausen, N., Bühlmann, and Peters, Anchor regression: heterogeneous 2018.
data meets causality. arXiv preprint
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge. International journaa of computer vision, 1 115:21 1-222, 2015.
Sagawa, S., Koh, W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint 1oXiv:1911.08311, 2019.
Saunshi, N., Ash, J., Goel, S., Misra, D., Zhang, C., Arora, S., Kakade, S., and Krishnamurthyy, A. Understanding contrastive learning requires incorporating inductive biases. arXiv preprint 20Xi::2202.14037, 2022.
Schölkopf. B., Locatello, F., Bauer, S., Ke, N. R., Kalchbrenner, N., Goyal, A., and Bengio, Y. Toward causal representation learning. Proceedings of the IEEE, 109(5))612-634, 2021.
Shaartz,, S. and Ben-David, S. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shamir, O., Sabato, S., and Tishby, N. Learning and generalization with the information bottleneck. Theor Comput. Sci., (211(2293))296666611) 27 2010a.
Shamir, O., Sabato, S., and Tishby, N. Learning and generalization with the information bottleneck. Theoretical Computer Science, 41 411029930):299-2271 2010b.
Shen, X., Liu, F., Dong, H., Lian, Q., Chen, Z., and Zhang, T. Disentangled generative causal representation learning, arXiv preprint arXiv:2010.02637, 2020.
Shen, Z., Liu, J., He, Y., Zhang, X., Xu, R., Yu, H., and Cui, P. Towards out-of-distribution generalization: A survey, arXiv preprint arXiv:2108.13e8 136.. 2021.
Sontakke, S. A., Mehrjou, A., Itti, I.., and Schölkopf, B. Causal curiosity: RI agents discovering self-supervised experiments for causal representation learning. In International Conference on Machine Learning, pp. 9848-9858. PMLR, 2021.
Steudel, B., Janzing, D., and Schölkopf, Causal markov condition for submodular information measures. arXiv preprint 40224 2010.
12

---

Vapnik, N. An overview of statistical learning theory. IEEE transactions on neural networks, 10 (5)9988 999, 1999.
Wang, Y. and Jordan, M. Desiderata for representation learning: A causal perspective. arXiv preprint arXiv:2109.0377 2021.
Wang. Y., Li, H., and Kot, A. C. Heterogeneous domain generalization via domain mixup. In ICASSP 2020-2020 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3622 3626. IEEE, 2020.
Xiao, T., Wang, X., Efros, A. A., and Darrell, What should not be contrastive in contrastive learning. arXiv preprint arXiv:2008. 05659, 2020.
Xu, M., Zhang, J., Ni, B., Li, T., Wang, C., Tian, Q.. and Zhang, W. Adversarial domain adaptation with domain mixup. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6502- 6509, 2020.
Yan. S., Song, H.,, Li, N., Zou, L., and Ren, L. Improve unsupervised domain adaptation with mixup training. arXiv preprint arXiv:2001.0061 006777, 2020.
Yang, M., Liu, F., Chen, Z., Shen, X., Hao, J., and Wang, J. Causalvae: disentangled representation learning via neural structural causal models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patlern Recognition, pp. 9593-9602, 2021.
Yang, M., Cai, X., Liu, F., Zhang, W., and Wang, J. Specify robust causal representation from mixed observations. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2978 2987, 2023.
You, K., Wang, X., Long, M., and Jordan, M. Towards accurate model selection in deep unsupervised domain adaptation. International Conference on Machine Learming, pp. 7124-7133, PMLR, 2019.
Zhang. K. and Hyvarinen, A. On the identifiability of the post-nonlinear causal model. arXiv preprint 1rXiv:1205.2550 1205.2599, 2012.
Zhang, K., Schölkopf, B., Muandet, K., and Wang, Z. Domain adaptation under target and conditional shift. In International conference on machine learning, pp. 819-827. PMLR, 2013.
Zhang, K., Gong. M., and Schölkopf. B. Multi-source domain adaptation: A causal view. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
Zhang, Y., Liu, T., Long, M., and Jordan, M. Bridging theory and algorithm for domain adaptation.
In International Conference on Machine Learning, pp. 7404-7413, PMLR, 2019.
Zhang, Y., Gong, M., Liu, T., Niu, G., Tian, X., Han, B., Schölkopf, B., and Zhang, K. Adversarial robustness through the lens of causality. In International Conference on Learning Representations, 2022.
Zhao, H., Des Combes, R. T., Zhang, K., and Gordon, G. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pp. 7523-7532. PMLR. 2019.
Zhou, K., Liu, Z., Qiao, Y., Xiang, T., and Loy, C. C. Domain generalization: A survey, arXiv preprint arXiv:2 103. 025002 2021.
13

---

A Discussion
In this section, we provide discussions of how better understand PNS value, the understanding of Theorem 4.3, the connection on domain generalization, and the limitations of this work.
A.1 Examples to Understand PNS Value
The 'cat feet' patch is sufficient but unnecessary
The 'ear shape' patch necessary but insufficient
Figure 3: Example for causal sufficiency and necessity in image classification problem. The images on the left are for training and the rights are for OOD tests.
We provided two examples to help understand the PNS (Probability of Necessity and Sufficiency) value. We will add the following explanations our revision.
Example.1. We use the feature 'has cat legs' represented by the variable C' (taking binary values or 0) predict the label of being cat fox. 'has cat legs' is the sufficient but unnecessary cause because the image contains cat legs must have cat but cat image might not contain cat leg.
We assume P(Ydo(C=1) =1) =1 and P(Ydo(C==0
0) 0.5, P(Y = 1) = 0.75, P(C = 1,Y 1) = 0.5, P(C 0, = 0) = 0.25, P(C 0, Y = 1) 0.25.
Now, applying the concept of the probability of sufficiency and necessity, we obtain:
Probability of necessity: P(Yao(C=o) O 1,C 1) PY==1)-PVaacc-0
P(Y=1,C-1)
P(Y=1,C=1) 0.5
0.75-0.5
Probability of sufficiency: P(Yáo(C=1) 1 0,C 0) PU) P(Y
1-0.75
P(Y=1,C=T)
In this example, the calculation PN and PS are from eq.9.29 and cq.9.30 Chapter at (Pearl, 2009).
state that variable C' has probability of being sufficient cause. Note that
Ex If we use feature 'pointy ear' C' (taking values 1, O. Value means pointy ear), to predict Y (cat other animal 0). Since a cat must have pointy ears but if an animal has pointy ears, should not be cat, we assume P(Y = 1) = 0.5 and C() = 0) = 1, P = 1) = 0.25,
P(C = 1, = 1) = 0.25, P(C = 0, Y = 0) = 0.5, P(C = 0, Y = 1) = 0.25.
Now, applying the concept of the probability of sufficiency and necessity, obtain: Probability of necessity: P(Yáo(C=0) = 0,
Probability of sufficiency: P(Yáo(C=1) 1|Y 0, =) 0) 0.5
In this example, we can state that variable has a probability of being a necessary cause.
Example.3, If we use feature 'eye size' C (taking values 1, 0.5 or 0 with the probability of 1 respectively, the lower value means smaller eye size face), to predict Y (cat 1 or fox 0). Assuming P(Yoo(==1) = 1) = 1, P(Vdo(C=0.55) = 1) = 0.5 and P(Yao(C=0) = 1) = 0 (cat have larger eye size than fox). In this example, we have P(C = Y. 0) P(C 1, = 1) = and P(C = 0.5, Y 0) P(C 0.5, Y 1) -
3-
14

---

In Definition 2.1, PNS(c, é) can take multiple choice. We provide Case. 1: 1 and č 0.5 and Case.2: c= and
Case. 1 In this case, PN = P(Ydo(C=.5)) = 0C = 1)=
PS P(Yao(C=1) = 1 0, C 0.5) =
(1, = PNP(C = 1,Y = 1) PSP(Y = O, 0.5 Case.2 In this case, PN (( 0 1,Y 1)
PS = P(Ydo(C=1) = 1| C, -)) 1.5
P = + PSP(Y 0)
We note that Case. I indicate the feature C has more sufficiency than necessity. Thus, if C' is not binary, we should consider the worst-case PNS value.
We introduced a PNS risk to investigate the PNS value between the representation and Y. When the algorithm optimizes the objective function to minimize the PNS risk, it indicates that the representation we found contains more sufficient and necessary causal information.
Considering there are multiple choices of and č (like Example.2), extend our algorithm by min-max optimization (Eq. in the main text), which aims to find the worst ē for c with highest PNS
risk.
A.2 Causal Assumptions and Invariant Learning
Our assumption of the causal graph in Figure 1 is based previous works out-of-distribution
(OOD) generalization, such as the causal graph in (Liu et al., 2021a; Ahuja et al., 2020b, 2021), they conclude the assumptions in OOD generalization task (1) fully informative invariant features (FIIF): Feature contains all the information about the label that is contained in input. (2) Non-spurious: The environment information is not correlated with the causal information.
(2) partially informative invariant features (PIIF). Our assumption X 1 Y C holds in the case of FIIF. As presented in Ahuja al. (2021) page 3, IRM is based on the assumption of PIIF, where X Y C does not hold and IRM fails in the case of FIIF. These three causal assumptions are shown in Figure 1 (b).
Given that in the domain generalization problem, the target domain is unavailable, 33 and 1) cannot be optimized directly. Thus, instead of directly optimizing the term Sx. we address the OOD generalization problem based theoretical results in Theorem 4.3, which shows that the algorithm can identify the invariant features. We will then take the invariant learning under Assumption 4.2(1) example show the relationship between invariant learning and satisfaction of Exogeneity. Theorem 4.3 establishes the equivalence between learning to optimize the Eq. (8) and intuitively demonstrates that by optimizing the objective function, the method learns representation C that satisfies conditional independence. Specifically, the logic is as follows:
i) In Section 4.3, describe that paper is based on the assumption of conditional independence X Y|C (PII assumption in Ahuja et al. (2021)), where is the invariant variable.
ii) Theorem 4.3 describes that the proposed algorithm makes representation satisfy such conditional independence. The proof of Theorem 4.3 indicates the learned representation is minimal suffi- cient statistics of Y (Definition F.2). Therefore, the learned representation identifies the essential information relative to in cause C theoretically.
Combining the above two points, the conclusion of Theorem 4.3 implies that the invariant variable can be learned by objective function Eq. (8).
A.3 Framework on Domain Adaptation
In the main text, we provide the learning framework by PNS on OOD generalization task with the practical algorithm. Compared with OOD generalization, Domain adaptation is task with the data from test distributions provided the learning process. The framework can be extended to the Domain Adaptation task, extra samples from the test domain help the method to get better generalization performance, Same with the learning framework for OOD generalization, we start from Proposition 3.1. The Eq. (5) is adoptable in the domain adaptation tasks. In that case, the
15

---

observation data x in the test domain is provided during the source process. Therefore, the terms in Eq. (5) which do not require the label information Y can directly evaluated on the test domain. The same with OOD Generalization, for the terms which need to be calculated from label information, we link the test risk RG and source risk R, by the divergent measurement BK (T](S). The divergence between T and S in infinite norm measures support of the source domain that is included in the test domain. We define i's as the distribution the part test domain distribution 7 which is not included in S, we give the upper bound of the worst risk below.
1e [x V) Px(X X & supp(S)) sup Re (w, (.
The value of 77, is always lower than P(x.g)>~T ((z, v) & supp(t)), which indicates the data distribu- tion for domain I. not covered by domain 8.
Theorem A.1. Given a source domain S and a test domain T. when T(x) is provided then the risk on the test domain is bounded by the risk source domain as follows.
Rs w, &. S lim MY (6, E) ( -) +m, k-++0
Theorem A.I shows the face of our proposed framework under a domain adaptation perspective. In domain adaptation task, we can evaluate the are not available in real-world scenarios, we only have the data samples from the test domain. The proof of Theorem A. is similar Theorem 3.2, the difference is that domain adaptation, the term (ó. {)) can be directly estimated on the provided test data. Because this term does not require the label information.
A.4 Limitations
Firstly, we propose a risk satisfying the identification condition Exogeneity under the assumption of a common causal graph in OOD generalization. However, there exist corner cases of causal assumption like anti-causal and confounder, etc. Hence, we plan to extend our framework with more causal assumptions. In addition, the theorem in our paper is based on the linear classification function. Future work would look into more complex functions in non-linear settings. We leave this exciting direction for future work is out the scope of this paper.
B Implementation Details
In this section, introduce the experimental setups and implementation details include the generate rules of synthetic dataset, real-world benchmarks, evaluation strategies, model architecture and hyperparameters setting.
B.1 Synthetic Dataset
In order to evaluate whether the proposed method captures the most essential information sufficient and necessary causes or not, we design synthetic data which contains four part of variables:
Sufficient and necessary cause (SN): the sufficient and necessary cause is generated from Bernoulli distribution sn; (005),, and the label Y/i generated based on the sufficient and necessary cause where = sn, + B00.15). Since Y is generated from SN E 1). The sufficient and necessary cause has high probability of P(Y OJdo(SN = 0)) + P(Y 1]do(SN = 1)).
Sufficient and unnecessary cause (SF): From the definition and identifiability results of PNS, the sufficient and unnecessary cause SF E {0, 1 in synthetic data has the same probability with SN, i.e. P(Y = (SF = 1)) = P(Y = 1 doo
1)). but has lower the probability of P(Y = OJdo(SF 0)) than P(Y Oldo SN = 0)). To generate the value of sf; we design transformation function fat {0, 1} + (0, 1} to generate sf, from sufficient and necessary cause
value sn,
sf; = far(sn,) (0011) where sn, = 0
(10)
sn;
where sn; =
From the functional intervention defined by (Puli et al., 2020; Pearl, 2009; Wang Jordan, 2021), we demonstrate the identifiability property to connect the SF and Y in following lemma:
16

---

Lemma B.1. Let SF == fa((NN, the intervention distribution P(Y|do(SF= = sf.)) is identified by the condition distribution PS =-
proof:
P(Y do(soF==FBF = / (lyldo(SN)))(SNNI((SN) = sf,)d SN
(11)
P(oISN)p(SN((f((S)) = sf.)d SN.
The lemma shows that even Y is only generated from SN in our synthetic simulator, the sufficient cause SF is exogenous relative to Y.
Insufficient and necessary cause (NC): From the definition and identifiability results of PNS, the insufficient and necessary cause has the same probability of P(Y OJdo(NC = =0) with P(Y 0 (Sdo(SN = 0)) but lower the probability of P(Y = 1|do(NCC = 1)) than P(Y 1odo = 1)). To generate the value of NC, we design transformation function fne {0, 1] - {0, to generate ne; from sufficient and necessary cause sn,, The generating process of ne; is defined below, and ne; is the cause of y. Similar with identifiability result of SF in Lemma B.1, NC is exogenous relative to Y.
ne; = fnc (sn.) == sn, BO0.9)
(12)
Spurious: We also generate the variable with spurious corrlated with sufficient and necessary cause. We set the degree of spurious correlation as s, the generator is defind as sp, = 8 * sn; * 1, (1 - (), 1), where (0, 1) denotes the Gaussian distribution, we select d = in synthetic generative process. When gets higher, the spurious correlation becomes stronger in the data sample. We select s 0.1 and 0.7 in synthetic experiments.
To make the data more complex, we apply non-linear function to generate x from (sn,, SF;, 1; nei, sp;}. We fistly generate temporary vector, which defind as [sn; 1a, SF; ld. DC; 1d. sp, la] + (O0, 0.3). Then we define functions Kı (t) = t t 0.5 if t > 0, otherwise otherwise N2(t) = 0. x generated by a (x) (t)). where Rd - IR is sigmoid function. We generate 20000 data samples for training and 500 data samples for evaluation.
(t) and (t(t) ++0.5
B.2 Experiment setup on synthetic data
Methods. In the synthetic experiment, we compare the proposed CaSN with the reduced method CaSN (-m). the CaSN(-m), we remove the monotonicity evaluator MW (t), {) and the 8's constraint ||c lc- 0 2 5 from the objective Eq. (8).
Evaluation. We evaluate the distance correlation (Jones et al., 1995) between the learned represen- tation é; and four features {sn;, sf,, ne,, sP; J. For example, the larger distance correlation value between è; and sn; means è; contains more information of sn,-
Model Architecture. For the synthetic dataset, we use the three-layer MLP networks with an activate function the feature inference model. Denoting Ve weighting parameters, the neural network is designed as V (VLLUVL)LL(( where ELU() is the activation function (Clevert al., 2015). The dimension of hidden vectors calculated from Vi, V2, Va are specified as 64, 32, 128 separately. Since the output of the feature learning network is consist of the mean and variance vector, the dimension of representation 64. The prediction neural networks w which predict y by representation c.
B.3
Experiment setup on DomainBed
Dataset. In addition to the experiments synthetic data, we also evaluate the proposed method on real-world OOD generalization datasets. We use the code from the popular repository DomainBed (Gulrajani & Lopez-Paz, 2020), and use the dataset which is downloaded generated by the DomainBed code. The dataset includes the following three:
PACS (Li et al., 2017): PACS dataset contains overall 9, 991 data samples with dimension (3, 224, 224). There are 7 classes in the dataset. The datasets have four domains art, cartoons, photos, sketches.
17

---

VLCS (Fang et al., 2013): VLCS dataset contains overall 10. 729 data samples with dimension (3, 224, 224). There are classes in the dataset. The datasets have four domains Caltech101, LabelMe, SUN09, VOC2007.
The DomainBed randomly split the whole dataset as training, validation and test dataset. Baselines. For OOD Generalization task, we consider following baselines realized by DomainBed.
Empirical Risk Minimization (ERM) (Vapnik, 1999) (ERM, Vapnik [1998]) is common baseline that minimizes the risk on all the domain data.
Invariant Risk Minimization (IRM) (Arjovsky et al., 2019) minimize the the risk for different domains separately. It extract the representation on all the domains and project them on shared representation space. Then, all the domain share one prediction model. The algorithm is formed as bi-level optimization objective.
Group Distributionally Robust Optimization (DRO) (Sagawa et al., 2019) weigh the different domains by their evaluated error. It reweights the optimization of domains in objective. The domain with a larger error gets a larger weight.
Inter-domain Mixup (Mixup) (Xu et al., 2020; Yan et al., 2020; Wang et al., 2020), ERM is performed for linear interpolation of samples of random pairs from domains and their labels.
Meta- Learning for Domain Generalization (MLDG) (Li et al., 2018a) uses meta learning strategy (Finn et al., 2017) to learn the cross domain generalization.
MMD method for domain generalization (Li et al., 2018b) method uses the MMD (Gretton et al., 2012) of the feature distribution to measure the distance of domain representation. They learn the invariant representation across domains by minimize MMD.
Neural Networks DANN (Ganin et al., 2016) uses adversarial networks to learn the invariant features across domains.
Class-conditional DANN CDANN (Li et al., 2018c) is extension of DANN, which is learned to match the conditional distribution by giving the label information.
Evaluation. All the evaluation results are reported from the DomainBed paper (Gulrajani & Lopez- Paz, 2020). We use evaluation strategy from DomainBed. DomainBed provides the evaluation strategy Training-domain validation set. The training dataset is randomly split as training and validation datasets, the hyperparameters are selected on the validation dataset, which maximizes the performance of the validation dataset. The overall accuracy results are evaluated on the test dataset rather than the validation dataset.
All the experiments are conducted based on server with a 16-core CPU, 128g memory and RTX 5000 GPU.
Implementation Details. We implement CaSN based on the DomainBed repository. The feature extractor and classifier different neural networks across different datasets.
We set distribution of representation C as (CIX = x) - (f((x;;)) Φ),, ax; x)) and its prior as TC =N [Noo, oo). d4 and do pre-defined and not updated in the learning process. Similarly, for C we define (C) x) N (ā(x: {), (xx: {)) and मe NN oo). Colored Mnist: The model architecture on Colored Mnist dataset is given by DomainBed repository. We use MNIST ConvNet for feature extraction. The details of the layers
referred from Table 7 in Guirajani & Lopez-Paz (2020). We simply use a linear function as the label prediction network and transformation function T. In the Colored Mnist dataset, the variance of c is fixed as 0.001.
The model architecture on PACS and VLCS datasets are both given by DomainBed repository. They use ResNet-50 for feature extraction. In DomainBed, they replace the last layer of ResNet50 pre-trained on ImageNet and fine-tum tune and freeze all the bach normalization layer before fine-tune. We simply use linear function as the label prediction network w and transformation function T. In the PACS and VLCS datasets, the variances of e are also fixed as 0.001
PACS and VLCS:
The Hyperparameters are shown in Table 3. The general hyperparameters (e.g. ResNet, Mnist, Not Minist) are directly given from Table 8 Gulrajani Lopez-Paz (2020). All the experiments run for 2 times.
18

---

Table 2: Results on Colored Mnist
Condition
+90%
+80%
-90%
Avg
Min
ERM
71.7 + 0.1
72.9 + 0.2
10.0 + 0.1
51.5
10.0
IRM
72.5 0.1
13.3
52.0
10.2
GroupDRO
73.1 0.3
0.2
10.0
52.1
10.0
Mixup
72.7 + 0.4
0.1
1011
52.1
10.1
MLDG
7.2
0.2
9.8
51.5
9.8
MMD
0.3
0.2
9.9
51.5
9.9
DANN
7.94
7.1
1.00
51.5
10.0
CDANN
72.0
0.2
10.
51.7
10.2
CaSN (Ours)
0.1
73.7 0.1
10.3 0.3
52.2
10.3
Table 3: Hyperparameters setting
Parameter
Default value
Random distribution
batch size
32
Unilorm (3,5.5)
Basic
minimization process learning rate
0.0001
10 Uniform (-5,-3.5)
maxmization process learning rate
0.00001
10 Uniform (-6,-4)
weight decay
10 Uniform (-6,-2)
Not Mnist
generator weight decav
10 Uniform (-6,-2)
weight decay generator weight decav
Mnist
0.7
{0.3, 0.7, 1.0. 1.5, 3.0)
CaSN
0.01
{0.001, 0.01, 0.1]
Weight of constraint |/c E||2
0.1
(0.001,0.01,0.1,, 0.73
0.7
1.0, 1.0,
0.01
0.1.0,1011
CaSN(ir)
Weight of constraint ||c E||2
0.1
(0.001, 0.01, 0.1, 0.1.0,0..100,,00.7
Weight of IRM penalty Lim IRM penalty iters
0.001
00.01, (500, 1000)
1000
0.7
{0.3, 0.7, 1.0,
0.01
(0.001, 0.01, 0.1, 0.7,
CaSN(mmd)
Weight of constraint |/c - Weight of MMD penalty Lmmdd
E|I2
0.1
{0.001, 0.01, 0.1, 0.7, {1}
Adversarial
Max optimization per iters
500
{500, 1000}
B.4 Experiment setup on SpuCo
We provide the experiment on the large scale spurious correlation dataset SpuCo (Joshi et al., 2023). SpuCo is Python package developed address spurious correlations in the context of visual prediction scenarios. includes two datasets: the simulated dataset SpuCoMNIST and the large-scale real-world dataset SpuCoANIMALS, This Python package provides code for benchmark methods these datasets, along with test results.
Dataset. We test CaSN on the large-scale real-world dataset SpuCoANIMALS, which is derived from ImageNet (Russakovsky et al., 2015). This dataset captures spurious correlations in real- world settings with greater fidelity compared to existing datasets. There are 4 classes in this dataset: landbirds, waterbirds, small dog breeds and big dog breeds, which are spuriously correlated with different backgrounds. Based the different backgrounds, this dataset contains groups with more than 10, 000 samples.
Baselines. We realize CaSN based on the code of SpuCo. We have CaSN implementation, one is based on ERM, the other based on the strategy of Group Balance, We compare CaSN with ERM, GroupDRO and Group Balance.
19

---

Table 4: Results on SpuCo
ERM
CaSN
GroupDRO
GB
CaSN-GB
Average
80.26+4.1
84.34+0.6 9.722.7
50.7+4.2
49, 19,9+1.4 .4
50.5447.6
Min
8.3+1.3
36.740.6
41.1+2.7
42.0+0.8
Hyperparameters. The hyperparameters employed for robust retraining detailed as follows. During the robust training phase, we set the hyperparameters as their default value:
When conducting training from scratch, we utilize SGD the optimizer with a learning rate of 0.0001, weight decay of 0.0001, batch size of 128, and momentum of 0.9. The model undergoes training for 300 epochs, with early stopping applied based its performance the validation set. In addition to the basic hyperparameters, we set and {0.005, 0.01}.
C Additional Results
C.1 OOD generalization results on Colored MNIST
Due to the page limitation in the main text, we show OOD generalization results on Colored Mnist data in Table 2.
C.2 Domain generalization on SouCo
The results on SpuCo (Joshi et al., 2023) based on the code SpuCo". We test CaSN on SpuCoAnimal which comprises 8 different spurious correlation groups.
We set hyperparameters as
and 0.005, 0.01, while the remaining parameters followed SpuCo's default values. We conducted two types of experiments: the first involved training the model without providing any additional information, and the second involved resampling based on the spurious correlation group information, where the base models corresponded to ERM and Group Balance (GB) as presented in SpuCo. We also include GroupDRO as one the baselines, baseline performance is reported SpuCo. Data augmentation-basel methods, ERM* and GB were not included these experiments.
We reported the results in Table 4, with each result obtained from fixed random seeds. The baseline results are directly taken from SpuCo. Our method showed higher average accuracy on average accuracy compared to the baseline, and even the worst spurious correlation group exhibited higher accuracy than the baseline.
D Proof of Theorems
In this section, we provide the proof of the risk bounds which include Proposition 3.1, Theorem 3.2 and Theorem 3.3 for OOD generalization task.
D.1 Proposition 3.1
To explicitly form the Monotonocity evaluator, decompose the original objective by three terms de- fined by sufficiency objective SF,(w, (T((w)) Φ), necessity objective NC, (w, {) and Monotonicity evaluator objective Mt (Ø, E). The Monotonicity M," (Ø) E) term can be decomposed as
(w, ()) (L.-SF((,))).CCG MM (6. E SF.(w, (1 (w.(w,
(13)
The following equation understands the above decomposition.
P(sign(w w T c) = sign(w 2))
(14)
=P(sign( w Tc) = y) P(sign (w 2) y) + P(sign(wTTe c) P(s [T) #))
20

---

We can further derive Eq. 13 as follows.
MM (0. =SF, ( (o),,,)))ccc..
(F) NN,, -2SF((..)))C.
(15)
R.(w.o.T)
(w, 0, -.,.FsWWWWW.. N)W,))NCCWWWWW
Then we can rewrite the original objective Eq. by)
Re(w, 0. (6.5) 2SF (C
(16)
Then get the results of Proposition 3.1. The reasons why we need this proposition are because the final objective need to explicitly evaluate the Monotonicity.
D.2 Theorem 3,2
The motivation Theorem 3.2 is to bridge the gap between the risk on the source domain and the risk the test domain. To prove the result in Theorem 3.2, refer to the technicals in Germain et al. (2016), We first define o = E(x,)>>I[(( y) & sup(S)), then we can get the value of 5-Monotonicity measurement on the samples from test domain that not included in source domain is:
E(x,))~T((xx, y) $ =olE, B Usign(("
( Usiggu "c) sign(w [c]]
sign(w Ta] oM," (b)
Similarly, the overall risk on the samples from the test domain that is not included in the source domain is 7 (Y.Y..
Then we change the distribution measure, we also take MM (0.E) of Eq. (5) as an example.
(M
=
c) sign(w TT)] 2)
T -E
Tc) c) sign w c)] (e.
S SBA
P [ssign (w' T c) sign w - - MN (0,E)
cxx=
[TISS]
( B
I/sgn w Tc) sign w = + o. (0.
(17)
The third line is due Hölder inequality. For the last line, we remove the exponential term / in I[sign(w w c) sign(w c)] न since the function take the results from {0, 1}. Similarily on term SF (F,.w.q Φ), we can get the final bound of overall R, (w, a. {) as Eq. (7) shows.
D.3 Theorem 3.3
In this theorem, we study how the risk on distribution is bounded by empirical risk. The proof of theorem refers to popular inequality Jensen's inequality, Markov inequality and Hoeffding's inequality. We first focus on the term SF.(w. (w,@), Φ). The sketch of the proof is that firstly we will use the variational inference process change the measure of distribution. Then, we use Markov's incquality to calculate the bound of risk.
21

---

Define A(SF, 6)) SF,(W, 6) (F.(W. o). We apply the variational inference trick and use
Jensen's inequality to get the following inequality:
A(SF((w,))
=FF, Ø) SF. (w. ②)
< Eg KL P P (C = x) TT) 2(n 1) In P ( = x)
TC
+ In Be exp ssign( w c) # v])
In BeNto exp (EsT(sign( w/ Tc) # vl)
(18)
Po(CI =x)
EL ( x) TT) EsE py (C|--)
TC
In Be exp (A (S)),
Eg
EL KL
p (C x) TT) (CX =
In Be exp A (5)),
where A (S) = B I[sinn( c) + y| - [Es[siig( w Tc) a v/1. Recall that Hoeffding's inequality, we get the following inequality.
PIA(S) 2 n) S exp(-2m)11
(19)
Then, denoting the density function of (S)) as f(A(S))
P(A(S)
2nn7
00
f(A(S))dA(S) 2nm
(T)) Anne 2nn?
Then, we get
Es Es|exp (2 1))3
/ (x)())))xp((mmm-)11))) -
(20)
<
(1 (S)
= - n exe (-2A
(1 - 2 m <
Combining Bq. (20) with Eq. (18). Suppose g(A(S)) In B.c (exp(2(n- since have,
Es Bs (exp (2(n 1)42 (S))) < n
by Markov's inequality, we further get,
P(s))o(A(S)) 2 n| < e"
(21)
Suppose that 17 In(n/e), and with the probability of least e, we have that for all Te-
2 1) In Bxcalexp (A² (S)) < In
(22)
Since AS E [0, 1], then we have,
exp(A?(S)) < (exp(A(S))) e -eep)(AA3)
(23)
22

---

The last inequality due to exp (xp(A?(S)) (exp(A(S)))² is monotonically decreasing when AS E [0, 1]. Then, according Jensen's inequality, we conclude that
In( exp A (5))² In (ex A (S))²
< In(e (C) exp A (5)) -
1
In n +1
2(n
(24)
1
In (x) <
In
4(n - 1)
2
Then,
ISF -F
< <E (C) - (XX= + 1
+ 1
4(n - In(n/e)
(25)
1
< EL = + (CX + 1(n-1) In(n/c)
2
According to the assumption, we have
= x)|[=c) + 1 4(n In(n/e)+ +
SSF (w, σ) SF,(w, 6)) S Es
(26)
We get the results demonstrated in Theorem 3.3 (1).
For the term (ó. we define (MM)) MM (o. (d. where M <)
Es- Ef Pf P [[sign(w w c) sign e)]. Different from Theorem 3.3 (1),
the monotonicity measurement has an extra expectation on We apply Jensen's inequality again and then use the variational inference trick to get the derivation results.
4(n 1) (M,)² 4(n 1)3 ( AM (0.E) - M, (0.5))
(27)
Then, we consider the term M (d, E) and ( {) separately.
M (d, E)
EsLE en of Ba (C [ssin((w c) sign(w' Ec]
Po = x)
E.E. In P5 =x)
Eg In
TC
TC
+ E. In
TC
T exp(Tssign(w c) sign(w Sig]() (28)
(C P
< (KLL)s((K((Ppp)
x) TT) KL ( = x)][=c]]
+ In Enwx Eenne exp (EEsE w T c) sign( (w E))).
Similarly, for the empirical risk M. (t)
Mw (Ø,E) = E(x.u)= (C) xx) E eB (C Isign( ww c) = sign(w') Ta)
P (C = x)
E.Eg In Ee ( =x)
Ess E. In
TC
AC
TC
FC exp(I[sign(w c) = sign(w Ta))
(29)
+ E. In
< (x xx)
TC) -XX =
+ In Eerxe Ee exp (E.. I[sinn w c) sign(w (w T E)]).
Combining Eq. (29) with Eq. (28) and plugin to Eq. (27), we have 4(n 1)22 (M.)² 4(n 10-111 1)2 M (0. NT (c)
< (2(n 1)(E KT, P.0 (C = x)][=C) + Es- (C
+ In Berne Ee exp (2 {)a(M)))
where (M.) = Es= [(sin] ( Tc) = sign(w w Ta)] - EEs Tssgn Tc) = sign Ta)].. The rest of the proof is similar to Theorem 3.3 (1), thus get the theoretical results of Theorem 3.3 (2).
23

---

E Satisfaction of Exogeneity
In this section, we provide the proof of Theorem 4.3 and demonstrate why minimizing the objective equivalent to finding the C satisfying conditional independence.
The proof process consists of three steps: (i) proof the optimization of
min SF. (w, の) + KL (C)X x)][=c) 6.W
(30)
equivalent with the optimization of Information Bottleneck Shamir et al. (2010a) objective Lib max / /CC, -)--((X C), where I (A, B) denotes the mutual information between A and B. X, Y are from S" (ii) The optimal solution of Information Bottleneck satisfies X T C. To simplify the writing, we represent (.(-) by P(-).
For step (i): The objective Eq. (30) is coincide with the objective of variational autoencoder (Doersch, 2016) which is proved to be equivalent
the IB objective. The theoretical results provided in Alemi et al. (2016), and we report the proof process from the notations in our paper. The derivation starts with bound the I(C,Y) Y) and T(C, X) separately, for the term I(C, Y),
P(Y,C) C) T(C,Y)= = f P(Y. C(Y,C) C) log P(Y)
dYdC = / P(Y. C) P(Y C) dyac. P(Y)
(31)
Decompose the P(Y |C) as below
f 4XP(Y X)P(X dx P(Y X) |
P(Y - dxp(X,Y C) -
P(C)
In the process, the P(Y C) is approximated by parameterized P(Y | C). Since the KL divergence is always larger than 0,
KLJP(Y PYY о) 2 20- - / CC P(Y C)dY 2 / P(Y 1 CC) P(Y C)dY.
and hence
I(,,)) / P(Y, P(Y IC)
P(Y)
/ C(Y, P(Y [C) - -dYP(Y) log P(Y)aAac
/ P(Y, P(Y C) + H(Y)aYdC
Then (CCY) is lower bounded by follows:
T(C,Y) > / P(X))(Y X)P(C) dXdYdC) log P | C)
Then, consider the term AC,C, is decomposed by following equation:
/ م () (c| dCax
T(C,X)=
P(C)
(32)
/ (x C) Pa(C X)dCaX - / PgC) P(C)aCaX.
It is upper bounded by
PC X) P(C)
X) I(C S P(X) P
dXdC
where P(C) prior of C. Combining the upper bound of I(C,X) and the lower bound of I(C, Y) together, the lower bound of IB objective is
((C,)) P(X)P(Y X)P x) log P(Y C)
(33)
P(X)) log (C X)
dXdC
P(C)
24

---

From the results, we can draw a conclusion that maximizing the IB objective I(C,Y) AI(C, X) is equivalent to minimizing the objective (9) in Theorem 4.3.
For step (ii): The proof refers to the theoretical results in Shamir et al. (2010a), they correspond the optimal solution of information bottleneck with minimal sufficient statistics defined below. We first demonstrate the definition of Mininal Sufficient Statistic in Fisher (1922); Shamir et al. (2010a) below.
Definition E,1 (Sufficient Statistic Fisher (1922); Shamir et al. (2010a)). Let Y be parameter of probability distributions and X is random variable drawn from a probability distribution determined by Y. of C is function of X, then C is sufficient for Y if
Vx E C. R. E y P(X - C c, Y = y) P(X = C=
The definition indicates that the sufficient statistic C satisfy the conditional independency X J. YJC. Definition E.2 (Minimal Sufficient Statistic Fisher (1922); Shamir et al. (2010a)). A sufficient statistic C' is minimal if and only if for any sufficient statistic C, there exists deterministic function such that C' = f(C) almost everywhere w.r.t X.
From Theorem 7 in Shamir et al. (2010a), the optimization of IB is correspond finding the minimal sufficient statistic. We show Theorem as a lemme below.
Lemma E.3 (Shamir et al. (2010a)). Let be a sample drawn according to a distribution determined by the random variable Y. The set of solutions to
min /XX, C) s.t. [(Y; C) mmax (Y;C')
is exactly the set of minimal sufficient statistics for Y based the sample X.
From Lemma E.3, the process of optimizing the IB objective I(C,Y) AI, X) is equivalent to finding the minimal sufficient statistic. Then, the process of optimizing the IB objective is the process to find a C satisfying conditional independency X LYC.
From Step (i) and (ii), we get the result in Theorem 4.3 that optimizing the objective mins.w.1 n.A. Lexo equivalent finding a C satisfying conditional independency X T C.C. Considering Assumption 4.2 in our paper, we can draw the conclusion that optimizing the objective (q. is equivalent to satisfying the exogeneity.
F Additional Related Works
OOD generalization. In addition to the related works in main text, some works (Gong et al., 2016; Li et al., 2018b; Magliacane al., 2017; Lu et al., 2021; Rojas-Carulla et al., 2018; Meinshausen, 2018; Peters al., 2016) solve the OOD generalization problem by learning causal representations from source data by introducing invariance- based regularization into cross-domain representation learning and consider the task labels across multi-domains.
Domain adaptation. Domain Adaptation aims at learning to generalize to the test domain where the distribution is not the same as source domain, while the data from the test data is available during traning process. Existing works on domain adaptation use different way to achieve the goal (Pan et al., 2010; You et al., 2019; Zhang et al., 2013). Magliacane et al. (2018) considers solving the generalization problem from the causality perspective and Zhao et al. (2019) propose a framework of invariant representation learning in domain adaptation. Furthermore, Zhang et al. (2019) provides theoretical analysis of domain adaptation.
Causal discovery. In order to investigate the relationship between causally related variables in real-world systems, traditional methods often employ principles such the Markov condition and the principle of conditional independence between cause and mechanism (ICM) to discover causal structures or differentiate causes from effects (Mooij et al., 2016). Additionally, several studies have focused on the inherent asymmetry between cause and effect, as seen in the works of Sontakke et al. (2021): Steudel et al. (2010); Janzing & Schölkopf (2010), and Cover (1999). These ideas have also been utilized by Parascandolo et al. (2018) and Steudel et al. (2010). Other research lines focus on modeling structural causal models and discussing the identifiability of causal structures and functions (Hoyer et al., 2008; Zhang & Hyvarinen, 2012). The task of causal discovery typically assumes that
25

---

all variables are observable, aiming to identify the unknown causal graph. In contrast, our work deals with causal factors that are hidden within observational data, given a known causal graph. Our objective is to extract causal information from the observational data.
Causal Disentangled Representation Learning: Causal representation learning methods, such as those discussed in Schölkopf et al. (2021), aim to find the disentanglement representation from observational data with causal semantic meaning. Previous works have utilized structural causal models to capture causal relationships within complex observational data, as seen in the works of Yang et al. (2021); Shen al. (2020); Lu et al. (2021); Wang et al. (2020); Yang al. (2023), which focus on disentangling causal concepts from the original inputs. While our work also aims to specify causal representations from observational data, we distinguish ourselves by focusing specifically on identifying sufficient and necessary causes. Wang & Jordan (2021) concentrate on learning to disentangle causal representations using non-spurious and efficient information from observational data. Their framework is inspired by the concept of PNS and extends it to a continuous representation space. In contrast, our learning framework is based on the task of OOD generalization, and our algorithms consider both monotonicity and exogeneity conditions. Additionally, we provide a theoretical analysis of the generalization ability of our approach based on PAC learning frameworks, as explored in the works of Shalev-Shwartz & Ben-David (2014) and Shamir et al. (2010b).
Contrastive Learning: The proposed method is also related to another line of research called contrastive learning. These works often deal with the OOD generalization task by designing an objective function that contrasts certain properties of the representation. Saunshi et al. (2022) argue that the framework learns invariant information by introducing certain biases, and the core problem of contrastive learning is the objective function (Xiao al., 2020). Different from their approaches that perform learning by contrastivity, we use counterfactual PNS reasoning as the function to be optimized, which learns invariant causal information with an explicit stability guarantee for the model's 's performance.
G Broader Impacts
In this paper, we propose a method to specify the more critical representations based on invariant learning, where we extract the representations from the invariant information that possess sufficient and necessary causalities for the prediction task. This effectively helps improve the performance and robustness of machine learning models in unknown domains. The application of this method can promote reliability and usability in various real-world scenarios. Furthermore, through experiments on real-world datasets, our method demonstrates the ability enhance model performance even in the worst-case scenarios. This highlights the potential of our method to enhance reliability and usability in various out-of-distribution (OOD) settings. By extracting the essential causal representations from the invariant information, our method provides valuable insights into the underlying causal relationships the data, leading improved generalization and robustness in OOD scenarios. These findings support the broader impact of our approach in enhancing the reliability and usability of machine learning models across different domains and applications.
26


Reviews:
[{"review_id": "1OiW0Z8wde", "reviewer": "Reviewer_aG69", "summary": "This paper addresses the crucial issue of out-of-distribution (OOD) generalization in machine learning models, where the testing data distribution differs from the training data. To tackle this limitation, the authors introduce the concept of the Probability of Sufficiency and Necessary Causes (PNS), representing the likelihood of a feature being both necessary and sufficient. They propose a novel optimization approach, PNS risk, to enhance representations with high PNS values, effectively capturing the information of sufficient and necessary causes. The paper provides theoretical analysis and experimental results on synthetic and real-world datasets.", "questions": "Please refer to weaknesses.", "limitations": "Please refer to weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The authors propose a novel PNS risk and build the theoretical connections between PNS risk and generalization errors under some assumptions.\n* An approximate algorithm is derived to optimize the proposed risk.\n* Experimental results validate the effectiveness of PNS risk.", "weaknesses": "I have the following comments:\n* The difference between the proposed PNS risk objective and other invariant learning methods: Although the PNS risk objective is newly incorporated in invariant learning, I would like to know the key difference from existing metrics/objectives. Since the objective is also to minimize the upper bound of PNS. I am confused about this.\n* The exact meaning of the derived bounds: In Equation (7), the authors provide an upper bound of the generalization error on the target distribution. I have some concerns about the RHS: when $k\\rightarrow \\infty$, $\\beta_k$ will be extremely large, and it seems that the proposed method could not address the covariate shift problem. Therefore, I double the real effect of this bound.\n* Approximation of algorithms: In algorithms, conditional distributions are parameterized by some parameters, could you analyze the approximation error of such parameterizations? It seems that this is a very theoretical work, but there is a gap between theories and algorithms. Also, the authors do not mention how to calculate $\\mathbb E_{c\\sim P(C|X)}$, does this require multiple implementations $C$ for one given input $X$? Also, in Equation (8), why the minimization is taken over $\\phi, w$?\n* Mismatch between algorithmic design and experiments: I think this algorithm & theories are not designed for covariate shifts, which could be seen from the remaining $\\beta_k) term in Theorem 3.2. But for image classification tasks, the shift patterns are mainly covariate shifts, since one image is not likely to be given different labels in different domains. Also, for image datasets, the supports of different domains are likely to be disjoint, then why the proposed method could achieve good performance in these settings, which are not well-supported by theoretical analysis. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer aG69:\nWe would like to thank reviewer aG69's comments for our novelty as well as our experiments to validate the effectiveness of the proposed PNS risk. We respond to each of the reviewer's questions in the following.\n\n**Q1.**  **The differences between existing PNS risk and other invariant learning methods.**\n\nWe conclude the answer in G.P. 2 of General Response.\n\n**Q2.1**  **When $k →\n ∞, β_k$ will be large.**\n\nThe definition of $β_k$ is from Eq. 7 in [1], namely, $β_k$ is a transformation of widely used  **Renyi divergence** $D_k(T|S)$ (footnote in page 4 of [1]):\n\n$β_∞(T|S)=sup _{(x, y) \\in SUPP(S)}(\\frac{T(x, y)}{S(x, y)})$\n\n We can see that when $k →\n ∞, β_∞(T|S)=2^{{D_∞(T|S)}}$. When the source domain support includes the target one, the divergence does not tend to infinity as $k → ∞$. This proposition is similar to KL divergence.\n \n**Q2.2**  **The method based on Theorem 3.2 could not address the covariate shift problem**\n\nInspired by your valuable question, we will highlight the following explanations in our revision. Given that in the domain generalization problem, the target domain is unavailable, $β_k$ and $η$ cannot be optimized directly. Thus, instead of directly optimizing the term $β_k$, we address the domain generalization problem based on theoretical results in Theorem 4.3, which shows that the algorithm can identify the invariant features. Specifically, the logic is as follows:\n\n- i) In Section 4.3, we describe that our paper is based on the assumption of conditional independence $X⊥Y∣C$ (PIIF assumption in[4]), where $C$ is invariant variable. \n- ii) Theorem 4.3 describes that the proposed algorithm makes representation satisfy such conditional independence. The proof of Theorem 4.3 indicates the learned representation is minimal sufficient statistics of $Y$ (Definition E.2 in Appendix). Therefore, the learned representation identifies the essential information relative to $Y$ in cause $C$ theoretically. \n\nCombining the above two points, the conclusion of Theorem 4.3 implies that the invariant variable can be learned by objective function Eq. 8. \n\nIn discussions of Theorem 3.2, including Eq. 7, we express that invariant feature causes $β_k$ to decrease and narrows the bound. Theorem 4.3 suggests that it's theoretically possible to learn an invariant representation through the objective function. In domain generalization, even though the bounds may account for the divergence between training and target domains, the prevalent approach is to learn generalization by learning invariant representations rather than directly optimizing such divergence, as mentioned in Section 3.2.2 [2].\n\n**Q3.1**  **The approximation error of parameters P(C|X).**\n\nFrom a causal perspective, given that the ground truth for C is not provided during training, our primary concern is the identifiability of C rather than the approximation error. Theorem 4.3 is key to identifiability. Satisfying identifiability ensures that, given infinite model capacity, there won't be a significant gap between approximation error and true error.\n\nIn experiments, our synthetic data provides ground truth information of C. Results in Figure 2 present that we can approximate SN (PA is a typo), SF and NC (information of C).\n\n**Q3.2 How to calculate $E_c$?**\n\nThank you for your question. We did not elaborate $E_c$ in our paper detailedly, which may lead to misunderstandings. The expectation is on the distribution of C parameterization by a certain $ϕ$. The mathematical formulation of inferenced representation distribution and its expectation is commonly used and aligns with the general approach of Variational Inference, such as the Variational Autoencoder(VAE).\n\nOur implementation mirrors VAE: we first infer the Gaussian distribution's parameter of representations through an encoder (lines 654-656 of appendix), then sample from this distribution. The expectation is calculated on c but not on $ϕ$. We will add discussion to prevent confusion in revision.\n\n**Q3.3**  **Why the minimization is taken over $ϕ, w$?**\n\n$ϕ，w$ and $ξ$ denote the parameters of the representation encoder, classifier, and intervening distribution. Minimizing $ϕ，w$ aims to infer a better representation that can correctly predict label.\n \n**Q4.1**  **Mismatch between algorithm and experiments. This algorithm & theories are not designed for covariate shifts. Why good performance?**\n\nThank you for pointing out this potentially confusing problem. We will give detailed explanations for the priority of our proposed algorithm, i.e., our algorithm is designed for the mentioned shift.\n- Algorithm design. The causal assumption $X⊥Y|C$ indicates that given invariant feature $C$, $X$ and $Y$ are independent. Specifically, the distribution shift caused by domain-variant features is unrelated to $Y$. Theorem 4.3 suggests our algorithm theoretically satisfies $X⊥Y|C$ and learns the invariant representation.\n- Algorithm eveluation. We experimentally chose covariate shifts to validate our method since, within such shifts, Y remains unchanged despite domain variations if a certain image is provided. A good performance on covariate shifts implies our algorithm can empirically identify representations satisfying $X⊥Y|C$.\n\n**Q4.2** **The supports of different domains are likely to be disjointed.**\n\nIn our paper, we considered the domain disjoint problem following[1]. We introduce the term $η_{t /\\ s}$. If the support sets of two domains match, this term becomes zero. Similar to $\\beta_k$, the term $η_{t /\\ s}$ cannot be optimized directly in domain generalization, but it will lower if there are invariant features.\n\n[1] Germain et.al. A new pac-bayesian perspective on domain adaptation. \n\n[2] Wang et.al. Generalizing to Unseen Domains: A Survey on Domain Generalization.\n\n[3] Shen et al. Towards out-of-distribution generalization: A survey. \n\n[4] Ahuja et al. Invariance principle meets information bottleneck for out-of-distribution generalization. "}, {"review_id": "hDcqvRXCK1", "reviewer": "Reviewer_jeo8", "summary": "A mostly theoretical paper that formulates the necessity and sufficiency of causal variables in order to optimize models to rely on necessary & sufficient variables. The paper provides rigorous theory connecting the empirical loss when models are optimized using the Probability of Necessity and Sufficiency Loss (PNS). Finally, there are some empirical results verifying the effectiveness of this approach. ", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1) Rigorous theoretical guarantees for OOD generalization when optimizing with the introduced PNS loss on source domain S. Builds upon prior well-established theory. \n\n2) Clear and well-explained intuition of using necessary and sufficient causal variables to prevent performance degradation when generalizing to unseen domains\n", "weaknesses": "1) Rigorous empirical evaluation in the presence of more realistic datasets could help this paper be even more convincing. Evaluating on the recent more challenging dataset SpuCo for spurious correlations where existing methods fail can be a good starting point. Alternatively, considering other datasets from the WILDS package would be another useful direction. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer jeo8:\n\nWe thank reviewer jeo8 for their suggestions and appreciate their recognition that our method is intuitive and our theory is rigorous. We will address each of the questions posed by the reviewer in the sections below.\n\n**Questions. Rigorous empirical evaluation in the presence of more realistic datasets like SpuCo and WILDS could help this paper be even more convincing.**\n\nThank you for your suggestion! We obtained some new results on SpuCo[1] based on the code [SpuCo](https://github.com/BigML-CS-UCLA/SpuCo). Our experimental data is SpuCoAnimal which comprises 8 different spurious correlation groups.\n\nWe set hyperparameters as $\\delta=3$ and $\\lambda\\in{0.005,0.01}$, while the remaining parameters followed SpuCo's default values. We conducted two types of experiments: the first involved training the model without providing any additional information, and the second involved resampling based on the spurious correlation group information, where the base models corresponded to ERM and Group Balance (GB) separately. We also include GroupDRO[2] as one of the baselines, the baselines performance is reported SpuCo[1]\n\nData augmentation-based methods, ERM* and GB*, were not included in these experiments.\n\nWe reported the results below, with each result obtained from 4 fixed random seeds. \n\n|     | ERM  |  CaSN    | GroupDRO| GB  | CaSN-GB  |\n|  ----  | ----  |----  |----  |---- | ---- |\n|  Average  | 80.26±4.1  |84.34±0.6  | 50.7±4.2 |49.9±1.4 | 50.54±7.6 |\n|  Min  | 8.3±1.3  | 9.7±2.7  | 36.7±0.6 |41.1±2.7| 42.0±0.8 |\n\nThe baseline results are directly taken from SpuCo[1].  Our method showed higher average accuracy on average accuracy compared to the baseline, and even the worst spurious correlation group exhibited higher accuracy than the baseline. We plan to continually update the results by sufficient hyperparameter tuning in revision.\n\nRegarding the WILDS dataset, it is too large and we have not been able to obtain results due to computational resource limitations. We will report the WILDS dataset results in the revision.\n\n[1] Joshi S, Yang Y, Xue Y, et al. Towards Mitigating Spurious Correlations in the Wild: A Benchmark & a more Realistic Dataset[J]. arXiv preprint arXiv:2306.11957, 2023.\n\n[2] Sagawa S, Koh P W, Hashimoto T B, et al. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization[J]. arXiv preprint arXiv:1911.08731, 2019."}, {"review_id": "XUjALZGVjq", "reviewer": "Reviewer_qVZ2", "summary": "The paper proposes a new formulation of the out-of-distribution generalization task via finding necessary and sufficient features, similar to invariant feature learning but with some added constraints.\nThe paper uses the definition of necessary and sufficient from Pearl (2008) and proposes a related risk measure.\nThen, a connection between source and test risks is given along with assumptions needed for the bounds to hold. \nFinally, the paper proposes a practical adversarial algorithm to minimize the proposed objective and presents empirical results on DomainBed and a toy simulated dataset. \n", "questions": "- Do you limit the number of hyperparameter choices to a fixed number for every method? I believe DomainBed (or maybe WILDS) fixes the number of hyperparameter choices allowed for each method. This means that methods with more hyperparameters are harder to fit and thus may perform worse on average.\n\n- What is PA in Figure 2? I'm guessing that is a typo and should be SN?\n\n- Why not call OOD Generalization the more standard term of \"domain generalization\"?\n", "limitations": "- The paper does not discuss the practical limitations or computational complexity of the method. The paper does not acknowledge that adversarial learning is inherently a very difficult problem both theoretically and practically. Were any instabilities encountered during training? How were these handled? It seems there were two encoders trained but this would seem to increase training instability. What about the constraint in Eq 8? How is that enforced in practice? Again, this seems to be a very difficult constraint to maintain. Furthermore, the KL term likely requires the distributions to be Gaussians to allow closed for computation, or did you use something else?\n\n- The paper acknowledges some of the limitations with respect to theory. More discussion on the assumptions and which are reasonably likely to hold in practice or not would be helpful. Also, how bad will the theory break if the assumptions do not hold? \n\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes an interesting new direction to find necessary and sufficient features and proposes a risk based on this objective.\n\n- The paper theoretically connects the target risk and source risk based on the theoretic objective.\n\n- The paper provides reasonable results on PACS and VLCS and a toy simulated dataset to validate the theory.\n", "weaknesses": "- PNS needs to be explained and discussed more. This is a very difficult concept to grasp theoretically. Also, Definition 2.1 seems incomplete. What are $c$ and $\\bar{c}$? How can just two realizations be used to determine necessity and sufficiency? Is it some expectation over $c$ and $\\bar{c}$? Even theoretically, how would I come up with $c$ and $\\bar{c}$?  After looking at (Pearl 2009), it seems that it only deals with binary variables which would make more sense. Is this an extension of (Pearl 2009)? If so, this needs to explained more.\n\n- What is the distribution of the $\\bar{C}$ variable (even in theory)? This again is important missing detail. This is not explained except that there is another auxiliary distribution. It seems to be a completely independent random variable but it is unclear what distribution it is or should be in theory (or in practice).\n\n- It is not explained why the monotonicity term can be \"absorbed\" into the monotonicity measurement (Line 144). Also, why does this make sense as a monotonicity term? Why would this encourage monotonicity? Again, part of the confusion is that it is completely unclear what the distribution of $\\bar{C}$ should be in theory.\n\n- For equation 6, is $\\mathcal{T}(x,y) = P_t(x,y)$? If so, then this is the expected ratio to the $k$-th power? But this isn't a divergence because if $\\mathcal{T} = \\mathcal{S}$ this \"divergence\" would be 1. Thus, it does not even satisfy the most basic property of a distribution divergence. I also could not find the definition of $\\beta$ divergence quickly in (Gong et al. 2016). Could you reference the specific definition?\n\n- Again, assumption 4.1 is unclear. And perhaps this could aid in answering the questions above. But it seems that the distributions of $C$ and $\\bar{C}$ need to be different. Yet, again, I am not sure why as the paper does not explain $\\bar{C}$ well.\n\n- Theorem 4.3 contains typos and seems to be incomplete. The statement after the equation is not a complete sentence and does not match the previous sentence.\n\n- The paper lacks a direct comparison with related works like IRM. How is the proposed objective or algorithm fundamentally different or similar to IRM or related methods? A direct comparison of the final equations would aid in understanding how this work fits in with related work.\n\n- The paper lacks discussion on the limitations of the practical optimization algorithm especially since this is a new adversarial optimization algorithm. See limitations comments.\n\n**Minor:**\n- The examples of necessary and sufficient features could be clarified. Perhaps just a 2 x 2 table of with necessary/ not necessary and  sufficient/not sufficient. And then, just fill in each box with a feature. This might be simpler than having an example that takes careful analysis. Also perhaps showing with arrows, it might be easier to show. Like whiskers <-> cat, cat feet -> cat, pointy ears <- cat...\n\n- The figure is in the completely wrong place. Figures should always be placed after they are referenced and not before.\n\n**Review summary**\nOverall, I think the paper could be very good. The perspective is fresh and introduces some new concepts. However, the lack of conceptual and notational clarity and other weaknesses hinder it from being a strong paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer qVZ2:\n\nWe appreciate reviewer qVZ2's constructive feedback and positive comments on our idea, theoretical contributions, and experiments contributions. We respond to each of the reviewer's questions in the following.\n\n**Q1.1**  **Need to discussed more to understand PNS**\n\nWe conclude the answer in G.P.1 of General Response.\n\n**Q1.2**  **What are $c$ and $\\bar{c}$? if Def 2.1 is an extension of (Pearl 2009)?**\n\nIn the definition of PNS (Definition 2.1), $c$ and $\\bar{c}$ are different samples of variable C. In our study, we extend the concept of PNS to cases where C is not binary. In such scenarios, PNS on c and $\\bar{c}$ can still describe sufficient and necessary. We conclude a more detailed discussion in Example.2 in General Response G.P.1\n\n**Q2&Q5**  **It is not clear about the $\\bar{C}$ in theory and Assumption 4.1.**\n\nThank you for pointing out the unclear definitions in the paper. We detailedly explain it here.\n$\\bar{C}$ is an auxiliary variable to describe the intervention samples obtained by sampling from a specific distribution (lines 129-133). 'Intervention' describes we force a variable to be a certain value (may be different from its natural value), it is commonly accepted that the distribution of intervention data can be different from the original distribution. In our paper, the distribution of $\\bar{C}$ is set to be different from the distribution of $C$. Generally, they are different distributions, but in the same distribution class, e.g., different distributions from the Gaussian distribution class.\n\n\nWe can understand Assumption 4.1 as stating that there should be some distance between $c$ and $\\bar{c}$ if they lead to different semantics on Y. The constraint $|\\bar{c}-c|>δ$ in Eq. 8 actually ensures that if Assumption 4.1 holds, original value $c$ and intervention $\\bar{c}$ should have a distance to make c predicts y and avoids $\\bar{c}$ predicting y.\n\n\n**Q3**  **Why NC term can be \"absorbed\" into the monotonicity measurement?**\n\nIn Appendix D1, we provide proof that the Monotonicity Measurement ($M_t$) can be decomposed into a combination of two components (SF and NC). The key proofs are in Eqs. 15&16. It is evident that the optimization of the NC component is implicitly included in the decomposition of $M_t$. \n\n\n**Q4**  **Is $T(x, y)=P_t(x, y)$? What is the detailed property of $\\beta$-divergence?** \n\n\nYes, $T(x, y)=P_t(x, y)$. The definition of $\\beta_k$ is from Eq. 7 in Germain et. al.[1]. $β_k$ is a transformation of widely used Renyi divergence (footnote on page 4 of [1]), the relationship is,\n\n$for~ k\\ge 0, \\log β_k(T|S)=\\frac{k-1}{k}{{D_k}(T|S)}.$\n\n$\\log β_k$ will take the lowest value 0 when $T=S$. There was a reference typo in the main text that mistakenly cited Gong et al. We'll address this and correct the typo in the revision as Germain et. al.[1].\n\n\n\n**Q6**  **Theorem 4.3 contains typos and seems to be incomplete**\n\nWe will modify Theorem 4.3 as below to make it more fluent.\n\nTheorem 4.3. The optimal solution of C was learned by the following objective\n...$X ⊥ Y | C$.\n\n\n**Q7**  **The paper lacks a direct comparison with related works like IRM.**\n\nWe conclude the answer in G.P.2 of General Response.\n\n**Q9**  **Do you limit the number of hyperparameter choices to a fixed number for every method?**\n\nYes, during the training process, we limit the number of hyperparameters choices. We list the range of hyperparameters in Appendix Table 3. We utilized DomainBed's sweep script to run experiments and set the number of hyperparameter choices (--n_hparams) as 10.\n\n\n\n**Questions.** **Typos and figure re-ognization**\n\n\n1. We will follow your suggestion and modify the presentation of examples in  Figure 1 to make them clearer.\n2. We will correct the typo in Figure 2 and replace \"PA\" with \"SN.\"\n3. As per your advice, we will consider changing the phrasing from \"OOD generalization\" to \"domain generalization\" to avoid any ambiguity.\n\n**L.1**  **Should discuss the practical limitations of adversarial objective and report computational complexity of the method**\n\nThank you for your suggestion! We compared the time complexity of our method with other approaches. On the Colored-MNIST dataset, the average runtime per 100 steps across 3 domains is CaSN(ours): 19.5ms, ERM: 5.9ms, IRM: 8.1ms, and MLDG: 17.8ms. The differences in runtime mainly stem from the separate optimization steps for the min and max optimization processes. While our method's runtime is higher than ERM and IRM, it is still acceptable compared to classical domain generalization methods like MLDG.\n\nRegarding adversarial learning, we lower the learning rate and fewer steps for maximization to make the training process stable. Inspired by your valuable question, we surprisingly find that introducing a warm-up scheme can further stabilize the training process. Namely, we initially exclude the max step and pre-train all the components including parameters of $\\bar{C}$ in the minimization step. We will highlight these experimental details in our revision.\n\nFor the constraint in Eq. 8, we optimize it by a Lagrange multiplier. Specifically, during training, we added an additional objective in both the min and max steps as $λ min||\\bar{c}-c|_2-δ|_2$. This constraint is not a hard constraint. In our experiments, this constraint makes $|\\bar{c}-c|_2$ approach $\\delta$. We set δ as a hyperparameter, and the experimental results in Figure 2 showed that smaller values of δ are less conducive to discovering SN information, which aligns with our Assumption 4.1.\n\nWe will include more discussion on the implementation details and limitations of the practical algorithm in the revision.\n\n\n\n**L.2**  **More discussion on the assumptions and which are reasonably likely to hold in practice or not would be helpful**\n\nWe conclude this answer in G.P.2 of General Response.\n\n\n[1] Germain et. al. A new pac-bayesian perspective on domain adaptation. "}, {"review_id": "JpLvwcdSov", "reviewer": "Reviewer_pPMP", "summary": "This paper presents a novel approach to enhance out-of-distribution (OOD) generalization by identifying both sufficient and necessary conditions, thereby extending the existing literature that primarily focuses on causal invariance. The proposed method employs the probability of sufficient and necessary causes (PNS) to demonstrate its effectiveness in improving OOD generalization, through theoretical analysis and experimental results,.", "questions": "Please answer the questions in Weakness.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is very intuitive and novel, as far as I know. It focuses on sufficient and necessary causes to explore the invariance. This method successfully combines existing ideas in invariant causality with PNS, and has good experimental results. \n\n2. The proposed delta-PNS is reasonable to me. If the semantics have overlap, it is impossible to make good prediction.\n\n3. The experiment part is extensive which covers a variety of common datasets, including synthetic data, an ablation study, and datasets for both OOD generalization and domain adaptation tasks.", "weaknesses": "1. It is difficult to understand the definition of PNS in Definition 2.1, Could you provide more details?\n\n2. Typo: missing ) in line 222.\n\n3. Do you have discussed more general causal structure?\n\n\n-------\n\nAfter reading the author's response, my concerns have been well addressed, so I will keep my score as accept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer pPMP:\nWe thank reviewer pPMP for the constructive feedback and recognition of our novel and intuitive idea, as well as our experiments on various datasets. We respond to each of the reviewer's questions in the sections below.\n\n**Q1 It is difficult to understand the definition of PNS in Definition 2.1, Could you provide more details?**\n\nAccording to your valuable question, we will highlight the following details in the revision to enhance understanding of PNS.\nConsidering that the definition of PNS is based on the counterfactual distribution, it is not inherently intuitive. To better grasp how PNS is calculated and its relation to sufficiency and necessity, we provide two examples in General Response's G.P.1.\n\nFrom the example, we demonstrate how to calculate the PNS value of a feature in a predictive task and establish how a sufficient but unnecessary cause aligns with a specific PNS value. This straightforward case suggests that the PNS value can distinguish the extent to which a feature is necessary or sufficient.\n\nTo enhance understanding of PNS, we will provide more descriptions in the revision.\n\n\n**Q2 Typo: missing ) in line 222.**\n\nThank you for your suggestion; we will diligently review and correct typos to enhance the quality of the paper.\n\n\n**Q3 Do you have discussed a more general causal structure?**\n\nThank you for your question. The various assumptions in causality have always been a topic worth discussing. Our paper's assumption is based on conditional independence $X\\perp Y|C$, following the PIIF in [1], which is widely accepted. In [1], they also discuss other assumptions, such as FIIF, where the conditional independence $X \\perp Y \\mid C$ no longer holds, but it has assumption $Y \\perp \\mathcal{E} \\mid C$, where $\\mathcal{E}$ denotes the variable of domain). The IRM-based approach [2] effectively addresses generalization issues under this assumption but fails on PIIF assumption $X\\perp Y|C$.\n\nIn Section 7, we briefly discuss potential extensions of our paper to accommodate a broader range of causal assumptions, such as PIIF, confounders, and anti-causal. For instance, under the PIIF assumption, conditional independence should be described as $Y \\perp \\mathcal{E} \\mid C$. To meet Exogeneity under this assumption, an objective function (e.g., the invariant constraint in IRM) that incorporates additional domain label information is required. Further, when considering the existence of a confounder in causal assumption, an auxiliary objective function must be designed to identify the confounder, ensuring the satisfaction of Exogeneity.\n\nMore details about causal assumptions are concluded in General Response's G.P.2. We will provide more descriptions in the revision.\n\n[1] Ahuja et al. Invariance principle meets information bottleneck for out-of-distribution generalization.\n\n[2] Arjovsky et al. Invariant risk minimization."}, {"review_id": "oc0i9HDAgA", "reviewer": "Reviewer_CQCE", "summary": "This paper proposes the new concept of 'essential causal information' to achieve OOD generalization and proposes the probability of necessarity and sufficiency (PNS) risk to estimate the representation if satisfies the new concept. Then, it proposes a new algorithm to achieve loss PNS risk on the test domain.", "questions": "Why you don't consider recent methods (2021~2023) for Domain Adaptation? I am not an expert in this domain but I think there have many strong and new baselines for out-of-distribution generalization.", "limitations": "I don't see any potential negative social impact of their work.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Introducing the PNS risk for out-of-distribution generalization is novel and interesting. The proof for it is rigorous.\n(2) The method is general and works well on various datasets.\n(3) The writing of this paper is good.", "weaknesses": "(1) The fox also has long whiskers. The example in section 2.3 does not hold on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer CQCE:\n\nWe appreciate the suggestions from reviewer CQCE and are grateful for the recognition of the novelty of our approach, the rigor of our theory, and our writing style. We will respond to each of the questions posed by the reviewer below.\n\n**Q1 The fox also has long whiskers. The example in section 2.3 does not hold on.**\n\nThank you for your insightful question. We presented this example in the paper to provide a more vivid understanding of PNS. To strengthen our example, in revision, we will modify the example of 'sufficient and necessary cause' in the context of predicting cats and foxes by the feature of 'long mouth' instead of 'whisker'.\n\n**Q2 Why you don't consider recent methods (2021~2023).**\n\nThank you for your constructive suggestion.\nOur main method primarily focuses on Domain Generalization. Additionally, we included a recently proposed causal-based method EQRM[1] proposed in 2022, and its results on  VLCS datasets are shown below. \n\n|     | C  |  L    | S  | V  |Avg |Min   |\n|  ----  | ----  |----  |----  |----  |----  |----  |\n| ERM  | 97.7±0.4| 64.3±0.9 | 73.4±0.5 |74.6±1.3|77.5|64.3\n| IRM  | **98.6±0.1**|64.9±0.9|**73.4±0.6**|**77.3±0.9**| 78.5 |64.9|\n| EQRM  | 98.3±0.0 | 63.7±0.8 | 72.6±1.0 | 76.7±1.1| 77.8| 63.7|\n| CaSN(ours)  |98.3 ±0.3 |**66.9±1.2** | 73.1±0.6 | 76.8±0.8 |**78.8** | **66.9**|\n\nThe results show that our method has a competitive performance compared with the recent methods on EQRM. We plan to implement more recent baseline methods and test them on more datasets. The results will update in revision.\n\nOur extended algorithm for Domain Adaptation is not the main focus of our paper. Instead, we provided experimental validation of its effectiveness in comparison with classical algorithms in the appendix. We plan to implement the recent Domain Adaptation method based on the DomainBed code. We plan to update the relevant results in the revision.\n\n\nIn addition，we test our method on the recent dataset SpuCo[2] in 2023 and compare our method CaSN with the benchmark they provided. We obtained some new results and the code implementation is based on [SpuCo](https://github.com/BigML-CS-UCLA/SpuCo). Our experimental data is SpuCoAnimal which comprises 8 different spurious correlation groups.\n\nWe set hyperparameters as $\\delta=3$ and $\\lambda\\in{0.005,0.01}$, while the remaining parameters followed SpuCo's default values. We conducted two types of experiments: the first involved training the model without providing any additional information, and the second involved resampling based on the spurious correlation group information, where the base models corresponded to ERM and Group Balance (GB) respectively. \n\nWe reported the results below, with each result obtained from 4 fixed random seeds. \n\n\n|     | ERM  |  CaSN (ours)   | GB  | CaSN-GB  |\n|  ----  | ----  |----  |----  |---- |\n|  Average  | 80.26±4.1  |84.34±0.6   |49.9±1.4 | 50.54±7.6 |\n|  Min  | 8.3±1.3  | 9.7±2.7   |41.1±2.7| 42.0±0.8 |\n\nOur method showed higher average accuracy compared to the baseline, and even the worst spurious correlation group exhibited higher accuracy than the baseline.  We plan to continually update the results in revision.\n\n[1] Eastwood C, Robey A, Singh S, et al. Probable domain generalization via quantile risk minimization[J]. Advances in Neural Information Processing Systems, 2022, 35: 17340-17358.\n\n\n[2] Joshi S, Yang Y, Xue Y, et al. Towards Mitigating Spurious Correlations in the Wild: A Benchmark & a more Realistic Dataset[J]. arXiv preprint arXiv:2306.11957, 2023.\n"}]

Author rebuttal:
# General Response:
We sincerely appreciate all reviewers's great efforts on review and comments of our work. We thank for the positive comments:
- **Clear and well-explained  intuition** (Reviewer #jeo8 #pPMP )
- **Interesting and reasonable idea** (Reviewer #qVZ2 #pPMP #CQCE)
- **Novel idea** (Reviewer #CQCE #aG69)
- **Rigorous theoretical guarantees** (Reviewer #jeo8 & #qVZ2 #CQCE) 
- **Reasonable results** (Reviewer #qVZ2 #pPMP #CQCE #aG69)
- **Good writing** (Reviewer #CQCE)
We provide detailed responses in response to your valuable comments. Due to space limitations, we have listed the common responses first.

**G.P. 1. Understanding PNS**
We provided two examples to help understand the PNS (Probability of Necessity and Sufficiency) value. We will add the following explanations to our revision.

**Example.1** We use the feature 'has cat legs' represented by the variable C (taking values 1 or 0) to predict the label of being a cat or a fox. 'has cat legs' is sufficient but unnecessary cause because the image contains cat legs must have cat but cat image might not contains cat leg. We assume P(Y=1|do(C=1))=1 and P(Y=0|do(C=0))=0.5.

Now, applying the concept of the probability of sufficiency and necessity, we obtain:

Probability of necessity: P(Y(do(C=0)=0|Y=1,X=1)=0.5

Probability of sufficiency: P(Y(do(C=1)=1|Y=0,X=0)=1

In this example, we can state that variable C has a probability of being a sufficient cause.

**Example.2** If we use feature 'eye size' C (taking values 1, 0.5 or 0, the lower value means smaller eye size on face), to predict Y (cat 1 or fox 0). Assuming P(Y=1|do(C=1))=1, P(Y=1|do(C=0.5))=0.5 and  P(Y=1|do(C=0))=0. 

In Definition 2.1, PNS($c, \bar{c}$) can take multiple choice. We provide Case.1: $c=1$ and $\bar{c}=0.5$ and Case.2: $c=1$ and $\bar{c}=0$,

Case.1 PNS(1, 0.5) = PN+PS = P(Y(do(C=0.5)=0|C=1, Y=1)+P(Y(do(C=1)=1|Y=0,C=0.5)= 0.5 + 1 = 1.5

Case.2 PNS(1, 0) = PN+PS = P(Y(do(C=0)=0|C=1, Y=1)+P(Y(do(C=1)=1|Y=0,C=0) = 1 + 1 = 2

We note that Case.1 indicate the feature has more sufficiency than necessity. 

We introduced a PNS risk to investigate the PNS value between the representation and Y. When the algorithm optimizes the objective function to minimize the PNS risk, it indicates that the representation we found contains more sufficient and necessary causal information. 

Considering there are multiple choices of $c$ and $\bar{c}$ (like Example.2), we extend our algorithm by min-max optimization (Eq. 8 in our paper), which ait to find the worst $\bar{c}$ for $c$ with highest PNS risk. 

**G.P. 2. Difference from other invariant learning methods:**

- i) Form the perspective of goals, while both our approach and invariant learning methods aim for domain generalization by discovering invariant features, our method further emphasises the importance of sufficient and necessary properties in the learned representations. The invariant feature doesn't mean sufficient and necessary. For example, the feature 'has cat legs' is invariant causal feature but it is unnecessary because having cat legs indicates it's a cat, but the absence of cat legs doesn't necessarily mean there is no cat in the image.


- ii) From the perspective of causal assumption, our assumption of the causal graph in Figure 1 is based on previous works on out-of-distribution (OOD) generalization, such as the causal graph in Liu et al. [1], and Ahuja et al. [2]. In Ahuja et al. [2], they conclude the assumptions in OOD generalization task as (1) fully informative invariant features (FIIF): Feature contains all the information about the label that is contained in input. (2) partially informative invariant features (PIIF). Our assumption $X \perp Y \mid C$ holds in the case of FIIF. As presented in [2] page 3, IRM [3] is based on the assumption of PIIF, where $X \perp Y \mid C$ does not hold and IRM fails in the case of FIIF. 

  In our paper, we demonstrate that this paper only focuses on the causal assumption in Figure 1 where $X \perp Y \mid C$ (FIIF) holds. 

  Other assumptions such as PIIF, confounders and anti-causal, will be solved by adding additional constraints. For example, in the assumption of PIIF, conditional independence should be represented as $Y \perp \mathcal{E} \mid C$ (PIIF). To satisfy Exogeneity, an objective function (e.g. invariant constraint in IRM) with additional domain label information is required.

- iii）From the perspective of objective function： The objective function of our method CaSN is presented in Eq. 8 in the paper. The objective function of IRM is 

  $\min_{\phi} \sum_{e \in \mathcal{E}_{tr}} R^e(\phi)+\lambda | ∇ {w \mid w=1.0} R^e(w \cdot \phi)|^2,$ where the second term is invariant constraint.

  Our approach differs from the IRM-based methods on the final objective function for several reasons: 1) Because of the different assumptions, in our paper, there is no need to introduce additional domain label information. However, under the PIIF assumption where IRM operates [2], there's a need to introduce additional domain label information to compute the second term in the IRM objective function. Thus, IRM is only available for multi-domain scenarios, but our method can be used without providing domain information. 2) Our proposed method CaSN is built upon the PNS risk, while IRM is constructed on the ERM risk. From a causal perspective, PNS risk offers a more precise design compared to ERM, which allows CaSN to not only achieve invariant learning but also further discern sufficiency and necessary features.

We will add the discussion in the revision.

[1] Liu et. al., Learning causal semantic representation for out-of-distribution prediction

[2] Ahuja et al. Invariance principle meets information bottleneck for out-of-distribution generalization.

[3] Arjovsky et al. Invariant risk minimization.

[4] Joshi et al. Towards Mitigating Spurious Correlations in the Wild: A Benchmark & a more Realistic Dataset.

Meta-review: The paper presents an interesting idea to capture causal features for a particular task: using the notion of necessary and sufficiency for an outcome variable. Reviewers appreciated the clean writing as well as the theoretical results.  The difference to the invariant property can be better explained, which I hope the authors will add to their camera-ready version. In addition, I recommend the authors to add the empirical experiments from their rebuttal to the main paper.
Decision: Accept (spotlight)