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

61–70 of 77 posts

Re: Kullback–Leibler divergence

#61

Post by topaz0 »

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?

My intro to K-L divergence was in the context of maximum likelihood estimation with a misspecified model. The asymptotic expected value of a parametric MLE is the parameter value that minimizes the K-L divergence from the true distribution to the model. That means that when the parametric model contains the true distribution, the MLE is a consistent estimator (as is well known). But it also gives you a way of analytically finding the (asymptotic) bias of the MLE when the model does not contain the true distribution.

Re: Kullback–Leibler divergence

#62

Post by ramblenode »

eutectic wrote: post #55
sarma17 wrote: post #54

Earlier quoted context omitted.

qq, can you explain a few noob thoughts. Why is surprisal defined as `log (1/p(X=x)`? I'm lacking the intuition for 1. why did someone think to use 1/p? 2. why do we have a log term here. Log shows up a lot but I don't think I ever really understood when/how do people decided to use it in their formulas. One KL divergence youtube video said, `let's normalize the p(P)/p(Q) using (log(p(P)/q(P)))^N` and then shows how…

Negative log is the only decreasing function which satisfies f(x * y) = f(x) + f(y). If you have two independent events it makes sense that the total surprisal (information content) should be the sum of the surprisals of the two events. Another way to see it is as a continuous generalization of the idea that you need n bits to represent 2^n equally likely alternatives.

> If you have two independent events it makes sense that the total surprisal (information content) should be the sum of the surprisals of the two events.

I think the parent is also asking why we would expect surprisal to be additive rather than multiplicative like probabilities.

Re: Kullback–Leibler divergence

#63

Post by Majromax »

ramblenode wrote: post #62
eutectic wrote: post #55

Earlier quoted context omitted.

Negative log is the only decreasing function which satisfies f(x * y) = f(x) + f(y). If you have two independent events it makes sense that the total surprisal (information content) should be the sum of the surprisals of the two events. Another way to see it is as a continuous generalization of the idea that you need n bits to represent 2^n equally likely alternatives.

> If you have two independent events it makes sense that the total surprisal (information content) should be the sum of the surprisals of the two events. I think the parent is also asking why we would expect surprisal to be additive rather than multiplicative like probabilities.

Because if two things happen – one totally expected and one very surprising – then on net you’re still surprised.

Re: Kullback–Leibler divergence

#64

Post by pama »

zmmmmm wrote: post #52
3abiton wrote: post #48

Earlier quoted context omitted.

Forgive my peasant mind, I've heard about K-L divergence before, I just don't know what it is used for nor what's special about it compared to other metrics?

I think people who love math expressed in nomenclature well never understand those who don't ... K-L divergence is the pretty much really dumb, obvious thing you would probably think up if someone asked you to compare two probability distributions. You would start by going "oh I suppose I will look at how far apart they are at all the different values" and add it up. Then you would say, "oh, but 0.1 and 0.01 are real…

I agree, however the next step would be to symmetrize the KL divergence because otherwise we get a result that depends on the order that we parse the distributions.

Re: Kullback–Leibler divergence

#65

Post by stygiansonic »

sarma17 wrote: post #54
jwarden wrote: post #37

Here's how I describe KL Divergence, building up from simple to complex concepts. surprisal: how surprised I am when I learn the value of X Suprisal(x) = -log p(X=x) entropy: how surprised I expect to be H(p) = 𝔼_X -log p(X) = ∑_x p(X=x) * -log p(X=x) cross-entropy: how surprised I expect Bob to be (if Bob's beliefs are q instead of p) H(p,q) = 𝔼_X -log q(X) = ∑_x p(X=x) * -log q(X=x) KL divergence: how much *more*…

qq, can you explain a few noob thoughts. Why is surprisal defined as `log (1/p(X=x)`? I'm lacking the intuition for 1. why did someone think to use 1/p? 2. why do we have a log term here. Log shows up a lot but I don't think I ever really understood when/how do people decided to use it in their formulas. One KL divergence youtube video said, `let's normalize the p(P)/p(Q) using (log(p(P)/q(P)))^N` and then shows how…

There’s some information here about why this was chosen. Specifically it fulfills certain criteria: https://en.m.wikipedia.org/wiki/Entropy_(information_theory)...

Re: Kullback–Leibler divergence

#66

Post by KRAKRISMOTT »

eutectic wrote: post #55
sarma17 wrote: post #54

Earlier quoted context omitted.

qq, can you explain a few noob thoughts. Why is surprisal defined as `log (1/p(X=x)`? I'm lacking the intuition for 1. why did someone think to use 1/p? 2. why do we have a log term here. Log shows up a lot but I don't think I ever really understood when/how do people decided to use it in their formulas. One KL divergence youtube video said, `let's normalize the p(P)/p(Q) using (log(p(P)/q(P)))^N` and then shows how…

