read

KL-divergence

초보를 위한 정보이론 안내서 - Entropy란 무엇일까 SERIES 1/3
초보를 위한 정보이론 안내서 - Cross Entropy 파헤쳐보기SERIES 2/3
초보를 위한 정보이론 안내서 - KL divergence ✓ SERIES 3/3

우리가 지난 시간에 살펴봤던 cross entropy, $H(p,q)$ 에 이어서 이번 글에서는 KL-divergence에 대해 살펴보겠습니다. 사실 단어자체는 cross-entropy만큼 많이 보이지만, 그 개념은 낯섭니다. 하지만 이번 글을 통해서 KL-divergence가 전혀 낯선 개념이 아니라는 것을 볼 수 있습니다.

Kullback-Leibler divergence

풀네임은 쿨백-라이블러 divergence(발산)입니다. 줄여서 KL-divergence라고 부르곤 합니다. 위키피디아에 나와있는 정의를 살펴보면 이렇게 나옵니다.

쿨백-라이블러 발산(Kullback–Leibler divergence, KLD)은 두 확률분포의 차이를 계산하는 데에 사용하는 함수로, 어떤 이상적인 분포에 대해, 그 분포를 근사하는 다른 분포를 사용해 샘플링을 한다면 발생할 수 있는 정보 엔트로피 차이를 계산한다. 상대 엔트로피(relative entropy), 정보 획득량(information gain), 인포메이션 다이버전스(information divergence)라고도 한다.

두 확률분포의 차이를 계산한다고 나와있는데, 두 분포의 무엇의 차이를 계산하는 것일까요? 바로 엔트로피입니다. 두 분포가 관여하는 개념이었던 cross entropy가 떠오릅니다. 이 cross entropy로부터 KL-divergence가 무엇인지 수식으로 유도해보겠습니다.

Derivation of the KL-divergence
Cross entropy, $H(p,q)$를 전개해보면 그 안에 이미 확률분포 $p$의 엔트로피가 들어있습니다. 그 $H(p)$에 무언가 더해진 것이 cross entropy입니다. 이때 이 무언가 더해지는 것이 바로 “정보량 차이”인데, 이 정보량 차이가 바로 KL-divergence입니다. 직관적으로 정리를 해보겠습니다. KL-divergence는 $p$와 $q$의 cross entropy에서 $p$의 엔트로피를 뺀 값입니다. 결과적으로 두 분포의 차이를 나타냅니다.

$KL(p \| q) = H(p,q) - H(p)$

KL-divergence의 정확한 식은 이렇습니다. 대개 $D_{KL}(p | q)$ 또는 $KL( p| q)$로 표현합니다.

$KL( p \ \| \ q) = \begin{cases} {\displaystyle \sum_{i} p_i \log \frac{p_i}{q_i}} \,\,또는\,\,-{\displaystyle \sum_{i} p_i \log \frac{q_i}{p_i}} \ \ (이산형) &\\[2ex] {\displaystyle \int p(x) \log {\frac {p(x)}{q(x)}}dx} \,\,또는\,\, -{\displaystyle \int p(x) \log {\frac {q(x)}{p(x)}}dx}\ \ (연속형)&\\[2ex] \end{cases}$

우리가 대개 cross entropy를 minimize 하는 것은, 어차피 $H(p)$는 고정된 상수값이기 때문에 결과적으로는 KL-divergence를 minimize 하는 것과 같습니다.

KL-divergence의 특성

KL-divergence의 몇 가지 특징들이 있는데, 대표적인 것이 2가지입니다.

$KL( p| q) \ge 0$
$KL( p| q) \neq KL(q | p)$
- “KL-divergence는 거리 개념이 아니다”라는 말로 매우 자주 등장합니다

0 이상이다

우선 직관적으로 생각해보면 당연히 0이상일 수밖에 없습니다. 왜냐하면 KL-divergence는 Cross-entropy에서 entropy를 뺀 값이기 때문입니다. Cross entropy는 아무리 낮아져봤자 entropy가 lower bound입니다. $H(p,q)$는 $q$가 $p$가 될 때 그 최솟값을 가진다는 사실을 떠올리면 됩니다. 그러므로 $H(p,q)-H(p)$는 아무리 작아봤자 0입니다. 이런 직관적 방법도 있지만 대개 KL-divergence가 0이상이라는 사실을 증명할 때는 Jensen’s Inequality(젠슨 부등식)을 사용합니다.

Jensen’s Inequality

이 부등식을 사용하려면 우선 convex function, 소위 말하는 아래로 볼록한 함수를 엄밀하게 정의해보겠습니다. 위 그림을 위키피디아에서 가져와봤습니다. 두 점 $x_1, x_2$와 그 사이에 있는 점 $tx_1 + (1-t)x_2$을 생각해보겠습니다($t \in $ [0,1]). 가운데 점의 식은 두 점 $x_1, x_2$의 weighted sum입니다. 그리고 이제 그 가운데 점을 함수 $f(x)$에 넣었을 때 나온 값 $f(tx_1 + (1-t)x_2)$와 두 점 $x_1, x_2$를 각각 $f(x)$에 넣은 값의 weighted sum인 $t(f(x_1))+(1-t)f(x_2)$ 을 비교합니다. Convex function이라면 이 두 가지 값을 크기 비교했을 때 언제나 이런 결과가 나옵니다.

