2 - Structure of the causal model

Every result carries its provenance:

• [standard] in the literature and cited
• [ours] derived here and proved
• [assumption] imposed to restrict the model class, owed a discharge later
• [conjecture] believed, not proved, and a result if proved.

Numbered citations [n] resolve in References & related works.

---

Standing assumptions

Two assumptions, held throughout the note.

Positivity [assumption] — every CPT entry is strictly positive, for every and every family configuration. A zero entry sends to and the coefficient column below ceases to be a real vector, so the objects of this note are defined on positive models and on no others.

Parent-minimality [assumption] — no declared edge is vacuous: for every edge of , the kernel genuinely varies in . Without it the structure recovered below is the model’s support rather than the modeller’s declaration.

---

Normalisation is global

Def. 3 requires each CPT to be normalised column by column: one equation per node per parent configuration. What the compilation needs is that the joint they generate is normalised over the whole configuration space: one equation, over terms. The second does not follow from the first alone, and the missing ingredient is acyclicity — which enters through a labelling.

Lemma 1 — a DAG admits a topological order [standard] [1,2]

Let be a finite directed acyclic graph. Then its nodes can be labelled so that for every : every edge points from a lower index to a higher one.

Proof. A finite acyclic graph has a node with no outgoing edge, since following edges forward from any start cannot revisit a node without closing a cycle. Label such a node and delete it; the remainder is acyclic on nodes, so it has such a labelling by induction, and prefixing it leaves the property intact because has no outgoing edge and so appears in no parent set.

Convention

Lemma 1 is applied once and then never mentioned again: every later result assumes the nodes are indexed along a topological order, so that and, in particular, This is without loss of generality, since Lemma 1 says such a labelling always exists, and it is what lets the proofs below telescope instead of re-deriving an ordering each time. The order is not unique; nothing below depends on which one is chosen.

Theorem 1 — local normalisation gives [standard] [3,4]

Let the kernels of a DAG be locally normalised, for every and every . Then the chain-rule joint is normalised over the whole configuration space:

Proof. Sum over last:

The bracket is one by local normalisation: by the convention is a configuration of , so the outer sum holds it fixed and it does not involve . What remains is the same expression on , which inherits both the ordering and local normalisation, so induction closes it, with being local normalisation itself.

This is the note’s most-used result: every partition function computed later is read against it. Note where the work went — the convention did it. Without a topological order there is no last variable whose parents all lie elsewhere, and the telescoping has nothing to start on.

---

From a Bayesian network to an energy

Prop. 1 — BN-to-energy equivalence [standard] [5,6]

Let be a Bayesian network with chain-rule joint and define the energy per node and total Then

Proof. By positivity every is finite, so is real-valued on all of . Then and give and then by Theorem 1.

Result could be extended by taking the convention , assigning probability zero with an infinite energy barrier. This will be treated in a later note as a hardware constraint for the mode

The Boltzmann form is the joint: the same numbers, read once as a product of conditionals and once as an energy landscape. The log-linear half of this is standard; the exact normalisation is stated as a numbered result nowhere we could find, and follows from Theorem 1 in one line.

What certifies, and what it does not [ours]

For a general energy model is a sum over configurations and intractable. For a BN-derived one it is known analytically, so every compilation ships with a free exact check: a correctly compiled unconditioned model has . It certifies normalisation of the compiled measure and nothing further — it is one scalar equation obtained by summing the local ones, and models that differ in every structural respect share it.

---

Decomposing an energy into coefficients

Prop. 1 produces an energy function. To say what a machine can carry, that function has to be resolved into numbers. Two features of the resolution are worth separating before it is done.

The first is that it has nothing to do with graphs: the decomposition is a fact about functions on a binary cube, so it is stated that way and specialised afterwards.

The second is that the graph will then enter in exactly one way. is a sum of terms, one per family, and a term depends only on the variables of its own family — so each term resolves on its own cube , and the graph contributes nothing but the list of families. The number of terms is the number of families; the variables a term can couple are its child–parent and parent–parent pairs, which are the edges of (Def. 4). No path, depth, ancestor set or collider is consulted anywhere below. That is why the bookkeeping is per family rather than per edge. [ours]

For a real function on a binary cube write for the finite difference in the coordinate , all others held fixed. Recall (Def. 1bis) for the configuration with exactly on , so is the all-zero reference.

Theorem 2 — the monomial basis and coefficient recovery [standard] [7,8,9,10]

