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

71–77 of 77 posts

Re: Kullback–Leibler divergence

#71

Post by kgwgk »

leourbina wrote: post #70
kgwgk wrote: post #35

Earlier quoted context omitted.

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

I was just clarifying that norm and distance are not the same as you seemed to imply with "a real distance (a norm)". (And I think one can also intuitively understand that the distance from A to B may not be the same as the distance from B to A as soon as we step outside of geometry.)

Re: Kullback–Leibler divergence

#72

Post by joelthelion »

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.

I think in part because it's really nice to measure information in bits rather than tiny probabilities. And it aligns well with how information is stored.

Re: Kullback–Leibler divergence

#73

Post by yobbo »

imjonse wrote: post #22
mrv_asura wrote: post #9

I learnt about KL Divergence recently and it was pretty cool to know that cross-entropy loss originated from KL Divergence. But could someone give me the cases where it is preferred to use Mean-squared Error loss vs Cross-entropy loss? Is there any merits or demerits of using either?

If you look deep enough they are not exclusive. From the deeplearning book: "Many authors use the term “cross-entropy” to identify specifically the negative log-likelihood of a Bernoulli or softmax distribution, but that is a misnomer. Any loss consisting of a negative log-likelihood is a cross- entropy between the empirical distribution defined by the training set and the probability distribution defined by model. For…

Also, the gradients of "softmax loss" and mean-square-error loss are the same. The network learns to optimize the same function, up until the output activation.

Re: Kullback–Leibler divergence

#74

Post by jwarden »

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…

> Why is surprisal defined as `log (1/p(X=x)`?

Good question. It's because -log P(X) is the number of bits of information I would need to eliminate any surprise about the value of X.

For example, let's say X is the value of an 8-bit register, and each of the 2^8=256 possible values has a probability of 1/256. I would need to learn all 8 bits to know the value of X: so Surprisal(X=x) = -log P(X=x) = -log 1/256 = 8.

Suppose I learned only that X is odd, which is equivalent to learning that the last bit of the register is equal to 1. The probability that X is 1 is 1/2, and so I would need to be provided with -log P(X is odd) = -log 1/2 = 1 bit of information to learn that X is odd.

Information can be thought of as simply the elimination of uncertainty. So Surprisal (uncertainty) is basically a measure of information, but instead of how much information you have, it's how much information you need to eliminate all uncertainty.

Re: Kullback–Leibler divergence

#75

Post by ramblenode »

Majromax wrote: post #63
ramblenode wrote: post #62

Earlier quoted context omitted.

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

That's also the case for probabilities.

Re: Kullback–Leibler divergence

#76

Post by beyondCritics »

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.

> Negative log is the only decreasing function which satisfies f(x * y) = f(x) + f(y)

Times a constant!

Re: Kullback–Leibler divergence

#77

Post by sixo »

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`.

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.

Post reply on HN