Clustering and Pruning in Causal Data Fusion

본 논문은 다중 소스 데이터 융합에서 인과 그래프의 복잡성을 줄이기 위한 전처리 기법으로서 가지치기(pruning)와 클러스터링(clustering)을 제안하며, 이러한 연산들이 인과 식별 가능성을 보존하고 복잡한 모델을 위한 식별 기능(identifying functionals) 구축을 가능하게 하는 조건들을 도출한다.

핵심

당신이 미스터리를 해결하려는 탐정이라고 상상해 보십시오: "임신 중 흡연이 조산의 원인이 되는가?"

현실 세계에서는 모든 단서가 담긴 완벽한 파일 하나를 갖는 경우가 드뭅니다. 대신, 서로 다른 출처에서 온 파편화된 증거 더미를 갖게 됩니다:

• 출처 A에는 흡연 습관과 교육 수준에 대한 데이터가 있습니다.
• 출처 B에는 흡연과 출산 결과에 대한 데이터가 있지만, 교육 데이터는 없습니다.
• 출처 C에는 교육과 소득에 대한 데이터가 있지만, 흡연 데이터는 없습니다.

이 미스터리를 풀기 위해서는 이 파일들을 결합해야 합니다. 이것을 **인과 데이터 퓨전(Causal Data Fusion)**이라고 부릅니다. 하지만 이 파일들을 결합하려고 시도하는 것은 마치 퍼즐 조각이 엄청나게 크고, 조각들은 여기저기 흩어져 있으며, 심지어 일부 조각은 통째로 사라진 거대한 직소 퍼즐을 맞추는 것과 같습니다. 변수(조각)가 많아질수록 컴퓨터가 정답을 찾아내는 것은 더 어려워집니다.

이 논문은 정답을 놓치지 않으면서도 이 퍼즐을 더 쉽게 풀 수 있는 두 가지 영리한 기술을 소개합니다: **가지치기(Pruning)**와 **클러스터링(Clustering, 군집화)**입니다.

1. 가지치기(Pruning): "불필요한 것을 쳐내는" 기술

비유: 당신이 거대하고 지저�한 방에서 특정 열쇠를 찾고 있다고 상상해 보십시오. 만약 그 열쇠가 반드시 주방 카운터 위에 있다는 것을 알고 있다면, 구석에 있는 러그 밑이나 다락방, 혹은 잠겨 있는 금고 안을 들여다볼 필요가 없습니다. 당신은 중요한 것에 집중하기 위해 나머지 방의 구역들을 안전하게 무시(가지치기)할 수 있습니다.

논문의 내용:
때때로 데이터 속의 특정 변수들은 당신이 묻고자 하는 구체적인 질문과 전혀 상관이 없을 수 있습니다.

• 비조상(Non-Ancestors): 만약 어떤 변수(예: "눈 색깔")가 당신이 관심을 갖는 결과(예: "조산")로 이어지는 경로를 가지고 있지 않다면, 그것을 버려도 됩니다.
• 단절된 변수(Disconnected Variables): 만약 어떤 변수가 단 하나의 실 하나로 나머지 퍼즐과 연결되어 있거나, 혹은 개입(예: 누군가에게 강제로 담배를 피우게 하는 것)을 했을 때 쓸모가 없어지는 변수라면, 이를 제거할 수 있습니다.

이점: 본격적인 수학 계산을 시작하기 전에 이러한 쓸모없는 변수들을 잘라냄으로써 퍼즐의 크기를 줄일 수 있습니다. 논문은 만약 올바른 조각을 잘라낸다면, 당신의 미스터리에 대한 답은 정확히 동일하게 유지된다는 것을 증명합니다. 당신은 진실을 잃은 것이 아니라, 단지 노이즈를 제거했을 뿐입니다.

2. 클러스터링(Clustering): "그룹화하는" 기술

비유: 당신이 도서관을 정리하고 있다고 상상해 보십시오. 모든 책을 정확한 제목, 저자, 발행 연도로 일일이 나열하는 대신, "소설", "역사", "과학" 등으로 그룹을 묶습니다. 당신은 "역사" 섹션 전체가 역사 섹션에 속한다는 것을 알기 위해 그 안의 모든 책의 세부 사항을 알 필요가 없습니다.

논문의 내용:
때때로 매우 유사하게 작동하는 변수 그룹이 존재합니다. 예를 들어, "소득", "교육", "직업 상태"는 모두 "사회경제적 지위"라는 하나의 블록의 일부일 수 있습니다.

