Information Theory

Information Theory

'정보란 무엇인가'라는 물음은 철학적인 질문이라 결론을 내리기 어렵지만, 확률의 입장에서 이러한 어려움을 정면으로 맞서 성공을 거둔 이론이 바로 정보이론이다.

정보량을 깜짝 놀라는 정도로 정도(깜짝도)로 측정

• Self Information, Degree of Surprise, Quantities of Information

  정보의 크기, 놀람의 정도, 자기 정보

  $I(x_{i}) = \log ({{1}\over{P(X=x_{i})}}) = -\log P(X=x_{i})$

  정보량의 단위를 비트로 설정한 경우, log의 밑을 2로 설정할 수 있다.

  (자연 로그를 사용하면 내트(nats)로 설정한 것)

  현실 세계와 얼마나 부합하는 지는 예시를 통해 알 수 있다.

  • 깜짝도

    주사위를 던져 2가 나오는 놀람 정도 > 짝수가 나오는 놀람 정도

  • 정보량의 관점

    동전을 던져 앞이 나왔다 → log2 = 1 (1비트 또한 2가지를 나타 낼 수 있다.)

    8면체 주사위 → log8 = 3 (3비트)

  • 여러 현상을 합칠 때의 깜짝도
    • 주사위를 던져 짝수가 나오고 게다가 소수였다. (독립이 아님)

      P(짝수, 소수) = P(짝수) P(소수|짝수) ≠ P(짝수)P(소수)

      log(2*3) = log 2 + log 3 (2밖에 없으므로)

    • 놀람의 정도의 합: 주사위를 던져 2가 나오고 동전을 던져 앞이 나옴.

      log (6*2) = log6 + log 2 → 각 사건의 합

• Entropy, Shannon Entropy

  $H[X] \equiv E[I(x)] = \sum_{x} P(X=x)\log{{1}\over{P(X=x)}}$

  이 z때, 편의상 $P(X=x)=0$인 경우 $0 \log (1/0) =0$ 으로 해석

  H(X)가 아닌 H[X]로 표현 → 범함수

  분포가 균등할수록 엔트로피가 큼

  앞면이 나올 확률을 변화시킴에 따라 엔트로피의 변화는 아래와 같으며, 앞면이 나올 확률이 1/2 일때 가장 엔트로피가 큼을 볼 수 있다.

  

  또한, X가 취할 수 있는 값이 m가지 일 때 0≤H[X] ≤ logm 이 성립한다. H[X] =0은 확률변수가 일정한 값만 나오는 경우이며, H[X] = logm은 균등분포일 때

  노이즈 없는 코딩 이론(Noiseless coding Theorem)에 따르면, 엔트로피는 확률 변수의 상태를 전송하기 위해 필요한 비트 숫자의 하한선

• Joint Entropy

  X=x, Y=y 라는 소식을 들었을 때의 깜짝도

  $H[X,Y] \equiv E[h(X,Y)] = \sum_{x} \sum_{y} P(X=x,Y=y)\log{{1}\over{P(X=x,Y=y)}}$

• Conditional Entropy

  즉 X=x를 알고 있을 때, Y=y의 소식을 들을 때의 깜짝도

  $H[Y|X] \equiv E[h(Y|X)] = \sum_{x} \sum_{y} P(X=x,Y=y)\log{{1}\over{P(Y=y|X=x)}}$

  $= \sum_{x} \sum_{y} P(x,y)\log{{P(x,y)}\over{P(x)}}$

  cf) 조건부 기댓값

  

• Mutual Information, Information Gain

  상호 정보량: Y를 들었을 때 기대 깜짝도와 X를 이미 듣고 난 후 Y를 들을 때의 기대 깜작도의 차이

  차이가 클수록 X는 Y에 대해 많은 정보를 포함하고 있다는 것

  Y에 대해 알고 있을 때, X에 대한 불확실성을 표현한 것

  베이지안 관점 → P(y)를 Y에 대한 사전분포 P(y|x)를 새로운 데이터 X를 관찰한 후의 사후 분포로 보면, 상호 정보량은 새 관찰값 X의 결과로 줄어드는 Y에 대한 불확실성을 표현한 것

  $I[X;Y] \equiv H[Y] - H[Y|X] = I[Y;X] = \sum_{x} \sum_{y} P(x,y)\log{{P(x,y)}\over{P(x)P(y)}}$

  

  상호정보량 $I[X;Y]$와 상관계수 $\rho_{X,Y}$의 차이

  $I[X;Y]$는 X, Y가 얼마나 독립이 아닌지를 나타냄, (I=0에서 독립과 동치) 범위 0 ~ 1

  $\rho_{X,Y}$는 영향의 정도를 나타냄(상관계수에서 분산의 크기를 나눔) 범위 -1 ~ 1

  (둘다 독립이라면 0이지만 상관계수는 역이 성립하지 않음)

  Decision Tree 모델 중 ID3 알고리즘은 Information Gain 이 큰 feature를 노드로 설정해 분기

  $IG[X_{1};Y] = H[Y] - H[Y|X_{1}]$ > or < $IG[X_{2};Y] = H[Y] - H[Y|X_{2}]$

