Paper Review : Counterfactual Graphical Models - Constraints and Inference (Bareinboim et al., ICML 2025)

1. Counterfactual (반사실)

Pearl's Causal Hierarchy 에서는 보통 "관찰", "개입", "반사실"로 세 층위로 나눈다. 그중에 반사실은 $P(Y_x|X=x')$ 같이, 어떠한 Treatment X를 실행하지 않은 집단에 대해, Treatment를 실행할 경우에 실제론 어떻게 변화할지 알고 싶다는 것이다.

---

2.1. Do-Calculus

현실에서 우리가 접할 수 있는 데이터는 대부분 Observational Data, 즉 관측 데이터이다. 이러한 관측 데이터로는 쉽게 상관관계는 알 수 있지만 인과관계는 파악하기 어렵다는 것이다. 이때, Do-Calculus를 통해 P(y|do(x)) 같은 query를 Do-Calculus를 통해 observational data 에서의 항들로 바꿀 수 있다면 identification (식별) 할 수 있다고 한다. 곧, $\mathcal{L_2}$ 를 $\mathcal{L_1}$ 을 통해 처리할 수 있다는 것이다.

문제는 $\mathcal{L_3}$ 에 대한 연구가 개입에 비해 부족하다는 것이다. 이를 위해 해당 논문에서는 ctf-calculus (Counterfactual Calculus) 를 제안하고, Multi-world counterfactual 에 대해서 기존의 graphical model에서의 independence-test 기법인 d-seperation을 이용하여 multi-world counterfactual에서의 독립성을 d-seperation을 통해 처리할 수 있는 새로운 Graphical Model인 Ancestral Multi-World Network (AMWN) 을 제안한다.

2.2 Counterfactual Constraints

해당 논문에서는 세 가지 Constraints 를 제시한다.

(1) Consistency Constraint
(2) Exclusion Constraint
(3) Independence Constraint

Consistency Constraint

데이터셋 내의 개별 데이터는 우리가 관측할 수 없는 외생 변수들의 집합 $\bold{U}$ 내의 변수들의 값에 따라 결정론적으로 정해진다고 가정한다.

이때, Counterfactual World $(Y_x=y,\,X=x)$ 에 대해 생각해보자.

$P(Y_x=y,\,X=x)\\=\underset{u}{\sum}1[Y_x(u)=y,\,X(u)=x]P(u)\\=\underset{u}{\sum}1[Y(u)=y,\,X(u)=x]P(u)\\=P(Y=y,\,X=x)$

곧, intervention 없이 $X=x$ 인 값들에 대해 동일한 값을 intervention 하는 counterfactual은 observational data에서의 확률 분포와 다르지 않다.

Lemma (Consistency)
Given SCM $\mathcal{M}$ and $X,\,Y\in V$, $\bold{T}_*$ be any combination of counterfactuals, and let $x$ be a value in the domain of $X$.
Then, $P(Y_{\bold{T}_*},\,X_{\bold{T}_*}=x)=P(Y_{\bold{T}_*x},X_{\bold{T}_*}=x)$

직관적으론, $X$가 $x$라는 값을 가지게 되는 외생변수 조합들에 대해선, $do(X=x)$ 로 고정을 시킨다고 하더라도 기존의 값과 달라지지 않는다고 해석할 수 있다. 그런 관점에서 consistent 하다고 하여, 이 성질을 저자들은 Consistency (일관성) 이라 명명했다.

Exclusion Constraint

Intervention을 하고 나면 기존의 causal graph 에서, fix 시킨 변수의 incoming edge 들이 전부 pruning 된다. 그렇기에 counterfactual-world를 생각해볼 때, 해당 sub-graph에서 directed path가 없는 변수들의 경우엔 해당 변수에 대해 do-operation을 통해 고정을 시키든 안 시키든 값이 동일하게 나온다고 해석할 수 있다.

이를 수식적으로는 다음과 같이 작성할 수 있다.

Lemma (Exclusion Operator)
Let $Y_x$ be a counterfactual variable, $\mathcal{G}$ a causal diagram, and
$Y_z$ s.t. $Z=X\cap An(Y)_{\mathcal{G}_{\overline{X}}}$ and $z=x\cap Z$.

Then, $Y_z=Y_x$ holds for any model compatible with $\mathcal{G}.$ Moreover, this transformation is denoted as $||Y_x||:=Y_z$.

이를 그래프적으로 확인해보기 위해, 다음과 같은 causal diagram을 가정해보자.

위의 그래프의 상황에서 $Y_{wx}$ 를 생각해보자. $do(W=w,\,X=x)$ 연산을 하게 되면 X에서 Y로 가는 directed path는 존재하지 않는다. 곧, 해당 sub-graph 하에서 X는 Y에 대해 인과적 효과가 없어진다.

이에 따라, counterfactual variable $Y_{xw}$ 는 $Y_w$ 와 같아진다. 고로, $||Y_{xw}||=Y_w$ 다.

Independence Constraint

마지막 constraint를 이해하기 위해 우리는 Ancestral Multi-World Network를 이해할 필요가 있다.

