Dictionary Based Pattern Entropy for Causal Direction Discovery

이 논문은 심볼릭 시계열 데이터에서 인과 방향을 추론하고 효과 변수의 변화를 주도하는 하위 패턴을 식별하기 위해 알고리즘 정보 이론과 섀넌 정보 이론을 통합한 '사전 기반 패턴 엔트로피 (DPE)' 프레임워크를 제안하며, 다양한 합성 및 생물학적 데이터셋에서 기존 방법들보다 우수한 성능을 입증합니다.

핵심

🕵️‍♂️ 핵심 비유: "수사관과 암호 해독기"

상상해 보세요. 두 사람이 서로 대화하고 있습니다.

• A 씨는 일기를 쓰고, B 씨는 그 일기를 보고 반응합니다.
• 우리는 누가 먼저 말을 시작했는지 (인과 관계) 알 수 없지만, 두 사람의 대화 내용 (데이터) 만 가지고 추론해야 합니다.

기존의 방법들은 "통계적 상관관계"를 보거나, "복잡한 수학적 모델"을 만들어서 답을 찾으려 했습니다. 하지만 이 논문은 **"패턴 (규칙)"**에 집중하는 새로운 수사관, **DPE(사전 기반 패턴 엔트로피)**를 소개합니다.

1. DPE 가 하는 일: "규칙 찾기" (사전 만들기)

DPE 는 두 가지 가설을 세우고 데이터를 뒤집니다.

• 가설 1: "A 씨의 말 (패턴) 이 B 씨의 반응을 일으켰다."
• 가설 2: "B 씨의 말 (패턴) 이 A 씨의 반응을 일으켰다."

어떻게 찾나요?

1. 사전 (Dictionary) 만들기:

   • B 씨가 갑자기 말을 바꿀 때 (예: 웃음에서 울음으로), 그 직전 A 씨가 무슨 말을 했는지 기록합니다.
   • 예를 들어, B 씨가 울기 직전 A 씨가 항상 **"안녕하세요, 오늘 날씨가..."**라고 말했다면, 이 구절을 '사전'에 저장합니다.
   • 이 과정을 반복해서 A 씨의 말과 B 씨의 반응 사이의 고정된 규칙을 찾아냅니다.

2. 엔트로피 (불확실성) 측정:

   • 이제 이 규칙이 얼마나 확실한지 확인합니다.
   • "A 씨가 '안녕하세요'라고 하면 100% B 씨가 울었다"라면? → 불확실성 (엔트로피) = 0. 아주 확실한 인과 관계입니다.
   • "A 씨가 '안녕하세요'라고 했는데 B 씨가 울기도 하고 웃기도 했다"라면? → 불확실성 (엔트로피) = 높음. 인과 관계가 약하거나 우연일 수 있습니다.

결론:
DPE 는 **"어떤 방향 (A→B 또는 B→A) 으로 보았을 때 규칙이 더 명확하고, 불확실성이 더 적은가?"**를 비교합니다. 불확실성이 낮은 쪽이 진짜 인과 관계라고 판단합니다.

---

2. 왜 이 방법이 특별한가요? (기존 방법과의 차이)

• 기존 방법 (통계/모델): "A 와 B 는 함께 움직이니까 인과 관계일 거야"라고 추측하거나, 복잡한 수식을 만들어서 적합도를 따집니다. 하지만 데이터가 짧거나 잡음이 많으면 실패하기 쉽습니다.
• DPE 방법: "A 의 특정 말 (패턴) 이 B 의 반응을 규칙적으로 유도했나?"를 봅니다. 마치 암호 해독처럼, "이 패턴이 나오면 저 반응이 온다"는 명확한 규칙을 찾아냅니다.

비유하자면:

• 기존 방법: "비가 오면 우산을 쓰는 사람이 많으니, 우산이 비를 부르는 건가?"라고 통계만 봅니다.
• DPE 방법: "우산을 쓴 사람 (A) 이 비를 보자마자 (패턴) 우산을 폈다 (반응)"는 구체적인 행동 규칙을 찾아냅니다.

---

3. 이 방법이 잘 작동한 곳들 (실험 결과)

논문은 이 방법이 다양한 상황에서 얼마나 잘 작동하는지 테스트했습니다.

1. 인공 데이터 (가상 시나리오):

   • 지연된 비트 플립: A 가 특정 패턴을 만들면, B 가 2 초 뒤에 반응하는 상황. DPE 는 99% 정확도로 "A 가 원인이다"라고 맞췄습니다. (다른 방법들은 실패하거나 50% 대였습니다.)
   • 생태계 (포식자 - 피식자): "사자가 달려들면 (원인) 토끼가 도망친다 (결과)"는 관계를 찾아냈습니다.

2. 실제 데이터 (바이러스):

   • 코로나바이러스 (SARS-CoV-2): "전 세계 공통 바이러스가 각 나라의 변이를 만들었나?" 아니면 "각 나라의 초기 바이러스가 변이를 만들었나?"를 분석했습니다.
   • DPE 는 다른 방법들과는 조금 다른 결론을 내렸는데, 이는 데이터의 특성에 따라 다른 관점을 제공할 수 있음을 보여줍니다.

