이 포스트는 제가 공부하면서 정리 목적으로 작성한 것입니다. 너무 기본적인 내용은 포함되어 있지 않으며 혼란스러울 만한 부분(특히 저에게)의 내용 위주로 정리하는 것이 목적입니다. 엄밀하거나 깊이 있게 내용을 다루지 않을 수 있으며, 잘못된 내용이 포함되어 있을 수 있습니다. 혹시 해당 내용을 발견해주신다면 메일로 알려주시면 감사하겠습니다!
What is information?
천재적인 수학자 섀넌은 정보에 관한 아래 성질을 관찰했습니다.
낮은 확률일수록 더 많은 정보를 가지고 있다.
즉, 확률이 아주 높은 사건이라면 발생해도 적은 정보만을 제공합니다. 리그 전승 중인 팀이 리그에서 전패 중인 팀을 만나서 이겼다는 소식을 들어도 새로 얻는 정보는 거의 없습니다. 반대로 전패 중이던 팀이 승리했단 소식이나 T1과 징동의 대결 같은 흥미진진한 결과는 많은 정보를 포함하고 있습니다. 다만 이 개념은 정보의 ‘가치’와는 다른 것입니다. 요지는, 일어날 일이 낮은 사건일수록 많은 정보를 포함하고 있다는 것입니다.
현대 정보이론의 근간을 만든 섀넌이 정의하는 정보는 직관적이면서도 조금만 수식이 복잡해도 혼란스러울 때도 많습니다. 특히 양자 상태에서의 정보량을 설명하는 폰 노인만 엔트로피로 간다면 더더욱 이해하기 어려워집니다. 저도 공부하다가 너무 어려워서 왜 정보가 엔트로피라고 불리는지, 왜 로그를 사용하는지, 조건부 엔트로피란 무엇이며 Mutual Information이란 무엇인지 등등을 차근차근 정리해보려고 합니다. 본 내용은 Quantum Computing and Quantum Information 책의 11, 12장 내용과 연관되어 있습니다.
Shannon Entropy
확률변수 X의 확률분포가 $p_1, p_2, … , p_n$이라 하자. 이때 확률변수 X의 Shannon entropy는 아래와 같이 정의된다. 편하게 X가 가지고 있는 정보량이라고 이해하자.
\[H(X) = H(p_1, p_2, ... , p_n) = -\sum_{x}p_xlogp_x\]만약 X의 확률분포가 {0.7, 0.15, 0.1, 0.05} 라면 H(X) = 1.319 입니다. 이제 특이한 점을 살펴봅시다.
1. 왜 로그를 사용하는가
컴퓨터에서 다루는 정보의 최소량인 1bit는 0 또는 1의 두 가지 상태를 나타낼 수 있습니다. 비트가 늘어나 2bit가 되면 00, 01, 10, 11의 4가지 상태를 나타낼 수 있습니다. 이런 식으로 n개의 비트는 $2^n$ 가지의 경우를 표현할 수 있습니다.
거꾸로, 가능한 결과값이 n개인 상태를 표현하기 위해서는 몇 비트가 필요할까요? (모든 상태가 일어날 확률은 같다고 가정합시다)
앞에서 h개의 비트가 $2^h$가지의 경우를 표현할 수 있으므로 거꾸로 생각해 보면 필요한 비트 수는 $h=log_2{n}$ 임을 쉽게 알 수 있습니다. 앞으로 여기서 사용하는 모든 log는 밑이 2인 로그입니다.
오로지 직관으로만 생각해 봅시다. 나타날 확률이 1/10인 상태는 발생 확률이 모두 동일한 결과값을 10개 가진 상태에 대응됩니다. 따라서 log10과 같으며, 이 값은 $log(1/p) = -log(p)$ 임을 쉽게 알 수 있습니다. 이 결과는 Shannon Entropy 식에서도 확인 가능합니다.
2. 왜 정보량에 기댓값 개념이 들어갈까
섀넌의 엔트로피 식을 들여다 본다면 앞서 설명한 log값에 더해 기댓값 개념이 들어가 있다는 것을 확인 가능합니다.
한번 생각해 봅시다. 어떤 상태가 90%확률로 10bit로 표현되고, 10%확률로 100bit로 표현된다면 실제로 컴퓨터에서 완벽하게 이 값을 담기 위해서는 최악의 경우를 상정하여 100bit를 준비해야 합니다. 그럼에도 Shannon Entropy는 위 상태가 오직 $0.9 \times 10 + 0.1 \times 100 = 19bit$ 만큼의 정보만 가지고 있다고 합니다. 왜 그럴까요?
이는 정보량을 받아들이는 관점의 차이 때문입니다. Shannon Entropy는 상태 그 자체의 본질적인 정보량을 구하는 것이 목적입니다. 한번 직관적으로 생각해 봅시다. 0.00001%의 확률로 발생하는 사건이 있다면 그 경우의 정보량은 대단히 많겠지만, 최종적인 엔트로피에는 크게 변화를 주지 못해야 합니다. 즉 확률변수의 각 사건들은 발생할 확률에 비례하여 엔트로피에 반영되어야 합니다.
로그와 기댓값 개념을 자연스럽게 적용시킨 식이 바로 Shannon Entropy이다.
Shannon’s Theorem
우선 typical sequences가 무엇인지부터 정의해야 합니다.