Skip to content

[statistics] Entropy, Relative Entropy and Mutual Information

Jump to bottom
Myungchul Shin edited this page Sep 22, 2021 · 29 revisions

Elements of Information Theory (Thomas M. Cover, Joy A. Thomas)

Chapter 2. Entropy, Relative Entropy and Mutual Information

Entropy

Entropy is Measure of uncertainty of a random variable

entropy_1

  • 위와 같이 정의한다면, H(X)의 단위는 bit이고 H(X)는 log(1/p(X))의 exectation이라고 할 수 있다. 또한, H(X) 는 항상 0보다 크거나 같다. X = { 0, 1 } 이고 p(X=0) = p 인 경우, X의 엔트로피 H(X) 혹은 H(p)는 아래 그래프와 같다. p=0 or 1 인 경우 엔트로피는 최소값이며, p=1/2인 경우 최대값이다. 엔트로피는 달리 "the minimum expected number of binary question"으로도 해석될 수 있다.

entropy_2

Joint Entropy and Conditional Entropy

  • discrete random variable X, Y에 대한 joint entropy는 아래와 같이 정의된다.
    entropy_3

  • conditional entropy는 아래와 같이 정의된다.
    entropy_4

  • conditional entropy H(Y|X)는 maximum entropy model에서 사용되는 아주 중요되는 수식. joint probability와 마찬가지로 joint entropy에도 chain rule이 적용되는데, 그것은 아래와 같다.
    entropy_5

    • 'H(X, Y) = H(X) + H(Y|X)' 이 chain rule은 'p(X, Y) = p(X) * p(Y|X)' 이 수식의 양변에 log를 취했을 때, 'log p(X,Y) = log p(X) + log p(Y|X)' 이와 같이 변형되는 성질을 이용해서 증명되기 때문에, joint probability chain rule의 연장선 상에 존재한다고 할 수 있다.
    • 만약, 어떤 random variable Z가 condition으로 주어진다면 H(X,Y)는 어떻게 될까?
      • H(X,Y | Z) = H(X|Z) + H(Y|X,Z)

Relative Entropy And Mutual Information

  • 어떤 (실제)확률 분포 p(X)와 어떤 (추정된)확률 분포 q(X)와의 거리는 어떻게 계산할 수 있을까?

    • 아래와 같이 정의된 Relative Entropy(혹은 KL-distance)를 사용하면 된다.
      entropy_7
    • p, q는 같은 random variable X에서 정의된 두 확률 분포이고, p에서 q로의 거리 D(p||q)는 위와 같이 정의된다. 그런데, 이 relative enropy는 D(p||q) != D(q||p) 이므로, 엄밀하게 말해서 거리는 아니지만(does not satisfy the triangle inequality) distance의 개념으로 많이 사용된다.

  • relative entropy(KL distance)가 같은 random variable X에 대한 두 확률 분포의 거리를 계산하는 척도라면 두개의 서로 다른 random variable X, Y에 대해서 각각 정의된 p(X), p(Y)에 대해서 X가 Y의 정보를 어느 정도 가지고 있는 지 판단하는 척도는 뭘까?

    • 이것은 아래와 같이 정의된 mutual information으로 계산할 수 있다.
      entropy_8
    • 즉, mutual information I(X;Y)는 p(X, Y)와 p(X) * p(Y)의 relative entropy이다. 복잡하긴 하지만, I(X;Y)는 entropy로 바꿔서 계산될 수도 있다.
      entropy_9
      entropy_10
    • 'I(X;Y) = H(X) - H(X|Y)' 이 식은 X, Y를 뒤바꿔도 성립된다. 따라서, 'I(X;Y) = H(Y) - H(Y|X)'
    • 앞에서 배운 chain rule 'H(X,Y) = H(X) + H(Y|X)' 를 이용하면 아래와 같이 정리된다.
    • I(X;Y) = H(X) + H(Y) - H(X, Y)
    • entropy와 mutual information의 관계는 아래 벤다이어그램과 같이 설명될 수 있다.
      entropy_11

  • 만약 어떤 두 명사 사이의 MI를 계산하려고 한다면?

    • 일반적으로 MI라고 하지만 정확하게는 PMI라고 한다.
    • point-wise mutual information
    • 출처는 http://register.itfind.or.kr/Report/200201/ETRI/ETRI-0899/ETRI-0899.pdf인데 지금은 접근이 안된다.
      entropy_12
    • 위 설명과 같이, 계산하면 된다. 여기서 문제는 p(x, y)를 계산하기 위한 대상 window를 추출하는 것과 그 사이즈를 정하는 것인데, 보통 window size = 1(즉, 바로 인접한 명사만 대상으로 한다)로 잡고 대량의 코퍼스에서 window를 추출하면 된다. 이렇게 추출된 데이터의 모양은 대략 아래와 같다.
 noun1 noun2
 noun1 noun2
 noun2 noun3
 noun3 noun10
 .....
  • 이렇게 데이터가 모아졌다면, 쉽게 PMI(noun1, noun2)를 계산할 수 있을 것다. (PMI가 계산되면 대략 어떤 임계치 이상만 '밀접한 관련이 있다'라고 정해서 뽑으면 된다)
  • PMI와 Pointwise t-score의 차이를 설명
    • MI와 t-score는 random variable X, Y에 대해서 계산되는 값이다.
    • 하지만, corpus linguistics에서는 두 단어 x, y 사이의 MI, t-score 값을 계산해서 사용해야한다.
    • PMI(Pointwise Mutual Information), Pointwise t-score 개념
    • PMI('검색', '엔진'), t-score('검색', '엔진')
    • 어떻게 계산하는가?
    • stubbs-1995 논문 참조
    • PMI의 경우는
    N : 전체 word의 수, 말 그대로 corpus에 존재하는 모든 단어의 수(중복허용)
