[Statistics] Entropy, Cross Entropy & KL divergence

Skywalk님의 블로그를 보고 정리한 내용입니다.

Quantity of information

정보량(Quantity of information)은 어떤 내용을 표현하기 위해 물어야 하는 최소한의 질문 개수로 생각할 수 있다. 예를 들어 알파벳 한 글자를 0과 1로 전송해야 한다고 하면 어떻게 해야 할까? 최적의 정보량으로 보내려면 그 글자가 26개의 알파벳 중 앞쪽 절반(a ~ m)에 속하는지, 뒤족 절반(n ~ z)에 속하는지 묻는거다. 이에 대한 답을 0 또는 1로 할 수 있고, 이렇게 최소 5번만 물으면 글자 하나를 알아낼 수 있다. 수학적으로 다음과 같이 표현할 수 있다.

\[2^{질문개수} = 26\] \[질문개수 = \log_2(26)\]

정보량을 일반화 하면 다음과 같다.

\[\begin{align} I &= n\log(s) \\ &= \log(s^n) \end{align}\]

$n$는 보내려는 문자열의 길이, $s$는 각 선택에서 가능한 경우의 수(알파벳의 경우 26)이다. 따라서 $s^n$는 총 경우의 수가 된다. 이렇게 어떠한 사건에 대한 정보를 수치화한 것을 정보량이라 한다.

정보량은 어떠한 사건이 일어날 확률과 반비례한다. 이는 수식으로 아래와 같이 표현된다.

\[\begin{align} I(X) &= \log(\frac{1}{p(x)}) \\ &= -\log(p(x)) \end{align}\]

정보량에 로그함수가 사용되는 이유는 첫 번째로 정보에 필요한 최소한의 자원(질문)을 표현할 수 있기 때문이다. 확률이 $\frac{1}{4}$인 사건을 2진수로 표현하면 $-\log_2(\frac{1}{4}) = 2$ bit로 표현할 수 있다. 2는 여기서 필요한 최소한의 질문 수이다.

두 번째는 log함수의 additive한 성질 때문이다. 독립 사건 A, B에 대해 두 사건이 동시에 일어날 확률 $P(A)P(B)$의 정보량 $I(A, B)$는 $I(A) + I(B)$로 쪼개질 수 있다.

\[\begin{align} I(A, B) &= -\log(P(A)P(B)) \\ &= -\log(P(A)) - \log(P(B)) \\ &= I(A) + I(B) \end{align}\]

Entropy

예를 들어 문자열을 출력하는 2개의 기계 $X$와 $Y$가 있다고 하자. 기계 $X$는 a, b, c, d를 각각 0.25의 확률로 출력한다. 반면 기계 $Y$는 a: 0.5, b: 0.125, c: 0.125, d: 0.25의 확률로 출력한다.

기계 $X$가 출력하는 문자 1개를 구분하기 위해 필요한 최소한의 질문 수는 2이다. 확률이 모두 0.25이므로 반 씩 나누어 질문하면 되기 때문이다. 기계 $Y$의 경우 $X$의 방식은 비효율적이다. 왜냐하면 a가 이미 50%의 확률을 갖기 때문이다. 그러므로 처음에 a인지, (b,c,d) 중에 있는지 묻는게 낫다. 이후 (b,c,d)중에선 d가 0.5중에 0.25로 50%의 확률을 가지므로 d인지, (b,c) 중에 있는지 물으면 된다. 기계 $Y$의 최소 질문 수는 앞서 $X$처럼 계산되지 않느다. 대신 a가 나타날 확률에 a를 추려내기 위한 질문 수 (처음 1개의 질문으로 추려낼 수 있다.)를 곱하고, b도 b가 나타날 확률에 b를 추려내기 위한 질문의 수(3번의 질문으로 특정된다.)를 곱하며 나머지 c,d에 대해서도 똑같이 한다. 이를 식으로 나타내면 다음과 같다.

\[p(a) \cdot 1 + p(b) \cdot 3 + p(c) \cdot 3 + p(d) \cdot 2 = 1.75\]

