Short summary of Condensation

Condensation is a theory of concepts by Sam Eisenstat. The paper can be read here. Abram wrote a review on Lesswrong, and a followup. The paper is very much worth reading, and can be skimmed to just understand the motivation if you’re time constrained.

What is a concept? One rough pointer is "the little packets of information that are the meaning of a word or phrase". Another is the clusters found in the cluster structure of thingspace. Maybe we could think of them as little chunks of a generative model that compose together to make complete model of a complex world.

It often seems to be the case that this kind of chunking is arbitrary, in the sense that there isn’t one way to chunk up a generative model. It just depends on the hypothesis class, prior and implementation details. But some concepts seem to be more objective than this, in that we would expect different agents with different implementation details to use the same concept. One question that Condensation answers is “under what conditions can concepts be more objective?”. The theory provides some assumptions and metrics that can be used to select among latent variable models (LVM)s to find ones that use more “objective”^[1] concepts. If we make these assumptions on two agents’ latent variable models, it tells us when they will (and won’t) use the same latent variables.

This is very similar to the motivation for John Wentworth’s Natural Latents, as is noted in the Condensation paper, but so far no one has worked through the similarities between the two on a mathematical level. So the main goal of this post is to show some simple relationships between these two theories. A secondary goal is to work through an intuitive example of a non-trivial condensation, and this is where we’ll start.

How does condensation work?

There are multiple ways we could organize a generative model. We’ll call a “way of organizing a generative model” an LVM. Condensation is a method for sorting among these and finding ones that are also likely to be found by other agents who are doing the same thing.

If we have a set of random variables , the space of LVMs can be (very roughly) thought of as the space of Bayesian Networks whose leaves are the random variables . Except if two latent variables are upstream of the same subset of s, we'll combine them into a single variable. So we can name all the latent variables () with the subscript indicating which variables they contribute to.

For example, for variables , an LVM might look like this:

There is a  variable for every subset of  variables, but under normal circumstances many of these will be constant random variables, so we can ignore them (they are omitted from the diagram to give a cleaner example).

The central metric of condensation is the conditioned score , which is a score for every variable  in an LVM. The idea is that if two LVMs minimize every  simultaneously, they end up “sharing the same concepts” (in a certain sense).

Example application

A simple example where the latent variables are more “objective” is in clustering problems. The “objectively correct” latent variables are cluster parameters. If some clusters share similarities, then we have an “objectively correct” hierarchy of clusters. Take a second to intuitively understand the generating process of this data:

We start with access to a distribution over a set of observation variables. In this example, we have a sequence of 36 2D observations.

For future use, we will calculate the joint entropy of some (carefully chosen) groups of these variables:

As you can see if you watch the animation for a while, there is a hierarchical generating process behind this data. There are always four clusters, divided into two groups. Within each cluster, each sample is independent of the others. In each group, the cluster means are relatively close to each other. The shape of each cluster is always roughly the same as the shape of each other cluster.

We have lots of options for modelling this. We could fit an autoregressive sequence model such that it outputs a distribution and samples from it at every timestep. This would look like:

Each node is labelled with its conditional entropy given its parents. We can use these to see how well this model does according to the  scores. To work out a score , we look at a subset of  variables and add up the conditional entropy of every  variable that contributes to that set. We then compare that to .  will always be bigger than , and if they’re close together the score is good. If we try  for the autoregressive model, we get . This is the same as , so the score is perfect at .

In contrast, if we try , we get . This is far higher than , so the score is bad at . Similarly, , and most other sets have very bad scores.

So let’s look at another model structure. We could fit a generative model of all datapoints simultaneously using a GAN, VAE or Normalizing Flow. These generative models all involve sampling vector from a simple distribution and then passing it through a neural net to produce a sample from the learned distribution.

This has a bad score for most choices of , especially where  is a small subset. The only good score is .

In contrast, if we represent it as a Bayes net like this, we can see the structure more clearly:

This has a much better score for most subsets. For example, . Compare this to , it’s not too bad, much closer than previous models. For , it’s close to .

You might be wondering why these scores aren’t perfect, i.e. why does  not equal . The difference will be , which is how precisely we can nail down the parameters in  after observing . This should give you some intuition for when it’s possible to make a good condensation: When the relevant latent variables of the model can be precisely estimated from a single observation (or small subset of observations). This is why it works well for clustering parameters. The location parameter of a cluster () can be fairly accurately estimated from just a single sample from that cluster.

