2
$\begingroup$

I'm familiar with the definition of the KL divergence between two discrete distributions

$D_{KL} = D_{KL}\big({\it P}(A) || {\it Q}(B)\big)=\sum_{j=1}^{n} {\it P}(A=a_{j}) \log \Big( \cfrac{{\it P}(A=a_{j})}{{\it Q}(B=b_{j})} \Big)$

and how it approaches the continuous limit as the size of a particular bin width approaches 0.

Implementing this practically with samples from Markov Chain Monte Carlo, I would anticipate that the KL divergence would asymptotically approach the true value as you divide samples into more and more bins.

However, what I find in a simple problem is that the KL divergence continues to drop as the number of bins increase. Below are some figures.

For a parameter $L$, I am comparing an exact distribution vs one I obtained using a Gaussian Process emulator. Two distributions of a parameter L

Calculating the KL divergence, I find the following behavior when increasing the number of bins: KL divergence vs. number of bins

In the second figure, there are ~50 steps in bin size. My expectation was that the KL divergence would approach a value and then begin to behave erratically as the bin widths became so small that in a given bin, one distribution would have no counts. Why is the KL divergence dropping in such a way and what is the best way to rigorously choose a number of bins for comparing distributions? As far as I've been able to tell, this question hasn't been answered clearly in the literature.

Edit to address a comment from Shimao: If I take samples from two distributions N(0,1) and N(2,1), I get similar behavior. KL Divergence between two normal distributions

Edit2: Adding the function I use to calculate the KL Divergence

def KL_divergence(h1, h0, dx):
    """ 
    h0, h1 are histograms
    dx is the bin width, which we assume is uniform
    
    Return the information gain of pdf h1 w.r.t. h0, approximated by
    riemann sum over histograms of each pdf. Assumes that distributions have the exact same bins
    and that bin widths are uniform! 
    """
    #get nonzero values of posterior, the logarithm is ill-defined for bins with zero
    nonzero_idx = [x!=0 for x in h1] # get indices for nonzero bins
    h1 = h1[ nonzero_idx ] # filter
    h0 = h0[ nonzero_idx ]
    
    nonzero_idx = [x!=0 for x in h0] # get indices for nonzero bins
    h1 = h1[ nonzero_idx ] # filter
    h0 = h0[ nonzero_idx ]

    KLdiv = np.sum( h1 * np.log2(h1/h0) ) * np.prod(dx) # calculate the KL divergence
    return KLdiv
$\endgroup$
4
  • 1
    $\begingroup$ can you replicate this on two distributions with known / closed form KL divergence? such as two normals N(0,1) and N(2,1)? $\endgroup$
    – shimao
    Feb 22, 2021 at 21:18
  • 1
    $\begingroup$ You are operating under the incorrect premise that the discrete and continuous versions of the KL divergence are the same things, but they're not. Thus a resolution to your problem must appeal to your reasons for using a KL divergence in the first place. $\endgroup$
    – whuber
    Feb 22, 2021 at 21:20
  • $\begingroup$ @shimao Yes, I can replicate this behavior - I updated my question to include a plot with the distributions you described. For the plot above, I took 10,000 samples of each normal distribution. $\endgroup$ Feb 22, 2021 at 21:41
  • $\begingroup$ @whuber What I'm trying to test is convergence between a true distribution and a distribution where the statistical model has been emulated as I increase the training points in the emulated distribution. Does that suggest that I should just pick a number and stick to it? $\endgroup$ Feb 22, 2021 at 21:42

1 Answer 1

2
$\begingroup$

The issue that was causing this behavior is that the discrete and continuous versions of the KL divergence approach each other in the limit where the $n_{samples} \rightarrow \infty$ and $width_{bin} \rightarrow 0$.

Holding $n_{samples}$ fixed and increasing $n_{bins}$ as a result is only fulfilling one criteria. The issue of how to choose a number of bins given a number of samples has been answered several times and in introductory texts; Rice (1944), for example, recommends $n_{bins} = 2\sqrt[3]{n_{samples}}$. Implementing this naively (so that sampling fluctuations haven't been taken care of), in the limit $n_{samples} \rightarrow \infty$, the discrete and continuous versions approach agreement for the example suggested by @Shimao in the comment above.

N.B. One must also be careful to compare in the correct units (bits vs. nats).

Plot demonstrating convergence

This convergence can also be seen when calculating KL divergence a set number of times to estimate the sampling error in the histogram below where KL Divergence is along the x axis. Histogram to quantify sampling error of the KL divergence

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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