• 경로 클러스터(Transit Clusters): 이 논문은 "경로 클서터"라고 불리는 특정 유형의 그룹에 집중합니다. 이것을 정보가 한쪽 끝으로 들어와 다른 쪽 끝으로 나가는 "복도"라고 생각하십시오. 만약 그 "복도"가 하나의 단위로서 작동한다는 것을 증명할 수 있다면, 복도 전체를 하나의 문(하나의 변수)으로 대체할 수 있습니다.
• 주의 사항: 이 작업은 데이터가 복도의 "입구"와 "출구"를 적절히 커버하고 있을 때만 가능합니다. 만약 데이터에 출구가 빠져 있다면, 아직 그룹화할 수 없습니다.

이점: 50개의 조각으로 된 퍼즐을 푸는 대신, 각 조각이 하나의 전체 그룹을 나타내는 10개의 조각으로 된 퍼즐을 풀게 됩니다. 이는 컴퓨터 계산 속도를 훨씬 빠르게 만듭니다.

3. "Do-search" 엔진

논문은 Do-search라고 불리는 도구를 언급합니다. 이것을 데이터 파일들을 조합하여 정답을 찾아내는 초스마트 로봇이라고 생각하십시오.

• 문제점: 퍼즐이 너무 크면, 로봇은 정답을 찾는 데 몇 시간 또는 며칠이 걸리거나 아예 포기해 버립니다.
• 해결책: 저자들은 만약 가지치기(불필요한 것 제거)와 클러스터링(조각 묶기)을 먼저 수행한다면, 로봇이 몇 초 만에 정답을 찾을 수 있다는 것을 보여줍니다.

4. 이것이 왜 중요한가 (논문에 따르면)

저자들은 수천 개의 무작위 퍼즐을 통해 이 방법을 테스트했습니다. 그 결과는 다음과 같습니다:

• 속도: 중간에서 큰 규모의 퍼즐의 경우, 가지치기와 클러스터링을 사용하면 컴퓨터가 수백 배 더 빨라졌습니다.
• 안전성: 그들은 만약 단순화된 작은 퍼즐에서 답이 "예"(식별 가능)라면, 크고 지저분한 원래의 퍼즐에서도 "예"라는 것을 수학적으로 증명했습니다. 또한 단순화된 퍼즐에서 답이 "아니오"라면(특정 규칙을 확인했을 때), 큰 퍼즐에서도 "아니오"였습니다.
• 손실 없음: 설령 이 기술들이 속도를 높이지 못하더라도, 속도를 크게 늦추지도 않습니다. 기술을 사용할 수 있는지 확인하는 데 드는 시간은 절약되는 시간에 비하면 아주 미미합니다.

논문에 등장하는 실제 사례

저자들은 단순히 가상의 숫자를 사용한 것이 아니라, 실제 사례를 사용했습니다:

1. 영아 사망률: 그들은 담배 가격와 영아 사망 사이의 연구를 살펴보았습니다. 중요하지 않은 변수(예: 특정 질문에 대한 "GDP")를 제거하고 "교육"과 "산모 연령"을 그룹화함으로써, 모델을 단순화하고 더 빠르게 답을 찾아냈습니다.
2. 심장 질환: 그들은 평생의 사회경제적 지위가 심장 건강에 어떤 영향을 미치는지에 대한 연구를 살펴보았습니다. 그들은 "사회경제적" 그룹 내부의 모든 변수에 대한 정확한 세부 사항을 알지 못하더라도, 전체 그룹을 하나의 단위로 취급하여 여전히 올바른 답을 얻을 수 있음을 보여주었습니다.

핵심 요약

이 논문은 복잡한 데이터 문제를 단순화하는 규칙을 제시합니다. 논문의 메시지는 이렇습니다: "거대한 전체 퍼즐을 풀려고 하기 전에, 버릴 수 있는 조각과 묶을 수 있는 그룹을 먼저 찾으십시오. 이 규칙을 따른다면, 당신은 똑같은 답을 얻으면서도 훨씬 더 빠르게 도달할 수 있을 것입니다."

이는 데이터의 어떤 부분이 필수적이고 어떤 부분이 그저 배경 소음인지 정확히 파악함으로써, 더 열심히 하는 것이 아니라 더 똑똑하게 일하는 것에 관한 것입니다.

기술 요약

기술 요약: 인과 데이터 퓨전에서의 클러스터링 및 프루닝(Pruning)

문제 정의

본 논문은 여러 소스로부터 관측 데이터와 실험 데이터를 결합하여, 단일 소스로는 식별할 수 없는 인과 효과 $p(y \mid do(x))$를 식별하는 것을 목표로 하는 일반적인 인과 효과 식별 문제를 다룹니다. do-calculus(Pearl, 1995)가 이 작업을 위한 범용 도구 역할을 하지만, 이를 기반으로 하는 알고리즘(예: Do-search)은 변수의 수가 증가하고 인과 그래프가 복잡해짐에 따라 상당한 계산적 어려움에 직면합니다.

