Week13 Causal Discovery - Summary

[euphoria0-0]

Summary

Causal Discovery란 주어진 데이터로부터 원래의 인과 그래프를 찾는 것입니다.
기존에 다뤘던 Causal Inference는 (인과 그래프를 가정한 상황에서) 처치의 효과를 추정하는 것입니다.

Preliminary

Pearl's Causal Model

Judea Pearl 교수님은 Observation(L1), Intervention(L2), Counterfactual(L3)를 formulate하고 더 낮은 level로 더 높은 level을 설명할 수 없는 framework을 제시하였습니다.
SCM (Structural Causal Model)은 변수 별 원인과 결과를 나타내는 그래프를 만들고 이들간 함수적 관계를 표현하는 도구입니다.
T라는 변수에 Intervention을 하게 되면 T로 incoming하는 edge들은 사라지는 것을 표현할 수 있습니다.

Graphical Model

세 확률변수 X, Y, Z가 있을 때 C가 given되었을 때 X와 Y는 조건부 독립인 경우는 다음을 말하며 $X \perp !!! \perp Y|Z$로 표기합니다:
$$P(X,Y|Z)=P(X|Y,Z)P(Y|Z)=P(X|Z)P(Y|Z)$$

PGM (Probabilistic Graphical Model)에서 conditioning에 따라 조건부 독립성 특성이 달라지는 세 가지 구조가 있습니다.

1. Fork (X<-Z->Y): X와 Y는 서로 종속적이나, Z를 조건부로 두면 서로 독립이 된다.
2. Chain (X->Z->Y): X와 Y는 서로 종속적이나, Z를 조건부로 두면 서로 독립이 된다.
3. V-structure (X->Z<-Y): X와 Y는 서로 독립이나, Z를 조건부로 두면 서로 종속적이다.

조건부 독립성 특성을 이용하여 인과 그래프를 살펴볼텐데, 이 특성을 이용해도 그래프를 특정짓지 못하여 Causal Discovery를 못하는 경우가 발생합니다.
MEC (Markov Equivalence Class)는 조건부 독립성 특성이 같은 그래프 집합을 말하며, 독립성 특성이 같으므로 그래프를 unique하게 특정짓지 못하게 됩니다.
위에서 설명한 SCM 외에도 DAG (Directed Acyclic Graph), BN (Bayesian Network) 등 다양한 그래프가 있습니다.
BN은 DAG를 가정하고, SCM은 BN을 가정합니다.

Assumptions for Causal Discovery

Causal Discovery에는 많은 가정들을 포함하는데, 이들은 원인과 결과를 명확하게 알고, 데이터로 추정한 확률 분포로부터 그래프를 추정하기 위한 가정들입니다. 아래의 모든 가정이 무조건 필요한 것은 아니며, 최근에는 Acyclicity 등의 가정을 완화하는 연구들도 많습니다.

1. Acyclicity: SCM은 DAG를 포함하므로, 그래프 내 순환성이 없어야 한다.
2. Causal Markov Assumption: 그래프 내 각 노드는 오로지 자손(descendant) 노드에만 의존한다.
3. Causal Minimality Assumption: 불필요한 인과관계는 그래프 내에 존재하지 않아야 한다. (not allow Y = 0 ⋅ X)
4. Causal Sufficiency: 그래프 내 모든 변수들의 관측되지 않은 confounder는 존재하지 않는다.
5. Faithfulness Assumption: 그래프 내 연결된 노드는 확률적으로도 의존한다.

Methods

Causal Discovery에는 크게 Intervention을 이용하는 방법과 Intervention을 이용하지 않고 주어진 관측 데이터(Observational Data)만 이용하는 방법이 있습니다.

Causal Discovery with Intervention

Intervention은 가장 기본적으로는 두 변수간 관계를 찾고 싶은 방법인데, 모든 변수들의 인과관계를 찾고 그래프를 만들어나가기 위해선 여러 번의 intervention이 필요합니다. 다음과 같이 변수 X 혹은 Y에 한번만 intervention을 하게 되면 IEC (interventional Equivanlence Class; MEC의 intervention 가한 버전)로, (worst case의 경우) 구별할 수 없게 됩니다.

따라서, 우리는 여러가지 intervention 세팅이 있겠지만, intervention 자체는 굉장히 비용이 비싼 행위이므로 최소한의 intervention으로 인과그래프를 찾아야 합니다.

Causal Discovery with Observations

관측 데이터를 이용한 방법은 크게 3가지 방법으로 나뉩니다. 조건부 독립성을 이용한 Constraint-based 방법 (혹은 Independence-based 방법), 모델의 적합성(fitting) 점수를 이용한 score-based 방법, 그리고 SCM의 변수 간 함수적 관계의 함수 클래스에 제약을 가하는 functional 방법이 있습니다.
각각의 대표적인 방법은 아래와 같습니다:

[fenzhantw]

1. Causal Discovery from intervention에서 "개입(intervention) 자체는 굉장히 비용이 비싼 행위"라는 점이 이해되지 않습니다. 데이터와 graph가 identifiability 조건에서 주어진다면, do-operation을 통해 X->Y 효과(L2 quantity)를 계산할 수 있는 것으로 알고 있습니다.

여기서 개입이라는 것이 X->Y를 추정할 수 있는 identifiability한 조건을 만들어주기 위해 RCT 처럼 처치군과 대조군을 구분하여 실험을 한다는 의미인가요? 만약에 아니라면, 여기서 말하는 비용적 문제는 계산 복잡성을 말하는 것인가요?

