결합 엔트로피와 조건부 엔트로피(Joint and conditional entropy)

1948년 클로드 섀넌은 잡음 섞인 통로를 다루면서, 받은 신호를 보고 난 뒤에도 보낸 신호에 대해 남는 불확실성에 '모호도(equivocation)'라는 이름을 붙였습니다. 오늘날 조건부 엔트로피라 부르는 양입니다. 스무고개(예/아니오 질문을 스무 번까지 던져 답을 맞히는 놀이)로 생각하면 쉽습니다. 예/아니오 질문 하나는 많아야 1비트를 알려 주니, 엔트로피⁠(entropy)⁠가 H비트인 답을 맞히려면 평균 H번 이상 물어야 하고, 질문을 잘 고르면 H + 1번 미만으로 끝낼 수 있습니다. 그래서 엔트로피를 '평균 질문 수'의 잣대로 읽어도 됩니다. 이제 맞힐 것이 둘이라고 합시다. 오늘 날씨 X와 내일 날씨 Y입니다. 짝 (x, y) 하나하나를 결과로 보고 계산한 엔트로피가 결합 엔트로피⁠(joint entropy)⁠ H(X,Y), 곧 둘을 한꺼번에 맞히는 데 드는 질문 수의 잣대입니다. 오늘 날씨를 먼저 알아낸 다음 내일 날씨를 물을 수도 있습니다. 오늘 날씨가 x일 때 내일 날씨에 남은 불확실성 H(Y|X=x)를 오늘 날씨의 확률⁠(probability)⁠로 평균한 것이 조건부 엔트로피⁠(conditional entropy)⁠ H(Y|X)입니다.

$$H(X,Y) = -\sum_{x,y} p(x,y)\log_2 p(x,y), \qquad H(Y\mid X) = \sum_x p(x)\,H(Y\mid X{=}x)$$

어느 도시는 맑은 날의 비율이 이고, 나머지 날을 흐림과 비가 6 : 4로 나눕니다. 내일 날씨는 확률 로 오늘과 같고, 그렇지 않으면 이 기후에서 새로 정해집니다. d는 날씨가 이어지는 정도입니다.

왼쪽 표의 네모 넓이⁠(area)⁠가 결합 확률 p(오늘, 내일)입니다. 지금 오늘 날씨의 엔트로피는 H(X) = 비트, 오늘을 안 뒤 내일에 남는 엔트로피는 H(Y|X) = 비트이고, 둘의 합 비트는 결합 엔트로피 H(X,Y) = 비트와 꼭 같습니다. 이것이 엔트로피의 연쇄법칙입니다. 둘을 한꺼번에 맞히나, 오늘부터 맞히고 내일을 맞히나 엔트로피로 잰 질문 수는 같습니다. 식으로는 조건부 확률⁠(conditional probability)⁠의 곱셈 규칙 $p(x,y) = p(x)\,p(y\mid x)$에 $-\log_2$를 씌워 평균한 것뿐입니다. 곱이 합으로 바뀌는 것은 로그의 성질이지요.

d를 0으로 내리면 내일이 오늘과 무관해져서 H(Y|X) = H(Y)이고, 오른쪽의 첫 두 막대 높이가 같아집니다. 서로 독립⁠(independence)⁠인 두 변수의 결합 엔트로피는 각자의 엔트로피의 합입니다. d를 1로 올리면 내일은 오늘의 복사본이라 H(Y|X) = 0이고, 두 날을 맞히는 데 오늘 하나를 맞히는 만큼의 질문이면 됩니다. 첫 막대와 둘째 막대의 차 H(X) + H(Y) − H(X,Y)는 오늘이 내일에 대해 알려 주는 정보의 양, 곧 상호 정보량⁠(mutual information)⁠입니다.

무언가를 알면 불확실성은 평균적으로 줄거나 그대로입니다($H(Y\mid X) \le H(Y)$). 그런데 '평균적으로'가 중요합니다. 아래 그림은 오늘 날씨마다 내일 날씨에 남은 엔트로피를 막대 높이로, 그 날씨가 나올 확률을 막대 폭으로 그렸습니다. 그래서 막대 넓이의 합이 H(Y|X)입니다.

