엔트로피(Entropy) 이야기(3) - 섀넌

 

3. 섀넌의 엔트로피

(1) 배경

 1940년대 당시 벨 연구소의 가장 큰 고민은 전화와 전신(Telegraph)의 효율성이었다. 전선을 통해 신호를 보낼 때 ,거리가 멀어지면 항상 노이즈(Noise)가 섞였기 때문이다. 당시의 엔지니어들은 신호의 세기(Power)를 키우거나 전선을 더 굵게 만드는 물리적인 방법에만 매달렸지만 클로드 섀넌(Claude Shannon)은 물리적인 전기 신호가 아닌 그 신호가 담고 있는 '메시지의 논리적인 구조' 자체를 수학적으로 정의할 수는 없을지 고민했다.

 섀넌은 2차 세계대전 당시 암화화 통신 시스템을 연구했는데, 당시에 '잘 암호화된 메시지는 겉보기에 무작위한 노이즈와 구별할 수 없다'는 통찰을 하며 확률과 정보를 연결하는 결정적인 계기를 맞이했다. 즉, 메시지가 얼마나 '의외성'을 갖느냐가 곧 암호의 강도이자 정보의 양이라는 사실을 깨달은 것이다.

 

(2) 섀넌의 엔트로피 정의

섀넌의 엔트로피 정의는 다음과 같다.

 

$H = \displaystyle p_i \sum_{i=1}^{n} \log_{2} \dfrac{1}{p_i}$

 

식을 해석해보면

 

$p_i$ : $i$번째 정보가 나타날 확률

$\log_{2} \dfrac{1}{p_i}$ : $i$번째 정보가 갖는 정보량(의외성, 놀라움)

 

즉, 들어온 정보의 놀라운 정도의 가중 평균이다.

 

예시1) 메세지 'dog'의 엔트로피를 측정해보자. 우선, 편의를 위해 모든 알파벳이 등장할 확률은 위치에 상관없이 동일하다고 하자. 그러면 각각의 알파벳이 등장할 확률은 $p_i = \frac{1}{26}$이므로 엔트로피는 다음과 같다.

 

$H(\text{dog}) = 3 \cdot \left( \dfrac{1}{26} \log_{2} 26 \right) \approx 0.5424$

 

현실적으로 d 다음에 o가 나올 확률은 독립이 아닌 종속이므로 가장 잘 쳐줘봐야 d는 1/26의 확률로 등장하지만 o는 d에, g는 o와 d에 종속이어서 계산 결과는 다를 것이다.

 

보통 발생 가능성이 낮은 일이 일어나면 놀라므로 확률의 역수가 의외성이나 놀라운 정도를 표현하는 좋은 방법임은 확실하다. 다만 왜 하필 로그, 그것도 밑(base)가 2인 로그인지 알아보자.

 

(3) 섀넌이 엔트로피를 정의한 방법1

섀넌은 "어떤 정보가 얼마나 불확실한가"를 측정하기 위해 몇 가지 합리적인 조건을 세우고, 이를 만족하는 유일한 수식이 무엇인지 찾아내는 전통적인 수학의 접근법인 공리적 방법(Axiomatic Approach)을 택했다.(선형대수학에서 행렬식의 공식을 유도하는 과정도 공리적 방법이다) 따라서 그는 정보의 불확실성을 측정하는 함수가 만족해야 할 가장 기본적인 성질들을 공리(증명없이 '참'이라고 약속하는 명제) 약속로 정했다.

 

섀넌은 엔트로피 함수$H(p_1, p_2, \cdots, p_n)$이 다음의 세 가지 조건을 만족해야 한다고 가정했다.

 

① 연속성(Continuity) : 각 확률 $p_i$에 대해 함수 $H$는 연속이어야 한다.(확률이 미세하게 변하면 정보량도 미세하게 변해야 한다는 뜻)

② 단조 증가성(Monotonicity) : 모든 확률이 $1/n$으로 같을 때, 선택지 $n$이 많아질수록 $H$는 $n$에 대해 단조 증가해야 한다.(선택지가 많을수록 불확실성이 큼)

③ 재귀성/가법성(Grouping Property) : 정보를 묶어서 전달해도 전체 정보량의 합은 기존 정보량의 합과 같아야 한다.

 

위 공리들 아래 균등 확률 아래에서 유도해보자.

 

모든 사건의 확률이 $1/n$으로 동일한 경우, 이 때의 엔트로피를 $A(n) = H(1/n, \cdots, 1/n)$이라 정의하자.

 

재귀성 조건에 의해, 우리가 $n$개의 선택지를 가진 사건을 $k$번 독립 시행한다면, 전체 선택지의 수는 $n^k$개가 된다. 이때의 전체 정보량은 개별 정보량의 합과 같아야 하므로 다음과 같은 함수방정식을 얻는다.

 

$A(n^k) = k A(n)$

 

이 방정식을 만족하는 연속 함수는 수학적으로 로그 함수가  유일하다. 따라서 상수 $C$를 도입하면 다음과 같이 쓸 수 있다.

 

$A(n) = C \log n$

 

여기서 단조 증가성을 가지려면 상수 $C$는 양수이어야 한다. 여기서 섀넌은 물리적 엔트로피와 형태를 맞추기 위해 $C$대신 $K$를 사용하여 $K \log n$을 채택했다.

 

