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
appropriately separated, then
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:
Each is correct if the set of latents contains all latents that contribute to .
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
(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).
(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.
(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.
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.
Thanks. For what it’s worth, I find this much easier to think about than the graph formulation I’ve seen at Sam’s talks.
I of course find this extremely reminiscent of parameter decomposition[1], but I guess a lot of things would be reminiscent of condensation, that’s sort of the point of it.
Just switch out “Turing machine” for “neural network”, “latent string ” for “parameter component ”, “contribution relation” for “causal importance function”, and pass the components into the network via addition in parameter space. It’s not a perfect match because if I understand correctly this seems to assume contributions relations are fixed and don’t vary when resampling a , while retraining a parameter component can change its causal importances.
I’ve been working on a condensation post which includes a proposal for algorithmic condensation. My version mostly matches yours, but one important difference is that I use which avoids paying constants without an optimality assumption. You can pay a log cost once at the very end instead of throughout the proofs.
I’m curious what you think of this… I’m still getting comfortable working with AIT so I’m not super confident of this but it seems to work...
I haven’t seen conditional K complexity defined that way before, is there a textbook you’re getting it from? I’m not sure I’d want to drop the interpretation of conditional complexity as the length of a program, since that fits nicely with the latent string model definition, but maybe it’s a good idea anyway.
It’s not a textbook definition but it is based on Chaitin, G. J. (1975). “A Theory of Program Size Formally Identical to Information Theory.” (link)
Here’s the idea:
You have , and then you just define so the chain rule holds by construction and .
You don’t have to interpret as program receiving , though, if you treat it just as arithmetic on K complexities. It’s a bit of a stupid thing, but if I understand correctly, you can avoid any optimality assumption and keep the program-length interpretation. Because of this asymmetry:
If we start with the latent string model assumptions you already have, then you can work in for and then you just have to go the other way and pay once at the very end.
Where in the paper does Chaitin use that definition?
I think there’s some sense in which the optimality assumption will be implicit if we do it like that, but I do like the idea of not stacking up a log for every merge.
I didn’t mean to imply that it was in the paper as I have it, that’s why I said based on instead of from, sorry if that was confusing. It’s a presentational thing and it’s fine to just use instead (although I think a bit less clean).
I don’t see how there’s an implicit optimality assumption unless you’re trying to read quantities at every step in the proof as a program length. I agree that there’s something aesthetically worse about a proof that routes through something less nicely interpretable.
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
a mapping from each index
In addition, if
Each
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
Almost perfect
We’ll say that this latent string model is an
(Reconstruction) For all
If
(Markov) for all
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.
(Well-separated) for all distinct
Any two latents will contribute to sufficiently different observation sets, such that the two latents can be easily distinguished.
When
Objectivity for almost perfect
Given two models,
For concreteness, let’s assume
and
First let’s bound
Here’s the proof structure: First we find observation patches outside of each non-
Observation patches are
The relevant latents to each patch are
Applying Lemma 5.4 to the first two:
Then combining that resulting set of
Merging the two equations:
We can immediately bound each of the mutual information terms by
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.
So overall we have
where
Now let’s bound
The same proof structure as above: First we find observation patches outside of each non-
Observation patches:
Relevant
Apply Lemma 5.4:
Now it’s slightly trickier to get rid of the K-complexities, because we only have the weaker reconstruction assumption
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
Proof of Lemma 5.4
On the complexity metric
We’re using
We could use
Objectivity theorem
Missing from this document is how this proof generalizes across all latents in
Sam says there’s an objectivity theorem that says that if both
Thanks. For what it’s worth, I find this much easier to think about than the graph formulation I’ve seen at Sam’s talks.
I of course find this extremely reminiscent of parameter decomposition[1], but I guess a lot of things would be reminiscent of condensation, that’s sort of the point of it.
Just switch out “Turing machine” for “neural network”, “latent string
I’ve been working on a condensation post which includes a proposal for algorithmic condensation. My version mostly matches yours, but one important difference is that I use
I’m curious what you think of this… I’m still getting comfortable working with AIT so I’m not super confident of this but it seems to work...
I haven’t seen conditional K complexity defined that way before, is there a textbook you’re getting it from? I’m not sure I’d want to drop the interpretation of conditional complexity as the length of a program, since that fits nicely with the latent string model definition, but maybe it’s a good idea anyway.
It’s not a textbook definition but it is based on Chaitin, G. J. (1975). “A Theory of Program Size Formally Identical to Information Theory.” (link)
Here’s the idea:
You have
You don’t have to interpret
If we start with the latent string model assumptions you already have, then you can work in
Where in the paper does Chaitin use that definition?
I think there’s some sense in which the optimality assumption will be implicit if we do it like that, but I do like the idea of not stacking up a log for every merge.
I didn’t mean to imply that it was in the paper as I have it, that’s why I said based on instead of from, sorry if that was confusing. It’s a presentational thing and it’s fine to just use
I don’t see how there’s an implicit optimality assumption unless you’re trying to read quantities at every step in the proof as a program length. I agree that there’s something aesthetically worse about a proof that routes through something less nicely interpretable.