기술 요약: 확률적 코드를 이용한 데이터 압축

문제 정의

본 논문은 전통적인 손실 소스 코딩의 근본적인 한계인 **양자화(quantisation)**에 대해 다룹니다. 표준 양자화기는 연속적인 소스 데이터를 이산적인 값의 집합으로 매핑하며, 이는 재구성 분포를 디락 측도(Dirac measure, 단일 점)로 강제합니다. 이러한 제약은 압축 메커니즘의 유연성을 제한하여, 레이트(rate), 왜곡(distortion), 그리고 "사실성(realism, 출력 분포가 소스 분포와 갖는 통계적 일치도)" 사이의 최적의 트레이드오프를 달성하는 데 있어 종종 하위 최적의 결과를 초래합니다.

저자들은 이에 대한 일반적인 대안으로 **상대 엔트로피 코딩(Relative Entropy Coding, REC)**을 제안합니다. REC는 결정론적인 양자화에 국한되지 않고, 재구성을 위한 임의의 원하는 조건부 분포 $P_{\hat{X}|X}$를 시뮬레이션할 수 있는 **확률적 코드(stochastic codes)**를 구축하는 것을 목표로 합니다. 핵심 과제는 계산 가능성을 유지하면서, 코드 길이를 상호 정보량 $I[X; \hat{X}]$에 가깝게 구현하는 것입니다.

방법론

논문은 확률적 코드를 다음의 세 요소로 구성된 삼중항 $(Z, \text{enc}_Z, \text{dec}_Z)$로 정의합니다:

1. $Z$는 공유된 무작위성(shared randomness, 입력 $X$와 독립적임)입니다.
2. $\text{enc}_Z$는 $X$를 비트 문자열로 매핑하는 인코더입니다.
3. $\text{dec}_Z$는 비트 문자열을 다시 샘플 $\hat{X}$로 매핑하는 디코더입니다.

목표는 기대 코드 길이를 최소화하면서 $\text{dec}_Z(\text{enc}_Z(X)) \sim P_{\hat{X}|X}$를 만족시키는 것입니다. 이론적인 코드 길이의 하한은 상호 정보량 $I[X; \hat{X}]$입니다.

본 논문은 몇 가지 구축 방법론을 상세히 설명합니다:

1. 선택 샘플러 (Selection Samplers)

저자들은 REC를 디코더가 공유된 i.i.d. 제안(proposals) 시퀀스 $\{Y_i\} \sim P_Y$로부터 샘플을 선택해야 하는 샘플링 문제로 프레임화합니다. 이때 선택된 샘플은 $P_{\hat{X}|X}$를 따라야 합니다.

• 기각 샘플링 (Rejection Sampling): 가장 단순한 접근 방식입니다. 인코더는 밀도 비율 임계값에 따라 제안이 수락되는 첫 번째 인덱스 $K$를 찾습니다. 인덱스 $K$가 인코딩됩니다. 그러나 표준 기각 샘플링은 종종 코드 길이가 $O(\|r\|_\infty)$가 되며, 밀도 비율이 유계가 아니거나 매우 큰 경우 $I[X; \hat{X}]$보다 지수적으로 더 커질 수 있습니다.
• 포아송 함수 표현 (Poisson Functional Representation, A 코딩):* 표준 기각 샘플링의 비효율성을 극복하기 위해, 저자들은 인덱스를 최소화하는 순서로 제안을 시뮬레이션하는 포아송 프로세스를 사용하는 방법을 설명합니다. 이 "재정렬된(reordered)" 접근 방식(A* 코딩)은 기대 코드 길이가 상호 정보량의 로그 인자 이내가 되도록 보장하여, 유효한 상대 엔트로피 코드가 되도록 합니다.
• 실행 시간 제한: 논문은 일반적인 선택 샘플러의 경우 기대 실행 시간이 $E[\|r_X\|_\infty]$와 같이 스케일링된다고 언급하며, 이는 정보량에 비해 종종 지수적으로 느려집니다. 이는 일반적인 REC 알고리즘을 엔트로피 코딩에 비해 비현실적으로 느리게 만듭니다.

