A Correspondence Theorem in the Maximum Entropy Framework

post by johnswentworth · 2020-11-11T22:46:38.732Z · LW · GW · 7 comments

Contents

  Background: Principle of Maximum Entropy
  Correspondence Theorem for Maximum Entropy Updates
  Proof
  What's Really Going On Here?
  Is This Trivial?
None
7 comments

Classical mechanics didn't work any less well once we discovered quantum, Galilean relativity and Newtonian gravity didn't work any less well once we discovered special and general relativity, etc. This is the correspondence principle, aka Egan's Law [? · GW]: in general, to the extent that old models match reality, new models must reproduce the old.

This sounds like it should be a Theorem, not just a Law [LW · GW] - a "correspondence theorem".

This post presents such a theorem within one particular framework - maximum entropy. It's not the theorem I'd eventually like - even my correspondence theorem [LW · GW] from last month has more substance to it. But this one is simple, intuitive, and both its strong points and shortcomings help to illustrate what I want out of a correspondence theorem. (In fact, I wrote down this one before the other correspondence theorem, and the shortcomings of this theorem partially inspired that one.)

Background: Principle of Maximum Entropy

By "maximum entropy framework", I mean roughly the technique used by Jaynes - see e.g. the widget problem in Logic of Science, page 440. If you've seen the principle of maximum entropy in the context of statistical mechanics, it's the same thing. I expect a lot of people who are otherwise familiar with maximum entropy distributions are not familiar with this particular framework (especially outside of a physics context), so a bit of background is in order.

We'll start with the widget problem: a company produces red, green and blue widgets, and for inventory purposes we wish to predict how many of each color will be sold on a given day. Based on sales aggregated over the past year, the average sales per day are roughly 40 green, 20 red, and 10 blue. Given only this information, what distribution should we assign to tomorrow's sales?

In a high-school statistics class, the answer would be "insufficient information" - the averages are not enough info to figure out the whole distribution. But this isn't a high-school statistics class. We're Bayesians, we've received relevant information, we have to update somehow.

Jaynes argues that the canonically-correct way to do this is maximum entropy: we find the model $M$ which has the highest possible entropy, subject to the constraints $E\left[\#green|M\right]=40$, $E\left[\#red|M\right]=20$, and $E\left[\#blue|M\right]=10$. A couple ways to interpret this idea:

• The classical argument from stat mech: the vast majority of distributions are very close to the maximum entropy distribution. Equivalently, we implicitly have a (non-normalizable) uniform prior over distribution-space which we're updating (via Bayes' rule) based on the expections.
• The argument from information: maximizing entropy means minimizing the information assumed in the model. By maximizing entropy subject to the expectation constraint, we're accounting for the expectation but assuming as little as possible aside from that (in an information-theoretic sense).

Regardless of how we interpret it, the math works out the same. If our variable is X and our constraints are $E\left[f_i\right(X\left)|M\right]={\mu }_i$, then the maximum entropy distribution is

$P\left[X|M\right]=\frac{1}{Z}{e}^{\lambda .\left(f\right(x)-\mu )}dx$

where

$Z=mi{n}_{\lambda }{\int }_x{e}^{\lambda .\left(f\right(x)-\mu )}dx$

and $\lambda$ is the minimizing argument. You can find derivations and discussions and all that in any stat mech book, or in Jaynes. For the widget problem above, $X$ would be the colors of each widget ordered in a day, $f_{green}\left(X\right)$ would be the number of green widgets ordered, and the constraints would say $E\left[f_{green}\right(X\left)|M\right]=40$, etc. To compute the $\lambda$'s, we'd evaluate the integral analytically and then minimize (see Jaynes).

Anyway, the main point here is that we can now "update" on certain kinds of information by adding constraints to our maximum entropy problem. For instance, if we find out that the daily variance in green widget sales is 10, then we'd add a constraint saying $E\left[\right(f_{green}\left(X\right)-40{)}^2|M^{\prime }]=10$. Our maximum entropy distribution would then have one additional $\lambda ,$ and an additional term $\left(\right(f_{green}\left(x\right)-40{)}^2-10)$ in the exponent. All written out, we'd go from

