Integrating Background Knowledge for Scalable Causal Discovery

당신이 거대한 미스터리를 해결하려는 탐정이라고 상상해 보십시오. 당신의 임무는 날씨, 교통량, 커피 판매량과 같은 다양한 변수들이 서로 어떻게 영향을 미치는지 정확히 파악하는 것입니다. 당신에게는 거대한 단서의 그물망이 있지만, 그 그물은 너무나 얽혀 있어서 모든 연결 고리를 한꺼번에 지도화하려고 시도한다면 평생이 걸릴지도 모릅니다. 이것이 바로 인과 발견(causal discovery)의 문제입니다. 즉, 데이터로부터 진정한 인과관계 지도를 찾아내는 과정입니다.

보통 탐정들이 벽에 부딪히면 전문가에게 도움을 요청합니다. 예를 들어, 현지 바리스타가 당신에게 "커피 판매량이 비를 유발하지는 않아요"라거나 "비가 온 뒤에 교통 체증이 발생해요"라고 말해줄 수 있습니다. 컴퓨터 과학의 세계에서 이것을 배경 지식(Background Knowledge, BK)이라고 부릅니다.

오랫동안 대부분의 컴퓨터 프로그램은 이러한 전문가의 조언을 작업이 다 끝난 후에 벽에 붙이는 포스트잇처럼 취급했습니다. 즉, 먼저 거대하고 혼란스러운 지도를 만든 다음, "아, 전문가가 이 연결선은 틀렸다고 했나? 그럼 지우자"라고 말하는 식이었죠. 이 논문은 이것이 마치 집을 짓고 전체를 다 칠한 다음에야, 건축가가 말했던 벽을 허무는 것을 잊었다는 사실을 깨닫는 것과 같다고 주장합니다. 이는 시간과 에너지의 낭비입니다.

핵심 아이디어: 구축하는 동안 전문가에게 물어보기

이 논문의 저자들(네덜란드와 독일의 대학 팀)은 더 똑똑한 방법을 고안해 냈습니다. 그들은 컴퓨터가 조사를 마친 후가 아니라, 조사하는 도중에 전문가에게 도움을 요청할 수 있는 새로운 프레임워크를 구축했습니다.

이것은 마치 비밀 물건을 맞히는 "스무 고개" 게임을 하는 것과 같습니다.

• 기존 방식: 모든 것에 대해 20개의 질문을 던져 가능한 모든 답을 적어 놓은 뒤, "아, 전문가가 살아있는 생물이 아니라고 했지?"라며 적어둔 노트의 절반을 버리는 방식입니다.
• 새로운 방식 (이 논문): 시작할 때 전문가에게 "살아있나요?"라고 묻습니다. 전문가가 "아니요"라고 답하면, 당신은 즉시 털, 깃털, 혹은 꼬리에 대한 질문을 멈춥니다. 대신 돌, 자동차, 의자에 대해서만 질문하게 됩니다. 이렇게 하면 퍼즐을 훨씬 더 빠르고 적은 질문으로 풀 수 있습니다.

세 가지 마법의 기술

논문은 알고리즘이 실행되는 동안 이 전문가 지식을 통합함으로써 세 가지 구체적인 일이 일어난다는 것을 보여줍니다.

1. 당연한 것 건너뛰기: 만약 전문가가 "변수 A와 변수 B는 확실히 연결되어 있다"라고 말한다면, 컴퓨터는 두 변수가 연결되어 있지 않음을 증명하기 위해 시간을 낭비하는 것을 멈춥니다. 그냥 연결을 받아들이고 다음 단계로 넘어갑니다.
2. 탐색 범위 좁히기: 만약 컴퓨터가 A와 B가 왜 다른지를 파악하려고 노력 중이라면, 보통 다른 수백 개의 변수를 확인하여 그것이 "범인"인지 확인해야 합니다. 이때 전문가는 "그건 확실히 C나 D 때문이 아니에요"라고 말할 수 있습니다. 그러면 컴퓨터는 즉시 C와 D를 무시하며, 탐색 공간을 경기장에서 작은 방 하나 크기로 줄여버립니다.
3. "공백" 처리하기: 때때로 전문가는 "A와 B는 확실히 연결되어 있지 않다"라고 말합니다. 이 논문은 만약 그 연결을 즉시 삭제해 버리면, 나중에 다른 화살표의 방향을 결정하는 데 필요한 논리 구조를 실수로 깨뜨릴 수도 있다는 점을 발견했습니다. 그래서 그들의 새로운 방법은 영리합니다. 그것은 왜 연결되지 않았는지에 대한 "증거"(분리 집합, separating set)를 찾을 때까지 아주 잠시 기다리지만, 훨씬 더 작은 용의자 목록을 사용하여 이를 수행합니다. 이는 알고리즘이 멈추거나 혼란에 빠지는 것을 방지합니다.

결과: 더 빠르고 더 똑똑하게

