엔트로피로 불리는 평균 정보량(Entropy as Mean Information Content)

[경고] 아래 글을 읽지 않고 "엔트로피로 불리는 평균 정보량"을 보면 바보로 느껴질 수 있습니다.

1. 재미나는 정보량의 정의

[그림 1] 동전 던지기의 확률 변수 $X$에 대한 엔트로피 $H(X)$(출처: wikipedia.org)

사건 확률을 정의한 다음에 평균(mean)을 써서 특정 사건 $E$의 특성을 정량화하는 방식처럼, 정보량 $I(X)$를 가지고 평균을 구하고 이를 정보의 엔트로피(entropy) $H(X)$로 이름 붙인다. 섀넌Claude Elwood Shannon(1916–2001)의 제안을 명확히 하기 위해 섀넌 엔트로피(Shannon entropy)로 부르기도 한다.

                          (1)

여기서 $X$는 사건 $E$의 이산 확률 변수(discrete random variable)이며 그 확률은 $p_i$ = $\mathrm{Pr}[X=x_i]$, $h(p)$는 확률 $p$에 대한 엔트로피 성분(entropy component)이다. 엔트로피에 $H$를 쓴 이유는 에타(eta) $\eta$의 대문자가 H이기 때문이다.

우리가 통신을 하는 목적은 정보원(information source)에서 많은 정보를 얻기 위함이다. 정보량은 확률과 로그 함수로 쉽게 정의하지만, 정보량만으로 최대 정보를 얻는 방법을 고안하기는 어려워서 식 (1)로 만든 엔트로피를 사용한다. 예를 들면, 정보원이 가진 원천 알파벳(source alphabet) $S$의 기호(symbol) $s_i$의 발생 확률(probability of occurrence) 혹은 발생 빈도수(frequency of occurrence)를 고려해서 엔트로피 $H(S)$가 최대가 되도록 부호화를 하면, 수신원에서 최대의 정보를 획득할 수 있다. 여기서 원천 알파벳은 $S$ = $\{s_1,s_2,\cdots \}$처럼 정보원이 쓰는 기호를 모두 모은 집합이다. 식 (1)처럼 엔트로피는 평균 정보량(mean information content)이기 때문에, 평균 정보량이 최대가 되도록 원천 알파벳을 구성하면 수신원은 평균적으로 많은 정보를 정보원으로부터 얻을 수 있다.

[그림 2] 엔트로피 성분 $h(p)$의 변화

평균 정보량의 최대값으로부터 평균 정보량을 물리학의 엔트로피로 부르는 이유를 파악할 수 있다. 먼저 엔트로피를 구성하는 엔트로피 성분 $h(p)$의 성질부터 분석한다. 극단적인 $p$ = $0$과 $1$에서 $h(p)$ = $0$이다. 계산이 잘 안되는 $p$ = $0$인 경우는 로피탈의 규칙(L'Hopital's rule)을 써서 $\underset{p\to 0}{lim}h(p)$ = $-1/\log 2\cdot \underset{p\to 0}{lim}\log p/(1/p)$ = $1/\log 2\cdot \underset{p\to 0}{lim}(1/p)/(1/p^2)$ = $0$을 얻는다. 또한 $h(p)$의 변화 특성은 $dh(p)/dp$로 확인한다.

                          (2)

그러면 기울기에 따라 $h(p)$는 ↗↘로 변하며 $p$ = $1/e$ = 0.367879$\cdots$에서 $h(p)$는 최대값 ${\log }_{2}e/e$ = 0.5307378$\cdots$을 가진다. 이로 인해 $p$ = $0,1$을 제외한 확률에서는 항상 0보다 크다.

[그림 2]를 참고하면 엔트로피의 하한은 분명 $H(X)\ge 0$이다. 그러나 엔트로피의 상한은 쉽게 구해지지 않으므로, [그림 1]과 같은 베르누이 시행(Bernoulli trial)의 엔트로피 $H(X)$로 상한을 유추한다.

                          (3a)

여기서 $p$는 베르누이 시행이 성공하는 확률이다. 식 (3a)의 미분 $dH(X)/dp$는 식 (2)로 쉽게 구한다.

                          (3b)

따라서 $h(p)$처럼 $H(X)$도 ↗↘ 모양으로 변화한다. [그림 1]의 그래프가 명확히 보여주듯이 $H(X)$의 최대값은 $p$ = $1/2$에서 ${\log }_{2}2$ = $1$로 나온다. 이상의 관찰을 바탕으로 엔트로피의 최대값과 최소값을 증명한다.

[엔트로피의 최대와 최소(maximum and minimum of entropy)]

                         (4)

여기서 $n$은 사건 개수, 엔트로피의 최대값은 균등 분포(uniform distribution)인 $p_i$ = $1/n$에서 발생한다.