$P[X=x|M]=\frac{1}{Z}{e}^{{\lambda }_{green}\left(f_{green}\right(x)-40)+{\lambda }_{red}\left(f_{red}\right(x)-20)+{\lambda }_{blue}\left(f_{blue}\right(x)-10)}dx$

to

$P[X=x|M^{\prime }]=\frac{1}{Z^{\prime }}{e}^{{\lambda }_{green}^{\prime }\left(f_{green}\right(x)-40)+{\lambda }_{red}^{\prime }\left(f_{red}\right(x)-20)+{\lambda }_{blue}^{\prime }\left(f_{blue}\right(x)-10)+{\lambda }_{var}^{\prime }\left(\right(f_{green}\left(x\right)-40{)}^2-10)}dx$

... and we'd have to solve the modified minimization problem to find ${\lambda }^{\prime }$ and $Z^{\prime }$.

Conceptual takeaway: rather than updating on individual data points, in this framework we're given a sequence of summaries of "features" of the dataset, of the form "expectation of $f_i\left(X\right)$ is ${\mu }_i$" (found by e.g. computing the average of $f_i$ over a large data set). Each such feature becomes a new constraint in an optimization problem. This turns out to be equivalent to a Bayesian update in situations where a Bayesian update makes sense, but is more general - roughly speaking, it can work directly with virtual evidence updates.

Correspondence Theorem for Maximum Entropy Updates

On to the interesting part.

Let's imagine that two analysts are (separately) building maximum-entropy models of some data. They each query the giant database for average values of certain features - $f_1\left(X\right)$ for the first analyst, $f_2\left(X\right)$ for the second. They end up with two models:

• $M_1$ is the maximum-entropy model with features $E\left[f_1\right(X\left)|M_1\right]={\mu }_1$
• $M_2$ is the maximum-entropy model with features $E\left[f_2\right(X\left)|M_2\right]={\mu }_2$

We'll assume that both of these are "correct", in the sense that the average values $\mu$ actually do match the data.

Let's say that model 2 is "better" than model 1, in the sense that it has better predictive power on the real data-generating process $D$: $E\left[lnP\right[X|M_2\left]|D\right]>E\left[lnP\right[X|M_1\left]|D\right]$. (This is proportional to the average number of bits used by each model to encode a data point $X$ from $D$.) So,  the analysts' boss plans to just use model 2. But let's stretch the story to AI-alignment-style concerns: what if model 2 is using some weird ontology? What if the things the company cares about are easy to express in terms of the features $f_1$, but hard to express in terms of the features $f_2$?

Now for the claim.

We have two possibilities. Either:

• We can construct a third model $M^{\prime }$ which had strictly better predictive power than $M_2$, OR
• The features $E\left[f_1\right(X\left)|M_1\right]={\mu }_1$ are already implied by $M_2$; those features are already "in there" in some sense.

The proof will show the sense in which this is true.

Proof

The obvious thing to do is combine the two models into a single maximum-entropy model M' with both the features  $E\left[f_1\right(X\left)|M^{\prime }\right]={\mu }_1$ and  $E\left[f_2\right(X\left)|M^{\prime }\right]={\mu }_2$. How does the predictive power of this model look?

For maximum-entropy models in general, the predictive power $E\left[lnP\right[X|M\left]|D\right]$ is has a simple expression, assuming the values $\mu$ are correct for $D$ (i.e. $E\left[f\right(X\left)|D\right]=\mu$):

$E\left[lnP\right[X|M\left]|D\right]={\int }_x[\lambda .(f\left(x\right)-\mu )-lnZ]p\left[x|D\right]dx=\lambda .(\mu -\mu )-lnZ=-lnZ$

... so it's just the negative log of the normalizer $Z$. So, $M^{\prime }$ has higher predictive power than $M_2$ if-and-only-if $Z^{\prime }<Z_2$.

Now, recall that $Z$ comes from a minimization problem. Specifically:

$Z^{\prime }=mi{n}_{{\lambda }_1,{\lambda }_2}{\int }_x{e}^{{\lambda }_1.\left(f_1\right(x)-{\mu }_1)+{\lambda }_2.\left(f_2\right(x)-{\mu }_2)}dx$

$Z_2=mi{n}_{{\lambda }_2}{\int }_x{e}^{{\lambda }_2.\left(f_2\right(x)-{\mu }_2)}dx$

