SNU Causal Inference : Algorithmic ID

1. Factorization

1.1 Truncated Factorization

다음과 같은 Markovian Model 상황을 가정하자. 이 경우, Truncated Factorization 에서 unobserved variable을 생략해도 괜찮으며 $P(v_i|pa_i)$ 를 canonical factor 로 사용하여 분리할 수 있다.

Truncated Factorization
$P(\bold{v})=P(y|x,z)P(x|z)P(z)$

하지만 Semi-Markovian 이라면? 위와 같이 $P(v_i|pa_i)$ 를 canonical factor 로 사용할 수 없다. 우리가 원하는 건 구하는 식을 분해하여 observation 의 항으로 표현하고자 하는 것이기에 새로운 방식이 필요하다.

1.2 C-factors

위의 상황과 같은 경우엔 다음과 같이 P(v)를 작성할 수 있다.

$P(v_5|v_4)P(v_4|v_3)P(v_2|v_1)(\underset{u_1}{\sum}P(u_1)P(v_3|v_2,u_1)P(v_1|u_1))$

이처럼 unobserved confounder 를 공유하는 두 노드 $v_1,\,v_3$ 는 분리 불가능한 하나의 항으로서 계산된다.

마찬가지로 하나의 unobserved confounder 를 추가한 뒤 $P(\bold{v})$를 계산해보자.

$P(v_4|v_3)P(v_2|v_1)(\underset{\bold{u}}{\sum}P(\bold{u})P(v_5|v_4,u_2)P(v_3|v_2,u_1,u_2)P(v_1|u_1))$

이처럼 $v_3$를 매개로 $u_1,\,u_2$ 를 unobserved confounder 로 하는 노드들을 하나의 항으로서 확률 분포를 계산하는데에 사용한다.

이 경우에서도 앞선 사례들과 유사하게 아래와 같이 계산된다.

$(1)=\underset{u_2}{\sum}P(u_2)P(v_3|v_2,u_1)P(v_1|u_1)\\(2)=\underset{\bold{u}}{\sum}P(\bold{u})P(v_5|v_4,u_2)P(v_3|v_2,u_1,u_2)P(v_1|u_1)\\P(\bold{v})=(1)\cdot(2)$

이처럼, unobserved confounder 에 의해 연결되는 노드들을 기준으로 $P(\bold{v})$를 분리할 수 있고 이를 C-factor 라 부른다.

이와 같은 각각의 factor 들을 편의상 $Q[\{V_1,V_3,V_5\}]$와 $Q[\{V_2,V_4\}]$ 로 작성하며, 각각 위의 식에서의 $(1),\,(2)$ 에 대응된다.

이때, C-factor는 다음과 같이 나타낼 수 있고 C-factor의 정의의 일관성을 위해 우리는 $Q[\empty]=1$ 로 정의한다.
(집합적 관점에서 바라보면 $V=V\cup\empty$ 기 때문에, $Q[\bold{v}]=Q[\bold{v}]Q[\empty]$를 만족해야 함)

$Q[\bold{v}]=\underset{\bold{u}}{\sum}P(\bold{u})\underset{v_i\in\bold{v}}{\prod}P(v_i|pa_i,u_i)=P(\bold{v})$

1.3 C-factors are Causal Effects

$\bold{C}\subset\bold{V}$ 라 하자. 이때, $P(\bold{c}|do(\bold{v\backslash{}c}))=\underset{\bold{u}}{\sum}P(\bold{u})\underset{V_i\in\bold{C}}{\prod}P(v_i|\bold{pa_i,u_i})$이고 이는 위에서 살펴본 $Q[\bold{C}]$ 와 동일함을 알 수 있다.

고로, C-factor는 $\bold{V}$ 를 $\bold{C},\bold{V\backslash{C}}$ 의 두 집합으로 분리하여 $\bold{V\backslash{C}}$의 $\bold{C}$ 에 대한 인과 효과로 해석할 수 있다.

