Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

기술적 요약: 엣지별 불가능성 증명서를 활용한 반복적 인과 발견

문제 제기
현재의 인과 발견 알고리즘들은 일반적으로 완전히 방향이 지정된 방향성 비순환 그래프 (DAG) 를 반환하지만, 데이터에 의해 식별된 엣지 방향과 출력 제약을 만족시키기 위해 알고리즘이 부과한 방향을 구분하지 못합니다. 표준 마르코프 조건과 충실도 조건 하에서, 관측 데이터는 마르코프 동치 클래스만을 식별할 뿐; v-구조에 속하지 않는 엣지 방향은 결합 분포에 의해 결정되지 않습니다. 기존 방법들은 식별 불가능한 엣지에 대해 방향을 강제로 부여하거나 (예: NOTEARS, DAGMA), 진단적 근거 없이 방향을 지정하거나, 또는 (예: FCI) 해결하기 위해 필요한 구체적인 사전 정보를 명시하지 않은 채 방향을 지정하지 않은 채 둡니다. 또한, 연속 최적화 방법들은 진정한 식별을 모방하는 데이터 인공물 (예: varsortability) 을 악용하는 것으로 밝혀졌습니다. 데이터 기반 식별 가능성과 알고리즘적 부과를 명확히 분리하고, 식별 불가능한 엣지를 해결하는 데 필요한 구체적인 전문가 질문을 식별하는 원칙적인 프로토콜이 부재합니다.

방법론
본 논문은 연속 데이터에 대한 관측적 인과 발견을 위한 결정론적 3 단계 프로토콜을 제안합니다. 이 프로토콜은 데이터만의 스키레톤 (skeleton) 내의 모든 후보 엣지에 대해 이산형 "불가능성 증명서"를 발급하며, 해당 엣지를 해결됨(데이터 식별 또는 매개됨) 또는 불가능(데이터 불충분, 전문가 입력 필요) 으로 분류합니다.

1. 1 단계: 스키레톤 및 매개변수 탐색

   • FDR 제어 HSIC 검사를 사용하여 marginally 독립인 쌍을 제거함으로써 스키레톤을 구성합니다.
   • 다단계 매개변수 탐색을 수행하여 관측된 변수에 의해 매개되는 엣지를 식별하고 제거합니다.

2. 2 단계: 게이트형 식별 가능성 캐스케이드

   • 8 단계 캐스케이드가 남은 엣지들을 평가합니다. 이 단계에는 고전적 방법 (선형 ANM $L_0$, 비선형 ANM $L_1$, HOC LiNGAM $L_2$) 과 본 논문에서 새로 도입된 5 가지 단계가 포함됩니다: LSNM(위치 - 스케일 노이즈), IGCI(정보 - 기하학적), Stein(스코어 매칭), MDL(알고리즘적 마르코프 조건), PEIT(엔트로피 - 역전 테스트).
   • 게이팅 메커니즘: 각 단계는 통계적 검정 (예: 비정규성을 위한 Shapiro–Wilk 검정, 이분산성 검정) 으로 사전 조건이 설정됩니다. 특정 단계의 사전 조건이 실패하면 방향을 강제로 부여하는 대신 기권합니다.
   • 단계 간 합의: "불일치 가드"는 IGCI, Stein, MDL 과 같은 고정밀 단계가 방향과 모순될 경우 $L_0$의 결정을 강등시키고, 해당 엣지를 impossible_l0_disagrees_with_high_tier로 재레이블합니다.
   • 어떤 단계에서도 해결되지 않은 엣지는 impossible_* 라벨을 부여받으며, 이는 실패 모드 (예: 잠재적 교란, 약한 비선형성) 와 이를 해결하기 위한 전문가의 구체적인 질문을 인코딩합니다.

3. 3 단계: 표적 오라클 쿼리

   • 본 프로토콜은 impossible_*로 라벨링된 엣지에 대해서만 도메인 전문가와 상호작용합니다.
   • 쿼리 원시 연산자:
     • 엣지별 쿼리: 방향 (FWD/BWD) 또는 부재를 요청합니다.
     • 메타 허브 쿼리: 아웃-차수가 가장 큰 상위 $K$개 노드를 요청합니다.
     • 노드 - 자식 쿼리: 특정 노드의 직접적인 자식들을 요청하여 모든 나가는 엣지를 동시에 확정합니다.
   • 자동 전파: 오라클 확정 후, 시스템은 추가 쿼리 없이 추가 엣지들을 해결하기 위해 비용 제로 자동 해결 통과 (비순환성 확인, Meek 규칙, 전이적 d-분리) 를 실행합니다.

주요 기여