$f(tx_1 + (1-t)x_2) \le t(f(x_1))+(1-t)f(x_2)$

이를 확률론의 맥락에서는 $X$가 random variable이고, $f(\cdot)$가 convex function일 때, 이렇게 표현합니다.

$f \left(\operatorname {E} [X]\right)\leq \operatorname {E} \left[f (X)\right]$

이제 준비운동을 다 마쳤으니 KL-divergence에 관련해서 증명을 해보겠습니다. 우리의 KL-divergence 식에 있는 $-log$ 를 $f(x)$로 두고 가운데의 weighted sum 또는 $E[X]$를 $\frac{q_i}{p_i}$로 두면 Jensen’s 부등식에 넣을 수 있습니다.

$KL(p\|q)=−∫p(x)\log{\frac{q(x)}{p(x)}}dx≥−\log ∫p(x)\frac{q(x)}{p(x)}dx= -\log ∫q(x)dx = -\log 1 = 0 \\[2ex] \\ \ \\ \\ \ \\ \therefore KL(p\|q) \ge 0$

따라서 KL-divergence은 non-negative의 특성을 가집니다.

거리 개념이 아니다

KL-divergence를 검색해보면 알겠지만 가장 귀에 딱지가 앉도록 들리는 말이 바로 “KL-divergence는 거리 개념이 아니다!”입니다. 그러면서 대개 뒤따라오는 말은 “KL-divergence는 asymmetric하다”입니다. 무엇이 비대칭적이냐면 KL-divergence에서 p와 q를 바꾼 값과 원래의 값이 다르다는 점이 비대칭적입니다. 대칭적이라면 결과값이 같아야 합니다. 그 이유는 제가 위에서 다뤘던 식으로만 생각해도 쉽습니다. KL-divergence의 식을 살펴보겠습니다.

$\begin{align} KL(p\|q) & = H(p,q) - H(p) \\ & \neq H(q, p) - H(q) = KL(q\|p) \\ \end{align} \\ \ \\ \\ \ \\ \therefore KL(p\|q) \neq KL(q\|p)$

만약에 두 확률분포 사이의 거리라면 $p$에서 $q$ 사이의 거리나 $q$에서 $p$ 사이의 거리나 같아야 합니다. 하지만 KL-divergence는 그렇지 않습니다. 이런 이유 때문에 KL-divergence는 거리 개념(distance metric)이 아니라고 하는 것입니다. 하지만 거리 개념처럼 쓸 수 있는 방법이 존재합니다. 바로 Jensen-Shannon divergence입니다.

Jensen-Shannon divergence

$JSD(p\|q) = \frac{1}{2}KL(p\|M) + \frac{1}{2}KL(q\|M) \\ where, M = \frac{1}{2}(p+q)$

방법은 매우 간단합니다. KL-divergence를 2가지를 구하고는 평균을 내는 방식입니다. 이렇게 간편하게 쓸 수 있지만 Jensen-Shannon divergence는 KL-divergence만큼 자주 쓰이지 않습니다.

KL-divergence와 log likelihood

우리가 전체를 알 수 없는 분포 $p(x)$ 에서 추출되는 데이터를 우리가 모델링하고 싶다고 가정해보겠습니다. 우리는 이 분포에 대해 어떤 학습 가능한 parameter $θ$의 parametric distribution $q(x \lvert θ)$ 를 이용해 근사시킨다고 가정해보겠습니다. 이 $θ$ 를 결정하는 방법 중 하나는 바로 $p(x)$와 $q(x \lvert θ)$ 사이의 KL-divergence 를 최소화시키는 $θ$ 를 찾는 것입니다. 우리가 $p(x)$ 자체를 모르기 때문에 이는 직접 해내기는 불가능합니다. 하지만 우리는 이 $p(x)$에서 추출된 몇 개의 샘플 데이터(training set)는 압니다($x_n$, for $n=1, … , N$). 따라서 $p(x)$에 대한 기댓값은 그 샘플들의 평균을 통해 구할 수 있습니다.

$KL(p\|q) \simeq \frac{1}{N} \sum_{n=1}^ N \{ -\ln q(x_n| \theta) + \ln p(x_n) \}$

$\ln p(x_n)$ 는 $θ$에 대해 독립이고, $-\ln q(x_n \lvert θ)$ 는 training set으로 얻은 $ q(X \lvert θ)$ 분포 하에서 $θ$ 에 대한 negative log likelihood 입니다. 그러므로 KL-divergence를 minimize하는 것이 likelihood를 maximize하는 것과 같다는 것을 알 수 있습니다. [Pattern Recognition and Machine Learning, C.M. Bishop 참조]

정리

Cross entropy는 negative log likelihood와 같습니다. 그래서 cross entropy를 minimize하는 것이 log likelihood를 maximize하는 것과 같습니다. 그리고 확률분포 $p,q$에 대한 cross entropy는 $H(p)+KL(p|q)$ 이므로 KL-divergence를 minimize하는 것 또한 결국 log likelihood를 maximize하는 것과 같습니다.

초보를 위한 정보이론 안내서 - Entropy란 무엇일까 SERIES 1/3
초보를 위한 정보이론 안내서 - Cross Entropy 파헤쳐보기 SERIES 2/3
초보를 위한 정보이론 안내서 - KL divergence 쉽게 보기 ✓ SERIES 2/3

Information theory

초보를 위한 정보이론 안내서 - KL divergence 쉽게 보기 SERIES 3/3