Bishop PRML - Ch1. Introduction (6)

Information Theory

• information

  • information(surprisal)
    • $h\left(x\right)=-\ln p\left(x\right)$
  • entropy
    • $H\left[x\right]=-{\sum }_{x}p\left(x\right)\ln p\left(x\right)=-{\int }_{x}p\left(x\right)\ln p\left(x\right)dx$
    • expected information (expected surprisal)

• thermodynamics

  • 총 입자수$N$, $i$싱태에 $n_i$개의 입자가 속함
  • multiplicity
    • $W=\frac{N!}{{\prod }_i{n}_i!}$ (Linus Pauling, 1969)
    • the number of microstates corresponding to a macrostate
    • N개의 입자가 가질 수 있는 총 상태의 수
  • entropy
    • $S=\frac{R}{N}\ln W=k\ln W$ ($J{K}^{-1}$) (Ralph Baierlein, 1999)
    • $H=\frac{1}{N}\ln W$
      • 만약 온도를 섭씨의 스케일을 따른 절대온도를 쓰지 않고, 적절하게 스케일링한 온도 ($R\ast \text{absolute temperature}$)를 쓸 경우
    • $H=\frac{1}{N}\ln W=\frac{1}{N}\ln N!-\frac{1}{N}{\sum }_i\ln n!$
    • $H=-{\lim }_{N\to \infty }{\sum }_i\left(\frac{n_i}{N}\right)\ln \left(\frac{n_i}{N}\right)=-{\sum }_{i}p\left(x_i\right)\ln p\left(x_i\right)$
      • ${\sum }_i{n}_i=N$
      • $p\left(x_i\right)={\lim }_{N\to \infty }\left(n_i/N\right)$ (입자가 $x_i$상태에 속할 확률)
      • $n_i/N$비를 유지시키면서 $N\to \infty$
        • $\ln N!\simeq N\ln N-N$ (Stirling's approximation)

• discrete distribution에서 entropy의 성질

  • $0\le H$
  • $p\left(x_i\right)=1,p\left(x_{j\ne i}\right)=0$일때 $H=0$
  • $p\left(X\right)$가 uniform할 때 $H$가 최대
    • Lagrange multiplier 통해 증명
      • functional
        • $L=-{\sum }_{i}p\left(x_i\right)\ln p\left(x_i\right)+\lambda \left({\sum }_{i}p\right(x_i)-1)$
      • stationary point를 찾으면 모든 $p\left(x_i\right)$값이 같은 경우가 됨
      • second derivative를 구하면 음수로, 최대치임을 확인 가능
        • $\frac{{\partial }^2\tilde{H}}{\partial p\left(x_i\right)\partial p\left(x_j\right)}=-I_{ij}\frac{1}{p_i}$
    • Jensen's inequality를 통해서도 유도 가능

• continuous distribution

  • $H\left[x\right]=-\int p\left(x\right)\ln p\left(x\right)dx$
    • measure theory에서 실수 변수를 $\Delta$너비의 인터벌로 쪼갠 뒤, 각 인터벌의 분포를 discrete로 가정 후, ${\lim }_{\Delta \to 0}$를 취하여 continuous한 경우에 대한 식을 얻을 수 있음
  • $H\left[x\right]=-\int p\left(x\right)\ln p\left(x\right)dx$
    • multivariable

• continuous distribution에서 entropy의 성질

  • Lagrange multiplier적용하기 위하여 constraint셋업
    • ${\int }_{-\infty }^{\infty }p\left(x\right)dx=1$
    • ${\int }_{-\infty }^{\infty }xp\left(x\right)dx=\mu$
    • ${\int }_{-\infty }^{\infty }(x-\mu {)}^{2}p(x)dx={\sigma }^2$
  • functinal
    • $L=-{\int }_{-\infty }^{\infty }p\left(x\right)\ln p\left(x\right)dx+{\lambda }_1({\int }_{-\infty }^{\infty }p\left(x\right)dx-1)+{\lambda }_2({\int }_{-\infty }^{\infty }xp\left(x\right)dx-\mu )+{\lambda }_3({\int }_{-\infty }^{\infty }(x-\mu {)}^{2}p(x)dx-{\sigma }^2)$
  • stationary point
    • $p\left(x\right)=\exp \{-1+{\lambda }_1+{\lambda }_{2}x+{\lambda }_3(x-\mu {)}^2\}$
    • $p\left(x\right)=\frac{1}{(2\pi {\sigma }^2{)}^{1/2}}\exp \{-\frac{(x-\mu {)}^2}{2{\sigma }^2}\}$
      • constraint 이용
  • 가우시안 분포 하에서 엔트로피 최대가 된다는 것 확인 가능
  • 가우시안 분포 하에서의 엔트로피
    • $H\left[x\right]=\frac{1}{2}\{1+\ln (2\pi {\sigma }^2\left)\right\}$
      • ${\sigma }^2$이 클 수록 엔트로피가 증가
      • 일 때,

• conditional entropy

  • $H[y\mid x]=-\int \int p(y,x)\ln p(y\mid x)dydx$
  • conditional probability에 대한 entropy

• joint entropy

  • $H[x,y]=H[y\mid x]+H\left[x\right]$
  • $x$와 $y$를 특정하기 위한 정보량은 $x$를 특정하기 위한 정보량과 $x$가 주어졌을 때 $y$를 특정하기 위한 정보량의 합 (덧셈임에 주의)

• Kullback-Leibler divergence (relative entropy)

  • $D_{KL}(p\parallel q)=-\int p\left(x\right)\ln q\left(x\right)dx-(-\int p\left(x\right)\ln p\left(x\right)dx)=-\int p\left(x\right)\ln \left\{\frac{q\left(x\right)}{p\left(x\right)}\right\}dx$
  • 비대칭임에 주의 ($D_{KL}(p\parallel q)\ne D_{KL}(q\parallel p)$)
  • 분포의 dissmilarity 척도
    • 증명 : Jensen's inequality
      • for convex function $f\left(x\right)$
      • $f\left({\sum }_{i=1}^M{\lambda }_i{x}_i\right)\le {\sum }_{i=1}^M{\lambda }_{i}f\left(x_i\right)({\lambda }_i\ge 0,{\sum }_i{\lambda }_i=1)$
      • $f\left(E\right[x\left]\right)\le E\left[f\right(x\left)\right]$
      • $f(\int xp\left(x\right)dx)\le \int f\left(x\right)p\left(x\right)dx$
      • $D_{KL}(p\parallel q)=-\int p\left(x\right)\ln \left\{\frac{q\left(x\right)}{p\left(x\right)}\right\}dx\ge -\ln \int q\left(x\right)dx=0$
        • $-\ln x$는 convex, $\int q\left(x\right)dx=1$
  • $-\int p\left(x\right)\ln q\left(x\right)dx$
    • $p$의 entropy($-\int p\left(x\right)\ln p\left(x\right)dx$)를 constant 취급할 경우, 앞 항($-\int p\left(x\right)\ln q\left(x\right)dx$)만 남음
    • $p$가 조건부 레이블 분포, $q$가 조건부 예측 분포라고 할 때, 이 값은 곧 cross-entropy가 됨
      • 이 값은 곧 negative log likelihood와 동일
      • multinomial distribution(classification 문제)에서는 곧 cross-entropy error
      • gaussian distribution(regression 문제)에서는 곧 SSE
  • 조절 가능한 패러미터 $\theta$에 종속된 parametric distribution $q(x\mid \theta )$를 통하여 알려지지 않은 분포 $p\left(x\right)$를 찾는 상황을 가정
    • $p\left(x\right)$는 모르지만 $p\left(x\right)$에서 샘플링된 학습 데이터셋 $(x_1,\cdots ,x_N)$은 있는 상태, 데이터셋을 통하여 $p\left(x\right)$의 기대값 근사 가능
    • 이 때, KLD를 구하면
      • $D_{KL}(p\parallel q)\simeq \frac{1}{N}{\sum }_{n=1}^N\{-\ln q(x_n\mid \theta )+\ln p\left(x_n\right)\}$
    • 두 번째 항은 $\theta$에 대하여 독립, 첫 번째 항은 negative log likelihood

• mutual information

  • $I[x,y]=D_{KL}\left(p\right(x,y)\parallel p(x\left)p\right(y\left)\right)=-\int \int p(x,y)\ln \left(\frac{p\left(x\right)p\left(y\right)}{p(x,y)}\right)dxdy$
  • 두 변수가 얼마나 독립적인지 척도
  • $I[x,y]\ge 0$
  • $x$와 $y$가 서로 독립일 때 $I[x,y]=0$
  • $I[x,y]=H\left[x\right]-H[x\mid y]=H\left[x\right]-H[y\mid x]$