특정 시나리오(예: g-식별성, g-전이성)를 위한 기존 식별 알고리즘은 관측된 변수와 개입된 변수의 합집합이 모든 내생 변수를 포함하는 전체 결합 분포의 가용성과 같은 제한적인 가정에 의존하는 경우가 많습니다. 반면, 실제 세계의 데이터 퓨전은 부분적으로 중첩되는 입력 분포(예: 한 소스는 $p(x, z)$를 측정하고 다른 소스는 $p(z, y)$를 측정함)를 포함하는 경우가 많으며, 현재의 어떤 알고리즘도 계산 비용이 많이 드는 탐색 기반 방법론에 의존하지 않고는 식별 가능성을 결정할 수 없습니다.

핵심 과제는 인과 그래프의 크기를 줄이는 것(전처리)이 인과 효과의 식별성을 자동으로 보존하지는 않는다는 점입니다. 만약 그래프가 수정된다면, 수정된 그래프에서 수행된 추론이 원래의 그래프로 전달된다는 보장이 없습니다. 본 논문은 프루닝(변수 제거)과 클러스터링(변수 결합)을 적용할 때 식별 가능성의 상태를 변경하지 않고 적용할 수 있는 엄격한 조건을 확립하고자 합니다.

방법론

저자들은 다중 데이터 소스 맥락에서 인과 그래프를 전처리하기 위한 프레임워크를 제안합니다. 이들은 단일 관측 데이터 소스로 제한되었던 이전 연구들(Tikka and Karvanen, 2018; Tikka et al., 2023)을 일반화합니다.

1. 프루닝 (Pruning)

프루닝은 특정 인과 효과의 식별에 무관한 변수를 제거하는 과정을 포함합니다. 본 논문은 여러 입력 분포 $I = \{p(a_i \mid do(b_i), c_i)\}$가 존재하는 상황에서의 프루닝을 위해 세 가지 정리를 도출합니다:

• 정리 7 (비조상 프루닝): 반응 변수 $Y$의 조상이 아닌 변수는, 모든 입력 분포의 조건부 집합(conditioning sets)이나 개입 집합(intervention sets)에 관여하지 않는 한 제거될 수 있습니다.
• 정리 8 (개입 후 프로닝): $X$에 대한 개입 후 $Y$와 d-분리(d-separated)되는 변수는, 제거가 $X$의 구성원 간의 d-분리 속성을 변경하거나 입력 분포의 구조를 위반하지 않는다는 조건 하에 제거될 수 있습니다.
• 정리 9 (고립된 정점 프루닝): 단일 변수를 통해서만 나머지 그래프와 연결된 정점은, 해당 변수가 입력 분포의 조건부 집합이나 개입 집합의 일부가 아니라면 제거될 수 있습니다.

2. 클러스터링 (Clustering)

클러스터링은 정점 집합 $T$를 단일 정점 $\mathcal{T}$로 대체합니다. 본 논문은 정보가 "수신기"(외부에 부모를 둔 노드)에서 "발신기"(외부에 자식을 둔 노드)로 특정하고 균일한 방식으로 흐르는 집합인 **경유 클러스터(transit clusters)**에 초점을 맞춥니다.

• 정의 13 (경유 클러스터): 집합 $T$가 경유 클러스터라는 것은 모든 수신기가 동일한 외부 부모를 공유하고, 모든 발신기가 동일한 외부 자식을 공유하며, 내부 연결성이 모든 노드를 수신기 또는 발신기에 연결함을 의미합니다.
• 식별 불변성: 본 논문은 클러스터링 연산이 식별성을 보존하는지 확인하기 위해 **알고리즘 1 (VerifyInputs)**을 도입합니다.
  • 정리 17: 클러스터링된 그래프에서 인과 효과가 식별 가능하다면, 원래의 그래프에서도 식별 가능합니다.
  • 정리 18: 클러스터링된 그래프에서 인과 효과가 식별 불가능하고, VerifyInputs가 TRUE를 반환한다면, 원래의 그래프에서도 식별 불가능합니다.
  • 정리 19: 수신기와 발신기가 교차하는(즉, 한 노드가 두 역할을 모두 수행하는) 경우 클러스터링이 항상 식별 불변성을 갖는 특수 사례입니다.

3. 식별 함수(Identifying Functionals)의 복구

