[Causal Discovery] PC algorithm

Causal Discovery의 개념과 그 중 대표적인 알고리즘인 PC algorithm에 대해 정리한 글입니다.

아래 그림의 출처는 [Youtube] [Session 18-3] 데이터 기반의 인과관계 발견(Causal Discovery)입니다 

 

---

인과 다이어그램이란

변수 간의 인과관계를 도식화 한 것을 인과다이어그램(Causal Diagram)이라고 합니다. 동그라미로 표시된 노드는 변수를 의미하고, 화살표로 표시된 엣지는 두 변수 간 직접적인 인과 관계를 의미합니다 (화살표가 나가는 노드가 원인, 화살표가 향하는 노드가 결과입니다)

인과 다이어그램을 왜 그릴까요? 우리의 관심사인 원인과 결과 간의 인과관계를 알기 위해서입니다. 두 변수 간 인과관계를 확인하기 위해 통제해야할 path 및 노드(변수)를 규명하기 위함입니다. 두 변수 간 인과 관계를 측정할 때 외부 영향을 통제하지 않은 상태에서 단순히 두 변수 간 상관성만 본다면 인과 관계가 아닌 여러 요인의 영향이 섞인 상관 관계를 추정할 가능성이 높습니다. 이를테면 위의 그래프에서 $T$가 $Y$에 미치는 인과 효과를 알고 싶다면 $T \leftarrow A \leftarrow B \rightarrow C \rightarrow Y$로 흐르는 외부 영향을 통제해야합니다.

즉, 조건 통제를 통해 인과관계를 추정하기 위해서는 인과 다이어그램이 필요합니다.

 

Causal Discovery

위에서 언급하였듯이 조건 통제를 통해 인과 관계를 규명하기 위해서는 외부 영향이 무엇이 있는지 확인해야하고, 이를 위해 변수 간 주고 받는 영향을 도식화 한 인과다이어그램이 필요하다고 하였습니다. 기존에는 인과다이어그램을 연구자가 도메인 지식에 의거하여 설계하였기에, 연구자마다 설계한 다이어그램이 다를 수 있으며 또한 실제 인과다이어그램과 일치하지 않을 수 있다는 문제점이 있습니다.

그래서 데이터에 기반하여 객관적으로 인과다이어그램을 그리는 방법이 필요하였고 이 때 등장한 것이 Causal Discovery입니다.

Causal Discovery는 우리가 가진 데이터에서 변수 간 관계를 이용하여 인과 다이어그램을 그리는 방법입니다.

그리고 본 포스팅에서는 대표적인 방법 및 알고리즘인 PC 알고리즘에 대해 소개하고자 합니다.

Data Driven Causal Discovery

 

변수 3개의 관계를 먼저 보자

가장 먼저 심플하게 데이터로 변수 3개 간의 관계를 추론해봅니다. (이후 이 룰을 적용해나가며 여러 변수 간 관계로 확장해나가며 인과다이어그램을 그릴 것입니다)

변수 3개 간에 나타날 수 있는 관계는 크게 3가지입니다. 그리고 Markov Assumption 하에 각 관계에서 conditioning independence는 다음과 같이 나타납니다.

Chain

$$X \not\perp\!\!\perp Y$$

$$X \perp\!\!\perp Y | C$$

Fork

$$X \not\perp\!\!\perp Y$$

$$X \perp\!\!\perp Y | C$$

Immorality

$$X \perp\!\!\perp Y$$

$$X \not\perp\!\!\perp Y | C$$

 

위와 같이 변수 간 관계에 따라 conditioning independence check 결과가 다르게 나오므로 (참고. Chain과 Fork는 결과가 같습니다) 이를 역으로 이용하여 세 변수 간의 관계를 추론할 수 있습니다.

 

Markov Equivalent Class

세 변수 간 conditioning independence를 확인하였을 때, $X \not\perp\!\!\perp Y$이고 $X \perp\!\!\perp Y | C$ 라면 $X$,$Y$,$C$의 관계를 확정할 수 없습니다. 세 변수 간 Chain, Fork 형태 둘 다 가능하기 때문입니다.

