The LZ78 Source

이 논문은 LZ78 압축 알고리즘에서 유도된 확률적 소스 (LZ78 Source) 의 정의, 엔트로피적 특성, 그리고 이를 Transformer 모델의 인-컨텍스트 학습 (In-Context Learning, ICL) 성능 평가에 적용하는 방법을 다룹니다. 저자들은 LZ78 기반의 순차적 확률 할당 (Sequential Probability Assignment, SPA) 을 통해 생성된 소스의 이론적 성질을 규명하고, 이를 비정상적 (non-stationary) 이고 비마코프 (non-Markovian) 인 데이터에 대한 모델 평가 기준으로 활용합니다.

다음은 논문의 상세 기술 요약입니다.

---

1. 연구 배경 및 문제 정의 (Problem)

• LZ78 의 확률적 소스로서의 미비점: LZ78 은 보편적 압축 (Universal Compression) 과 예측 분야에서 널리 연구되었으나, 이를 **데이터 생성 확률 소스 (Probability Source)**로 체계적으로 연구한 사례는 드뭅니다. 기존 연구는 주로 손실 압축 (lossy compression) 맥락에 국한되었습니다.
• 기존 벤치마크의 한계: 인-컨텍스트 학습 (ICL) 연구는 주로 고정 차수 (fixed-order) 마코프 과정이나 가변 차수 마코프 과정 (Context Tree Weighting 등) 을 사용하여 수행되었습니다. 그러나 이러한 과정들은 맥락 (context) 의 깊이가 제한적이거나 고정되어 있어, Transformer 모델이 실제로 학습할 수 있는 복잡한 의존성 구조를 충분히 평가하기 어렵습니다.
• 연구 목표: LZ78 압축의 원리를 역이용하여 새로운 확률 소스를 정의하고, 이 소스의 엔트로피적 한계 (Entropy Rate) 와 유한 상태 (finite-state) 모델의 예측 한계를 이론적으로 규명하며, 이를 통해 Transformer 의 ICL 능력을 더 엄격하게 평가하는 새로운 벤치마크를 제시하는 것입니다.

2. 방법론 (Methodology)

A. LZ78 확률 소스 (LZ78 Source) 의 정의

• 구축 과정:
  1. 심플렉스 (Simplex) 위의 확률 분포 $\Pi$에서 i.i.d. 로 $\Theta_0, \Theta_1, \dots$를 샘플링합니다.
  2. LZ78 프리픽스 트리 (Prefix Tree) 를 동적으로 성장시킵니다.
  3. 현재 트리의 노드에 할당된 $\Theta$ 값 (Bernoulli 파라미터 등) 을 기반으로 다음 심볼 $X_t$를 생성합니다.
  4. 생성된 심볼로 트리를 업데이트하고, 새로운 리프 노드가 생성되면 다시 루트로 돌아갑니다.
• 특징: 이 과정은 LZ78 SPA (Sequential Probability Assignment) 와 동치이며, 생성된 시퀀스는 **비정상적 (non-stationary)**이고 **비마코프 (non-Markovian)**입니다. 즉, 예측에 필요한 맥락 길이가 시퀀스 길이에 따라 무한히 증가합니다.

B. 이론적 분석 도구

• 경험적 분포 (Empirical Distribution): LZ78 소스에서 생성된 시퀀스의 유한 차원 경험적 분포가 거의 확실하게 (almost surely) 결정적인 i.i.d. 법칙으로 수렴함을 증명합니다.
• 엔트로피 분석: Shannon-McMillan-Breiman 정리의 변형, 엔트로피율 (Entropy Rate), 유한 상태 압축성 (Finite-state Compressibility) 을 분석합니다.

3. 주요 기여 및 이론적 결과 (Key Contributions & Results)

A. 엔트로피적 성질 (Entropic Properties)

1. 엔트로피율 (Entropy Rate): LZ78 소스의 엔트로피율은 $E[H(\Theta)]$입니다. 여기서 $\Theta \sim \Pi$이고 $H(\cdot)$는 섀넌 엔트로피입니다.
2. Shannon-McMillan-Breiman (SMB) 성질: 생성된 시퀀스의 정규화된 로그 확률이 엔트로피율로 거의 확실하게 수렴합니다.
   $$\lim_{n \to \infty} \frac{1}{n} \log \frac{1}{Q_{LZ}(X^n)} = E[H(\Theta)] \quad \text{a.s.}$$