---

4. 요약: 이 논문이 우리에게 주는 메시지

이 논문의 핵심은 **"인과 관계는 복잡한 수식이 아니라, 반복되는 '규칙'에서 찾아야 한다"**는 것입니다.

• **DPE(사전 기반 패턴 엔트로피)**는 데이터 속에서 **"이 패턴이 나오면 저 반응이 온다"**는 규칙을 찾아내고, 그 규칙이 얼마나 확실한지 (엔트로피가 낮은지) 측정합니다.
• 이 방법은 잡음이 많거나 데이터가 짧을 때도, 규칙적인 패턴을 가진 시스템에서는 매우 강력하게 작동합니다.
• 마치 수사관이 용의자의 행동 패턴을 분석해 범행 시점을 추적하듯, 데이터의 패턴을 분석해 인과 관계를 찾아냅니다.

한 줄 요약:

"복잡한 수학적 모델 대신, 데이터 속에 숨겨진 **'규칙적인 패턴'**을 찾아내어, 무엇이 무엇을 일으켰는지 불확실성 없이 찾아내는 새로운 수사법입니다."

기술 요약

1. 문제 정의 (Problem Statement)

기존의 인과 관계 발견 (Causal Discovery) 방법론은 주로 관측 데이터에서 인과 방향을 추론하는 데 어려움을 겪고 있습니다. 특히 기호 시퀀스 (symbolic sequences) 나 노이즈가 포함된 데이터의 경우 다음과 같은 한계가 존재합니다.

• 기능적 모델 부재: 많은 실제 데이터는 명확한 함수 관계나 노이즈 가정을 따르지 않습니다.
• 기존 방법의 한계:
  • 그래프 기반 또는 함수적 인과 모델 (FCM) 은 조건부 독립성이나 특정 함수 형태에 대한 강한 가정을 필요로 합니다.
  • 알고리즘 정보 이론 (AIT) 기반 방법 (예: LZP, ETCE, ETCP) 은 데이터 압축을 통해 인과성을 추론하지만, 노이즈가 많거나 데이터 길이가 짧은 경우 신뢰도가 떨어질 수 있습니다.
  • 정보 이론적 (Shannon 기반) 방법은 정확한 확률 분포 추정을 위해 긴 시퀀스가 필요하며, 데이터가 부족한 환경에서는 불안정합니다.

이 논문은 이러한 한계를 극복하고, 노이즈가 있는 관측 데이터로부터 인과 방향과 이를 주도하는 구체적인 하위 패턴 (subpatterns) 을 동시에 식별할 수 있는 새로운 프레임워크를 제안합니다.

2. 제안 방법론: 사전 기반 패턴 엔트로피 (DPE)

저자들은 알고리즘 정보 이론 (AIT) 과 섀넌 정보 이론 (Shannon Information Theory) 을 결합한 사전 기반 패턴 엔트로피 (Dictionary Based Pattern Entropy, DPE) 프레임워크를 제안합니다.

핵심 개념

• 인과성의 정의: 인과 관계는 원인 변수 (Cause) 에 존재하는 압축된 규칙 기반 패턴이 결과 변수 (Effect) 의 변화를 체계적으로 제약하는 현상으로 해석합니다.
• 목표:
  1. 인과 방향 (X→Y 또는 Y→X) 결정.
  2. 결과 변수의 변화를 일으키는 구체적인 원인 패턴 식별 및 기여도 측정.

알고리즘 단계

1. 사전 구축 (Dictionary Construction):
   • 결과 변수 (Y) 에서 비트 플립 (상태 변화) 이 발생하는 지점을 기준으로, 원인 변수 (X) 의 해당 시점까지의 서브스트링 (부분 문자열) 을 추출하여 사전 ($G_{X \to Y}$) 을 구성합니다.
   • 반대 방향 ($G_{Y \to X}$) 에 대해서도 동일한 과정을 수행합니다.
2. 패턴 추출 (Pattern Extraction):
   • 추출된 서브스트링들 간의 유사성을 분석하기 위해 XNOR 기반 슬라이딩 비교를 수행합니다.
   • 연속적인 매칭 (1) 이 발생하는 공통 서브스트링들을 최종 패턴 사전 ($P_{X \to Y}$) 으로 정의합니다.
3. 반응 결정성 측정 (Response Determinism, $R_{flip}$):
   • 각 패턴이 원인 변수에서 발생할 때, 결과 변수에서 상태 변화 (비트 플립) 를 일으키는 비율을 계산합니다.
   • $R_{flip} = \frac{\text{변화 발생 횟수}}{\text{총 발생 횟수}}$
   • 값이 1 에 가까우면 결정론적 영향, 0 에 가까우면 상태 유지, 중간 값은 확률적 영향을 의미합니다.
4. 가중 엔트로피 계산 (Weighted Entropy):
   • 각 패턴의 불확실성을 이진 엔트로피 함수 $H_b(r_p)$로 계산하고, 패턴의 발생 빈도에 따라 가중치 ($W_p$) 를 부여합니다.
   • 평균 가중 엔트로피 ($\bar{H}$): 전체 패턴 집합에 대한 가중 엔트로피의 평균을 구합니다.
   • $H_w(p) = W_p \cdot H_b(r_p)$