기계 $Y$에서 글자 1개를 추려내려면 평균적으로 1.75개의 질문이 필요하다. 결과적으로 기계 $Y$가 기계 $X$보다 더 적은 정보량을 생산한다고 볼 수 있다. 이는 기계 $Y$의 불확실성이 더 적기 때문이다. 기계 $X$와 같이 모든 사건이 같은 확률로 일어나는 것이 가장 불확실하다. 이를 식으로 정립한 것이 Claude Shannon으로 Shannon은 이 불확실성 측정을 엔트로피라 불렀으며 단위를 bit로 하였다.

기계 $Y$의 평균 질문 수(정보량)를 계산하는 식은 각각이 발생할 확률과 관련있다.
$p(a): 0.5=1/2, p(b): 0.125=1/8, p(c): 0.125=1/8, p(d): 0.25=1/4$ 이므로 각각의 확률에 대한 정보량을 구하면

\[\log_2 \left(\frac{1}{1/2}\right) = 1, \log_2 \left(\frac{1}{1/8}\right) = 3, \log_2 \left(\frac{1}{1/4}\right) = 2\]

가 된다. 즉 정보량에서의 가능한 경우의 수는 해당 사건이 발생할 확률의 역수가 되고 위에서 구해진 정보량에 확률을 곱한 값이 엔트로피가 된다. Shannon의 엔트로피 식은 이산확률분포일 때를 가정하므로 시그마를 통해 아래와 같이 엔트로피 식이 일반화 된다.

\[\begin{align} H &= \sum_i p_i \log \left( \frac{1}{p_i} \right) \\ &= - \sum_i p_i \log(p_i) \end{align}\]

엔트로피는 최적의 전략 하에 특정 사건을 예측하는 데 필요한 질문 수를 의미한고, 다른 말로는 질문 수에 대한 기댓값(Expected Value) 이 된다. 엔트로피가 감소한다는 것은 해당 사건을 특정하기 위해 필요한 질문의 수가 줄어든다는 것을 의미하고, 질문의 수가 줄어든다는 것은 정보량이 줄어든다는 의미가 된다.

Cross Entropy

이번에도 Entropy와 동일한 기계 2개로 예를 들어보자. 이번엔 기계 $X$를 $Q$로, 기계 $Y$를 $P$라 지칭하겠다. 엔트로피를 구할 때 보았듯이 각 기계에 맞는 최적화된 전략은 엔트로피 식에 적용했을 때 계산된다. 엔트로피라는 것은 최적화된 전략 하에서의 질문 수에 대한 기댓값이기 때문이다.

하지만 다른 전략을 쓰면 어떻게 될까? 전략 $Q$를 기계 $P$에 적용해보자. 엔트로피 식은 다음과 같이 바뀐다.

\[0.5 \times 2 + 0.125 \times 2 + 0.125 \times 2 + 0.25 \times 2 = 2\]

기존에 1.75였던 엔트로피에 비해 0.25가 더 커졌다. 이러한 값이 cross entropy값 이다. 크로스 엔트로피는 어떠한 문제에 대해 특정 전략을 쓸 때 예상되는 질순 수에 대한 기댓값이다. 여기서 전략 또한 확률분포로 표현된다. 전략 $Q$의 경우는 a,b,c,d의 확률이 모두 0.25인 확률분포이다. 마찬가지로 문제역시 확률분포로 표현된다. 어떠한 문제에 대한 최적의 전략을 사용할 때 크로스 엔트로피는 최소가 된다. 이는 결국 두 확률분포에 대한 식이다.

cross entropy는 수식으로 적으면 다음과 같다.

\[\begin{align} H(p, q) &= \sum_i p_i \log \left( \frac{1}{q_i} \right) \\ &= - \sum_i p_i \log q_i \end{align}\]

대개 머신러닝에서의 cross entropy는 $p_i$가 특정 확률에 대한 참 또는 목표 확률이고, $q_i$가 현재 학습한 확률값이다. 앞선 예로는 $p = [0.5, 0.125, 0.125, 0.25]$이고, $q = [0.25, 0.25, 0.25, 0.25]$인 셈이다. 따라서 우리가 $q$를 학습하고 있는 상태라면 $p$에 가까워질수록 cross entropy loss는 줄어들게 된다.

크로스 엔트로피는 이산형이 아니라 연속형의 확률분포에 대해서 integral을 사용한다.

\[- \int p(x) \log q(x) dx\]

Binary Cross Entropy