맑은 날이 흔한 도시에서는 내일도 맑으리라고 꽤 자신할 수 있는데, 오늘 비가 왔다는 소식은 그 자신감을 흔듭니다. 그런 날은 드물어서 막대가 좁고, 맑은 날의 확신이 넓은 폭으로 이를 덮기 때문에 평균은 H(Y) 아래에 머뭅니다. 맑은 날 비율을 올려 볼수록 이 역전이 뚜렷해집니다. 일기예보도 마찬가지입니다. 비 오는 날이 10%인 도시에서 내일 비가 올지의 엔트로피는 0.469비트입니다. 예보가 15%의 날에 비를 말하고 그때 실제로 반반의 확률로 비가 온다면, 예보를 들은 그날의 불확실성은 1비트로 오히려 커집니다. 그러나 나머지 85%의 날에는 비 올 확률이 2.9%로 내려가 불확실성이 0.191비트가 되므로, 예보를 들은 뒤의 평균은 0.313비트로 줄어듭니다.

조건부 엔트로피는 방향이 있습니다. 주사위 눈 X를 알면 홀짝 Y는 확실하니 H(Y|X) = 0이지만, 홀짝을 알아도 눈은 세 가지가 남아 $H(X\mid Y) = \log_2 3 \approx 1.585$비트입니다. 위 도시에서는 오늘과 내일의 분포가 같게 만들어 두어서 두 방향이 같을 뿐입니다. 연쇄법칙은 변수가 여럿이어도 성립합니다. $H(X_1,\ldots,X_n) = \sum_i H(X_i\mid X_1,\ldots,X_{i-1})$이므로 글 전체의 엔트로피는 '앞 글자들을 알 때 다음 글자의 엔트로피'를 차례로 더한 것이고, 앞을 더 많이 볼수록 각 항은 줄거나 그대로입니다. 앞 n − 1글자만 보고 다음 글자를 맞히는 n-그램⁠(n-gram)⁠ 모형은 이 조건부 엔트로피를 문맥을 n − 1글자로 잘라 어림합니다. 섀넌은 1948년 논문에서 $H(X,Y) \le H(X) + H(Y)$, $H(X,Y) = H(X) + H(Y\mid X)$, $H(Y\mid X) \le H(Y)$를 이미 한데 정리해 두었습니다.

이어지는 곳. 오늘이 내일을 정하는 규칙이 이 그림처럼 이어지는 과정이 마르코프 연쇄⁠(Markov chain)⁠이고, 정상 분포(이 그림에서는 기후)에서 출발했다면 한 걸음마다 새로 생기는 불확실성 H(X_n+1|X_n)이 그 엔트로피율입니다. 엔트로피율⁠(entropy rate)⁠은 원천 부호화 정리⁠(source coding theorem)⁠에서 압축의 한계가 되고, 앞 기호를 문맥으로 쓰는 산술 부호화⁠(arithmetic coding)⁠나 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠이 그 한계에 다가갑니다. X를 알아서 줄어든 불확실성 H(Y) − H(Y|X)가 상호 정보량입니다. 잡음 통로⁠(noisy channel)⁠에서 보낸 신호의 불확실성 H(X)에서 모호도 H(X|Y)를 뺀 이 양을, 입력 분포를 바꿔 가며 가장 크게 만든 값이 통로 용량⁠(channel capacity)⁠입니다. 틀린 분포를 믿을 때 치르는 비용을 재는 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠으로도 같은 양들을 다시 쓸 수 있고, 은닉 마르코프 모델⁠(hidden Markov model)⁠은 보이지 않는 상태를 관측으로부터 추정할 때 이 조건부 구조를 그대로 씁니다. 질문 하나로 후보를 절반으로 줄이는 이진 탐색⁠(binary search)⁠은 스무고개 그대로이고, 허프만 부호⁠(Huffman coding)⁠의 나무는 갈림길 하나하나가 예/아니오 질문 하나인 스무고개 전략표로, 평균 질문 수를 가장 적게 하는 전략입니다.