Some Rules for an Algebra of Bayes Nets

David Lorell

Here's a new Bookkeeping Theorem, which unifies all of the Bookkeeping Rules mentioned (but mostly not proven) in the post, as well as all possible other Bookkeeping Rules.

If all distributions which factor over Bayes net also factor over Bayes net $G_{2}$ , then all distributions which approximately factor over $G_{1}$ also approximately factor over $G_{2}$ . Quantitatively:

$D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{1} (i)}]) \geq D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{2} (i)}])$

where $p a^{j} (i)$ indicates parents of variable $i$ in $G_{j}$ .

Proof: Define the distribution $Q [X] := \prod_{i} P [X_{i} | X_{p a^{1} (i)}]$ . Since $Q [X]$ exactly factors over $G_{1}$ , it also exactly factors over $G_{2}$ : $Q [X] = \prod_{i} Q [X_{i} | X_{p a^{2} (i)}]$ . So

$D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{1} (i)}]) = D_{K L} (P [X] | | Q [X])$

$= D_{K L} (P [X] | | \prod_{i} Q [X_{i} | X_{p a^{2} (i)}])$

Then by the factorization transfer rule (from the post):

$\geq D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{2} (i)}])$

which completes the proof.

[-]Mateusz Bagiński1y70

$= D_{K} L (P [X] | | \prod_{i \leq k + 1} P [X_{i - 1} | X_{i}]) P [X_{k + 1}] (\prod_{k + 1 \leq i} P [X_{i + 1} | X_{i}])$

I think the parentheses are off here. IIUC you want to express the equality of divergences, not divergences multiplied by probabilities (which wouldn't make sense I think).

$ϵ_{blanket} g e q D_{K L} (P [X, Y, Z] | | P [X | Y] P [Y] P [Z | Y])$
$= D_{K L} (P [X, Y, Z] | | P [X, Y] P [Z, Y] / P [Y])$

Typo: $g e q$ -> $\geq$

[-]johnswentworth1y20

Man, that top one was a mess. Fixed now, thank you!

[-]Vanessa Kosoy9moΩ560Review for 2023 Review

This article studies a natural and interesting mathematical question: which algebraic relations hold between Bayes nets? In other words, if a collection of random variables is consistent with several Bayes nets, what other Bayes nets does it also have to be consistent with? The question is studied both for exact consistency and for approximate consistency: in the latter case, the joint distribution is KL-close to a distribution that's consistent with the net. The article proves several rules of this type, some of them quite non-obvious. The rules have concrete applications in the authors' research agenda.

Some further questions that I think would be interesting to study:

Can we derive a full classification of such rules?
Is there a category-theoretic story behind the rules? Meaning, is there a type of category for which Bayes nets are something akin to string diagrams and the rules follow from the categorical axioms?

[-]Alexander Gietelink Oldenziel9moΩ574

I've been told a Bayes net is "just" a functor from a free Cartesian category to a category of probability spaces /Markov Kernels.

[-]Vanessa Kosoy9moΩ450

Seems right, but is there a categorical derivation of the Wentworth-Lorell rules? Maybe they can be represented as theorems of the form: given an arbitrary Markov category C, such-and-such identities between string diagrams in C imply (more) identities between string diagrams in C.

[-]Lorxus5mo*Ω230

Hi! I spent some time working on exactly this approach last summer at MATS, and since then have kept trying to work out the details. It's been going slowly but parts of it have been going at all.

My take regarding your and @Alexander Gietelink Oldenziel's comments below is - that's not a thing that really happens? You pick the rules and your desired semantics first, and then you write down your manipulation rules to reflect those. Maybe it turns out that you got it wrong and there's more (or fewer!) rules of derivation to write down, but as long as the rules you wrote down follow some very easy constraints, you can just... write down anything. Or decline to. (Also, from a quick read I'm fairly sure you need a little bit more than just "free cartesian category" to hold of your domain category if you want nice structures to hang state/kernel-labels on. You want to be able to distinguish a concrete Bayes net (like, with numbers and everything) from an abstract "Bayes net", which is just a directed acyclic graph representing local conditionality structures - though we should note that usually people working with Bayes nets assume that we actually have trees, and not just DAGs!)

Maybe there's arguments from things like mathematical elegance or desired semantics or problematizing cases to choose to include or exclude some rule, or formulate a rule in one or another way, but ultimately you get to add structure to a category as suits you.

Can we derive a full classification of such rules?

Probably there's no full classification, but I think that a major important point (which I should have just written up quickly way way long ago) is that we don't quite care about Markov equivalence class - only about whether any given move takes us to a diagram still compatible with the joint distribution/factorization that we started with.

Is there a category-theoretic story behind the rules? Meaning, is there a type of category for which Bayes nets are something akin to string diagrams and the rules follow from the categorical axioms?

In my understanding there's a pretty clear categorical story - some of which are even just straight trivial! - to most of the rules. They make good sense in the categorical frame; some of them make so much sense that they're the kind of thing string diagrams don't even bother to track. I'm thinking of Factorization Transfer here, though the one major thing I've managed to get done is that the Joint Independence rule actually follows as a quick technical lemma from its assumptions/setup, rather than having to be assumed.