Key thing to notice: the objective for $Z_2$ is just the objective for $Z^{\prime }$ with ${\lambda }_1$ set to zero. In other words: the space which model $M_2$ searches for minima is a subset of the space which model $M^{\prime }$ searches for minima. Thus, $Z^{\prime }$ is always at least as small as $Z_2$; model $M^{\prime }$ has predictive power at least as high as $M_2$.

Furthermore, let's assume that the optima in these problems are unique - that's not necessarily the case, but it is usually true in practice. (The objectives are convex, so uniqueness of the minimum can only fail in specific ways - I'll leave the "fun" of working that out as an exercise to the reader.) We know that $M^{\prime }$ reduces to $M_2$ when ${\lambda }_1=0$; if the optima are unique and $Z^{\prime }=Z_2$ then that means ${\lambda }_1$ is indeed 0, so $M^{\prime }=M_2$.

... but $M^{\prime }$ has to satisfy the constraints $E\left[f_1\right(X\left)|M^{\prime }\right]={\mu }_1$. So if $M^{\prime }=M_2$, then $M_2$ also satisfies those constraints. That's the sense in which the features $E\left[f_1\right(X\left)|D\right]={\mu }_1$ are "already present" in $M_2$: $E\left[f_1\right(X\left)|M_2\right]={\mu }_1$.

So, we have two cases:

• $M^{\prime }\ne M_2$: $M^{\prime }$ has strictly better predictive power (i.e.$E\left[lnP\right[X|M^{\prime }\left]|D\right]>E\left[lnP\right[X|M_2\left]|D\right]$)
• $M^{\prime }=M_2$: the features $E\left[f_1\right(X\left)|D\right]={\mu }_1$ from model 1 are already implicit in model 2 (i.e. $E\left[f_1\right(X\left)|M_2\right]={\mu }_1$)

What's Really Going On Here?

If we strip away the math, the underlying phenomenon here seems kind of trivial.

The key is that we assume $\mu$ is correct for the true data-generation process $D$. We justify this by imagining that we have some very large number of data points, so law of large numbers kicks in and we can correctly estimate averages of our features. We're not just collecting noisy data points; we're directly learning facts about the true distribution, and we're learning those facts with perfect certainty.

So our theorem is saying something like... two models both contain some facts about the (observable) true distribution. Either:

• we can combine them into a strictly better model which contains all the facts from both, OR
• all the facts from one model are already contained in the other, and the combined model makes the same predictions as the "better" original model.

(A warning, however: this intuitive story is not perfect. Even if the combined model makes the same predictions as one of the original models about the data, it can still update differently as we learn new facts.)

Is This Trivial?

Let's go back to the starting point: it all adds up to normality. New models need to reproduce the old models in all the places where the old models worked - otherwise the new models are strictly suboptimal.

The obvious-but-trivial formalization of this is that new models have to make the same predictions about the data as the old models, in all the places where the old models predicted correctly. Corollary: any features (i.e. functions) of the data correctly predicted by the old models must also be correctly predicted by the new models.

... and that's basically what we've proven. Within the maximum entropy framework, any features of the data (specifically long-run average values) correctly predicted by an "old" model must also be correctly predicted by a "new" model, else the new model is strictly suboptimal. So in that sense, it seems pretty trivial.

However, there are two senses in which it's nontrivial. First, in the case where the new model incorrectly predicts some feature-values $\mu$ encoded in the old model, we've explicitly constructed a new model which outperforms the old. It's even a pretty simple, clean model - just another maximum entropy model.

Second, even the "trivial" idea that new models must make the same predictions about the data in places where the old model was right can cover some pretty nontrivial cases, because "features" of the data distribution can be pretty nontrivial. For instance, we can have a whole class of features of the form $E\left[g_i\right(X_1\left)g_j\right(X_2\left)\right]=E\left[g_i\right(X_1\left)\right]E\left[g_j\right(X_2\left)\right]$. With infinitely many such constraints, we can encode independence of $X_1$ and $X_2$. After all, independence of two observed variables is a property of the data distribution, so it's something we can use as a "feature". Likewise for conditional independence. (Of course, once we get into infinite-feature territory we do need to be more careful about applying the theory to real, finite data sets...)

7 comments

Comments sorted by top scores.