Information Theory

On this page

• 정보이론
  • Kraft Inequality
  • Expected codeword length
  • Entropy
  • Joint Entropy
  • Conditional Entropy
  • Mutual Information
  • Relative Entropy (KL Divergence)
  • Markov Inequality
  • Chebyshev inequality
  • Weak law of large number (WLLN)
  • Asymptotic equipartition property (AEP)
  • Jensen’s Inequality
  • Information Inequality
• 헷갈릴만한 부분

정보이론

스터디 내용 정리

---

Kraft Inequality

\[ \sum^{l_{max}}_{i=l_{min}}D^{-i}\le 1 \]

---

Expected codeword length

\[ E[L] = \sum^{l_{max}}_{l_{min}} p_i i \]

---

Entropy

(위의 Expected codeword length 를 가장 작게 하는)

\[ H(L) = -\sum^{l_{max}}_{i=l_{min}} p_i \text{log}_D p_i \]

? \(E[X]\) 는 \(H_D(X)\) 보다 항상 큰가?

• \(E[X] - H_D(X) > 0\) 로 증명해보기

  \(\sum p_i i - (- \sum p_i \text{log}_D p_i) = \sum p_i (i + \text{log}_D p_i) = \sum p_i (\text{log}_D D^i p_i) = \sum p_i \frac{\text{ln}(D^i p_i)}{ln D}\)

  \(= \frac{1}{ln D} \sum p_i \text{ln}(D^i p_i) \ge \frac{1}{\text{ln}D} \sum p_i (1-\frac{1}{D^i p_i}) \quad \quad (\because 1-\frac{1}{x} \le \text{ln} x \le x-1)\)

  \(\quad \quad \quad \quad \quad \quad \quad \quad \quad = \frac{1}{\text{ln}D} \sum (p_i -\frac{1}{D^i})\)

  \(\quad \quad \quad \quad \quad \quad \quad \quad \quad = \frac{1}{\text{ln}D} (1 - \sum {D^{-i}}) \ge 0 \quad \quad (\because \sum^{l_{max}}_{i=l_{min}}D^{-i}\le 1)\)

  \(\therefore E[X] - H_D(X) \ge 0\)

---

Joint Entropy

\[ H(X,Y) = -\sum_x\sum_yp(x,y) \text{log}_2 p(x,y) \]

---

Conditional Entropy

\[ H(X|Y) = \sum_y p(y)H(X|Y=y) \]

---

Mutual Information

\[ I(X;Y) = \sum_x \sum_y p(x,y)\text{log}_2 \frac{p(x,y)}{p(x)p(y)} \]

\(I(X;Y) = H(X) - H(X|Y)\)

\(\quad = -\sum_x p(x)\text{log}p(x) - \sum_y p(y)H(X|Y=y)\)

\(\quad = -\sum_x \sum_y p(x,y) \text{log}p(x) + \sum_x \sum_y p(y) p(x|y) \text{log}p(x|y)\)

\(\quad = -\sum_x \sum_y p(x,y) \text{log}p(x) + \sum_x \sum_y p(x,y) \text{log}\frac{p(x,y)}{p(y)}\)

\(\quad = \sum_x \sum_y p(x,y) \text{log}_2 \frac{p(x,y)}{p(x)p(y)}\)

---

Relative Entropy (KL Divergence)

원래 분포는 \(p(x)\) 지만 분포 \(q(x)\) 로 잘못 상정하여 생겨버린 불확실성

\[ D(p(x)||q(x)) = -\sum_x p(x)\text{log}q(x) - (- \sum_x p(x)\text{log}p(x)) = \sum_x p(x) \text{log} \frac{p(x)}{q(x)}\]

\(D(p(x,y)||p(x)p(y))=I(X;Y)\)

• 의미? 독립인 경우 \(p(x,y) = p(x)p(y)\) 이고, \(I(X;Y)=0\) 이다. 즉, 독립이면 정보가 0

---

Markov Inequality

\[P(X\ge a) \le \frac{E[X]}{a}\]

증명

\(E[X]=\int^\infty_{-\infty} xf(x)dx\), 모든 x가 양수이면 다음이 성립 \(\int^{\infty}_0 xf(x) dx\)

\(\int^\infty_0 xf(x)dx\ge\int^\infty_a xf(x)dx \ge a \int^\infty_a f(x) dx = a P(X\ge a)\)

\(\therefore P(X\ge a ) \le \frac{E[X]}{a}\)

---

Chebyshev inequality

Markov inequality에 분산도 이용해보자.

\[P(|X-\mu|\ge k\sigma) \le \frac{1}{k^2}\]

증명

Markov inequality에 \(X\) 대신 \((X-\mu)^2\) 대입

\(P((X-\mu)^2\ge a) \le \frac{E[(X-\mu)^2]}{a}\)

\(=P(|X-\mu|\ge\sqrt{a})\le \frac{\sigma^2}{a}\), \(\quad\) \(a\) 에 \(k^2\sigma^2\) 대입 (\(k\sigma\) 형태로 만들기 위함)

\(\Rightarrow P(|X-\mu|\ge k\sigma) \le \frac{1}{k^2}\)

---

Weak law of large number (WLLN)

시행이 많아질수록 표본 평균이 모평균에 근접해 간다.

수식으로 나타내보면,

\[P(|\frac{X_1+X_2+...+X_n}{n}-\mu| \ge \epsilon) \rightarrow 0\quad \text{as} \quad n\rightarrow\infty\]

증명

체비셰프를 이용해보면,

• Chebyshev: \(P(|X-\mu|\ge k\sigma) \le \frac{E[(X-\mu)^2]}{k^2\sigma^2}\)