\[-y \log \hat{y} - (1 - y) \log (1 - \hat{y})\]

logistic regression에서 흔히 볼 수 있는 cost function이다. 이 식 역시 cross entropy로 계산된 식이다. Binary classification에서는 0 또는 1로 두 가지 class를 구분한다. 이를 수식으로 표현하면 $y \in {0, 1}$이다. 어떤 대상이 1이라고 분류할 확률 $q_{y=1}$을 $\hat{y}$라 하자. 그렇다면 어떤 대상을 0으로 predict할 확률 $q_{y=0}$은 $(1 - \hat{y})$가 된다. 실제로 어떠한 대상이 0 또는 1일 확률 (ground truth) $p_{y=1}, p_{y=0}$은 각각 $y$와 $(1 - y)$가 된다. 정리를 하면 다음과 같다.

\[\begin{align} p &= [y, 1 - y] \\ q &= [\hat{y}, 1 - \hat{y}] \end{align}\]

이 두 확률분포에 대한 cross entrop 식의 sigma를 풀어서 쓰면 Binary Cross Entropy 식이 나온다.

KL Divergence

KL Divergence(Kullback-Leibler divergence)는 두 확률분포의 차이를 계산하는 데에 사용하는 함수로, 이상적인 분포에 대해, 그 분포를 근사하는 다른 분포를 사용해 샘플링 한다면 발생할 수 있는 엔트로피의 차이를 계산한다.

KL Divergence는 cross entropy로부터 다음과 같이 유도된다.

\[\begin{align} H(p, q) &= -\sum_i p_i \log q_i \\ &= - \sum_i p_i \log q_i - \sum_i p_i \log p_i + \sum_i p_i \log p_i \\ &= H(p) + \sum_i p_i \log p_i - \sum_i p_i \log q_i \\ &= H(p) + \sum_i p_i \log \frac{p_i}{q_i} \end{align}\]

cross entropy $H(p, q)$를 전개한 결과를 보면 확률분포 $p$의 엔트로피가 있다. 그 $H(p)$에 무언가 더해진 것이 cross entropy임을 알 수 있는데 그 더해지는 값이 정보량 차이인 KL Divergence이다. 결과적으로 KL Divergence는 $p$와 $q$의 cross entropy에서 $p$의 엔트로피를 뺀 값이다.

\[KL(p \parallel q) = H(p, q) - H(p)\]

따라서 KL Divergence의 정확한 식은 다음과 같다.

\[KL(p \parallel q) = \begin{cases} \sum_i p_i \log \left( \frac{p_i}{q_i} \right) & \\ \int p(x) \log \left( \frac{p(x)}{q(x)} \right) dx \end{cases}\]

$p$의 엔트로피인 $H(p)$는 고정된 상수값이기 때문에 cross entropy를 최소화 하는건 KL Divergence를 최소화 하는 것과 동일하다.

KL-divergence는 다음과 같은 특성이 있다.

1. $KL(p \vert q) \ge 0$
2. $KL(p \vert q) \neq KL(q \vert p)$

첫 번째는 KL Divergence가 0 이상이다는 점이다. KL Divergence는 cross entropy에서 entropy를 뺀 값이기 때문에 아무리 값이 낮아져 봤자 entropy가 lower bound가 된다. $H(p,q)$는 $q$가 $p$가 될 때 최솟값을 가지므로, $H(p,q) - H(p)$는 아무리 작아도 0이다.

두 번째는 KL Divergence가 거리 개념이 아니다는 말로도 자주 나온다. 즉 KL Divergence는 asymmetric하다는 것인데, KL Divergence는 $p$와 $q$를 바꾼 값과 원래의 값이 다르다는 점이 비대칭적이다. 이는 다음과 같이 확인할 수 있다.

\[\begin{align} KL(p \parallel q) &= H(p,q) - H(p) \\ &\neq H(q,p) - H(q) = KL(q \parallel p) \\ &\therefore KL(p \parallel q) \neq KL(q \parallel p) \end{align}\]

만약 KL Divergence가 두 확률분포 사이의 거리를 의미하면 $p$에서 $q$ 사이의 거리나 $q$에서 $p$사이의 거리나 값이 같아야 한다. 하지만 KL Divergence는 그렇지 않으므로 KL Divergence는 distance metric이 아니다.