기술 요약: 동시 DAG 학습

문제 정의

본 논문은 생물학부터 금융에 이르기까지 다양한 분야에서 인과 추론의 핵심 과제인 관측 데이터로부터 방향성 비순환 그래프 (DAG) 를 학습하는 근본적인 과제를 다룹니다. 이 문제는 구조 방정식 모델 (SEM) 에 의해 생성된 데이터셋 $X$로부터 잠재 DAG $G$의 인접 행렬 $W$를 복원하는 것으로 공식화됩니다.

식별된 핵심 어려움은 다음과 같습니다:

1. 조합적 복잡성: DAG 의 공간은 변수의 수에 따라 초지수적으로 증가하여 정확한 조합 탐색을 비실용적으로 만듭니다.
2. 비순환성 제약: 비순환성 제약 ($G \in \mathcal{D}$) 을 부과하는 것은 비볼록하며 계산적으로 어렵습니다.
3. 식별 가능성과 노이즈: 동일한 관측 분포를 생성하는 DAG 들을 구별하는 것은 자명하지 않습니다. 또한, 표준 최소제곱법 (OLS) 접근법은 동분산성 (변수 간 동일한 노이즈 분산) 을 암묵적으로 가정합니다. 이분산성 환경 (노이즈 분산이 다른 경우) 에서 OLS 는 편향을 도입하며, 희소성 정규화 매개변수 $\lambda$는 알려지지 않은 노이즈 수준과 결합되어 번거로운 수동 튜닝이 필요합니다.
4. 최적화 지형: 기존 연속 완화 방법은 종종 유효한 DAG 에서 기울기가 소실되는 퇴화 카루시 - 쿤 - 터커 (KKT) 조건으로 고통받아 수렴을 복잡하게 만듭니다.

방법론

본 논문은 인과 구조 학습에 동시 스케일 추정을 통합하는 CoLiDE(Concomitant Linear DAG Estimation) 프레임워크를 제안합니다. 이 방법론은 다음과 같은 세 가지 기둥에 기반합니다:

1. 동시 스케일 추정

강건 통계학의 동시 추정기 (예: Huber 의 작업 및 평활화 동시 라소) 에서 영감을 받아 CoLiDE 는 DAG 인접 행렬 $W$와 외생 노이즈 수준을 동시에 추정합니다.

• 동분산 환경 (CoLiDE-EV): 이 방법은 가중 최소제곱 항, 희소성 페널티 ($\ell_1$-norm), 그리고 노이즈 스케일 $\sigma$에 대한 항을 포함하는 볼록 스코어 함수 $S(W, \sigma; X)$를 최소화합니다. 스코어는 다음과 같습니다:
  $$\min_{W, \sigma \ge \sigma_0} \frac{1}{2n\sigma}\|X - W^\top X\|_F^2 + \frac{d\sigma}{2} + \lambda\|W\|_1$$
  비순환성 제약을 따릅니다. 이 공식화는 정규화 매개변수 $\lambda$를 알려지지 않은 노이즈 수준 $\sigma$로부터 분리하여 서로 다른 노이즈 영역에서 재튜닝할 필요가 없게 합니다.
• 이분산 환경 (CoLiDE-NV): 이 프레임워크는 각 변수가 고유한 노이즈 분산을 갖는 시나리오로 확장됩니다. 노이즈 표준편차의 대각 행렬 $\Sigma$를 추정하며, 가중 트레이스 손실을 최소화합니다:
  $$\min_{W, \Sigma \ge \Sigma_0} \frac{1}{2n} \text{tr}((X - W^\top X)^\top \Sigma^{-1} (X - W^\top X)) + \frac{1}{2}\text{tr}(\Sigma) + \lambda\|W\|_1$$

2. 연속 최적화 및 비순환성 특성화

본 논문은 조합적 비순환성 제약을 완화하기 위해 매끄러운 비볼록 함수를 활용합니다.

• DAGMA 페널티: CoLiDE 는 로그-행렬식 정규화기 $H_{ldet}(W; s) = d \log(s) - \log(\det(sI - W \circ W))$를 채택합니다. 이 함수는 특정 도메인에서 비순환성의 정확한 특성화이며, 행렬 지수 기반 접근법 (NOTEARS 등) 에 비해 개선된 기울기 행동과 더 긴 주기 탐지 능력을 제공합니다.
• 최적화 알고리즘: 제약 문제는 장벽 방법 접근법을 사용하여 일련의 비제약 문제로 해결됩니다. 알고리즘은 불완전 블록 좌표 하강 (BCD) 전략을 사용합니다:
  1. 증강 목적 함수에서 1 차 방법 (예: ADAM 의 단일 단계) 을 사용하여 $W$를 업데이트합니다.
  2. 현재 잔차에 기반하여 폐쇄형으로 노이즈 추정치 ($\sigma$ 또는 $\Sigma$) 를 업데이트합니다.
  3. 이 과정은 수렴하거나 최대 반복 횟수에 도달할 때까지 반복됩니다.

3. 음이 아닌 엣지 가중치 (NOMAD)

본 논문은 흥분성 신경망이나 흐름 모델과 같은 특정 도메인에서 유효한 엣지 가중치에 대한 음이 아닌 제약 ($W \ge 0$) 을 부과하는 것이 미치는 영향도 탐구합니다.

