15. 정보 이론(Information Theory)

이전 포스트에서 Maxwell의 악마에 대해서 언급했었습니다. 그러면서 열역학적인 엔트로피로 해결되지 않는 문제가 '정보'라는 개념에 의해서 정리된다고 이야기를 했었죠.

오늘은 정보가 무엇인지, 그리고 정보의 엔트로피가 어떻게 해석되는지에 대해서 알아보도록 하겠습니다.

---

정보와 Shannon의 엔트로피(information and Shannon's entropy)

먼저 정보가 무엇인지 논해보도록 하겠습니다. 정보의 사전적 정의는 관찰이나 측정을 통해서 주어진 문제를 해결하거나 판단할 수 있도록 정리된 지식이나 자료입니다. 이것은 너무 친숙한 개념이어서 쉽게 이해할 수 있습니다. 그러면 '정보가 많이 담겨있다'는 이야기를 수치적이고 정량적으로 나타내려면 어떻게 해야할까요?

그 부분에 답을 하기 위해서, 다음과 같은 예시를 들어보겠습니다. '아이작 뉴턴(Issac Newton)'에 대한 정보를 추론하는 것으로 시작해보도록 하죠.

위와 같이, 뉴턴의 생일에 대해 3가지의 참인 문장이 있습니다. 이 셋을 정보량으로 나누었을 때 정보가 가장 많은 것은 왠지 3번인 것 같습니다. 어느 정도 직감적으로 알 수 있죠.

정보량을 어떻게 정량화하는가에 대한 출발점은 위에서의 논지와 동일합니다. 어떤 정보를 받아들였을 때, 가장 적은 경우의 수로 줄이기 쉬워질수록 정보가 많다고 이야기를 할 수 있습니다. 직감적인 답안이었던 3번 문장을 선택하면, 열두달 중에서 하나로 특정 지을 수 있으므로 가능성의 변화를 제일 많이 줄일 수 있게 됩니다.

뉴턴의 생일이 가질 수 있는 전체 경우의 수는 365(윤년이라면 366이겠죠)입니다. 여기서 각 문장의 조건에 맞는 생일이 될 확률을 Pi 로 정의하면 각각의 조건에 대한 확률은 다음과 같이 됩니다.

첫번째 문장의 경우, 생일은 당연히 어떤 날을 의미하므로 명제를 만족할 확률은 항상 1 입니다. 그리고 두번째 문장의 경우, 1년을 크게 상반기와 하반기로 나누어 '하반기'에 존재할 것이라고 특정짓기 때문에 약 1/2이라고 볼 수 있죠. 그렇다고 해서 완벽히 1/2이라고 생각하면 오산입니다. 양력이 만들어지고 로마 제국의 황제였던 아우구스투스가 자신의 생일이 8월이었기에 8월에는 조금 더 많은 날짜가 있었다면 좋겠다고 생각했기에 2월의 마지막 날을 하나 떼왔기 때문이죠. 그래서 상반기의 날이 조금 더 적습니다.

마지막으로 세번째 문장의 경우, 25일이라는 조건은 1년 중 12일의 경우에만 참일 수 있는 문장입니다. 따라서 확률은 약 12/365입니다. 물론 이 역시도 완벽히 1/365라고 볼 수는 없습니다. 윤년이라면 마찬가지로 1/366이 되니까요.

따라서 확률과 정보량을 비교해보면, 다음과 같습니다.

1번째 확률은 1입니다. 그 소리는 우리가 뉴턴의 생일을 추정하는데 도움이 전혀 안된다는 것입니다. 2번째 확률은 1/2이고, 이는 절반의 확률로 맞을 수 있기 때문에 정보량이 존재하고, 3번째 확률 역시도 1이 아니기에 정보량을 가지게 됩니다. 상대적인 수치로 비교해본다면, 3번째 문장이 정보량이 조금 더 많다고 볼 수 있겠습니다.

만약 2번 조건과 3번 조건을 모두 만족하는 경우일 확률은, 두 사건이 서로 거의 독립이므로(상반기/하반기의 날짜 차이에 의해 완벽한 독립이지는 않습니다), 두 확률을 곱하면 됩니다.

따라서 우리는 확률과 정보량을 수치적으로 비교했을 때 어떤 문장을 만족할 확률이 0에 수렴할수록 정보량이 많다고 생각할 수 있습니다. 그러면 확률과 정보량이 반비례하는 느낌으로 생각하면 될 것 같네요.

그리고 두 정보가 더해지면 그러한 두 조건의 교집합을 만족시킬 확률은 곱으로 나타났습니다. 따라서 두 정보를 합치게 되면, 확률의 역수의 곱으로 나타납니다. 이러한 연산을 쉽게 만족시킬 수 있는 계산법은 뭐가 있을까요?

로그(log)를 이용하면 됩니다! 역수는 로그에다 (-)를 붙이면 해결되는 문제죠. 그래서, 어떤 문장에 대한 정보량 Q를 수학적으로 나타내면 다음과 같습니다.

k는 임의의 상수이되, 양수이기만 하면 됩니다. 정보의 scale을 조정하는 비례 상수라고 생각하면 되고, P는 위에서 언급했듯 무작위 확률 변수에 대해서 문장이 참이 될 확률을 의미하죠.

그러면 이제 기댓값, 즉 평균적인 정보량에 대한 논의도 할 수 있습니다.

는 얼마일까요?

위와 같이 계산을 거치면 (확률)*(확률의 로그값)의 전체 sum 형태로 나오게 되는데, 이것이 바로 Shannon의 엔트로피라고 불리게 되는 물리량입니다. 여기에 물리적인 의미를 담아서 정보 엔트로피라는 것이 무엇인지 생각해볼 수 있습니다.

제비뽑기를 한다고 합시다. 제비가 여러개 있는데, 서로 다른 벌칙이 한 개씩 적혀있죠. 이러한 경우 우리는 제비뽑기를 함으로써 어떤 벌칙을 당하게 될지 추정하기가 쉽지가 않습니다. 한 마디로 불확정도(uncertainty)가 큰 것 입니다. 이런 경우 정보 엔트로피가 큰 경우입니다.

하지만 반대로 제비뽑기를 하는데 단 한 가지의 제비를 제외한 모든 제비가 당첨 제비이고, 하나가 벌칙이 적혀있는 제비라고 합시다. 여기서 제비의 숫자가 정말 무수히 많아진다면, 우리는 직감적으로 '이 제비 뽑기는 시도 해볼만하다'라고 생각이 들거에요. 이런 경우는 불확정도가 작고, 정보 엔트로피 역시도 작습니다.

즉, 정보의 엔트로피는 물리적 불확정도와 연관지을 수 있는 개념이라는 것입니다.

다음의 예시를 보면서 확인해봅시다.

---

공평한 6면체 주사위를 고려해봅시다. 각 면이 가지는 정보 엔트로피는 얼마일까요? 먼저 정보량을 계산해보면 주사위의 한 면이 나올 확률은 1/6이므로, 정보량 Q는 k log 6을 가지게 됩니다.

이제 여기서 정보 엔트로피는 정보량의 기댓값

로 나타나므로, 각 확률과 로그값을 곱한 후 모든 눈금에 대해 sum을 해주면, 당연히 각 면의 정보량과 동일한 값(각 면의 정보량의 평균이므로)이 나옵니다. 이런 경우는 2진수 형태의 정보로 변환했을 때 2.58 bit가 나오게 됩니다(k = 1이라고 하고, 로그의 밑을 2로 계산하면 됩니다).

하지만, 1~5의 눈금이 나올 확률이 1/10이고, 6일 확률이 1/2인 경우의 불공평한 주사위를 가져다 놓고 다시 계산해봅시다. 이런 경우는 어떻게 달라질까요?

다시 각 눈금에 대한 정보량을 계산해보면 다음과 같습니다.

1~5의 면과 6이 적힌 눈금의 면의 정보량이 다르죠. 여기서 Shannon 엔트로피를 계산해보면

로, 약 2.16 bit가 나오게 됩니다. 이 소리는 정보의 엔트로피가 더 적다는 겁니다! 6으로 결정될 확률이 높은거니까요.

---

우리가 한참 전에 다루었던 Bernolli(베르누이) 시행을 가져와 봅시다. 베르누이 시행은 사건이 두 가지밖에 없는 경우입니다. 이런 경우의 Shannon 엔트로피는 다음과 같이 계산할 수 있습니다.

정보와 열역학(information and thermodynamics)

위에서 정보의 엔트로피가 물리적 불확정도와 연관 지을 수 있다고 했습니다. 그러면 이것을 열역학에도 연관을 지을 수 있습니다. 14장의 내용에서 엔트로피가 거시상태에 대응되는 미시상태의 상태수를 통해서 정의 될 수 있다고 하였죠.

미시상태는 우리가 관심없는(쉽게 말해서 고려하기 어려운, 알 수 없는거죠) 자유도에 대한 상태를 의미합니다. 알 수 없다는 것은 불확정도를 제공한다는 것입니다. 따라서 이러한 관점에서 정보 엔트로피가 도입될 수 있을 것입니다.

그래서, 열역학과 정보 이론은 서로 상호 보완적인 관계가 될 수 있습니다. 다음과 같은 예시를 보면 이해가 될 겁니다.

열역학에서의 '미시상태에 대한 불확정도'를 정보 엔트로피로 해석할 수 있고, 반대로 정보 이론을 열역학으로 해석하면 '저장되는 정보 자체가 물리적 매체에 저장되는 것이고, 저장한 것을 지우면서 열이 발생한다'고 연관시킬 수 있죠.

만약 N개 bit의 정보가 온도 T의 매체에 담겨 있고, 이 정보들을 모두 지운다고 생각해봅시다.

그러면 당연히 우주 전체의 엔트로피는 증가하거나 유지되는 경우 밖에 없으므로, 환경의 엔트로피는 매체에서 감소된 엔트로피만큼 증가해야 할 것 입니다(물론 이것은 이상적인 상황, 실질적으로는 동일한 양이 아니라 더 많이 증가할 것입니다).

따라서 환경은 정보를 제거하는 과정 중에 엔트로피가 증가하며 열을 공급받을 겁니다. 이 때 환경은 란다우어의 원리(Landauer's principle)에 의해 최소 값인 Nk**B**T ln 2 과 같거나 큰 양의 열을 흡수합니다. 이것이 14장에서 언급했던 Maxwell의 악마에 대한 해답을 주는 것입니다.

데이터 압축(data compression)

이번에는 데이터의 압축에 대해서 알아보도록 하겠습니다. 데이터를 다루는 과정은 보통 두가지로 나뉩니다. 부호화(encoding)과 복호화(decoding)이죠.

이 두 과정 모두 정보를 어떤 한 형태에서 다른 형태로 변환하는 과정을 의미합니다. 하지만 그 중에서도 일반적으로 부호화는 용량을 줄이면서 정보를 담는 것이고, 반대로 복호화는 원래의 상태로 복구하는 과정입니다.

예시를 들어보겠습니다. 2진수 데이터를 다음과 같이 부호화한다고 합시다.

이러한 규칙을 따르는 부호화 과정은 압축(compression)효과가 있을 수도 있고, 없을 수도 있으며 반대로 커질 수도 있습니다. 하지만 직관적으로 생각을 해보면, '00'이라는 문자열이 많이 존재한다면 충분히 압축효과가 발생할 것을 기대할 수 있습니다.

만약 n개의 비트열(bit column)이 있다면, 2진수 데이터라는 가정 하에서 1과 0으로 기술할 수 있습니다. 이때 특정 bit가 나올 확률(예를 들어 1)이 P라면 평균적으로 1은 nP개가 있으며, 반대로 0은 평균적으로 n(1-P)개가 있습니다. 그러므로 특정 비트열이 나올 확률은

로 근사할 수 있습니다. 여기서 양변에 로그를 취해봅시다.

그러면 로그값은(- 부호도 붙였습니다), nS로 쓸 수 있습니다. 이때 S는 베르누이 시행에서의 엔트로피였습니다! 양변에 지수를 취해 로그를 지워주면, 특정 비트열 (x1, x2, ..., xn)을 가질 확률은 1/2nS 로 나타나게 됩니다(독립 시행의 결과죠). 이를 통해 다음과 같은 성질을 갖는 것을 알 수 있습니다.

무손실 압축에 대한 이야기는, Shannon 정리로 이어지는 내용입니다. 자세한 내용은 링크를 참고하세요. 즉, S 값은 데이터의 압축 한계(compression limit)을 정의하게 됩니다.

양자 정보(quantum information)

*이 절은 양자역학을 수강하신 분들이 이해할 수 있는 내용입니다.*

양자역학에서의 대표되는 일반적인 개념은 불확정성입니다. 따라서 이러한 양자 계에도 정보의 개념을 적용할 수 있습니다. 이때, 밀도 행렬(density matrix)를 도입합니다.

밀도 행렬 ρ는 위와 같이 확률과 고유벡터(eigenfunction) psi의 외적을 통해 정의됩니다. 여기서 일반적인 양자 상태는 pure state라고 부르고, 불확정성이 섞여 있는 양자 상태는 mixed state라고 하죠. 이렇게 mixed state를 기술하기 위해 ρ를 사용합니다(밀도의 개념을 적용하는 것 자체가 어떤 불균일한 계를 평균적으로 취급하기 위해서라는 것을 감안하면, 어느정도 감이 잡히실 겁니다).

양자역학에서 어떤 행렬 A의 기댓값은 A와 밀도행렬의 곱의 대각합(Tr; Trace)과 같습니다(나머지 비대각성분들은 bra와 ket의 orthogonality에 의해서 사라집니다).

이때 밀도행렬의 대각합은 1이고, 밀도행렬의 제곱의 대각합은 1보다 작거나 같습니다. 만약 pure state라면 등호가 성립합니다.

예를 들어봅시다. 만약 3준위 상태의 계가 있다고 하고, 그 계의 밀도 행렬은 다음과 같이 나타납니다.

조건부 확률과 결합 확률(conditional and joint probabilities)

이번엔 조건부 확률과 결합 확률에 대해서 알아보겠습니다. 조건부 확률(conditional probability)은, 어떤 조건을 달고 발생할 확률입니다. 사건 A와 B가 있을 때, 사건 B가 일어났을 때 A가 일어날 확률을 의미하죠. 결합 확률(joint probability)는 두 사건 A, B가 동시에 일어날 확률을 의미합니다.

기호로는 다음과 같이 표시합니다.

결합 확률의 경우 두 사건의 교집합이 발생하는 경우로도 생각할 수 있죠! 조건부 확률과 결합 확률 사이의 관계는 다음과 같이 나타납니다.

이때 A와 B의 조건에 따라 달라질 수 있는데요, A와 B가 서로의 사건에 대해 영향을 끼치지 않는 독립 사건인 경우 두 확률의 곱이 결합 확률로 나타납니다.

그리고 A라는 사건이 1, 2, ... i 로 나누어지고, 이 각각의 경우가 배반 사건(exclusive event)이라면 하나의 사건이 발생함으로써 나머지 사건에 대한 발생을 제거합니다. 따라서 전체 index의 사건에 대한 합이 1이 되어야 하죠.

따라서, X라는 사건이 발생할 확률 P(X)는 다음과 같이 나타낼 수 있습니다.

베이즈 정리(Bayes theorem)

베이즈 정리는 위의 내용에서 이어지게 됩니다. P(A|B)*P(B) = P(B|A)*P(A)에서 양변을 P(B)로 나누어 봅시다.

그러면 P(A|B)에 대해서 하나의 식으로 정리가 됩니다. 이러한 원리를 베이즈 정리(Bayes theorem)이라고 합니다. 그리고 이러한 확률 사이의 관계를 이용하여 과학적 추론을 하는 것을 Bayesian inference라고 하죠.

앞으로 가설을 H(Hypothesis)로, 증거를 E(Evidence)로 표기하겠습니다. 그러면 베이즈 정리에 따라, P(H|E) (= 증거에 의한 가설이 옳을 확률)은 다음과 같이 정리할 수 있습니다.