SNU Causal Inference : Adjustment Criterion

1. Back-door Criterion

1.1 Conditional Back-door Criterion

위의 정리에 따르면, 앞서 배운 back-door criterion을 만족하는 변수들에 대해, w를 만족하는 특정 집단에 대한 treatment의 인과효과를 측정할 수 있으며 이를 w-specific effect 라고 부른다.

1.2 Tightness of the Back-door Criterion

위의 그래프의 경우, $Z_1,\,Z_2$ 모두 $X_1$ 의 후손(descendant) 이므로 back-door criterion을 만족하지 않기에 얼핏 보면 Adjustment formula를 사용하지 못할 것처럼 보인다.

하지만 실제론 $Z_2$를 이용하면 $X_2$ 에서 $Y$로 가는 back-door path가 끊어지게 되므로 곧 $P(Y|do(X_1),do(X_2))=\underset{z_2}{\sum}P(Y|X_1,X_2,z_2)P(z_2)$와 같은 형태로 계산할 수 있다.

이에 따라, back-door criterion 이 adjustment formula 를 적용할 수 있는지에 대해 충분조건일 뿐, 필요 충분 조건이 아니기에 이를 정의하고자 한다.

---

2. Adjustment Criterion

2.1 Proper Causal Paths

Adjustment formula를 이용하여 인과 효과를 계산할 수 있는 조건을 정의하기에 앞서, 먼저 Proper Causal Path, 곧 실제로 인과 효과를 일으키는 경로들에 대해 정의내릴 필요가 있다.

다음의 그래프가 주어져 있다고 생각해보자. Intervention은 곧 주어진 Graph $\mathcal{G}$ 을 변형하는 것으로, 이를 Graph Surgery 라고도 부른다.

X를 condition 함으로서 우리가 새로운 그래프에서 얻을 수 있는 인과 경로 상의 중간에는 다른 X 집합 안의 변수는 들어올 수 없다. 이유는 intervention은 곧 X 집합 내의 노드들의 incoming edge를 pruning 하는 것이기 때문이다.

고로 우리는 $\bold{X}\rightarrow\bold{Y}$ 로의 진정한 인과 경로 상에서 출발점을 제외한 그 어떠한 중간 지점에도 X 집합 내 원소는 존재하지 않는다고 정의한다.

Proper Causal Paths of given Graph $\mathcal{G}$
$X_1\rightarrow{W_3}\rightarrow{Y}\\X_2\rightarrow{W_2}\rightarrow{Y}\\$
Non-proper Causal Path
$X_1\rightarrow{W_1}\rightarrow{X_2}\rightarrow{W_2}\rightarrow{Y}$

이때, 만약 proper causal path 의 변수의 자손을 사용할 경우, adjustment formula를 이용하여 인과 효과를 계산할 수 없다.

고로, adjustment criterion 은 identifiability 에 대한 조건이 아닌, adjustment formula 를 사용할 수 있는지에 대한 필요 충분 조건인 것 뿐이므로 이에 주의하도록 하자.

귀류법(Proof by Contradiction)으로 위가 참임을 보여보자.
z를 이용해서 adjustment formula를 통해 X가 Y에 미치는 인과 효과를 계산할 수 있다고 가정하자. 위의 경우 confounding bias 가 존재하지 않으므로 $P(y|do(x))=P(y|x)$ 이다.

$P(y|do(x))\\=\underset{z}{\sum}{P(y|x,z)P(z)}\\=\underset{z}{\sum}P(z)\underset{w}{\sum}P(w,y|x,z)\\=\underset{z}{\sum}P(z)\underset{w}{\sum}P(y|w)P(w|x,z)P(x|z)\\=\underset{z}{\sum}\underset{w}{\sum}P(x,y,z,w)\\=P(x,y)\neq{P(y|x)}$ (in general, but can be equal)

따라서 모순이 발생, z로는 adjustment formula를 사용할 수 없음을 쉽게 알 수 있다.

2.2 Implementation of Adjustment Criterion

이산 수학적으로 주어진 집합 X, Y, Z와 $\mathcal{G}$에 대해 Z가 adjustment criterion을 만족하는지 여부를 반환하는 알고리즘을 설계해보자.

$\mathcal{G}_{\bar{X}}\equiv$ Graph after intervention (do(X))
$\bold{W}=De(\bold{X})_{\mathcal{G}_{\bar{X}}}\cap{An(\bold{Y})_{\mathcal{G}_{\bar{X}}}}$

