7 ms·

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) = -l

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))

mrfox321 3y ago
Typo in cross entropy, should be p log q
- jwarden 3y ago
  Thank you, fixed.
3abiton 3y ago
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?
- JonyEpsilon 3y ago
  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.
- zmmmmm 3y ago
  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.
  - pama 3y ago
    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.
  - creata 3y ago
    > 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.
sarma17 3y ago
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?
- eutectic 3y ago
  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.
  - beyondCritics 3y ago
    > Negative log is the only decreasing function which satisfies f(x * y) = f(x) + f(y) Times a constant!
  - sarma17 3y ago
    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`.
    - sixo 3y ago
      I think "information" is a better name than surprisal. If your distribution has N equally-likely values, `p(x) = 1/N`, and information/surprisal `I(x) = log(N)`. In base 2, this is how many bits are required to specify exactly WHICH of the N values you're talking about. If `x` is not a single one of the N states but an event consisting of `n(x)` states, then `I(x) = log(N) - log(n(x))`, suggesting it takes _somewhat less information_ to specify this particular state, and it correctly gives 0 if `n(x) = N`, i.e. there's only one state. Exactly what this "less information" means is vague, but you might think of it in terms of compression: if you compress some stream of data which is sampled from `X` with probability `p(x)`, you could use use the shortest codes (0, 10, 11, etc) for the most common values with some "stop word" to say when the end of a datum is reached. `I(x)` captures this sense in general, but it might only become literally true in the limit of a very large stream of data with a very large dictionary.

mrfox321 3y ago

Typo in cross entropy, should be p log q

jwarden 3y ago
Thank you, fixed.

3abiton 3y ago

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?

JonyEpsilon 3y ago
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.
zmmmmm 3y ago
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.
- pama 3y ago
  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.
- creata 3y ago
  > 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.

sarma17 3y ago

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?

eutectic 3y ago
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.
- beyondCritics 3y ago
  > Negative log is the only decreasing function which satisfies f(x * y) = f(x) + f(y) Times a constant!
- sarma17 3y ago
  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`.
  - sixo 3y ago
    I think "information" is a better name than surprisal. If your distribution has N equally-likely values, `p(x) = 1/N`, and information/surprisal `I(x) = log(N)`. In base 2, this is how many bits are required to specify exactly WHICH of the N values you're talking about. If `x` is not a single one of the N states but an event consisting of `n(x)` states, then `I(x) = log(N) - log(n(x))`, suggesting it takes _somewhat less information_ to specify this particular state, and it correctly gives 0 if `n(x) = N`, i.e. there's only one state. Exactly what this "less information" means is vague, but you might think of it in terms of compression: if you compress some stream of data which is sampled from `X` with probability `p(x)`, you could use use the shortest codes (0, 10, 11, etc) for the most common values with some "stop word" to say when the end of a datum is reached. `I(x)` captures this sense in general, but it might only become literally true in the limit of a very large stream of data with a very large dictionary.