There's noncanonical choices getting made in the two "binary operation" rules, but even then it seems to me like the fact that we only ever apply that operation to two diagrams of the same "flavor" means we should likely only ever get back another diagram of the same "flavor"; apart from that, there's a strong smell of colimitness to both of those rules, which has kept me mulling over whether there's a useful "limitish" sort of rule that John and David both missed. Underlying this is my suspicion that we might get a natural preorder structure on latent Bayes nets/string diagrams as the pullback of the natural lattice on Markov equivalence classes, where one MEC is above another if it has strictly more conditionality relationships in it - i.e. the unique minimal element of the lattice is "everything is independent", and there's lots of maximal elements, and all our rules need to keep us inside the preimage of the upset of our starting MEC.

Which is to say: yes, yes there totally is such a type of category, but existing work mostly stopped at "Bayes nets akin to string diagrams", although I've seen some non-me work lately that looks to be attacking similar problems.

[-]Vanessa Kosoy5moΩ220

I found the above comment difficult to parse.

that's not a thing that really happens?

What is the thing that doesn't happen? Reading the rest of the paragraph only left me more confused.

we don't quite care about Markov equivalence class

What do you mean by "Markov equivalence class"?

[-]Lorxus5moΩ130

that's not a thing that really happens?
What is the thing that doesn't happen? Reading the rest of the paragraph only left me more confused.

Somehow being able to derive all relevant string diagram rewriting rules for latential string diagrams, starting with some fixed set of equivalences? Maybe this is just a framing thing, or not answering your question, but I would expect to need to explicitly assume/include things like the Frankenstein rule - more generally, picking which additional rewriting rules you want to use/include/allow is something you do in order to get equivalence/reachability in the category to line up correctly with what you want that equvialence to mean - you could just as soon make those choices poorly and (e.g.) allow arbitrary deletions of states, or addition of sampling flow that can't possibly respect causality; we don't do that here because it wouldn't result in string diagram behavior that matches what we want it to match.

I think I may have misunderstood, though, because that does sounds almost exactly like what I found to happen for the Joint Independence rule - you have some stated equivalence, and then you use string diagram rewriting rules common to all Markov category string diagrams in order to write the full form of the rule.

Simple form of the JI Rule - note the equivalences in the antecedent, which we can use to prove the consequent, not just enforce the equivalence!

we don't quite care about Markov equivalence class
What do you mean by "Markov equivalence class"?

Two Bayes nets are of the same Markov equivalence class when they have precisely the same set of conditionality relations holding on them (and by extension, precisely the same undirected skeleton). You may recognize this as something that holds true when applicable for most of these rules, notably (sometimes) including the binary operations and notably excluding direct arrow-addition; additionally, this is something that applies for abstract Bayes nets just as well as concrete ones.

[-]Vanessa Kosoy5moΩ220

Somehow being able to derive all relevant string diagram rewriting rules for latential string diagrams, starting with some fixed set of equivalences?

What are "latential" string diagrams?

What does it it mean that you can't derive them all from a "fixed" set? Do you imagine some strong claim e.g. that the set of rewriting rules being undecidable, or something else?

Two Bayes nets are of the same Markov equivalence class when they have precisely the same set of conditionality relations holding on them (and by extension, precisely the same undirected skeleton).

Okay, so this is not what you care about? Maybe you are saying the following: Given two diagrams X,Y, we want to ask whether any distribution compatible with X is compatible with Y. We don't ask whether the converse also holds. This is a certain asymmetric relation, rather than an equivalence.

[-]Lorxus5moΩ010

What are "latential" string diagrams?

Just the word I use to describe "thing that has something to do with (natural) latents". More specifically for this case: a string diagram over a Markov category equipped with the extra stuff, structure, and properties that a Markov category needs to have in order to faithfully depict everything we care about when we want to write down statements or proofs about Bayes nets which might transform in some known restricted ways.

What does it it mean that you can't derive them all from a "fixed" set? Do you imagine some strong claim e.g. that the set of rewriting rules being undecidable, or something else?

Something else. I'm saying that:

You would need to pick your set of identities once and for all at the start, as part of specifying what extra properties the category has; you could totally use those as (or to derive) some of the rules (and indeed I show how you can do just that for Breakout Joint Independence)
Binary operations like Frankenstein or Stitching probably don't fall out of an approach like that (they look a lot more like colimits
Rules which a categorical approach trivializes like Factorization Transfer don't particularly fall out of an approach like that
You could probably get some kind of "ruleset completeness" result if you had a strong sense of what would constitute a complete ruleset - the paper I linked above looks to be trying to do this

...so maybe some approach where you start by listing off all the identities you want to have hold and then derive the full ruleset from those would work at least partially? I guess I'm not totally clear what you mean by "categorical axioms" here - there's a fair amount that goes into a category; you're setting down all the rules for a tiny toy mathematical universe and are relatively unconstrained in how you do so, apart from your desired semantics. I'm also not totally confident that I've answered your question.

Okay, so this is not what you care about? Maybe you are saying the following: Given two diagrams X,Y, we want to ask whether any distribution compatible with X is compatible with Y. We don't ask whether the converse also holds. This is a certain asymmetric relation, rather than an equivalence.

