If $P\ll Q$ (that is $P(x)=0$ if $Q(x)=0$, $D_{KL}(P||Q)=E_Q\big[\frac{P}{Q}\log\big(\frac{P}{Q}\big)\big]$ Thus integration is over $Q$. Also, notice that $D_{KL}(P|Q)$ is optimum when $P=Q$.

@Mittens: I do not understand. Why does the KL divergence switches $mathbb E_P$ into $mathbb E_Q \frac1Q$ for $P<<Q$? Also, why is this relevant to my question? I mean: If using your argument, and not $P<<Q$ and we still integrate over P.

Your concern was why expectation is taken with respect to $P$. I am saying that that is an "illusion" since $E_P[\log(P/Q)]=\sum_x\log\Big(\frac{P(x)}{Q(x)}\Big)\frac{P(x)}{Q(x)}Q(x)=E_Q[\log(P/Q)P/Q]$. It is the function $\eta(s)=s\log(s)\mathbb{1}_{s>0}$ what defines the KL-divergence of $P$ relative to $Q$. This is related to what physicists called relative entropy. The second comment is to show that if one deviates from the "base" measure $Q$, $D_{KL}$ becomes positive (when $P=Q$, $D_{KL}(P|Q)=0$.

@Mittens: When looking at $𝐸_𝑄[log(𝑃/𝑄)𝑃/𝑄]$, I might still ask, why not using $𝐸_𝑄[log(𝑃/𝑄)𝑄/𝑃]$ ? Where does $𝜂(𝑠)=𝑠log(𝑠)𝟙𝑠>0$ appear in the KL divergence; what is $s$? The second comment, I understand.

The KL-divergence was adapted from the concept of entropy in thermodynamics (Some clever statistician who also knew Physics, or perhaps some statistician who knew about information theory). Any way, the notion of divergence measures in Statistics is develop by comparison of measures though convex functions. There are a whole family of divergence measures that generalize entropy. Using $\eta(s)=s\log(s)\mathbb{1}_{s>0}$ happened yields the known relative entropy. I wrote a little digression about this in this posting.

Here is a Wikipedia article that touches on this.

@Mittens: I am sorry, but this confuses me more than it enlightens me. Rephrasing my original question: Why is $\sum_x 𝑃(𝑥) \cdot log( 𝑃(𝑥) / 𝑄(𝑥))$ used instead of $\sum_x Q(𝑥) \cdot log( 𝑃(𝑥) / 𝑄(𝑥))$ ?

The definition of relative entropy of $P$ relative to $Q$ is $D_{HL}(P|Q)=E_Q\Big[\frac{P}{Q}\log\big(\frac{P}{Q}\big)\Big]$. (in Physcis they use the $-D_{KL}(P|Q)$). It just so happens that the expression for $D_{KL}$ simplifies to $D_{KL}(P|Q)=E_P[\log(P/Q)]$. It is assume that $P\ll Q$.

@Mittens

@Make42 The intuition is not complete without the Physics. The definition of $D_{KL}$ is based on the concept of entropy (Thermodynamics) Engineers and Statisticians adopt it because it turns out to be useful for their purposes. The appearance of the function $\eta(s)=s\log s$ follows from the Physics intuition: The entropy of two thermodynamical systems combined is the sum of the entropy of each system.

A quick read at this will give you a better idea (do not worry if you don't follow it entirely, just the ideas).

@Mittens: I'll check it out at once.

@Mittens: When I consider S = -k_B sum pi * ln(pi), this looks like the KL divergence if we have P(x)/Q(x) for pi. However, then what about the minus at the front ? (I guess we can disregard the Boltzmann constant.)

Ah, no, this is wrong.

@Make42 Yes, disregard the constant. The ideas (about disorder) are similar. Like I said before, for some reason Information theoryst and statisticians took the negative of Physicists entropy. (the later prefer to maximize, the former to minimize)

@Mittens: Even then, this does not work out. I cannot get from $sum pi * ln(pi)$ to $sum P(x) * log( P(x) / Q(x) )$ no matter what I put into pi.

because what you are reading is "entropy" (integration is with respect the universe's measure). you are dealing with relative entropy (a disorder of a measure (p) relative to another one (q)).

In general terms, if $P$ is a probability measure with density $p$ (w.r.t to another measure, say $\mu$) The entropy of $P$ is $H(P):=\int_X p(x)\log(p(x))\,\mu(x)$. Now, one may have two Probability measures, $P$ and $Q$ such that $P$ has density $\frac{dP}{dQ}$ with respect to $Q$; then the entropy of $P$ relative to $Q$ is $H(P|Q):=\int_X \frac{dP}{dQ}(x)\log\Big(\frac{dP}{dQ}(x)\Big)\, Q(dx)$.

If in addition both $P$ and $Q$ have densities $p(x)$ and $q(x)$ with respect to another measure, say $\mu$, then one can check that $H(P|Q)=E_Q[\frac{p}{q}\log\Big(\frac{p}{q}\Big)]=\int_X\frac{p(x)}{q(x)}\log\Big(\frac{p(x)}{q(x)}\big) q(x)\,\mu(dx)=\int_X p(x)\log\Big(\frac{p(x)}{q(x)}\Big)\,\mu(x)=E_P[\log(p/q)]$, which is what you have.

@Mittens: I am lost. What does (dP/dQ)(x) mean?

Which variable is H(P) := \int_X p(x) * log(p(x)) mu(x) integrating over? mu(x) or x?

I come from engineering and machine learning, not so much from probability theory. Maybe you need to lay down some basics that I am not familiar with? Maybe that is the problem for me?

(When I say machine learning, I mean not-so-probabalistic stuff, more optimization theory and deterministic algorithms.)

@Make42 $\int f(x)\,\mu)dx)$ is notation for $\int f\,d\mu$, the integral of a function $f$ with respect to the measure $\mu$. If a measure $\nu$ has a density $p$ with respect to another measure $\mu$, it means that $\nu(A)=\int_A p\,d\mu$ for all sets $A$. Usually, the density $f$ of $\nu$ with respect to $\mu$ (when it exists) is denoted as $\frac{d\nu}{d\mu}$.

$\int f(x)\,\mu)dx)$?

