David Lorell comments on Resampling Conserves Redundancy (Approximately)

[David Lorell]

(Update 2)

Taking the limit of the ratio of $D_{KL}$s (using summation rather than max) with $c\to 0$ while $b:=10c$ gives $5\left(\frac{r+1}{11}\right)$

Setting c very small and ramping up r indeed brakes the bound more and more severely. (Code changes from the collab you provided, below.)

Code changes /​ additions

Block 1:
a,b,c,d,r = sp.symbols(“a b c d r”)
variable_substitutions = { # The definitions of these variables
a: 0.25,
b: 1e-90,
c: 1e-91,
r: 20000000,
}

Block 2 (later on):
expr = (kl3/​(kl1 + kl2)).subs(d, (1-3*c-(r+1)*b-2*a))
print(“KL(X2->X1->L’)/​sum[KL(X1->X2->L),KL(X2->X1->L)]=”,(kl3/​(kl1 +kl2)).evalf(subs=variable_substitutions))

Block3 (right after Block 2):
expr = (kl3/​(kl1 + kl2)).subs(d, (1-3*c-(r+1)*b-2*a)).subs(b, 10*c)
lim = sp.simplify(sp.limit(expr, c, 0))
print(“Limit of KL(X2->X1->L’)/​sum[KL(X1->X2->L),KL(X2->X1->L)] as c->0+ =”, lim)

[johnswentworth]

(Update 3)

We’re now pursuing two main threads here.

One thread is to simplify the counterexamples into something more intuitively-understandable, mainly hopes of getting an intuitive sense for whatever phenomenon is going on with the counterexamples. Then we’d build new theory specifically around that phenomenon.

The other thread is to go back to first principles and think about entirely different operationalizations of the things we’re trying to do here, e.g. not using diagram $D_{KL}$’s as our core tool for approximation. The main hope there is that maybe $D_{KL}$ isn’t really the right error metric for latents, but then we need to figure out a principled story which fully determines some other error metric.

Either way, we’re now >80% that this is a fundamental and fatal flaw for a pretty big chunk of our theory.

[johnswentworth]

(Update 4)

We have now started referring to “Jeremy et Al” when discussing the findings at top-of-thread, and find this amusing.

As of this morning, our current thread is an adjustment to the error measure. Thinking it through from first principles, it makes intuitive sense to marginalize out latents inside a $D_{KL}$, i.e.$D_{KL}\left(P\right[X\left]||{\sum }_{\Lambda }Q\right[X,\Lambda \left]\right)$ rather than $D_{KL}\left(P\right[X,\Lambda \left]||Q\right[X,\Lambda \left]\right)$ (where $Q$ is typically some factorization of $P[X,\Lambda ]$). Conceptually, that would mean always grounding out errors in terms of predictions on observables, not on mind-internal latent constructs. We’re now checking whether that new error gives us the properties we want in order to make the error measure useful (and in the process, we’re noticing what properties we want in order for the error measure to be useful, and making those more explicit than we had before).

[David Lorell]

(Update 5)

A conjecture we are working on which we expect to be generally useful beyond possibly rescuing the stoch->det proof that used to rely on the work in this post:

Chainability (Conjecture):
$\forall P[X,\Lambda ]$with ${ϵ}_1:=D_{KL}(X_1\to X_2\to \Lambda )$, ${ϵ}_2:=D_{KL}(X_1\leftarrow \Lambda \to X_2)$,
Define $Q[X,\Lambda ]:=P\left[X\right]P\left[\Lambda |X_2\right]$, and $Q^{\prime }[X,\Lambda ]:=Q\left[X_1|\Lambda \right]Q\left[X_2|\Lambda \right]Q\left[\Lambda \right]$.
Then, $D_{KL}\left(P||Q\right)<n({ϵ}_1+{ϵ}_2)$

Here is a collab with a quick numerical test that suggests the bound holds (and that n=1, in this case).

(Note: The above as written is just one step of chaining, and ultimately we are hoping to show it holds for arbitrarily many steps, accumulating an associated number of epsilons as error.)

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

[Alfred Harwood]

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

[Jeremy Gillen]

our current thread is an adjustment to the error measure.

We’re not sure that this is necessary. I quite like the current form of the errors. I’ve spent much of the past week searching for counterexamples to the ∃ deterministic latent theorem and I haven’t found anything yet (although it’s partially a manual search). My current approach takes a P(X_1,X_2) distribution, finds a minimal stochastic NL, then finds a minimal deterministic NL. The deterministic error has always been within a factor of 2 of the stochastic error. So currently we’re expecting the theorem can be rescued.

$D_{KL}\left(P\right[X\left]||{\sum }_{\Lambda }Q\right[X,\Lambda \left]\right)$ rather than $D_{KL}\left(P\right[X,\Lambda \left]||Q\right[X,\Lambda \left]\right)$

That seems like a cool idea for the mediation condition, but Isn’t it trivial for the redundancy conditions?

[johnswentworth]

That seems like a cool idea for the mediation condition, but Isn’t it trivial for the redundancy conditions?

Indeed, that specific form doesn’t work for the redundancy conditions. We’ve been fiddling with it.

[Daniel C]

Would this still give us guarantees on the conditional distribution $P\left(X|\Lambda \right)$?

E.g. Mediation: $D_{KL}\left(P\right(X_1,X_2,\Lambda )\parallel P(X_1|\Lambda \left)P\right(X_2|\Lambda \left)P\right(\Lambda \left)\right)$$=D_{KL}\left(P\right(X_1,X_2|\Lambda \left)P\right(\Lambda )\parallel P(X_1|\Lambda \left)P\right(X_2|\Lambda \left)P\right(\Lambda \left)\right)$$=D_{KL}\left(P\right(X_1,X_2|\Lambda )\parallel P(X_1|\Lambda \left)P\right(X_2|\Lambda \left)\right)$

is really about the expected error conditional on individual values of $\Lambda$, & it seems like there are distributions with high mediation error but low error when the latent is marginalized inside $D_{KL}$, which could be load-bearing when the agents cast out predictions on observables after updating on $\Lambda$

[Jeremy Gillen]

Oh nice, we tried to wrangle that counterexample into a simple expression but didn’t get there. So that rules out a looser bound under these assumptions, that’s good to know.