Maxent and Abstractions: Current Best Arguments

[johnswentworth]

This post is not-very-distilled and doesn’t contain much background; it’s intended for people who already have the context of at least these four posts. I’m putting it up mainly as a reference for people who might want to work directly on the math of natural abstractions, and as a technical reference post.

There’s various hints that, in most real-world cases, the distribution of low-level state given high-level natural abstractions should take the form of a maximum entropy distribution, in which:

• The “features” are sums over local terms, and

• The high-level variables are (isomorphic to) the Lagrange multipliers

More formally: we have a low-level causal model (aka Bayes net) $P\left[X^L\right]={\prod }_{i}P\left[X_i^L|X_{pa\left(i\right)}^L\right]$. Given the high-level variables $X^H$, the distribution of low-level variable values should look like

$P\left[X^L|X^H\right]=\frac{1}{Z}P\left[X^L\right]e^{{\lambda }^T\left(X^H\right){\sum }_i{f}_i(X_i^L,X_{pa\left(i\right)}^L)}$

… i.e. the maximum-entropy distribution subject to constraints of the form $E\left[{\sum }_i{f}_i\right(X_i^L,X_{pa\left(i\right)}^L\left)|X^H\right]=\mu \left(X^H\right)$. (Note: $\lambda$, $f_i$, and $\mu$ are all vector-valued.)

This is the sort of form we see in statistical mechanics. It’s also the form which the generalized Koopman-Pitman-Darmois (gKPD) theorem seems to hint at.

I don’t yet have a fully-satisfying general argument that this is the main form which abstractions should take, but I have two partial arguments. This post will go over both of them.

Maxent Telephone Argument

Two different nested layers of Markov blankets on the same underlying causal DAG

Quick recap of the Telephone Theorem: information about some variable $X$ passes through a nested sequence of Markov blankets $M_1,M_2,\dots$. Information about $X$ can only be lost as it propagates. In the limit, all information is either perfectly conserved or completely lost. Mathematically, in the limit $P\left[X|M_n\right]=P\left[X|F_n\right(M_n\left)\right]$ for some $F$ such that $F_n\left(M_n\right)=F_{n+1}\left(M_{n+1}\right)$ with probability approaching 1 as $n\to \infty$; $F$ is the perfectly-conserved-in-the-limit information carrier.

In this setup, we can also argue that the limiting distribution $li{m}_{n\to \infty }P\left[X|M_n\right]$ should have a maxent form. (Note: this is a hand-wavy argument, not a proper proof.)

Think about how the distribution $(x\mapsto P[X=x|M_n\left]\right)$ transforms as we increment $n$ by 1. We have

$P\left[X|M_{n+1}\right]={\sum }_{M_n}P\left[X|M_n\right]P\left[M_n|M_{n+1}\right]$

First key property of this transformation: it’s a convex combination for each $M_{n+1}$ value, i.e. it’s mixing. Mixing, in general, cannot decrease the entropy of a distribution, only increase it or leave it the same. So, the entropy of $P\left[X|M_n\right]$ will not decrease with $n$.

When will the entropy stay the same? Well, our transformation may perfectly conserve some quantities. Since the transformation is linear, those quantities should have the form ${\sum }_{X}f\left(X\right)P\left[X|M_n\right]$ for some $f$, i.e. they’re expected values. They’re conserved when $E\left[f\right(X\left)|M_n\right]=E\left[f\right(X\left)|M_{n+1}\right]$ with probability 1.

Intuitively, we’d expect the entropy of everything except the conserved quantities to strictly increase. So, we’d expect the distribution $P\left[X|M_n\right]$ to approach maximum entropy subject to constraints of the form $E\left[f\right(X\left)|M_n\right]=\mu \left(M_n\right)$, where $E\left[f\right(X\left)|M_n\right]=E\left[f\right(X\left)|M_{n+1}\right]$ with probability 1 (at least in the limit of large $n$). Thus, we have the maxent form

$P\left[X|M_n\right]=\frac{1}{Z}P\left[X\right]e^{{\lambda }^T\left(M_n\right)f\left(X\right)}$

(Note on the $P\left[X\right]$ in there: I’m actually maximizing relative entropy, relative to the prior on $X$, which is almost always what one should actually do when maximizing entropy. That results in a $P\left[X\right]$ term. We should find that $E\left[lnP\right[X\left]|M_n\right]$ is a conserved quantity anyway, so it shouldn’t actually matter whether we include the $P\left[X\right]$ multiplier or not; we’ll get the same answer either way.)

Shortcomings of This Argument

Obviously it’s a bit handwavy. Other than that, the main issue is that the Telephone Theorem doesn’t really leverage the spatial distribution of information; information only propagates along a single dimension. As a result, there’s not really a way to talk about the conserved $f$’s being a sum over local terms, i.e. $f\left(X\right)={\sum }_i{f}_i(X_i,X_{pa\left(i\right)})$.

Despite the handwaviness, it’s an easy result to verify computationally for small systems, and I have checked that it works.

Resampling + gKPD Argument

