비선형 인과성 발견의 확장성-정확도 경계 매핑 및 발전

확장 가능한 비선형 인과성 발견(nonlinear causal discovery)은 유연한 메커니즘 추정기(flexible mechanism estimators)와 대규모 그래프 공간에 대한 효율적인 탐색을 결합하는 방법을 필요로 합니다. 이 문제를 해결하기 위해 여러 알고리즘 계열이 제안되었지만, 이들의 정확도-실행 시간 트레이드오프는 여전히 제대로 이해되지 않고 있습니다. 우리는 네 가지 주요 접근 방식, 즉 미분 가능 구조 학습(differentiable structure learning), 상각 구조 학습(amortized structure learning), 스코어 매칭(score-matching), 그리고 조합적 탐색(combinatorial search)을 경험적으로 비교합니다. 우리의 결과는 보완적인 병목 현상을 밝혀냅니다: 미분 가능 및 상각 방식은 확장성이 좋지만 정확도 격차를 보이며, 스코어 매칭 방식은 낮은 차원에서는 정확할 수 있지만 특징 크기 증가에 따라 빠르게 저하되고, 조합적 방식은 여전히 정확하지만 반복적이고 중복적인 지역 점수 계산(local scoring)으로 인해 속도가 느려집니다. 이러한 병목 현상에 동기를 얻어, 우리는 SPADE라는 스플라인 기반의 스코어 평가 체계(spline-based score-evaluation scheme)를 개발했습니다. 이는 충분 통계량(sufficient statistics)을 한 번 컴파일하고 조합적 탐색 전반에 걸쳐 재사용합니다. 유한한 인디그리(indegree) 하에서, 그 가우시안 변형은 알고리즘 복잡도를 O(nd^3)에서 O(nd^2+d^3)로 줄입니다. 경험적으로, SPADE는 관찰된 확장성-정확도 경계를 수 배 크기만큼 이동시킵니다: 이는 100개 변수 문제와 160K 샘플을 몇 초 만에, 그리고 1600개 변수 문제와 2.5K 샘플을 몇 분 만에 해결하면서도 합성 및 실제 세계 벤치마크 전반에 걸쳐 높은 구조적 정확도를 유지합니다. 이러한 결과는 조합적 탐색의 실질적인 규모가 크게 이동했음을 보여주며, 확장 가능한 인과성 발견 방법들을 전체 정확도-실행 시간 경계를 따라 평가하는 것의 중요성을 강조합니다.