Diffractor comments on Less Basic Inframeasure Theory

[Diffractor]

So, we’ve also got an analogue of KL-divergence for crisp infradistributions.

We’ll be using $P$ and $Q$ for crisp infradistributions, and $p$ and $q$ for probability distributions associated with them.$D_{KL}$ will be used for the KL-divergence of infradistributions, and $d_{KL}$ will be used for the KL-divergence of probability distributions. For crisp infradistributions, the KL-divergence is defined as

$D_{KL}\left(P|Q\right):={max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)$

I’m not entirely sure why it’s like this, but it has the basic properties you would expect of the KL-divergence, like concavity in both arguments and interacting well with continuous pushforwards and semidirect product.

Straight off the bat, we have:

Proposition 1: $D_{KL}\left(P|Q\right)\ge 0$

Proof: KL-divergence between probability distributions is always nonnegative, by Gibb’s inequality.

Proposition 2: $D_{KL}\left(P|Q\right)=0\leftrightarrow Q\subseteq P$

$D_{KL}\left(P|Q\right)=0\leftrightarrow {max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)=0\leftrightarrow \forall q\in Q:{min}_{p\in P}{d}_{KL}\left(p|q\right)=0$

$\forall q\in Q:{min}_{p\in P}{d}_{KL}\left(p|q\right)=0\leftrightarrow \forall q\in Q\exists p\in P:d_{KL}\left(p|q\right)=0$

And now, because KL-divergence between probability distributions is 0 only when they’re equal, we have:

$\forall q\in Q\exists p\in P:d_{KL}\left(p|q\right)=0\leftrightarrow \forall q\in Q:q\in P\leftrightarrow Q\subseteq P$

Proposition 3: If $u$ is the uniform distribution on $X$, then $D_{KL}\left(P|u\right)=\ln \left(|X|\right)-H\left(P\right)$

$D_{KL}\left(P|u\right)={min}_{p\in P}{d}_{KL}\left(p|u\right)={min}_{p\in P}\left(H\right(p,u)-H(p\left)\right)$

And the cross-entropy of any distribution with the uniform distribution is always $\ln \left(|X|\right)$, so:

$=\ln \left(|X|\right)+{min}_{p\in P}(-H(p\left)\right)=\ln \left(|X|\right)-{max}_{p\in P}H\left(p\right)=\ln \left(|X|\right)-H\left(P\right)$

Proposition 4: $D_{KL}$ is a concave function over $({\square }^{crisp}X{)}^2$.

Proof: Let’s use $a$ as our number in $[0,1]$ in order to talk about mixtures. Then,

$D_{KL}(a{P}_1+(1-a)P_2|a{Q}_1+(1-a\left)Q_2\right)={max}_{q\in a{Q}_1+(1-a)Q_2}{min}_{p\in a{P}_1+(1-a)P_2}{d}_{KL}\left(p|q\right)$

$={max}_{q_1\in Q_1,q_2\in Q_2}{min}_{p_1\in P_1,p_2\in P_2}{d}_{KL}(a{p}_1+(1-a)p_2|a{q}_1+(1-a\left)q_2\right)$

Then we apply concavity of the KL-divergence for probability distributions to get:

$\le {max}_{q_1\in Q_1,q_2\in Q_2}{min}_{p_1\in P_1,p_2\in P_2}\left(a{d}_{KL}\right(p_1|q_1)+(1-a\left)d_{KL}\right(p_2|q_2\left)\right)$

$={max}_{q_1\in Q_1,q_2\in Q_2}\left(a{min}_{p_1\in P_1}{d}_{KL}\right(p_1|q_1)+(1-a\left){min}_{p_2\in P_2}{d}_{KL}\right(p_2|q_2\left)\right)$

$=a{max}_{q_1\in Q_1}{min}_{p_1\in P_1}{d}_{KL}\left(p_1|q_1\right)+(1-a){max}_{q_2\in Q_2}{min}_{p_2\in P_2}{d}_{KL}\left(p_2|q_2\right)$

$=a{D}_{KL}\left(P_1|Q_1\right)+(1-a)D_{KL}\left(P_2|Q_2\right)$

Proposition 5: $D_{KL}(P⋉K|Q⋉J)\ge D_{KL}\left(P|Q\right)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}(K\left(x\right)|J\left(x\right)\left)\right]$

