Score-Based Methods Overview

개요

**점수 기반 방법(score-based methods)**은 각 그래프에 점수 함수(score function)를 부여하고, 데이터에 가장 잘 맞는 그래프를 탐색하는 인과 발견 접근법이다. 제약 기반 방법(constraint-based)이 조건부 독립성 검정(CI test)을 반복하는 것과 달리, 점수 기반 방법은 모델 적합도(model fit)를 직접 최적화한다.

Mermaid source (click to expand)

> flowchart LR
>     Data[Data] --> Score[Score Function]
>     Score --> Search[Search Algorithm]
>     Search --> Best[Best Graph/MEC]
>

핵심 아이디어

최적화 문제: $\mathcal{G}^* = \arg\max_{\mathcal{G} \in \text{DAGs}} S(\mathcal{G}; D)$

$S$ : 점수 함수 (BIC, BGe 등)
$D$ : 데이터
효율을 위해 MEC 단위로 탐색한다

주요 알고리즘 비교

Algorithm	Search Strategy	Complexity	Feature
GES	Greedy	$O(n^4)$	Forward-backward phases
FGES	Parallel Greedy	Fast	Parallelized GES
Hill-climbing	Local search	$O(n^2)$	Simple but local optima
NOTEARS	Continuous opt	$O(n^3)$	Acyclicity constraint

점수 함수(score functions)

BIC (Bayesian Information Criterion)

$S_{\text{BIC}}(\mathcal{G}; D) = \log P(D | \hat{\theta}, \mathcal{G}) - \frac{k}{2}\log n$

$k$ : 모수 개수
$n$ : 표본 크기
모델 복잡도에 벌점을 부과한다

BGe (Bayesian Gaussian equivalent)

$S_{\text{BGe}}(\mathcal{G}; D) = \log P(D | \mathcal{G})$

가우시안 가정을 둘 때의 **주변 가능도(marginal likelihood)**다.

켤레 사전분포(conjugate prior)를 사용한다
닫힌 형식(closed-form)으로 계산된다

BDeu (Bayesian Dirichlet equivalent uniform)

$S_{\text{BDeu}}(\mathcal{G}; D) = \sum_{i} \sum_{j} \left[ \log\frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij} + n_{ij})} + \sum_k \log\frac{\Gamma(\alpha_{ijk} + n_{ijk})}{\Gamma(\alpha_{ijk})} \right]$

이산형 데이터(discrete data)에 쓰는 점수다.

점수 동치성(score equivalence)

정의: 점수가 MEC 안에서 일정하다는 성질이다.

$\mathcal{G}_1 \equiv \mathcal{G}_2 \implies S(\mathcal{G}_1; D) = S(\mathcal{G}_2; D)$

함의:

MEC 안의 DAG들을 서로 구분하지 못한다
대신 CPDAG를 직접 탐색할 수 있다

장단점

장점

충실성(faithfulness)을 요구하지 않음
- 제약 기반 방법보다 약한 가정에 기댄다
- 충실하지 않은 분포(unfaithful distribution)에서도 동작한다
원칙에 기반한 모델 선택
- 베이지안(Bayesian) 틀을 따른다
- 복잡도를 자동으로 제어한다 (BIC 벌점)
전역 최적화
- 국소적인 CI 판단이 아니라 전역 적합도를 본다

단점

NP-난해(NP-hard) 문제
- DAG 공간이 초지수적으로 커진다
- 탐욕적 탐색(greedy search)은 국소 최적점(local optima)에 빠질 수 있다
점수 함수 선택
- 결과가 어떤 점수를 쓰느냐에 좌우된다
- 모델 오설정(misspecification) 문제가 있다
계산 비용
- 고차원(high-dimensional)에서 느리다
- FGES로 이를 완화한다

제약 기반 vs 점수 기반 비교

Aspect	Constraint-Based	Score-Based
Core operation	CI tests	Score optimization
Assumption	Faithfulness	Score decomposability
Local vs Global	Local decisions	Global fit
Noise sensitivity	High (CI test errors)	Moderate
Computation	Many CI tests	Score evaluations

개선 방향

혼합 방법(hybrid methods)

Hybrid Methods Overview:

제약 기반으로 골격(skeleton)을 잡은 뒤 점수 기반으로 방향을 정한다
예: GFCI, MMHC

연속 최적화(continuous optimization)

NOTEARS:

DAG 공간을 연속 공간으로 변환한다
비순환성 벌점(acyclicity penalty)을 활용한다

병렬화(parallelization)

FGES:

엣지(edge) 추가·제거를 병렬화한다
대규모 데이터를 처리한다

참고 논문

Chickering, D.M. (2002). Optimal Structure Identification with Greedy Search
Heckerman et al. (1995). Learning Bayesian Networks
zangaSurveyCausalDiscovery2023 - Section 3.2

개요