Natural Latents Are Not Robust To Tiny Mixtures

In our previous natural latent posts, our core theorem typically says something like:

Assume two agents have the same predictive distribution $P\left[X\right]$ over variables $X$, but model that distribution using potentially-different latent variables. If the latents both satisfy some simple “naturality” conditions (mediation and redundancy) then the two agents’ latents contain approximately the same information about $X$. So, insofar as the two agents both use natural latents internally, we have reason to expect that the internal latents of one can be faithfully translated into the internal latents of the other.

This post is about one potential weakness in that claim: what happens when the two agents’ predictive distributions are only approximately the same?

Following the pattern of our previous theorems, we’d ideally say something like

If the two agents’ distributions are within $ϵ$ of each other (as measured by some KL-divergences), then their natural latents contain approximately the same information about $X$, to within some $O\left(ϵ\right)$ bound.

But that turns out to be false.

The Tiny Mixtures Counterexample

Let’s start with two distributions, $P^0$ and $Q^0$, over $X$. These won’t be our two agents’ distributions—we’re going to construct our two agents’ distributions by mixing these two together, as the name “tiny mixtures” suggests.

$P^0$ and $Q^0$ will have extremely different natural latents. Specifically:

• $X_1$ consists of 1 million bits, $X_2$ consists of another 1 million bits

• Under $P^0$, $X_1$ is uniform, and $X_2=X_1$. So, there is an exact natural latent ${\Lambda }^P=X_1=X_2$ under $P^0$.

• Under $Q^0$, $X_1$ and $X_2$ are independent and uniform. So, the empty latent ${\Lambda }^Q$ is exactly natural under $Q^0$.

Mental picture: we have a million-bit channel, under $P^0$ the output ($X_2$) is equal to the input ($X_1$), while under $Q^0$ the channel hardware is maintained by Comcast so they’re independent.

Now for our two agents’ distributions, $P$ and $Q$. $P$ will be almost $P^0$, and $Q$ will be almost $Q^0$, but each agent puts a $\frac{1}{2^{50}}$ probability on the other distribution:

• $P=(1-\frac{1}{2^{50}})P^0+\frac{1}{2^{50}}{Q}^0$

• $Q=\frac{1}{2^{50}}{P}^0+(1-\frac{1}{2^{50}})Q^0$

First key observation: $D_{KL}\left(P||Q\right)$ and $D_{KL}\left(Q||P\right)$ are both roughly 50 bits. Calculation:

