2-1. 엔트로피, 상관 엔트로피 및 상호 정보

Elements of Information Theory - Second Edition, Thomas M. Cover & Joy A. Thomas

2.1 시작하며

해당 내용은 서적의 2번째 장 (chapter 2)의 내용을 다루고 있다. 서적에 대한 정보는 글의 맨 위에 있다.

2장에서는 "엔트로피 (entropy)"와 "상호 정보 (mutual information)"에 대해서 다시 정의하고,

그 이후에는 "체인 규칙 (chain rule)", "mutual information의 비음수성 (non-negativity)",

"데이터 처리 부등식 (data-processing inequality)"을 정의한다.

또한, "충분 통계량(sufficient statistics)"과 "파노의 부등식 (Fano's inequality)"를 이용하여 이러한 정의들을 설명한다.

2장에서 상당히 많은 내용을 다루고 있어서 전반부(2-1)와 후반부(2-2)로 나누어 다룰 것이다.

2.2 엔트로피

엔트로피는 확률변수 (random variable)의 불확실성 (uncertainty)를 측정하는 척도이다.

예를 들어보면, 확률질량함수 (probability mass function) p(x) = Pr(X = x) 를 갖는 확률변수 X 가 있다고 하자.

여기서 x 는 alphabet X 의 요소 (component), 즉, x in alphabet X 이다.

이전 글에서 다뤘던 것처럼, 확률변수 X 에 대한 엔트로피의 정의는 다음과 같다.

달리 말이 없다면, 로그의 밑이 2인 것으로 가정한다. 따라서, 모든 엔트로피는 bit로 측정된다.

엔트로피는 X 의 분포 (distribution)에 대한 함수이다.

이는 확률변수 X 가 취하는 실제 값에 의해 정해지는 것이 아니라, 오직 "확률 (probability)"에 의해 정해진다는 의미이다.

우리는 기댓값 (expectation)을 E 라 표현한다고 해보자. 따라서 X ~ p(x), 즉, 확률변수 X 가 p(x) 의 확률을 갖는다면, 확률변수 X 의 기댓값 g(X) 는 다음과 같다.

2.3 엔트로피의 정리 및 예제

이제 엔트로피의 특성 (property)에 대해 살펴보자. 엔트로피는 다음 두개의 명제 (Lemma)를 만족한다.

(참고: 오른쪽 아래에 있는 검정색 사각형은 수학에서의 증명완료(Q.E.D.)를 의미한다.)

이 중 하나를 설명해보면, 첫번째 Lemma 2.1.1의 경우, 확률변수 X 의 확률은 0과 1사이에 존재한다.

따라서 log를 취할 경우, log(1/p(x))가 0 이상을 의미하기에, X 에 대한 엔트로피 H(X) 는 음수가 될 수 없다.

이제 예제를 들어 엔트로피를 구해보자.

Example 1: 확률변수 X 는 p 의 확률로 1의 값을 갖고, 1-p 의 확률로 0의 값을 갖는다. 이를 수식으로 정의한 것과 확률변수 X의 엔트로피를 구해보면 다음과 같다.

이와 같은 분포를 베르누이 분포 (Bernoulli distribution)라 한다.
만약 p = 1/2 이라면, 엔트로피 H(X) 는 1bit이다.
해당 엔트로피의 그래프는 아래와 같은 그림으로 나타낼 수 있다.
그림을 분석하면, p=1/2 인 경우에 uncertainty가 최대값을 가지며, 이는 엔트로피의 최대값에 해당한다.

2.4 결합 엔트로피 및 조건부 엔트로피

지금까지 단일 확률변수 (single random variable)의 엔트로피에 대해 정의하였다.

이제 이러한 정의를 확장하여 두 확률변수에 대해서도 적용한다.

먼저, "결합 엔트로피 (joint entropy)"에 대해 정의한다.

두 이산 (discrete) 확률변수 X 및 Y 가 결합확률분포 (joint distribution)을 가질 때, joint entropy는 H(X,Y) 로 정의된다.

이에 대한 식은 다음과 같이 두 형태로 표현할 수 있다.

이제 "조건부 엔트로피 (conditional entropy)"에 대해 정의하자.