Let be a finite index set and . Then has a unique multilinear expansion , and its coefficients are recovered from the values of by Moreover whenever does not depend on some .

Proof. The monomials are linearly independent and the cube has points, so they are a basis of the functions on it; existence and uniqueness follow.

A monomial satisfies if and only if , so . Substituting into the alternating sum and exchanging the order of summation, the inner sum evaluated by letting range over the subsets of , giving , which is for and otherwise.

For the operator form, annihilates every monomial not containing and strips from the rest, so . The operators commute, so iterating over in any order gives , and evaluating at kills every term with .

For the last claim, if does not depend on then identically; for apply that first, which the freedom of order permits, and the whole nested difference vanishes.

Example. On with , , , : , , , and . The order-two coefficient is what the two first differences fail to account for — it is nonzero exactly when the effect of flipping depends on .

Applying Theorem 2 at two index sets gives the two objects the rest of the note works with.

Cor. 2.1 — the two decompositions [ours]

1. (Totals) At on : the totals , , the unique coefficients of the compiled energy. These are the numbers a machine is given.
2. (Columns) At on : for each node a column , .
3. (Support property) Extending each column by zero to all ,

Proof. Clauses 1 and 2 are Theorem 2 at the two index sets. For clause 3, if then does not depend on , so the last claim of Theorem 2 applies to every .

The columns are the finer object and the totals the coarser one. What relates them is the whole of what compilation does arithmetically.

Prop. 2 — the totals are the column sums [ours]

For every ,

Proof. The map is linear in , and by Prop. 1. Applying it to both sides gives over all , and by the support property only the families containing contribute.

Cost. Each column costs evaluations of one CPT, so the whole compilation costs — set by the widest family, never by . The totals are assembled by summing per-family contributions, not by enumerating states.

---

The tagged family

Cor. 2.1 gives one column per node. Keeping the node index attached to its column, rather than discarding it once the sum of Prop. 2 is taken, is the whole of what follows.

Definition — the tagged family. For , the tagged family is the indexed collection one column per node index, retained even when the column is constant.

Two properties of the object before the proposition. A column is indivisible, because it comes from one term: every entry of is an iterated difference of the single function , and there is no finer split inside it. And the index is not bookkeeping: a node whose mechanism does not vary at all has a column supported on alone, so it is invisible in the coefficients and visible only in its index.

Prop. 3 — the tagged family determines the model [ours]

Under the standing assumptions:

1. (Column inversion) each column determines its own mechanism,
2. (Structure recovery) the parent set is the column’s support with the index removed,
3. (Faithfulness) is injective: the tagged family determines both and ;
4. (Dimension) the counts agree — for binary variables has free parameters, and has reals subject to normalisation equations.

Proof. 1. By Theorem 2 the expansion of on is unique with coefficients , so evaluating that expansion returns the function; positivity makes it real-valued, and exponentiating returns the entry.

2. By uniqueness, depends on if and only if some has . So lies in the column’s support if and only if the kernel varies in , which under parent-minimality holds if and only if is a parent of . The index supplies , removed to leave the parents.

3. If two tagged families agree then, index by index, the supports agree, so the parent sets agree by 2 and the graphs agree; and the columns agree, so the mechanisms agree by 1.

4. A binary child has one free entry per parent configuration, giving . Its column has reals, and local normalisation imposes one equation per parent configuration. The difference is the same count.

Example — orientation lives in the index. Take the chain , the reversed chain and the fork , each carrying the CPTs one common joint induces on it. All three have a column supported on and a column supported on , with the same values. What differs is which node each column is indexed by: in the chain the column is ‘s, in the fork it is ‘s. The index is the head of the mechanism, so reorienting an edge necessarily moves it. The three models are separated by their indices and by nothing else — no arithmetic on coefficient values distinguishes them.

What the topological convention already supplies, and what it does not

Under the convention : the child of a family is its largest index. So a topological labelling carries the head half of what the index does, and to that extent the index is redundant.

It does not carry the other half. Recovering needs to know which subsets are families, and that is what the columns supply and the totals do not: the cliques of are not marked as families, and carries parent–parent edges that are not edges of , so orienting every moral edge from lower to higher index would invent edges that were never there. A topological order together with the family decomposition does recover ; a topological order together with the moral graph does not. And since many DAGs share a topological order, the labelling is strictly weaker than the per-column index.

---

What a coefficient is

Theorem 2 says how to compute a coefficient. Composing it with says what one is.

Prop. 4 — a coefficient is an iterated log-cross-ratio [ours]

For every and every ,

