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

51–60 of 77 posts

Re: Kullback–Leibler divergence

#51

Post by mreid »

tech_ken wrote: post #21
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?

Lots of different ways of motivating KL, but I think one that's frequently neglected in the ML era is its relationship to a likelihood ratio test. Kullback and Leibler originally characterized the KL divergence as the measure of the ability of discriminate between two distributions (ie. perform a hypothesis test between them), given some set of observations (the thing you're averaging over). You can read their origin…

This likelihood ratio approach highlights the fact that KL divergence is a member of the family of Csiszár F-divergences. These are measures of "distance" between distributions of the form E_Q[ F(p(x)/q(x)) ] where F is any convex function with F(1) = 0. This is kind of a generalization of log-likelihood where F kind of "weights" the badness of ratios different to 1. When F is -log you get KL divergence.

Another curious fact about KL divergences is they are also a Bregman divergence: take a convex function H and define B_H(P, Q) = \sum_x H(p(x)) - H(q(x)) - . These generalize pointwise square Euclidean distance. KL is obtained when H(P) is negative entropy \sum_x p(x) log p(x).

I spent a bunch of time studying divergences over distributions (e.g., see my blog post[1]) and in particular these two classes and the really neat fact about KL divergence is that it is essentially the only divergence that is both an F-divergence and a Bregman divergence. This is basically due to the property of log that turns logs of products into sums.

[1]: https://mark.reid.name/blog/meet-the-bregman-divergences.htm...

Re: Kullback–Leibler divergence

#52

Post by zmmmmm »

3abiton wrote: post #48
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*…

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 really an order of magnitude apart, just like 0.01 and 0.001. Perhaps it will work better if I use the log of the probability". Then you would pause for thought and say, "Hmmmm hang on some of the values are really extreme but almost never happen, shouldn't it be weighted by how frequently they occur?".

But of course paragraphs of mathematical symbols are the way many people prefer to express this.

Re: Kullback–Leibler divergence

#53

Post by riemannzeta »

tysam_and wrote: post #42
riemannzeta wrote: post #39

KL divergence has also been used to generalize the second law of thermodynamics for systems far from equilibrium: https://arxiv.org/abs/1508.02421 And to explain the relationship between the rate of evolution and evolutionary fitness: https://math.ucr.edu/home/baez/bio_asu/bio_asu_web.pdf The connection between all of these manifestations of KL divergence is that a system far from equilibrium contains more informatio…

I'm not sure if I follow the fitness-driving argument. Without an informational sieve of some kind, isn't it just random entropy? In this case, sure, far from equilibrium has more information, but that just means the system has more flexibility to move, not that the system actually inherently contains more information (stored information vs inbound throughput). Unless it's some kind of Nash game, or problem with mult…

I will confess that at least the biology work is still somewhat mysterious to me. John Baez used to be active on Twitter. I believe he's still active on Mathstodon now. If you're curious, you might ask him.

Re: Kullback–Leibler divergence

#54

Post by sarma17 »

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 to derived the KL formula. I'd also appreciate if you know how the N (sample size ig) is being used here.

For a lot of math stuff I endup being confused about how people use operations. Like using 1/p(X=x) is like magic to me because I don't understand what the context is when someone thinks about the problem and then decides to do something. What's their thinking process here, what tool or process do I not know about that makes me confused?

Re: Kullback–Leibler divergence

#55

Post by eutectic »

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…

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.

Re: Kullback–Leibler divergence

#56

Post by sarma17 »

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.

thanks for the reply but I don't think I understood what you said in the context of my question.

I'm stuck on why we care about surprisal as `log 1/p`.

Re: Kullback–Leibler divergence

#57

Post by eutectic »

sarma17 wrote: post #56
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.

thanks for the reply but I don't think I understood what you said in the context of my question. I'm stuck on why we care about surprisal as `log 1/p`.

log 1/p is just -log p

Re: Kullback–Leibler divergence

#58

Post by necroforest »

janalsncm wrote: post #50

Btw, KL divergence isn’t symmetrical. So D(P,Q) != D(Q,P). If you need a symmetrical version of it, you can use Jensen–Shannon divergence which is the mean of D(P,Q) and D(Q,P). Or if you only care about relative distances you can just use the sum.

JS divergence isn't just the average. it's 0.5(KL(P||M) + KL(Q||M)) where M is the mixture of P and Q: M = 0.5(P + Q)

Re: Kullback–Leibler divergence

#59

Post by janalsncm »

necroforest wrote: post #58
janalsncm wrote: post #50

Btw, KL divergence isn’t symmetrical. So D(P,Q) != D(Q,P). If you need a symmetrical version of it, you can use Jensen–Shannon divergence which is the mean of D(P,Q) and D(Q,P). Or if you only care about relative distances you can just use the sum.

JS divergence isn't just the average. it's 0.5(KL(P||M) + KL(Q||M)) where M is the mixture of P and Q: M = 0.5(P + Q)

Oh nice catch. All this time I had been thinking the wrong thing.

Re: Kullback–Leibler divergence

#60

Post by JonyEpsilon »

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…

It's not answering quite the question you asked, but Shannon - who invented much of this stuff - has some really nice practical arguments in the start of his amazing paper that introduced "information theory" [1]. It's a really readable paper, much less intimidating than you might think, and worth a look.

Hartley was (as far as I know) the first person to recognise the usefulness of log probabilities in the context of measuring information [2]. It's a really amazing paper, for several reasons ... but one thing that really strikes me about it is how it's aged: the first half has an essentially timeless presentation of the essence of information, and the second has a now-quite-irrelevant presentation of how to make a better TV. I guess that was the really interesting problem at the time!

[1] https://people.math.harvard.edu/~ctm/home/text/others/shanno...

[2] http://dotrose.com/etext/90_Miscellaneous/transmission_of_in...

Post reply on HN