2. 디더링 및 계층적 양자화기 (Dithered and Layered Quantisers)

계산 효율성을 달기 위해 논문은 특정 채널 구조에 집중합니다:

• 디더링 양자화 (Dithered Quantisation): 가산 균등 노이즈 채널($Y = X + U$)의 경우, 저자들은 양자화된 값의 엔트로피 코딩된 인덱스를 전송하는 코드를 구축하기 위해 "디더링 항등식(dithering identity)"을 활용합니다. 이는 $I[X; Y] + O(1)$의 코드 길이와 선형 실행 시간을 달성합니다.
• 계층적 양자화 (Layered Quantisation): 이는 디더링 양자화를 단봉형 가산 노이즈(unimodal additive noise) 채널로 확장한 것으로, 노이즈를 이동된 균등 분포의 스케일 혼합(scale mixture of shifted uniforms, SMSU)으로 표현합니다. 양자화 그리드를 무작위로 스케일링하고 이동시킴으로써, 이 방법은 1차원 단봉형 분포에 대해 최적의 코드 길이와 빠른 실행 시간을 달성합니다.

3. 근사 및 고급 방법론

• 근사 코드 (Approximate Codes): 유계가 아닌 밀도 비율(예: 확산 모델)을 처리하거나 실행 시간을 줄이기 위해, 논문은 **단계 제한 샘플러(step-limited samplers)**를 논의합니다. 이 알고리즘은 예산을 초과하면 조기에 종료되어 근사 샘플을 출력합니다. 이는 정확한 분포 매칭을 약간 희생하는 대신 다항 시간 실행 시간과 병렬성을 확보합니다.
• 분기 한정 탐색 (Branch-and-Bound, BnB) 샘플러: 단봉형 분포의 경우, BnB 탐색 전략은 기대 실행 시간을 밀도 비율에 대해 지수적에서 로그 수준으로 줄여 계층적 양자화기의 대안을 제공합니다.
• 채널 코드: 고차원 i.i.d. 베르누이 채널을 위해 최적의 실행 시간을 갖는 REC를 구축하는 방법으로 최근의 폴라 코드(polar codes) 사용이 언급되었습니다.

주요 기여 및 응용 분야

본 논문은 REC를 단순한 이론적 호기기가 아니라 학습된 압축(learned compression) 및 개인정보 보호 데이터 공개를 위한 실질적인 도구로 자리매김합니다.

1. 학습된 손실 압축:

   • REC는 압축 시스템의 엔드 투 엔드(end-to-end) 학습을 가능하게 합니다. 양자화와 달리 비미분적인 양자화와 달리, REC는 재매개변수화 기법(reparameterization trick)을 사용하여 경사 하강법을 통해 조건부 분포 $P_{\hat{X}|X}$를 직접 최적화할 수 있게 해줍니다.
   • 사례 연구 (INRs): 저자들은 신경망 가중치가 확률 변수로 취급되는 **베이지안 암시적 신경 표현(Bayesian Implicit Neural Representations)**을 강조합니다. 가중치를 양자화하는 대신, 시스템은 사후 분포를 학습하고 REC를 사용하여 그로부터의 샘플을 인코딩합니다.
   • 사례 연구 (연합 학습): 연합 확률적 마스크 훈련(FedPM)에서, REC는 마스크 자체를 인코딩하는 대신 선택된 서브 네트워크 마스크의 인덱스를 인코딩함으로써 통신 비용을 줄이고 최대 82배의 비트레이트 감소를 달성합니다.

2. 사실성 제약이 있는 압축:

   • REC는 재구성 $\hat{X}$가 픽셀 단위 왜곡을 최소화하기보다는 소스 통계량을 따르는 분포를 갖도록 합니다. 논문은 양자화기가 여기서 본질적으로 불리한 반면, REC는 노이즈 메커니즘(예: 확산 모델)을 활용하여 주어진 사실성 제약에 대해 더 낮은 레이트를 달성할 수 있다고 주장합니다.