$D_{KL}(P⋉K|Q⋉J)={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{d}_{KL}(p⋉k|q⋉j)$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{\sum }_{x,y}(p⋉k)(x,y)\cdot \ln \left(\frac{(p⋉k)(x,y)}{(q⋉j)(x,y)}\right)$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{\sum }_{x,y}p\left(x\right)\cdot k_x\left(y\right)\cdot \ln \left(\frac{p\left(x\right)\cdot k_x\left(y\right)}{q\left(x\right)\cdot j_x\left(y\right)}\right)$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{\sum }_{x,y}p\left(x\right)\cdot k_x\left(y\right)\cdot (\ln \left(\frac{p\left(x\right)}{q\left(x\right)}\right)+\ln \left(\frac{k_x\left(y\right)}{j_x\left(y\right)}\right))$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}\left({\sum }_{x,y}p\right(x)\cdot k_x(y)\cdot \ln \left(\frac{p\left(x\right)}{q\left(x\right)}\right)+{\sum }_{x,y}p(x)\cdot k_x(y)\cdot \ln \left(\frac{k_x\left(y\right)}{j_x\left(y\right)}\right))$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}(\left({\sum }_{x}p\right(x)\cdot \ln \left(\frac{p\left(x\right)}{q\left(x\right)}\right)\cdot \left({\sum }_y{k}_x\right(y\left)\right))$
$+\left({\sum }_{x}p\right(x)\cdot \left({\sum }_y{k}_x\right(y)\cdot \ln \left(\frac{k_x\left(y\right)}{j_x\left(y\right)}\right))))$

At this point we can abbreviate the KL-divergence, and observe that we have a multiplication by 1, to get:

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}\left(d_{KL}\right(p|q)+{\sum }_{x}p(x)\cdot d_{KL}(k_x|j_x\left)\right)$

And then pack up the expectation

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}\left(d_{KL}\right(p|q)+E_p[\lambda x.d_{KL}\left(k_x|j_x\right)\left]\right)$

Then, with the choice of $q$ and $j$ fixed, we can move the choice of the $k_x$ all the way inside, to get:

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.{min}_{k_x\in K\left(x\right)}{d}_{KL}\left(k_x|j_x\right)\left]\right)$

Now, there’s something else we can notice. When choosing $j$, it doesn’t matter what $p$ is selected, you want to take every $x$ and maximize the quantity inside the expectation, that consideration selects your $j_x$. So, then we can get:

$={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.{max}_{j_x\in J\left(x\right)}{min}_{k_x\in K\left(x\right)}{d}_{KL}\left(k_x|j_x\right)\left]\right)$

And pack up the KL-divergence to get:

$={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

And distribute the min to get:

$\ge {max}_{q\in Q}\left({min}_{p\in P}{d}_{KL}\right(p|q)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

And then, we can pull out that fixed quantity and get:

$={max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}(K\left(x\right)|J\left(x\right)\left)\right]$

And pack up the KL-divergence to get:

$=D_{KL}\left(P|Q\right)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}(K\left(x\right)|J\left(x\right)\left)\right]$

Proposition 6: $D_{KL}(P_1\times P_2|Q_1\times Q_2)=D_{KL}\left(P_1|Q_1\right)+D_{KL}\left(P_2|Q_2\right)$

To do this, we’ll go through the proof of proposition 5 to the first place where we have an inequality. The last step before inequality was:

$D_{KL}(P⋉K|Q⋉J)={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

Now, for a direct product, it’s like semidirect product but all the $K\left(x\right)$ and $J\left(x\right)$ are the same infradistribution, so we have:

$D_{KL}(P_1\times P_2|Q_1\times Q_2)={max}_{q_1\in Q_1}{min}_{p_1\in P_1}\left(d_{KL}\right(p_1|q_1)+E_{p_1}[\lambda x.D_{KL}\left(P_2|Q_2\right)\left]\right)$

Now, this is a constant, so we can pull it out of the expectation to get:

$={max}_{q_1\in Q_1}{min}_{p_1\in P_1}\left(d_{KL}\right(p_1|q_1)+D_{KL}(P_2|Q_2\left)\right)$

$={max}_{q_1\in Q_1}{min}_{p_1\in P_1}{d}_{KL}\left(p_1|q_1\right)+D_{KL}\left(P_2|Q_2\right)=D_{KL}\left(P_1|Q_1\right)+D_{KL}\left(P_2|Q_2\right)$

Proposition 7: $D_{KL}\left(g_{\ast }\right(P\left)|g_{\ast }\right(Q\left)\right)\le D_{KL}\left(P|Q\right)$

For this, we’ll need to use the Disintegration Theorem (the classical version for probability distributions), and adapt some results from Proposition 5. Let’s show as much as we can before showing this.

$D_{KL}\left(g_{\ast }\right(P\left)|g_{\ast }\right(Q\left)\right)={max}_{q^{\prime }\in g_{\ast }\left(Q\right)}{min}_{p^{\prime }\in g_{\ast }\left(P\right)}{d}_{KL}\left(p^{\prime }|q^{\prime }\right)={max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)$

Now, hypothetically, if we had

$d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)\le d_{KL}\left(p|q\right)$

