J Bostock comments on $500 Bounty Problem: Are (Approximately) Deterministic Natural Latents All You Need?

[J Bostock]

I’ve been working on the reverse direction: chopping up $P\left[\Lambda \right]$ by clustering the points (treating each distribution as a point in distribution space) given by $P[\Lambda |X=x]$, optimizing for a deterministic-in-$X$ latent $\Delta =\Delta \left(X\right)$ which minimizes $D_{KL}\left(P\right[\Lambda |X\left]||P\right[\Lambda |\Delta \left(X\right)\left]\right)$.

This definitely separates $X_1$ and $X_2$ to some small error, since we can just use $\Delta$ to build a distribution over $\Lambda$ which should approximately separate $X_1$ and $X_2$.

To show that it’s deterministic in $X_1$ (and by symmetry $X_2$) to some small error, I was hoping to use the fact that—given$X_1$$X_2$—has very little information about $\Lambda$, so it’s unlikely that $P\left[\Lambda |X_1\right]$ is in a different cluster to $P[\Lambda |X_1,X_2]$. This means that $P\left[\Delta |X_1\right]$ would just put most of the weight on the cluster containing $P\left[\Lambda |X_1\right]$.

A constructive approach for $\Delta$ would be marginally more useful in the long-run, but it’s also probably easier to prove things about the optimal $\Delta$. It’s also probably easier to prove things about $\Delta$ for a given number of clusters $|\Delta |$, but then you also have to prove things about what the optimal value of $|\Delta |$ is.

[johnswentworth]

Sounds like you’ve correctly understood the problem and are thinking along roughly the right lines. I expect a deterministic function of $X$ won’t work, though.

Hand-wavily: the problem is that, if we take the latent to be a deterministic function $\Delta \left(X\right)$, then $P\left[X|\Delta \right(X\left)\right]$ has lots of zeros in it—not approximate-zeros, but true zeros. That will tend to blow up the KL-divergences in the approximation conditions.

I’d recommend looking for a function $\Delta \left(\Lambda \right)$. Unfortunately that does mean that low entropy of $\Delta \left(\Lambda \right)$given $X$ has to be proven.

[Alex Gibson]

I’m confused by this. The KL term we are looking at in the deterministic case is
$D_{\text{KL}}\left(P\right[X,\Lambda \left]||P\right[\Lambda \left]P\right[X_1|\Lambda \left]P\right[X_2|\Lambda \left]\right)$, right?

For simplicity, we imagine we have finite discrete spaces. Then this would blow up if $P[X=(x_1,x_2),\Lambda =\lambda ]\ne 0$, and $P[\Lambda =\lambda ]P[X_1=x_1|\Lambda =\lambda ]P[X_2=x_2|\Lambda =\lambda ]=0$. But this is impossible, because any of the terms in the product being 0 imply that $P[X=(x_1,x_2),\Lambda =\lambda ]$ is $0$.

Intuitively, we construct an optimal code for encoding the distribution $P\left[\Lambda \right]P\left[X_1|\Lambda \right]P\left[X_2|\Lambda \right]$, and the KL divergence measures how many more bits on average we need to encode a message than optimal, if the true distribution is given by $P[X,\Lambda ]$. Issues occur when but the true distribution $P[X,\Lambda ]$ takes on values which never occur according to $P\left[\Lambda \right]P\left[X_1|\Lambda \right]P\left[X_2|\Lambda \right]$, i.e: the optimal code doesn’t account for those values potentially occurring.

Potentially there are subtleties when we have continuous spaces. In any case I’d be grateful if you’re able to elaborate.

[johnswentworth]

Yeah, I’ve since updated that deterministic functions are probably the right thing here after all, and I was indeed wrong in exactly the way you’re pointing out.

[J Bostock]

Huh, I had vaguely considered that but I expected any $P\left[X|\Delta \right(X\left)\right]=0$ terms to be counterbalanced by $P[X,\Delta (X\left)\right]=0$ terms, which together contribute nothing to the KL-divergence. I’ll check my intuitions though.

I’m honestly pretty stumped at the moment. The simplest test case I’ve been using is for $X_1$ and $X_2$ to be two flips of a biased coin, where the bias is known to be either $k$ or $1-k$ with equal probability of either. As $k$ varies, we want to swap from $\Delta \cong \Lambda$ to the trivial case $|\Delta |=1$ and back. This (optimally) happens at around $k=0.08$ and $k=0.92$. If we swap there, then the sum of errors for the three diagrams of $\Delta$ does remain less than $2(ϵ+ϵ+ϵ)$ at all times.

Likewise, if we do try to define $\Delta \left(X\right)$, we need to swap from a $\Delta$ which is equal to the number of heads, to $|\Delta |=1$, and back.

In neither case can I find a construction of $\Delta \left(X\right)$ or $\Delta \left(\Lambda \right)$ which swaps from one phase to the other at the right time! My final thought is for $\Delta$ to be some mapping $\Lambda \to P\left(\Lambda \right)$ consisting of a ball in probability space of variable radius (no idea how to calculate the radius) which would take $k\to \left\{k\right\}$ at $k\approx 1$ and $k\to \{k,1-k\}$ at $k\approx 0.5$. Or maybe you have to map $\Lambda \to P\left(X\right)$ or something like that. But for now I don’t even have a construction I can try to prove things for.

Perhaps a constructive approach isn’t feasible, which probably means I don’t have quite the right skillset to do this.