7.11 엔트로피의 연쇄 법칙(Chain Rule)과 부가 분해 성질

1. 두 변수에 대한 연쇄 법칙

1.1 기본 형태

엔트로피의 연쇄 법칙(chain rule for entropy)은 결합 엔트로피를 개별 엔트로피와 조건부 엔트로피의 합으로 분해하는 항등식이다. 두 이산 확률 변수 $X$ 와 $Y$ 에 대해:

$H(X, Y) = H(X) + H(Y \vert X)$

이 항등식은 $(X, Y)$ 를 동시에 아는 것의 불확실성이, 먼저 $X$ 를 아는 것의 불확실성과 $X$ 를 알고 난 후 $Y$ 에 대해 남는 조건부 불확실성의 합과 같다는 것을 진술한다.

1.2 증명

결합 확률의 곱 법칙 $p(x, y) = p(x) p(y \vert x)$ 로부터 출발한다:

$H(X, Y) = -\sum_x \sum_y p(x, y) \log_2 p(x, y)$

$= -\sum_x \sum_y p(x, y) \log_2 [p(x) p(y \vert x)]$

$= -\sum_x \sum_y p(x, y) \log_2 p(x) - \sum_x \sum_y p(x, y) \log_2 p(y \vert x)$

첫째 합에서 $\sum_y p(x, y) = p(x)$ 이므로:

$-\sum_x p(x) \log_2 p(x) = H(X)$

둘째 합은 조건부 엔트로피의 정의:

$-\sum_x \sum_y p(x, y) \log_2 p(y \vert x) = H(Y \vert X)$

따라서 $H(X, Y) = H(X) + H(Y \vert X)$ 이다.

1.3 대칭적 분해

결합 확률은 $p(x, y) = p(y) p(x \vert y)$ 로도 분해되므로, 동일한 논증에 의해:

$H(X, Y) = H(Y) + H(X \vert Y)$

두 분해를 결합하면:

$H(X) + H(Y \vert X) = H(Y) + H(X \vert Y)$

이 등식은 상호 정보량의 대칭성 $I(X; Y) = I(Y; X)$ 의 직접적 귀결이기도 하다. $H(X) - H(X \vert Y) = H(Y) - H(Y \vert X) = I(X; Y)$ 이기 때문이다.

2. $n$ 개 변수에 대한 일반 연쇄 법칙

2.1 일반 형태의 진술

연쇄 법칙은 임의 유한 개의 확률 변수에 대해 확장된다. $n$ 개의 이산 확률 변수 $X_1, X_2, \ldots, X_n$ 에 대해:

$H(X_1, X_2, \ldots, X_n) = \sum_{i=1}^{n} H(X_i \vert X_1, X_2, \ldots, X_{i-1})$

여기서 $H(X_1 \vert X_0) = H(X_1)$ 로 약속한다 (공집합에 조건화하는 것은 무조건부와 동일).

2.2 증명 (수학적 귀납법)

기저 사례: $n = 1$ 일 때 $H(X_1) = H(X_1)$ 으로 자명하다.

귀납 단계: $n-1$ 개의 변수에 대해 연쇄 법칙이 성립한다고 가정한다. 두 변수에 대한 연쇄 법칙에서 $X = (X_1, \ldots, X_{n-1})$ , $Y = X_n$ 으로 놓으면:

$H(X_1, \ldots, X_n) = H(X_1, \ldots, X_{n-1}) + H(X_n \vert X_1, \ldots, X_{n-1})$

귀납 가정에 의해:

$H(X_1, \ldots, X_{n-1}) = \sum_{i=1}^{n-1} H(X_i \vert X_1, \ldots, X_{i-1})$

따라서:

$H(X_1, \ldots, X_n) = \sum_{i=1}^{n} H(X_i \vert X_1, \ldots, X_{i-1})$

2.3 직관적 해석

일반 연쇄 법칙은 $n$ 개 확률 변수의 결합 불확실성을, 변수를 하나씩 순차적으로 관측하는 과정에서 각 단계의 조건부 불확실성의 합으로 분해한다. 첫 번째 변수 $X_1$ 에 대한 불확실성은 $H(X_1)$ 이고, $X_1$ 을 알고 난 후 $X_2$ 에 대한 추가 불확실성은 $H(X_2 \vert X_1)$ 이며, 이를 $X_n$ 까지 반복한다.