이렇듯 동일한 conditional independence를 갖는 변수 관계들의 집합을 Markov Equivalent Class라고 합니다.

Markov Equivalent Class

예를 들어 보겠습니다

관계를 하나로 규정할 수 없는 경우

$X \not\perp\!\!\perp Y$이며 $X \perp\!\!\perp Y | Z$라는 패턴이 나왔다면 세 변수 간 관계는 위의 초록색 표시가 된 클래스입니다. 세 변수 간 관계가 3가지 중 하나일 것입니다. 변수 간 인과관계를 하나로 규정할 수 없는 것이지요.

흠, 명확히 규정할 수 없다라.. 너무 아쉬운 부분입니다. 방법이 없을까요?

 

관계를 하나로 규정할 수 있는 경우

아닙니다, 여기서 주목할 구조가 있습니다. 바로 Immorality 구조입니다. 해당 구조에서는 Markov Equivalence Class의 집합의 요소는 한 개입니다. 즉 세 변수 간 관계를 특정할 수가 있다는 의미입니다.

(그림에서 볼 수 있듯이 두 엣지의 방향이 하나의 노드로 모이기 때문에 "V Structure"라고도 불립니다)

$X \perp\!\!\perp Y$ 이고 $X \not\perp\!\!\perp Y | Z$라는 패턴이 나왔다면 이 세 변수 간 관계는 하나만 존재합니다. 바로 위의 빨간색 표시가 된 Immorality 관계입니다.

 

이처럼, conditioning independence check를 이용한 Causal Discovery에서 Immorality 구조는 엣지의 방향을 규정하는 중요한 단서가 됩니다.

 

PC 알고리즘

이제 인과다이어그램을 도출하기 위한 Causal Discovery 방법론 중 대표적인 PC 알고리즘에 대해 알아보겠습니다. 

(알고리즘의 이름은 이를 개발한 개발자의 이름에서 비롯되었다고 합니다)

 

PC 알고리즘의 각 단계를 예시를 통해 살펴보겠습니다.

변수는 총 4개($X$, $Y$, $W$, $Z$)이며 ground truth에 해당하는 인과다이어그램은 아래와 같습니다.

 

이제 주어진 데이터에서 변수 간 conditioning independence check를 통해 causal diagram을 도출하는 알고리즘 중 하나인 PC 알고리즘을 사용하여 아래의 ground truth에 해당하는 다이어그램을 도출해보겠습니다 

 

1. Complete Undirected Graph 로 시작합니다.

우리가 가지고 있는 변수를 노드로 표시하고 해당 변수들 간에 방향이 없는 엣지를 그려줍니다. 모두 변수 간 연결된 상태에서 시작하는 것입니다.

 

2. Conditioning 없이도 Independence(독립) 관계인 두 노드 사이의 엣지를 제거합니다.

직접적으로 연결되지 않은 두 노드 간 엣지를 제거해주는 작업입니다.

예시에서 각 노드 쌍 간 independence check를 하면 아래와 같습니다. 따라서 $X - Y$를 연결하는 엣지만을 제거합니다.

(1) $X \perp\!\!\perp Y$: independent

(2) $X \not\perp\!\!\perp W$: 실제 $X \rightarrow Z \rightarrow W$ 연결(chain형태)되어 있으므로 dependent

(3) $X \not\perp\!\!\perp Z$: 실제 $X \rightarrow Z$ 로 연결되어 있으므로 dependent

(4) $Y \not\perp\!\!\perp W$:실제 $Y \rightarrow Z \rightarrow W$ 연결(chain형태)되어 있으므로 dependent

(5) $Y \not\perp\!\!\perp Z$: 실제 $Y \rightarrow Z$ 로 연결되어 있으므로 dependent

(6) $Z \not\perp\!\!\perp W$: 실제 $Z \rightarrow W$ 로 연결되어 있으므로 dependent

 

3. 다른 변수를 Conditioning하였을 때 두 변수 간 Independence가 되는 경우, 엣지를 제거해줍니다.