What we can see is that minimizing the  score everywhere requires that we divide up the noise variables in a way that attaches them only to exactly the observation variables that they influence. It also forces each  variable to have the minimal possible entropy, so any unnecessary entropy will be removed. So we end up with this minimal latent variable model that is factored into meaningful chunks.

Selected Results from Sam’s paper

When is perfect condensation possible?

Theorem 5.10 in the paper^[2] gives us the necessary and sufficient properties for a perfect condensation (which is a condensation where every score  is equal to :

1. Every  is a function of any  if . I.e. only one example suffices to nail down every latent variable above it.
2. The  variables satisfy a Bayes net structure^[3] such that  is a parent of  iff  is a subset of  (i.e. parents are always supersets, children are always subsets).

A third condition to keep in mind is enforced by the definition of a Latent Variable Model (Definition 4.2): Every  variable needs to be recoverable from the  variables that contribute to it.

To what extent will LVMs be approximately equivalent?

When the scores are perfect there is a kind of exact correspondence (Theorem 5.15). We take a  and all of its parents, grandparents, etc, () and consider this combined object to be a concept. Then for any two LVMs with perfect scores, each concept is equivalent in the sense that these random variables are deterministic functions of each other ().

Things get more complicated when the score aren’t quite perfect, because the theorem needs to account for information that might be mixed up in surrounding nearby concepts.

Sam has a more general theorem (6.8) for the imperfect case (where the scores aren't perfectly minimized) that extends the above theorem in two ways:

1. For each , instead of only having a bound for , we can bound a more general conditional entropy term  where we have some freedom in choosing the set . So we'll usually have  be a slightly larger set than  (so it captures most of the information that has "leaked" into surrounding concepts) and then the theorem will show that we can almost recover  from .
2. Insofar as the "Bayesnet structure" of perfect condensation is violated, we can bound the conditional entropy  by "how much the Bayesnet structure is violated", which is measured by some conditional mutual information terms.

Correspondences between Natural Latents and Condensations

Here we have a sequence of theorems that show how closely related the theory of Condensation is to the theory of Natural Latents. They are also helpful for highlighting the differences.

Definitions

Natural Latent

Let's first recall the definition of a Natural Latent. An -approximate natural latent  with respect to variables  satisfies two conditions:

Mediation:  ^[4]

Redundancy:  ^[5]

Condensation

Now let's more formally write out a definition of a Condensation. An -approximate Condensation with respect to variables  is a set of latent variables , where  can represent any subset of .

The latent variables must satisfy two conditions:

Conditioned Score:

The score  is called the conditioned score, where  is the set of  variables “above” . It’s bounded below by .

We have an -approximate condensation when the conditioned score is almost minimal:

Latent Variable Model condition (Definition 4.2): We can exactly recover each  from the set of latent variables  (all the latent variables “above” ).

An approximate condensation can be used to construct an approximate weak natural latent

If we have an approximate condensation of a set of observables, then we can construct a weak natural latent of any subset of those observables. A weak natural latent can’t be recovered from any observable, instead it can be recovered from all-but-one (slightly different from the definition above). We construct the natural latent by collecting together all of the condensation latent variables that contribute to more than one of the observables.

Setup

We say that a latent variable model satisfies -approximate condensation if the following holds:

 ^[6]

Suppose that we have an -approximate condensation .

Now fix a subset of observables . We construct a natural latent  over  by bundling together all latent variables (from the perfect condensation)  with .

Proof

We'll start by proving the mediation condition.

Denote  where .

Each  is a deterministic function of , which means:

 (1)

From our assumptions about the conditioned score we get:

^[7] (2)

Using (1) and (2), we can show that the mediation error of  is less than :

Now we'll prove the approximate weak redundancy property.

A latent variable  satisfies the weak redundancy property for variables in  when

We start with  from Proposition 5.2 (for arbitrary ), and apply the definition of -approximate condensation to get:

Since  is a deterministic function of , we have that .

Combining these we have (for any ):

If we set  to  for any , then this gives us the weak redundancy property:

This follows because we can turn  into  because  includes  as well as .

When can we recover an approximate strong natural latent?

The previous statement was about weak natural latents. This one tells us when we can get the usual definition of natural latents out of a condensation, and it ends up being exactly when there isn't lower level structure inside of that subset. For both this theorem and the above, we are getting lots of natural latents out of a single condensation.

Setup

Given an -approximate condensation  that satisfies . For any subset , we define  and set . If we have , then  is an -approximate natural latent over .

Intuitively, the  condition means that there’s approximately no lower-level structure among the variables in . Approximately all the shared information between these variables is stored in .

Proof

To show strong redundancy:

For each  is a deterministic function of  (because of the Latent Variable Model condition).

And  by applying the definition of -approximate condensation with .

Combining these we have for all :

Which is the strong redundancy condition.

To show Mediation:

 is an approximate weak natural latent for  as constructed in the previous section

For any random variable  we have ^[8] (1)

We also have ^[9] (2)

Applying (1) to each  term and (2) to , we have

From previous section  satisfies approximate mediation  which means 

(The bound can be improved a bit but would result in a more complicated expression, intuitively for each , once we condition on ,  only contains latent variables in  that are not already included in , whereas  includes latent variables not in , which makes  larger.)

If we have a natural latent we can construct a condensation

This is the reverse of the above. Any time we have a natural latent, we can use it to construct a condensation. Because a natural latent is a relatively simple structure, we get a condensation with a simple structure (with double the error because we get error contribution from both the mediation and redundancy properties).

Setup

Given a -approximate natural latent  over , we construct an -approximate condensation  over  by setting ,  and set the rest of the latent variables empty.

Proof

The latent variable model condition is satisfied because  (all  variables above ) is equivalent to  and  fully determines .

The mediation property of natural latents can be rearranged to give .

We substitute that into the conditioned score to get this bound:

Then we can use the strong redundancy property :

Which is a  bound on the conditioned score:

The conditioned score  for each subset  is also bounded by following the same reasoning.

Comparison of agreement theorems in condensation and natural latents

The condensation agreement says that if we have two perfect condensations  and  on a collection of observables , then  will be a deterministic function w.r.t  for all subsets , similarly  will be a deterministic function w.r.t  for all subsets .

The natural latent agreement condition says that if we have two natural latents  w.r.t a collection of observables , then  and  will be deterministic functions of each other

The natural latent agreement theorem can be thought of as a special case of the condensation agreement theorem. To see this, suppose that we have two natural latents  over some observables . We can construct two latent variable models ,  by setting  and . Note that both  and  will be perfect condensations since our construction is identical to the theorem in the previous section.

By the condensation agreement theorem,  is a function of , but  as there is no strict super set of  in ,^[6] this means that  is a function of , applying this in reverse also gives us  is a function of . Since we initially set  and , we conclude that  and  are deterministic functions of each other.

In summary, condensation provides agreement result in a more general setting where your latent variable can be decomposed into smaller pieces (instead of just being a single undifferentiated latent variable ), and we can reason about uniqueness of those smaller pieces. Of course, in this more general case we don’t get exact isomorphism of the latent variable model, instead we have the weaker guarantee that  is a function of .

This post was written as part of the PIBBSS × Iliad research residency. Daniel C has more results about relationships between Natural Latents and Condensations but we didn't have time to include them all in this post, hopefully they'll be posted separately later.

1. ^{^}

   More precisely we should say inter-subjective, since it depends on each agent having similar observations, among other shared assumptions.

2. ^{^}

   

3. ^{^}

   A Bayes net is a set of conditional independence statements. By satisfy I mean that it has to satisfy all of these independence statements, but it might also be compatible with more.

4. ^{^}

   Usually written as  in John’s posts

5. ^{^}

   This is the deterministic redundancy condition from here.

6. ^{^}

   We're using  for the powerset minus the empty set, and  is just . So  is the set of all possible latent variable indices.

7. ^{^}

   We start with 

   (to see this, expand  by chain rule, and we can see that the LHS condition on more variables than RHS which only conditions on upstream variables, and conditioning can only reduce entropy

   Similarly, expand  by chain rule, we can see that the LHS condition on more variables than RHS for subsets  with )

   Applying the definition of -approximate condensation:

   which we can rearrange to get:

    

8. ^{^}

   Subtracting  by both sides gives the desired inequality.

9. ^{^}