Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning

이 논문은 선형 모델의 인과 구조 학습을 위해 빠른 부모 선택과 반복적 콜레스키 기반 점수 업데이트를 결합한 FLOP 알고리즘을 제안하며, 이를 통해 이산 탐색을 효율적으로 수행하여 기존 알고리즘보다 훨씬 빠른 실행 시간과 높은 정확도를 달성할 수 있음을 보여줍니다.

핵심

1. 문제 상황: 미로 찾기 게임

우리가 가진 데이터는 마치 거대한 미로와 같습니다. 수많은 변수 (사람, 사물, 사건) 가 서로 얽혀 있는데, "A 가 B 를 일으켰을까? 아니면 B 가 A 를 일으켰을까?" 혹은 "둘 다 C 에 의해 영향을 받았을까?"를 찾아내야 합니다.

• 기존의 방법 (연속 최적화): 마치 미로 벽을 녹여서 (연속적인 수학 기법) 길을 찾으려 시도하는 방법입니다. 벽이 녹으면 길이 보일 것 같지만, 실제로는 벽이 다시 생기고, 계산이 너무 복잡해서 길을 잃거나 엉뚱한 곳에 멈추는 경우가 많았습니다.
• 기존의 방법 (이산 탐색): 미로의 각 갈림길 하나하나를 꼼꼼히 확인하는 방법입니다. 이론적으로는 가장 정확하지만, 미로가 너무 크면 (변수가 많으면) 모든 길을 다 확인하는 데 우주 나이만큼의 시간이 걸려서 실용적이지 않았습니다.

2. FLOP 의 등장: "빠른 나침반과 지혜로운 탐색"

FLOP(Fast Learning of Order and Parents) 는 이 이산 탐색 (갈림길 하나하나 확인하기) 방식을 다시 부활시켰지만, 두 가지 강력한 무기를 추가해서 속도를 비약적으로 높였습니다.

무기 1: "이전 발자국을 활용하는 지혜" (Warm Start)

• 비유: 미로를 찾을 때, 한 번 지나간 길을 완전히 지우고 처음부터 다시 시작하는 게 아니라, 이전 단계에서 찾은 길의 흔적을 남겨두고 그 위에 조금만 더 추가하거나 빼는 방식입니다.
• 효과: 매번 0 부터 시작하는 게 아니라, 이미 알고 있는 정보를 바탕으로 다음 단계를 빠르게 계산합니다.

무기 2: "수학의 마법 (Cholesky 업데이트)"

• 비유: 미로의 지도를 그릴 때, 한 칸만 바뀌었다고 해서 지도 전체를 다시 그리는 게 아니라, 바뀐 부분만 **수정 (업데이트)**하는 기술입니다.
• 효과: 컴퓨터가 계산해야 할 양이 기하급수적으로 줄어들어, 수천 개의 변수가 있는 복잡한 미로도 순식간에 처리할 수 있게 됩니다.

3. 더 똑똑해진 전략: "실수하지 않는 시작점과 반복 학습"

FLOP 는 단순히 빠르기만 한 게 아니라, 정확도도 높였습니다.

• 똑똑한 시작점 (Initial Order):

  • 비유: 미로에 들어설 때, 아무 데나 막무가내로 들어가는 게 아니라, 가장 밀접하게 연결된 두 지점을 먼저 잡고 시작합니다.
  • 이유: 멀리 떨어진 두 지점 (예: A 와 Z) 은 직접적인 연결이 약해서 놓치기 쉽지만, FLOP 는 먼저 연결이 강한 부분부터 채워나가서 이런 실수를 방지합니다.

• 반복 학습 (Iterated Local Search):

  • 비유: 한 번 미로를 빠져나와서 "이게 최선인가?"라고 생각하다가, 다시 조금 엉뚱한 길로 들어갔다가 (Perturbation) 다시 최적의 길을 찾아내는 과정을 반복합니다.
  • 효과: 컴퓨터가 "국소 최적해 (가장 가까운 언덕)"에 갇혀서 "전체 최고 (산 정상)"를 놓치는 것을 방지합니다. 시간이 좀 더 걸리더라도, 이 과정을 여러 번 반복하면 거의 완벽한 지도를 그릴 수 있습니다.

4. 결론: 왜 이것이 중요한가요?

이 논문은 **"복잡한 인과관계를 찾는 일은, 수학적으로 어려운 '연속적인' 방법을 쓸 필요가 없다"**는 것을 증명합니다.

• 기존의 오해: "변수가 많으면 이산 탐색 (하나하나 확인) 은 불가능하다"라고 생각했습니다.
• FLOP 의 주장: "아닙니다. 우리가 계산 속도를 높이고, 시작점을 잘 잡으며, 반복해서 학습하면, 이산 탐색이 오히려 가장 빠르고 정확한 방법입니다."

한 줄 요약:
FLOP 는 거대한 데이터 미로에서 **빠른 발걸음 (최적화 기술)**과 **똑똑한 나침반 (초기화 전략)**을 들고, **실수하지 않기 위해 여러 번 다시 시도 (반복 학습)**하는 방식으로, 우리가 믿고 따라갈 수 있는 완벽한 인과관계 지도를 만들어냅니다.