Another approach is to start from the redundancy + resampling formulation of abstractions. In this approach, we run an MCMC process on our causal model. Any information which is highly redundant in the system—i.e. the natural abstractions—is near-perfectly conserved under resampling a single variable at a time; other information is all wiped out. Call the initial (low-level) state of the MCMC process $X^0$, and the final state $X$. Then we have

$P\left[X|X^0\right]=P\left[X|F\right(X^0\left)\right]=P\left[X|F\right(X\left)\right]P\left[F\right(X\left)|F\right(X^0\left)\right]=\frac{1}{Z}P\left[X\right]I\left[F\right(X)=F(X^0\left)\right]$

… where $F$ is conserved by the resampling process with probability 1.

It turns out that $P\left[X|X^0\right]$ factors over the same DAG as the underlying causal model:

$P\left[X|X^0\right]={\prod }_{i}P[X_i|X_{pa\left(i\right)},X^0]$

If the conserved quantities $F\left(X\right)$ are much lower-dimensional than $X$ itself, then we can apply the gKPD theorem: we have a factorization of $P\left[X|X^0\right]$, we have a low-dimensional summary statistic $F\left(X\right)$ which summarizes all the info in $X$ relevant to $X^0$, so the gKPD theorem says that the distribution must have the form

$P\left[X|X^0\right]=\frac{1}{Z}{e}^{{\lambda }^T\left(X^0\right){\sum }_{i\notin E}{f}_i(X_i,X_{pa\left(i\right)})}{\prod }_{i\notin E}P[X_i|X_{pa\left(i\right)},X^0=(X^0{)}^{\ast }\left]{\prod }_{i\in E}P\right[X_i|X_{pa\left(i\right)},X^0=X^0]$

… where $E$ is a relatively-small set of “exceptional” indices, and $(X^0{)}^{\ast }$ is some fixed reference value of $X^0$. This is slightly different from our intended form—there’s the exception terms, and we have ${\prod }_{i\notin E}P[X_i|X_{pa\left(i\right)},X^0=(X^0{)}^{\ast }]$ rather than just ${\prod }_{i\notin E}P\left[X_i|X_{pa\left(i\right)}\right]$. The latter problem is easily fixed by absorbing ${\prod }_{i\notin E}\frac{P[X_i|X_{pa\left(i\right)},X^0=(X^0{)}^{\ast }]}{P\left[X_i|X_{pa\left(i\right)}\right]}$ into $f$ (at the cost of possibly increasing the summary dimension by 1), so that’s not really an issue, but the exception terms are annoying. Absorbing and assuming (for convenience) no exception terms, we get the desired form:

$P\left[X|X^0\right]=\frac{1}{Z}{e}^{{\lambda }^T\left(X^0\right){\sum }_i{f}_i(X_i,X_{pa\left(i\right)})}P\left[X\right]$

Note that this is maxentropic subject to constraints of the form $E\left[{\sum }_i{f}_i\right(X_i,X_{pa\left(i\right)}\left)|X^0\right]=\mu \left(X^0\right)$. Since the summary statistic $F\left(X\right)={\sum }_i{f}_i(X_i,X_{pa\left(i\right)})$ is conserved by the resampling process, we must have $\mu \left(X^0\right)={\sum }_i{f}_i(X_i^0,X_{pa\left(i\right)}^0)$, so the conservation equation is

$E\left[{\sum }_i{f}_i\right(X_i,X_{pa\left(i\right)}\left)|X^0\right]={\sum }_i{f}_i(X_i^0,X_{pa\left(i\right)}^0)$

Shortcomings of This Argument

Obviously there’s the exception terms. Other than that, the main issue with this argument is an issue with the resampling approach more generally: once we allow approximation, it’s not clear that the natural abstractions from the resampling formulation are the same natural abstractions which make the Telephone Theorem work. Both are independently useful: information dropping to zero at a distance is an easy property to leverage for planning/​inference, and knowing the quantities conserved by MCMC makes MCMC-based planning and inference much more scalable. And in the limit of perfect conservation and infinite “distance”, the two match. But it’s not clear whether they match under realistic approximations, and I don’t yet have efficient methods to compute the natural abstractions both ways in large systems in order to check.

That said, resampling + gKPD does give us basically the result we want, at least for redundancy/​resampling-based natural abstractions.

[adamShimi]

I followed approximately the technical discussion, and now I’m wondering what that would buy us if you are correct.

• Max entropy distributions seem nicely behaved and well-studied, so maybe we get some computations, properties, derivation for free? (Basically applying a productive frame to the problem of abstraction)

• It would reduce computing the influence of the summary statistics on the model to computing the constraints, as I’m guessing that this is the hard part in computing the max entropy distribution (?)

Are these correct, and what am I missing?

[johnswentworth]

That’s basically correct; the main immediate gain is that it makes it much easier to compute abstractions and compute using abstractions.

One additional piece is that it hints towards a probably-more-fundamental derivation of the theorems in which maximum entropy plays a more central role. The maximum entropy Telephone Theorem already does that, but the resampling + gKPD approach routes awkwardly through gKPD instead; there’s probably a nice way to do it directly via constrained maximization of entropy. That, in turn, would probably yield stronger and simpler theorems.