Mathematics | Information Theory | Entropy, Information

References

• Elements of Information Theory (Thomas M. Cover) - Chapter 2

---

정보 (a measure of information)

정보의 양을 측정하고자 하는 시도는 통신에서 시작됐다. 통신에서 한 채널은 특정 time frame에 0 또는 1의 binary 정보만을 담고 있다. 같은 정보여도 0101..의 인코딩을 효율적으로 하여 채널 점유를 최소화하는 문제를 풀어야 했다. 얼마나 최소화할 수 있을까? 이 방법이 저 방법보다 효율적일까?에 대한 질문에 답하기 위해 정보를 측정할 필요가 있었다. 수학적으로 정의하기 이전에 아래 예시를 살펴보자.

점심 메뉴 예측

신입이 회식 메뉴를 결정해야 하는 상황이다. 신입은 부장이 먹고 싶은 메뉴를 맞춰서 부장을 감동시키고자 한다. 신입은 부장에게 먹고 싶은 메뉴가 무엇인지 yes/no 질문을 할 수 있다. 부장은 이 질문을 적게 받을 수록 더 감동한다고 한다. 신입은 부장 B가 햄버거 또는 피자를 같은 확률로 먹을 것이라는 정보를 알고 있다. 회식을 100만 번 한다고 했을 때, 신입은 부장이 먹고 싶은 음식을 확정하기 위해 평균 몇 번의 질문을 해야 할까? 답은 1번이다. 당연한 결과이다. 그러면 부장 B의 메뉴 취향은 1 bit의 sequence로 표현할 수 있다. 다음 예시도 살펴보자.

이번엔 상무 C와 같이 회식을 할 일이 생겼다. 상무 C는 메뉴가 아니라 브랜드까지 맞춰야 한다. 회식을 100만 번 한다고 했을 때, 상무 C를 최대한 감동시키려면 평균 질문을 몇 번 해야 할까? 답은 2번이다. 위 그림과 같이 각 브랜드에 $\{00, 01, 10, 11\}$을 인코딩 해주면 질문을 "1. 혹시 앞자리가 $0$이세요? 2. 뒷자리가 $0$이세요?"의 두 개만 하면 되기 때문이다. 따라서 상무 C의 메뉴 취향은 2bit의 sequence로 표현할 수 있다. 예시를 하나 더 보자.

어느날 버거킹과 맥도날드가 "(주)맥킹"으로 합병을 했다. 그럼 상무 C의 메뉴 취향을 맞추기 좀 더 쉬워질 것이다. 이 때는 평균 몇 번 질문을 해야 할까? 답은 $1.5$ 번이다. 질문을 "1. 앞자리가 $0$이세요?(=햄버거세요?) 2. 뒷자리가 $0$이세요?(=도미노세요?)"로 구성한다고 해보자. 그러면 $1/2$의 확률로 맥킹을 고를 것이기에 회식의 $1/2$은 질문을 한 번 하는 것으로 끝날 것이다. 도미노와 BHC가 먹고 싶다면 각각 질문을 2개 해야 하기 때문에 $1/4+1/4$의 확률로 2개의 질문이 필요하다. 따라서 $1/2 \times 1 + (1/4 + 1/4) \times 2 = 1.5 \text{ bits}$이다.

 

버거킹과 맥도날드가 합병하면서, 메뉴를 맞추기 위한 난이도가 낮아짐(느낌상으로)과 동시에 필요한 질문의 수가 줄어들었음(수치상으로)을 알 수 있다. 이때 필요한 질문의 수를 엔트로피(entropy)라 하고 이 엔트로피를 줄이는 것을 정보(information)라 한다. 위에서는 버거킹과 맥도날드가 합병했다는 정보가 "버거킹이세요?", "맥도날드세요?"라는 질문을 "햄버거세요?"라는 질문으로 줄여줬다. 평균 질문 수가 2개에서 1.5개로 0.5개 감소했으므로 합병정보는 0.5 bit의 정보를 담고 있다고 할 수 있다.

수학적 정의

• $X$: 랜덤변수
• $\mathcal{X}$: alphabet of $X$ ($X$가 가질 수 있는 값들의 집합)
• $p(x):=p_X(x)$: pmf

$X \sim p(x)$라 하자. 그러면 이때 랜덤변수 $X$의 엔트로피는
$$H(X) = -\sum_{x\in \mathcal{X}} p(x)\log p(x)$$이다. 단위는 bit이고 로그의 밑은 $2$이다. 로그의 밑인 $2$는 yes/no 질문의 선택지 yes, no의 $2$개를 나타낸다. (질문의 선택지 개수를 늘리면 다른 밑을 쓰면 된다.) 위의 마지막 상황에서의 엔트로피를 구해보면 1.5 bit로 메뉴 확정을 위해 필요한 질문 개수와 동일하다. 엔트로피는 랜덤변수의 uncertainty를 측정하는 척도 중 하나로써 사용된다. 이 식은 열역학에서의 엔트로피의 식과 로그의 밑만 다를 뿐 정확히 일치한다. 그리고 여러 가지 성질들이 소름돋을 정도로 닮았다. 때문에 이 식에도 엔트로피라는 이름이 붙게 됐다.

 

Example 1
$$X = \left \{ \begin{array}{ll} 1, & \text{with probability } p \\ 0, & \text{with probability } 1-p \end{array} \right .$$

이면 $H(X) = -p\log p - (1-p) \log(1-p)$이다. 그래프를 그리면 아래와 같다. 

$p = 0.5$일 때 최댓값 $1$을 가진다. 모든 선택지의 확률이 똑같으면 뭘 고를지 전혀 예측할 수 없기 떄문에 $X$를 알아내기 위해 질문을 무조건 1개 해야 하기 때문이다. 반대로 $p=0$이거나 $p=1$이면 질문을 할 필요가 없다. 이때 $H(X)=0$이므로 합당한 비유라 할 수 있다. (편의상 $0\log 0 =0$으로 놓는다.)

선택지가 3개인 경우도 똑같다