중요한 점은, 연쇄 법칙이 변수의 순서(ordering)에 무관하게 성립한다는 것이다. 어떤 순서로 분해하든 최종적인 합은 동일한 결합 엔트로피 $H(X_1, \ldots, X_n)$ 을 산출한다. 다만, 개별 조건부 엔트로피 항 $H(X_i \vert X_1, \ldots, X_{i-1})$ 의 값은 순서에 따라 달라진다.

3. 부가 분해 성질

3.1 독립인 경우의 가법성

$X_1, X_2, \ldots, X_n$ 이 상호 독립(mutually independent)이면, 각 $i$ 에 대해 $H(X_i \vert X_1, \ldots, X_{i-1}) = H(X_i)$ 이므로:

$H(X_1, X_2, \ldots, X_n) = \sum_{i=1}^{n} H(X_i)$

이 가법성(additivity)은 독립 확률 변수의 결합 불확실성이 개별 불확실성의 단순 합임을 의미한다. 독립성이 결합 확률의 곱 분해를 보장하고, 로그가 곱을 합으로 변환하는 데서 이 성질이 도출된다.

3.2 부가법성 (의존인 경우)

변수들이 독립이 아닌 경우, 조건부 엔트로피 감소 성질 $H(X_i \vert X_1, \ldots, X_{i-1}) \leq H(X_i)$ 에 의해:

$H(X_1, X_2, \ldots, X_n) \leq \sum_{i=1}^{n} H(X_i)$

이 부등식은 엔트로피의 부가법성(subadditivity)이라 하며, 등호는 모든 변수가 상호 독립일 때에만 성립한다. 부가법성의 의미는, 변수들 사이의 통계적 의존성은 결합 불확실성을 개별 불확실성의 합보다 줄인다는 것이다. 의존성이 존재하면 한 변수의 관측이 다른 변수에 대한 정보를 제공하므로, 전체적으로 필요한 ‘새로운’ 불확실성의 총량이 감소한다.

3.3 강한 부가법성

엔트로피의 강한 부가법성(strong subadditivity)은 세 확률 변수 $X$ , $Y$ , $Z$ 에 대한 다음 부등식이다:

$H(X, Y, Z) + H(Y) \leq H(X, Y) + H(Y, Z)$

이를 정리하면 동등한 형태로:

$H(X \vert Y, Z) \leq H(X \vert Y)$

이 부등식은 추가 변수 $Z$ 에 대한 조건화가 $X$ 의 조건부 엔트로피를 감소시킨다(또는 유지한다)는 것을 진술한다. 즉, 더 많은 정보를 조건으로 할수록 잔여 불확실성은 줄어든다.

강한 부가법성은 조건화에 의한 엔트로피 감소 $H(X \vert Y) \leq H(X)$ 의 일반화이다. 후자는 $Z$ 가 공집합인 특수한 경우에 해당한다.

4. 상호 정보량의 연쇄 법칙

4.1 진술

상호 정보량에 대해서도 연쇄 법칙이 성립한다. 확률 변수 $X_1, X_2, \ldots, X_n$ 과 $Y$ 에 대해:

$I(X_1, X_2, \ldots, X_n; Y) = \sum_{i=1}^{n} I(X_i; Y \vert X_1, \ldots, X_{i-1})$

이 법칙은 $n$ 개 변수의 집합이 $Y$ 에 대해 가지는 총 정보량을, 각 변수가 이전 변수들을 조건으로 하여 $Y$ 에 대해 추가적으로 제공하는 정보량의 합으로 분해한다.

4.2 증명

엔트로피의 연쇄 법칙과 조건부 엔트로피의 정의로부터 도출된다:

$I(X_1, \ldots, X_n; Y) = H(X_1, \ldots, X_n) - H(X_1, \ldots, X_n \vert Y)$