PMI = log { p(x,y)/p(x)p(y) }
p(x,y) = freq(x,y) / N
p(x) = freq(x) / N

여기서 p(x,y)/p(x)p(y)를 아래와 같이 다시 써본다. 

{ freq(x,y)/N } / { { freq(x)/N } * { freq(y)/N } }

freq(x, y)/N = observed co-occurrence frequency = OCF
freq(x)/N * freq(y)/N  = expected co-occurrence frequency = ECF
    • Pointwise t-score의 경우는
    Pointwise t-score = {OCF - ECF} / { root(freq(x,y)) / N }
    • 결국, N, freq(x, y), freq(x), freq(y) 값을 알면, PMI와 Pointwise t-score 계산이 가능하다.

Cross-entropy and Perplexity

  • cross-entropy
  • perplexity
  • language model perplexity
  • 정의를 읽어보면, KL distance와 cross-entropy는 비슷하면서도 다르다는 것을 알 수 있다. 또한, 학습데이터(sample)로 학습한 어떤 모델 q와 empirical distribution p' 사이의 cross-entropy를 어떻게 계산하는 지도 알 수 있음.
하나의 sample에 대해서(예, { 비, 눈, 우박, 눈, 눈, 비 } ) : 

H(p', q) = -SUM{ p'(x) * log(q(x)) } for all x

여기서, p'(x)는 sample 사이즈가 N이고 x가 거기서 n번 등장했다면, 
maximum likelihood estimator로 간단하게 계산 가능하다. 
p'(x) = n/N ( empirical distribution, 예, p'(비) = 2/6 )
만약 1회씩만 등장했다면, 1/N으로 계산하면 된다.

H(p', q) = -SUM{ (1/N) * log(q(x)) } for all x

가끔 보면, 위와같이 계산되는 수식이 있는데, 이것은 uniform하게 등장한 경우다.

하나의 sample에 대해서 : 
binary cross entropy의 경우는 위 cross entropy 수식을 그대로 사용해도 되지만,
x가 가질 수 있는 값이 두개이므로 변수를 줄여서 표현 가능하다. 

H(p’, q) = -a * log(b) - (1-a) * log(1-b)
여기서 a = p'(x=1), b = q(x=1)

위에서는 하나의 sample에 대해서 cross entropy를 어떻게 계산하는 지 알아봤는데,
만약 M개의 sample이 있다면 어떻게 계산되는가?

cross entropy = 1/M * SUM( H(p’, q) )

softmax regression의 경우를 생각해보자. 
M개의 학습데이터가 있고, 개별 학습데이터에 대해서는
real output p'와 prediction p가 주어진다면 : 

H(p', q) = -SUM( p' * log(p) ) for all x

하나의 학습데이터에 대한 cross entropy는 이렇게 계산되며,
모든 학습데이터에 대해서는 이 값들을 전부 더해서 학습데이터의 개수 M으로 나눠주면 된다. 

cross entropy = 1/M * SUM( H(p', q) )
(batch size별로 계산 가능)

perplexity는 cross-entropy가 지수로 오게되는 measurement라서 
거의 cross-entropy와 비례한다고 생각하면 된다.
학습된 language model이 실제 distribution에 얼마나 근사할지를 계산할 때, 
보통 perplexity를 사용하는데, 
이것은 결국 cross-entropy를 최소화시키는 모델 q를 찾아내는 일이라 할 수 있다.

Machine Learning Fundamental

- information gain
: the more probable observations yield less information.
: information gained from observing x.
: h(x) = -log(p(x))
: the number of bits (if base 2) required to send a message x

- entropy
: average amount of information gained by observing a random draw from p(x).
: H(x) = E_x[-log(p(x))] = -sum(p(x)*log(p(x)))

- cross entropy
: same as entropy, but using estimated q instead of true p.
: H(p, q) = E_p[-log(q(x))] = -sum(p(x)*log(q(x)))

- relative entropy(KL distance)
: Using q instead of p requires 'H(p, q) - H(x)' extra bits.
: cross entropy - entropy
: KL(p||q) = H(p, q) - H(x) = -sum(p(x)*log(q(x)/p(x)))

- mutual information
: if x and y are independent variables, then their joint distribution is p(x, y) = p(x)p(y)
: KL(joint || independent) = KL(p(x, y)||p(x)*p(y))

이들 수식이 좀 헷갈리기 쉬운데, 위와 같은 순서로 설명하면 이해하기 편할 것 같다.
여기에 추가해서, 아래 개념까지 알아두면 좋다.

- joint entropy
- conditional entropy
- mutual information
: entropy - conditional entropy
Clone this wiki locally