3. 확산 모델 (DiffC):

   • 논문은 가우시안 확산 모델을 사용하는 가변 레이트 압축 방식인 DiffC를 제시합니다. 확산 과정을 궤적을 따라 일련의 REC 문제로 취급함으로써, 이 방법은 "완벽하게 사실적인" 재구성을 달성합니다.
   • 실용성: 유계가 아닌 밀도 비율 때문에 확산 모델에 대한 정확한 REC는 불가능하므로, 저자들은 단계 제한 근사 샘플러를 권장합니다. 이는 GPU에서의 병렬화를 가능하게 하여 인코딩 시간을 몇 시간에서 몇 초로 단축합니다.

4. 개인정보 보호 및 강화 학습:

   • 차분 프라이버시 (Differential Privacy): REC는 개인정보 보호 메커니즘(예: 라플라스 또는 가우시안 노이즈)이 적용된 데이터를 효율적으로 인코딩하면서도 프라이버시 보장을 유지하는 프레임워크를 제공합니다.
   • 원격 강화 학습 (Remote Reinforcement Learning): REC는 컨트롤러가 에이전트의 정책으로부터 후보 행동을 식로는 짧은 인덱스를 전송할 수 있게 하여, 행동 자체를 전송하는 것보다 통신 오버헤드를 크게 줄여줍니다.

결과 및 주장

• 이론적 하한: 논문은 일반적인 REC 알고리즘의 코드 길이가 $I[X; \hat{X}] + \log(I[X; \hat{X}] + 1)$의 하한을 갖는 반면, 특정 구축 방식(예: 디더링 양자화기)은 $I[X; \hat{X}] + O(1)$을 달성할 수 있음을 입증합니다.
• 계산적 트레이드오프: 저자들은 일반적인 REC가 계산적으로 매우 비싸다는 점을 명시합니다. 선택 샘플러의 실행 시간은 일반적으로 정보량에 대해 지수적입니다. 그러나 특정 구조(단봉형 노이즈, 근사 모델을 사용하는 확산 모델 등)에 대해서는 효율적인 알고리즘이 존재합니다.
• 경험적 성능: 논문은 참조된 연구들의 실험 결과를 인용하며 다음을 보여줍니다:
  • 연합 학습(FedPM)에서 최대 82배의 비트레이트 감소.
  • 행동이나 보상을 직접 전송하는 것과 비교했을 때 원격 강화 학습에서 12배 및 41배의 감소.
  • GPU 상에서 DiffC의 성공적인 구현을 통해 인코딩 시간을 몇 시간에서 몇 초로 단축.

의의 및 한계

의의:
논문은 REC가 손실 압축의 패러다임을 "양자화기를 선택하고 그 오차를 분석하는 것"에서 "원하는 재구성 분포를 선택하고 이를 구현하는 것"으로 전환한다고 주장합니다. 이러한 유연성은 생성형 AI와 같이 **사실성(realism)**이 중요한 현대적 응용 분야와 프라이버시 분야에서 매우 중요합니다. 이는 정보 이론과 머신러닝을 결에는서, 미분 가능한 압축 파이프라인을 가능하게 합니다.

한계:
저자들은 광범위한 채택을 가로막는 두 가지 주요 장벽을 인정합니다:

1. 속도: 일반적인 REC 알고리즘은 양자화 기반 방식보다 현저히 느립니다. 특정 분포를 위한 특수 알고리즘이 존재하지만, 범용적이고 빠른 REC 알고리즘은 여전히 미해결 과제로 남아 있습니다.
2. 동기화: REC는 공유된 무작위성(예: PRNG 시드)에 의존합니다. 인코더와 디코더 사이의 완벽한 동기화를 유지하는 것은 공학적 도전이며, 동기화 실패는 치명적인 오류로 이어집니다.

결론:
논문은 REC가 학습된 압축과 프라이버시 분야에서 깊은 이론적 우아함과 실질적인 잠재력을 가진 신흥 분야라고 결론짓습니다. 그러나 현재의 실용성은 계산 복잡도와 공학적 오버헤드에 의해 제약을 받고 있으며, 빠르고 특수 목적에 맞는 REC 알고리즘을 개발하는 것이 향후 연구의 핵심 방향이 될 것입니다.