... A typo, I meant to write $\int f(x)\,\mu(dx)$, notation for $\int f\,d\mu$.

Ok, you see, there I am already lost. How can you integrate over a measure and without any x?

For example, if $\mu$ is the Gaussian measure on the real line, $\mu$ has density $f(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$ with respect to the Lebesgue measure (the measure that assigns to each interval its length). Thus $\mu(A)=\int_A f(x)\,dx$.

Is $\int f(x)\,\mu(dx)$ the same as $\int \mu \cdot f(x) dx$ ?

I have to look up Gaussian measure... (never heard of it :-D )

Is there a way to explain this with undergraduate math?

I can see you are completely lost since you have likely not taken a course in integration in the sense of Lebesgue. OK. Let's substitute $\int_X$ by $\sum_{x\in X}$ and for the time being, the probability measures $P$ and $Q$ on $X$ are of the form $P(A)=\sum_{x\in A}p(x)$, $Q(A)=\sum_{x\in A}q(x)$. Then $H(P|Q)=E_Q[\frac{p}{q}\log\Big(\frac{p}{q}\big)]=\sum_{x\in X}\frac{p(x)}\log(\frac{q(x)}\log\Big(\frac{p(x)}{q(x)}\Big) p(x)\log\Big(\frac{p(x)}{q(x)}\big)=E_P[\log(p/q)]$.

That is fine... you should take a Probability course based on Measure theory (either in EE department or in a Maths/Statistics department). unfortunately, without the basics of such a course, progress to more sophisticated areas becomes limited (because the part of the foundations are based on integration theory). I took a few courses in EE departments (information theor, Queueing theory, and optimization) at the graduate level.

I can't take courses, cause I am working remote. If you know an online course, feel free to recommend.

(I am still reading your text.)

the foundations are, as you will see, very mathematical (integration theory, functional analysis, etc).

It will not help with my research though. Even my papers are considered by some reviewers "too math heavy".

MIT Open courses has some integration theory (Graduate Analysis). Check for online graduate courses in Probability, where very likely they will develop all the measure theoretic framework right away. The book of Durrett (Probaility theory now un Cambridge Univ. Press) is a good book to have (you may get a copy for free in Rick Durret's website at Duke)

@Mittens: Can you check your formulas? Do you have typos?

.. typos. Let me rewrite the formula: $H(P|Q)=E_Q[\frac{p}{q}\log\Big(\frac{p}{q}\Big)]=\sum_{x\in X}\frac{p(x)}{q(x)}\log\Big(\frac{p(x)}{q(x)}\Big)q(x)=\sum_{x\in X}p(x)\frac{p(x)}{q(x)}=E_P[\log(p/q)]$

That is the definition of entropy of $P$ relative to $Q$. Why one can dream of such a definition? Well, at is core, it is based on Physics (Thermodynamics). The Information theorists adopted it. There is an axiomatic notion of what entropy is. That leads to the appearance of the function $\eta(s)=s\log(s)$. Thus, $H(P|Q):=E_Q[\eta(p/q)]$

@Mittens: give me a sec...

The function $\eta$ happens to be the one that satisfies the axiomatics of entropy in information theory, just the way it work for Boltzmann and Gibbs in their development of Statistical Mechanics.

So, someone had $H(P|Q):=E_Q[\eta(p/q)]$ in mind and was searching for an eta. And then $\eta(s)=s\log(s)$ was found based on some criteria?

@Mittens?

Yes! The criteria is based ion what entropy is and what properties it has.

@Mittens: Is there an intuitive explanation of where the formula for $H(P|Q):=E_Q[\eta(p/q)]$ is coming from?

@Mittens: Can you explain what criteria lead to $\eta(s)=s\log(s)$?

There are different approaches. Here is one. Here is another one (rather simpler but with less motivation)

Here is yet another one but a little terse (as you can see is in posted in MO, the mathematics research site os Stack Exchange).

That is entropy of of the law of the random variable $X$. Suppose (forget if I use - or +, at this point is not that relevant) $p(x)=P[X=x]$. The $H(X)=E_X[\log(P(X)]=\sum \log(p(x)) \,p(x)$. This entropy is not a relative entropy, it is the entropy of the law of $X$. You are dealing with "relative entropy" where you have either two random variables $X$ and $Y$ with lows $p$ and $q$ or two Probability measures $P$ and $Q$ with densities $p$ and $q$.

In, any case, the axiomatics of entropy leads to a "natural" definition of relative entropy.

@Mittens

Or maybe there is a less strict but inuitive explanation?

The first link is more to my liking. The point is that $H(X)$ or (rather $H(P)$, where $P$ is the probability distribution of $P$) is a measure of disorder (or information dependent on your inclination) of $P$. $H(P)=E_P[\log(P(X)]=\sum_Xp(X=x)\log(P(x=x))$. Here the is an integration process going on. The summation is in a sense integration with respect to a counting measure. This is where measure theory comes at handy.

$P$ has density $p$ with respect to this counting measure. What if instead of integrating with respect to this "counting" measure $m$, integration is done with respect to another probability measure (say $Q$) and that $Q$ has also density, say $q$. Then (assuming that $p(x)=0$ when $q(x)=0$) $P$ has a density with respect to $Q$ and is given by $\frac{p}{q}$.

Thus, it would be natural to define $H(P|Q)$ as $E_P[\log(p/q)]$. Expanding a little one gets that $H(P|Q)=E_Q[\frac{p}{q}\log(p/q)]$. This is a property of densities $\frac{dP}{dm}=\frac{dP}{dQ}\frac{dQ}{dm}$ which is based on Lebegue integration theorem.

$m(dx)$ is integration with respect to a measure $m$.

@Make42 Just did above your last comment. I think I should closed this discussion by just giving you one more reading material that seems to be at a reasonable level.

Specially this section: Kullback-Leibler information measure on that set of notes.

@Mittens: Ok, thanks!