4
$\begingroup$

Consider $p(x)$ and $q(x)$ are two pdfs of $X$, where $q(x)$ is a Gaussian distribution with the following form

$$q(x) = \frac{1}{\sqrt{2\pi\sigma_q^2}} \exp\left(-\frac{x^2}{2\sigma_q^2}\right).$$

Additionally, the variance of $x$ under pdf $p(x)$ is given (constrained), say $\sigma_p^2$, where $\sigma_p \neq \sigma_q$. Note that $p$ can be any pdf which is Lebesgue integrable.

Then which distribution $p(x)$ can minimize the KL-divergence $D(p\|q)$? The KL-divergence is defined as follows.

$$D(p\|q) = \int_{-\infty}^\infty p(x) \log\frac{p(x)}{q(x)} \, dx.$$

Thanks!

Note: If there is no variance constraint of $p(x)$, the answer is simply $p = q$ (a.e.). But this question is based on $\sigma_p \neq \sigma_q$. How to find the minimizer $p(x)$? Thanks a lot!

$\endgroup$
2
  • 3
    $\begingroup$ It seems that a logarithm is missing in your definition of KL-divergence? $\endgroup$ – Cave Johnson Jul 11 '17 at 3:18
  • $\begingroup$ @CaveJohnson Thanks very much for pointing out the typo :-) $\endgroup$ – Ryan Jul 11 '17 at 3:21
5
+50
$\begingroup$

Hint. The optimal distribution is still Gaussian. In this case, the optimal Gaussian parameter is easily calculated. We show this by Lagrange multipliers: $$D^*(p\|q)=\int p(x)\log\frac{p(x)}{q(x)}dx-\lambda_1\left(\int x^2p(x) dx-\mu_p^2-\sigma_p^2\right)\\-\lambda_2\left(\int xp(x)dx-\mu_p\right)-\lambda_3\left(\int p(x)dx-1\right)$$ By calculus of variation we get $$ \log\frac{p(x)}{q(x)}+1-\lambda_1x^2-\lambda_2x-\lambda_3=0 $$ From which we may conclude $p(x)=q(x)e^{\lambda_1x^2+\lambda_2x+\lambda_3-1}$, hence a Gaussian.

$\endgroup$
7
  • 1
    $\begingroup$ write $p(x)dx$ as $dp(x)$ and then take derivative wrt $p(x)$. $\endgroup$ – Dhruv Kohli - expiTTp1z0 Jul 11 '17 at 6:22
  • $\begingroup$ @expiTTp1z0 Thanks very much for your help :-) $\endgroup$ – Ryan Jul 11 '17 at 6:28
  • $\begingroup$ @CaveJohnson Thanks very much for your answer. I can just derive $\int \left[\log \frac{p(x)}{q(x)} + 1 - \lambda_1 x^2 - \lambda_2 x - \lambda_3\right] dx= 0$. Could you show me how to get the second equation? Thanks a lot! $\endgroup$ – Ryan Jul 13 '17 at 7:00
  • 1
    $\begingroup$ @Ryan It's a standard technique in calculus of variations. Take an arbitrary function $\phi$ and consider function $p_\alpha=p+\alpha\phi$. Since $D(p_\alpha\|q)$ attains its extremum at $p$, i.e. when $\alpha=0$, Fermat's principle yields $\partial D(p_\alpha\|q)/\partial \alpha\big|_{\alpha = 0}=0$. This means $$\int \phi\left[\log \frac{p(x)}{q(x)} + 1 - \lambda_1 x^2 - \lambda_2 x - \lambda_3\right]=0$$ holds for arbitraty $\phi$, hence $\left[\log \frac{p(x)}{q(x)} + 1 - \lambda_1 x^2 - \lambda_2 x - \lambda_3\right]=0$ everywhere. $\endgroup$ – Cave Johnson Jul 13 '17 at 8:07
  • $\begingroup$ Thanks a lot for the detailed explanations. I got a mistake when I applying the calculus of variation. Sorry... $\endgroup$ – Ryan Jul 13 '17 at 8:31
2
$\begingroup$

$$\begin{align}D(p||q) &= E_{p}\left(\log\frac{p(x)}{q(x)}\right) \\ &= E_{p}(\log p(x)) - E_{p}\left(\log q(x)\right)\\ &= E_{p}(\log p(x)) - E_{p}\left(\log\left(\frac{\exp\left(-\frac{x^2}{2\sigma_q^2}\right)}{\sqrt{2\pi}\sigma_q}\right)\right)\\ &= E_{p}(\log p(x)) + \log(\sqrt{2\pi}\sigma_q) + E_{p}\left(\frac{x^2}{2\sigma_q^2}\right)\\ &= E_{p}(\log p(x)) + \log(\sqrt{2\pi}\sigma_q) + \frac{\sigma_p^2 + \mu_p^2}{2\sigma_q^2}\end{align}$$

$$\begin{align}D(p||q) \geq 0 &\iff E_{p}(\log p(x)) + \log(\sqrt{2\pi}\sigma_q) + \frac{\sigma_p^2 + \mu_p^2}{2\sigma_q^2} \geq 0\\ &\iff H(p) \leq \log(\sqrt{2\pi}\sigma_q) + \frac{\sigma_p^2 + \mu_p^2}{2\sigma_q^2} = \log\left(\sqrt{2\pi e^{(\sigma_p^2 + \mu_p^2)/\sigma_q^2}}\sigma_q\right)\end{align}$$

$$D(p||q) = 0 \iff H(p) = \log\left(\sqrt{2\pi e^{(\sigma_p^2 + \mu_p^2)/\sigma_q^2}}\sigma_q\right)$$

Any distribution $p(x)$ with mean $0$ and variance $\sigma_p^2$, which has an entropy of $\log\left(\sqrt{2\pi e^{(\sigma_p^2 + \mu_p^2)/\sigma_q^2}}\sigma_q\right)$, will make $D(p||q) = 0$.

If one would like to minimize the KL-divergence and maximize the entropy of the distribution $p(x)$, then the $p(x)$ should be chosen to be a gaussian distribution with mean $0$ and variance $\sigma_p^2$.

Edit: I think the answer by @CaveJohnson is more appropriate than mine. However, I will keep my answer here for review later.

$\endgroup$
11
  • $\begingroup$ Thanks for your answer. [+1] Sorry, my question is not stated very clearly. I mean $\sigma_p$ is a given number (e.g., $\sigma_p = 1 + \sigma_q$), where $\sigma_p \neq \sigma_q$. I have already changed the description :-) Thanks! $\endgroup$ – Ryan Jul 11 '17 at 4:57
  • $\begingroup$ Then you cannot minimize $D(p||q)$ since it will be a fixed quantity. $\endgroup$ – Dhruv Kohli - expiTTp1z0 Jul 11 '17 at 4:59
  • 1
    $\begingroup$ This wiki link will help: en.wikipedia.org/wiki/… $\endgroup$ – Dhruv Kohli - expiTTp1z0 Jul 11 '17 at 5:03
  • 1
    $\begingroup$ Thanks :-) The variance is fixed, but the distribution is not. I also guess the minimizer is Gaussian, but I don't know how to prove it... $\endgroup$ – Ryan Jul 11 '17 at 5:04
  • 1
    $\begingroup$ Ohh. You meant that. Now, I understand. I will edit my answer then. $\endgroup$ – Dhruv Kohli - expiTTp1z0 Jul 11 '17 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.