5. 인과 방향 추론:
   • $\bar{H}_{X \to Y}$와 $\bar{H}_{Y \to X}$를 비교합니다.
   • 최소 불확실성 원칙: 더 낮은 평균 엔트로피를 보이는 방향이 더 강한 결정론적 구조를 가지므로, 이를 인과 방향으로 판정합니다.

3. 주요 기여 (Key Contributions)

1. 하이브리드 프레임워크: 알고리즘적 구조 (패턴 추출) 와 확률적 변동성 (엔트로피) 을 통합하여, 결정론적 패턴과 확률적 노이즈를 동시에 처리할 수 있는 새로운 접근법을 제시했습니다.
2. 해석 가능성 (Interpretability): 단순히 인과 방향만 추론하는 것을 넘어, 어떤 구체적인 하위 패턴이 인과를 주도하는지 식별하고 그 기여도를 정량화합니다.
3. 강건한 성능: 짧은 시퀀스, 노이즈가 있는 데이터, 그리고 다양한 비선형 동역학 시스템에서 기존 AIT 기반 방법들 (ETCE, ETCP, LZP) 보다 우수한 또는 동등한 성능을 입증했습니다.

4. 실험 결과 (Results)

논문은 다양한 합성 데이터와 실제 데이터셋을 통해 DPE 의 성능을 평가했습니다.

• 합성 데이터 (Synthetic Systems):

  • 지연 비트 플립 (Delayed Bit-flip): 0~6 단계의 지연이 있는 경우, DPE 는 99% 의 정확도로 인과 방향을 정확히 예측했습니다 (LZP 는 97.9%, ETCP 는 57%).
  • AR(1) 결합 (Unidirectional Coupling): 결합 강도가 증가함에 따라 DPE 의 정확도는 98.5% 이상으로 급격히 상승하며, ETCE/ETCP 보다 우월한 성능을 보였습니다.
  • 희소 프로세스 (Sparse Processes): 데이터가 매우 희소한 경우에도 DPE 는 100% 정확도를 기록했으나, 다른 방법들은 대부분 독립으로 잘못 판단했습니다.
  • 1D Skew-tent Maps (비선형 카오스): 결합 계수 $\eta > 0$인 모든 구간에서 DPE 는 90% 이상의 정확도를 보였으며, 특히 동기화가 발생하는 높은 결합 강도 ($\eta=0.9$) 에서도 100% 정확도를 달성했습니다. 이는 다른 방법들이 실패하는 영역입니다.

• 실제 데이터 (Real-world Datasets):

  • SARS-CoV-2 유전체 분석: 국가별 초기 서열 (CW) 과 글로벌 참조 서열 (RS) 간의 인과성을 분석했습니다. DPE 는 19 개 국가 중 10 개 국가에서 CW 가 RS 보다 강한 인과성을 가진다고 판단했으나, LZP 와 ETCP 는 RS 가 주된 원인이라고 판단하는 경향이 더 강했습니다. 이는 데이터 특성에 따라 방법론 간 차이가 있음을 보여줍니다.
  • 포식자 - 피식자 시스템 (Predator-Prey): 실제 생태계 데이터 (Didinium 와 Paramecium) 에서 포식자가 피식자에 미치는 영향이 더 크다는 것을 DPE 가 정확히 포착했습니다 (엔트로피 값이 더 낮음).

• 종합 비교 (Table 7):

  • DPE 는 모든 합성 실험에서 80% 이상의 평균 정확도를 달성하여 가장 일관된 신뢰도를 보였습니다.
  • 반면, ETCE 와 ETCP 는 비선형 시스템이나 희소 데이터에서 성능이 크게 저하되었습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 해석 가능한 인과 발견: DPE 는 "왜" 그 방향이 인과적인지 설명할 수 있는 구체적인 패턴 (알고리즘 단위) 을 제공함으로써 블랙박스 모델의 한계를 극복합니다.
• 범용성: 결정론적 규칙이 명확한 동역학 시스템뿐만 아니라, 노이즈가 섞인 실제 관측 데이터에서도 robust 하게 작동합니다.
• 한계 및 향후 과제:
  • 혼란 변수 (Confounding variables) 를 명시적으로 고려하지 않음.
  • 두 시스템이 완전히 독립적인 경우 ($\eta=0$) 를 인과가 없는 것으로 판단하는 기준이 아직 완벽하지 않아, 위양성 (Spurious influence) 을 보일 수 있음.
  • 향후에는 위약 데이터 (Surrogate data) 분석과 통계적 유의성 검정을 도입하여 독립성 판단 기준을 강화할 필요가 있음.

결론적으로, 이 논문은 패턴 기반의 엔트로피 최소화를 통해 인과 방향과 그 메커니즘을 동시에 규명하는 강력하고 해석 가능한 프레임워크를 제시하며, 특히 복잡한 동역학 시스템과 제한된 데이터 환경에서의 인과 발견에 중요한 기여를 합니다.