Resampling Conserves Redundancy (Approximately)

Suppose random variables $X_1$ and $X_2$ contain approximately the same information about a third random variable $\Lambda$, i.e. both of the following diagrams are satisfied to within approximation $ϵ$:

“Red” for redundancy

We call $\Lambda$ a “redund” over $X_1,X_2$, since conceptually, any information $\Lambda$ contains about $X$ must be redundantly represented in both $X_1$ and $X_2$ (to within approximation).

Here’s an intuitive claim which is surprisingly tricky to prove: suppose we construct a new variable ${\Lambda }^{\prime }$ by sampling from $P\left[\Lambda |X_2\right]$, so the new joint distribution is

$P[X_1=x_1,X_2=x_2,{\Lambda }^{\prime }={\lambda }^{\prime }]=P[X_1=x_1,X_2=x_2]P[\Lambda ={\lambda }^{\prime }|X_2=x_2]$

By construction, this “resampled” variable satisfies one of the two redundancy diagrams perfectly: $X_1\to X_2\to {\Lambda }^{\prime }$. Intuitively, we might expect that ${\Lambda }^{\prime }$ approximately satisfies the other redundancy diagram as well; conceptually, ${\Lambda }^{\prime }$ (approximately) only contains redundant information about $X$, so $X_2$ contains (approximately) the same information about ${\Lambda }^{\prime }$ as $X$ does, so the resampling operation should result in (approximately, in some sense) the same distribution we started with and therefore (approximately) the same properties.

In this post, we’ll prove that claim and give a bound for the approximation error.

Specifically:

Theorem: Resampling (Approximately) Conserves (Approximate) Redundancy

Let random variables $X_1,X_2$, $\Lambda$ satisfy the diagrams $X_1\to X_2\to \Lambda$ and $X_2\to X_1\to \Lambda$ to within $ϵ$, i.e.

$ϵ\ge D_{KL}\left(P\right[X_1,X_2,\Lambda \left]||P\right[X_1,X_2\left]P\right[\Lambda |X_2\left]\right)$

$ϵ\ge D_{KL}\left(P\right[X_1,X_2,\Lambda \left]||P\right[X_1,X_2\left]P\right[\Lambda |X_1\left]\right)$

Also, assume $P[X,\Lambda ]>0$.

Construct ${\Lambda }^{\prime }$ by sampling from $P\left[\Lambda |X_2\right]$, so $P[X_1,X_2,{\Lambda }^{\prime }]=P[X_1,X_2]P[\Lambda ={\lambda }^{\prime }|X_2]$. Then $X_1\to X_2\to {\Lambda }^{\prime }$ is perfectly satisfied by construction, and $X_2\to X_1\to {\Lambda }^{\prime }$ is satisfied to within $9ϵ$, i.e.

$9ϵ\ge D_{KL}\left(P\right[X_1,X_2,{\Lambda }^{\prime }\left]||P\right[X_1,X_2\left]P\right[{\Lambda }^{\prime }|X_1\left]\right)$

---

In diagrammatic form:

(Where O(Ɛ) in this version of the proof is 9Ɛ, specifically.)

Notation

We will use the shorthand $D_{KL}(<\text{diagram over X}>)$ to mean $D_{KL}\left(P\right[X\left]||{\prod }_{i}P\right[X_i|X_{pa\left(i\right)}\left]\right)$. For instance, $D_{KL}(X_1\to X_2\to \Lambda )$ is shorthand for $D_{KL}\left(P\right[X_1,X_2,\Lambda \left]||P\right[X_1\left]P\right[X_2|X_1\left]P\right[\Lambda |X_2\left]\right)$, which is equivalent to $D_{KL}\left(P\right[X,\Lambda \left]||P\right[X\left]P\right[\Lambda |X_2\left]\right)$.

We will work with nats for mathematical convenience (i.e. all logarithms are natural logs).

Proof

The proof proceeds in three steps:

• From $\Lambda$, we can construct a new variable $\Gamma$ which is equal to $\Lambda$ with probability $p$ and is otherwise a constant. Then the errors on all diagrams in the theorem for $\Gamma$ are the same as the corresponding errors for $\Lambda$, but scaled down by factor $p$. This allows us to focus only on the regime of arbitrarily small errors, and obtain a global bound from that regime.

• Within the regime of arbitrarily small errors, $D_{KL}\left(P||Q\right)$ is approximately (to second order) equal to twice the Hellinger distance, $2{\sum }_X(\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}{)}^2$. Hellinger distance is a straightforward Euclidean distance metric, so we can use standard geometric reasoning on it.

