Answers.Body: <p>The distribution being conditional or not does not change the notion of KL divergence.</p>
  <p>Indeed, given <span class="math-container">$p(x) \sim N(\mu_1, \sigma_1^2)$</span> and <span class="math-container">$q(x) \sim N(\mu_2, \sigma_2^2)$</span>, the KL can be estimated in closed form.</p>
  <p>However, the KL between <span class="math-container">$p(y|x) \sim N(\mu_1, \sigma_1^2)$</span> and <span class="math-container">$q(y|x) \sim N(\mu_2, \sigma_2^2)$</span> shares the same closed form with the previous one</p>
  <p>The only thing you have to know is what family of distribution does the conditional probability falls in</p>
  <p>And in your example, <span class="math-container">$x$</span> is the conditioning, thus you are saying that &quot;you know a point estimate <span class="math-container">$\theta$</span> and a point estimate <span class="math-container">$x$</span>&quot;, which means that that term can be estimated in closed form as it's a product of two point estimates, aka numbers/vectors</p>
  <hr />
  <p>the solution of you (last) formulation is straightforward, as <span class="math-container">$P(y|x,\theta) ~ Bernoulli$</span>, and the kl of discrete distribution is trivial</p>
  <p>The only thing you have to do is to compute the KL sample wise, and then average the KL over all the samples</p>
  <p>What you will get is a unbiased monte carlo estimate of your overall KL</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T10:30:44.227Z