Proof. The first equality is Theorem 2 applied to the term. The second moves an alternating sum of logarithms inside a single logarithm of an alternating product.

The formula reads better regrouped. Fix a family, take two of its coordinates , hold the others at the reference, and write for the value of at , . The alternating sum at then splits into two differences:

An order-one coefficient is one such effect, . An order-two coefficient is the difference between that same effect measured at two levels of a second variable. In probabilities, writing for the CPT entry,

a log-ratio and a log-ratio-of-ratios. At order the nesting continues over entries, so there is no pair of states the number can be attributed to.

Every one of those differences was taken against . That choice is not innocent, and what it costs is a result of its own.

Prop. 5 — the coefficients depend on the reference [ours]

Let have coefficients , fix , and let be with the two values of coordinate interchanged, . Then the coefficients of are

Proof. Substitute into . A term with is untouched. A term with becomes

Collect the coefficient of . If it receives from the term , and from the first piece of the term . If it receives only , from the second piece of the term . Uniqueness of the expansion (Theorem 2) makes the collected coefficients the coefficients of .

Renaming the two values of one variable is a symmetry of the energy and of the distribution — it relabels a value and changes nothing measurable. Prop. 5 says the coefficients do not respect it, and says exactly how they fail to:

• a coefficient containing merely flips sign, which is what one would expect of a renaming;
• a coefficient not containing absorbs the coefficient one order above it, . Relabelling one variable does not leave the others alone — it pushes higher-order structure down into lower orders.

Two consequences. The constant is not spared: , so even the energy offset moves. And the coefficient on the full index set contains every variable, so it is the one quantity here that no relabelling can do more than negate; everything below it mixes.

The mixing is a property of the basis, not of the information, and it can be removed at a price worth knowing.

Set , so that and the variables take values . The monomials become the parity functions , and these are orthonormal for the uniform measure on the cube,

so the expansion inverts by projection rather than by difference:

A binary coefficient is a nested difference over the states below , with every other coordinate pinned at one corner. A spin coefficient is an average of over all states, weighted by the parity of . There is no reference cell because every cell is used.

That is exactly what undoes Prop. 5. Relabelling coordinate is , which sends when and leaves untouched otherwise, so

A pure sign change, with no mixing anywhere. Every is invariant, not only the one at top order, and is the mean energy over the cube rather than the value at an arbitrary corner. Prop. 4’s reading survives in altered form: is still minus a log of a cross-product of CPT entries, but taken over the whole table with fractional exponents instead of over a sub-cube with signs.

The price is sparsity, which is what this note has been trading on throughout. The change of variables is triangular, and it spreads: so a single binary pair-monomial becomes four spin coefficients. Maximal order is preserved, and so is which variables a column involves — Prop. 3 is therefore untouched, since a term depends on exactly when it depends on . What is not preserved is the sparsity pattern inside a family, and the cost of one coefficient rises from evaluations to all . The choice between the two bases is a trade, not a repair, and this note stays in the binary one because the compilation’s economy lives there.

---

Where the totals live

Prop. 6 — the compiled model is an MRF over the moral graph [standard] [3,4,12]

Let have energy with totals . Then:

1. (Support) every occupied monomial is a clique of the moral graph — implies is a clique of ;
2. (Factorisation) factorises over the cliques of , with maximal interaction order .

Proof. 1. By the support property requires for some ; every family is a clique of by Def. 4, and a subset of a clique is a clique.

2. Exponentiating the per-family decomposition,

a product of nonnegative potentials each carried by a family, which is a clique by clause 1 — a clique factorisation over , so is Markov with respect to . The maximal order is the support property’s.

So the index set of the totals is the clique complex generated by the families, and moralisation is not a rule the compiler follows but a consequence of the terms being local to families. Everything that survives compilation lives on that complex; nothing else can be written.

What the count does not settle is the gap between its two sides. The monomials receiving more than one contribution are precisely those in more than one family, and the next section is about what happens to them.

---

The chain

The three objects are the same energy written three ways, and the writing shows what each step costs.

At the model the energy is a sum over nodes, one term per family, which is what the factorisation buys

Resolving each term on its own cube turns that into a double sum — over nodes, and within each node over its own coefficients

Carrying out the inner accumulation collapses the two sums into one, over coefficients alone

The node index is gone from the last line, and that is the loss made typographic: the first two forms know which node contributed what, the third does not. As a chain of objects,

The first arrow is faithful, by Prop. 3. The second is the column sum. The third is not established.