정보이론-5(1)W

• Ball weight problem

- 12개의 공 중 하나가 무게가 다르다. (더 가볍거나 무겁다.)
Q) 양팔 저울 사용하여 최소 횟수로 이상(odd) 공을 찾는 방법은?
A) 

1번째 가능성

운이 좋으면 3번만에 찾는다.

운이 나쁘면 4번만에 찾는다.

=> 이는 optimal solution이 아니다.

 

• Optimal Solution

- 모든 결과들을 가능한 같게끔 만든다!

이 방법이 optimal solution

=> 가능한 결과가 동등한 확률 분포를 가지도록 설정해야 정보량이 극대화된다.

 "Maximizing" the information gain = "minimizing" the uncertainty
: 정보 이득을 최대화하려면 불확실성이 최소화 되어야 한다.

• Shannon Information Content

- 사건이 발생할 확률이 p일때 그 사건에서 얻을 수 있는 정보량은 h(x) = log 1/p 로 정의된다.

• The 63 Game

- 0~63 사이의 숫자를 맞추는 게임 (이진 질문으로)
Q) 가장 적은 질문 횟수로 맞추는 방법은?
A) 가능한 후보를 1/2로 나누도록 질문한다.

 

• The Game of Submarine

- 1~64 위치 중 무작위로 잠수함이 숨어 있다.
- 미사일이 잠수함을 맞추면 게임 종료
Q) 잠수함을 맞춘다면 얼마의 정보를 얻는가?
A) 항상 정보량은 6bits 이다.

 

- 정보량이 많을수록(엔트로피가 높을수록) 더 많은 비트가 필요하다.
- 엔트로피가 낮다면 더 효율적으로 압축이 가능하다.

=> Data Compression에는 Lossy Compression / Lossless Compression이 존재

 

• Lossy Compression

- 서로 다른 몇 개의 사건을 같은 이진 문자열로 mapping한다.
- 일부 가능한 결과들을 동일한 이진 문자열로 mapping하여 정보를 압축하는 방법 
EX1)

EX2)

=> 문자 집합이 8개 일때, 이를 3비트로 인코딩하면 모든 문자를 구별 가능
=> 일부 문자를 제거하면 2비트로도 충분하다.

• Compressing Blocks of Symbols

- 여러 기호를 묶어서 압축하는 방법

EX)

• Shannon's Source Coding Theorem

- 데이터가 충분히 많으면 평균 정보량 (H)에 거의 정확히 수렴하여 압축할 수 있다. 

• Typicality

- 이론적으로 데이터의 분포는 대부분 평균 정보량에 가까운 값을 가진다.
- 즉, 충분히 많은 데이터를 sampling하면 대부분의 sample은 평균 정보량에 근접한 값을 가진다.

• AET(Asymptotic Equipartition Theorem)

- N개의 독립적인 동일 분포, 랜덤 변수들이 있을때 충분히 큰 N에 대해 가능한 모든 사전은 2^NH(X)개의 집합으로 구성되며, 각 사건의 확률은 2^-NH(X)에 근접

 

# Chebyshev's Inequality

=> 증명 살펴보기

1. 

 

2. 

 

• Shannon's Source Coding Theorem

=> 즉, N이 무한대로 가면 정보량은 무조건 H에 수렴