I think a subpartition of S can be thought of as a partial function on S, or equivalently, a variable on S that has the possible value "Null"/"undefined".
That's right. A partial function can be thought of as a subset (of its domain) and a total function on that subset. And a (total) function can be thought of as a partition (of its domain): the parts are the inverse images of each point in the function's image.
We now want to extend our notion of orthogonality to conditional orthogonality. This will take a bit of work. In particular, we will have to first extend our notions of partition generation and history to be defined on partitions of subsets of S.
4.1 Generating a Subpartition
Definition 20 (subpartition). A subpartition of a set S is a partition of a subset of S. Let SubPart(S)=⋃E⊆SPart(E) denote the set of all subpartitions of S.
Definition 21 (domain). The domain of a subpartition X of S, written dom(X), is the unique E⊆S such that X∈Part(E).
Definition 22 (restricted partitions). Given sets S and E and a partition X of S, let X|E denote the partition of S∩E given by X|E={[e]X∩E∣e∈E}.
Definition 23 (generating a subpartition). Given a finite factored set F=(S,B), and X∈SubPart(S), and a C⊆B, we say C generates X (in F), written C⊢FX, if χFC(x,dom(X))=x for all x∈X.
Note that this definition clearly coincides with Definition 16, when X has domain S. Despite the similarity of the definitions, the idea of generating a subpartition is a bit more complicated than the idea of generating a partition of S.
To see this, consider the following list of equivalent definitions. Notice that while the first five directly mirror their counterparts in Proposition 10, the last two (and especially the last one) require an extra condition.
Proposition 20. Let F=(S,B) be a finite factored set, let X∈SubPart(S) be a subpartition of S, let E=dom(X) be the domain of X, and let C be a subset of B. The following are equivalent.
Proof. The equivalence of conditions 1 and 2 is by definition.
The equivalence of conditions 2 and 3 follows directly from the fact that χFC(s,s)=s for all s∈x, so χFC(x,E)⊇χFC(x,x)⊇x.
To see that conditions 3 and 4 are equivalent, observe that since E=⋃y∈Xy, χFC(x,E)=⋃y∈XχFC(x,y). Thus, if χFC(x,E)⊆x, χFC(x,y)⊆x for all y∈X, and conversely if χFC(x,y)⊆x for all y∈X, then χFC(x,E)⊆x.
To see that condition 3 is equivalent to condition 5, observe that if condition 5 holds, then for all x∈X, we have χFC(s,t)∈[s]X=x for all s∈x and t∈E. Thus χFC(x,E)⊆x. Conversely, if condition 3 holds, χFC(s,t)∈χFC([s]X,E)⊆[s]X for all s,t∈E.
Condition 6 is clearly a trivial restatement of condition 5.
To see that conditions 6 and 7 are equivalent, observe that if condition 6 holds, then χFC(s,t)∈E for all s,t∈E, so χFC(E,E)⊆E, so χFC(E,E)=E. Further, if s,t∈E satisfy s∼⋁S(C)|Et, then s∼ct for all c∈C, so χFC(s,t)=t, so t=χFC(s,t)∼Xs. Thus X≤E⋁S(C)|E.
Conversely, if condition 7 holds, then for all s,t∈E, we have χFC(s,t)∼⋁S(C)s, so χFC(s,t)∼⋁S(C)|Es, and thus χFC(s,t)∼Xs. Further, clearly χFC(E,E)=E implies χFC(s,t)∈E for all s,t∈E. □
The first half of condition 7 in the above proposition can be thought of as saying that the values of factors in C are sufficient to distinguish between the parts of X.
The second half can be thought of as saying that no factors in C become entangled with any factors outside of C when conditioning on E. This second half is actually necessary (for example) to ensure that the set of all C that generate X is closed under intersection. As such, we will need this fact in order to extend our notion of history to arbitrary subpartitions.
Proposition 21. Let F=(S,B) be a finite factored set, let C and D be subsets of B, let X,Y,Z∈SubPart(S) be subpartitions of S, and let dom(X)=dom(Y)=E.
Proof. The first 4 parts will use the equivalent definition from Proposition 20 that C⊢FX if and only if X≤S⋁S(C). 1 and 2 are immediate from this definition.
3 follows directly from Definition 23.
4 follows directly from the fact that ⋁S({})=IndS, and IndS|E=IndE so X≤E⋁S(C)|E if and only if X=IndE.
For part 5, we will use the equivalent definition from Proposition 20 that C⊢FX if and only if χFC(s,t)∈[s]X for all s,t∈E. Assume that for all s,t∈E, χFC(s,t)∈[s]X and χFD(s,t)∈[s]X. Thus, for all s,t∈E, χFC∩D(s,t)=χFC(χFD(s,t),t)∈[χFD(s,t)]X=[s]X. Similarly, for all s,t∈E, χFC∪D(s,t)=χFC(s,χFD(s,t))∈[s]X. Thus C∩D⊢FX and C∪D⊢FX.
For part 6, we use the definition that C⊢FX if and only if χFC(x,y)∈x for all x,y∈X. Clearly if X⊆Z, and χFC(x,y)∈x for all x,y∈Z, then χFC(x,y)∈x for all x,y∈X.
Note that while the set of C that generate an X∈Part(S) is closed under supersets, the set of C that generate an X∈SubPart(S) is merely closed under union.
Further note that part 6 of Proposition 21 uses the subset relation on subpartitions, which is a slightly unnatural relation.
4.2 History of a Subpartition
Definition 24 (history of a subpartition). Given a finite factored set F=(S,B) and a subpartition X∈SubPart(S), let hF(X) denote the smallest (according to the subset ordering) subset of B such that hF(X)⊢FX.
Proposition 22. Given a finite factored set F=(S,B), hF:SubPart(S)→P(B) is well-defined, and if X is a partition of S, this definition coincides with Definition 17.
Proof. Fix a finite factored set F=(S,B) and a subpartition X∈SubPart(S), and let hF(X) be the intersection of all C⊆B such that C⊢FX. It suffices to show that hF(X)⊢FX. Then hF(X) will clearly be the unique smallest (according to the subset ordering) subset of B such that hF(X)⊢FX. The fact that this definition coincides with Definition 17 if X∈Part(S) is clear.
Note that hF(X) is a finite intersection, since there are only finitely many subsets of B, and that hF(X) is a nonempty intersection since B⊢FX. Thus, we can express hF(X) as a (possibly empty) composition of finitely many binary intersections. By part 5 of Proposition 21, the intersection of two subsets that generate X also generates X. Thus hF(X)⊢FX.
We will now give five basic properties of the history of subpartitions, followed by two more properties that are less basic.
Proposition 23. Let F=(S,B) be a finite factored set, let X,Y,Z∈SubPart(S) be subpartitions of S, and let dom(X)=dom(Y)=E.
Proof. Parts 1, 3, and 4 are trivial consequences of Proposition 21, and part 5 is just a restatement of part 4 of Proposition 13.
For part 2, first observe that hF(X∨EY)⊇hF(X)∪hF(Y), by part 1 of Proposition 21. Thus it suffices to show that hF(X)∪hF(Y)⊇hF(X∨EY), by showing that hF(X)∪hF(Y)⊢FX∨EY.
We will use condition 7 in Proposition 20. Clearly
X≤E(⋁E(hF(X))|E)≤E(⋁S(hF(X)∪hF(Y))|E),and similarly,
Y≤E(⋁E(hF(Y))|E)≤E(⋁Se(hF(X)∪hF(Y))|E).Thus, X∨EY≤E(⋁S(hF(X)∪hF(Y))|E).
Next, we need to show that χFhF(X)∪hF(Y)(E,E)=E. Clearly E⊆χFhF(X)∪hF(Y)(E,E).
Let s and t be elements of E, and observe that χFhF(X)∪hF(Y)(s,t)=χFhF(X)(s,χFhF(Y)(s,t)). We have that χFhF(Y)(s,t)∈E, since χFhF(Y)(E,E)=E. Thus, we also have that χFhF(X)(s,χFhF(Y)(s,t))∈E, since χFhF(X)(E,E)=E. Thus, χFhF(X)∪hF(Y)(E,E)⊆E.
Thus we have that X∨EY≤E(⋁S(hF(X)∪hF(Y))|E) and χFhF(X)∪hF(Y)(E,E)=E. Thus, by condition 7 in Proposition 20, hF(X)∪hF(Y)⊢FX∨EY, so hF(X∨EY)=hF(X)∪hF(Y). □
Lemma 1. Let F=(S,B) be a finite factored set, and let X,Y∈Part(E) be subpartitions of S with the same domain. If hF(X)∩hF(Y)={}, then hF(X)=hF(X|y) for all y∈Y.
Proof. Let F=(S,B) be a finite factored set, let E⊆S, and let X,Y∈Part(E).
We start by showing that (B∖hF(X))⊢FY and (B∖hF(Y))⊢FX. Observe that χB∖hF(X)(E,E)=χhF(X)(E,E)=E. Further observe that B∖hF(X)⊇hF(Y), so ⋁S(B∖hF(X))≥S⋁S(hF(Y)), so (⋁S(B∖hF(X))|E)≥E(⋁S(hF(Y))|E)≥EY. Thus, (B∖hF(X))⊢FY. Symmetrically, (B∖hF(Y))⊢FX.
Fix some y∈Y. We start by showing that hF(X)⊇hF(X|y).
We have that χFB∖hF(X)(y,E)⊆y, so χFhF(X)(E,y)⊆y, so for all x∈X, we have χFhF(X)(x∩y,y)⊆y. We also have χFhF(X)(x∩y,y)⊆χFhF(X)(x,E)⊆x. Thus χFhF(X)(x∩y,y)⊆x∩y. Every element of X|y is of the form x∩y for some x∈X, so we have hF(X)⊢F(X|y), so hF(X)⊇hF(X|y).
Next, we need to show that hF(X)⊆hF(X|y). For this, it suffices to show that hF(X|y)⊢FX. Let s,t be arbitrary elements of E. It suffices to show that χFhF(X|y)(s,t)∈[s]X.
First, observe that since (B∖hF(Y))⊇hF(X)⊇hF(X|y), we have that χFhF(X|y)(s,t)=χFB∖hF(Y)(χFhF(X|y)(s,t),t).
Let r be an arbitrary element of y. We thus have:
χFhF(X|y)(s,t)=χFB∖hF(Y)(χFhF(X|y)(s,t),t)=χFB∖hF(Y)(χFhF(Y)(r,χFhF(X|y)(s,t)),t)=χFB∖hF(Y)(χFhF(X|y)(χFhF(Y)(r,s),χFhF(Y)(r,t)),t).Let s′=χFhF(X|y)(χFhF(Y)(r,s),χFhF(Y)(r,t)). Note that χFhF(Y)(r,t) and χFhF(Y)(r,s) are both in y. Thus we have that s′∈[χFhF(Y)(r,s)](X|y). Since (B∖hF(Y))⊢FX, χFhF(Y)(r,s)=χFB∖hF(Y)(s,r)∈[s]X. Thus [χFhF(Y)(r,s)](X|y)⊆[χFhF(Y)(r,s)]X=[s]X, so s′∈[s]X.
We have that χFhF(X|y)(s,t)=χFB∖hF(Y)(s′,t). However, since B∖hF(Y)⊢FX, we have χFB∖hF(Y)(s′,t)∈[s′]X=[s]X. Thus, hF(X)⊆hF(X|y), so hF(X)=hF(X|y). □
Lemma 2. Let F=(S,B) be a finite factored set. Let E⊆S and let X,Y∈Part(E) be subpartitions of S with the same domain. Then hF(X∨EY)=hF(X)∪⋃x∈XhF(Y|x).
Proof. Since X≤EX∨EY, we have hF(X)⊆hF(X∨EY). Similarly, for all x∈X, since Y|x⊆X∨EY, we have hF(Y|x)⊆hF(X∨EY). Thus, hF(X∨EY)⊇hF(X)∪⋃x∈XhF(Y|x). We still need to show that hF(X∨EY)⊆hF(X)∪⋃x∈XhF(Y|x).
We start with the special case where |X|=2. Let X={x0,x1}. In this case, we want to show that hF(X∨EY)=hF(X)∪hF(Y|x0)∪hF(Y|x0). Let C=hF(X), let C0=hF(Y|x0), and let C1=hF(Y|x1).
Consider arbitrary s,t∈E. Without loss of generality, assume that s∈x0, and let y=[s]Y. It suffices to show that χFC∪C0∪C1(s,t)∈x0∩y. Fix some r∈x1.
χFC∪C0∪C1(s,t)=χFC0(s,χFC(s,χFC1(s,t)))=χFC0(s,χFC(s,χFC(r,χFC1(s,t))))=χFC0(s,χFC(s,χFC1(χFC(r,s),χFC(r,t)))).Observe that χFC(r,s) and χFC(r,t) are both in x1, so χFC1(χFC(r,s),χFC(r,t))∈x1, and thus is in E. Combining this with the fact that s∈x0 gives us that χFC(s,χFC1(χFC(r,s),χFC(r,t)))∈x0. Thus, since s∈x0∩y, χFC∪C0∪C1(s,t)=χFC0(s,χFC(s,χFC1(χFC(r,s),χFC(r,t))))∈x0∩y.
Now, consider the case where |X|≠2. If |X|=0, then E={}, so all subpartitions involved are empty, and thus have the same (empty) history. If |X|=1, let X={E}. Then
hF(X∨EY)=hF(Y)=hF(Y|E)⊆hF(X)∪hF(Y|E)=hF(X)∪⋃x∈XhF(Y|x).Thus, we can restrict our attention to the case where |X|≥3.
Observe that X∨EY=⋁E({(Y|x)∪{E∖x}∣x∈X}). Thus hF(X∨EY)=⋃x∈XhF((Y|x)∪{E∖x}). However, from the case where |X|=2, we have
hF((Y|x)∪{E∖x})=hF({x,E∖x}∨E((Y|x)∪{E∖x}))=hF({x,E∖x})∪hF({E∖x})∪hF(Y|x).hF({E∖x}) is empty, so this gives us that hF(X∨EY)=⋃x∈X(hF(Y|x)∪hF({x,E∖x})). Since ⋁E({{x,E∖x}∣x∈X})=X, ⋃x∈XhF({x,E∖x})=hF(X), so we have hF(X∨EY)=hF(X)∪⋃x∈XhF(Y|x). □
4.3 Conditional Orthogonality
We can also extend our notions of orthogonality and time to subpartitions.
Definition 25. Let F=(S,B) be a finite factored set. Let X,Y∈SubPart(S) be subpartitions of S. We write X⊥FY if hF(X)∩hF(Y)={}, we write X≤FY if hF(X)⊆hF(Y), and we write X<FY if hF(X)⊂hF(Y).
We give this definition in general, but it is not clear whether orthogonality and time should be considered philosophically meaningful when the domains of the inputs differ from each other. Further, the temporal structure of subpartitions will mostly be outside the scope of this paper, and the orthogonality structure on subpartitions will mostly just be used for the following pair of definitions.
Definition 26 (conditional orthogonality given a subset). Given a finite factored set F=(S,B), partitions X,Y∈Part(S), and E⊆S, we say X and Y are orthogonal given E (in F), written X⊥FY|E, if (X|E)⊥F(Y|E).
Definition 27 (conditional orthogonality). Given a finite factored set F=(S,B), and partitions X,Y,Z∈Part(S), if X⊥FY|z for all z∈Z, then we say X and Y are orthogonal given Z (in F), written X⊥FY|Z.
Unconditioned orthogonality can be thought of as a special case of conditional orthogonality, where you condition on the indiscrete partition.
Proposition 24. Given a finite factored set F=(S,B) and partitions X,Y∈Part(S), X⊥FY if and only if X⊥FY|IndS.
Proof. If S={}, then there is only one partition X={}, and X⊥FX holds. Also, since IndS is empty, X⊥FX|IndS holds vacuously.
If S≠{}, then IndS={S}, so X⊥FY|IndS if and only if X⊥FY|S if and only if X|S⊥FY|S if and only if X⊥FY. □
The primary combinatorial structure of finite factored sets that we will be interested in is the structure of orthogonality (X⊥FY), conditional orthogonality (X⊥FY|Z), and time (X≤FY and X<FY) on inputs that are partitions.
We now will show that conditional orthogonality satisfies (a slight modification of) the axioms for a compositional semigraphoid.
Theorem 2. Let F=(S,B) be a finite factored set, and let X,Y,Z,W∈Part(S) be partitions of S.
Proof. Symmetry is clear from the definition.
Decomposition and composition both follow directly from the fact that for all z∈Z, hF((Y∨SW)|z)=hF((Y|z)∨z(W|z))=hF(Y|z)∪hF(W|z).
For weak union, assume that X⊥F(Y∨SW)|Z. Thus, for all z∈Z, hF(X|z)∩hF((Y∨SW)|z)={}. In particular, this means that hF(X|z)∩hF(W|z)={}, so by Lemma 1, for all w∈W, hF(X|z)=hF(X|w∩z). Further, we have that for all w∈W, hF(Y|w∩z)⊆hF(Y∨SW|z). Thus, for all w∈W, hF(X|w∩z)∩hF(Y|w∩z)={}, which since every element of W∨SZ is of the form w∩z for some w∈W and z∈Z, means that X⊥FY|(Z∨SW).
Finally, for contraction, assume that X⊥FY|Z and X⊥FW|Z∨SY. Fix some z∈Z. We want to show that hF(X|z)∩hF((Y∨SW)|z)={}. We have that hF((Y∨SW)|z)=hF((Y|z)∨z(W|z)), and by Lemma 2, hF((Y|z)∨z(W|z))=hF(Y|z)∪⋃y∈YhF(W|(y∩z)). Thus, it suffices to show that hF(X|z)∩hF(Y|z)={} and hF(X|z)∩hF(W|(y∩z))={} for all y∈Y.
The fact that hF(X|z)∩hF(Y|z)={} follows directly from X⊥FY|Z.
Fix a y∈Y. If y∩z={}, then hF(W|(y∩z))={}, so hF(X|z)∩hF(W|(y∩z))={}. Otherwise, we have hF(X|z)=hF(X|(y∩z)) by Lemma 1, and we have that hF(X|(y∩z))∩hF(W|(y∩z))={}, since X⊥FW|Z∨SY, so we have hF(X|z)∩hF(W|(y∩z))={}.
Thus, X⊥F(Y∨SW)|Z. □
The first four parts of Theorem 2 are essentially the semigraphoid axioms. The difference is that the semigraphoid axioms are normally defined as a ternary relation on disjoint sets of variables. We use partitions instead of sets of variables, use common refinement instead of union, and have no need for the disjointness condition. The fifth part (composition) is a converse to the decomposition axiom that is sometimes added to define a compositional semigraphoid.
The results in this paper will not depend on the theory of compositional semigraphoids, so we will not need to make the analogy any more explicit, but it is nice to note the similarity to existing well-studied structures.
We also get a nice relationship between conditional orthogonality and the refinement order.
Proposition 25. Let F=(S,B) be a finite factored set, and let X,Y∈Part(S) be partitions of S. X⊥FX|Y if and only if X≤SY.
Proof. If X⊥FX|Y, then for all y∈Y,hF(X|y)={}, so X|y=indy, so for all s,t∈y, we have s∼X|yt, and thus s∼Xt. Thus, for all s,t∈S, if s∼Yt, then s∼Xt. Thus X≤SY.
Conversely, if X≤SY, observe that for all y∈Y, X|y=indy, so hF(X|y)={}. Thus, X⊥FX|Y. □
In the next post, we will prove the fundamental theorem of finite factored sets, which says that conditional orthogonality exactly corresponds to conditional independence in all probability distributions that can be put on the relevant finite factored set.