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

41–50 of 77 posts

Re: Kullback–Leibler divergence

#41

Post by tysam_and »

Here is the simplest way of explaining the KL divergence:

The KL divergence yields a concrete value that tells you how many actual bits of space on disk you will waste if you try to use an encoding table from one ZIP file of data to encode another ZIP file of data. It's not just theoretical, this is exactly the type of task that it's used for.

The closer the folders are to each other in content, the fewer wasted bits. So, we can use this to measure how similar two sets of information are, in a manner of speaking.

These 'wasted bits' are also known as relative entropy, since entropy basically is a measure of how disordered something can be. The more disordered, the more possibilities we have to choose from, thus the more information possible.

Entropy does not guarantee that the information is usable. It only guarantees how much of this quantity we can get, much like pipes serving water. Yes, they will likely serve water, but you can accidentally have sludge come through instead. Still, their capacity is the same.

One thing to note is that with our ZIP files, if you use the encoding tables from one to encode the other, then you will end up with different relative entropy (i.e. our 'wasted bits') numbers than if you did the vice versa. This is because the KL is not what's called symmetric. That is, it can have different meaning based upon which direction it goes.

Can you pull out a piece of paper, make yourself an example problem, and tease out an intuition as to why?

Re: Kullback–Leibler divergence

#42

Post by tysam_and »

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 multiple similarly-deep valleys, I don't see how that would do much more from a fitness perspective other than allow us to effect something approaching an unbiased estimator of the minima density of whatever problem we're working on is. Or...whatever, I'm not quite sure.

Anywho, however it is, I'm a bit confused on the last part there.

Re: Kullback–Leibler divergence

#44

Post by j2kun »

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!

Would you be interested in chatting with me about this topic for a book I'm working on? If so please reach out at mathintersectprogramming@gmail.com and we can set up a time to chat!

Re: Kullback–Leibler divergence

#45

Post by nuancebydefault »

tysam_and wrote: post #41

Here is the simplest way of explaining the KL divergence: The KL divergence yields a concrete value that tells you how many actual bits of space on disk you will waste if you try to use an encoding table from one ZIP file of data to encode another ZIP file of data. It's not just theoretical, this is exactly the type of task that it's used for. The closer the folders are to each other in content, the fewer wasted bits…

Thanks for giving a concrete example. For me, formulas like - log p (x) are much harder to understand.

Re: Kullback–Leibler divergence

#46

Post by 317070 »

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?

Here is another view, which also explains where the logarithm comes from.

The KL between two distributions of a random variable, say Kl[p|q], says that if you made a perfect compression algorithm for samples from distribution q, how many extra bits/nats you expect to need to code samples that actually come from p instead if you use that compression algorithm.

And compression is all about keeping only the true information that is encoded in a sample.

Re: Kullback–Leibler divergence

#47

Post by tysam_and »

nuancebydefault wrote: post #45
tysam_and wrote: post #41

Here is the simplest way of explaining the KL divergence: The KL divergence yields a concrete value that tells you how many actual bits of space on disk you will waste if you try to use an encoding table from one ZIP file of data to encode another ZIP file of data. It's not just theoretical, this is exactly the type of task that it's used for. The closer the folders are to each other in content, the fewer wasted bits…

Thanks for giving a concrete example. For me, formulas like - log p (x) are much harder to understand.

First -- thank you for the thanks! It means a lot. :) Secondly -- same. It's the way my brain works. In a particular test I was administered a while back, 'coding' (i.e. mapping information transiently to symbols) was by far one of my weakest skills, oddly enough.

To me, I think in shapes. Ideas have shapes. Some ideas have very similar shapes.

This makes me very good at neural network engineering and research.

Re: Kullback–Leibler divergence

#48

Post by 3abiton »

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?

Re: Kullback–Leibler divergence

#49

Post by JonyEpsilon »

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?

Practically speaking, it's a simple measure of how similar two probability distributions are, minimised (with value zero) when they are the same. So it's often used as a loss term in optimisations when you want two distributions to be pushed towards being similar. Sometimes this motivated by clever reasoning about information/probability ... but often it's more just "slap a KL on it", because it tends to work.

Re: Kullback–Leibler divergence

#50

Post by janalsncm »

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.
Post reply on HN