Negative log is the only decreasing function which satisfies f(x * y) = f(x) + f(y). If you have two independent events it makes sense that the total surprisal (information content) should be the sum of the surprisals of the two events. Another way to see it is as a continuous generalization of the idea that you need n bits to represent 2^n equally likely alternatives.

Convolution?

Re: Kullback–Leibler divergence

#67

Post by creata »

zmmmmm wrote: post #52
3abiton wrote: post #48

Earlier quoted context omitted.

Forgive my peasant mind, I've heard about K-L divergence before, I just don't know what it is used for nor what's special about it compared to other metrics?

I think people who love math expressed in nomenclature well never understand those who don't ... K-L divergence is the pretty much really dumb, obvious thing you would probably think up if someone asked you to compare two probability distributions. You would start by going "oh I suppose I will look at how far apart they are at all the different values" and add it up. Then you would say, "oh, but 0.1 and 0.01 are real…

> K-L divergence is the pretty much really dumb, obvious thing you would probably think up if someone asked you to compare two probability distributions.

I don't think if anyone was asked simply to "compare two probability distributions", they'd come up with something asymmetric like the KL divergence. You'd need to at least add that one of the distributions is the "real" distribution.

Re: Kullback–Leibler divergence

#68

Post by [deleted] »

sarma17 wrote: post #54
jwarden wrote: post #37

Here's how I describe KL Divergence, building up from simple to complex concepts. surprisal: how surprised I am when I learn the value of X Suprisal(x) = -log p(X=x) entropy: how surprised I expect to be H(p) = 𝔼_X -log p(X) = ∑_x p(X=x) * -log p(X=x) cross-entropy: how surprised I expect Bob to be (if Bob's beliefs are q instead of p) H(p,q) = 𝔼_X -log q(X) = ∑_x p(X=x) * -log q(X=x) KL divergence: how much *more*…

qq, can you explain a few noob thoughts. Why is surprisal defined as `log (1/p(X=x)`? I'm lacking the intuition for 1. why did someone think to use 1/p? 2. why do we have a log term here. Log shows up a lot but I don't think I ever really understood when/how do people decided to use it in their formulas. One KL divergence youtube video said, `let's normalize the p(P)/p(Q) using (log(p(P)/q(P)))^N` and then shows how…

[deleted]

Re: Kullback–Leibler divergence

#69

Post by [deleted] »

sarma17 wrote: post #54
jwarden wrote: post #37

Here's how I describe KL Divergence, building up from simple to complex concepts. surprisal: how surprised I am when I learn the value of X Suprisal(x) = -log p(X=x) entropy: how surprised I expect to be H(p) = 𝔼_X -log p(X) = ∑_x p(X=x) * -log p(X=x) cross-entropy: how surprised I expect Bob to be (if Bob's beliefs are q instead of p) H(p,q) = 𝔼_X -log q(X) = ∑_x p(X=x) * -log q(X=x) KL divergence: how much *more*…

qq, can you explain a few noob thoughts. Why is surprisal defined as `log (1/p(X=x)`? I'm lacking the intuition for 1. why did someone think to use 1/p? 2. why do we have a log term here. Log shows up a lot but I don't think I ever really understood when/how do people decided to use it in their formulas. One KL divergence youtube video said, `let's normalize the p(P)/p(Q) using (log(p(P)/q(P)))^N` and then shows how…

[deleted]

Re: Kullback–Leibler divergence

#70

Post by leourbina »

kgwgk wrote: post #35
leourbina wrote: post #6

Earlier quoted context omitted.

One intuition is that KL-divergence represents a sort of “distance” between probability distributions. However, this isn’t quite right as it doesn’t satisfy some basic properties a real distance (a norm) would satisfy, including the fact that it isn’t symmetric: KL(Q, P) != KL(P,Q), and it does not satisfy the triangle inequality. Nonetheless, KL(P,Q) gives you a good idea of how “far” is P is from Q: in the context…

> it doesn’t satisfy some basic properties a real distance (a norm) would satisfy, including the fact that it isn’t symmetric [...] and it does not satisfy the triangle inequality. Not sure about "real" but one can have useful distances which are not symmetric like the distance between cities measured in time or in gallons.

It just needs to be clarified that KL divergence isn’t a proper mathematical norm, so it doesn’t behave the way we intuitively think a distance should. As mentioned, it doesn’t satisfy the triangle inequality, which is a basic property for any distance-like function.

In comparison, both of your examples are much closer to norms as they both satisfy the triangle inequality.

For reference, this is what I’m referring to when I say a “norm”:

https://en.m.wikipedia.org/wiki/Norm_(mathematics)

Post reply on HN