Answers.Text: Ah yeah that make sense. the question is a bit confused. So really I should ask given the distribution cannot be written in closed form, or if the random vector $\mathbf{x}$ makes an appearance in the distribution like above, how do you estimate the KL divergence? Would you sample out of some $P(\mathbf{x})$ to estimate it? It seems like this is the way: https://arxiv.org/pdf/0809.0853 , https://stats.stackexchange.com/questions/280885/estimate-the-kullback-leibler-kl-divergence-with-monte-carlo.  Does it make sense to say "the KL divergence evaluated at some point $x$"?
Answers.UserDisplayName: xiaolingxiao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T14:12:24.857Z
Answers.Text: @xiaolingxiao conditioning on X means that you already know X, so you would just proceed to use it as if it's a constant, and not a random variable... on the who would you estimate a KL of two non parametric distributions, you need to resort to approximations, and since KL is just an integral, if it's low dimensions you can use quadrature procedures, but if it's somewhat high dimension, something like monte carlo estimate (there are more advanced procedures, however at that point it highly depends on your specific problem)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T14:43:11.030Z
Answers.Text: if i have many X's, ie data = $\{(x_1, y_1),..,(x_n, y_n)\}$, then the KL divergence would be evaluated at every point $x_i$? But what exactly is this quantity $D(\theta_0||\theta_1) | x_i$, is it the KL divergence between two distributions at the point $x_i$?. And if you computed the set of values $ D(\theta_0||\theta_1) | x_1, ..,  D(\theta_0||\theta_1) | x_n$, then what do you do with the set? Do you just average them? what would be the principle behind the average? Moreover, how do you account for the fact the sample may be biased?
Answers.UserDisplayName: xiaolingxiao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T15:29:56.527Z
Answers.Text: @xiaolingxiao well that's your problem definition, i can't tell you what that means... also, you are increasing the non-clear part, now you start by definition two distribution $y|x,\theta$ and then comparing instead the distribution of the $\theta$ where earlier they were just conditional informations, so the initial distributions seems useless now
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T15:31:48.930Z
Answers.Text: @xiaolingxiao I would suggest you to open a new question where you stead the REAL problem, and not a paraphrasis of your, because for the moment, seems like you have a dataset XY, some parameters $\theta$, and you are trying to estimate the distance between two parameters distributions (which makes no sense for the current formalization)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T15:33:46.950Z
Answers.Text: I meant there's 2 distributions with 2 different $\theta$: $\theta_0$ - a random initialization, & $\theta_1$ - a better estimate. The point is to compute the "improvement"  in quality of $\theta_1$ over $\theta_0$. The idea is to evaluate this improvement on the dataset, so the expected KL divergence is given here: https://math.stackexchange.com/questions/3016421/confused-by-kullback-leibler-on-conditional-probability-distributions. But that def assumes there is $P(x)$, which I do not have. Averaging it would be assuming uniform distribution.
Answers.UserDisplayName: xiaolingxiao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T15:36:18.903Z
Answers.Text: I edited the question so it's easier to read.
Answers.UserDisplayName: xiaolingxiao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T15:38:33.080Z
Answers.Text: @xiaolingxiao it's still a bit unclear, because of the "some training" is not well defined. Initially $\theta_0$ is a point estimate (a specific vector say), and after training, it's also still a specific vector, just a different one. At no point in this whole procedure, $\theta$ represents a distribution, thus estimating the KL divergence, it's impossible (it's infinite for two point estimate/lambda distributions)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T16:02:51.683Z
Answers.Text: i changed the notation so it's more clear. $\theta$ is the parameter to a distribution, I'm trying to compute the divergence between two different distributions.
Answers.UserDisplayName: xiaolingxiao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T17:23:29.847Z
Answers.Text: @xiaolingxiao sorry but I have to say it... do you realize how your change in notation completely changes the problem?
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T17:26:14.687Z
Answers.Text: @xiaolingxiao answered on the answer, but please consider that wants to be the last answer, as it's probably the 3rd completely different formulation you are posting, and it's 100% against the community rules
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T18:08:16.693Z
Answers.Text: why is this true: "What you will get is a unbiased monte carlo estimate of your overall KL"? As in why is it that the sample KL divergence is the unbiased estimate? It's only true in so far as the sample it self is unbiased right?
Answers.UserDisplayName: xiaolingxiao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T18:18:12.533Z
Answers.Text: @xiaolingxiao it's an unbiased estimate for the distribution you have in your hand, that's it. you have a coin that gives you 80% times head and is bised? the MC estimate will tell you that the coin gives head 80% of the times (aka an unbiased estimate)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-30T10:19:09.607Z
Answers.LastActivityDate: 2024-04-30T17:25:24.690Z
Answers.LastEditDate: 2024-04-30T17:25:24.690Z
Answers.UserDisplayName: Alberto
Body: <p>The KL divergence between two distributions is:
  <span class="math-container">\begin{equation}
     \int \mathbf{p}(x;\theta_{1}) \; log \frac{\mathbf{p}(x;\theta_{1})}{\mathbf{p}(x;\theta_{2})} \nu(dx) \\
  \end{equation}</span></p>
  <p>If the expression <span class="math-container">$\mathbf{p}(x;\theta)$</span> is specified by its canonical parameters, we can simply calculate the KL divergence using the expressions of <span class="math-container">$\mathbf{p}$</span>. However in the case of (conditional: deleted) distributions (where random vector <span class="math-container">$\mathbf{x}$</span> appears: added) <span class="math-container">$\mathbf{p}(y|x;\theta_{1})$</span>, how would one find the KL divergence? Would it require sampling many <span class="math-container">$x$</span>'s to estimate this value?</p>
  <p>As a concrete example, in the case of Logistic regression we have for some random initialized <span class="math-container">$\theta_0$</span>:
  <span class="math-container">\begin{equation}
      \mathbf{p}(y = 1|x;\theta_0) = \frac{1}{1+e^{-\theta_0^{\intercal}x}} \quad\quad
      \mathbf{p}(y = 0|x;\theta_0) = \frac{e^{-\theta_0^{\intercal}x}}{1+e^{-\theta_0^{\intercal}x}}.
  \end{equation}</span></p>
  <p>and another one with <span class="math-container">$\theta_1$</span>:
  <span class="math-container">\begin{equation}
      \mathbf{p}(y = 1|x;\theta_1) = \frac{1}{1+e^{-\theta_1^{\intercal}x}} \quad\quad
      \mathbf{p}(y = 0|x;\theta_1) = \frac{e^{-\theta_1^{\intercal}x}}{1+e^{-\theta_1^{\intercal}x}}.
  \end{equation}</span></p>
  <p>Now we want to compute the improvement of model <span class="math-container">$\theta_1$</span> over <span class="math-container">$\theta_0$</span>, using KL divergence:</p>
  <p><span class="math-container">\begin{align*}
      D(P(y|x;\theta_0)|P(y|x;\theta_1)) &amp;= \frac{1}{1+exp(-\theta_0^{\intercal}x)} \cdot ln \biggl(
      \frac{1+exp(-\theta_{1}^{\intercal}x)}{1+exp(-\theta_0^{\intercal}x)} \biggr) \\
      &amp;+\;
      \frac{exp(-\theta_0^{\intercal}x)}{1+exp(-\theta_0^{\intercal}x)} \cdot ln \biggl(
      \frac{1+exp(-\theta_0^{\intercal}x)}{exp(-\theta_0^{\intercal}x)} \cdot
      \frac{exp(-\theta_{1}^{\intercal}x)}{1+exp(-\theta_{1}^{\intercal}x)} \biggr).\\
  \end{align*}</span></p>
  <p>How would one evaluate <span class="math-container">$exp(-\theta_0^{\intercal} x)$</span>? Would you sample the values of x if possible? Now suppose you have many examples of <span class="math-container">$x$</span> available, ie in a training set, would it be &quot;fair&quot; to sample from the training set to evaluate <span class="math-container">$D$</span>?</p>
  <h2>edit</h2>
  <p>Removed the &quot;conditional distribution&quot;, and replaced it with expressions where random vector <span class="math-container">$\mathbf{x}$</span> makes an appearance in the definition. There is a comparable question here <a href="https://math.stackexchange.com/questions/3016421/confused-by-kullback-leibler-on-conditional-probability-distributions">https://math.stackexchange.com/questions/3016421/confused-by-kullback-leibler-on-conditional-probability-distributions</a>. But in that case the accepted answer compute the expected value of the KL divergence wrt the distribution <span class="math-container">$P(x)$</span>. But in my case I do not have this distribution <span class="math-container">$P(x)$</span>, only a dataset <span class="math-container">$\{(x_1,y_1),..,(x_n,y_n)\}$</span>. I can evaluate the quantitity <span class="math-container">$D(P(y|x;\theta_0)|P(y|x;\theta_1))$</span> for every <span class="math-container">$(x_i,y_i)$</span> in the dataset, but how would you compute the expecatation:
  <span class="math-container">\begin{equation}
  E_{x \sim P(x)}[ D(P(y|x;\theta_0)|P(y|x;\theta_1)) ] 
  \end{equation}</span>
  without this <span class="math-container">$P(x)$</span>?. The naive method is to assume <span class="math-container">$P(x)$</span> is a uniform distribution, at which point the expectation is just the average... but it seems like a better solutions is available somewhere. The closest I can find is this: <a href="https://www.tsc.uc3m.es/%7Efernando/bare_conf3.pdf" rel="nofollow noreferrer">https://www.tsc.uc3m.es/~fernando/bare_conf3.pdf</a>, which builds a CMF from the data itself.</p>
  