• Differential Entropy

  연속확률분포에 대한 Shannon Entropy이다. X가 연속확률변수이고 pdf가 p(x)일 때,

  $H[X] = E[I(x)] = \int{p(x)\ln{{1}\over{p(x)}}dx} = - \int{p(x)\ln{p(x)}dx}$

  Joint, Conditional, Relative Entropy는 이산확률변수일 때와 유사한 방식으로 정의됨

  섀넌 엔트로피와의 차이점: 모든 속성이 동일하진 않음

  단위에 종속됨: mm로 측정된 미분엔트로피는 m로 측정된 엔트로피보다 log(1000) 더 큼

  (→ 변수 변환에 변화한다)

  음수 값을 가질 수 있음: 특정 지점에서 1보다 큰값을 가질 수 있어 음수 값을 가질 수 있음

  ex. $H[\mathcal {U}(0,1/2)] = -\log(2)$

• KL Divergence, Relative Entropy

  분포 P와 Q가 얼마나 다른지 측정하기 위해 사용. 교차 엔트로피는 엔트로피, 결합엔트로피, 조건부 엔트로피, 미분엔트로피, 상호정보량은 확률변수를 인수로 받고, KLD는 확률분포를 인수로 받는다.

  P: 추정하고자 하는 분포 / Q: P를 추정한 분포

  $KL[P||Q] = \Sigma P(x)\log{{P(x)}\over{Q(x)}}$

  $KL[p||q] = \int p(x)\log{{p(x)}\over{q(x)}}$

  분포 P, Q의 구분하기 쉬운 정도를 나타냄 . 얼마나 유사한가

  ex. KL(앞면이 0.1인 확률 동전 0.2로 추정) $\approx$ 0.044 > KL(앞면이 0.5인 확률 동전 0.6로 추정) $\approx$ 0.02

  • KL Divergence 와 Likelihood

    모델링하고자 하는 알려지지 않은 확률분포 $p(\mathbf{x})$로부터 데이터가 생성된다고 가정.

    우리는 변경 가능한 파라미터 $\theta$를 이용해 만든 $q(\mathbf{x|\theta})$를 이용해 $p(\mathbf{x})$를 추정하고자 함.

    이러한 $q(\mathbf{x|\theta})$의 $\theta$를 정하는 방법 중 하나는 KLD를 최소화하는 $\theta$를 찾는 것. (MLE)

    $p(\mathbf{x})$를 알지 못하지만, 추출된 데이터 $\mathbf{x}_{n}(n={1,..,N})$와 아래식 활용해 $p(\mathbf{x})$에 대한 기댓값을 근사할 수 있음. ($E[f(\mathbf{X})]=\int{p(x)f_{\mathbf{X}}(x)}dx \simeq {{1}\over{N}}\Sigma_{n=1}^{N}f_{\mathbf{X}}(x_{n})$ )

    이를 이용해 KLD로 표현하면, 아래와 같음.

    $KL(p‖q)= \int p(x)\log{{p(x)}\over{q(x)}} \simeq {{1}\over{N}}\Sigma_{n=1}^{N}\left\{−\ln{q(\mathbf{x}_{n}|\theta)}+\ln{p(\mathbf{x}_{n})} \right\}$

    여기서 우변의 첫 번째 항 ${−\ln{q(\mathbf{x}_{n}|\theta)}}$ 가 로그가능도이며, 이것만 $\theta$와 연관되어 있음을 확인할 수 있음. KLD를 최소화하는 것은 Likelihood를 최대한다는 것임을 알 수 있음.

    KL은 MLE와 연관이 있으며, 이 내용은 EM알고리즘과 변분추론과 많은 관련이 있음. (참고)

    

  • 정보 기하

    KLD는 비대칭성으로 진짜 '거리'는 아니다. 오히려 거리의 제곱에 상응함. 확장 피타코라스 정리로 KL(p||q) + KL(q||r) = KL(p||r) 이 성립.

    

  • KLD는 변수 변환에 변하지 않으며 항상 0이상 이다.

    

  • 베이지안 통계에서, KLD은 사전분포에서 사후분포의 information gain의 측정값으로 사용될 수 있다.

• Cross Entropy

  $H[p,q] = - \Sigma_{k=1}^{K}p(y_{k})\log{q(y_{k})}$

  $H[p,q] = - \int_{k}p(y)\log{q(y)}dy$

  결합엔트로피와 notation이 같아 헷갈릴 수 있다. 교차엔트로피는 확률분포를 인수로 받는다.

  교차엔트로피는 자기 엔트로피와 KLD 의 합이다. Cross Entropy를 minize 한다는 것은 KL Divergence를 줄인다는 것과 같다.

  $H[P,Q] = H[P] + KL[P||Q]$

  아래 Visual Information Theory를 보면, 교차 엔트로피는 확률 분포 P를 기준으로 최적으로 인코딩 했을 때 확률분포 Q의 평균 메시지 길이이다.

  ML의 손실함수로써도 자주 사용된다.

  Binary Classification에서

  

  하나의 샘플에 대하여

  Y=1일 경우, 교차 엔트로피는 $-\log {\mu}$

  Y=0일 경우, 교차 엔트로피는 $-\log {(1-\mu)}$ 이다

  N개의 학습데이터로 확장하면,

  

  이 를, 다중분류 문제로 확장하면

  

  → 이는 불균형일 경우, 출현 빈도가 많은 샘플에 대한 교차 엔트로피만 학습할 수 있다.