[ Example ]
주어진 Causal Diagram은 앞서 주어진 diagram 과 동일하다고 하자.
이때, 우리가 알고 싶은 query는 $(Y_{xw},W_{x'}\perp X|Z_{x'})$ 의 참, 거짓 여부다.

기존 방법론인 Twin-Network의 자연스러운 확장 방식으로 $k$-plet network 를 만들 수 있고, 이는 다음과 같다.

여기서 우리가 착각하기 쉬운 건, $Y_{xw}-Z_{xw}-U_z-Z-X$ 로 d-connected 되어 있지 않는지 하고 착각할 수 있다는 것이다.

하지만 앞서 정의한 exclusion-operator를 통해
$||Z||=||Z_{x'}||=||Z_{xw}||=Z$ 임을 쉽게 알 수 있기에 위의 그래프를 아래의 그래프와 같이 바꾸어보자. (같은 변수는 합치고, do-operation으로 고정된 변수는 생략)

이 그래프에서 다시 한 번 d-seperation을 확인해본다면 $||Z_{x'}||=Z$ 가 conditioned variable 이므로 d-seperated 되어 있음을 쉽게 확인해볼 수 있다.

고로, $Y_{xw}\perp X|Z_{x'}$ 임을 쉽게 확인할 수 있다. 하지만 이 경우, d-seperation을 확인할 때의 graph의 크기가 크기 때문에 오래 걸린다는 단점이 있다.

이를 해결하고자 나온 것이 AMWN이다. 우선 생각해봐야 하는 것은 위의 k-plet network에서 서로 다른 counterfactual world의 두 변수가 d-seperated 되어 있는가를 확인하기 위해선 조상 노드들만 확인해보면 된다는 것이다.

두 변수가 서로 다른 counterfactual world에 있는 이상, 두 변수의 공통 후손은 존재할 수 없다. 그에 따라 우리가 실제로 d-seperation에 있어 필요한 변수 집합은 $An(\bold{T}_*)$ 이다.

수학적으로 $An(\bold{T}_*)=\underset{T_i\in\bold{T}_*}{\cup}An(T_i)$ 인데, 이때 Counterfactual variable에서의 ancestor 를 정의할 필요가 있다.

Definition (Ancestors of a counterfactual)
Let $Y_x$ be such that $Y\in\bold{V},\,X\subset V$.
Then the set of (counterfactual) ancestors of $Y_x$, denoted by $An(Y_x)$, consist of each $W_z$ s.t. $W\in An(Y)_{\mathcal{G}_{\overline{X}}}\backslash X$ (which includes $Y$ itself), and $z=x\cap An(W)_{\mathcal{G}_{\overline{X}}}$.

이때, 왜 $X$가 ancestor에서 빠지는 걸지 생각해봤을 때, X는 intervention을 통해 incoming-edges 가 pruning 된 변수 집합이므로 다른 counterfactual-world와 공유되지 않기 때문으로 생각해볼 수 있을 것 같다.

이산 수학에서의 그래프 이론적 차원에서는 엄밀하게는 조상에 포함될 수 있지만, counterfactual 에서의 d-seperation 확인 차원에서는 전혀 도움이 되지 않는다는 것이다. 그에 따라 위와 같이 Ancestors of a counterfactual 이 정의되지 않았나 조심스레 추측해본다.

이제 위에서 정의된 Ancestor of a counterfactual을 이용해서 AMWN을 구성해보자.

위의 말들을 해석해보면 다음과 같다.

1. Query 내의 변수들의 Ancestor를 구해서 그래프에 넣어라. (이때, Ancestor 에는 e.g. An(X) 라고 한다면, X도 An(X) 안에 포함된다.)
2. 여러 번 나타나는 변수들에 대해서 (e.g. $X,\,X_w$) 외생변수 $U$를 추가한 뒤, 그 변수들에 directed edge를 추가해라.
이는 곧, 다른 counterfactual world에서의 변수라고 할지라도 외생변수를 통해 d-connected 된다는 걸 표현하기 위함이다.
3. 그래프 내의 bidirection에 대해서도 2와 마찬가지로 외생변수를 추가하여, 모든 counterfactual world에서 해당 변수들에 대해 directed edge를 추가해라. 마찬가지로 d-connected 됨을 표현하기 위함이다.

이를 통해 얻은 AMWN는 아래의 그래프와 같다.

이 그래프를 통해, $||Y_{xw}||=Y_w$ 가 $W_{x'}$ 과 독립임을 쉽게 알 수 있고, 마찬가지로 $Y_w$ 가 $Z$ 가 given condition 이기에 $X$ 와는 d-seperated 됨을 쉽게 확인해볼 수 있다.

이제 아래와 같은 케이스를 살펴보자.

위의 AMWN은 $Y_{xw}\perp X|Z,W$ 를 판별하기 위해 구축된 그래프로, $Y_{xw}-Z_w-U_{zx}-X$ 로 d-connected 되는 그래프다. 이를 통해 위의 Query 가 틀렸다고 얘기할 수 있다. (엄밀하게 따지자면 ambiguous 하지만, causal faithfullness 같은 가정을 하게 되면 맞는 말임)

이러한 방법론을 통해, d-seperation을 통한 independence test를 sound & complete 하게 할 수 있다.

Soundness & Completeness
알고리즘의 정확성을 말할 때 보통 위의 두 가지를 기준으로 말하는데, 각 용어의 뜻은 아래와 같다.
(1) Soundness : Ensures that formal proofs do not accept anything wrong.
(2) Completeness : Ensures that the proof system is powerful enough to discover all true statements.

Performance Table

Method	Any sep	Complete	Time Complexity
k-plet Network	Yes	Yes	O(zn(n+m)
AMWN	Yes	Yes	O(z(n+m))

Construct-AMWN 의 시간 복잡도는 위와 같다. 이때, z는 각기 다른 intervention-set의 개수이며, n과 m은 node의 개수와 edged의 개수다.

Counterfactual ancestor에 대한 집합은 size-of-graph에 대해 linear 하기에 O(n+m)이다. 여기서, 각 intervention 별로 counterfactual ancestor를 계산해야 하므로 O(z(n+m))의 시간 복잡도임을 알 수 있다.

여기서, latent node는 n개 초과, zn개 초과의 edges를 추가할 수 없다. m에 대해, 최대 m개의 노드와 2zm 개의 edge를 추가할 수 있기 때문에 최종적으로 O(z(n+m))이라는 그래프의 사이즈와 counterfactual variable set의 크기에 대한 다항 시간 복잡도의 효율적인 알고리즘임을 알 수 있다.

---

3. The Counterfactual Calculus

앞서 살펴본 세 가지 성질을 통해, 이 논문에서는 세 가지 변환식을 소개한다.

사실상 이미 얘기했던 세 성질들에 대해 정리했을 뿐이기에, 예시를 따라가보면서 위의 변환 공식들을 적용시켜보자.

ETT (Effect of Treatment on the Treated) : Back-door Case

위와 같은 Back-door graph 를 생각해보자.
이때 우리가 알고 싶은 것은 Query는 $P(Y_x|x')$이다.

Judea Pearl 의 교재에서는 보통 아래의 세 단계로 진행된다.
1) Abduction : 관측된 사실을 통해 외생 변수의 사후 확률 분포를 구함
2) Action : 행동/개입으로, 반사실을 강제 주입
3) Prediction : 1단계의 사후 분포와 2단계의 변형된 모델을 통해 Y 값 예측

$P(y_x|x')\\=\underset{z}{\sum}P(y_x,z|x')\,(Abduction)\\=\underset{z}{\sum}P(y_x|z,x')P(z|x')\,(product\,\,rule)\\=\underset{z}{\sum}P(y_x|z_x,x')P(z|x')\,(Rule\,\,3)\\=\underset{z}{\sum}P(y_{xz}|z_x,x')P(z|x')\,(Rule\,\,1)\\=\underset{z}{\sum}P(y_{xz}|z,x')P(z|x')\,(Rule\,\,3)\\=\underset{z}{\sum}P(y_{xz}|z,x)P(z|x')\,(Rule\,\,2)\\=\underset{z}{\sum}P(y|z,x)P(z|x')$

여기서 Rule-1을 적용하기 위해 Rule-3로 x를 counterfactual 조건으로 추가하는 걸 볼 수 있다. Rule-1은 곧, 동일한 counterfactual world에 있는 변수에 대해서는 joint probability일 때 제거해도 되고, 추가해도 된다는 의미다.

우리가 이 예시에서 살펴볼 수 있는 지점은, Rule-1을 적용시키기 위해 동일한 counterfactual world로 진입하고자 Rule 3를 많이 접목시킨다는 점이다. 그리고서 Rule-1, 3로 대부분의 변수들을 바꾸곤 $x'$을 $x$로 바꾸는 마지막 과정으로 Rule-2를 사용하여 $\mathcal{L}_3$ query를 $\mathcal{L}_1$의 항들로 최종 변환해주는 방식임을 알 수 있다.

마지막으로, ctf-calculus는 do-calculus와 마찬가지로 아래가 성립한다.

Query is identifiable $\iff$ $\exists$ sequence of ctf-calculus that induces identification formula

여기서, counterfactual 이 identifiable 하다는 것은 곧, observational/interventional distribution의 term으로 정리된다는 것이다.

---

3. Conclusion

위의 세 가지 공식과 AMWN을 통해서, 기존의 Single-World Counterfactual World에서 더 나아가 Multi-World Counterfactual Query를 평가할 수 있게 되었다.

그리고 더 나아가, observational data 뿐 아니라 한 intervention을 통한 sub-graph의 정보를 알게 된다면 독립성 테스트를 통해, 종속일 경우 이러한 다른 intervention data 에서의 실험 결과를 counterfactual 을 통해 정보를 얻을 수 있게 됨을 생각해볼 수 있다.

4. Personal Opinion

우선은 위의 세 공식을 자연스럽게 적용시키기가 상당히 까다로울 것으로 보인다. Do-Calculus가 Counterfactual Calculus에 포함된다고 적혀 있었는데,