Constraint-Based Methods Overview

개요

Constraint-based methods는 데이터에서 조건부 독립(conditional independence, CI) 관계를 검정해 인과 그래프를 복원하는 방법이다. Faithfulness 가정이 성립할 때 CI 관계와 d-separation이 일대일로 대응한다는 성질을 활용한다.

Mermaid source (click to expand)

> flowchart LR
>     Data[Data] --> CI[CI Tests]
>     CI --> Skeleton[Skeleton Learning]
>     Skeleton --> Orient[Edge Orientation]
>     Orient --> Graph[CPDAG/PAG]
>

핵심 아이디어

Faithfulness 가정: $X \perp_P Y \mid Z \iff X \perp_\mathcal{G} Y \mid Z$

1. CI 검정으로 독립 관계를 찾는다
2. 독립 관계가 d-separation에 대응한다
3. 이로부터 그래프 구조를 추론한다

주요 알고리즘 비교

Algorithm	Output	Latent OK	Complexity	Key Feature
PC Algorithm	CPDAG	✗	$O(n^d)$	Standard baseline
FCI Algorithm	PAG	✓	$O(n^{d+2})$	Latent confounders
CPC	CPDAG	✗	$O(n^d)$	Conservative PC
RFCI	PAG	✓	$O(n^d)$	Fast FCI

공통 알고리즘 구조

1단계: Skeleton 학습

1. Complete undirected graph로 시작
2. 각 edge (X, Y)에 대해:
   - Conditioning set Z ⊆ Adj(X) 탐색
   - X ⊥ Y | Z 이면 edge 제거
   - Z를 SepSet(X, Y)에 저장
3. 결과: Skeleton (undirected graph)

2단계: Edge 방향 결정

1. v-structure 식별:
   - X — Z — Y에서 Z ∉ SepSet(X, Y)
   - → X → Z ← Y
2. Orientation rules 적용:
   - Meek rules (PC)
   - FCI orientation rules (FCI)
3. 결과: CPDAG 또는 PAG

조건부 독립성 검정(conditional independence test)

Conditional Independence Test 참조:

Test	Data Type	Assumption
Fisher’s z	Continuous	Gaussian
Partial correlation	Continuous	Linear
G-test / χ²	Discrete	-
KCI	Any	Nonparametric

유의수준 α: 보통 0.01 또는 0.05를 쓴다.

장단점

장점

1. 이론적 보장

   • Faithfulness가 성립하면 점근적 일치성(asymptotic consistency)이 보장된다
   • 표본이 충분히 크면 참 MEC를 복원한다

2. 해석 가능

   • 각 edge를 제거하거나 방향을 정하는 데 명확한 근거가 있다
   • SepSet 정보를 활용할 수 있다

3. 구현 용이

   • 표준 CI 검정을 그대로 쓴다
   • pcalg, causal-learn 등 구현체가 많다

단점

1. 고차원(high-dimensional) 한계

   • conditioning set의 크기가 지수적으로 커진다
   • 그만큼 많은 CI 검정이 필요하다

2. 유한 표본 문제

   • 표본 n이 작거나 conditioning set이 크면 CI 검정의 검정력이 떨어진다
   • PC는 처리 순서에 결과가 달라진다(order-dependence)

3. Faithfulness 의존

   • faithfulness가 깨진 분포에서는 실패한다

개선 방향

처리 순서 비의존성(order-independence)

• PC-stable: edge 제거 결과가 처리 순서에 무관하다
• CPC (Conservative PC): 방향이 불확실한 edge는 무방향으로 남긴다

효율성

• Parallelization: CI 검정을 병렬화한다
• RFCI: FCI에서 일부 검정을 생략한다

강건성(robustness)

• Majority voting: 여러 부분집합에서 일치하는 결과를 채택한다

관련 개념

알고리즘 상세

• PC Algorithm - 대표적인 constraint-based 알고리즘
• FCI Algorithm - 잠재 교란변수(latent confounder)를 허용
• Conditional Independence Test - CI 검정의 종류

이론적 토대

• Faithfulness - 필수 가정
• d-separation - CI와 그래프의 대응
• CPDAG - PC의 출력
• PAG - FCI의 출력

비교

• Score-Based Methods Overview - 대안적 접근
• Hybrid Methods Overview - constraint와 score의 결합

참고 논문

• Spirtes, Glymour, Scheines (2000). Causation, Prediction, and Search
• Colombo & Maathuis (2014). Order-independent constraint-based causal structure learning
• zangaSurveyCausalDiscovery2023 - Section 3.1