Visual Information Theory - Chris Olah

---

• Simpson's Paradox

  데이터의 세부 그룹별 경향성이 전체적으로 보면 추세가 사라지거나 반대 방향 경향성을 보이는 경우

  전체적으로 보면 B 치료제가 신장 결석에 더 효과가 있는 것있지만, B치료제를 실험한 사람은 비교적 쉬웠던 작은 신장결석의 비율이 더 높았음

  

• Variable-Length Codes - 가변 길이 코드

  

  4가지 단어로 통신한다고 할 때, 왼쪽 그림처럼 사용할 경우 2bit로 표현이 가능. 가운데 이미지처럼 단어마다 사용하는 확률이 다르다면, 오른 쪽과 같이 가변길이 코드를 이용할 경우 기대 비트는 1.75bit로 줄어듬.

  우리가 영리하게 인코딩을 하더라도 평균 길이를 1.75비트 보다 적게 사용할 수 없는 한계 → 엔트로피

  가변길이코드를 설정할 경우에는 코드의 길이가 가변하므로 코드가 언제 끝인지 알 수 있는 표시가 필요함

  → '1', '11' 등을 사용하지 않은 이유 → 이런 것들이 아래 cost로 작용함.

  

• Optimal Encoding - 최적 인코딩

  가변길이코드에서도, 코드를 unique하게 만들 수 있는 것은 가능하다. 어떤 코드를 사용하면, 해당 코드가 다른 코드의 접두사(prefix)가 아니도록 구성하면된다. 이를 prefix property라고 한다.(cf. https://en.wikipedia.org/wiki/Prefix_code)

  따라서 우리가 01이라는 가변길이 코드를 사용하는 경우, 생기는 손실은 아래와 같다

  

  이것을 한정된 예산 내에서, 가장 큰 이득을 보기 위한 것으로 생각할 수 있다. 나올 확률이 높은 단어에는, 비용이 크더라도 average length contribution을 작게 해주므로 기꺼이 지불할 것이다.

  

• Calculating Entropy - 엔트로피의 계산

  $cost = {{1}\over{(2^{L}))}}$ 이며, 이를 길이에 cost 대한 식으로 바꿔주면 길이 $L = \log_{2}(1/cost)$ 이다. x에 대하여 p(x)를 사용하는 것이 최적의 인코딩 방안이므로 $L = \log_{2}(1/p(x))$가 된다.

  따라서 위 예시에서 최적의 인코딩 방안을 사용하는 평균 메시지 길이는 아래와 같이 계산 가능하며, H[P]를 엔트로피라고 함.

  

• Cross Entropy - 교차엔트로피

  

  강아지 애호가의 엔트로피에 맞춰 고양이 애호가와 통신하는 경우, 고양이 애호가가 전송하는 평균 메시지 길이 → 교차 엔트로피

  아래 그림에서 $H_{p}(q) = H[p,q]$ (교차엔트로피, 결합엔트로피와 헷갈리지 않기 위해)

  

  고양이 애호가의 엔트로피에 맞춰 코딩할 때에도, 강아지 애호가의 평균 길이 메시지(엔트로피)는 더 커지는 것을 확인할 수 있다. 그리고 이 차이가 바로 KL Divergence 이다.

  $H[P,Q] = H[P] + KL[P||Q]$

  $KL[P||Q] = H[P,Q] - H[P]$

• Joint, Conditional Entropy 에 대한 실생활에서의 시각화 예시도 좋음

  두 변수에 대한 시각화에서는 확률에 대한 코드 길이를 높이로 설정함

  

  

• Variation of Information - 결합엔트로피 - 상호정보량

  $V[X,Y] = H[X,Y] - I[X,Y]$

  KLD는 같은 변수에 대한 두 분포의 거리를 나타내는 것이고, Variation of Information은 두 개의 변수에 대한 하나의 결합분포에 대한 거리를 나타낸다.

• 마무리

  Information theory turns up in all these places because it offers concrete, principled formalizations for many things we need to express. It gives us ways of measuring and expressing uncertainty, how different two sets of beliefs are, and how much an answer to one question tells us about others: how diffuse probability is, the distance between probability distributions, and how dependent two variables are.

Refrences

---

• http://colah.github.io/posts/2015-09-Visual-Information/#fn4

• https://en.wikipedia.org/

• http://norman3.github.io/prml/docs/chapter01/6

• https://books.google.co.kr/books/about/프로그래머를_위한_확률과_통.html?id=dFSeDwAAQBAJ&redir_esc=y

• https://datascienceschool.net/02 mathematics/10.03 교차엔트로피와 쿨백-라이블러 발산.html