johnswentworth comments on Resampling Conserves Redundancy (Approximately)

[johnswentworth]

(Update 6)

Most general version of the chainability conjecture (for arbitrary graphs) has now been falsified numerically by David, but the version specific to the DAGs we need (i.e. the redundancy conditions, or one redundancy and the mediation condition) still looks good.

Most likely proof structure would use this lemma:

Lemma

Let $f_1,f_2$ be nonexpansive maps under distance metric $D$. (Nonexpansive maps are the non-strict version of contraction maps.)

By the nonexpansive map property, $D(x,f_1(x\left)\right)\ge D\left(f_2\right(x),f_2(f_1\left(x\right)\left)\right)$. And by the triangle inequality for the distance metric, $D(x,f_2(f_1\left(x\right)\left)\right)\le D(x,f_2(x\left)\right)+D\left(f_2\right(x),f_2(f_1\left(x\right)\left)\right)$. Put those two together, and we get

$D(x,f_2(f_1\left(x\right)\left)\right)\le D(x,f_1(x\left)\right)+D(x,f_2(x\left)\right)$

(Note: this is a quick-and-dirty comment so I didn’t draw a nice picture, but this lemma is easiest to understand by drawing the picture with the four points and distances between them.)

I think that lemma basically captures my intuitive mental picture for how the chainability conjecture “should” work, for the classes of DAGs on which it works at all. Each DAG $j$ would correspond to one of the functions $f_j$. where $f_j$ takes in a distribution and returns the distribution factored over the DAG $j$ , i.e.

$f_j(X\mapsto P[X\left]\right):=(X\mapsto {\prod }_{i}P[X_i|X_{p{a}^j\left(i\right)}\left]\right)$

In order to apply the lemma to get our desired theorem, we then need to find a distance metric which:

• Is a distance metric (in particular, it must satisfy the triangle inequality, unlike $D_{KL}$)

• Makes our DAG functions nonexpansive mappings

• Matches $D_{KL}(P,f_j(P\left)\right)$ AT THE SPECIFIC POINT P (not necessarily anywhere else)

The first two of those are pretty easy to satisfy for the redundancy condition DAGs: those two DAG operators are convex combinations, so good ol’ Euclidean distance on the distributions should work fine. Making it match $D_{KL}$ at $P$ is trickier, still working that out.

[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.