[증명]
엔트로피 성분 $h(p)$는 항상 0보다 크거나 같아서 엔트로피의 최소값이 0임은 명백하다. 엔트로피의 최대값을 증명하기 위해 기브스의 부등식(Gibbs's inequality)을 활용한다. 이를 위해 $f(X)$ = $H(X)-{\log }_{2}n$을 정의해서 기브스의 부등식 형태로 만든다.

                          (5)

따라서 엔트로피는 ${\log }_{2}n$을 넘어설 수 없다.

______________________________

[그림 3] 입자가 무작위로 퍼져서 엔트로피가 증가한 모습(출처: wikipedia.org)

함수 $H(X)$가 최대가 되는 순간은 모든 사건 원소가 같은 확률인 $1/n$으로 구성되는 경우이다. 열 역학(thermodynamics)의 엔트로피는 경향성을 가지지 않고 무작위로 흩어질 때 최대가 된다는 성질과 식 (5)의 결과가 동일하기 때문에 $H(X)$를 정보의 엔트로피로 개념화한다.

엔트로피는 원천 부호화(source coding)의 한계를 나타내는 유용한 지표이다. 원천 부호화는 정보원이 만들어내는 기호(symbol)를 특정한 진법을 가진 부호(code)로 바꾸는 과정이다. 기호 원소 $s_i$를 담은 집합은 원천 알파벳(source alphabet) $S$ = $\{s_1,s_2,\cdots \}$가 되고, 부호 $c_i$를 원소로 하는 집합은 부호 알파벳(code alphabet) $C$ = $\{c_1,c_2,\cdots \}$로 부른다. 예를 들어, 이진 부호(binary code) 혹은 간단히 이진수(binary number)의 부호 알파벳은 $C$ = $\{c_1,c_2\}$ = $\{0,1\}$이다.

[표 1] 4가지 기호(symbol)를 표현하는 부호어(codeword)의 구성 체계

기호 $s_i$ (Symbol)	발생 확률 $p_i$	고정 길이 부호 $W_1$ (유일 부호)	부호어 길이 $l_i$	가변 길이 부호 $W_2$ (유일 부호, 순시 부호)	가변 길이 부호 $W_3$ (유일 부호)
$s_1$	1/2	00	1	0	0
$s_2$	1/4	01	2	10	01
$s_3$	1/5	10	3	110	011
$s_4$	1/20	11	3	111	111

원천 부호화를 이해하기 위해 [표 1]처럼 4가지 기호를 가진 원천 알파벳 $S$ = $\{s_1,s_2,s_3,s_4\}$를 이진 부호 $C$ = $\{0,1\}$로 나타내본다. 기호가 4개라서 이진수로 4가지를 표현하는 2비트 부호를 $s_1$ = $00$, $s_2$ = $01$, $s_3$ = $10$, $s_4$ = $11$처럼 선택할 수 있다. 이는 각 기호의 발생 확률이 동일하다고 가정하는 고정 길이 부호(fixed-length code)에 대한 엔트로피의 최대값인 $H(S)$ = ${\log }_{2}4$ = $2$비트가 된다. 고정 길이 부호는 각 기호에 배정된 기호 개수가 변하지 않아서 붙여진 이름이며, 부호 모임이 블록을 이루어서 블록 부호(block code)라 할 수도 있다. 각 기호에 대응하는 부호 모임은 부호어(codeword)라 이름 붙인다. 현재 원천 부호화에서 $s_2$의 부호어는 $01$이다. 다른 관점으로 $s_i$의 발생 확률이 다르면 기호마다 부호 길이를 다르게 주는 가변 길이 부호(variable-length code)를 써서 평균 부호어 길이(average codeword length) $L$을 고정 길이 부호보다 더 짧게 만들 수 있다. 예를 들어, $s_i$의 발생 확률 $p_i$가 $p_1$ = $1/2$, $p_2$ = $1/4$, $p_3$ = $1/5$, $p_4$ = $1/20$으로 주어진다. 그러면 각 $s_i$에 부호어 길이(codeword length) $l_i$를 [표 1]처럼 배정한다. 여기서 부호어 길이는 정보량(information content)에 가깝게 선택한다. 따라서 [표 1]의 $W_2,W_3$ 부호 체계에 대한 평균 부호어 길이는 $L$ = 1.75비트, 엔트로피는 $H(S)$ = 1.68비트로 나온다.

                          (6)

다만 부호화(encoding)를 할 때는 복호화(decoding)를 반드시 고려해야 한다. 예를 들어 [표 1]과 같이 가변 길이 부호를 구성하지 않고 $s_1$ = $0$, $s_2$ = $1$, $s_3$ = $10$, $s_4$ = $11$으로 해도 부호화가 가능하다. 평균 부호어 길이도  $L$ = 1.25비트로 [표 1]보다 훨씬 짧아진다. 하지만 이런 부호 체계는 복호화에 문제가 생긴다. 가령 부호어가 $11$로 들어온 경우에 2개의 $s_2$인지 혹은 하나의 $s_4$인지 구별되지 않는다. 그래서 부호화를 할 때는 복호화가 유일하게 되도록 유일 복호화(unique decoding)를 지향해야 한다. 유일 복호화가 되는 부호는 유일 부호(unique code or uniquely decodable code)가 된다.

유일 복호화의 성질을 더 명확히 파악하기 위해, 정보원에서 수신원으로 정보가 전달되는 과정을 수학적으로 표현한다. 이진 부호화의 경우에 수신원에 들어오는 이진 수열은 0, 1로만 구성된다. 이 이진 수열을 복호화한다는 의미는 이진수로부터 기호를 찾아내서 $s_i{s}_j{s}_k{s}_l\cdots$처럼 나열한다는 뜻이다. 이런 기호의 나열에는 부호의 $n$차 확장($n$th extension of code)이란 명칭이 붙어있다. 부호의 $n$차 확장은 수신된 원천 부호(source code)를 적당히 병합(concatenation)하여 부호어를 만든 후 대응되는 원천 알파벳의 기호 $n$개를 일렬로 배치한 형태를 이른다. 원천 알파벳 $S$ = $\{s_1,s_2,\cdots ,s_q\}$의 원소 개수가 $q$라면 $n$차 확장에 대한 경우의 수는 $q^n$이 된다. 따라서 부호 체계가 유일 복호화 가능이라는 말은 임의로 선택한 원천 부호와 그 $n$차 확장이 항상 일대일 대응(one-to-one mapping)함으로 바꾸어 쓸 수 있다. 이를테면, [표 1]의 고정 길이 부호 혹은 블록 부호 $W_1$을 가정하면 수신열 $0110110011$의 $n$차 확장은 5차인 $s_2{s}_3{s}_4{s}_1{s}_4$만 가능해서 이 부호 체계는 유일 복호화 성질이 있다. 이처럼 정상적으로 배정된 고정 길이 부호는 모두 유일 부호에 속한다. 반면에 $s_1$ = $0$, $s_2$ = $1$, $s_3$ = $10$, $s_4$ = $11$인 부호 체계에서는 $n$차 확장이 7차인 $s_1{s}_2{s}_3{s}_4{s}_1{s}_1{s}_4$, 9차인 $s_1{s}_2{s}_2{s}_1{s}_4{s}_1{s}_1{s}_2{s}_2$ 등으로 다양하게 생길 수 있어서 유일 복호화가 되지 않는다.

(a) 유일 부호(unique code)이며 순시 부호(instantaneous code)

(b) 유일 부호이지만 비순시 부호(non-instantaneous code)

[그림 4] 복호화 트리로 그린 순시와 비순시 부호의 예시

나열된 부호를 확장할 때, 각 부호어가 그 뒤에 나오는 부호와 관계없이 복호되는 부호를 순시 부호(instantaneous code)라 한다. [표 1]에서 부호어 체계 $W_2$는 순시 부호이지만 $W_3$는 순시 부호가 되지 않는다. 이를 판단하기에 좋은 도구는 [그림 4]에 보인 복호화 트리(decoding tree)이다. 복호화 트리에서 그 다음에 나오는 분기(branch)에 상관없이 원천 알파벳의 기호가 결정되어야 [그림 4(a)]와 같은 순시 부호가 된다. 순시 부호를 정의하는 복호화 트리가 있어서 순시 부호는 자동적으로 유일 부호가 된다. 부호어 체계 $W_3$는 기호를 지정할 때 그뒤의 분기까지 고려해야 유일하게 기호가 정해지기 때문에, [그림 4(b)]처럼 순시가 아닌 비순시 부호(non-instantaneous code)로 판정된다. 복호화 트리를 쓰지 않고 순시와 비순시 부호를 구분하려면 부호어의 접두사(prefix)도 유용하다. 부호어 체계 $W_2$는 어떤 부호어의 접두사든지 다른 부호어의 접두사가 되지 않는다. 그러나 $W_3$는 반복되는 접두사가 $0$, $01$이 있어서 현재 분기까지만 봐서는 복화하가 되지 않는다. 예를 들면, $s_1,s_2,s_3$는 접두사가 $0$으로 같고, $s_2,s_3$는 동일한 $01$ 접두사가 있다. 이러한 이유로 순시 부호를 접두사 부호(prefix code)로 명하기도 한다. 주어진 부호어 길이 선택에 대해 순시 부호가 존재하는지를 알려주는 관계식으로 크래프트 부등식(Kraft inequality) 혹은 크래프트–맥밀런 부등식(Kraft–McMillan inequality)이 있다[2].

[참고문헌]

[1] C. E. Shannon, "A mathematical theory of communication", Bell System Tech. J., vol. 27, pp. 379–423, 623–656, Jul., Oct. 1948.

[2] L. G. Kraft, A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses, M.S. Thesis, MIT, MA, USA, 1949.