$= \sum_{i=1}^{n} H(X_i \vert X_1, \ldots, X_{i-1}) - \sum_{i=1}^{n} H(X_i \vert X_1, \ldots, X_{i-1}, Y)$

$= \sum_{i=1}^{n} [H(X_i \vert X_1, \ldots, X_{i-1}) - H(X_i \vert X_1, \ldots, X_{i-1}, Y)]$

$= \sum_{i=1}^{n} I(X_i; Y \vert X_1, \ldots, X_{i-1})$

5. 연쇄 법칙의 응용

5.1 엔트로피율의 존재성 증명

정상 확률 과정(stationary stochastic process) $\{X_i\}$ 에 대해, 엔트로피율 $\mathcal{H} = \lim_{n \to \infty} (1/n) H(X_1, \ldots, X_n)$ 의 존재를 증명하는 데 연쇄 법칙이 핵심적으로 사용된다. 연쇄 법칙에 의해:

$\frac{1}{n} H(X_1, \ldots, X_n) = \frac{1}{n} \sum_{i=1}^{n} H(X_i \vert X_1, \ldots, X_{i-1})$

정상성에 의해 $H(X_i \vert X_1, \ldots, X_{i-1})$ 는 $i$ 에 대해 감소하는 수열이며(조건화 정보가 많아질수록 조건부 엔트로피가 감소하므로), 하계가 0이므로 극한이 존재한다. 이 극한은 체사로 평균(Cesàro mean)의 수렴에 의해 $(1/n) H(X_1, \ldots, X_n)$ 의 극한과 일치한다.

5.2 무잡음 부호화 정리의 증명

무잡음 부호화 정리에서, $n$ 개의 독립 동일 분포 기호를 블록 부호화(block coding)할 때의 최적 평균 부호 길이가 $H(X)$ 에 수렴함을 보이는 증명에서, 연쇄 법칙은 결합 엔트로피를 $H(X_1, \ldots, X_n) = nH(X)$ (i.i.d.인 경우)로 분해하는 데 사용된다.

5.3 베이지안 네트워크에서의 결합 분포 분해

베이지안 네트워크(Bayesian network)에서 결합 분포는 연쇄 법칙에 기반한 조건부 독립성 가정을 통해 분해된다. $n$ 개의 변수로 구성된 베이지안 네트워크의 결합 분포는:

$p(x_1, \ldots, x_n) = \prod_{i=1}^{n} p(x_i \vert \text{pa}(x_i))$

여기서 $\text{pa}(x_i)$ 는 변수 $X_i$ 의 부모 노드 집합이다. 이 분해는 일반 연쇄 법칙에서 조건부 독립성 가정을 적용하여 조건 집합을 축소한 것이다. 결합 엔트로피에 대해서도 동일한 분해가 적용된다:

$H(X_1, \ldots, X_n) = \sum_{i=1}^{n} H(X_i \vert \text{pa}(X_i))$

6. 조건부 연쇄 법칙

제3의 변수 $Z$ 가 주어진 조건 하에서도 연쇄 법칙이 성립한다:

$H(X_1, X_2, \ldots, X_n \vert Z) = \sum_{i=1}^{n} H(X_i \vert X_1, \ldots, X_{i-1}, Z)$

이 조건부 연쇄 법칙은 무조건부 연쇄 법칙의 자연스러운 확장이며, 증명은 조건부 확률의 곱 법칙을 반복 적용하는 것으로 무조건부의 경우와 동일한 구조를 따른다.

7. 결론

엔트로피의 연쇄 법칙은 정보 이론의 가장 기본적이고 강력한 도구 중 하나이다. 이 법칙은 복잡한 다변수 시스템의 불확실성을 순차적 조건부 불확실성의 합으로 분해하는 체계적 방법을 제공한다. 독립인 경우의 가법성과 의존인 경우의 부가법성은 변수 간 의존 구조가 결합 불확실성에 미치는 영향을 정량적으로 포착한다. 연쇄 법칙은 정보원 부호화 정리, 채널 부호화 정리, 엔트로피율의 존재성 등 정보 이론의 핵심 결과들의 증명에서 반복적으로 활용되며, 기계 학습에서 베이지안 네트워크의 이론적 기초와도 직결된다.