저자들은 이 아이디어를 여러 가지 서로 다른 탐정 알고리즘(PC, SNAP, MB-by-MB, LDECC, LOAD라고 불림)에 테스트했습니다. 그들은 100개의 변수(노드)를 가진 시뮬레이션을 실행했으며, 선형 가우시안(매끄러운 곡선)과 이진(예/아니오) 데이터를 포함한 다양한 유형의 데이터를 사용했습니다.

시뮬레이션 결과는 다음과 같습니다:

• 속도: 새로운 방식들이 현저히 빨랐습니다. PC-BK와 LDECC+-BK 같은 일부 알고리즘의 경우, 배경 지식을 사용했을 때 문제를 푸는 데 걸리는 시간이 한 자릿수 차이(즉, 10배 빠르게!)로 줄어들었습니다.
• 적은 질문: "조건부 독립(CI) 테스트"(컴퓨터가 데이터에 던지는 질문)의 횟수가 극적으로 감소했습니다. 어떤 경우에는 테스트 횟수가 수십만 번에서 단 몇 천 번으로 줄어들기도 했습니다.
• 더 높은 정확도: 배경 지식이 정확할 때, 최종 지도는 더 정확했습니다. "중재 거리(intervention distance)"(추정된 인과관계가 진실에 얼마나 가까운지를 나타내는 척도)가 개선되었는데, 이는 변수를 변화시켰을 때 어떤 일이 일어날지에 대한 컴퓨터의 추측이 실제와 훨씬 더 가까워졌음을 의미합니다.

명시적으로 제외하는 사항들

이 논문은 무엇이 작동하지 않는지, 혹은 무엇을 하고 있지 않은지를 매우 명확히 밝히고 있습니다:

• "사후 처리"만으로는 부족함: 그들은 전문가의 지식을 마지막에 사용하는 것은 비효율적이라고 주장합니다. 완벽한 세상이라면 결국 같은 지도를 얻을 수는 있겠지만, 그 과정에서 엄청난 컴퓨팅 자원을 낭비하게 됩니다.
• 나쁜 데이터로는 마법을 부릴 수 없음: 전문가가 틀렸을 경우(불완전한 지식)를 테스트했습니다. 그 결과, 알고리즘들이 대체로 견고하긴 하지만, 전문가가 너무 많은 오답(예: 30%의 오류)을 낼 경우 컴퓨터가 혼란을 겪게 되며, 특정 방법(SNAP 등)에서는 문제를 푸는 데 걸리는 시간이 오히려 늘어날 수 있다는 것을 발견했습니다.
• 숨겨진 변수에 대한 "해결책" 아님: 이 논문은 모든 것에 영향을 미치는 비밀 변수(교란 요인)가 없는 상황에 초점을 맞춥니다. 그들은 숨겨진 변수를 다루는 것이 훨씬 더 어렵다는 점을 인정하며, 현재의 방식이 아직 이를 완전히 해결하지 못했음을 밝히고 있습니다. 그들은 여전히 이 부분을 연구 중입니다.

얼마나 확신하는가?

저자들은 자신들의 수학적 모델에 매우 자신감이 있습니다. 그들은 단순히 추측한 것이 아닙니다. 그들은 새로운 방법들이 "건전(sound)"하다는 것(데이터와 전문가가 완벽하다면 틀린 답을 내놓지 않음)과 "완전(complete)"하다는 것(정답이 존재한다면 반드시 찾아냄)을 증명했습니다.

• 증명됨: 새로운 알고리즘(PC-BK, SNAP-BK, MB-by-MB-BK)의 논리는 이상적인 조건 하에서 올바르게 작동함이 수학적으로 증명되었습니다.
• 측정됨: 그들은 각 시나리오에 대해 100번의 실험을 수행했으며, 가장 좋거나 나쁜 5개의 결과를 제외하여 견고한 평균값을 얻었습니다. 그들은 합성 데이터(만들어진 그래프)와 bnellarn 저장소의 실제 데이터와 유사한 데이터(44개 노드를 가진 MAGIC-NIAB 및 107개 노드를 가진 ARTH150 네트워크)를 모두 테스트했습니다.
• 시뮬레이션됨: 속도와 정확도에 관한 결과는 이러한 컴퓨터 시뮬레이션에서 나온 것입니다. 아직 실제 의료 시험이나 주식 시장 폭락 등에 적용해 보지는 않았지만, 수학적 근거는 이 방법이 거기에서도 작동할 것임을 시사합니다.

결론

이 논문은 복잡한 시스템에서 인과관계를 파악하고 싶다면, 전문가를 마지막까지 무시해서는 안 된다는 점을 시사합니다. 컴퓨터가 생각하는 동안 전문가의 말을 듣게 함으로써, 10배 더 빠르게, 그리고 훨씬 적은 노력으로 미스터리를 풀 수 있습니다. 이것은 마치 단순히 현재 위치를 알려주는 것이 아니라, 교통 체증에 걸리기 전에 미리 경로를 재탐색해 주는 GPS를 가진 것과 같습니다.