Rate-Distortion Theory for Deductive Sources under Closure Fidelity

1. 문제 정의 (Problem Statement)

전통적인 정보 이론 (Shannon 이론) 은 소스 심볼을 이산적인 기호의 집합으로 간주하며, 재구성 충실도 (fidelity) 를 심볼 간의 정확한 일치 (symbolwise equality) 또는 해밍 거리 (Hamming distortion) 로 측정합니다. 그러나 현대 통신 환경, 특히 지식 베이스 (Knowledge Base) 나 의미론적 통신 (Semantic Communication) 의 맥락에서는 수신자가 다른 표현으로부터 동일한 연역적 결론 (deductive consequences) 을 도출할 수 있다면, 원본 심볼을 정확히 전송할 필요가 없을 수 있습니다.

이 논문은 다음과 같은 새로운 소스 코딩 문제를 제시합니다:

• 소스 모델: 고정된 증명 체계 (proof system) 와 그로 유도된 닫힘 연산자 (closure operator, $Cn(\cdot)$) 를 갖춘 유한한 지식 베이스 (statement source).
• 충실도 기준: 심볼 단위의 정확성이 아니라, 연역적 닫힘 (deductive closure) 의 보존 여부. 즉, 전송된 데이터와 재구성된 데이터가 생성하는 논리적 결론의 집합이 동일하면 왜곡 (distortion) 이 0 으로 간주됩니다.
• 목표: 이러한 '닫힘 충실도 (Closure Fidelity)' 하에서 최소 전송 속도 (rate) 와 왜곡 (distortion) 의 관계를 규명하는 속도 - 왜곡 함수 (Rate-Distortion Function) 를 유도하는 것.

2. 방법론 및 모델 (Methodology & Model)

논문의 핵심은 소스의 중복성 구조 (redundancy structure) 를 정보 이론적으로 분석하는 데 있습니다.

• 비중복 핵심 (Irredundant Core, $A$): 주어진 증명 체계와 고정된 순서 (canonical order) 하에서, 다른 명제들로부터 유도될 수 없는 명제들의 집합.
  • $A = \text{Atom}(S_O)$: $S_O$에서 $s \in Cn(S_O \setminus \{s\})$인 원소들을 제거한 나머지 집합.
• 중복 부분 (Redundant Part, $J$): 이미 알려진 전제들로부터 유도 가능한 저장된 결론들 ($J = S_O \setminus A$).
• 닫힘 왜곡 (Closure Distortion, $d_{Cn}$): 두 명제 집합의 닫힘 집합 간의 Jaccard 유사도를 기반으로 정의된 왜곡 함수. $d_{Cn}(s, \hat{s}) = 0$은 $Cn(S_O \setminus \{s\} \cup \{s\}) = Cn(S_O \setminus \{s\} \cup \{\hat{s}\})$일 때 성립합니다.
• 가정 (Assumption 3.1): 서로 다른 핵심 심볼 (core symbols) 에 대한 0-왜곡 재구성 집합이 서로 겹치지 않는다는 조건 (Disjointness condition). 이는 0-왜곡 문제를 그래프 엔트로피가 아닌 단일 문자 (single-letter) 엔트로피로 정확히 풀 수 있게 해주는 핵심 가정입니다.

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

A. 0-왜곡 속도의 정확한 특성화 (Exact Zero-Distortion Rate)

• 결과: 닫힘 충실도 하에서 0-왜곡을 달성하는 최소 전송 속도는 전체 소스 엔트로피가 아닌, 비중복 핵심 ($A$) 의 엔트로피에 의해 결정됩니다.
• 공식:
  $$R_{sem}(0) = P_A H(\pi_A)$$
  여기서 $P_A$는 소스 분포에서 핵심 $A$가 차지하는 확률 질량이고, $H(\pi_A)$는 $A$에 조건부인 소스 분포의 엔트로피입니다.
• 의미: 중복된 결론 ($J$) 은 수신자가 추론을 통해 재구성할 수 있으므로 전송할 필요가 없습니다. 따라서 효율적인 전송은 오직 '핵심'만 전송하는 것으로 축소됩니다.

