Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Kullback–Leibler divergence

en.wikipedia.org

Post reply on HN
Print view View original

11–20 of 77 posts

Re: Kullback–Leibler divergence

#11

Post by tel »

max_ wrote: post #2

K-L Divergence is something that Keeps coming up in my research but I still don't understand what it is. Could someone give me a simple explanation as to what it's is. And also, what practical use cases does it have?

It's a useful way of measuring how different two probability distributions are. If F and G are distributions, Kl(F||G) is non-negative real number which is larger if F and G are less similar.

In a lot of statistical estimation procedures, you have some kind of "current estimate" distribution which has nice properties and some kind of "true distribution" which you'd like to use your nice distribution to approximate. It's then common to create a system which manipulates the parameters of your current estimate distribution to minimize the KL-divergence with the true distribution.

A relatively simple example of this is fitting a Gaussian mixture model. If you look up how that process is derived you'll see it depends centrally on minimizing the KL-divergence between two distributions.

There are other ways to measure the difference between two probability distributions, but the KL-divergence has some nice properties. It shows up as the answer to lots of well-motivated questions around statistical inference (Neyman-Pearson testing, information geometry, Bayesian inference, entropy) and it has a form which is somewhat amenable to algebraic manipulation.

In some sense it's popular because it keeps showing up and working. People recognize its form, consider it relatively simple, and find it meaningful to talk about. It's common enough that you might even begin considering a problem by asking if you can minimize the KL-divergence between your estimate and some goal just knowing that outright it will likely lead to a successful solution to your problem.

Re: Kullback–Leibler divergence

#12

Post by uoaei »

mrv_asura wrote: post #9

I learnt about KL Divergence recently and it was pretty cool to know that cross-entropy loss originated from KL Divergence. But could someone give me the cases where it is preferred to use Mean-squared Error loss vs Cross-entropy loss? Is there any merits or demerits of using either?

This is the NN 101 explanation: mean-square loss is for regression, cross-entropy is for classification.

NN 201 explanation: mean-square is about finite but continuous errors (residuals) of predicted value vs true value of the output, cross-entropy is for distributions over discrete sets of categories.

NN 501 explanation: the task of the NN and the form of its outputs should be defined in terms of the "shape" or nature of the residuals of its predictions. Mean-square corresponds to predicting means with Gaussian residuals, cross-entropy corresponds to predicting over discrete outputs with multinomial (mutually exclusive) structure. Indeed you can derive any loss function you want by first defining the expected form of the residuals and then deriving the negative log-likelihood of the associated distribution.

Re: Kullback–Leibler divergence

#13

Post by zerojames »

I have used KL-divergence in authorship verification: https://github.com/capjamesg/pysurprisal/blob/main/pysurpris...

My theory was: calculate entropy ("surprisal") of used words in a language (in my case, from an NYT corpus), then calculate KL-divergence between a given prose and a collection of surprisals for different authors. The author to whom the prose had the highest KL-divergence was assumed to be the author. I think it has been used in stylometry a bit.

Re: Kullback–Leibler divergence

#14

Post by versteegen »

eob wrote: post #5
max_ wrote: post #2

K-L Divergence is something that Keeps coming up in my research but I still don't understand what it is. Could someone give me a simple explanation as to what it's is. And also, what practical use cases does it have?

As for practical use cases, one is to find an approximate optimization to a function - You want to find the min/max of some probability distribution P(x) - P(x) is too complicated to find a closed-form min, but you can draw samples from it. - So instead, you carefully construct some OTHER probability distribution Q(x|θ) that you claim is structurally similar "enough" to P(x), parameterized by θ. - Now you find the th…

Note that "drawing samples from P(x)" means to have training data drawn from P(x).

You can form the 'empirical' probability distribution P'(x) from your n training samples {x_i}, with P'(x_i) = 1/n and P'(x) = 0 for all other x.

Then finding the θ which minimizes KL(P'(x) ∥ Q(x|θ)) is equivalent to finding the maximum likelihood estimate (MLE) given your training data.

(Note: I don't know what's meant by "the min/max of some probability distribution P(x)" and suggest ignoring that)

Re: Kullback–Leibler divergence

#15

Post by versteegen »

zerojames wrote: post #13

I have used KL-divergence in authorship verification: https://github.com/capjamesg/pysurprisal/blob/main/pysurpris... My theory was: calculate entropy ("surprisal") of used words in a language (in my case, from an NYT corpus), then calculate KL-divergence between a given prose and a collection of surprisals for different authors. The author to whom the prose had the highest KL-divergence was assumed to be the author.…

*lowest KL-divergence

Re: Kullback–Leibler divergence

#18

Post by puzzlingcaptcha »

max_ wrote: post #2

K-L Divergence is something that Keeps coming up in my research but I still don't understand what it is. Could someone give me a simple explanation as to what it's is. And also, what practical use cases does it have?

One practical use might be assessing the similarity of a high-dimensional data set and its low-dimensional projection, as used in e.g. t-SNE.

Re: Kullback–Leibler divergence

#19

Post by mufasachan »

mrv_asura wrote: post #9

I learnt about KL Divergence recently and it was pretty cool to know that cross-entropy loss originated from KL Divergence. But could someone give me the cases where it is preferred to use Mean-squared Error loss vs Cross-entropy loss? Is there any merits or demerits of using either?

TL;DR: One is about distance in space, the other is about spread in space.

KL-Divergence is not a metric, it's not symmetric. It's biased toward your reference distribution. Although, it gives an probabilistic / information view of a difference in distributions. One of the outcome of KL is that it will highlight the tail of your distribution.

Euclidean distance, L2, is a metric. So it is suited when you need a metric. Also, it does not give an insight of any distribution phenomenons expect the means of the distribution.

For example, you are a teacher, you have two classes. You want to compare the grades. L2 can be a summary of how far the grades are apart. The length of tails of both grades distribution won't have impact if they have the same mean. That's good if you want to know the average level of both classes. KL will give the point of view how the class grades spread are alike. Two classes can have small KL Divergence if they have the same shapes of distributions. If your classes are very different - one is very homogeneous and the other one is very heterogeneous - then your KL will be big, even if the average are very close.

Re: Kullback–Leibler divergence

#20

Post by zerojames »

versteegen wrote: post #15
zerojames wrote: post #13

I have used KL-divergence in authorship verification: https://github.com/capjamesg/pysurprisal/blob/main/pysurpris... My theory was: calculate entropy ("surprisal") of used words in a language (in my case, from an NYT corpus), then calculate KL-divergence between a given prose and a collection of surprisals for different authors. The author to whom the prose had the highest KL-divergence was assumed to be the author.…

*lowest KL-divergence

Yes indeed -- thank you! :facepalm:
Post reply on HN