# What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

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})$?

• I'm not sure why this was voted down. It's a perfectly reasonable question. – Suresh Venkat Jul 1 '13 at 5:41
• 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$ – user8477 Jul 2 '13 at 22:42
• 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. – user8477 Jul 2 '13 at 22:51
• 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. – Eponymous Jul 3 '13 at 15:54
• 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. – Eponymous Jul 3 '13 at 16:45

## 1 Answer

(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

• 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. – Eponymous Jul 21 '14 at 14:06