3. 유한 상태 압축성과 "Jensen Gap":
   • 일반적인 정상 마코프 소스와 달리, LZ78 소스의 유한 상태 모델 (Finite-state model) 이 달성할 수 있는 최소 로그 손실은 엔트로피율보다 큽니다.
   • 그 차이는 Jensen Gap으로, $H(E[\Theta]) - E[H(\Theta)] = I(\Theta; Y)$ (상호 정보량) 입니다.
   • 이는 임의의 유한한 메모리 (유한 차수 마코프 모델) 를 가진 모델은 LZ78 소스를 완벽하게 예측할 수 없으며, 엔트로피율보다 항상 더 큰 손실을 가진다는 것을 의미합니다.

B. 마코프 법칙과의 발산 (Divergence with Markovian Law)

• LZ78 소스와 $k$-차 마코프 법칙 사이의 상대 엔트로피 (Relative Entropy) 는 $n \to \infty$일 때 0 이 되지 않습니다.
• 오히려 $H(E[\Theta]) - E[H(\Theta)]$만큼의 발산이 발생하며, 이는 고차 마코프 모델조차 LZ78 소스의 무한히 깊어지는 트리 구조를 따라갈 수 없기 때문입니다.

C. 인-컨텍스트 학습 (ICL) 실험 결과

• 실험 설정: 다양한 Prior (Dirichlet, Dirac-Dirichlet mixture 등) 를 사용하여 생성된 LZ78 소스 데이터로 Transformer 모델을 학습시켰습니다.
• 결과:
  • 깊이 (Depth) 의 중요성: 레이어 수가 증가할수록 (1~5 레이어) 로그 손실이 감소하며, 이는 Transformer 이 인-컨텍스트에서 예측 알고리즘 (마코프 모델 또는 CTW 와 유사한 구조) 을 학습하고 있음을 시사합니다.
  • 비교: 3~5 레이어 Transformer 은 CTW (Context Tree Weighting) 나 고차 마코프 모델 ($\mu_k$) 보다 더 좋은 성능을 보였습니다.
  • 일반화: LZ78 소스로 학습된 모델은 실제 인간 게놈 데이터 (Genomic Data) 에 대해서도 CTW 와 유사한 성능을 보이며, 학습된 ICL 휴리스틱이 합성 데이터를 넘어 실제 데이터에도 전이됨을 확인했습니다.
  • 한계: 엔트로피가 높은 소스 (Dirichlet(2,2)) 나 거의 퇴화한 (almost-degenerate) 소스에서는 학습이 더 어렵거나, 모델이 지역 최소값에 갇히는 현상이 관찰되었습니다.

4. 의의 및 결론 (Significance)

1. 새로운 벤치마크 제시: LZ78 소스는 맥락 길이가 시퀀스 길이에 비례하여 증가하는 비마코프적이고 비정상적인 데이터를 제공합니다. 이는 기존 마코프 기반 벤치마크보다 Transformer 의 ICL 능력을 더 엄격하게 테스트할 수 있는 도구입니다.
2. 이론적 한계 규명: LZ78 소스는 유한 상태 모델의 예측 한계가 엔트로피율보다 엄격하게 높다는 것을 보여주며, 이는 "Jensen Gap"이라는 개념으로 정량화되었습니다. 이는 유한한 메모리를 가진 모델이 가질 수 있는 근본적인 한계를 보여줍니다.
3. Transformer 의 ICL 메커니즘 이해: Transformer 이 단순한 통계적 학습을 넘어, LZ78 과 같은 복잡한 의존성 구조를 가진 데이터에서 **알고리즘을 학습 (learning an algorithm)**할 수 있음을 실험적으로 입증했습니다. 특히, 모델의 깊이가 증가할수록 더 긴 의존성 (long-range dependencies) 을 포착할 수 있음을 보였습니다.
4. 향후 연구 방향: 다른 보편적 압축 알고리즘 기반 소스 연구, 더 정교한 유한 샘플 결과 개발, 그리고 슬라이딩 윈도우 기반의 보편적 손실 압축기 개발 등으로 확장 가능성이 있습니다.

요약하자면, 이 논문은 LZ78 압축을 확률 소스로 재해석하여 그 수학적 성질을 규명하고, 이를 통해 Transformer 모델의 인-컨텍스트 학습 능력을 평가하는 강력한 새로운 프레임워크를 제시했습니다.