이제 우리는 더 이상 "계산이 너무 느려서 포기해야 한다"고 생각하지 않아도 되며, 시간과 정확도 사이의 균형을 직접 조절할 수 있게 되었습니다.

기술 요약

FLOP: 이산 탐색을 수용한 인과 구조 학습에 대한 기술적 요약

이 논문은 선형 인과 모델 (Linear Additive Noise Models, ANM) 을 위한 FLOP (Fast Learning of Order and Parents) 라는 새로운 점수 기반 (score-based) 인과 발견 알고리즘을 제안합니다. 저자들은 기존 알고리즘들의 한계를 극복하고, 이산 탐색 (discrete search) 이 인과 구조 학습에 있어 매우 합리적이고 효과적인 접근법임을 입증하기 위해 이 연구를 수행했습니다.

1. 문제 정의 및 배경

• 목표: 관측 데이터로부터 데이터 생성 과정을 설명하는 방향성 비순환 그래프 (DAG) 를 학습하는 것.
• 배경:
  • 점수 기반 방법: 각 DAG 에 페널티가 적용된 가능도 점수 (예: BIC) 를 부여하고 최적의 그래프를 찾습니다.
  • 기존 접근법의 한계:
    • 정확한 알고리즘 (Exact algorithms): 최적 해를 보장하지만 지수 시간 복잡도를 가지며, 변수 수가 약 30 개를 넘으면 실행이 불가능합니다.
    • 국소 탐색 (Local Search): 그라디언트 기반의 연속 최적화 방법 (예: NOTEARS, DAGMA) 이나 단순한 힐 클라임빙은 국소 최적해 (local optima) 에 갇히거나, 수렴 문제, 엣지 임계값 설정 등의 어려움을 겪습니다.
    • 이산 탐색의 오해: NP-난해성 (NP-hardness) 이 주장되지만, 이는 관측되지 않은 변수가 포함된 특수한 경우에만 해당되며, 희소 DAG 가 가정되는 일반적인 인과 발견 설정에서는 다항 시간 내에 최적 해를 찾을 수 있음이 이론적으로 입증되었습니다.
• 핵심 문제: 유한 표본 (finite-sample) 에서 발생하는 국소 최적해와 계산 비용의 문제로 인해, 이산 탐색이 실제 성능에서 뒤처지는 것으로 여겨져 왔습니다.

2. 방법론 (Methodology)

FLOP 는 순서 기반 (order-based) 탐색과 재삽입 (reinsertion) 전략을 기반으로 하되, 4 가지 핵심 기술적 혁신을 통해 계산 효율성을 극대화하고 탐색 품질을 높입니다.

2.1. 이전 부모 집합을 활용한 Grow-Shrink 초기화 (Warm Start)

• 기존 방식 (BOSS 등): 노드를 순서 내에서 재배치할 때마다, 해당 노드의 부모 집합을 빈 집합 (empty set) 에서부터 다시 Grow-Shrink 알고리즘으로 탐색했습니다.
• FLOP 방식: 순서가 변경될 때, 이전 순서에서 학습된 부모 집합을 초기값 (Warm Start) 으로 사용합니다. 순서 변경은 최대 하나의 노드만 추가되거나 제거되므로, 부모 집합의 변화가 미미합니다. 이를 통해 부모 선택 과정을 훨씬 빠르게 수행할 수 있으며, 메모리 및 계산 비용을 크게 절감합니다.

2.2. 효율적인 Cholesky 분해 업데이트 (Dynamic Cholesky Updates)

• 문제: 선형 가우시안 모델에서 BIC 점수를 계산하려면 조건부 분산을 추정해야 하며, 이는 공분산 행렬의 역행렬 계산이나 Cholesky 분해를 필요로 합니다. 매번 처음부터 계산하면 $O(k^3)$ 의 비용이 듭니다.
• 해결: 부모 집합이 한 노드씩만 변할 때, 랭크-1 업데이트 (rank-one update) 및 다운데이트 (downdate) 기법을 사용하여 Cholesky 분해 결과를 $O(k^2)$ 복잡도로 갱신합니다. 이는 대규모 및 고밀도 그래프에서 계산 속도를 획기적으로 향상시킵니다.

2.3. 원칙적인 초기 순서 생성 (Principled Initialization)

• 문제: 무작위 초기 순서 (random initial order) 를 사용할 경우, 멀리 떨어진 조상 - 자손 쌍 (far-apart ancestor-descendant pairs) 간의 약한 종속성을 Grow-Shrink 가 놓쳐 비마르코프 (non-Markovian) 그래프가 생성될 수 있습니다 (특히 경로 그래프에서 치명적).
• 해결: 상관관계가 강한 노드들이 인접하도록 초기 순서를 구성합니다. 구체적으로, 현재 순서에 포함된 변수들로 설명 가능한 잔차 분산이 가장 작은 변수를 다음 순서로 선택하는 방식으로 Cholesky 분해를 활용하여 효율적으로 초기 순서를 생성합니다.

