- acyclicity, causal faithfulness, causal sufficiency가 충족되면 PC 알고리즘을 사용해 데이터에 맞는 인과 구조를 도출할 수 있다
- PC 알고리즘 절차
- 그래프 뼈대 잡기 (방향성 없는 변으로만 구성)
- v-structure 잡기 (D-separation 기반)
- 추가적으로 변의 방향 잡기
- 모든 변의 방향성이 정해지지 않을 수 있어 PDAG(Partially Directed Acyclic Graph)가 나올 수도 있다
Step1: 그래프 뼈대 잡기
- 뼈대(skeleton)은 방향성 그래프를 모두 방향성 없는 그래프로 바꾼 형태
- 모든 정점(node)이 연결된 무방향성 그래프에서 시작
- k=0,1,2,... 에 대해 $|S|=k$인 $X_i$와 $X_j$에 인접한 모든 $X_s$에 대해 조건부 독립을 테스트한다
- 말이 어려운데 a와 b의 관계를 볼 때 조건부를 Null부터 c, {c,d}, {c,d,e}, ... 순으로 넣는다는 것을 의미한다.
- a~f 변수가 있다면 a와 b의 관계, a와 c의 관계, ...를 구할텐데 a와 c의 관계를 구할 때는 앞서 {a,b,c}의 관계를 구했기 때문에 굳이 b는 확인하지 않아도 된다
- 사전에 정한 유의성 레벨 $\alpha$보다 큰 조건부 독립 변을 제거한다
Step2: v-structure 잡기
i와 k가 인접하지 않은 i o-o j o-o k 일 때 d-separation을 통해 v-structure를 파악한다 (항상 triplet의 관계를 파악하는 것이 핵심)
Step3는 v-structure를 통해 나온대로 하면 됨