Yes. Well... almost. Classically you'd care a lot more about the MEC, but I've gathered that that's not actually true for latential Bayes nets. For those, we have some starting joint distribution J, which we care about a lot, and some diagram D_J which it factors over; alternatively, we have some starting set of conditionality requirements J, and some diagram D_J from among those that realize J. (The two cases are the same apart from the map that gives you actual numerical valuations for the states and transitions.)

We do indeed care about the asymmetric relation of "is every distribution compatible with X also compatible with Y", but we care about it because we started with some X_J and transformed it such that at every stage, the resulting diagram was still compatible with J.

[-]Vanessa Kosoy5moΩ340

I think that there are two different questions which might be getting mixed up here:

Question 1: Can we fully classify all rules for which sets of Bayes nets imply other Bayes nets over the same variables? Naturally, this is not a fully rigorous question, since "classify" is not a well-defined notion. One possible operationalization of this question is: What is the computational complexity of determining whether a given Bayes net follows from a set of other Bayes nets? For example, if there is a set of basic moves that generate all such inferences then the problem is probably in NP (at least if the number of required moved can also be bounded).

Question 2: What if we replace "Bayes nets" by something like "string diagrams in a Markov category"? Then there might be less rules (because maybe some rules hold for Bayes nets but not in the more abstract setting).

[-]Jeremy Gillen2y60

This is one of my favorite posts because it gives me tools that I expect to use.

A little while ago, John described his natural latent result to me. It seemed cool, but I didn't really understand how to use it and didn't take the time to work through it properly. I played around with similar math in the following weeks though; I was after a similar goal, which was better ways to think about abstract variables.

More recently, John worked through the natural latent proof on a whiteboard at a conference. At this point I felt like I got it, including the motivation. A couple of weeks later I tried to prove it as an exercise for myself (with the challenge being that I had to do it from memory, rigorously, and including approximation). This took me two or three days, and the version I ended up with used a slightly different version of the same assumptions, and got weaker approximation results. I used the graphoid axioms, which are the standard (but slow and difficult) way of formally manipulating independence relationships (and I didn't have previous experience using them).

This experience caused me to particularly appreciate this post. It turns lots of work into relatively little work.

[-]rotatingpaguro2y60

Re-Rooting Rule for Markov Chains
Joint Independence Rule
Frankenstein Rule
Factorization Transfer Rule
Stitching Rule for A Shared Markov Blanket
Swap Rule <=====
Bookkeeping Rules

Can't find the "Swap rule" in the post, what was that?

The more complex approximation rule requires some additional machinery. For any diagram, we can decompose its into one term for each variable via the chain rule:
$D_{K L} (P [X_{1}, \dots, X_{n}] | | \prod_{i} P [X_{i} | X_{p a (i)}]) = D_{K L} (\prod_{i} P [X_{i} | X_{< i}] | | \prod_{i} P [X_{i} | X_{p a (i)}])$
$= \sum_{i} E [D_{K L} (P [X_{i} | X_{< i}] | | P [X_{i} | X_{p a (i)}])]$ <=====
If we know how our upper bound $ϵ$ on the diagram’s $D_{K L}$ decomposes across variables, then we can use that for more fine-grained bounds. Suppose that, for each diagram $j$ and variable $i$ , we have an upper bound
$ϵ_{j}^{i} \geq E [D_{K L} (P [X_{i} | X_{< i}] | | P [X_{i} | X_{p a_{j} (i)}])]$ <=====

I guess here there are missing expectations (indicated in red), otherwise $X_{< i}$ would remain a free RV. The second expectation is not necessary, although omitting it makes the bound unnecessarily strict.

I have never encountered this topic, and I couldn't find it skimming the Handbook of Graphical Models (2019), did you invent it? If not, could you list references?

Do you perchance have something for conditioning or marginalization? I know that graphical marginalization requires using ADMGs (graphs with double-headed arrows) instead of DAGs, I don't know about conditioning.

Exercise
Extend the above proofs to re-rooting of arbitrary trees (i.e. the diagram is a tree). We recommend thinking about your notation first; better choices for notation make working with trees much easier.

In a tree each node has a single parent. Re-rooting means flipping the arrow from the root to one of its children.

In the factorization I do P(old_root)P(new_root|old_root) = P(old_root|new_root)P(new_root), so the proof is the same.

The fact that notation is not involved makes my suspect I may be missing something. Maybe they mean it's needed to write out in full the factorization expression? I guess the nice notation is using ch(X_i) instead of pa(X_i).

Joint Independence Rule: Exercise
The Joint Independence Rule can be proven using the Frankenstein Rule. This is left as an exercise. (And we mean that unironically, it is actually a good simple exercise which will highlight one or two subtle points, not a long slog of tedium as the phrase “left as an exercise” often indicates.)
Bonus exercise: also prove the conditional version of the Joint Independence Rule using the Frankenstein Rule.

Joint independence starts from the graphs

X_i {X_not i}

for all i. The Frankenstein rule can not be applied right away because the graphs are not on the same variables, since all but one appear grouped as a single tuple node.

To change that, I replace the tuple nodes with fully connected subgraphs. This is valid because cliques do not constrain the distribution, as any distribution can be factorized in any order if all variables are kept in the conditionals.

I choose the connection order of the cliques such that they respect a global ordering.

Then I apply Frankenstein, picking, for each node, the graph where that node is isolated.

Is there a way to obtain a narrower bound? Yes: I can pick only $D_{K L} (P (X_{i} | X_{< i}) ∥ P (X_{i}))$ from the i-th graph.

Conditional version: basically the same proof, with the common parent as first node in the global order. Needs more care in justifying replacing a tuple node with a clique: Conditional on the parent, the argument above still goes. The only additional independence property of the graph with the tuple is that the parent d-separates the tuple from the singlet, and that is preserved as well.

Frankenstein Rule
We’ll prove the approximate version, then the exact version follows trivially.
Without loss of generality, assume the order of variables which satisfies all original diagrams is $X_{1}, \dots, X_{n}$ . Let $P [X] = \prod_{i} P [X_{i} | X_{p a^{j} (i)}]$ be the factorization expressed by diagram $j$ , and let $σ (i)$ be the diagram from which the parents of $X_{i}$ are taken to form the Frankenstein diagram. (The factorization expressed by the Frankenstein diagram is then $P [X] = \prod_{i} P [X_{i} | X_{p a^{σ (i)} (i)}]$ .)
The proof starts by applying the chain rule to the $D_{K L}$ of the Frankenstein diagram:
$D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{σ (i)} (i)}]) = D_{K L} (\prod_{i} P [X_{i} | X_{< i} | | \prod_{i} P [X_{i} | X_{p a^{σ (i)} (i)}])$
$= \sum_{i} E [D_{K L} (P [X_{i} | X_{< i}] | | P [X_{i} | X_{p a^{σ (i)} (i)}])]$ <=====
Then, we add a few more expected KL-divergences (i.e. add some non-negative numbers) to get:
$\leq \sum_{i} \sum_{j} E [D_{K L} (P [X_{i} | X_{< i}] | | P [X_{i} | X_{p a^{j} (i)}])] = \sum_{j} D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{j} (i)}])$
$\leq \sum_{j} ϵ_{j}$
Thus, we have
$D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{σ (i)} (i)}]) \leq \sum_{j} D_{K L} (P [X] | | \prod_{i} P [X_{i} | X_{p a^{j} (i)}]) \leq \sum_{j} ϵ_{j}$ <=====