본 논문은 프루닝되거나 클러스터링된 그래프에서 도출된 식별 함수를 원래의 그래프로 매핑하는 방법을 보여줍니다:

• 정리 20: 프루닝의 경우, 식별 함수는 변하지 않습니다 ($f(I) = g(I')$).
• 정리 21: 클러스터링의 경우, 함수는 대응하는 입력 분포에 나타나는 원래 클러스터 $T$의 특정 부분 집합으로 클러스터링된 변수 $\mathcal{T}$를 대체함으로써 얻어집니다.

주요 결과

1. 다중 소스로의 일반화: 저자들은 프루닝 및 클러스터링 불변성 결과를 단일 소스 환경에서 다중의 부분적으로 중첩되는 데이터 소스가 존재하는 일반적인 경우로 성공적으로 확장했습니다. 이는 전체 분포를 사용할 수 없을 때 c-컴포넌트(c-components)나 잠재 투영(latent projections)과 같은 개념들이 정의되지 않기 때문에 매우 까당한 작업입니다.
2. 알고리즘 검증: VerifyInputs(알고리즘 1)의 개발은 클러스터링된 그래프에서의 비식별성이 원래 그래프의 비식별성을 의미하는지를 결정하는 실용적인 방법을 제공하며, 이는 거짓 음성(false negatives)을 피하기 위한 중요한 단계입니다.
3. 계산 효율성: 108,933개의 인스턴스에 대한 Do-search를 사용한 시뮬레이션 연구 결과, 축소 전략(프루닝 + 클러스터링)이 직접 전략(원래 그래프에 Do-search 실행)보다 더 큰 그래프에서 성능이 크게 향상됨을 보여주었습니다.
   • 12개의 정점을 가진 그래프의 경우, 비식별 사례(Setting B)에서 중앙값 시간 절감 효과는 12분을 초과했습니다.
   • 프러닝/클러스터링 조건을 확인하는 오버헤드는 무시할 수 있는 수준입니다(중앙값 < 0.05초).
   • 축소가 적용되지 않는 경우에도 시간 손실은 최소화되었습니다.
4. 실제 적용: 본 방법론은 두 가지 실제 사례에 적용되었습니다:
   • 영아 사망 연구: 프로닝이 담배 가격이 간접 흡연에 미치는 효과를 식별하기 위해 복잡한 그래프를 관리 가능한 크기로 어떻게 줄이는지 보여주었습니다.
   • 동맥경화 연구 (ELSA-Brasil): 변수들을 클러스터링하는 방식(예: 사회경제적 요인)이 특정 조건이 충족되는 한, 클러스터의 상세한 내부 구조를 파악하지 않고도 식별 가능성을 평가할 수 있게 함을 보여주었습니다.

의의 및 주장

본 논문은 프로닝과 클러스터링이 특히 현재의 다항 시간 알고리즘을 적용할 수 없는 부분적으로 중첩된 데이터를 포함하는 시나리오에서 인과 데이터 퓨전을 위한 필수적인 전처리 도구 역할을 한다고 주장합니다.

• 효율성: 주요 의의는 계산 부하의 감소입니다. 식별 알고리즘을 적용하기 전에 그래프 크기를 줄임으로써, 이 방법은 더 크고 복잡한 모델에 대한 인과 효과 식별을 가능하게 합니다.
• 단순화: 이 방법들은 더 간결한 인과 그래프 표현과 더 단순한 식별 함수를 가능하게 합니다.
• 데이터 수집 계획: 저자들은 이러한 기술이 데이터 수집 전략을 안내할 수 있다고 언급합니다. 만약 변수를 프로닝할 수 있다면 측정할 필요가 없습니다. 만약 경유 클러스터를 사용한다면, 식별성을 보존하기 위해 클러스터의 "발신기"만을 측정하면 됩니다.
• 이론적 기여: 본 연구는 전체 분포 지식이 필요한 개념(c-컴포넌트, 헤지 등)에 의존하지 않고 식별 불변성에 대한 충분 조건을 제공합니다. 이는 이론적 인과 추론과 실제적인 데이터 퓨전 제약 사이의 간극을 메워줍니다.

저자들은 결과가 **한계 인과 효과(marginal causal effects)**에 적용된다는 점을 명시하며 범위에 대해 신중한 입장을 유지하며, 제약이 없는 일반적인 경우에 대한 do-calculus의 완결성은 여전히 열려 있는 이론적 문제임을 밝힙니다. 그들은 이러한 연산의 적용이 계산적 이득과 해석 가능성의 상실 또는 특정 도메인 지식의 필요성 사이에서 균형을 맞추는 연구자의 결정임을 강조합니다.