【통계학】 20강. 정보이론

20강. 정보이론(information theory)

 

추천글 : 【통계학】 통계학 목차 

---

1. 정보이론 [본문]

2. 현대 정보이론 [본문]

---

 

1. 정보이론 [목차]

⑴ 개요

① low probability event : high information (surprising)

② high probability event : low information (unsurprising)

⑵ entropy

① 문제 상황 : X는 Raining / Not Raining. Y는 Cloudy / Not Cloudy

 

Figure. 1. 엔트로피 예제

 

② 통계학 기본 개념

 

 

③ 정보(information) : 결과를 알게 되었을 때 얻게 되는 모든 것

④ uncertainty(surprisal, unexpectedness, randomness) 

 

 

○ 정의 1. 결과에 대한 정보의 부재 

○ 정의 2. 주어진 경우의 수를 표현하기 위해 필요한 비트 수

○ 밑이 2인 log₂인 경우 : bits라는 단위를 사용

○ 밑이 e인 자연로그인 경우 : nats라는 단위를 사용

⑤ entropy (self information)

 

 

○ 이해 

○ 즉, entropy는 uncertainty의 평균값으로 정의됨

○ 물리학에서의 엔트로피처럼 무질서할수록 높은 값이 나옴 : 엔트로피가 높으면 heterogeneity가 높음을 의미

○ 각 사건의 surprisal(-log p(x))에 각 사건에 대한 확률 가중치(p(x))를 적용한 것

○ 예시

○ fair coin toss : H = -0.5 log₂ 0.5 - 0.5 log₂ 0.5 = 1

○ fair die : H = 6 × (-(1/6) log₂ (1/6)) = log₂ 6 = 2.58  

○ X가 균일분포를 따른다면, H(X) = log n이 성립함 

○ 크로스 엔트로피(cross entropy)

○ 정의 : 두 확률분포 p와 q를 구분하기 위해 필요한 평균 비트 수

○ 머신러닝에서는 일반적으로 surprisal에 model prediction을, 사건의 가중치에 true distribution을 적용함 

 

 

○ 특징 1. H(X)는 shift-invariant 

○ Y = X + a일 때, p_Y(y) = p_X(x)이므로 H(Y) = H(X)가 성립

○ 특징 2. H(X) ≥ 0

○ 특징 3. H_b(X) = (log_ba) H_a(X) (단, a, b는 로그의 밑)

○ log_bp = (log_ba) log_ap

⑥ joint entropy 

 

 

○ 특징 1. X와 Y가 독립이라면 H(X, Y) = H(X) + H(Y)

 

 

⑦ conditional entropy 

○ 특정 조건에 대한 조건부 엔트로피

 

 

○ 전체 조건부 엔트로피

 

 

○ 정보 이득(IG, information gain) : X라는 정보를 앎으로써 무질서한 상황이 질서 있게 바뀐 경우 정보 이득이 큼

 

 

○ information bottleneck method (IB) : 정보이론을 이용하여 복잡도와 정확도 간 트레이드오프를 기술

○ 응용 : 가령, 주어진 데이터에서 클러스터의 개수를 몇 개로 할 것인지를 알려줄 수 있음

○ 특징 1. X와 Y가 독립이라면 H(Y | X) = H(Y)

○ 특징 2. H(Y | Y) = 0

○ 특징 3. H(X, Y) = H(X) + H(Y | X) = H(Y) + H(X | Y) (연쇄법칙(chain rule))

 

 

○ 특징 4. H(X, Y | Z) = H(X | Z) + H(Y | X, Z)

 

 

⑧ 상대 엔트로피(relative entropy, Kullback Leibler distance, KL distance) 

 

 

○ 개요

○ 두 개의 확률분포가 얼마나 발산하는지를 나타내는 척도 

○ true distribution을 모방하는 approximate distribution p(x)가 앞에 오고, true distribution q(x)가 뒤에 옴

○ 일반적으로 true distribution은 복잡한 분포 함수이고, approximate distribution은 parameter model

○ approximate distribution은 manageble하므로, 정규분포처럼 단순한 분포로 할 수 있음 

○ mutual information 

 

 

○ 정보 이득과 mutual information은 동일함

 

 

○ mutual information은 이미지 간 유사도 판단 시 사용할 수 있음 

○ 특징 1. asymmetry : D_KL(p(x) || q(x)) ≠ D_KL(q(x) || p(x))

○ 특징 2. D(p || q) ≥ 0 (등호조건 : p(x) = q(x))

 

○ 특징 3. mutual information ≥ 0 (등호조건 : X와 Y가 독립)

 

 

○ 특징 4. H(X) ≤ log n (단, n은 X가 취할 수 있는 원소의 개수)

 

 

○ 특징 5. H(X | Y) ≤ H(X) (등호조건 : X와 Y가 독립) : 조건은 엔트로피를 감소시킨다는 의미 

 

 

○ 응용 : 알려지지 않은 진실한 데이터 분포 q와 가장 KL distance가 작은 예측 데이터 분포 p를 결정하는 문제

○ log-likelihood를 극대화하면 KL distance를 최소화할 수 있음 

 

 