I guess you meant the green thing (first margin arrow) to appear in place of the red thing (second margin arrow)? The math is right, but I hypothesize the final line was intended to express at once the narrow and the loose bounds.

[-]johnswentworth2y30

Can't find the "Swap rule" in the post, what was that?

Oh lol, that was in a draft and I took it out.

I guess here there are missing expectations (indicated in red), otherwise would remain a free RV.

Good catch, thanks.

Exercise answers look good.

[-]rotatingpaguro2y40

Aaaand about this?

I have never encountered this topic, and I couldn't find it skimming the Handbook of Graphical Models (2019), did you invent it? If not, could you list references?

[-]johnswentworth2y40

I wouldn't be surprised if someone else has done this before, but I did not get it from anywhere else and have never seen anyone else do something quite like it.

[-]Oliver Sourbut2y*52

This is really great!

A few weeks ago I was playing with the Good Regulator and John's Gooder version and incidentally I also found myself pulling out some simple graphical manipulation rules. Your 'Markov re-rooting' came into play, and also various of the 'Bookkeeping' rules. You have various more exciting rules here too, thanks!

I also ended up noticing a kind of 'good regulator motif' as I tried expanded the setting with a few temporal steps and partial observability and so forth. Basically, doing some bookkeeping and coarse-graining, you can often find a simple GR structure within a larger 'regulator-like' structure, and conclude things from that. I might publish it at some point but it's not too exciting yet. I do think the overall move of finding motifs in manipulated graphs is solid, and I have a hunch there's a cool mashup of Bayes-net algebra and Gooder Regulator waiting to be found!

I love the Frankenstein rule. FYI, the orderings you're talking about which are 'consistent' with the graphs are called topological orderings, and every DAG has (at least) one. So you could concisely phrase some of your conditions along the lines of 'shared topological order' or 'mutually-consistent topological ordering'.

BTW causal graphs are usually restricted to be DAGs, right? (i.e., the 'causes' relation is acyclic and antisymmetric.) So in this setting where we are peering at various fragments which are assumed to correspond to some 'overall mega-distribution', it might come in handy to assume the overall distribution has some acyclic presentation - then there's always a(t least one) topo ordering available to be invoked.

[-]Oliver Sourbut2y30

Oh yeah, I don't know how common it is, but when manipulating graphs, if there's a topo order, I seem to strongly prefer visualising things with that order respected on the page (vertically or horizontally). So your images committed a few minor crimes according to that aesthetic. I can also imagine that some other aesthetics would strongly prefer writing things the way you did though, e.g. with . (My preference would put $M$ and $N$ slightly lower, as you did with the $M$ , $X_{i}$ graph.)

[-]XelaP4mo30

I think you have an indexing typo in the section on the general re-rooting rule.