위의 결과를 토대로 $Q[\{V_1,V_3,V_5\}]$ 를 위한 Graph $G_{\bar{v_2},\bar{v_4}}$는 아래와 같다.

---

2. Marginalizing Variables in C-factors

앞서 살펴본 예시를 기준으로 C-factor 안에서도 Marginalization이 가능한지 살펴보자.

$Q[\{V_1,V_3,V_5\}]\\=\underset{u_1,u_2}{\sum}P(u_1,u_2)P(v_1|u_1)P(v_3|v_2,u_1,u_2)P (v_5|v_4,u_2)\\$
$\underset{v_3}{\sum}Q[\{V_1,V_3,V_5\}]\\=\underset{v_3}{\sum}\underset{u_1,u_2}{\sum}P(u_1,u_2)P(v_1|u_1)P(v_3|v_2,u_1,u_2)P(v_5|v_4,u_2)\\=\underset{u_1,u_2}{\sum}P(u_1,u_2)P(v_1|u_1)P(v_5|v_4,u_2)\underset{v_3}{\sum}P(v_3|v_2,u_1,u_2)\\=\underset{u_1,u_2}{\sum}P(u_1,u_2)P(v_1|u_1)P(v_5|v_4,u_2)\\=Q[\{V_1,V_5\}]$

하지만 모든 경우에서 C-factor가 Marginalization 가능한 것은 아니다. 아래의 예를 살펴보자.

$\underset{v_1}{\sum}Q[\{V_1,V_2,V_3\}]\\=\underset{v_1}{\sum}\underset{\bold{u}}{\sum}P(\bold{u})P(v_1|u_1)P(v_2|v_1,u_2)P(v_3|v_2,u_1,u_2)\\=\underset{\bold{u}}{\sum}P(\bold{u})P(v_3|v_2,u_1,u_2)\underset{v_1}{\sum}P(v_1|u_1)P(v_2|v_1,u_2)\\\neq\underset{\bold{u}}{\sum}P(\bold{u})P(v_3|v_2,u_1,u_2)P(v_2|v_1,u_3)\\=Q[\{V_1,V_3\}]$

그렇다면 어떠한 경우일 때 C-factor 에서의 Marginalization 이 가능한 것일까?

2.1 Ancestral Reduction

이때, $\bold{W}\subset\bold{C}\subseteq\bold{V}$ 으로, 모든 graph $\mathcal{G}$의 노드가 아닌 $\mathcal{G}[\bold{C}]$ 에서만 $An(\bold{W})=\bold{W}$ 을 만족시키면 된다.

앞서 살펴본 $\bold{C}=\{V_1,V_3,V_5\}$ 의 경우 $\bold{W}=\{V_1,V_3\}$ 에 대해, $\mathcal{G}[\bold{C}]$ 에서 $An(\bold{W})=\bold{W}$ 를 만족하므로 Marginalization 이 가능했던 것으로 이해할 수 있다.

주어진 $\mathcal{G}[\bold{C}]$를 살펴보자. 여기서 아래의 집합들이 Ancestral Set인지 아닌지 확인해보도록 하자.

$\bold{W_1}=\{V_1,V_2\}\rightarrow{Ancestral}$
$\bold{W_2}=\{V_1\}\rightarrow{Ancestral}$
$\bold{W_3}=\{V_2,V_3\}\cancel{\rightarrow}{Ancestral}$

이러한 Ancestral Reduction 은 C-factor Algebra 에서 거의 기초에 가깝게 사용되는만큼, sub-model을 기준에서의 subset 이 Ancestral Set이기만 하면 된다는 걸 기억해두자.

2.2 Confounded Components (C-Components)

앞서 다룬 예시를 떠올려보자. 이 경우 $\{V_1,V_3,V_5\},\,\{V_2,V_4\}$ 이렇게 두 집합을 기준으로 공통의 unobserved confounder 에 의해 연결 되었다.

이러한 각 집합을 우리는 Confounded Component 라 부른다.