• The Hellinger distance between $P\left[\Lambda |X_2\right]$ and $P\left[\Lambda |X\right]$, between $P\left[\Lambda |X\right]$ and $P\left[\Lambda |X_1\right]$, and between $P\left[\Lambda |X_1\right]$ and $P\left[{\Lambda }^{\prime }|X_1\right]$ are all small, so end-to-end the Hellinger distance between $P\left[\Lambda |X_2\right]$ and $P\left[{\Lambda }^{\prime }|X_1\right]$ is small. That yields the bound we’re after.

Step 1: Scaling Down The Errors

First we construct the new variable $\Gamma$ as a stochastic function of $\Lambda$. Specifically, $\Gamma$$=\Lambda$ with probability $p$, else $\Gamma$ is a constant $C$, where $C$ is outside the support of $\Lambda$ (so when we see $\Gamma =C$, we gain no information about $\Lambda$).

A little algebra confirms that $\Gamma$‘s errors are simply $\Lambda$’s errors scaled down by $p$:

$D_{KL}\left(P\right[X,\Gamma \left]||P\right[X\left]P\right[\Gamma |X_i\left]\right)$

$=E_X\left[P\right[\Gamma =C\left]\right(lnP[\Gamma =C|X]-lnP[\Gamma =C|X_i])+{\sum }_{\lambda }P[\Gamma =\lambda |X\left]\right(lnP[\Gamma =\lambda |X]-lnP[\Gamma =\lambda |X_i]\left)\right]$

$=E_X\left[\right(1-p\left)\right(ln(1-p)-ln(1-p))+{\sum }_{\lambda }pP[\Lambda =\lambda |X\left]\right(ln\left(pP\right[\Lambda =\lambda |X\left]\right)-ln\left(pP\right[\Lambda =\lambda |X_i\left]\right)\left)\right]$

$=p{E}_X\left[{\sum }_{\lambda }P\right[\Lambda =\lambda |X\left]\right(ln\left(P\right[\Lambda =\lambda |X\left]\right)-ln\left(P\right[\Lambda =\lambda |X_i\left]\right)\left)\right]$

$=p{D}_{KL}\left(P\right[X,\Lambda \left]||P\right[X\left]P\right[\Lambda |X_i\left]\right)$

Similarly, constructing ${\Gamma }^{\prime }$ just like ${\Lambda }^{\prime }$ (i.e. $P[X,{\Gamma }^{\prime }]=P\left[X\right]P[\Gamma ={\gamma }^{\prime }|X_2]$) is equivalent to constructing ${\Gamma }^{\prime }$ as a stochastic function of ${\Lambda }^{\prime }$ where ${\Gamma }^{\prime }={\Lambda }^{\prime }$ with probability $p$, else ${\Gamma }^{\prime }$ is $C$. So, by the same algebra as above,

$D_{KL}\left(P\right[X,{\Gamma }^{\prime }\left]||P\right[X\left]P\right[{\Gamma }^{\prime }|X_i\left]\right)=p{D}_{KL}\left(P\right[X,{\Lambda }^{\prime }\left]||P\right[X\left]P\right[{\Lambda }^{\prime }|X_i\left]\right)$

The upshot: if there exists a distribution over variables $X_1,X_2,\Lambda$ for which

$D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })>n\cdot \text{max}\left(D_{KL}\right(X_1\to X_2\to \Lambda ),D_{KL}(X_2\to X_1\to \Lambda \left)\right)$

then there also exists a distribution satisfying the same inequality with all $D_{KL}$‘s arbitrarily small^[1]. Flipping that statement around: if there does not exist any distribution for which the $D_{KL}$’s are all arbitrarily small and the inequality is satisfied, then there does not exist any distribution for which the inequality is satisfied.

In other words: if we can show

$D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })\le n\cdot \text{max}\left(D_{KL}\right(X_1\to X_2\to \Lambda ),D_{KL}(X_2\to X_1\to \Lambda \left)\right)\le nϵ$

in the regime where all the $D_{KL}$’s are arbitrarily small, then the same inequality is also established globally, proving our theorem. The rest of the proof will therefore show

$D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })\le n\cdot \text{max}\left(D_{KL}\right(X_1\to X_2\to \Lambda ),D_{KL}(X_2\to X_1\to \Lambda \left)\right)$

in the regime where all the $D_{KL}$‘s are arbitrarily small. In particular, we’ll use a second order approximation for the $D_{KL}$’s.

Step 2: Second Order Approximation

Validity

Before we can use a second order approximation of the $D_{KL}$’s, we need to show that small $D_{KL}$ implies that second order approximationis valid.

For that purpose, we use the Hellinger-KL inequality:

$D\left(P||Q\right)\ge 2ln\frac{2}{2-H^2(P,Q)}$

where $H^2(P,Q):={\sum }_X(\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}{)}^2$ is the squared Hellinger distance.^[2]

Using standard logarithm inequalities, we can weaken the Hellinger-KL inequality to

$D\left(P||Q\right)\ge H^2(P,Q)$