Your picture has a "linear diagram" (that's not your term, it's mine) rooted at X_i, with variables from X_1 to X_n. You then say that this expresses the factorization P(X) = (\prod_{i \le k} P(X_{i-1} | X_i) P(X_k) \prod_{k \le i \le n-1} P(X_{i+1} | X_i)

This looks to me like the factorization of a linear diagram rooted at X_k, with the index i running over everything to the left and then to the right of X_k.

Secondly, right after that you say that the approximate rerooting theorem states that if the KL divergence of that expression is true for any i, then it is true for all i. This has the same problem - i is a bound variable, so I think you mean that if the bound is true for any k, then it is true for all k.

You should either change the two pictures to have the root variable be labeled X_k instead, or you can change the text in that section (including the mathematical expressions) to swap i with k.

[-]Lorxus10mo30

We’ll refer to these as “Bookkeeping Rules”, since they feel pretty minor if you’re already comfortable working with Bayes nets. Some examples:
We can always add an arrow to a diagram (assuming it doesn’t introduce a loop), and the approximation will get no worse.

Here's something that's kept bothering me on and off for the last few months: This graphical rule immediately breaks Markov equivalence. Specifically, two DAGs are Markov-equivalent only if they share an (undirected) skeleton. (Lemma 6.1 at the link.)

If the major/only thing we care about here regarding latential Bayes nets is that our Grand Joint Distribution factorize over (that is, satisfy) our DAG $G$ (and all of the DAGs we can get from it by applying the rules here), then by Thm 6.2 in the link above, $P$ is also globally/locally Markov wrt $G$ . This holds even when $P [X_{G}] > 0$ is not guaranteed for some of the possible joint states in $X_{G}$ , unlike Hammersley-Clifford would require.

That in turn means that (Def 6.5) there's some distributions $P$ can be such that $P [X_{G}]$ factors over $G$ , but not $G^{'} = G + a n o n l o o p y e x t r a a r r o w$ (where $G^{'}$ trivially has the same vertices as $G$ does); specifically, because $G, G^{'}$ don't (quite) share a skeleton, they can't be Markov-equivalent, and because they aren't Markov-equivalent, $P$ no longer needs to be (locally/globally) Markov wrt $G^{'}$ (and in fact there must exist some $P$ which explicitly break this), and because of that, such $P$ need not factor over $G^{'}$ . Which I claim we should not want here, because (as always) we care primarily about preserving which joint probability distributions factorize over/satisfy which DAGs, and of course we probably don't get to pick whether our $P$ is one of the ones where that break in the chain of logic matters.

[-]DanielFilan10mo84

A way I'd phrase John's sibling comment, at least for the exact case: adding arrows to a DAG increases the set of probability distributions it can represent. This is because the fundamental rule of a Bayes net is that d-separation has to imply conditional independence - but you can have conditional independences in a distribution that aren't represented by a network. When you add arrows, you can remove instances of d-separation, but you can't add any (because nodes are d-separated when all paths between them satisfy some property, and (a) adding arrows can only increase the number of paths you have to worry about and (b) if you look at the definition of d-separation the relevant properties for paths get harder to satisfy when you have more arrows). Therefore, the more arrows a graph G has, the fewer constraints distribution P has to satisfy for P to be represented by G.

[-]johnswentworth10mo33

Proof that the quoted bookkeeping rule works, for the exact case:

The original DAG asserts $P [X] = \prod_{i} P [X_{i} | X_{p a^{G} (i)}]$
If $G^{'}$ just adds an edge from $j$ to $k$ , then $G^{'}$ says $P [X] = P [X_{k} | X_{p a^{G} (k)}, X_{j}] \prod_{i \neq k} P [X_{i} | X_{p a^{G} (i)}]$
The original DAG's assertion $P [X] = \prod_{i} P [X_{i} | X_{p a^{G} (i)}]$ also implies $P [X_{k} | X_{p a^{G} (k)}, X_{j}] = P [X_{k} | X_{p a^{G} (k)}]$ , and therefore implies $G^{'}$ 's assertion $P [X] = P [X_{k} | X_{p a^{G} (k)}, X_{j}] \prod_{i \neq k} P [X_{i} | X_{p a^{G} (i)}]$ .

The approximate case then follows by the new-and-improved Bookkeeping Theorem.

Not sure where the disconnect/confusion is.

[-]Lorxus10mo30

Let me see if I've understood point 3 correctly here. (I am not convinced I have actually found a flaw, I'm just trying to reconcile two things in my head here that look to conflict, so I can write down a clean definition elsewhere of something that matters to me.)

factors over $G$ . In $G$ , $X_{j}, X_{k}$ were conditionally independent of each other, given $X_{p a^{G} (k)}$ . Because $P$ factors over $G$ and because in $G$ , $X_{j}, X_{k}$ were conditionally independent of each other, given $X_{p a^{G} (k)}$ , we can very straightforwardly show that $P$ factors over $G^{'}$ , too. This is the stuff you said above, right?

But if we go the other direction, assuming that some arbitrary $P^{'}$ factors over $G^{'}$ , I don't think that we can then still derive that $P^{'}$ factors over $G$ in full generality, which was what worried me. But that break of symmetry (and thus lack of equivalence) is... genuinely probably fine, actually - there's no rule for arbitrarily deleting arrows, after all.

That's cleared up my confusion/worries, thanks!

[-]Oliver Sourbut2y30

I might be missing something, but I don't see where is actually used in the worked example.

