Algorithmic condensation

I needed a more detailed sketch of algorithmic condensation so I could build on it, so here's what I've got. I've done a proof for two concrete cases of the objectivity theorem, which I find much easier to understand than keeping track of the indices in the fully general proof.

Latent String model

A latent string model is a set of observations and a set of latent strings , and a Turing machine , such that prints

1. appropriately separated, then
2. a mapping from each index to subsets of (in some specified format, e.g. "<numeral for j>:<ordered list of ts>,..."), which defines the contribution function . We guarantee that the first latent contributes to all observations.

In addition, if is given any -upward closed subset of the latents, it prints roughly the same output, except we only guarantee that:

1. Each is correct if the set of latents contains all latents that contribute to .
2. The printed contribution function is correct on all given latents. Additionally, it needs to be able to overestimate the contribution of unseen latents. We'll call this overestimating version of the contribution function , and guarantee that for all unseen , . We also guarantee that if then .

Almost perfect

We'll say that this latent string model is an -almost perfect condensation if

1. (Reconstruction) For all , if then
   • If contains more than a fraction of the observations that contribute to , then we can reconstruct from that set of observations (given the larger context latents).
2. (Markov) for all -upward closed sets , we have
   • If we set up the strings in a directed graph where a node is a child if its contribution is a subset of a parent (so there are never any grandparents, only parents), we have analogous conditional independence properties as a Bayes net, approximately.
     • A Bayes net has a local Markov property that each variable is conditionally independent of its non-descendants given its parents. don't have shared descendants, and all shared ancestors are in their intersection. So d-separation can be used to show that this Markov property is implied by the Bayes net local Markov property. In the reverse direction, we can recover the local Markov property for any given node by taking any node , then for every node that isn't a descendant, we have that 's parents gives us independence from those nodes.
3. (Well-separated) for all distinct , either we have or
   • Any two latents will contribute to sufficiently different observation sets, such that the two latents can be easily distinguished.
   • When is a smallest parent of , we assume that we still have (using the overestimating contribution function rather than the true contribution function).

Objectivity for almost perfect

Given two models, and , which are both -almost perfect condensations of the same data , we want to sketch how the objectivity result works.

For concreteness, let's assume looks like:

1: {1,2,3,4,5,6,7,8,9,10,11,12}
2,3,4:
{1,2,3,4,5,6},{4,5,6,7,8,9},{7,8,9,10,11,12}

and looks like:

1: {1,2,3,4,5,6,7,8,9,10,11,12}
2,3,4:
{2,3,4,5,6},{5,6,7,8,9,10},{8,9,10,11,12,1}

First let's bound .

Here's the proof structure: First we find observation patches outside of each non- latent. Then we find the latents that contribute to these opposite patches. Then we apply Lemma 5.4 as many times as necessary to isolate .

Observation patches are , , .

The relevant latents to each patch are , , .

Applying Lemma 5.4 to the first two:

Then combining that resulting set of s with the last set :

Merging the two equations:

We can immediately bound each of the mutual information terms by using the Markov condition.

To bound the first K-complexity, we use the definition of latent string model that allows us to recover subsets of observations from subsets of latents. prints out all the observations and prints out which tells us which ones definitely doesn't contribute to (so we can rely on the printed observations being accurate). Well-separatedness guarantees that more than enough of these remain such that can be reconstructed using the Reconstruction assumption. By applying the reconstruction assumption we can replace the K-complexity with .

So overall we have

where is the number of merges required (usually low, but can be up to ).

Now let's bound .

The same proof structure as above: First we find observation patches outside of each non- latent. Then we find the latents that contribute to these opposite patches. Then we apply Lemma 5.4 (see proof below) as many times as necessary to isolate .

Observation patches: ,

Relevant s: ,

Apply Lemma 5.4:

Now it's slightly trickier to get rid of the K-complexities, because we only have the weaker reconstruction assumption . But we can reconstruct from with only error, so we can do

.

This uses the bound

This overall leaves us with

Note that the 5 comes from the example and depends on the number of merge steps required, it'll generally scale up with the number of children.

A small modification probably gives us and might be considered a more natural bound, but haven't checked the details.

Proof of Lemma 5.4

On the complexity metric

We're using , which is the length of the shortest prefix-free code for the string .

We could use complexity, which defines the conditional . To do this, we'd need to assume that all strings in the latent model are maximally compressed (or that we know their maximally compressed length) and that we know the compressed length of every upward closed subset. This isn't that implausible an assumption, since we usually want a latent variable model to also be (at least approximately) a minimal length model. This would allow every step of our proofs to only have additive constants rather than . The reason I'm choosing to not use Kc is that I want the result to be more robust to approximation, so I don't want a strong optimality condition on the latent string model.

Objectivity theorem

Missing from this document is how this proof generalizes across all latents in and , and how it generalizes to any latent variable models that satisfies the Reconstruction, Markov and Well-Separated conditions.

Sam says there's an objectivity theorem that says that if both and are -almost perfect condensations of the same observation set, then there is a bijection between the latents. I think this might require an extra axiom (something like "every latent is necessary" or "there aren't additional independences other than the ones implied by the latents"). I'm fairly sure this will hold but haven't worked through a full proof yet.