DAG 구조 학습에서 비음성(Non-Negativity)의 활용

본 연구는 선형 구조 방정식 모델(linear structural equation model)에 의해 생성된 노드 관측값으로부터 유향 비순환 그래프(Directed Acyclic Graphs, DAGs)를 학습하는 문제를 다룹니다. DAG 학습은 신호 처리(signal processing), 머신러닝(machine learning), 인과 추론(causal inference) 분야의 핵심 과제이지만, 비순환성(acyclicity)이 전역적인 조합론적 특성(global combinatorial property)이기 때문에 여전히 어려운 과제로 남아 있습니다. 연속적인 비순환성 제약 조건(Continuous acyclicity constraints)은 이산적인 DAG 제약을 매끄러운 등식 제약(smooth equality constraints)으로 대체함으로써 중요한 알고리즘적 발전을 이끌어냈습니다. 그러나 기존의 공식화(formulations)는 여전히 어려운 비볼록 최적화 지형(non-convex optimization landscapes)을 포함하며, 퇴화된 1차 최적 조건(degenerate first-order optimality conditions)으로 인해 어려움을 겪을 수 있습니다. 본 연구에서는 에지 가중치(edge weights)가 비음수(non-negative)인 DAG로 주의를 제한하고, 이러한 추가적인 구조를 활용하여 비순환성에 대한 더 단순한 특성화를 얻습니다. 이 특성화를 바탕으로, 우리는 정규화된 비음수 DAG 학습 문제를 공식화하고 승수법(method of multipliers)에 기반한 알고리즘을 개발합니다. 나아가 우리는 비음성으로 인해 유도되는 양호한 최적화 지형(benign optimization landscape)을 분석합니다. 모집단 영역(population regime)에서, 우리는 실제 DAG가 제안된 증강 라그랑주(augmented-Lagrangian) 공식화의 유일한 전역 최소화 지점(global minimizer)임을 보여줍니다. 더욱이, 이 지형에는 가짜 내부 정지점(spurious interior stationary points)이 존재하지 않으며, 실제 DAG가 유일한 비순환 KKT 점(acyclic KKT point)입니다. 합성 데이터 및 실제 데이터에 대한 수치 실험 결과, 제안된 방법이 최신(state-of-the-art) 연속 DAG 학습 대안들보다 성능이 향상됨을 보여줍니다.