지난 포스팅의 [PML intro] Ch6 Information Theory (Sec.6.2 Relative entropy (KL divergence) - 1)에서는 분포 사이의 차이를 측정하는 방법 중 하나인 KL 발산의 정의와 예시에 대해서 알아보았습니다. 오늘 포스팅에서는 KL 발산의 중요한 성질로 KL 발산이 항상 0 이상임을 증명해보도록 하겠습니다.
이를 위해 저희는 옌센 부등식(Jensen's Inequality)를 사용해야합니다. 옌센 부등식은 임의의 볼록함수 $f$에 대해 다음을 만족하는 것을 의미합니다.
$$f \left( \sum_{i = 1}^{n} \lambda_{i} x_{i} \right) \le \sum_{i = 1}^{n} \lambda_{i} f(x_{i}) \Rightarrow f(\mathbb{E}[x]) \mathbb{E}[f(x)]$$
여기서 $\lambda_{i} \ge 0$이고 $\sum_{i = 1}^{n} \lambda_{i} = 1$입니다. 이는 간단하게 설명하면 볼록함수 $f$라면 함숫값의 산술평균값 (우항)이 산술평균값의 함숫값 (좌항)보다 더 크거나 같다는 것을 의미합니다. 여기서 $f(x) = \log (x)$라고 가정하겠습니다. 그러면 이는 오목 함수(concave function)이기 때문에 볼록함수와는 반대의 부등식을 얻게 됩니다. 즉, $\log \mathbb{E}_{x}[g(x)] \ge \mathbb{E}_{x} [\log g(x)]$가 되죠. 이 부등식이 앞으로의 증명에서 가장 중요한 힌트로 활용됩니다.
정리1 [정보 부등식 (Information Inequality)]. $\mathcal{D}_{\mathcal{KL}} (p || q) \ge 0$이며 등호가 성립하는 것은 $p = q$일 경우이다.
제일 먼저 집합 $A = \{x | p(x) > 0\}$를 $p(x)$의 지지집합 (support set)이라고 가정하겠습니다. 이는 확률의 특성상 0인 곳에서는 이후에 수식의 전개가 애매해지기 때문에 0보다 큰 양수 영역만 고려하겠다는 의미이죠. 여기서, $\log$ 함수의 오목성과 옌센 부등식을 사용하면 다음과 같은 결과를 얻을 수 있습니다.
$$\begin{align*} -\mathcal{D}_{\mathbb{KL}} (p || q) = -\sum_{x \in A} p(x) \log \frac{p(x)}{q(x)} \\ &= \sum_{x \in A} p(x) \log \frac{q(x)}{p(x)} \\ &\le \log \sum_{x \in A} p(x) \cdot \frac{q(x)}{p(x)} \\ &= \log \sum_{x \in A} q(x) \\ \le \log \sum_{x \in \mathcal{X}} q(x) = \log 1 = 0 \end{align*}$$
결론적으로 $-\mathcal{D}_{\mathbb{KL}} (p || q) \le 0 \Rightarrow \mathcal{D}_{\mathbb{KL}} (p || q) \ge 0$이 됩니다. 마지막으로 언제 등호가 성립하는 지 확인해보도록 하겠습니다. $\log (x)$는 엄밀한 오목함수 (strictly concave function)이기 때문에 위 수식에서 등호가 성립하기 위해서는 $\frac{q(x)}{p(x)} = c$가 되는 어떤 상수 $c$가 존재해야합니다. 따라서, $p(x) = cq(x)$이어야하는 것으로 전체공간 $\mathcal{X}$ 중에서 $A$가 차지하는 비율을 의미합니다. 또한, 증명 마지막에 등호가 성립하기 위해서는 $\sum_{x \in A} q(x) = \sum_{x \in \mathcal{X}} q(x) = 1$이어야하죠. 이는 곧 $q(x)$가 $A$ 밖에서는 0이라는 뜻이므로 위의 상수 $c = 1$이여야함을 의미하죠. 결과적으로 $\mathcal{D}_{\mathbb{KL}} (p || q) = 0 \Leftrightarrow p(x) = q(x)$가 됩니다.
따름정리1.1 균등분포는 엔트로피를 최대화한다. 즉, $\mathbb{H}(X) \le \log |\mathcal{X}|$로 $|\mathcal{X}|$는 $X$가 가질 수 있는 상태의 개수를 의미하며 등호가 성립하기 위해서는 $p(x)$가 균등분포여야한다.
이는 $u(x) = \frac{1}{|\mathcal{X}|}$라고 두겠습니다. 그러면 $u(x)$는 $\mathcal{X}$ 위의 균등분포로 정의됩니다. 그러면 다음과 같이 식을 풀어서 작성할 수 있죠.
$$\begin{align*} 0 \le \mathcal{D}_{\mathbb{KL}} (p || u) \\ &= \sum_{x} p(x) \log \frac{p(x)}{u(x)} \\ &= \sum_{x} p(x) \log p(x) - \sum_{x} p(x) \log u(x) \\ &= - \mathbb{H}(X) + \log |\mathcal{X}| \Rightarrow \mathbb{H}(X) \le \log |\mathcal{X}| \end{align*}$$
그리고 $\mathcal{D}_{\mathbb{KL}} (p || u) = 0$이 되는 경우 즉, $p(x) = u(x)$인 경우에만 등호가 성립하므로 균등분포가 엔트로피를 최대화하는 분포임을 알 수 있습니다.
