Chapter 8. 정보 이론 기반 데이터 압축의 수학적 기초
1. 서론: 데이터 압축의 이론적 위상
데이터 압축(data compression)은 정보의 표현에 사용되는 비트 수를 줄이는 과정이다. 클로드 섀넌(Claude Shannon)의 정보 이론은 데이터 압축의 이론적 한계를 엄밀하게 규정하였으며, 무잡음 부호화 정리에 의해 정보원의 엔트로피가 무손실 압축의 절대적 하한임이 증명되었다. 본장에서는 이 이론적 기초 위에서, 실제 데이터 압축 알고리즘의 수학적 원리와 엔트로피 한계에의 접근 방식을 체계적으로 분석한다.
2. 무손실 압축과 손실 압축의 구분
2.1 무손실 압축
무손실 압축(lossless compression)은 압축된 데이터로부터 원래 데이터를 완전히 복원할 수 있는 압축 방식이다. 부호화 함수 E와 복호화 함수 D가 모든 메시지 x에 대해 D(E(x)) = x를 만족한다. 무잡음 부호화 정리에 의해, 무손실 압축의 평균 압축률은 정보원의 엔트로피에 의해 하한이 설정된다.
무손실 압축은 텍스트, 프로그램 코드, 데이터베이스 등 원본의 정확한 복원이 필수적인 응용에서 사용된다. 허프만 부호화, 산술 부호화, 렘펠-지브(Lempel-Ziv) 알고리즘 등이 대표적 무손실 압축 기법이다.
2.2 손실 압축
손실 압축(lossy compression)은 원본 데이터의 정확한 복원을 포기하고, 허용 가능한 왜곡(distortion) 수준 내에서 더 높은 압축률을 달성하는 방식이다. 율-왜곡 이론(rate-distortion theory)이 손실 압축의 이론적 기초를 제공하며, 주어진 왜곡 수준에서 달성 가능한 최소 전송률을 규정한다.
손실 압축은 이미지(JPEG), 음성(MP3, AAC), 동영상(H.264, H.265) 등 인간의 지각적 한계를 활용할 수 있는 멀티미디어 데이터에서 주로 사용된다.
3. 정보원 부호화의 수학적 기초
3.1 엔트로피와 압축 한계의 관계
이산 무기억 정보원(DMS) X의 엔트로피 H(X)는 무손실 압축의 기호 당 최소 평균 비트 수이다. 이 한계는 두 가지 측면에서 정확하다:
- 달성 불가능성: 어떠한 무손실 부호도 기호 당 평균 부호 길이를 H(X) 미만으로 줄일 수 없다.
- 달성 가능성: 블록 부호화에 의해 기호 당 평균 부호 길이를 H(X) + \epsilon (\epsilon > 0 임의)으로 만드는 부호가 존재한다.
이 두 결과의 결합이 엔트로피를 압축의 정확한 한계로 확립한다.
3.2 정보원 부호화의 범주
정보원 부호화 기법은 크게 두 범주로 분류된다:
고정 대 가변 길이 부호화(fixed-to-variable length coding): 고정 길이의 정보원 블록을 가변 길이의 부호어로 변환한다. 허프만 부호화가 대표적이다. 빈번한 패턴에 짧은 부호어를, 드문 패턴에 긴 부호어를 할당하여 평균 부호 길이를 줄인다.
가변 대 고정 길이 부호화(variable-to-fixed length coding): 가변 길이의 정보원 수열을 고정 길이의 부호어로 변환한다. 렘펠-지브 부호화의 특정 변종이 이 범주에 속한다.
4. 유니버설 압축의 개념
4.1 정보원 분포 미지의 상황
실제 응용에서 정보원의 확률 분포는 일반적으로 사전에 알려져 있지 않다. 유니버설 부호(universal code)는 정보원의 분포에 대한 사전 지식 없이도, 충분히 긴 데이터에 대해 엔트로피에 점근적으로 접근하는 압축률을 달성하는 부호이다.
렘펠-지브 알고리즘은 유니버설 부호의 대표적 사례이다. 이 알고리즘은 데이터 자체로부터 통계적 구조를 점진적으로 학습하여 적응적으로 부호화하며, 에르고드 정보원에 대해 엔트로피율에 점근적으로 수렴하는 압축률을 보장한다.
4.2 적응적 부호화
적응적(adaptive) 부호화는 이미 처리된 데이터로부터 정보원의 확률 모형을 점진적으로 갱신하며 부호화하는 방식이다. 적응적 허프만 부호화, 적응적 산술 부호화, 예측 기반 부호화(prediction-based coding) 등이 이 범주에 속한다. 적응적 부호화는 정보원의 통계적 특성이 시간에 따라 변하는 비정상(non-stationary) 정보원에 대해서도 효과적이다.
5. 율-왜곡 이론의 기초
5.1 율-왜곡 함수
손실 압축의 이론적 한계는 율-왜곡 함수(rate-distortion function) R(D)에 의해 규정된다. 정보원 X와 재구성 변수 \hat{X}, 왜곡 측도 d(x, \hat{x})가 주어졌을 때:
R(D) = \min_{p(\hat{x} \vert x): E[d(X, \hat{X})] \leq D} I(X; \hat{X})
R(D)는 평균 왜곡이 D 이하인 모든 부호 중에서 달성 가능한 최소 전송률이다. D = 0이면 무손실 압축이 필요하므로 R(0) = H(X)이다. D가 증가함에 따라 R(D)는 단조 감소하며, 충분히 큰 D에서 R(D) = 0이 된다.
5.2 가우시안 정보원의 율-왜곡 함수
평균 0, 분산 \sigma^2인 가우시안 정보원에서 평균 제곱 오차(MSE) 왜곡 측도를 사용하면:
R(D) = \begin{cases} \frac{1}{2}\log_2 \frac{\sigma^2}{D} & \text{if } 0 < D \leq \sigma^2 \\ 0 & \text{if } D > \sigma^2 \end{cases}
이 결과는 가우시안 정보원에서 왜곡 D를 허용할 때 필요한 최소 전송률을 정확히 규정한다.
6. 인공지능에서의 데이터 압축
6.1 학습된 압축
심층 신경망에 기반한 학습된 이미지 압축(learned image compression)은 전통적 부호화 기법을 대체하는 새로운 패러다임이다. 변분 오토인코더(VAE)와 같은 생성 모형을 기반으로 정보원의 잠재 표현(latent representation)을 학습하고, 이 표현에 대한 엔트로피 부호화를 수행한다. 율-왜곡 최적화의 목적 함수:
\mathcal{L} = R + \lambda D = E[-\log_2 q(\hat{z})] + \lambda E[d(x, \hat{x})]
는 율-왜곡 이론의 라그랑주 완화(Lagrangian relaxation)에 직접 대응한다.
6.2 토큰화와 압축
자연어 처리에서 토큰화(tokenization)는 텍스트를 토큰의 수열로 변환하는 과정이며, 이는 정보원 부호화의 관점에서 해석할 수 있다. 바이트 쌍 인코딩(Byte Pair Encoding, BPE)은 빈번한 문자 쌍을 반복적으로 합쳐 새로운 토큰을 생성하는 방식으로, 데이터 압축에서의 사전 기반(dictionary-based) 접근법과 유사한 원리를 따른다.
7. 결론
정보 이론 기반 데이터 압축은 엔트로피에 의한 근본적 한계의 규정으로부터 출발하여, 이 한계에 실용적으로 접근하는 알고리즘의 설계로 나아간다. 무손실 압축에서의 엔트로피 한계, 손실 압축에서의 율-왜곡 한계, 유니버설 압축에서의 정보원 미지 상황에 대한 대응은 정보 이론이 데이터 압축의 전 영역에 걸쳐 제공하는 이론적 기초의 체계적 구조를 형성한다. 이 수학적 기초의 이해는 현대 인공지능에서 학습된 압축, 표현 학습, 정보 병목 원리 등의 이론적 배경을 파악하는 데 필수적이다.