[컴] 정보이론에서 entropy

information theory

정보이론에서 entropy

자세한 이야기는 ref. 1, 2, 3 을 통해 배우자.

모든 사건이 같은 확률로 일어나는 것이 가장 불확실하다.즉, 랜덤하게 사건이 일어나는 것이 제일 확실하다. 예를 들어, 우리가 동전던지기를 한다고 했을 때도, 한번은 앞면, 다른 한번은 뒷면, 이렇게 계속 ’앞뒤앞뒤’로 나오는 것이 가장 불확실하다.

’엔트로피(entropy)’는 이 불확실한 정도를 이야기 한다. 즉,

• 사건이 랜덤하게 일어나는 경우
  –> 각 사건이 발생하는 확률이 random하다.
  –> 제일 확실한 경우이다.
  –> 불확실성이 낮다.
  –> entropy 값이 가장 낮다.
• 사건이 규칙적으로 일어나는 경우
  –> 각 사건이 발생하는 확률이 다 같다.
  –> 제일 불확실한 경우이다.
  –> 불확실성이 높다.
  –> entropy 값이 가장 높게 된다.

entropy 란, 최적의 전략하에서 그 사건을 예측하는 데에 필요한 질문 개수를 의미한다.
이 말은 곧 최적의 전략 하에서 필요한 질문개수에 대한 기댓값을 구하면 된다는 뜻이다.
entropy 가 감소한다는 것은 우리가 그 사건을 맞히기 위해 필요한 질문의 개수가 줄어든다는 이야기다.

위의 사건이 발생하는 경우와 연관지어서 이야기해보면,

• 사건의 발생확률이 한쪽으로 몰려있다.
  --> 필요한 질문 개수의 평균은 줄어들게 된다.
  --> 적은 질문으로 어떤 사건이 일어날 지 맞출 수 있기 때문이다.
  --> 그 사건을 예측하는데 필요한 질문 개수가 작다

만약 아래와 같은 이산확률분포(discrete probability distribution)가 있다고 하자.

• A 가 나오는 확률은 50% = 1/2
• B 가 나오는 확률은 12.5% = 1/8
• C 가 나오는 확률은 12.5% = 1/8
• D 가 나오는 확률은 25% = 1/4

그러면, 처음에 나오는 문자가 뭔지를 알려면 몇번의 질문을 해야 할까? 이것에 대한 자세한 설명은 ref. 1 을 보면 된다.

결과적으로, 아래처럼 1개의 글자를 추려내기 위해서는 평균적으로 1.75개의 질문을 하면 된다는 결론이 난다.

\(p(A) \cdot 1 + p(B) \cdot 3 + p(C) \cdot 3 + p(D) \cdot 2 = 1.75\)

각 문자를 판단하기 위해 하는 질문횟수는 다음과 같다.

• A는 1번 : \(\log_2(\frac{1}{1/2})\)
• B는 3번 : \(\log_2(\frac{1}{1/8})\)
• C는 3번 : \(\log_2(\frac{1}{1/8})\)
• D는 2번 : \(\log_2(\frac{1}{1/4})\)

즉, 아래와 같은 식이 성립한다.

\((사건발생확률) \cdot log_{2}(\frac{1}{사건발생확률})\)

그리고, 이것을 모든 경우에 대한 값을 합산하면 아래와 같이 된다. 이것이 entropy 이다. 이 entropy 를 \(H\)라고 정의하자.

\(\begin{align} H & = \sum (사건\,발생확률) \cdot \log_2(\frac{1}{사건\,발생확률}) \\ & = \sum_i p_i \ \log_2(\frac{1}{p_i})\\ & = - \sum_i p_i \ \log_2(p_i) \end{align}\)

Reference

1. 초보를 위한 정보이론 안내서 - Entropy란 무엇일까