이때, C-component Relation 은 Reflexive, Symmetric, Transitivie 하므로 이산수학에서의 Equivalence Relation 과 동일한 구조라고 생각해볼 수 있다.

2.3 C-Component Factorization

수식만 봐서는 어렵게 느껴질 수 있으나, 요약해서 설명하자면 $\bold{H}$를 Partition 하는 $k$개의 confounded component 가 존재할 때, 각 confounded component의 c-factor의 곱이 곧 $Q[\bold{H}]$ 와 같다는 것이다.

[ Case study ]

여기서 총 두 개의 Confounded Components가 생기고, 이를 위의 C-Component Factorization Lemma를 적용하면 아래와 같이 나타낼 수 있다.

$P(\bold{V})=Q[\bold{V}]=Q[\{X,Z_2,Z_3,Y\}]Q[\{Z_1\}])$

이때, C-Factor에 대해 다음과 같은 성질이 존재하는데, 우선 $\bold{H}$라고 하는 $\bold{V}$의 부분 집합에 대해 생각해보자.

$\bold{H}$ 를 이루는 각 노드들에 대해 topological sort 를 수행하여 ordering 을 만들어 냈다고 하자. 이때 각 confounded component $\bold{H}_i$ 에 대해, 낮은 ordering 기준으로 $V_j\in\bold{H}_i$에 대하여 $Q[V_{1:j}]/Q[V_{1:j-1}]$ 의 연쇄적인 곱으로 생각해볼 수 있다.

이때 각 항을 계산하고자 할 때, 우리는 앞서 다룬 Ancestral Reduction 을 통해 이를 계산한다.

이렇게 글로만 읽었을 때는 잘 와닿지 않을 것이기에, 아래와 같은 예시를 통해 이해해보도록 하자.

[ Case Stduy 1 ]

이때 topological sort를 이용한 ordering 에 맞춰 수식을 전개하므로 ancestral reduction 의 조건은 자동으로 충족되므로 다음과 같이 계산할 수 있다.

[ Case Study 2 ]

$Q[\{V_2,V_4\}]$ 에 대해서도 생각해보자. 이때, $\bold{W}=\{V_2\},\,\bold{C}=\{V_2,V_4\}$라고 설정하면 다음의 경우 직접적인 인과 관계가 존재하지 않으므로 주어진 $\bold{W}$는 $\mathcal{G}[C]$에서 Ancestral Set이다. 고로, Marginalization을 적용할 수 있고, 이는 다음과 같이 표현된다.

$Q[\{V_2,V_4\}]\\={Q[\{V_2,V_1\}]\over{Q[\{V_1\}]}}\times{Q[\{V_4,V_3,V_2,V_1\}]\over{Q[\{V_3,V_2,V_1\}]}}\\=P(v_2|v_1)P(v_4|v_1,v_2,v_3)\\$
$Q[\{V_2\}]\\=\underset{v_4}{\sum}Q[\{V_2,V_4\}]\\=P(v_2|v_1)\underset{v_4}{\sum}P(v_4|v_1,v_2,v_3)\\=P(v_2|v_1)$

3. Case Study : C-factor Algebra

3.1 Back-door

우선 주어진 $\bold{V}$에 대해 confounded components 는 $\{X\},\,\{Y\},\,\{Z\}$ 로 총 세 개다. 이에 따라, $Q[\bold{V}]=Q[\bold{X}]\cdot{Q[\bold{Y}]\cdot{Q}[\bold{Z}]}$ 로 나타낼 수 있다.

$\bold{H}=\{X,Y,Z\},\,Z\prec{X}\prec{Y}$ 이므로 $Q[\{Y\}]={Q[\{Z,X,Y\}]\over{Q[\{Z.X\}]}}=P(y|z,x)$

$P(y|do(x))=\sum_z{}P(y,z|do(x))=\sum_{z}Q[\{Y\}]\cdot{}Q[\{Z\}]$으로, $Q[\{Z\}]$은 $\bold{C}=\{Z,X,Y\}$로 설정할 때 Ancestral Set이므로 Marginalization이 가능하고 이에 따라 $P(z)$임을 알 수 있다.