So, as $D_{KL}\left(P||Q\right)$ goes to 0, the Hellinger distance goes to 0, and therefore $\sqrt{P}$ and $\sqrt{Q}$ are arbitrarily close together in standard Euclidean distance. Since $D_{KL}$ is smooth (for strictly positive distributions, which we have assumed), we can therefore use a second order approximation (with respect to $\sqrt{P}-\sqrt{Q}$) for our arbitrarily small $D_{KL}$’s.

Expansion

Now for the second order expansion itself.

Our small quantity is $\delta \left[X\right]:=\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}$. Then

$D_{KL}\left(P||Q\right)={\sum }_{X}P\left[X\right]\left(lnP\right[X]-2ln\sqrt{Q\left[X\right]})$

$={\sum }_{X}P\left[X\right]\left(lnP\right[X]-2ln(\sqrt{P\left[X\right]}-\delta \left[X\right]\left)\right)$

$={\sum }_{X}P\left[X\right]\left(lnP\right[X]-2ln(\sqrt{P\left[X\right]})+2\frac{\delta \left[X\right]}{\sqrt{P\left[X\right]}}+2\frac{1}{2}(\frac{\delta \left[X\right]}{\sqrt{P\left[X\right]}}{)}^2)+o({\delta }^3)$

$={\sum }_{X}2\sqrt{P\left[X\right]}\delta \left[X\right]+\delta [X{]}^2+o({\delta }^3)$

To simplify that further, we can use the sum-to-1 constraints on the distributions: $\sqrt{Q\left[X\right]}=\sqrt{P\left[X\right]}-\delta \left[X\right]$ implies

${\sum }_{X}Q\left[X\right]={\sum }_X(\sqrt{P\left[X\right]}-\delta [X]{)}^2={\sum }_{X}P[X]-2\sqrt{P\left[X\right]}\delta [X]+\delta [X{]}^2$

so ${\sum }_{X}2\sqrt{P\left[X\right]}\delta \left[X\right]={\sum }_X\delta [X{]}^2$. That simplifies our second order approximation to

$D_{KL}\left(P||Q\right)=2{\sum }_X\delta [X{]}^2+o({\delta }^3)$

$=2{\sum }_X(\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}{)}^2+o({\delta }^3)$

i.e. in the second order regime $D_{KL}$ is twice the Hellinger distance.

Combining this with Step 1, we’ve now established that if we can prove our desired bound for Hellinger distances rather than $D_{KL}$, then the bound also applies globally for $D_{KL}$ errors. So now, we can set aside the notoriously finicky KL divergences, and work with good ol’ Euclidean geometry.

Step 3: Good Ol’ Euclidean Geometry

Writing everything out in the second order regime, our preconditions say

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2]$

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_1\right]}{)}^2]$

and we want to bound

$2E_X\left[{{\sum }_{\Lambda }}^{\prime }\right(\sqrt{P\left[{\Lambda }^{\prime }|X\right]}-\sqrt{P\left[{\Lambda }^{\prime }|X_1\right]}{)}^2]$

$=2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X_2\right]}-\sqrt{{\sum }_{X_2^{\prime }}P\left[\Lambda |X_2^{\prime }\right]P\left[X_2^{\prime }|X_1\right]}{)}^2]$

That last expression has a Jensen vibe to it, so let’s use Jensen’s inequality.

Jensen

We’re going to use Jensen’s inequality on the squared Hellinger distance, so we need to establish that squared Hellinger distance is convex as a function of the distributions $P,Q$.

Differentiating $(\sqrt{p}-\sqrt{q}{)}^2$ twice with respect to $(p,q)$ yields the Hessian

$\frac{1}{2}\frac{1}{\sqrt{pq}}\left(\begin{array}{cc}\frac{q}{p}& -1\\ -1& \frac{p}{q}\end{array}\right)$

Note that one column is the other column multiplied by $-\frac{p}{q}$, so one of the eigenvalues is 0. The trace is positive, so the other eigenvalue is positive. Thus, the function is (non-strictly) convex.

Now, we’ll use Jensen’s inequality on

$ϵ\ge E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2]$

Specifically:

• We’ll hold $X_1$ constant, so it’s not involved in our application of Jensen.

• For each $X_1$ value, the expression takes a convex combination with weights $P\left[X_2|X_1\right]$ of the function ${\sum }_{\Lambda }(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2$.

• Viewing $\left(P\right[\Lambda |X],P[\Lambda |X_2\left]\right)$ at fixed $X_1$ as the function’s inputs, the function is convex.

So, applying Jensen’s, we get

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2]$

$\ge 2E_{X_1}\left[{\sum }_{\Lambda }\right(\sqrt{{\sum }_{X_2}P\left[\Lambda |X\right]P\left[X_2|X_1\right]}-\sqrt{{\sum }_{X_2}P\left[\Lambda |X_2\right]P\left[X_2|X_1\right]}{)}^2]$