then we could use that result to get

$\le {max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)=D_{KL}\left(P|Q\right)$

and we’d be done. So, our task is to show

$d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)\le d_{KL}\left(p|q\right)$

for any pair of probability distributions $p$ and $q$. Now, here’s what we’ll do. The $p$ and $q$ gives us probability distributions over $X$, and the $g_{\ast }\left(p\right)$ and $g_{\ast }\left(q\right)$ are probability distributions over $Y$. So, let’s take the joint distribution over $X\times Y$ given by selecting a point from $X$ according to the relevant distribution and applying $g$. By the classical version of the disintegration theorem, we can write it either way as starting with the marginal distribution over $X$ and a semidirect product to $Y$, or by starting with the marginal distribution over $Y$ and you take a semidirect product with some markov kernel to $X$ to get the joint distribution. So, we have:

$d_{KL}(p⋉g|q⋉g)=d_{KL}\left(g_{\ast }\right(p)⋉k|g_{\ast }(q)⋉j)$

for some Markov kernels $k,j:Y\to X$. Why? Well, the joint distribution over $X\times Y$ is given by $p⋉g$ or $q⋉g$ respectively (you have a starting distribution, and $g$ lets you take an input in $X$ and get an output in $Y$). But, breaking it down the other way, we start with the marginal distribution of those joint distributions on $Y$ (the pushforward w.r.t. $g$), and can write the joint distribution as semidirect product going the other way. Basically, it’s just two different ways of writing the same distributions, so that’s why KL-divergence doesn’t vary at all.

Now, it is also a fact that, for semidirect products (sorry, we’re gonna let $p,q,k,j$ be arbitrary here and unconnected to the fixed ones we were looking at earlier, this is just a general property of semidirect products), we have:

$d_{KL}(p⋉k|q⋉j)=d_{KL}\left(p|q\right)+E_p\left[d_{KL}\right(k\left(x\right)|j\left(x\right)\left)\right]$

To see this, run through the proof of Proposition 5, because probability distributions are special cases of infradistributions. Running up to right up before the inequality, we had

$D_{KL}(P⋉K|Q⋉J)={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

But when we’re dealing with probability distributions, there’s only one possible choice of probability distribution to select, so we just have

$d_{KL}(p⋉k|q⋉j)=d_{KL}\left(p|q\right)+E_p\left[d_{KL}\right(k\left(x\right)|j\left(x\right)\left)\right]$

Applying this, we have:

$d_{KL}\left(p|q\right)+E_p\left[d_{KL}\right(g\left(x\right)|g\left(x\right)\left)\right]=d_{KL}(p⋉g|q⋉g)$
$=d_{KL}\left(g_{\ast }\right(p)⋉k|g_{\ast }(q)⋉j)=d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)+E_{g_{\ast }\left(p\right)}\left[d_{KL}\right(k\left(y\right)|j\left(y\right)\left)\right]$

The first equality is our expansion of semidirect product for probability distributions, second equality is the probability distributions being equal, and third equality is, again, expansion of semidirect product for probability distributions. Contracting the two sides of this, we have:

$d_{KL}\left(p|q\right)+E_p\left[d_{KL}\right(g\left(x\right)|g\left(x\right)\left)\right]=d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)+E_{g_{\ast }\left(p\right)}\left[d_{KL}\right(k\left(y\right)|j\left(y\right)\left)\right]$

Now, the KL-divergence between a distribution and itself is 0, so the expectation on the left-hand side is 0, and we have

$d_{KL}\left(p|q\right)=d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)+E_{g_{\ast }\left(p\right)}\left[d_{KL}\right(k\left(y\right)|j\left(y\right)\left)\right]\ge d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)$

And bam, we have $d_{KL}\left(p|q\right)\ge d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)$ which is what we needed to carry the proof through.