8.1 데이터 압축의 정의와 정보 이론적 동기

1. 데이터 압축의 형식적 정의

1.1 부호화와 복호화의 쌍

데이터 압축(data compression)은 데이터의 표현을 보다 적은 비트 수로 변환하는 과정이다. 형식적으로, 알파벳 $\mathcal{X}$ 위의 데이터 수열 $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ 에 대해, 부호화 함수(encoder) $E: \mathcal{X}^n \to \{0, 1\}^*$ 는 데이터를 이진 수열로 변환하고, 복호화 함수(decoder) $D: \{0, 1\}^* \to \hat{\mathcal{X}}^n$ 는 이진 수열을 원래 데이터 또는 그 근사로 복원한다.

무손실 압축에서는 $D(E(\mathbf{x})) = \mathbf{x}$ 가 모든 $\mathbf{x}$ 에 대해 성립해야 하며, 손실 압축에서는 $D(E(\mathbf{x})) = \hat{\mathbf{x}}$ 가 원래 데이터의 근사이되 왜곡 $d(\mathbf{x}, \hat{\mathbf{x}})$ 가 허용 수준 이하여야 한다.

1.2 압축률의 정의

압축률(compression ratio)은 원래 데이터의 비트 수 대비 압축된 데이터의 비트 수의 비율이다:

$\rho = \frac{\lvert E(\mathbf{x}) \rvert}{n \log_2 \lvert\mathcal{X}\rvert}$

$\rho < 1$ 이면 압축이 달성된 것이며, $\rho$ 가 작을수록 압축 효율이 높다. 기호 당 평균 부호 길이(average bits per symbol)는 $\bar{R} = E[\lvert E(\mathbf{X}) \rvert] / n$ 으로 정의된다.

2. 정보 이론적 동기

2.1 잉여성의 존재

현실의 데이터는 균등하게 분포하지 않는다. 자연어 텍스트에서 특정 문자 쌍(예: ‘th’, ‘he’)이 다른 쌍(예: ‘qx’, ‘zj’)보다 압도적으로 자주 출현하며, 이미지에서 인접 픽셀 값은 강한 상관관계를 가진다. 이러한 비균등성과 의존성은 데이터에 잉여성(redundancy)을 생성한다.

잉여성은 정보원의 최대 가능 엔트로피와 실제 엔트로피의 차이로 정량화된다:

$\text{redundancy} = \log_2 \lvert\mathcal{X}\rvert - H(X)$

또는 상대적 잉여성:

$r = 1 - \frac{H(X)}{\log_2 \lvert\mathcal{X}\rvert}$

영어 텍스트의 경우 $r \approx 0.7\text{--}0.8$ 으로, 텍스트의 약 70~80%가 잉여적이다. 이 잉여성의 존재가 데이터 압축을 가능하게 하는 근본적 이유이다.

2.2 엔트로피 — 압축의 근본적 한계

섀넌의 무잡음 부호화 정리는 이산 무기억 정보원의 무손실 압축에서 기호 당 평균 비트 수의 하한이 엔트로피 $H(X)$ 임을 증명하였다:

$\bar{R} \geq H(X)$

이 한계는 달성 가능하다: 충분히 긴 블록에 대해 $\bar{R}$ 을 $H(X)$ 에 임의로 가깝게 만드는 부호가 존재한다. 따라서 데이터 압축의 목표는 정보원의 잉여성을 최대한 제거하여 기호 당 비트 수를 엔트로피에 가깝게 만드는 것이다.

2.3 데이터 압축과 모형화의 동등성

데이터를 효율적으로 압축하려면 데이터의 확률적 구조를 정확히 파악해야 한다. 최적 부호어 길이가 $l(x) = -\log_2 p(x)$ 이므로, 참 확률 분포 $p$ 를 정확히 알수록 더 짧은 부호어를 할당할 수 있다. 잘못된 분포 $q$ 에 기반한 부호는 교차 엔트로피 $H(p, q) = H(p) + D_{\text{KL}}(p \| q)$ 의 평균 부호 길이를 가지며, 이는 최적보다 $D_{\text{KL}}(p \| q)$ 만큼 길다.

이 관계는 데이터 압축과 확률 모형화(probabilistic modeling)의 근본적 동등성을 확립한다. 좋은 압축기는 좋은 확률 모형이고, 그 역도 성립한다. 이 동등성은 현대 기계 학습에서 “학습은 압축이다“라는 관점의 정보론적 기초이다.

3. 잉여성의 유형

3.1 통계적 잉여성

통계적 잉여성(statistical redundancy)은 기호의 비균등 확률 분포에서 기인한다. 빈번한 기호에 짧은 부호를, 드문 기호에 긴 부호를 할당하는 가변 길이 부호화(variable-length coding)에 의해 제거된다.

3.2 구조적 잉여성

구조적 잉여성(structural redundancy)은 기호 간의 통계적 의존성에서 기인한다. 이전 기호를 알면 다음 기호에 대한 불확실성이 감소하며, 이 감소분이 구조적 잉여성이다. 정보 이론적으로, 이는 $H(X) - H(X \vert \text{context}) > 0$ 에 해당하며, 맥락 기반 모형(context model)과 예측 기반 부호화(predictive coding)에 의해 활용된다.

3.3 심리 시각적/청각적 잉여성

인간의 지각 체계가 감지하지 못하는 데이터 성분은 지각적 잉여성(perceptual redundancy)을 구성한다. 이 잉여성은 무손실 압축이 아닌 손실 압축에서 활용되며, JPEG의 이산 코사인 변환(DCT) 계수의 양자화, MP3의 심리 음향 모형(psychoacoustic model)에 의한 마스킹(masking) 효과 활용 등이 대표적 사례이다.

4. 압축과 학습의 관계

4.1 예측과 압축의 동등성

데이터의 다음 기호를 예측하는 것과 데이터를 압축하는 것은 정보론적으로 동등하다. 예측 모형이 $P(x_t \vert x_1, \ldots, x_{t-1})$ 를 정확히 추정하면, 산술 부호화에 의해 기호 $x_t$ 를 약 $-\log_2 P(x_t \vert x_{<t})$ 비트로 부호화할 수 있다. 더 정확한 예측은 더 짧은 부호를 산출하므로, 예측 정확도의 향상은 압축 효율의 향상과 직결된다.

이 동등성에 의해, 언어 모형의 퍼플렉서티가 낮을수록 해당 모형을 기반으로 한 텍스트 압축이 더 효율적이다. 현대의 대규모 언어 모형은 전통적 압축 알고리즘보다 텍스트 데이터에 대해 더 높은 압축률을 달성할 수 있으며, 이는 이 모형들이 언어의 통계적 구조를 매우 정밀하게 포착하고 있음의 증거이다.

5. 결론

데이터 압축의 정보 이론적 동기는 데이터에 내재하는 잉여성의 존재와 엔트로피에 의한 압축 한계의 규정으로 요약된다. 잉여성의 제거가 압축의 본질이며, 엔트로피는 이 제거의 한계를 정확히 규정한다. 데이터 압축, 확률 모형화, 예측의 정보론적 동등성은 데이터 과학과 기계 학습의 근본적 연결 고리를 형성하며, 이 연결에 대한 이해는 현대 인공지능의 이론적 기초를 구성한다.