• WLLN: \(P(|Y-\mu|\ge\epsilon)\le \frac{E[(Y-\mu)^2]}{\epsilon^2}\quad(Y=\frac{X_1+X_2+...+X_n}{n})\)

\(Y-\mu = \frac{X_1+X_2+...+X_n}{n}-\mu\) 이므로 \(\frac{(X_1-\mu)+(X_2-\mu)+...+(X_n-\mu)}{n}\). 이 식을 제곱해보면

\((Y-\mu)^2 = \frac{1}{n^2}((X_1-\mu)^2+...+(X_n-\mu)^2+2(X_1-\mu)(X_2-\mu)+...+2(X_{n-1}-\mu)(X_n-\mu))\)

이제 \(E[(Y-\mu)^2]\) 를 구해보자.

\(E[(Y-\mu)^2] = E[\frac{1}{n^2}(\sum^n_{i=1}(X_i-\mu)^2 + \sum^n_{i=1}\sum^n_{j=1}2(X_i-\mu)(X_j-\mu))] = \frac{1}{n^2}(\sigma^2 + \sigma^2+...+0+0+...) = \frac{1}{n^2}(n\sigma^2)\)

(\(X_1, X_2, ... ,X_n\) 이 서로 독립이라고 가정하면 교차항의 기댓값 \(E[(X_i-\mu)(X_j-\mu)]\) 은 0이 되므로)

\(\therefore \frac{E(Y-\mu)^2}{\epsilon^2} = \frac{\sigma^2}{n\epsilon^2}\), \(n\rightarrow \infty\) 로 가면 0에 가까워지므로 증명완료

---

Asymptotic equipartition property (AEP)

\[p(x_1,x_2, ..., x_n)=2^{-nH(X)}\]

대수의 법칙: \(E[X]≅\frac{X_1+X_2+...+X_n}{n}\) 이를 엔트로피에 적용해보자. (엔트로피 \(H(X) = E[-\text{log}_2p(x)]\))

\(H(X)≅\frac{-\text{log}_2p(x_1)-\text{log}_2p(x_2)-...-\text{log}_2p(x_n)}{n}\) 이 성립할 것. 즉, 최적길이의 산술 평균과 엔트로피 사이에도 큰 수의 법칙이 성립할 것

\(P(|\frac{-\text{log}_2p(x_1)-\text{log}_2p(x_2)-...-\text{log}_2p(x_n)}{n}-H(X)|>\epsilon)\rightarrow0\)

\(\epsilon\) 보다 클 확률이 0이니 \(\epsilon\) 보다 작을 확률은 1

\(P(|\frac{-\text{log}_2p(x_1)-\text{log}_2p(x_2)-...-\text{log}_2p(x_n)}{n}-H(X)|\le\epsilon)\rightarrow1\)

확률 시행이 모두 독립이라고 가정하면, 로그로 묶이는 \(p(x_1)p(x_2)...p(x_n) = p(x_1,x_2,...,x_n)\)

\(P(|\frac{-\text{log}_2p(x_1,x_2,...,x_n)}{n}-H(X)|\le\epsilon)\rightarrow1\)

\(\epsilon\) 보다 작을 확률이 1이라는 말은 무조건 그 사건이 성립한다는 말이므로,

\(|\frac{-\text{log}_2 p(x_1,x_2,...,x_n)}{n}-H(X)|\le \epsilon\)

\(\Rightarrow -n\epsilon \le \text{log}_2p(x_1,x_2,...,x_n)+nH(X) \le n\epsilon\)

\(\Rightarrow 2^{-n(H(X)+\epsilon)}\le p(x_1,x_2,...,x_n) \le 2^{-n(H(X)-\epsilon)}\)

\(\epsilon\) 이 충분히 작으면 다음 식이 성립 \(p(x_1, x_2, ..., x_n) = 2^{-nH(X)}\)

의미? 시행횟수 \(n\) 을 점점 늘려 나가면, 많은 관측자들이 점점(Asymptotic) 비슷한 패턴들의 집합(Equipartition)을 마주한다.

’전형적이다’라는 말은 \(2^{-n(H(X)+\epsilon)}\le p(x_1,x_2,...,x_n) \le 2^{-n(H(X)-\epsilon)}\) 부등식을 성립하는 사건들의 집합 \(\{x_1,x_2,...,x_n\}\) 이라는 것. 이를 typical set이라고 정의

사람의 직관과 물리적 현상을 이어주는 부등식

---

Jensen’s Inequality

• Convex function \(f(x)\)

  \(f(E[X])\le E[f(x)]\)

• Concave function \(f(x)\)

  \(f(E[X])\ge E[f(x)]\)

* Convex: \(\cup\) 곡선, Concave: \(\cap\) 곡선

---

Information Inequality

\(D(p(x)||q(x))\) 가 0보다 크다는 것을 증명하기

\(D(p(x)||q(x)) = \sum_x p(x) \text{log}\frac{p(x)}{q(x)}\) 이므로

\(- D(p(x)||q(x)) = \sum_x p(x) \text{log}\frac{q(x)}{p(x)}\)

\(\text{log}_2(.)\) 는 concave 함수이므로, Jensen’s inequality를 적용하면 \(\le \text{log}_2 (\sum_x p(x) \frac{q(x)}{p(x)}) = \text{log}_2(\sum_x q(x))=0\)

\(- D(p(x)||q(x))\) 가 항상 0보다 작거나 같으므로 \(D(p(x)||q(x))\) 는 항상 0보다 크거나 같다

---

---

헷갈릴만한 부분

• \(I(Y;Z|X)\) 는 Y와 Z given X 의 mutual information가 아니라 X가 조건부로 주어진 상태에서 Y와 Z의 mutual information이다.