5
$\begingroup$

If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$?

$\endgroup$
  • 2
    $\begingroup$ I'm not sure why this was voted down. It's a perfectly reasonable question. $\endgroup$ – Suresh Venkat Jul 1 '13 at 5:41
  • 1
    $\begingroup$ You will get a set of parameter resulting in a distribution $P_{parameters}$, that, had it been the true distribution, would have made the cost of assuming $P_{data}$ instead of $P_{distribution}$ minimal. An example: suppose you want to estimate the frequency of each character 'A','B' and 'C' in a stream in order to compress it with a Huffman code. if the parameter p has value 1, then $Prob('A') = 0.5, Prob('B') = 0.45, Prob('C') = 0.05$, and if parameter p has value 0, then $Prob('A') =.5, Prob('B') =0.5, Prob('C') = 0$. Also, $P_{data}(A)=0.5, P_{data}(B)=0.499, P_{data}(C) = 0.001$ $\endgroup$ – user8477 Jul 2 '13 at 22:42
  • $\begingroup$ Now it's clear that you should estimate the value of the parameter p to be 1, not 0, since you have 'C' characters in your data. But if you minimize $D_{KL} (P_{parameter}||P_{data})$ you will choose instead the value 0 for p. $\endgroup$ – user8477 Jul 2 '13 at 22:51
  • $\begingroup$ I should have thought of using a simple parameterized distribution like you provided. (Though I think your conclusion that $p$ ought to be 1 is not so clear if we make $P_{param}(C|p=0)=10^{-5}$). This gives me a good way to think about the question. $\endgroup$ – Eponymous Jul 3 '13 at 15:54
  • $\begingroup$ It is interesting to note that your distribution can't be used for the MLE version of the minimization because $D_{KL}(P||Q)$ is undefined if there exists an $\alpha$ such that $Q(\alpha) = 0$ and $P(\alpha) \neq 0$. Since $P_{data}(C)=10^{-3}$ and $P_{param}(C|p=0)=0$ this makes $D_{KL}(P_{data}(\cdot)||P_{param}(\cdot|p=0))$ undefined. $\endgroup$ – Eponymous Jul 3 '13 at 16:45
1
$\begingroup$

(Azoury and Warmuth, 2001) have shown that minimizing the KL-divergence between two exponential family distributions is the same as minimizing the Bregman divergence that corresponds to their cumulant function, i.e.

$KL(P_{F,\theta_1} || P_{F,\theta_2}) = D_F(\theta_1 || \theta_2)$

For $f = \nabla F$, and $F^*$ the Fenchel conjugate of $F$, we get the following nice relationship for Bregman divergences:

$D_F(\theta_1 || \theta_2) = D_{F^*}(f(\theta_2) || f(\theta_1))$

See Lemma 4 in this paper, which also has references to other work that discusses this connection. The above can also be written without the $f$ transfers on $\theta$. So, there is a simple relationship between these two losses, i.e. between minimizing with $\theta_1$ as the first argument or with $\theta_2$ as the first argument.

Also, I feel I should mention that we can generally talk about maximizing likelihood in terms of Bregman divergences and P(data | params), rather than KL-divergences on densities. The above linked paper shows that

$\max_\theta log \ p(data | \theta) = \min_\theta D_F(\theta | data)$

The relationship above where we swapped the two variables of interest in the loss has a correspondence here:

$p(\theta | data) \ p(data) = p(data | \theta) \ p(\theta)$

giving

$log \ p(\theta | data) = log \ p(data | \theta) + log \ p(\theta) - log \ p(data)$

Since we typically do not put a prior on data, we find that maximizing the likelihood of $p(\theta | data)$ (typically called the MAP estimate) corresponds to maximizing likelihood of the data with a prior on the parameters. Correspondingly, maximum likelihood is like the MAP estimate, with a non-informative, uniform prior on $\theta$.

K. S. Azoury and M. K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. 2001

$\endgroup$
  • 1
    $\begingroup$ It has been a while since I asked the question and the answer is pretty dense, so it will take a while before I can get the spare cycles to understand it. I am writing this comment so that you will understand I am grateful for your answer and will be looking at it as soon as I can to accept it or ask for clarification. $\endgroup$ – Eponymous Jul 21 '14 at 14:06

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.