B. 전체 속도 - 왜곡 함수의 핵심 분해 (Core Decomposition)

• 결과: 임의의 왜곡 수준 $D$에 대해, 전체 속도 - 왜곡 함수 $R_{sem}(D)$는 비중복 핵심에 대한 고전적인 속도 - 왜곡 함수로 분해됩니다.
• 공식:
  $$R_{sem}(D) = P_A \cdot R^{(A)}\left(\frac{D}{P_A}\right)$$
• 의미: 중복 상태 ($J$) 는 속도와 왜곡 모두에 대해 '보이지 않는 (invisible)' 존재가 됩니다. 전체 문제는 단순히 핵심 소스에 대한 고전적인 압축 문제로 환원됩니다.

C. 제한된 추론 예산을 위한 속도 - 지연 - 왜곡 트레이드오프 (Rate-Delay-Distortion Tradeoff)

• 배경: 수신자가 무한한 추론 능력을 가진 것이 아니라, 제한된 수의 추론 단계 ($\delta$) 만 수행할 수 있는 경우.
• 결과: $\delta$-비중복 핵심 ($A_\delta$) 을 정의하고, 이에 따른 정확한 속도 - 지연 - 왜곡 관계를 유도했습니다.
  • $\delta = 0$: 고전적인 심볼 단위 압축 (해밍 왜곡) 과 동일.
  • $\delta \ge D_d$ (최대 유도 깊이): 무제한 추론이 가능한 경우의 연역적 압축과 동일.
• 의미: 추론 능력 (지연) 이 증가할수록 전송해야 할 데이터의 양 (속도) 이 감소하는 정량적인 관계를 규명했습니다.

D. 이종 수신자 및 채널 분리 (Heterogeneous Receivers & Separation)

• 이종 수신자: 수신자의 어휘 (reconstruction alphabet) 가 송신자의 것과 다를 경우, 핵심 심볼에 대해 '닫힘 동등한 대표 (closure-equivalent representative)'가 존재하는지 여부가 0-왜곡 가능 여부를 결정합니다.
• 채널 분리: 단일 문자 왜곡을 사용하므로, 소스 - 채널 분리 정리 (Source-Channel Separation Theorem) 가 그대로 적용됩니다. 즉, 소스 코딩과 채널 코딩을 분리하여 설계할 수 있으며, 채널 용량이 $P_A H(\pi_A)$를 초과하면 신뢰성 있는 통신이 가능합니다.

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

1. 구조적 소스 코딩의 이론적 기반: 의미론적 통신 (Semantic Communication) 이나 태스크 지향 통신을 단순한 아키텍처 제안이 아닌, 엄밀한 정보 이론적 소스 모델로 정립했습니다.
2. 공유 추론 구조의 가치 정량화: 송수신자가 공유하는 증명 체계 (proof system) 가 통신의 근본적인 한계를 어떻게 변화시키는지 정량화했습니다. 즉, 공유된 추론 구조는 전송 비용을 줄이는 자원 (rate-reducing resource) 으로 작용함을 보였습니다.
3. 데이터베이스 및 지식 베이스 적용: 데이터베이스의 물리화 (materialization) 된 결론들을 전송할 때, 원본 지식 베이스의 핵심 (EDB facts) 만 전송하면 충분함을 정보 이론적으로 증명했습니다. 이는 데이터 압축 및 통신 효율성 향상에 직접적인 시사점을 줍니다.
4. 한계 및 향후 과제: 현재 결과는 0-왜곡 재구성 집합이 서로 겹치지 않는다는 가정 (Assumption 3.1) 하에 성립합니다. 이 가정이 깨지는 경우 (핵심 심볼 간의 혼동 가능성, confusability) 에 대한 일반화된 해법 (그래프 엔트로피 기반 접근 등) 은 향후 연구 과제로 남았습니다.

요약하자면, 이 논문은 "무엇을 전송해야 하는가?"에 대한 전통적인 답을 넘어, "무엇을 공유된 추론으로 대체할 수 있는가?"를 정보 이론적으로 규명함으로써, 지식 기반 소스 코딩의 새로운 패러다임을 제시했습니다.