Finite Factored Sets: Conditional Orthogonality

by Scott Garrabrant11 min read9th Jul 20212 comments

27

Ω 16

Finite Factored SetsCausalityAbstractionRationalityAI
Frontpage
Crossposted from the AI Alignment Forum. May contain more technical jargon than usual.

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 .

 

4.1 Generating a Subpartition

Definition 20 (subpartition). A subpartition of a set  is a partition of a subset of . Let  denote the set of all subpartitions of .

Definition 21 (domain). The domain of a subpartition  of , written , is the unique  such that .

Definition 22 (restricted partitions). Given sets  and  and a partition  of , let  denote the partition of  given by .

Definition 23 (generating a subpartition). Given a finite factored set , and , and a , we say  generates  (in ), written , if  for all .

Note that this definition clearly coincides with Definition 16, when  has domain . 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 .

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  be a finite factored set, let  be a subpartition of , let  be the domain of , and let  be a subset of . The following are equivalent.

  1. .
  2.  for all .
  3.  for all .
  4.  for all .
  5.  for all .
  6.  and  for all .
  7.  and .

Proof. The equivalence of conditions 1 and 2 is by definition.

The equivalence of conditions 2 and 3 follows directly from the fact that  for all , so .

To see that conditions 3 and 4 are equivalent, observe that since . Thus, if  for all , and conversely if  for all , then .

To see that condition 3 is equivalent to condition 5, observe that if condition 5 holds, then for all , we have  for all  and . Thus . Conversely, if condition 3 holds,  for all .

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  for all , so , so . Further, if  satisfy , then  for all , so , so . Thus 

Conversely, if condition 7 holds, then for all , we have , so , and thus . Further, clearly  implies  for all 

The first half of condition 7 in the above proposition can be thought of as saying that the values of factors in  are sufficient to distinguish between the parts of .

The second half can be thought of as saying that no factors in  become entangled with any factors outside of  when conditioning on . This second half is actually necessary (for example) to ensure that the set of all  that generate  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  be a finite factored set, let  and  be subsets of , let  be subpartitions of S, and let .

  1. If  and , then .
  2. If  and , then .
  3. .
  4.  if and only if .
  5. If  and , then  and .
  6. If , and , then .

Proof. The first 4 parts will use the equivalent definition from Proposition 20 that  if and only if . 1 and 2 are immediate from this definition.

3 follows directly from Definition 23. 

4 follows directly from the fact that , and  so  if and only if .

For part 5, we will use the equivalent definition from Proposition 20 that  if and only if  for all . Assume that for all  and . Thus, for all . Similarly, for all . Thus  and .

For part 6, we use the definition that  if and only if  for all . Clearly if , and  for all , then  for all .

Note that while the set of  that generate an  is closed under supersets, the set of  that generate an  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  and a subpartition , let  denote the smallest (according to the subset ordering) subset of  such that .

Proposition 22. Given a finite factored set  is well-defined, and if  is a partition of , this definition coincides with Definition 17.

Proof. Fix a finite factored set  and a subpartition , and let  be the intersection of all  such that . It suffices to show that . Then  will clearly be the unique smallest (according to the subset ordering) subset of  such that . The fact that this definition coincides with Definition 17 if  is clear.

Note that  is a finite intersection, since there are only finitely many subsets of , and that  is a nonempty intersection since . Thus, we can express  as a (possibly empty) composition of finitely many binary intersections. By part 5 of Proposition 21, the intersection of two subsets that generate  also generates . Thus 

We will now give five basic properties of the history of subpartitions, followed by two more properties that are less basic.

Proposition 23. Let  be a finite factored set, let  be subpartitions of , and let .

  1. If , then .
  2. .
  3. If , then .
  4.  if and only if .
  5. If  is nonempty, then  for all .

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 , by part 1 of Proposition 21. Thus it suffices to show that , by showing that .

We will use condition 7 in Proposition 20. Clearly

 and similarly,

Thus, .

Next, we need to show that . Clearly 

Let  and  be elements of , and observe that . We have that , since . Thus, we also have that , since . Thus, .

Thus we have that  and . Thus, by condition 7 in Proposition 20, , so 

Lemma 1. Let  be a finite factored set, and let  be subpartitions of  with the same domain. If , then  for all .

Proof. Let  be a finite factored set, let , and let .

We start by showing that  and . Observe that . Further observe that , so , so . Thus, . Symmetrically, .

Fix some . We start by showing that 

We have that , so , so for all , we have . We also have . Thus  . Every element of  is of the form  for some , so we have , so .

Next, we need to show that . For this, it suffices to show that . Let  be arbitrary elements of . It suffices to show that 

First, observe that since , we have that 

Let  be an arbitrary element of . We thus have:

Let . Note that  and  are both in . Thus we have that . Since . Thus , so .

We have that . However, since , we have . Thus, , so 

Lemma 2. Let  be a finite factored set. Let  and let  be subpartitions of  with the same domain. Then .

Proof. Since , we have . Similarly, for all , since , we have . Thus, . We still need to show that .

We start with the special case where . Let . In this case, we want to show that . Let , let , and let .

Consider arbitrary . Without loss of generality, assume that , and let . It suffices to show that . Fix some .

Observe that  and  are both in , so , and thus is in . Combining this with the fact that  gives us that  Thus, since .

Now, consider the case where . If , then , so all subpartitions involved are empty, and thus have the same (empty) history. If , let . Then

Thus, we can restrict our attention to the case where 

Observe that . Thus . However, from the case where , we have

 is empty, so this gives us that . Since , so we have 

 

4.3 Conditional Orthogonality

We can also extend our notions of orthogonality and time to subpartitions.

Definition 25. Let  be a finite factored set. Let  be subpartitions of . We write  if , we write  if , and we write  if .

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 , partitions , and , we say  and  are orthogonal given  (in ), written , if .

Definition 27 (conditional orthogonality). Given a finite factored set , and partitions , if  for all , then we say  and  are orthogonal given  (in ), written .

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  and partitions  if and only if 

Proof. If , then there is only one partition , and  holds. Also, since  is empty,  holds vacuously.

If , then , so  if and only if  if and only if  if and only if 

The primary combinatorial structure of finite factored sets that we will be interested in is the structure of orthogonality (), conditional orthogonality (), and time  and  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  be a finite factored set, and let  be partitions of .

  1. If , then .   (symmetry)
  2. If , then  and .   (decomposition)
  3. If , then .   (weak union)
  4. If  and , then .   (contraction)
  5. If  and , then .   (composition)

Proof. Symmetry is clear from the definition.

Decomposition and composition both follow directly from the fact that for all .

For weak union, assume that . Thus, for all . In particular, this means that , so by Lemma 1, for all . Further, we have that for all . Thus, for all , which since every element of  is of the form  for some  and , means that .

Finally, for contraction, assume that  and . Fix some . We want to show that . We have that , and by Lemma 2, . Thus, it suffices to show that  and  for all .

The fact that  follows directly from 

Fix a . If , then , so . Otherwise, we have  by Lemma 1, and we have that , since , so we have 

Thus, 

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  be a finite factored set, and let  be partitions of S.  if and only if .

Proof. If , then for all , so , so for all , we have , and thus . Thus, for all , if , then . Thus .

Conversely, if , observe that for all , so . Thus, 

 

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.

27

Ω 16

2 comments, sorted by Highlighting new comments since Today at 2:22 AM
New Comment

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.