Thankyou to David Lorell for his contributions as the ideas in this post were developed.
For about a year and a half now, my main foundation for natural abstraction math has been The Telephone Theorem: long-range interactions in a probabilistic graphical model (in the long-range limit) are mediated by quantities which are conserved (in the long-range limit). From there, the next big conceptual step is to argue that the quantities conserved in the long-range limit are also conserved by resampling, and therefore the conserved quantities of an MCMC sampling process on the model mediate all long-range interactions in the model.
The most immediate shortcoming of the Telephone Theorem and the resampling argument is that they talk about behavior in infinite limits. To use them, either we need to have an infinitely large graphical model, or we need to take an approximation. For practical purposes, approximation is clearly the way to go, but just directly adding epsilons and deltas to the arguments gives relatively weak results.
This post presents a different path.
The core result is the Lightcone Theorem:
Start with a probabilistic graphical model on the variables X1,…,Xn.
The graph defines adjacency, distance, etc between variables. For directed graphical models (i.e. Bayes nets), spouses (as well as parents and children) count as adjacent.
We can model those variables as the output of a Gibbs sampler (that’s the MCMC process) on the graphical model.
Call the initial condition of the sampler X0=(X01,…,X0n). The distribution of X0 must be the same as the distribution of X (i.e. the sampler is initialized “in equilibrium”).
We can model the sampler as having run for any number of steps to generate the variables; call the number of steps T.
At each step, the process resamples some set of nonadjacent variables conditional on their neighbors.
The Lightcone Theorem says: conditional on X0, any sets of variables in X which are a distance of at least 2T apart in the graphical model are independent.
Yes, exactly independent, no approximation.
In short: the initial condition of the resampling process provides a latent, conditional on which we have exact independence at a distance.
This was… rather surprising to me. If you’d floated the Lightcone Theorem as a conjecture a year ago, I’d have said it would probably work as an approximation for large T, but no way it would work exactly for finite T. Yet here we are.
The Proof, In Pictures
The proof is best presented visually.[1] High-level outline:
Perform a do() operation on the Gibbs sampler, so that it never resamples the variables a distance of T from XR.
In the do()-operated process, X0 mediates between XTR and XTD(R,≥2T), where D(R,≥2T) indicates indices of variables a distance of at least 2T from XR.
Since X0, XTR and XTD(R,≥2T) are all outside the lightcone of the do()-operation, they have the same joint distribution under the non-do()-operated sampler as under the do()-operated sampler.
Therefore X0 mediates between XTR and XTD(R,≥2T) under the original sampler.
We start with the graphical model:
Within that graphical model, we’ll pick some tuple of variables XR (“R” for “region”)[2]. I’ll use the notation XD(R,t) for the variables a distance t away from R, XD(R,>t) for variables a distance greater than t away from R, XD(R,<t) for variables a distance less than t away from R, etc.
Note that for any t, XD(R,t) (the variables a distance t away from R) is a Markov blanket, mediating interaction between XD(R,<t) (everything less than distance t from XR), and XD(R,>t) (everything more than distance t from XR).
Next, we’ll draw the Gibbs resampler as a graphical model. We’ll draw the full state Xt at each timestep as a “layer”, with X0 as the initial layer and X=XT as the final layer. At each timestep, some (nonadjacent) variables are resampled conditional on their neighbors, so we have arrows from the neighbor-variables in the previous timestep. The rest of the variables stay the same, so they each just have a single incoming variable from themselves at the previous timestep.
Now for the core idea: we’re going to perform a do() operation on the resampler-graph. Specifically, we’re going to hold XD(R,T) constant; none of the variables in that Markov blanket are ever resampled in the do()-transformed resampling process.
Many arrows omitted.
Notice that, in the do()-operated process, knowing X0 also tells us the value of XtD(R,T) for all t. So, if we condition on X0, then visually we’re conditioning on:
Note that the “cylinder” is hollow, and XR is inside of it.
Note that the “cylinder” (including the “base”) separates XT into two pieces—one contains everything less than distance T from X1R,...,XTR, and the other everything more than distance T from X1R,...,XTR. The separation indicates that X0 is a Markov blanket between those pieces… at least within the do()-operated resampling process.
Now for the last step: we’ll draw a forward “lightcone” around our do()-operation. As the name suggests, it expands outward along outgoing arrows, starting from the nodes intervened-upon, to include everything downstream of the do()-intervention.
Though it’s hard to see, the orange “cone” flares inwards inside of the red “cylinder”, and flares outwards outside the cylinder. It generally moves away from the cylinder walls. Note that the do()- intervention starts at t=1, so that’s where the cone starts.
Outside of that lightcone, the distribution of the do()-operated process matches that of the non-do()-operated process.
Crucially, X0, XTR=XR, and XTD(R,≥2T)=XD(R,≥2T) are all outside of the lightcone, so their joint distribution is the same under the do()-operated and non-do()-operated resampling process.
Since X0 mediates between XR and XTD(R,≥2T) in the do()-operated process, and the joint distribution is the same between the do()-operated and non-do()-operated process, X0 must mediate between XR and XTD(R,≥2T) under the non-do()-operated process.
In other words: any two sets of variables at least a distance of 2T apart (i.e.XR and XTD(R,≥2T)) are independent given X0. That’s the Lightcone Theorem for two sets of variables.
Finally, note that we can further pick out two subsets of XTD(R,≥2T) which are themselves separated by 2T, and apply the Lightcone Theorem for two sets of variables again to conclude that XR and the two chosen sets of variables are all mutually independent given X0. By further iteration, we can conclude that any number of sets of variables which are all separated by a distance of 2T are independent given X0. That’s the full Lightcone Theorem.
How To Use The Lightcone Theorem?
The rest of this post is more speculative.
X0 mediates interactions in X over distance of at least 2T, but X0 also typically has a bunch of “extra” information in it that we don’t really care about—information which is lost during the resampling process. So, the next step is to define the latent Λ:
Λ(X0):=(x↦lnP[X=x|X0])
By the minimal map argument, Λ=P[X|Λ]=P[X|X0]; Λ is an informationally-minimal summary of all the information in X0 relevant to X.
… but that doesn’t mean that Λ is minimal among approximate summaries, nor that it’s a very efficient representation of the information. Those are the two main open threads: approximation and efficient representation.
On the approximation front, a natural starting point is to look at the eigendecomposition of the transition matrix for the resampling process. This works great in some ways, but plays terribly with information-theoretic quantities (logs blow up for near-zero probabilities). An eigendecomposition of the log transition probabilities plays better information-theoretic quantities, but worse with composition as we increase T, and we’re still working on theorems to fully justify the use of the log eigendecomposition.
On the efficient representation front, a natural stat-mech-style starting point is to pick “mesoscale regions”: m sets of variables XR1,...,XRm which are all separated by at least distance 2T, but big enough to contain the large majority of variables. Then
lnP[XR1,…,XRm|Λ]=∑ilnP[XRi|Λ]
At this point the physicists wave their hands REALLY vigorously and say “… and since XR1,...,XRm includes the large majority of variables, that sum will approximate P[X|Λ]”. Which is of course extremely sketchy, but for some (very loose) notions of “approximate” it can work for some use cases. I’m still in the process of understanding exactly how far that kind of approximation can get us, and for what use-cases.
Insofar as the mesoscale approximation does work, another natural step is to invoke generalized Koopman-Pitman-Darmois (gKPD). This requires a little bit of a trick: a Gibbs sampler run backwards is still a Gibbs sampler. So, we can swap X0 and X in the Lightcone Theorem: subsets of X0 separated by a distance of at least 2T are independent given X. From there:
Λ(X0) is a summary of all information in X0 relevant to X
Insofar as the mesoscale argument works, “most of” X0 is independent given X
… which is most of what we need to apply gKPD. If we ignore the sketchy part—i.e. pretend that regions X0R1,...,X0Rm cover all of X0 and are all independent given X - then gKPD would say roughly: ifΛ can be represented as n/2 dimensional or smaller, thenΛ is isomorphic to ∑ifi(XRi) for some functions fi, plus a limited number of “exception” terms. There’s a lot of handwaving there, but that’s very roughly the sort of argument I hope works. If successful, it would imply a nice maxent form (though not as nice as the maxent form I was hoping for a year ago, which I don’t think actually works), and would justify using an eigendecomposition of the log transition matrix for approximation.
I’ve omitted from the post various standard things about Gibbs samplers, e.g. explaining why we can model the variables of the graphical model as the output of a Gibbs sampler, how big T needs to be in order to resample all the variables at least once, how to generate X0 from X (rather than vice-versa), etc. Leave a question in the comments if you need more detail on that.
The Lightcone Theorem: A Better Foundation For Natural Abstraction?
Thankyou to David Lorell for his contributions as the ideas in this post were developed.
For about a year and a half now, my main foundation for natural abstraction math has been The Telephone Theorem: long-range interactions in a probabilistic graphical model (in the long-range limit) are mediated by quantities which are conserved (in the long-range limit). From there, the next big conceptual step is to argue that the quantities conserved in the long-range limit are also conserved by resampling, and therefore the conserved quantities of an MCMC sampling process on the model mediate all long-range interactions in the model.
The most immediate shortcoming of the Telephone Theorem and the resampling argument is that they talk about behavior in infinite limits. To use them, either we need to have an infinitely large graphical model, or we need to take an approximation. For practical purposes, approximation is clearly the way to go, but just directly adding epsilons and deltas to the arguments gives relatively weak results.
This post presents a different path.
The core result is the Lightcone Theorem:
Start with a probabilistic graphical model on the variables X1,…,Xn.
The graph defines adjacency, distance, etc between variables. For directed graphical models (i.e. Bayes nets), spouses (as well as parents and children) count as adjacent.
We can model those variables as the output of a Gibbs sampler (that’s the MCMC process) on the graphical model.
Call the initial condition of the sampler X0=(X01,…,X0n). The distribution of X0 must be the same as the distribution of X (i.e. the sampler is initialized “in equilibrium”).
We can model the sampler as having run for any number of steps to generate the variables; call the number of steps T.
At each step, the process resamples some set of nonadjacent variables conditional on their neighbors.
The Lightcone Theorem says: conditional on X0, any sets of variables in X which are a distance of at least 2T apart in the graphical model are independent.
Yes, exactly independent, no approximation.
In short: the initial condition of the resampling process provides a latent, conditional on which we have exact independence at a distance.
This was… rather surprising to me. If you’d floated the Lightcone Theorem as a conjecture a year ago, I’d have said it would probably work as an approximation for large T, but no way it would work exactly for finite T. Yet here we are.
The Proof, In Pictures
The proof is best presented visually.[1] High-level outline:
Perform a do() operation on the Gibbs sampler, so that it never resamples the variables a distance of T from XR.
In the do()-operated process, X0 mediates between XTR and XTD(R,≥2T), where D(R,≥2T) indicates indices of variables a distance of at least 2T from XR.
Since X0, XTR and XTD(R,≥2T) are all outside the lightcone of the do()-operation, they have the same joint distribution under the non-do()-operated sampler as under the do()-operated sampler.
Therefore X0 mediates between XTR and XTD(R,≥2T) under the original sampler.
We start with the graphical model:
Within that graphical model, we’ll pick some tuple of variables XR (“R” for “region”)[2]. I’ll use the notation XD(R,t) for the variables a distance t away from R, XD(R,>t) for variables a distance greater than t away from R, XD(R,<t) for variables a distance less than t away from R, etc.
Note that for any t, XD(R,t) (the variables a distance t away from R) is a Markov blanket, mediating interaction between XD(R,<t) (everything less than distance t from XR), and XD(R,>t) (everything more than distance t from XR).
Next, we’ll draw the Gibbs resampler as a graphical model. We’ll draw the full state Xt at each timestep as a “layer”, with X0 as the initial layer and X=XT as the final layer. At each timestep, some (nonadjacent) variables are resampled conditional on their neighbors, so we have arrows from the neighbor-variables in the previous timestep. The rest of the variables stay the same, so they each just have a single incoming variable from themselves at the previous timestep.
Now for the core idea: we’re going to perform a do() operation on the resampler-graph. Specifically, we’re going to hold XD(R,T) constant; none of the variables in that Markov blanket are ever resampled in the do()-transformed resampling process.
Notice that, in the do()-operated process, knowing X0 also tells us the value of XtD(R,T) for all t. So, if we condition on X0, then visually we’re conditioning on:
Note that the “cylinder” (including the “base”) separates XT into two pieces—one contains everything less than distance T from X1R,...,XTR, and the other everything more than distance T from X1R,...,XTR. The separation indicates that X0 is a Markov blanket between those pieces… at least within the do()-operated resampling process.
Now for the last step: we’ll draw a forward “lightcone” around our do()-operation. As the name suggests, it expands outward along outgoing arrows, starting from the nodes intervened-upon, to include everything downstream of the do()-intervention.
Outside of that lightcone, the distribution of the do()-operated process matches that of the non-do()-operated process.
Crucially, X0, XTR=XR, and XTD(R,≥2T)=XD(R,≥2T) are all outside of the lightcone, so their joint distribution is the same under the do()-operated and non-do()-operated resampling process.
Since X0 mediates between XR and XTD(R,≥2T) in the do()-operated process, and the joint distribution is the same between the do()-operated and non-do()-operated process, X0 must mediate between XR and XTD(R,≥2T) under the non-do()-operated process.
In other words: any two sets of variables at least a distance of 2T apart (i.e.XR and XTD(R,≥2T)) are independent given X0. That’s the Lightcone Theorem for two sets of variables.
Finally, note that we can further pick out two subsets of XTD(R,≥2T) which are themselves separated by 2T, and apply the Lightcone Theorem for two sets of variables again to conclude that XR and the two chosen sets of variables are all mutually independent given X0. By further iteration, we can conclude that any number of sets of variables which are all separated by a distance of 2T are independent given X0. That’s the full Lightcone Theorem.
How To Use The Lightcone Theorem?
The rest of this post is more speculative.
X0 mediates interactions in X over distance of at least 2T, but X0 also typically has a bunch of “extra” information in it that we don’t really care about—information which is lost during the resampling process. So, the next step is to define the latent Λ:
Λ(X0):=(x↦lnP[X=x|X0])
By the minimal map argument, Λ=P[X|Λ]=P[X|X0]; Λ is an informationally-minimal summary of all the information in X0 relevant to X.
… but that doesn’t mean that Λ is minimal among approximate summaries, nor that it’s a very efficient representation of the information. Those are the two main open threads: approximation and efficient representation.
On the approximation front, a natural starting point is to look at the eigendecomposition of the transition matrix for the resampling process. This works great in some ways, but plays terribly with information-theoretic quantities (logs blow up for near-zero probabilities). An eigendecomposition of the log transition probabilities plays better information-theoretic quantities, but worse with composition as we increase T, and we’re still working on theorems to fully justify the use of the log eigendecomposition.
On the efficient representation front, a natural stat-mech-style starting point is to pick “mesoscale regions”: m sets of variables XR1,...,XRm which are all separated by at least distance 2T, but big enough to contain the large majority of variables. Then
lnP[XR1,…,XRm|Λ]=∑ilnP[XRi|Λ]
At this point the physicists wave their hands REALLY vigorously and say “… and since XR1,...,XRm includes the large majority of variables, that sum will approximate P[X|Λ]”. Which is of course extremely sketchy, but for some (very loose) notions of “approximate” it can work for some use cases. I’m still in the process of understanding exactly how far that kind of approximation can get us, and for what use-cases.
Insofar as the mesoscale approximation does work, another natural step is to invoke generalized Koopman-Pitman-Darmois (gKPD). This requires a little bit of a trick: a Gibbs sampler run backwards is still a Gibbs sampler. So, we can swap X0 and X in the Lightcone Theorem: subsets of X0 separated by a distance of at least 2T are independent given X. From there:
Λ(X0) is a summary of all information in X0 relevant to X
Insofar as the mesoscale argument works, “most of” X0 is independent given X
… which is most of what we need to apply gKPD. If we ignore the sketchy part—i.e. pretend that regions X0R1,...,X0Rm cover all of X0 and are all independent given X - then gKPD would say roughly: if Λ can be represented as n/2 dimensional or smaller, then Λ is isomorphic to ∑ifi(XRi) for some functions fi, plus a limited number of “exception” terms. There’s a lot of handwaving there, but that’s very roughly the sort of argument I hope works. If successful, it would imply a nice maxent form (though not as nice as the maxent form I was hoping for a year ago, which I don’t think actually works), and would justify using an eigendecomposition of the log transition matrix for approximation.
I’ve omitted from the post various standard things about Gibbs samplers, e.g. explaining why we can model the variables of the graphical model as the output of a Gibbs sampler, how big T needs to be in order to resample all the variables at least once, how to generate X0 from X (rather than vice-versa), etc. Leave a question in the comments if you need more detail on that.
Notation convention: capital-letter indices like XA indicate index-tuples, i.e. if A=(1,2,3) then XA=(X1,X2,X3).