It seems that there's a consistent topo order between the $M$ and $N$ diagrams, so we Frankenstitch them. Then we draw an edge from $N$ to $M$ and reorder (bookkeep). Then we Frankenstein the $M$ diagrams and the resulting diagram again. Then we collect the $X_{i}$ together (bookkeep). Where's $M \leftarrow X \to N$ used?

[-]johnswentworth2y30

We need it for the stitching rule; otherwise there could be weird three-variable interactions (e.g. one thing is an xor of two other things) which mess up the stitch.

[-]Oliver Sourbut2y30

But this same move can alternatively be done with the Frankenstein rule, right? (I might be missing something.) But Frankenstein has no such additional requirement, as stated. If I'm not missing something, I think Frankenstein might be invalid as stated (like maybe it needs an analogous extra condition). Haven't thought this through yet.

i.e. I think either

I'm missing something
Frankenstein is invalid
You don't need

[-]Oliver Sourbut2y*30

Yeah, thinking slightly aloud, I tentatively think Frankenstein needs an extra condition like the blanket stitch condition... something which enforces the choice of topo ordering to be within the right class of topo orderings? That's what the chain does - it means we can assign orderings $M, X_{¯ i}, X_{i}, N$ or $M, X_{i}, X_{¯ i}, N$ , but not e.g. $M, X_{¯ i}, N, X_{i}$ , even though that order is consistent with both of the other original graphs.

If I get some time I'll return to this and think harder but I can't guarantee it.

ETA I did spend a bit more time, and the below mostly resolves it: I was indeed missing something, and Frankenstein indeed needs an extra condition, but you do need $M \leftarrow X \to N$ .

[-]Oliver Sourbut2y132

I had another look at this with a fresh brain and it was clearer what was happening.

TL;DR: It was both of 'I'm missing something', and a little bit 'Frankenstein is invalid' (it needs an extra condition which is sort of implicit in the post). As I guessed, with a little extra bookkeeping, we don't need Stitching for the end-to-end proof. I'm also fairly confident Frankenstein subsumes Stitching in the general case. A 'deductive system' lens makes this all clearer (for me).

My Frankenstein mistake

The key invalid move I was making when I said

But this same move can alternatively be done with the Frankenstein rule, right?

is that Frankenstein requires all graphs to be over the same set of variables. This is kind of implicit in the post, but I don't see it spelled out. I was applying it to an graph ( $N$ absent) and an $(X_{¯ i}, X_{i}, N)$ graph ( $M$ absent). No can do!

Skipping Stitch in the end-to-end proof

I was right though, Frankenstein can be applied. But we first have to do 'Node Introduction' and 'Expansion' on the graphs to make them compatible (these extra bookkeeping rules are detailed further below.)

So, to get myself in a position to apply Frankenstein on those graphs, I have to first (1) introduce $M$ to the second graph (with an arrow from each of $N$ , $X_{i}$ , and $X_{¯ i}$ ), and (2) expand the 'blanket' graph $M \leftarrow X \to N$ (choosing $X_{¯ i} \to X_{i}$ to maintain topological consistency). Then (3) we Frankenstein them, which leaves $N$ dangling, as we wanted.

Next, (4) I have to introduce $N$ to the first graph (again with an arrow from each of $M$ , $X_{i}$ , and $X_{¯ i}$ ). I also have a topological ordering issue with the first Frankenstein, so (5) I reorder $M$ to the top by bookkeeping. Now (6) I can Frankenstein those, to sever the $X_{¯ i} \to X_{i}$ as hoped.

But now we've performed exactly the combo that Stitch was performing in the original proof. The rest of the proof proceeds as before (and we don't need Stitch).

More bookkeeping rules

These are both useful for 'expansive' stuff which is growing the set of variables from some smaller seed. The original post mentions 'arrow introduction' but nothing explicitly about nodes. I got these by thinking about these charts as a kind of 'deductive system'.

Node introduction

A graph without all variables is making a claim about the distribution with those other variables marginalised out.

We can always introduce new variables - but we can't (by default) assume anything about their independences. It's sound (safe) to assume they're dependent on everything else - i.e. they receive an incoming arrow from everywhere. If we know more than that (regarding dependencies), it's expressed as absence of one or another arrow.

e.g. a graph with $A, B, C$ is making a claim about $P (A, B, C)$ . If there's also a $D$ , we haven't learned anything about its independences. But we can introduce it, as long as it has arrows $A \to D$ , $B \to D$ , and $C \to D$ .

Node expansion aka un-combine

A graph with combined nodes is making a claim about the distribution as expressed with those variables appearing jointly. There's nothing expressed about their internal relationship.

We can always expand them out - but we can't (by default) assume anything about their independences. It's sound to expand and spell them out in any fully-connected sub-DAG - i.e. they have to be internally fully dependent. We also have to connect every incoming and outgoing edge to every expanded node i.e. if there's a dependency between the combination and something else, there's a dependency between each expanded node and that same thing.

e.g. a graph with $X, Y, Z$ is making a claim about $P (X, Y, Z)$ . If $Y$ is actually several variables, we can expand them out, as long as we respect all possible interactions that the original graph might have expressed.

Deductive system

I think what we have on our hands is a 'deductive system' or maybe grandiosely a 'logic'. The semantic is actual distributions and divergences. The syntax is graphs (with divergence annotation).

An atomic proposition is a graph $G$ together with a divergence annotation $ϵ$ , which we can write $G (ϵ)$ .