2.4. 반복적 국소 탐색 (Iterated Local Search, ILS)

• 전략: 국소 최적해에 갇히는 것을 피하기 위해 ILS 메타휴리스틱을 적용합니다.
  1. 현재 최적의 순서에서 무작위 스왑 (random swaps) 을 통해 순서를 교란 (perturb) 합니다.
  2. 교란된 순서에서 다시 국소 탐색을 수행합니다.
  3. 계산 예산 (시간 또는 반복 횟수) 이 허용하는 한 이 과정을 반복하여 더 나은 BIC 점수를 가진 그래프를 찾습니다.
• 의미: 계산 자원을 하이퍼파라미터로 간주하여, 더 많은 탐색 시간을 투자함으로써 정확도를 높일 수 있음을 보여줍니다.

3. 주요 기여 (Key Contributions)

1. FLOP 알고리즘 개발: Rust 로 구현된 FLOP 는 기존 BOSS 알고리즘보다 100 배 이상 빠른 속도를 내면서도, ILS 를 통해 더 높은 정확도를 달성합니다.
2. 이산 탐색의 부활: 계산 효율성 향상과 ILS 를 결합하여, 이산 탐색이 인과 발견에서 "합리적인 접근법 (reasonable approach)"임을 실증적으로 증명했습니다.
3. 성능 - 시간 트레이드오프 명확화: 계산 예산을 늘림으로써 정확도를 극대화할 수 있음을 보여주며, "한 번의 추론 (one-shot)"에 집착하던 기존 구조 학습 커뮤니티의 관점을 전환시킵니다.
4. 오픈소스 제공: pip install flopsearch를 통해 Python 에서 바로 사용할 수 있는 Rust 기반 라이브러리를 공개했습니다.

4. 실험 결과 (Results)

다양한 벤치마크 (Erdős-Rényi, Scale-Free, Alarm, Pathfinder 네트워크 등) 에서 FLOP 는 기존 방법들 (BOSS, PC, GES, DAGMA 등) 보다 뛰어난 성능을 보였습니다.

• 정확도 (SHD 및 AID):
  • 표준 설정 (50 노드, 평균 차수 8) 에서 FLOP 는 거의 완벽한 CPDAG 복원 (약 60% 정확도) 을 달성했으며, BOSS(40%) 및 다른 알고리즘들보다 우월했습니다.
  • 경로 그래프 (Path graphs) 와 같은 어려운 사례에서도 FLOP 는 PC, GES 와 유사하거나 더 나은 성능을 보였습니다.
  • ILS 반복 횟수 (FLOP20, FLOP100) 를 늘릴수록 정확도가 지속적으로 향상되었습니다.
• 실행 시간:
  • 100 노드 규모의 그래프에서 BOSS 보다 100 배 이상 빠릅니다.
  • 500 노드 규모의 그래프에서도 실행 가능한 반면, BOSS 는 시간 제한에 걸립니다.
• 점수 최적화:
  • FLOP 가 찾은 그래프는 종종 진짜 그래프 (Ground Truth) 보다 더 좋은 BIC 점수를 가지는 경우가 많았습니다. 이는 유한 표본에서 BIC 점수가 항상 참인 그래프를 지시하지는 않음을 시사하며, 알고리즘이 점수 최적화 자체에는 매우 능숙함을 보여줍니다.
  • 연속 최적화 방법 (DAGMA 등) 이 제안하는 "미분 가능한 DAG 제약의 최적화 우위"에 대한 의문을 제기했습니다. FLOP 가 이산 탐색으로 더 낮은 BIC 점수를 달성했기 때문입니다.

5. 의의 및 결론 (Significance)

이 논문은 인과 구조 학습 분야에서 다음과 같은 중요한 통찰을 제공합니다:

1. 이산 탐색의 재평가: NP-난해성이라는 오해와 연속 최적화 방법의 부상 속에서 소외되었던 이산 탐색이, 적절한 최적화 기법 (Cholesky 업데이트, ILS 등) 과 결합될 때 가장 강력하고 효율적인 방법임을 증명했습니다.
2. 계산 자원의 중요성: 인과 발견의 성능은 단순히 알고리즘의 설계뿐만 아니라, 얼마나 많은 계산 자원을 탐색에 투자하느냐에 크게 의존합니다. FLOP 는 계산 효율성을 통해 더 많은 탐색을 가능하게 하여 정확도를 높이는 "무료 점심 (free lunch)"을 제공합니다.
3. 실제 적용의 방향성: 합성 데이터 벤치마크에서의 성공은 이미 달성되었으나, 실제 데이터에서의 과제는 점수 기준 (scoring criteria) 의 설계와 유한 표본에서의 식별 가능성에 있음을 강조합니다. 즉, 최적화 알고리즘의 개선보다는 데이터에 적합한 점수 함수 개발이 더 시급한 과제일 수 있습니다.

결론적으로, FLOP 는 인과 발견 분야에서 이산 탐색을 다시금 주류 접근법으로 끌어올리며, 계산 효율성과 탐색 깊이를 결합한 새로운 패러다임을 제시합니다.