⑨ AEP(asymptotic equipartition property)

 

 

⑶ 비교 1. Gini impurity

 

 

① entropy가 유일무이한 척도는 아니므로 Gini impurity와 같은 대안적인 척도가 제시됨

② Gini impurity는 잘못 레이블링할 확률(1 - P(x_i))에 각 샘플에 대한 가중치(P(x_i))를 고려한 것

③ Gini impurity와 entropy 모두 주어진 데이터가 무질서할수록 높은 값을 보임 : impurity의 어원

④ (구별 개념) 경제학에서의 지니계수

○ 소득의 불평등을 평가하기 위해 처음으로 도입된 개념 : 소득뿐만 아니라 변량의 분포의 불평등도도 비슷하게 평가할 수 있음

○ 지니계수가 경제학에서 머신러닝 및 정보이론 분야로 넘어가면서 비슷한 불평등도를 암시하나 수학적 정의가 달라짐

○ 차이 : 변량의 분포가 모두 동일하면,

○ 경제학에서의 지니계수 : 극단적으로 평등해지므로 경제학에서의 지니계수는 0의 값을 가짐 

○ 정보이론에서의 지니계수 : 코시-슈바르츠 부등식에 의해 최댓값을 가짐. 직관적으로는 가장 무질서해지므로 최댓값

⑷ 비교 2. connectivity index (CI)

① 공간전사체 상에서, 특정 스팟과 가장 유사한 스팟(nearest neighbor)이 서로 다른 클러스터에 있으면 CI 값이 높아짐 (ref)

② 따라서 CI 값이 높을수록 heterogeneity가 높음을 암시함 

⑸ 비교 3. Simpson index 

① Shannon entropy와 함께, 정보이론에 기반한 또다른 척도 

② 공간전사체 기준으로, 두 개의 랜덤한 스팟이 동일한 클러스터에 속할 확률 (ref)

③ Simpson index가 낮을수록 heterogeneity가 높음을 암시함 

⑹ 비교 4. cluster modularity

① 공간전사체 기준으로, 클러스터 내 스팟의 purity (homogeneity)를 나타내는 메트릭 (ref)

⑺ 비교 5. Lempel-Ziv complexity 

⑻ 비교 6. Silhouette coefficient

⑼ 비교 7. Calinski-Harabasz index

⑽ 응용 1. Markov process 

 

 

① two-state Markov chain  

 

Figure. 2. two-scale Markov chain

 

② hidden Markov model 

○ χ = {X_i}가 Markov process이고 Y_i = ϕ(X_i) (단, ϕ는 deterministic fuction)이면 y = {Y_i}는 hidden Markov model

③ 특징 1. Pr(x_n | x_n-1)이 n에 무관하면 Markov process는 stationary (time-invariant)

④ 특징 2. aperiodic ⊂ irreduicible

⑤ 특징 3. Markov process으로 열역학 제2법칙(엔트로피 증가 법칙)을 증명할 수 있음

○ 단, uniform stationary distribution 가정

 

 

2. 현대 정보이론 [목차]

⑴ 연혁

① Ludwig Boltzmann (1872) : 기체 입자의 엔트로피를 설명하기 위해 H-theorem을 제안 

② Harry Nyquist (1924) : "지능"과 이것이 통신 체계로 전파되는 속도를 정량화 

③ John von Neumann (1927) : 깁스 자유 에너지를 양자역학으로 확장

④ Ralph Hartley (1928) : 수신자의 구별 가능한 정보의 개수를 로그를 이용하여 표현

⑤ Alan Turing (1940) : 독일 에니그마 암호를 해독하기 위해 deciban을 소개

⑥ Richard W. Hamming (1947) : Hamming code를 개발 

⑦ Claude E. Shannon (1948) : 정보이론을 주창. A Mathematical Theory of Communication 

⑧ Solomon Kullback & Richard Leibler (1951) : Kullback-Leibler divergence를 소개 

⑨ David A. Huffman (1951) : Huffman encoding을 개발 

⑩ Alexis Hocquenghem & Raj Chandra Bose & Dwijendra Kumar Ray-Chaudhuri (1960) : BCH code를 개발

⑪ Irving S. Reed & Gustave Solomon (1960) : Reed-Solomon code를 개발

⑫ Robert G. Gallager (1962) : low-density parity check를 소개

⑬ Kolmogorov (1963) : Kolmogorov complexity (minimum description length)를 소개

⑭ Abraham Lempel & Jacob Ziv (1977) : Lempel-Ziv 압축 (LZ77)을 개발

⑮ Claude Berrou & Alain Glavieux & Punya Thitimajshima (1993) : Turbo code를 개발

⑯ Erdal Arıkan (2008) : polar code를 소개

⑵ 종류 1. 암호(encoding)

① Huffman code

② Shannon code

③ Shannon-Fano-Elias code (alphabetic code)

⑶ 종류 2. 압축(compression)

① UD(uniquely decodable)

② Kraft inequality

⑷ 종류 3. network information theory 

⑸ 종류 4. quantum information theory 

 

입력: 2021.11.10 22:28

수정: 2023.03.21 16:22