(4) 섀넌이 엔트로피를 정의한 방법2

이번에는 각각의 확률이 다를 수 있는 일반적인 상황에서 엔트로피를 유도해보자.

 

메세지의 놀라움의 척도(아니 이런 메세지가?)는 공 뽑기에서 놀라움의 척도(아니 이런 공을?)와 본질적으로 같으므로 공 뽑기 비유를 들어보겠다.

 

$N$개의 공이 들어있는 큰 박스가 하나 있다. 여기서 공을 하나 뽑은 후 놀라게 되는 정도를 $A(N)$이라 하자.

 

이번에는 큰 박스의 공들을 $k$개의 작은 박스들에 각각 $n_1, n_2, \cdots, n_k$개의 공들로 나누어 넣은 후에 공 뽑기를 시행해보자. 가법성 공리에 의해 $k$개의 작은 박스들에서 공을 뽑는 시행의 놀라움과 큰 박스 하나에서 공을 뽑는 시행의 놀라움은 같아야 한다.

 

그런데 $k$개의 박스들 중에서 공을 하나 뽑는 시행은 두가지 시행의 합이다.

 

① $k$개의 박스 중 공을 뽑을 박스를 선택하는 시행

② 선택한 박스에서 공을 뽑는 시행

 

그렇다면 다음과 같은 등식이 성립한다.

 

1개의 공을 큰 박스에서 꺼낸 후 놀라는 정도 = 박스 선택 후 놀라는 정도 + 각각의 박스에서의 놀라는 정도

 

1개의 공을 큰 박스에서 꺼낸 후 놀라는 정도가 $A(N)$

1개의 공을 꺼냈을 때, 각각의 박스가 선택되었을 놀라움의 정도는 $H(p_1, p_2, \cdots, p_k)$

1개의 공이 $i$번째 작은 박스에서 나왔을 때 놀라는 정도는 $p_i A(n_i)$

 

이다. 여기서 $p_i = \dfrac{n_i}{N}$이다. 따라서

 

$A(N) = H(p_1, p_2, \cdots, p_k) + \displaystyle \sum_{i=1}^{k} p_i A(n_i)$

 

가 성립한다. 이제 이 식을 정리해보자.

 

$H = \log N - \displaystyle \sum p_i \log n_i$

 

시그마를 합치기 위해 $\log N = \log N \cdot 1 = \log N \displaystyle \sum p_i = \sum p_i \log N$을 이용하면

 

$H = \displaystyle \sum p_i \log N - \sum p_i \log n_i = \sum p_i \log \dfrac{N}{n_i}$

 

이고 $p_i = \dfrac{n_i}{N}$이므로

 

$H = \displaystyle \sum p_i \log \dfrac{1}{p_i} = -\sum p_i \log p_i$

 

이다.

 

(5) 이름을 엔트로피로 지은 이유

섀넌은 정보나 불확실성 등의 다소 평범한 이름을 붙이려고 했으나 폰 노이만이 다음과 같은 두 가지 이유로 '엔트로피'를 추천해주었다.

 

① 수학적으로 일치하므로 (깁스의 엔트로피)

② 어려운 용어를 써야 논쟁에서 유리하기 때문

 

폰 노이만은 누구도 엔트로피를 제대로 알지 못하기 때문에 엔트로피라고 이름을 붙이면 바보들이 시비걸지 않을 것이라고 하며 조언을 했다고 한다.

 

(6) 로그의 밑을 $2$로 정한 이유

불확실성을 해소하는 가장 단순한 방법은 Yes/No 질문을 반복해서 던지는 것이다. 그래서 모든 정보는 2의 거듭제곱 수준의 질문 횟수 이내로 확실히 알아낼 수 있다. 섀넌은 두 가지 똑같은 확률(1/2)를 가진 선택지 중 하나를 결정할 때 필요한 정보량을 1 bit(Binary Digit의 줄임말)로 정의 후 1비트의 정보량을 가진 정보를 알아내기 위해 필요한 질문의 횟수가 1회라는 것에 착안하여 $\log_{2} 2 = 1$이 되도록 설계한 것이다.

 

(7) 예시2

영어 알파벳과 공백이 나타날 확률이 모두 같다고 하면 확률은 $p_i=1/27$이다. 만약 영어 알파벳과 공백을 하나씩 전송한다면 엔트로피는 $H_0 = \log_2 27 \approx 4.76 \text{bits/letter}$이다.

 

그런데, 실제 영어에서 e는 자주 나오지만 z나 q는 잘 나오지 않으므로 이런 빈도를 고려하여 다시 계산했더니 엔트로피는 $H_1 \approx 4.03 \text{bits/letter}$이었다.

 

여기서 더 나아가 문맥이 있기 때문에 q가 나오면 다음 글자는 거의 100%로 u가 나오고 th, he, in 조합도 흔하다. 이런 조건부 확률까지 고려하면 엔트로피는 $H_2 \approx 3.32 \text{bits/letter}$

 

섀넌은 실제로 사람이 문장을 예측하는 실험을 통해 영어의 진짜 엔트로피는 글자당 1.0에서 1.5비트 사이라는 결론을 내렸다. 즉, 영어는 75% 정도의 중복성을 가지고 있다는 것이다.