하나의 확률변수가 다른 확률변수에 대한 "조건부 분포"로써 정의된 엔트로피의 기대값으로 정의한다.

다음과 같이 정의할 수 있는 이유는 다음 이론을 기반으로한 사실로부터 표현할 수 있다.

이론은 "두 확률변수의 엔트로피"가 "한 확률변수의 엔트로피"와 "다른 확률변수의 조건부 엔트로피의 합"으로 표현된다.

이를 식으로 표현하면 다음과 같으며 이를 "chain rule"이라 한다.

증명에 대해 설명해보자. 먼저 첫번째 등식은 joint entropy의 정의에 의해 성립한다.

두번째 등식은 "베이스 정리 (Bayes' theorem)"에 의해 성립된다. 해당 부분은 <linear algebra>를 참고하자.

세번째 등식은 log의 성질 log(AB) = log(A) + log(B)에 의해 성립된다.

결과적으로, 이와같이 chain rule을 증명할 수 있다.

또한 앞에서 설명한 chain rule에 expectation을 취하면, 다음과 같이 표현할 수 있다.

여기서부터 파생된 다음과 같은 정리가 있다. 이또한, 위에서 증명한 것과 동일한 방식으로 증명 가능하다.

이제, 예제를 통해 conditional entropy와 joint entropy를 어떻게 구하는지 살펴보자.

Random variable X 및 Y 에 대한 joint distribution이 다음과 같다고 하자.

여기서, random variable X 와 Y 에 대한 한계 분포 (marginal distribution)는 각각 (1/2, 1/4, 1/8, 1/8)와 (1/4, 1/4, 1/4, 1/4)이다. 따라서, X 와 Y 에 대한 entropy를 구해보면, 각각 H(X) = 7/4 bits, H(Y) = 2bits 이다.

결론적으로 Y 가 주어졌을 때, Y 의 entropy, 즉, H(X|Y) 는 다음과 같이 구할 수 있다.

이와 동일한 방법으로 X 가 주어졌을 때, Y 의 entropy H(Y|X) 는 13/8 bits이고, 결론적으로 H(X,Y) 는 27/8 bits이다.

2.5 상대 엔트로피 및 상호 정보

상대 엔트로피 (relative entropy)는 두개의 분포 사이의 거리를 측정하는 지표이다.

통계학에서는 우도비 (likelihood ratio)의 로그 (logarithm)의 기댓값으로 나타낸다.

Relative entropy D(p||q) 는 실제 분포가 p 라고 할때, 분포가 q 라고 가정한 것의 비효율성 (inefficiency)를 측정한다.

다시 말해서, 우리가 확률변수의 실제분포가 p 라는 사실을 안다고 했을 때, H(p) 만큼의 길이를 갖는 코드를 설계할 수 있다. 그러나 p 라는 실제분포 대신에, q 라는 분포에 대한 코드를 사용한다면, H(p) + D(p||q) 만큼의 비트가 필요하다.

또한, Relative entropy는 "Kullback-Leibler distance"라고 불린다.
항상 음이 아닌 값을 가지며, p = q 인 경우에만 D(p||q) = 0 이 된다.

확률질량함수 (PMF) p(x)와 q(x)사이의 Kullback-Leibler (KL) distance는 다음과 같이 정의된다.

"KL divergence"라고도 하지만(사실, distance란 표현보다 더 정확한 표현이다), 서적에서는 distance란 표현을 사용하기 때문에, 이를 그대로 사용할 것이다.

여기서, p(x) > 0 을 만족시키고 q(x) = 0 인 symbol x가 존재한다면, D(p||q) 는 무한대가 된다.

이제 앞에서 다뤘던 것처럼, 한 확률변수가 다른 확률변수에 대해 포함되는 정보의 양을 측정하는 지표가 되는 mutual information을 KL distance를 이용하여 나타낼 것이다.

PMF p(x,y) 와 한계 PMF p(x) 및 p(y) 를 갖는 두 확률변수 X와 Y를 고려해보자.
Mutual information I(X;Y) 는 결합분포 (joint distribution)와 곱 분포 (product distribution) p(x)p(y) 간의 relative entropy로 다음과 같이 정의된다.