David Lorell comments on Resampling Conserves Redundancy (Approximately)

[David Lorell]

(Update 7)

After some back and forth last night with an LLM^[1], we now have a proof of “chainability” for the redundancy diagrams in particular. (And have some hope that this will be most of what we need to rescue the stochastic->deterministic nat lat proof.)

(Theorem) Chainability of Redunds

Let P be a distribution over $X_1$, $X_2$, and $\Lambda$.
Define:
$Q[X,\Lambda ]:=P\left[X\right]P\left[\Lambda |X_1\right]$
$S[X,\Lambda ]:=P\left[X\right]P\left[\Lambda |X_2\right]=P\left[X\right]{\sum }_{X_1}P\left[X_1|X_2\right]P\left[\Lambda |X\right]$$R[X,\Lambda ]:=P\left[X\right]Q\left[\Lambda |X_2\right]=P\left[X\right]{\sum }_{X_1}P\left[X_1|X_2\right]P\left[\Lambda |X_1\right]$

Where you can think of Q as ‘forcing’ P into factorizing per one redundancy pattern: $X_2\to X_1\to \Lambda$, S as forcing the other pattern: $X_1\to X_2\to \Lambda$, and R as forcing one after the other: first $X_2\to X_1\to \Lambda$, and then $X_1\to X_2\to \Lambda$.

The theorem states,
$D_{KL}\left(P||R\right)\le D_{KL}\left(P||Q\right)+D_{KL}\left(P||S\right)$,

Or in words: The error (in $D_{KL}$ from $P$) accrued by applying both factorizations to P, is bounded by the the sum of the errors accrued by applying each of the factorizations to P, separately.

Proof

The proof proceeds in 3 steps.

1. $D_{KL}\left(P||Q\right)\ge D_{KL}\left(S||R\right)$

   Pf.
   Let $a_{X_1}:=P\left[X_1|X_2\right]P\left[\Lambda |X\right]\ge 0$

   Let $b_{X_1}:=P\left[X_1|X_2\right]P\left[\Lambda |X_1\right]\ge 0$

   By the log-sum inequality:

   ${\sum }_{X_1}\left(a_{X_1}ln\frac{a_{X_1}}{b_{X_1}}\right)\ge \left({\sum }_{X_1}{a}_{X_1}\right)ln\left(\frac{{\sum }_{X_1}{a}_{X_1}}{{\sum }_{X_1}{b}_{X_1}}\right)$

   $⟹$$D_{KL}\left(P||Q\right)\ge D_{KL}\left(S||R\right)$ as desired.

2. $D_{KL}\left(P||R\right)=D_{KL}\left(P||S\right)+D_{KL}\left(S||R\right)$

   Pf.

   $D_{KL}\left(P||R\right)-D_{KL}\left(P||S\right)$

   $={\sum }_{X,\Lambda }P[X,\Lambda ]\left[lnP\right[\Lambda |X]-lnR[\Lambda |X_2]-lnP[\Lambda |X]+lnS[\Lambda |X_2\left]\right]$

   $={\sum }_{X_2}P\left[X_2\right]{\sum }_{\Lambda }{\sum }_{X_1}P\left[X_1|X_2\right]P\left[\Lambda |X\right]ln\frac{S\left[\Lambda |X_2\right]}{R\left[\Lambda |X_2\right]}$

   $={\sum }_{X_1}{\sum }_{X_2}P\left[X_1|X_2\right]P\left[X_2\right]{\sum }_{\Lambda }S\left[\Lambda |X_2\right]ln\frac{S\left[\Lambda |X_2\right]P\left[X\right]}{R\left[\Lambda |X_2\right]P\left[X\right]}$

   $=D_{KL}\left(S||R\right)$

3. Combining steps 1 and 2,
   $D_{KL}\left(P||Q\right)\ge D_{KL}\left(S||R\right)=D_{KL}\left(P||R\right)-D_{KL}\left(P||S\right)$

   $⟹D_{KL}\left(P||R\right)\le D_{KL}\left(P||Q\right)+D_{KL}\left(P||S\right)$

   which completes the proof.

Notes:
In the second to last line of step 2, the expectation over $P\left[X_1|X_2\right]$ is allowed because there are no free $X_1$’s in the expression. Then, this aggregates into an expectation over $S[X,\Lambda ]$ as $S\left[\Lambda |X_2\right]=S\left[\Lambda |X\right]$.

We are hopeful that this, thought different than the invalidated result in the top level post, will be an important step to rescuing the stochastic natural latent ⇒ deterministic natural latent result.

1. ^

   A (small) positive update for me on their usefulness to my workflow!

[johnswentworth]

Additional note which might be relevant later: we can also get proof step 1 in a somewhat more general way, which establishes that the function $P[X,\Lambda ]\mapsto P\left[X\right]P\left[\Lambda |X_i\right]$ is a nonexpansive map under $D_{KL}$. We’ll write that proof down later if we need it.

[Alfred Harwood]

Hi, Jeremy and I have a couple of updates on this thread. I have put them in a shortform here.