$=2E_{X_1}\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X_1\right]}-\sqrt{{\sum }_{X_2}P\left[\Lambda |X_2\right]P\left[X_2|X_1\right]}{)}^2]$

$=2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X_1\right]}-\sqrt{{\sum }_{X_2}P\left[\Lambda |X_2\right]P\left[X_2|X_1\right]}{)}^2]$

Euclidean Distances

With that, we have bounds on three (squared) Hellinger distances:

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2]$

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_1\right]}{)}^2]$

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X_1\right]}-\sqrt{{\sum }_{X_2}P\left[\Lambda |X_2\right]P\left[X_2|X_1\right]}{)}^2]$

So, on average over $X$:

• The Euclidean distance between $\sqrt{P\left[\Lambda |X_2\right]}$ and $\sqrt{P\left[\Lambda |X\right]}$ is at most $\sqrt{\frac{ϵ}{2}}$.

• The Euclidean distance between $\sqrt{P\left[\Lambda |X\right]}$ and $\sqrt{P\left[\Lambda |X_1\right]}$ is at most $\sqrt{\frac{ϵ}{2}}$.

• The Euclidean distance between $\sqrt{P\left[\Lambda |X_1\right]}$ and $\sqrt{{\sum }_{X_2}P\left[\Lambda |X_2\right]P\left[X_2|X_1\right]}$ is at most $\sqrt{\frac{ϵ}{2}}$.

So, on average, the Euclidean distance from end-to-end, between $\sqrt{P\left[\Lambda |X_2\right]}$ and $\sqrt{{\sum }_{X_2}P\left[\Lambda |X_2\right]P\left[X_2|X_1\right]}$, is at most $3\sqrt{\frac{ϵ}{2}}$.

That gives us the desired bound:

$(3\sqrt{\frac{ϵ}{2}}{)}^2\ge E_X[{\sum }_{\Lambda }(\sqrt{P\left[\Lambda |X_2\right]}-\sqrt{{\sum }_{X_2^{\prime }}P\left[\Lambda |X_2^{\prime }\right]P\left[X_2^{\prime }|X_1\right]}{)}^2]$

implying

$9ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X_2\right]}-\sqrt{{\sum }_{X_2^{\prime }}P\left[\Lambda |X_2^{\prime }\right]P\left[X_2^{\prime }|X_1\right]}{)}^2]$

Combined with our previous two sections, that establishes the desired upper bound of $9ϵ$ on $D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })$.

Empirical Results and Room for Improvement

Below is a plot of the maximal error achieved via numerical minimization of $-D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })$ subject to a constraint on$D_{KL}(X_1\to X_2\to \Lambda )+D_{KL}(X_2\to X_1\to \Lambda )$, searching over distributions of X and $\Lambda$. Above, we proved that the ratio of those two quantities can be no higher than $\frac{9}{2}$. As expected from the proof, it is visually clear that each point on the curve lies on a line between itself and the origin which itself always lies below the curve. Some, presumably, noise is present due to occasional failures of the optimizer to find the maximum error.

Zooming in on the steepest part of the curve and eyeballing the plot, it looks like the maximum ratio achieved is around 4 (.02/​.005), implying an empirical upper bound of the resampled diagram of ~8$ϵ$:

Looking into the actual solutions found, the solutions with ratio of ~4 involve one of the two terms in the x-axis sum being much larger than the other (5-10x). Therefore we expect to be able, in principle, to get a tighter bound (~4$ϵ$, empirically, rather than the proven 9$ϵ$ or empirical 8$ϵ$.) The most likely place for improvement in the proof is to bound the Hellinger distance between $P\left[\Lambda |X_1\right]$ and $P\left[\Lambda |X_2\right]$ directly by $ϵ$, cutting one step out of the “path”, and that would indeed reduce the bound from 9$ϵ$ to 4$ϵ$. We’ll leave that for future work.

Interesting additional piece for future reference: If we include the mediation condition into the denominator, and so look for a bound in terms of a factor of the sum of all natural latent condition epsilons, we find that the empirical factor in question is 1 (roughly. Not sure what happened at ~0.4):

1. ^

   Note that, since $P[X,\Lambda ]>0$ by assumption, none of the $D_{KL}$’s are infinite. This is the only place where we need $P[X,\Lambda ]>0$; that assumption can probably be eliminated by considering the infinite case directly, but we’re not going to do that here.

2. ^

   A quick aside: while it might look messy at first, the Hellinger distance is a particularly natural way to talk about Euclidean distances between probability distributions. In general, if one wants to view a distribution $P\left[X\right]$ as a vector, $\sqrt{P\left[X\right]}$ is the most natural vector to consider, since the sum-to-1 constraint says $\sqrt{P\left[X\right]}$ is a unit vector under the standard Euclidean distance.