Semantically, that's when the 'true distribution satisfies $G$ up to $ϵ$ KL divergence' as you described^[1]. Crucially, some variables might not be in the graph. In that case, the distributions in the relevant divergence expression are marginalised over the missing variables. This means that the semantic is always under-determined, because we can always introduce new variables (which are allowed to depend on other variables however they like, being unconstrained by the graph).

Then we're interested in sound deductive rules like

$G (ϵ_{G}) ⟹ H (ϵ_{H})$

Syntactically that is 'when we have deduced $G (ϵ_{G})$ we can deduce $H (ϵ_{H})$ '. That's sound if, for any distribution $P$ satisfying $G (ϵ_{G})$ we also have $P$ satisfying $H (ϵ_{H})$ .

Gesture at general Frankenstitch rule

More generally, I'm reasonably sure Stitch is secretly just multiple applications of Frankenstein, as in the example above. The tricky bit I haven't strictly worked through is when there's interleaving of variables on either side of the blanket in the overall topological ordering.

A rough HANDWAVE proof sketch, similar in structure to the example above:

Expand the $X \leftarrow Y \to Z$ blanket graph
- The arrows internal to $X$ , $Y$ , and $Z$ need to be complete
- We can always choose a complete graph consistent with the $X$ , $Y$ , and $Z$ parts of the original graphs (otherwise there wouldn't be an overall consistent topology)
- Notice that the connections $X \leftarrow Y$ are all $Y$ to all $X$ , which is not necessarily consistent with the original $X Y$ graph
  - and similarly for the $Y Z$ arrows
  - (there could be $X \to Y$ arrows in the original)
Introduce $Z$ to the $X Y$ graph (and vice versa)
- The newly-introduced nodes are necessarily 'at the bottom' (with arrows from everything else)
- We can always choose internal connections for the introduced $Z$ s consistent with the original $Y Z$ graph
Notice that the connections $X \to Z$ and $Y \to Z$ in the augmented $X Y$ graph all keep $Z$ at the bottom, which is not necessarily consistent with the original $Y Z$ graph (and vice versa)
- But this is consistent with the Expanded blanket graph
We 'zip from the bottom' with successive bookkeeping and Frankensteins
- THIS IS WHERE THE HANDWAVE HAPPENS
- Just like in the example above, where we got the $N$ sorted out and then moved the introduced $M$ to the 'top' in preparation to Frankenstein in the $M$ graph, I think there should always be enough connections between the introduced nodes to 'move them up' as needed for the stitch to proceed

I'm not likely to bother proving this strictly, since Stitch is independently valid (though it'd be nice to have a more parsimonious arsenal of 'basic moves'). I'm sharing this mainly because I think Expansion and Node Introduction are of independent relevance.

More formally, $G (ϵ)$ over variables $X$ is satisfied by distribution $P$ when $D_{K L} (P (X) | | \prod_{i} P (X_{i} | X_{p a^{G} (i)})) \leq ϵ$ . (This assumes some assignment of variables in $G$ to variables in $P$ .) ↩︎

[-]Oliver Sourbut2y*50

Perhaps more importantly, I think with Node Introduction we really don't need after all?

With Node Introduction and some bookkeeping, we can get the $N$ and $M$ graphs topologically compatible, and Frankenstein them. We can't get as neat a merge as if we also had $M \leftarrow X \to N$ - in particular, we can't get rid of the arrow $M \to N$ . But that's fine, we were about to draw that arrow in anyway for the next step!

Is something invalid here? Flagging confusion. This is a slightly more substantial claim than the original proof makes, since it assumes strictly less. Downstream, I think it makes the Resample unnecessary.

ETA: it's cleared up below - there's an invalid Reorder here (it removes a v-structure).

[-]johnswentworth2y51

I think one of the reorder steps on the bottom line is invalid.

Stock counterexample:

Let and $X_{¯ i}$ each be strings of bits. The zeroth bit of each is equal (i.e. $X_{i}^{0} = X_{¯ i}^{0}$ ); the rest are independent.
$M$ is another bitstring with zeroth bit equal to the zeroth bit of $X_{i}$ , and all other bits independent of $X$ .
$N$ is a bitstring with zeroth bit equal to the zeroth bit of $X_{i}$ , with the rest of the bits given by:
- odd-numbered bits are the odd-numbered independent bits of $M$ xor independent bits of $X_{i}$
- even-numbered bits are the even-numbered independent bits of $M$ xor independent bits of $X_{¯ i}$

Then the starting diagrams in your proof are all satisfied, but the final diagram is not.

The step which breaks for this counterexample is the first reorder step on the bottom line.

[-]Oliver Sourbut2y50

Mhm, OK I think I see. But appear to me to make a complete subgraph, and all I did was redirect the $N \to M$ . I confess I am mildly confused by the 'reorder complete subgraph' bookkeeping rule. It should apply to the $A \to B$ in $A \to B \leftarrow C$ , right? But then I'd be able to deduce $A \leftarrow B \leftarrow C$ which is strictly different. So it must mean something other than what I'm taking it to mean.

Maybe need to go back and stare at the semantics for a bit. (But this syntactic view with motifs and transformations is much nicer!)

[-]johnswentworth2y50

