8.2 정보 엔트로피와 데이터 압축률의 이론적 관계

1. 엔트로피와 최소 부호 길이

1.1 엔트로피의 조작적 의미

이산 무기억 정보원(DMS) $X$ 의 엔트로피 $H(X) = -\sum_i p_i \log_2 p_i$ 는 무손실 압축의 기호 당 최소 평균 비트 수라는 조작적 의미(operational meaning)를 가진다. 이 의미는 무잡음 부호화 정리에 의해 확립된다.

유일 복호 가능 부호(uniquely decodable code)의 부호어 길이 $l_i$ 에 대해, 평균 부호 길이 $\bar{L} = \sum_i p_i l_i$ 는 항상 $H(X)$ 이상이다:

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

등호는 모든 $p_i$ 가 $2^{-k}$ ( $k$ 는 양의 정수) 형태일 때에만 정수 길이 부호로 달성 가능하다. 일반적 경우, 허프만 부호에 의해 $H(X) \leq \bar{L}_H < H(X) + 1$ 이 보장된다.

1.2 이상적 부호 길이

개별 기호 $x_i$ 의 이상적 부호어 길이는 $l_i^* = -\log_2 p_i$ 이다. 이 길이는 자기 정보량(self-information)과 동일하며, 해당 기호의 발생이 전달하는 정보량에 정확히 대응한다. 빈번한 기호(높은 $p_i$ )에는 짧은 부호어가, 드문 기호(낮은 $p_i$ )에는 긴 부호어가 할당되어야 한다는 정보론적 원칙이 이 관계에서 도출된다.

2. 압축률과 엔트로피의 관계

2.1 기호 당 압축률

원래 데이터가 $\log_2 \lvert\mathcal{X}\rvert$ 비트/기호의 고정 길이 표현을 사용할 때, 압축 후의 기호 당 비트 수가 $\bar{L}$ 이면 압축률은:

$\rho = \frac{\bar{L}}{\log_2 \lvert\mathcal{X}\rvert}$

엔트로피에 의한 하한:

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

여기서 $r = 1 - H(X)/\log_2 \lvert\mathcal{X}\rvert$ 은 상대적 잉여성(relative redundancy)이다. 압축률의 이론적 하한은 $(1 - r)$ 이며, 잉여성이 클수록(정보원이 비균등할수록) 더 높은 압축이 가능하다.

2.2 블록 부호화에 의한 접근

$n$ 개 기호의 블록을 단일 단위로 부호화하면, 블록 당 엔트로피는 $H(X^n)$ 이다. i.i.d. 정보원에서 $H(X^n) = nH(X)$ 이므로, 기호 당 평균 비트 수는:

$H(X) \leq \frac{\bar{L}_n}{n} < H(X) + \frac{1}{n}$

$n \to \infty$ 에서 기호 당 비트 수는 $H(X)$ 에 수렴한다. 블록 길이의 증가는 압축 효율을 개선하되, 계산 복잡도와 지연의 증가를 수반한다.

3. 기억을 가지는 정보원에서의 압축

3.1 엔트로피율과 압축 한계

기억을 가지는 정상 에르고드 정보원(stationary ergodic source) $\{X_t\}$ 에서, 압축의 한계는 엔트로피율(entropy rate)에 의해 결정된다:

$\mathcal{H} = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n) = \lim_{n \to \infty} H(X_n \vert X_{n-1}, \ldots, X_1)$

엔트로피율은 조건화에 의해 개별 엔트로피 이하이다:

$\mathcal{H} \leq H(X)$

기호 간 통계적 의존성이 강할수록 엔트로피율이 $H(X)$ 보다 크게 감소하며, 이 감소분이 의존성의 활용에 의한 추가적 압축 가능 여지를 나타낸다.

3.2 조건부 부호화

기호 간 의존성을 활용하는 부호화에서, $t$ 번째 기호의 부호어 길이는 이상적으로 $l_t = -\log_2 P(x_t \vert x_1, \ldots, x_{t-1})$ 이다. 이 조건부 부호화에 의한 기호 당 평균 비트 수는:

$\frac{1}{n}\sum_{t=1}^{n} E[-\log_2 P(X_t \vert X_{<t})] = \frac{1}{n} H(X_1, \ldots, X_n)$

$n \to \infty$ 에서 이는 엔트로피율 $\mathcal{H}$ 에 수렴한다.

4. 교차 엔트로피와 모형 불일치의 비용

4.1 모형 불일치에 의한 압축 비효율

참 분포 $P$ 와 모형 분포 $Q$ 가 다를 때, $Q$ 에 기반한 부호의 기호 당 평균 비트 수는 교차 엔트로피 $H(P, Q)$ 이다:

$H(P, Q) = H(P) + D_{\text{KL}}(P \| Q)$

KL 발산 $D_{\text{KL}}(P \| Q)$ 는 모형 불일치에 의한 추가적 비트 수이다. 정보원의 통계적 구조를 정확히 모형화할수록 이 추가 비용이 줄어든다.

4.2 적응적 부호화의 수렴

적응적 부호화에서 모형은 데이터를 처리하면서 점진적으로 개선된다. 관측된 데이터가 충분히 축적되면 모형 $Q$ 가 참 분포 $P$ 에 수렴하고, 교차 엔트로피가 엔트로피에 접근한다. 이 수렴 속도는 모형의 학습 속도에 의해 결정되며, 정보 이론에서의 잉여성(redundancy)은 이 수렴 과정에서의 비용을 정량화한다.

5. 율-왜곡 함수와 손실 압축

5.1 손실 압축에서의 엔트로피 역할

손실 압축에서 허용 왜곡 $D$ 가 주어질 때, 최소 전송률은 율-왜곡 함수 $R(D)$ 에 의해 결정된다. $R(0) = H(X)$ 이므로, 무왜곡 조건에서 율-왜곡 함수는 엔트로피와 일치한다. $D > 0$ 이면 $R(D) < H(X)$ 이며, 왜곡 허용이 엔트로피 이하의 압축률을 가능하게 한다.

율-왜곡 함수는 상호 정보량의 최소화로 정의된다:

$R(D) = \min_{p(\hat{x} \vert x): E[d(X, \hat{X})] \leq D} I(X; \hat{X})$

이 정의에서 상호 정보량은 원본과 재구성 사이에 보존되는 정보의 양을 나타내며, 율-왜곡 최적화는 필요한 최소 정보만을 전달하는 부호화를 추구한다.

6. 결론

정보 엔트로피는 데이터 압축률의 근본적이고 정확한 한계를 규정한다. 무손실 압축에서 엔트로피는 기호 당 최소 평균 비트 수이며, 손실 압축에서 율-왜곡 함수는 왜곡 수준에 따른 최소 전송률을 규정한다. 모형 분포와 참 분포의 불일치는 KL 발산에 의해 정량화되는 추가적 비트 비용을 초래하며, 이는 효율적 압축이 정확한 확률 모형화를 필요로 함을 확인한다. 이 이론적 관계들은 데이터 압축 알고리즘의 설계와 성능 평가의 수학적 기반이다.