Score-Based Methods Overview

개요

Score-based methods는 그래프에 score function을 부여하고, 데이터에 가장 적합한 그래프를 탐색. Constraint-based와 달리 CI tests 없이 model fit 최적화.

Mermaid source (click to expand)

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

핵심 아이디어

Optimization problem: $\mathcal{G}^* = \arg\max_{\mathcal{G} \in \text{DAGs}} S(\mathcal{G}; D)$

• $S$: Score function (BIC, BGe, etc.)
• $D$: Data
• Search over MECs for efficiency

주요 알고리즘 비교

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$: Number of parameters
• $n$: Sample size
• Penalizes complexity

BGe (Bayesian Gaussian equivalent)

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

Marginal likelihood with Gaussian assumption:

• Conjugate priors 사용
• Closed-form computation

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

Score Equivalence

Definition: Score가 MEC 내에서 일정

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

Implication:

• MEC 내 DAGs를 구분하지 않음
• CPDAG를 직접 탐색 가능

장단점

장점

1. No Faithfulness Required

   • Constraint-based보다 약한 가정
   • Unfaithful distribution에서도 동작 가능

2. Principled Model Selection

   • Bayesian framework
   • Automatic complexity control (BIC penalty)

3. Global Optimization

   • Local CI decisions 아닌 global fit

단점

1. NP-hard Problem

   • DAG space super-exponential
   • Greedy search → local optima

2. Score Function Choice

   • 결과가 score에 의존
   • Misspecification 문제

3. Computational Cost

   • High-dimensional에서 느림
   • → FGES로 완화

Constraint vs Score Comparison

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:

• Constraint로 skeleton 후 Score로 orientation
• 예: GFCI, MMHC

Continuous Optimization

NOTEARS:

• DAG space를 continuous space로 변환
• Acyclicity penalty 활용

Parallelization

FGES:

• Edge 추가/제거 병렬화
• 대규모 데이터 처리

관련 개념

Algorithm Details

• GES - Greedy Equivalence Search
• FGES - Fast GES
• Scoring Criteria - BIC, BGe, BDeu 상세

Theoretical Foundations

• Markov Equivalence Class - Search space
• CPDAG - Output representation

Comparison

• Constraint-Based Methods Overview - 대안적 접근
• Hybrid Methods Overview - Constraint + Score 결합
• Asymmetry-Based Methods Overview - 다른 접근

참고 논문

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