곧, $P(y|do(x))=\underset{z}{\sum}Q[\{Y\}]\cdot{}Q[\{Z\}]=\underset{z}{\sum}P(z)P(y|z,x)$ 이다.

3.2 Front-door

$P(\bold{v})=Q[\bold{v}]=Q[X,Y]\cdot{}Q[Z](\because$ C-Components Factorization$)$

$P(y|do(x))=\underset{z}{\sum}Q[Y,Z]=\underset{z}{\sum}Q[Y]\cdot{}Q[Z]$

이때, $Q[Y]$의 경우, $\bold{C}=\{X,Y\}$로 설정하고 $\bold{W}=\{Y\}$로 하면 Ancestral Set이므로 $Q[Y]=\underset{x}{\sum}Q[X,Y]=\underset{x}{\sum}{Q[X]\over{Q[\empty]}}\cdot{Q[X,Z,Y]\over{}Q[X,Z]}=\underset{x}{\sum}P(x)P(y|x,z)$

$\bold{H}=\{X,Z,Y\}$로 설정하고, Z는 별개의 C-component를 이룬다.
곧, $Q[Z]={Q[X,Z]\over{}Q[X]}=P(z|x)$이며 아래와 같이 정리할 수 있다.

$P(y|do(x))=\underset{z}{\sum}P(z|x)\underset{x^\prime}{\sum}P(x^\prime)P(y|x^\prime,z)$

3.3 Napkin

$P(\bold{v})=Q[X,W_1,Y]\cdot{}Q[W_2]$ 으로 분리할 수 있다.
이때, $P(y|do(x))=\underset{w_1,w_2}{\sum}Q[W_1,W_2,Y]$ 라 할 수 있고, 마찬가지로 C-components factorization 을 수행하면 아래와 같다.

$P(y|do(x))\\=\underset{w_1,w_2}{\sum}Q[W_1,Y]\cdot{}Q[W_2]\\=\underset{w_2}{\sum}Q[W_2]\underset{w_1}{\sum}Q[W_1,Y]\\=\underset{w_2}{\sum}Q[W_2]Q[Y]$

이때, $Q[W_2]=P(w_2|w_1)(\because{}Marginalization)$

그렇다면 $Q[Y]$는 ?
$\bold{H}=\{X,Y\}$인 sub-graph를 생각해보자. 이때, $X,\,Y$는 각각의 confounded component를 이룬다.

그에 따라, $Q[Y]={Q[X,Y]\over{}Q[X]},\\Q[X,Y]=\underset{w_1}{\sum}P(w_1)P(x|w_1,w_2)P(y|w_1,w_2,x)$이다.
(topological sort를 $X\prec{Y}\prec{}W_1$로 하면 ancestral reduction 적용 가능해짐)

마찬가지로 ancestral reduction 에 의해 $Q[X]=\underset{y}{\sum}{Q[X,Y]}$이므로, $P(y|do(x))$는 정리된다. (식이 굉장히 복잡하고, topological ordering과 sub-graph를 여러 개를 동시에 사고해야 하기에 복잡한 예가 되겠다.)

4. General Identificaion Algorithm

우선 처음의 $P(y|do(x))=\underset{\bold{v}\backslash(\bold{x}\cup\bold{y})}{\sum}Q[\bold{V}\backslash\bold{X}]$는 C-factor의 정의와 Marginalization을 생각하면 당연한 이야기다.

그렇지만 $\bold{v}\backslash{\bold{x\cup{}y}}$는 너무나도 많은 변수를 포함하므로 계산량을 줄이는 데에 있어, x를 제외한 y의 조상 노드들만 고려하면 충분하다는 것이 위의 알고리즘의 논지다.

이를 이용하여 다음과 같이 재귀적인 identify 알고리즘을 구성할 수 있고, 다음과 같은 정리가 성립한다.