사실 두 변수는 직접적으로 연결되어 있지 않으나 다른 변수에 의해 두 변수가 dependent한 경우(Chain 또는 Fork)입니다. 즉, 두 변수는 직접적으로 연결되어 있지 않으므로 둘 사이의 엣지를 제거하는 것입니다.

 

위의 2번 단계의 (2), (4)번에 해당합니다. $X - W$ , $Y - W$ 는 직접적으로 연결되어 있지 않으나 $Z$에 의해 상관성을 갖습니다(dependent).

설명하자면, conditioning하지 않았을 때는 $X \not\perp\!\!\perp W $, $Y \not\perp\!\!\perp W $ 로 dependent하지만

$Z$로 conditioning 하였을 때는 $X \perp\!\!\perp W | Z$, $Y \perp\!\!\perp W | Z$ 로 independent하게 됩니다.

즉, conditioinal independence check를 통해 두 변수는 직접적으로 연결된 것이 아니며 $Z$를 통해 상관성이 생긴 것임을 알 수 있습니다.

따라서 $X - W$, $Y - W$ 사이의 직접적으로 연결된 엣지는 제거해줍니다.

 

(3번 과정을 마친 그래프는 필요한 엣지만 남게 되므로 skeleton(뼈대)이라고 부릅니다.)

 

4. V structure를 규명하여 엣지의 방향을 정해줍니다.

위의 markov equivalent class에서 중요하다고 한 Immorality 구조(V structure)가 여기서 등장합니다. 세 변수 간 conditioning independence check를 하였을 때 Immorality 구조에 부합하는 패턴이 나오는 경우 엣지의 방향을 하나로 규정할 수 있기 때문에 해당 과정을 통해 확실한 엣지방향을 먼저 만들어주는 것입니다.

V structure가 될 수 있는 경우를 확인해봅니다.

 

1) $X \rightarrow Z \leftarrow Y$ 라면

$X \perp\!\!\perp Y$, $X \not\perp\!\!\perp Y | Z$ 이어야 합니다. 실제로 맞습니다.

따라서 우리는 $X \rightarrow Z \leftarrow Y$로 엣지의 방향을 규명할 수 있습니다.

 

2) $Y \rightarrow Z \leftarrow W$ 라면

$Y \perp\!\!\perp W$, $Y \not\perp\!\!\perp W | Z$ 이어야 합니다.

하지만 실제로는 $Y \rightarrow Z \rightarrow W$  이므로 $Y \not\perp\!\!\perp W$, $Y \perp\!\!\perp W | Z$가 될 것입니다. 즉 $Z$, $Y$, $W$는 Immorality 구조가 아닙니다.

 

5. collider를 만들지 않도록(immorality 구조) 남아있는 undirected edge의 방향을 정해줍니다.

4번을 통해 Immorality 구조를 모두 찾았으며 방향이 확정되지 않은 엣지의 방향을 정해주는 단계입니다. 

 

이렇게 5단계를 거쳐 인과 다이어그램을 도출할 수 있습니다.

 

PC 알고리즘의 한계점

PC 알고리즘은 접근 방법이 매우 심플하지만 두 가지 한계점을 갖고 있습니다.

 

1. unobserved confounder를 규명하지 못한다

 PC 알고리즘은 관찰하지 못한 confounder는 존재하지 않는다는 가정 하에 수행됩니다. 만약 우리가 관찰하지 못한 (혹은 측정하지 못한) confounder가 존재한다면 실제 인과다이어그램은 다르게 나타날 수 있습니다. 그렇게 되면 PC 알고리즘으로는 ground truth에 해당하는 인과 다이어그램을 도출할 수 없게 됩니다.

 

2. edge의 방향을 규명하지 못하는 경우가 존재한다

---

마치며

Causal Discovery를 위한 PC algorithm에 대해 알아보았습니다.

한계점이 존재하지만 빠르게 적용하는 base model로는 좋은 것 같습니다.

 

긴 글 읽어주셔서 감사합니다.

 

▼ 글이 도움이 되셨다면 아래 클릭 한번 부탁드립니다 :) ▼