2. 완전 그래프에서의 Intervention은 어떻게 수행되는건가요?, 어떤 기준으로 A -> B , B <- A, A--B가 결정될 수 있나요?

3. Causal Discovery를 통해 얻은 인과 그래프의 성능이나 정확도는 어떻게 평가할 수 있나요?

항상 좋은 자료와 열띤 참여 감사합니다 : )

[euphoria0-0]

좋은 질문 주셔서 감사합니다.

1. 개입(intervention)의 비용에 대한 질문

데이터와 graph가 identifiability 조건에서 주어진다면, do-operation을 통해 X->Y 효과(L2 quantity)를 계산

네, 다만 말씀하셨다시피 graph가 "주어졌을 때"이기 때문에 이미 Causal Discovery 등을 통해 graph가 완성된 상태에서 처치에 대한 "효과를 추정" 할 수 있습니다.

개입이라는 것이 X->Y를 추정할 수 있는 identifiability한 조건을 만들어주기 위해 RCT 처럼 처치군과 대조군을 구분하여 실험을 한다는 의미인가요? 만약에 아니라면, 여기서 말하는 비용적 문제는 계산 복잡성을 말하는 것인가요?

여기서의 개입(intervention)은 하나의 값을 일괄적으로 할당하는 실험을 말합니다. do-operator로 표현하면, $$do(X:=x)$$은 변수 X에 대해서 x라는 값을 일괄적을 할당하는 처치를 수행하여 개입 데이터 (interventional data)를 모은다로 생각하시면 됩니다. 따라서 처치군과 대조군을 랜덤하게 나눠야하는 RCT와는 다릅니다.

이 경우 개입이 비용적으로, 윤리적으로 이슈가 발생할 수 있습니다.
비용적으로는 특정 변수의 인과 관계를 알고 싶은데, 그 변수에 개입을 가하는 것이 아예 불가하거나 비용이 비싸 어려울 수 있습니다(e.g. 특정 조건을 갖춘 사람들을 모아 비용을 지불하며 실험을 해야하는 경우).
윤리적으로도 특정 변수의 개입을 가하는 것이 어려울 수 있습니다(e.g. 희귀병 환자에게 약을 무조건 투약해야 하는 상황에서 약을 주지 않도록 개입하는 경우. RCT에서는 희귀병 환자 중 랜덤하게 나누어 어떤 그룹은 주고 어떤 그룹은 주지 않아야 하는데 그런 상황이 어려운 경우 개입을 생각할 수 있습니다.).
따라서 개입(intervention)이 특정 변수들에 가하는 것이 어려운 경우가 존재하며, 이를 회피하거나 최소화하는 방법이 필요할 수 있습니다.

2. 개입(intervention)으로부터 어떻게 Causal Discovery를 할 수 있을지에 대한 질문

완전 그래프에서의 Intervention은 어떻게 수행되는건가요?, 어떤 기준으로 A -> B , B <- A, A--B가 결정될 수 있나요?

기본적으로 효과(Effect)에 개입(intervention)을 가하면 효과 변수에 incoming하는 edge는 모두 제거할 수 있습니다. 이 개념을 활용해 개입으로부터 인과관계를 찾아나가는 것이 Causal Discovery with Intervention입니다.

두 변수 X, Y가 있습니다. 이 둘의 인과관계를 찾는 문제를 생각해봅시다.
문제 상황은 개입 이전에 관측 데이터(observational data)만으로 (조건부) 독립성 검정을 수행했을 때, 이 둘은 종속으로 나타났다고 가정합니다 (complete graph).
먼저, X에 개입을 한 후, 개입 데이터(interventional data)로부터 독립성 검정을 수행했을 때, X와 Y가 독립이라는 결과를 얻었습니다. 이 경우, 이전에는 종속이었으나 독립으로 나타났으므로, X에 incoming하는 edge가 제거되어 X와 Y가 독립이 된 것이므로, X가 효과(Effect)이고 Y가 원인(Cause)입니다.
만약, X에 개입을 했을 때 X와 Y가 종속이라는 검정 결과를 얻었다고 생각해봅시다. 이 경우, 개입 이전에도 종속, 이후에도 종속으로 나타난 것이며, 이는 어떤 edge도 제거되지 않은 것을 추측할 수 있으므로 X가 원인, Y가 효과임을 알 수 있습니다.

다만, complete graph 상에서 이변량 문제는 간단하지만, incomplete graph 혹은 여러 변수가 있는 상황에서는 한 번의 intervention 만으로는 그래프를 식별해내기 어렵습니다[1]. 즉, MEC (Markov Equivalence Class) 혹은 IEC (Interventional Equivalence Class)가 굉장히 흔하게 발생하므로 여러 번의 intervention이 필요합니다.

[1] Eberhardt, F., Glymour, C., & Scheines, R. (2006). N-1 experiments suffice to determine the causal relations among n variables. Innovations in machine learning: theory and applications, 97-112.

3. Causal Discovery의 Evaluation에 대한 질문

일반적으로 변수의 수는 알려진 상황에서, edge를 잘 orient했는지를 평가해야 합니다. 따라서 추정한 edge별로 일반적인 Precision, Recall 등의 metric을 이용해 평가합니다.
다만, 평가하고자 하는 인과관계가 "명확한" 도메인의 데이터를 구하는 것은 쉽지 않습니다. 따라서 제가 알기로는 1) 인과관계가 잘 알려져 있는 데이터(e.g. 물리)를 활용하거나, 2) 인과관계가 명확하도록 "생성된" 합성(Synthetic) 데이터를 이용해 방법론(알고리즘)을 평가하곤 합니다.