1. 엣지별 증명서: 본 프로토콜은 모든 엣지에 이산형 코드를 할당합니다. resolved_* 코드는 방향을 정당화하는 특정 정리 (예: $L_{Stein}$) 를 인용하는 반면, impossible_* 코드는 실패 모드와 이를 해결하기 위해 필요한 구체적인 질문을 기록합니다.
2. 단계 인지형 기권: LSNM, IGCI, Stein, MDL, PEIT 등 5 가지 새로운 게이트형 단계 도입으로 인해, 특정 식별 가능성 정리가 충족될 때만 방향이 확정됩니다. 사전 조건이 실패하면 시스템은 잠재적으로 위조된 방향을 강제로 부여하는 대신 기권합니다.
3. 1+K 상호작용 상한: 본 논문은 $K$를 비리프 (non-leaf) 정점의 수라고 할 때, 전문가 상호작용 $1+K$회로 어떤 참 DAG 도 복원할 수 있다는 정보 이론적 상한을 확립합니다. 이는 단일 메타 허브 쿼리 (타겟 식별용) 와 $K$개의 노드 - 자식 쿼리를 결합함으로써 달성됩니다.
4. 표적 유도: 전체 위상 순서나 광범위한 개입을 요청할 수 있는 능동 학습 방법과 달리, 본 프로토콜은 식별 불가능한 엣지만을 격리하고 이를 해결하는 데 필요한 구체적인 정보만 요청합니다.

실험 결과
본 프로토콜은 4 가지 표준 벤치마크 (Asia, Sachs, Child, Alarm) 와 특정 단계를 스트레스 테스트하도록 설계된 합성 데이터에서 평가되었습니다.

• 이상적 오라클 성능: 완벽한 오라클을 가정할 때, 본 프로토콜은 정확히 $1+K$회의 상호작용을 사용하여 4 가지 벤치마크 모두에서 정밀도 = 재현율 = F1 = 1.000으로 참 DAG 를 복원했습니다.
  • Alarm (V=37): 27 회 상호작용으로 46 개의 엣지 복원.
  • Sachs (V=11): 8 회 상호작용으로 17 개의 엣지 복원.
• 캐스케이드 효율성: Sachs 데이터셋에서 캐스케이드만으로도 데이터만으로 19 개의 참 엣지 중 5 개를 해결했습니다. 새로운 안전 단계 추가와 불일치 가드 활성화 시 방향 정밀도는 기존 (L0-L2 기반) 61.5% 에서 66.7% 로 향상되었습니다.
• 단계별 특이성: 합성 스트레스 테스트는 각 새로운 단계가 고유 영역 (예: 위치 - 스케일 노이즈에서의 LLSNM, 준결정론적 데이터에서의 LIGCI) 에서 정밀도 양 (+) 을 보이며, 영역 밖 데이터에서는 기권 (40 회 중 0 회 발동) 하여 위양성을 방지함을 확인했습니다.
• 파레토 프론티어: Sachs 데이터셋에서 본 프로토콜은 쿼리 수와 F1 점수 간의 트레이드오프를 보여주었습니다. "SAFE-only" 접근법 (오라클 없는 캐스케이드) 은 5 회 쿼리로 F1=0.571 을 달성한 반면, 전체 프로토콜은 캐스케이드를 사용하여 오라클 부담을 줄임으로써 13 회 쿼리로 F1=1.000 을 달성했습니다.

의의 및 주장
본 논문은 인과 발견의 근본적인 격차, 즉 현재 방법들이 데이터 식별 방향과 알고리즘적 부과 방향을 구분하지 못하는 문제를 해결한다고 주장합니다. 모든 엣지에 "증명서"를 첨부함으로써 프로토콜은 투명한 감사 추적을 제공합니다.

• 이론적 기여: $1+K$ 상한은 능동적 인과 발견의 개입 예산 상한에 대응하는 유도 측면의 상한으로, 전문가 지식이 이용 가능할 때 DAG 를 해결하는 데 필요한 최소 정보를 정량화합니다.
• 실용적 유용성: 본 프로토콜은 실무자가 식별 불가능한 엣지에만 전문가 노력을 집중할 수 있게 하며, raw 엣지 방향 대신 구체적이고 영역 인지형 질문을 제시함으로써 인지 부하를 줄입니다.
• 한계: 저자들은 현재 범위가 연속 변수로 제한되며, 이산 베이지안 네트워크는 오라클 레이어의 견고성 검정으로만 다루어진다고 명시합니다. 프로토콜은 완벽한 오라클을 가정하며, 노이즈가 있거나 확률적인 전문가 응답 처리는 향후 과제로 식별되었습니다. 또한, 스키레톤 구성 단계는 초기 HSIC 검정에 의해 제거된 엣지는 복원할 수 없으므로 재현율에 제한을 imposed 합니다.

본 연구는 확장 가능한 연속 최적화나 제약 기반 방법을 대체하는 것이 아니라, 엣지별 감사 가능성에 우선순위를 두고 표적화된 증명서 기반 쿼리를 통해 전문가 유도 비용을 최소화하는 직교적 접근법으로 자신을 위치시킵니다.