이때, proper causal path로 이루어지고 bidirected edge를 제거한 그래프를 $\mathcal{G}[\bold{W}]$ 라 표현할 수 있고, $\mathcal{H}$라 표시하자.

$\bold{F}\equiv$ Set of variables forbidden to adjustment
$\bold{F}=De(\bold{W}\backslash\bold{X})_{\mathcal{G}_{\bar{X}}}$

우선적으로 $\bold{Z}\cap\bold{F}=\empty$인지 확인한다. 만약 공집합이 아니라면 adjustment criterion을 위배하므로 바로 False 를 반환한다.

그 다음 D-Separation 여부를 확인하는데, 요약하자면 proper non-causal path들을 전부 본 다음 각 Path 별로 in-active triplet 이 존재하는지 확인하는 과정이라 말할 수 있다. 그렇게 모든 proper non-causal path가 d-separated 되었다면 Adjustment Formula를 적용할 수 있다.

---

3 Algorithms

3.1 Checking for Adjustment Criterion

주어진 그래프 $\mathcal{G}$ 에 대해, $\bold{Z}=\{C,D,I\}$는 adjustment criterion을 만족하는가?
(Is given set Z is admissible for adjustment?)

우선 proper causal path들을 전부 작성한다.

Proper Causal Paths in $\mathcal{G}$
$X_1\rightarrow{Y_1}\\X_1\rightarrow{E}\rightarrow{Y_2}\\X_2\rightarrow{F}\rightarrow{Y_2}$

이때, Proper causal path 내 변수들의 descendant 들을 정리한다.

Descendants of variables in proper causal path
$H$ (Descendant of both $Y_1,\,F$)

그러고 난 뒤, Proper causal path의 각 첫 번째 간선을 끊어버린다.

Why?

Proper causal path의 첫 번째 간선을 잘라내면 집합 X 내 변수들에서 Y로 가는 경로들은 proper non-causal path 만 존재한다.

이후에 C, D, I 변수들이 given일 때 하나 이상의 active path가 존재한다면 proper non-causal path를 모두 막지 못하므로 adjustment criterion을 만족하지 못하고, 어떠한 경로도 존재하지 않는다면 adjustment criterion을 만족한다고 볼 수 있다.

3.2 Construction of Admissible Sets

쉽게 말해서, 만약에 adjustment criterion을 만족하는 어떠한 집합 Z가 존재한다면 X와 Y의 조상 집합에서 X, Y, F를 뺀 집합 $\bold{Z_0}$는 무조건 adjustment criterion 을 만족 시킨다는 것이다.

다르게 말하면? Contraposition 인 $\bold{Z_0}$가 adjustment criterion을 만족하지 못한다면 어떠한 집합 Z도 adjustment criterion을 만족시키지 못한다는 것이다.

하지만 현실에선 모든 변수들을 관찰 가능한 것이 아니기 때문에, 다른 변수 집합 Z를 알 수 있다면 그 중 사용 가능한 집합을 사용하여 인과 효과를 계산할 수 있기에 이에 대한 알고리즘이 필요했다.

Polynomial Delay Class

모든 가능한 $\bold{Z}$ 를 열거하여 하나 하나 가능한지 확인하는 것은 못해도 지수 시간이 소요됨. (각 경우당 $O(1)$ 이 소요된다고 해도 $O(2^{| \bold{Z_0}|})$

그렇다면 전체 시간 자체는 지수 시간 아래로 낮출 수 없다고 하더라도 각 조합 별 시간 간격을 다항 시간으로 효율적으로 할 수 있다면?

이를 만족 시키기 위해 Inclusion and Restriction 을 활용한 Divide-and-Conquer 전략을 채택한 것이 바로 List-Seps 알고리즘이다.

앞서 다루었던 Forbidden Set F 에 대해, $\bold{F^+}=\bold{X\cup{Y}\cup{F}}$ 라 하자.
이때, 처음에 $\bold{I}=\empty,\,\bold{R}=\bold{V}\backslash{\bold{F^+}}$라 하고, graph $\mathcal{G}$ 에서 proper causal path의 첫 간선을 끊어두었다고 생각하자.

이때, 각각 inclusion, exclusion 하며 아래와 같은 이진 트리 형태로 전개해가며 inclusion set과 exclusion set이 같아질 때까지 트리를 전개하고, 중간에 d-separation 을 restriction set이 만족하지 못한다면 pruning 하는 식으로 전개할 수 있다.

그에 따라, 각 조합 별 간격은 $O(n^2+nm)$ 로 polynomial delay를 만족한다.