Tags: <machine-learning><data-preprocessing><probability-distribution><kl-divergence><conditional-probability>
Title: How to evaluate the KL divergence between two distributions that may require sampling?
UserDisplayName: xiaolingxiao
ThreadText: # How to evaluate the KL divergence between two distributions that may require sampling?
  
  (Asked by: username_0 on 2024-04-29)
  
  The KL divergence between two distributions is:
  \begin{equation}
  \int \mathbf{p}(x;\theta\_{1}) \; log \frac{\mathbf{p}(x;\theta\_{1})}{\mathbf{p}(x;\theta\_{2})} \nu(dx) \\
  \end{equation}
  
  If the expression $\mathbf{p}(x;\theta)$ is specified by its canonical parameters, we can simply calculate the KL divergence using the expressions of $\mathbf{p}$. However in the case of (conditional: deleted) distributions (where random vector $\mathbf{x}$ appears: added) $\mathbf{p}(y|x;\theta\_{1})$, how would one find the KL divergence? Would it require sampling many $x$'s to estimate this value?
  
  As a concrete example, in the case of Logistic regression we have for some random initialized $\theta\_0$:
  \begin{equation}
  \mathbf{p}(y = 1|x;\theta\_0) = \frac{1}{1+e^{-\theta\_0^{\intercal}x}} \quad\quad
  \mathbf{p}(y = 0|x;\theta\_0) = \frac{e^{-\theta\_0^{\intercal}x}}{1+e^{-\theta\_0^{\intercal}x}}.
  \end{equation}
  
  and another one with $\theta\_1$:
  \begin{equation}
  \mathbf{p}(y = 1|x;\theta\_1) = \frac{1}{1+e^{-\theta\_1^{\intercal}x}} \quad\quad
  \mathbf{p}(y = 0|x;\theta\_1) = \frac{e^{-\theta\_1^{\intercal}x}}{1+e^{-\theta\_1^{\intercal}x}}.
  \end{equation}
  
  Now we want to compute the improvement of model $\theta\_1$ over $\theta\_0$, using KL divergence:
  
  \begin{align\*}
  D(P(y|x;\theta\_0)|P(y|x;\theta\_1)) &= \frac{1}{1+exp(-\theta\_0^{\intercal}x)} \cdot ln \biggl(
  \frac{1+exp(-\theta\_{1}^{\intercal}x)}{1+exp(-\theta\_0^{\intercal}x)} \biggr) \\
  &+\;
  \frac{exp(-\theta\_0^{\intercal}x)}{1+exp(-\theta\_0^{\intercal}x)} \cdot ln \biggl(
  \frac{1+exp(-\theta\_0^{\intercal}x)}{exp(-\theta\_0^{\intercal}x)} \cdot
  \frac{exp(-\theta\_{1}^{\intercal}x)}{1+exp(-\theta\_{1}^{\intercal}x)} \biggr).\\
  \end{align\*}
  
  How would one evaluate $exp(-\theta\_0^{\intercal} x)$? Would you sample the values of x if possible? Now suppose you have many examples of $x$ available, ie in a training set, would it be "fair" to sample from the training set to evaluate $D$?
  
  ## edit
  
  Removed the "conditional distribution", and replaced it with expressions where random vector $\mathbf{x}$ makes an appearance in the definition. There is a comparable question here <https://math.stackexchange.com/questions/3016421/confused-by-kullback-leibler-on-conditional-probability-distributions>. But in that case the accepted answer compute the expected value of the KL divergence wrt the distribution $P(x)$. But in my case I do not have this distribution $P(x)$, only a dataset $\{(x\_1,y\_1),..,(x\_n,y\_n)\}$. I can evaluate the quantitity $D(P(y|x;\theta\_0)|P(y|x;\theta\_1))$ for every $(x\_i,y\_i)$ in the dataset, but how would you compute the expecatation:
  \begin{equation}
  E\_{x \sim P(x)}[ D(P(y|x;\theta\_0)|P(y|x;\theta\_1)) ]
  \end{equation}
  without this $P(x)$?. The naive method is to assume $P(x)$ is a uniform distribution, at which point the expectation is just the average... but it seems like a better solutions is available somewhere. The closest I can find is this: [https://www.tsc.uc3m.es/~fernando/bare\_conf3.pdf](https://www.tsc.uc3m.es/%7Efernando/bare_conf3.pdf), which builds a CMF from the data itself.
  
  **Tags:** machine-learning, data-preprocessing, probability-distribution, kl-divergence, conditional-probability
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-04-30. Score: 1
  
  The distribution being conditional or not does not change the notion of KL divergence.
  
  Indeed, given $p(x) \sim N(\mu\_1, \sigma\_1^2)$ and $q(x) \sim N(\mu\_2, \sigma\_2^2)$, the KL can be estimated in closed form.
  
  However, the KL between $p(y|x) \sim N(\mu\_1, \sigma\_1^2)$ and $q(y|x) \sim N(\mu\_2, \sigma\_2^2)$ shares the same closed form with the previous one
  
  The only thing you have to know is what family of distribution does the conditional probability falls in
  
  And in your example, $x$ is the conditioning, thus you are saying that "you know a point estimate $\theta$ and a point estimate $x$", which means that that term can be estimated in closed form as it's a product of two point estimates, aka numbers/vectors
  
  ---
  
  the solution of you (last) formulation is straightforward, as $P(y|x,\theta) ~ Bernoulli$, and the kl of discrete distribution is trivial
  
  The only thing you have to do is to compute the KL sample wise, and then average the KL over all the samples
  
  What you will get is a unbiased monte carlo estimate of your overall KL
  
  > **Comments:**
  > **username_0**: Ah yeah that make sense. the question is a bit confused. So really I should ask given the distribution cannot be written in closed form, or if the random vector $\mathbf{x}$ makes an appearance in the distribution like above, how do you estimate the KL divergence? Would you sample out of some $P(\mathbf{x})$ to estimate it? It seems like this is the way: https://arxiv.org/pdf/0809.0853 , https://stats.stackexchange.com/questions/280885/estimate-the-kullback-leibler-kl-divergence-with-monte-carlo.  Does it make sense to say "the KL divergence evaluated at some point $x$"?  
  > **username_1**: @xiaolingxiao conditioning on X means that you already know X, so you would just proceed to use it as if it's a constant, and not a random variable... on the who would you estimate a KL of two non parametric distributions, you need to resort to approximations, and since KL is just an integral, if it's low dimensions you can use quadrature procedures, but if it's somewhat high dimension, something like monte carlo estimate (there are more advanced procedures, however at that point it highly depends on your specific problem)  
  > **username_0**: if i have many X's, ie data = $\{(x_1, y_1),..,(x_n, y_n)\}$, then the KL divergence would be evaluated at every point $x_i$? But what exactly is this quantity $D(\theta_0||\theta_1) | x_i$, is it the KL divergence between two distributions at the point $x_i$?. And if you computed the set of values $ D(\theta_0||\theta_1) | x_1, ..,  D(\theta_0||\theta_1) | x_n$, then what do you do with the set? Do you just average them? what would be the principle behind the average? Moreover, how do you account for the fact the sample may be biased?  
  > **username_1**: @xiaolingxiao well that's your problem definition, i can't tell you what that means... also, you are increasing the non-clear part, now you start by definition two distribution $y|x,\theta$ and then comparing instead the distribution of the $\theta$ where earlier they were just conditional informations, so the initial distributions seems useless now  
  > **username_1**: @xiaolingxiao I would suggest you to open a new question where you stead the REAL problem, and not a paraphrasis of your, because for the moment, seems like you have a dataset XY, some parameters $\theta$, and you are trying to estimate the distance between two parameters distributions (which makes no sense for the current formalization)  
  > **username_0**: I meant there's 2 distributions with 2 different $\theta$: $\theta_0$ - a random initialization, & $\theta_1$ - a better estimate. The point is to compute the "improvement"  in quality of $\theta_1$ over $\theta_0$. The idea is to evaluate this improvement on the dataset, so the expected KL divergence is given here: https://math.stackexchange.com/questions/3016421/confused-by-kullback-leibler-on-conditional-probability-distributions. But that def assumes there is $P(x)$, which I do not have. Averaging it would be assuming uniform distribution.  
  > **username_0**: I edited the question so it's easier to read.  
  > **username_1**: @xiaolingxiao it's still a bit unclear, because of the "some training" is not well defined. Initially $\theta_0$ is a point estimate (a specific vector say), and after training, it's also still a specific vector, just a different one. At no point in this whole procedure, $\theta$ represents a distribution, thus estimating the KL divergence, it's impossible (it's infinite for two point estimate/lambda distributions)  
  > **username_0**: i changed the notation so it's more clear. $\theta$ is the parameter to a distribution, I'm trying to compute the divergence between two different distributions.  
  > **username_1**: @xiaolingxiao sorry but I have to say it... do you realize how your change in notation completely changes the problem?  
  > **username_1**: @xiaolingxiao answered on the answer, but please consider that wants to be the last answer, as it's probably the 3rd completely different formulation you are posting, and it's 100% against the community rules  
  > **username_0**: why is this true: "What you will get is a unbiased monte carlo estimate of your overall KL"? As in why is it that the sample KL divergence is the unbiased estimate? It's only true in so far as the sample it self is unbiased right?  
  > **username_1**: @xiaolingxiao it's an unbiased estimate for the distribution you have in your hand, that's it. you have a coin that gives you 80% times head and is bised? the MC estimate will tell you that the coin gives head 80% of the times (aka an unbiased estimate)  
  
  ---
  
  