Oh you're right, the rule about reordering complete subgraphs is missing some constraints. That's a mistake on my part.

Thinking about it for ~60 seconds: when reordering a complete subgraph, arrows going out of the subgraph stay the same, but if there's arrows going in then we may need to introduce new arrows between (former) spouses.

[-]Oliver Sourbut2y*50

Aha. Preserving v-structures (colliders like ) is necessary and sufficient for equivalence^[1]. So when rearranging fully-connected subgraphs, certainly we can't do it (cost-free) if it introduces or removes any v-structures.

Plausibly if we're willing to weaken by adding in additional arrows, there might be other sound ways to reorder fully-connected subgraphs - but they'd be non-invertible. Haven't thought about that.

Verma & Pearl, Equivalence and Synthesis of Causal Models 1990 ↩︎

[-]johnswentworth2y50

Either that's wrong or I'm misinterpreting it, because a fully-connected DAG should be equivalent to any other fully-connected DAG but they all have different v-structures.

[-]Oliver Sourbut2y*52

Mmm, I misinterpreted at first. It's only a v-structure if and $Z$ are not connected. So this is a property which needs to be maintained effectively 'at the boundary' of the fully-connected cluster which we're rewriting. I think that tallies with everything else, right?

ETA: both of our good proofs respect this rule; the first Reorder in my bad proof indeed violates it. I think this criterion is basically the generalised and corrected version of the fully-connected bookkeeping rule described in this post. I imagine if I/someone worked through it, this would clarify whether my handwave proof of Frankenstein $⟹$ Stitch is right or not.

[-]Oliver Sourbut2y10

Unironically, I think it's worth anyone interested skimming that Verma & Pearl paper for the pictures :) especially fig 2

[-]Oliver Sourbut2y10

That's concerning. It would appear to make both our proofs invalid.

But I think your earlier statement about incoming vs outgoing arrows makes sense. Maybe Verma & Pearl were asking for some other kind of equivalence? Grr, back to the semantics I suppose.

[This comment is no longer endorsed by its author]Reply

[-]Oliver Sourbut2y30

(I said Frankenstitch advisedly, I think they're kinda the same rule, but in particular in this case it seems either rule does the job.)

[-]David Reber2yΩ230

Could you clarify how this relates to e.g. the PC (Peter-Clark) or FCI (Fast Causal Inference) algorithms for causal structure learning?

Like, are you making different assumptions (than e.g. minimality, faithfulness, etc)?

[-]johnswentworth2y52

First, there's a different type signature. PC or FCI-style causal structure learning typically takes in a bunch of conditional independence tests (or a function for performing conditional independence tests, or a pile of data on which to perform conditional independence tests, etc) and spits out a DAG. For this post, it's DAGs in, DAGs out.

Second, a different use-case. The theorems in this post all say something like "if the distribution (approximately) factors according to <some DAGs>, then it also (approximately) factors according to <some other DAGs>". This use-case doesn't directly assume or prove anything about minimality; none of the theorems say that the distribution can't also satisfy some DAG with fewer edges. Likewise, we neither assume nor prove anything about faithfulness. (Though one could perhaps use these theorems to prove minimality and/or faithfulness in particular cases, in which case the preconditions for the proof would be that the distribution does/doesn't satisfy some DAGs.)

If we wanted to use these theorems for causal structure learning, at a high level the method would look something like:

First, find some DAGs the distribution satisfies via some other method(s).
Then, use the theorems here to derive a stronger DAG which must be satisfied.

For instance, we could imagine that two groups of scientists do a bunch of experiments on the same system. One group finds that the system is well-modelled by the left DAG at the top of the Frankenstein Rule section of this post, the other group finds that the system is well-modelled by the right DAG. Then, we could try to Frankenstein those two DAGs together in a way which keeps as few edges as possible.

[-]David Reber2y52

The theorems in this post all say something like "if the distribution (approximately) factors according to <some DAGs>, then it also (approximately) factors according to <some other DAGs>"

So one motivating research question might be phrased as "Probability distributions have an equivalence class of Bayes nets / causal diagrams which are all compatible. But what is the structure within a given equivalence class? In particular, if we have a representative Bayes net of an equivalence class, how might we algorithmically generate other Bayes nets in that equivlance class?"

[-]David Reber2y40

also, it appears that the two diagrams in the Frankenstein Rule section differ in their d-separation of (x_1 \indep x_4 | x_5) (which doesn't hold in the the left), so these are not actually equivalent (we can't have an underlying distribution satisfy both of these diagrams)

[-]johnswentworth2y72

Oh, we can totally have an underlying distribution satisfy both of these diagrams. The key is that, while the right diagram asserts (x_1 \indep x_4 | x_5), the left does not say that x_1 can't be independent of x_4 given x_5. Remember the interpretation: an underlying distribution satisfies a DAG if-and-only-if the distribution factors over that DAG. We neither assume nor prove minimality; the DAG does not need to be minimal.

So, for instance, a distribution in which all five variables are unconditionally independent would satisfy every diagram over those variables.

You are right that the two diagrams are not equivalent (i.e. there exist distributions which satisfy either one but not the other), and we're not claiming they're equivalent. We're just saying "assume that some distribution satisfies both of these two diagrams; what other diagrams must the distribution then satisfy?".