• $D_{KL}\left(P||Q\right)={\sum }_{X_1,X_2}P\left[X\right]\left(\text{log}P\right[X]-\text{log}Q[X\left]\right)$ $\approx {\sum }_{X_1=X_2}\frac{1}{2^{1000000}}(-1000000-\text{log}(\frac{1}{2^{2000000}}+\frac{1}{2^{50}}\frac{1}{2^{1000000}})\approx 50$

• $D_{KL}\left(Q||P\right)={\sum }_{X_1,X_2}Q\left[X\right]\left(\text{log}Q\right[X]-\text{log}P[X\left]\right)$ $\approx {\sum }_{X_1\ne X_2}\frac{1}{2^{2000000}}(-2000000-\text{log}(\frac{1}{2^{50}}\frac{1}{2^{2000000}}\left)\right)\approx 50$

Intuitively: since each distribution puts roughly $\frac{1}{2^{50}}$ on the other, it takes about 50 bits of evidence to update from either one to the other.

Second key observation: the empty latent is approximately natural under $Q$, and the latent $\Lambda :=X_1$ is approximately natural under $P$. Epsilons:

• Under $Q$, the empty latent satisfies mediation to within about $\frac{1}{2^{50}}\ast 1000000\approx \frac{1}{2^{30}}$ bits (this is just mutual information of $X_1$ and $X_2$ under $Q$), and redundancy exactly (since the empty latent can always be exactly computed from any input).

• Under $P$, $\Lambda :=X_1$ satisfies mediation exactly (since $X_1$ mediates between $X_1$ and anything else), redundancy with respect to $X_2$ exactly ($\Lambda =X_1$ can be exactly computed from just $X_1$ without $X_2$), and redundancy with respect to $X_1$ to within about $\frac{1}{2^{50}}\ast 1000000\approx \frac{1}{2^{30}}$ bits (since there’s a $\frac{1}{2^{50}}$ chance that $X_2$ doesn’t tell us the relevant 1000000 bits).

… and of course the information those two latents tell us about $X$ differs by 1 million bits: one of them is empty, and the other directly tells us 1 million bits about $X_1$.

Now, let’s revisit the claim we would’ve liked to make:

If the two agents’ distributions are within $ϵ$ of each other (as measured by some KL-divergences), then their natural latents contain approximately the same information about $X$, to within some $O\left(ϵ\right)$ bound.

Tiny mixtures rule out any claim along those lines. Generalizing the counterexample to an $N$ bit channel (where $N=1000000$ above) and a mixin probability of $\frac{1}{2^M}$ (where $M=50$ above), we generally see that the two latents are natural over their respective distributions to about $\frac{1}{2^M}N$, the $D_{KL}$ between the distributions is about $\frac{1}{2^M}$ in either direction, yet one latent contains $N$ bits of information about $X$ while the other contains zero. By choosing $2^M>>N$, with both $M$ and $N$ large, we can get arbitrarily precise natural latents over the two distributions, with the difference in the latents exponentially large with respect to the $D_{KL}$’s between distributions.

What To Do Instead?

So the bound we’d ideally like is ruled out. What alternatives might we aim for?

Different Kind of Approximation

Looking at the counterexample, one thing which stands out is that $P$ and $Q$ are, intuitively, very different distributions. Arguably, the problem is that a “small” $D_{KL}$ just doesn’t imply that the distributions are all that close together; really we should use some other kind of approximation.

On the other hand, $D_{KL}$ is a pretty nice principled error-measure with nice properties, and in particular it naturally plugs into information-theoretic or thermodynamic machinery. And indeed, we are hoping to plug all this theory into thermodynamic-style machinery down the road. For that, we need global bounds, and they need to be information-theoretic.

Additional Requirements for Natural Latents

Coming from another direction: a 50-bit update can turn $Q$ into $P$, or vice-versa. So one thing this example shows is that natural latents, as they’re currently formulated, are not necessarily robust to even relatively small updates, since 50 bits can quite dramatically change a distribution.

Interestingly, there do exist other natural latents over these two distributions which are approximately the same (under their respective distributions) as the two natural latents we used above, but more robust (in some ways) to turning one distribution into the other. In particular: we can always construct a natural latent with competitively optimal approximation via resampling. Applying that construction to $Q$, we get a latent which is usually independent random noise (which gives the same information about $X$ as the empty latent), but there’s a $\frac{1}{2^{50}}$ chance that it contains the value of $X_1$ and another $\frac{1}{2^{50}}$ chance that it contains the value of $X_2$. Similarly, we can use the resampling construction to find a natural latent for $P$, and it will have a $\frac{1}{2^{50}}$ chance of containing random noise instead of $X_1$, and an independent $\frac{1}{2^{50}}$ chance of containing random noise instead of $X_2$.

Those two latents still differ in their information content about $X$ by roughly 1 million bits, but the distribution of $X$ given each latent differs by only about 100 bits in expectation. Intuitively: while the agents still strongly disagree about the distribution of their respective latents, they agree (to within ~100 bits) on what each value of the latent says about $X$.

Does that generalize beyond this one example? We don’t know yet.

But if it turns out that the competitively optimal natural latent is generally robust to updates, in some sense, then it might make sense to add a robustness-to-updates requirement for natural latents—require that we use the “right” natural latent, in order to handle this sort of problem.

Same Distribution

A third possible approach is to formulate the theory around a single distribution $P\left[X\right]$.

For instance, we could assume that the environment follows some “true distribution”, and both agents look for latents which are approximately natural over the “true distribution” (as far as they can tell, since the agents can’t observe the whole environment distribution directly). This would probably end up with a Fristonian flavor.

ADDED July 9: The Competitively Optimal Natural Latent from Resampling Always Works (At Least Mediocrely)

Recall that, for a distribution $P[X_1,...,X_n]$, we can always construct a competitively optimal natural latent (under strong redundancy) $X^{\prime }$ by resampling each component $X_i$ conditional on the others $X_{\overline{i}}$, i.e.

$P[X=x,X^{\prime }=x^{\prime }]:=P[X=x]{\prod }_{i}P[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]$

We argued above that this specific natural latent works just fine in the tiny mixtures counterexample: roughly speaking, the resampling natural latent constructed for $P$ approximates the resampling natural latent constructed for $Q$ (to within an error comparable to how well $P$ approximates $Q$).

Now we’ll show that that generalizes. Our bound will be mediocre, but it’s any bound at all, so that’s progress.

Specifically: suppose we have two distributions over the same variables, $P[X_1,...,X_n]$ and $Q[X_1,...,X_n]$. We construct a competitively optimal natural latent $X^{\prime }$ via resampling for each distribution:

$P[X=x,X^{\prime }=x^{\prime }]:=P[X=x]{\prod }_{i}P[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]$

$Q[X=x,X^{\prime }=x^{\prime }]:=Q[X=x]{\prod }_{i}Q[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]$

Then, we’ll use $E\left[D_{KL}\right(P\left[X^{\prime }|X\right]||Q\left[X^{\prime }|X\right]\left)\right]$ (with expectation taken over $X$ under distribution $P$) as a measure of how well $Q$‘s latent $X^{\prime }$ matches $P$’s latent $X^{\prime }$. Core result:

$E\left[D_{KL}\right(P\left[X^{\prime }|X\right]||Q\left[X^{\prime }|X\right]\left)\right]\le n{D}_{KL}\left(P\right[X\left]||Q\right[X\left]\right)$

Proof:

$E\left[D_{KL}\right(P\left[X^{\prime }|X\right]||Q\left[X^{\prime }|X\right]\left)\right]=E\left[D_{KL}\right({\prod }_{i}P[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]||{\prod }_{i}Q[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]\left)\right]$

$={\sum }_{i}E\left[D_{KL}\right(P[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]||Q[X_i=x_i^{\prime }|X_{\overline{i}}=x_{\overline{i}}]\left)\right]$

$={\sum }_{i}E\left[D_{KL}\right(P\left[X_i|X_{\overline{i}}\right]||Q\left[X_i|X_{\overline{i}}\right]\left)\right]$

$\le {\sum }_i\left(E\right[D_{KL}\left(P\right[X_i|X_{\overline{i}}\left]||Q\right[X_i|X_{\overline{i}}\left]\right)]+D_{KL}(P\left[X_{\overline{i}}\right]||Q\left[X_{\overline{i}}\right]\left)\right)$

$={\sum }_i{D}_{KL}\left(P\right[X\left]||Q\right[X\left]\right)$

$=n{D}_{KL}\left(P\right[X\left]||Q\right[X\left]\right)$

So we have a bound. Unfortunately, the factor of $n$ (number of variables) makes the bound kinda mediocre. We could sidestep that problem in practice by just using natural latents over a small number of variables at any given time (which is actually fine for many and arguably most use cases). But based on the proof, it seems like we should be able to improve a lot on that factor of n; we outright add ${\sum }_i{D}_{KL}\left(P\right[X_{\overline{i}}\left]||Q\right[X_{\overline{i}}\left]\right))$, which should typically be much larger than the quantity we’re trying to bound.