• 간소화된 비순환성: 음이 아닌 조건 하에서 비순환성 조건은 $H_+(W; s) = d \log(s) - \log(\det(sI - W)) = 0$으로 단순화됩니다. 이는 하마르드 곱 ($W \circ W$) 을 피하여 더 온화한 최적화 지형을 만들어냅니다.
• NOMAD 알고리즘: 저자들은 NOMAD(Non-negative Optimization via Multipliers for Acyclic Digraphs) 를 도입하여 제약 문제를 해결하기 위해 승수법 (증강 라그랑지안) 을 사용합니다. 이 접근법은 일반적인 DAG 학습에서 발견되는 KKT 퇴화를 피하는데, 그 이유는 DAG 들이 더 이상 페널티 함수의 정상점이 아니기 때문입니다.

주요 기여

1. 노이즈 적응형 스코어 함수: DAG 와 노이즈 수준을 동시에 추정하는 볼록 스코어 함수의 도입. 이는 희소성 페널티와 알려지지 않은 노이즈 수준 간의 결합을 제거하여 수동 하이퍼파라미터 튜닝 없이 이분산성과 분포 변화에 강건한 방법을 만듭니다.
2. 이론적 보장: 선형 가우시안 SEM 의 경우, 논문은 CoLiDE 가 비식별 이분산 환경에서도 표본 크기 $n \to \infty$에 따라 실제 DAG 와 '준동치 (quasi-equivalent)'인 DAG 를 산출함을 입증합니다.
3. 최적화 지형 분석: 논문은 음이 아닌 제약 조건을 부과함으로써 퇴화 KKT 조건을 제거하고, 특정 가정 하에서 실제 DAG 를 인구 증강 라그랑지안의 유일한 전역 최소점으로 만드는 지형을 생성함을 보여줍니다.
4. 확장성 및 온라인 학습: 이 프레임워크는 미니배치 확률적 경사 하강법과 온라인 업데이트를 지원하여 시간에 따라 변하는 구조의 추적과 대규모 데이터셋에 대한 확장성을 가능하게 합니다.

결과

본 논문은 CoLiDE 와 NOMAD 를 합성 및 실제 데이터에서 최신 베이스라인 (GOLEM, DAGMA, NOTEARS, GES 포함) 과 비교 평가합니다:

• 합성 데이터: 200 개의 노드를 가진 Erdős–Rényi (ER4) 및 Scale-Free (SF4) 그래프에서 CoLiDE 변형들은 구조 해밍 거리 (SHD), 거짓 발견율 (FDR), 그리고 참 양성율 (TPR) 에서 경쟁자들을 일관되게 능가합니다. 특히, CoLiDE 는 노이즈 분산이 1.0 에서 5.0 으로 증가할 때 재튜닝 없이도 높은 성능을 유지하는 반면, OLS 기반 방법들은 크게 저하됩니다.
• 이분산성: 가우시안, 지수, 라플라스 등 다양한 노이즈 분포를 가진 이분산 시나리오에서 CoLiDE-NV 는 명백한 승자이며 모든 대안을 능가합니다. CoLiDE-EV 또한 종종 2 위를 기록하며 강건하게 수행되어, 문제가 기술적으로 동분산일지라도 노이즈 적응형 공식화의 가치를 입증합니다.
• 실제 데이터 (Sachs 데이터셋): Sachs 세포 신호 전달 데이터셋 ($d=11, n=853$) 에서 CoLiDE-NV 는 SHD 12 를 달성하여 다른 연속 최적화 방법들을 능가했습니다. 전체적으로 가장 좋은 성능 (SHD=10) 은 생물학적 시스템에 내재된 음이 아닌 제약을 활용하는 NOMAD 가 달성했습니다.

중요성과 주장

본 논문은 CoLiDE 를 신호 처리, 최적화, 인과 추론을 연결하는 중요한 진전으로 위치시킵니다. 그 주요 중요성은 다음과 같습니다:

• 강건성: 스코어 함수를 노이즈 적응형으로 만들어 표준 희소 회귀와 DAG 학습을 괴롭히는 "알려지지 않은 노이즈 수준" 문제를 효과적으로 처리하며, 광범위한 하이퍼파라미터 튜닝 필요성을 줄입니다.
• 이분산성 처리: 전통적인 OLS 기반 방법이 편향된 것으로 알려진 이분산 환경에서 DAG 학습을 위한 원칙적인 해결책을 제공합니다.
• 최적화 효율성: 동시 추정과 특정 비순환성 페널티 (DAGMA 및 음이 아닌 로그-행렬식 등) 의 사용은 이전 연속 완화 방법보다 더 나은 최적화 지형과 더 빠른 수렴을 이끕니다.
• 실용적 적용성: 이 프레임워크는 미니배치 및 온라인 학습을 지원하도록 설계되어 확장 가능하며, 현대의 고차원 및 스트리밍 데이터 응용에 적합합니다.

저자들은 일반적인 비볼록 DAG 학습에 대한 전역 최적성 보장은 여전히 달성하기 어렵지만, 동시 추정과 구조적 제약 (예: 음이 아닌 조건) 의 결합은 신뢰할 수 있고 확장 가능하며 강건한 인과 발견을 위한 유망한 길을 제시한다고 결론지었습니다.