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})$?
7
-
2$\begingroup$ I'm not sure why this was voted down. It's a perfectly reasonable question. $\endgroup$– Suresh VenkatJul 1, 2013 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$– user8477Jul 2, 2013 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$– user8477Jul 2, 2013 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$– EponymousJul 3, 2013 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$– EponymousJul 3, 2013 at 16:45
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
1
(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
-
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$ Jul 21, 2014 at 14:06