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 test로 독립 관계 발견
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

공통 알고리즘 구조

Phase 1: Skeleton Learning

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)

Phase 2: Edge Orientation

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

Significance level α: 보통 0.01 또는 0.05

장단점

장점

1. 이론적 보장

   • Faithfulness 하에서 asymptotic consistency
   • True MEC 복원 보장 (large sample)

2. 해석 가능

   • 각 edge 제거/방향 결정에 명확한 이유
   • SepSet 정보 활용 가능

3. 구현 용이

   • 표준 CI test 활용
   • 많은 구현 존재 (pcalg, causal-learn 등)

단점

1. High-dimensional 한계

   • Conditioning set 크기 exponential
   • 많은 CI test 필요

2. Finite sample 문제

   • CI test power 감소 (작은 n, 큰 conditioning set)
   • Order-dependence (PC)

3. Faithfulness 의존

   • Unfaithful distribution에서 실패

개선 방향

Order-independence

• PC-stable: Edge 제거 순서 무관
• CPC (Conservative PC): 불확실한 방향은 undirected

효율성

• Parallelization: CI tests 병렬화
• RFCI: FCI의 일부 tests 생략

Robustness

• Majority voting: 여러 subsets에서 일치하는 결과

관련 개념

Algorithm Details

• PC Algorithm - 대표적 constraint-based 알고리즘
• FCI Algorithm - Latent confounders 허용
• Conditional Independence Test - CI test 종류

Theoretical Foundations

• Faithfulness - 필수 가정
• d-separation - CI ↔ graph 대응
• CPDAG - PC output
• PAG - FCI output

Comparison

• 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