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

31–40 of 77 posts

Re: Kullback–Leibler divergence

#31

Post by enthdegree »

abetusk wrote: post #27
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?

Intuitively, it measures the difference between two probability distributions. It's not symmetric, so it's not quite that, but in my opinion, it's good intuition. As motivation, say you're an internet provider, providing internet service to a business. You naturally want to save money, so you perhaps want to compress packets before they go over the wire. Let's say the business you're providing service to also compres…

Your characterization (originally due to Cover, I think) is a strong one because it concretely ties KL divergence to nature. I also like Sanov's theorem for this.

I have sat through many frustrating anti-explanations of the following sort:

>What is KL divergence you ask? Why, it's simply a quantitative difference between distributions. The further away distributions are, the higher KL divergence is... It's like a distance-squared between distributions... but it isn't symmetric and it doesn't obey any usual triangle inequality, so this analogy isn't helpful for analysis... Pinsker's inequality gives a useful lower bound. A useful general upper bound is, uhh,... uh...

This class of answer is totally uninformative (and discrediting if given, IMO) because it does not provide a useful, unique characterization of KL divergence, only fundamentally inaccurate descriptions of it.

Re: Kullback–Leibler divergence

#32

Post by chermi »

tnecniv wrote: post #29
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?

In addition to what others have said, it fixes a “bug” in Shannon’s continuous version of the entropy. Shannon assumed you could just replace the sum with an integral and call it a day. However, two bad things happen: 1. This definition of entropy is not invariant to coordinate transforms. If you change the parameters of your distribution, you get a different value for the entropy, despite the change of parameters no…

I assume you're referring to his most famous work, where he introduces his maxent stuff? http://bayes.wustl.edu/etj/articles/theory.1.pdf

I would also highly recommend the free and excellent book by MacKay for understanding this: http://www.inference.org.uk/mackay/itila/book.html

Re: Kullback–Leibler divergence

#33

Post by glial »

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?

In the context of Bayesian inference, the KL divergence between the prior p(m) and the posterior p(m|x) is the information gained by observing x.

With VAEs, adding a KL divergence to the loss term can be thought of as regularizing information gain from individual inputs.

Re: Kullback–Leibler divergence

#34

Post by acc_297 »

techwizrd wrote: post #16

We use KL-divergence to calculate how surprising a time-series anomaly is and rank them for aviation safety, e.g., give me a ranked list of the most surprising increases in a safety metric. It's quite handy!

That’s very cool what are the most surprising increases in aviation safety metrics lately?

Re: Kullback–Leibler divergence

#35

Post by kgwgk »

leourbina wrote: post #6
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 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.

Re: Kullback–Leibler divergence

#37

Post by jwarden »

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* surprised I expect Bob to be than me

  Dkl(p || q) = H(p,q) - H(p,p)
              = ∑_x p(X=x) * log p(X=x)/q(X=x)
information gain: how much less surprised I expect Bob to be if he knew that Y=y

  IG(q|Y=y)   = Dkl(q(X|Y=y) || q(X))
mutual information: how much information I expect to gain about X from learning the value of Y

  I(X;Y)      = 𝔼_Y IG(q|Y=y)
                𝔼_Y Dkl(q(X|Y=y) || q(X))

Re: Kullback–Leibler divergence

#38

Post by mrfox321 »

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*…

Typo in cross entropy, should be

p log q

Re: Kullback–Leibler divergence

#39

Post by riemannzeta »

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 information (in the Shannon sense) than a system in equilibirum. That "excess information" is what drives fitness within some environment.

Re: Kullback–Leibler divergence

#40

Post by jwarden »

mrfox321 wrote: post #38
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*…

Typo in cross entropy, should be p log q

Thank you, fixed.
Post reply on HN