Finite Factored Sets: Inferring Time

post by Scott Garrabrant · 2021-08-31T21:18:36.189Z · LW · GW · 5 comments

Contents

  6.1. Factored Set Models
  6.2. Examples
None
5 comments

The fundamental theorem [LW · GW] of finite factored sets [? · GW] tells us that (conditional [? · GW]) orthogonality [? · GW] data can be inferred from probabilistic data. Thus, if we can infer temporal data from orthogonality data, we will be able to combine these to infer temporal data purely from probabilistic data. In this section, we will discuss the problem of inferring temporal data from orthogonality data, mostly by going through a couple of examples.

 

6.1. Factored Set Models

We'll begin with a sample space, .

Naively, one might except that temporal inference in this paradigm involves inferring a factorization of . What we'll actually be doing, however, is inferring a factored set model of . This will allow for the possibility that some situations are distinct without being distinct in —that there can be latent structure not represented in .

Definition 38 (model). Given a set , a model of  is a pair , where  is a finite factored set and  is a function from the set of  to .

Definition 39. Let  and  be sets, and let  be a function from  to 

Given a , we let 

Given an , we let 

Given an , we let  be given by .

Definition 40 (orthogonality database). Given a set , an orthogonality database on  is a pair , where  and  are both subsets of .

Definition 41. Given an orthogonality database  on a set , and partitions , we write  if , and we write  if 

Definition 42. Given a set , a model  of , and an orthogonality database  on , we say  models  if for all ,

  1. if  then , and
  2. if  then .

Definition 43. An orthogonality database  on a set  is called consistent if there exists a model  of  such that  models 

Definition 44. An orthogonality database  on a set  is called complete if for all , either  or .

Definition 45. Given a set , an orthogonality database  on , and , we say  if for all models  of  that model , we have 

 

6.2. Examples

Example 1. Let  be the set of all bit strings of length . For , let  be the event that the first bit is , and let  be the event that the second bit is i. Let  and let 

Let  be the event that the two bits are equal, let  be the event that the two bits are unequal, and let 

Let , where  and .

Proposition 33.  In Example 1,  is consistent.

Proof. First observe that  is a factored set, and so  is a model of , where  is the identity on . It suffices to show that  models .

Indeed , and , so , so 

Further, it is not the case that , since . Thus it is not the case that .

Thus  satisfies all of the conditions to model , so  is consistent. 

Proposition 34. In Example 1, .

Proof. Let  be any model of  that models . Let . For any , let . Our goal is to show that  is a strict subset of .

First observe that , so for any , if  and , then  and , so , so . Thus .

It follows that . However, since , we have that , so .

By swapping  and  in the argument above, we also get that . Since , we have that . Thus  contains some element . Observe that , but . Thus  is a strict subset of , so .

Since  was an arbitrary model of  that models , this implies that 

Example 2. Let  be the set of all bit strings of length . For , let  be the event that the first bit is , let  be the event that the second bit is , and let  be the event that the third bit is . Let , let , and let 

Let  be the event that the first two bits are equal, let  be the event that the first two bits are unequal, and let 

Let , where  and .

Proposition 35. In Example 2,  is consistent.

Proof. Let  be the set of all bit strings of length either  or 

For , let  be the event that the first bit is , and let .

For , let  be the event that the second bit is , and let .

Let  be the event that the first two bits are equal, let  be the event that the first two bits are unequal, and let .

For , let  be the event that the third bit exists and is , let  be the event that there are only two bits, and let .

Let . Clearly,  is a finite factored set.

Let  be given by  if , and , so  copies the last bit on inputs of length , and otherwise leaves the bit string alone. We will show that  models .

First, observe that , and 

It is easy to verify that , and . From this, we get that  holds, but   and  do not hold.

Next, observe that for . It is easy to verify that .

Also, observe that , and observe that . It is easy to verify that .

From this, we get that  and  hold, and  does not hold. 

Thus,  models , so  is consistent. 

Proposition 36. In Example 2, .

Proof. Let  be any model of  that models . Let . For any , let . Our goal is to show that  is a strict subset of  and that  is a strict subset of .

First observe that , so , so . Since , so . Symmetrically, , so .

Similarly, , so . Thus .

We also know that  and  are nonempty, because  and .

Thus  is a strict subset of , so .

Let  be arbitrary such that  and  are both nonempty. Fix some  and .

Since , there must exist  such that  for all , but not . Thus it is not the case that . Without loss of generality, assume that  and .

Similarly, since , there must exist  such that  for all , but not . Again, without loss of generality, assume that  and 

For , let .

Next, observe that , so , so . Similarly, , so . Thus, if , and if .

Further, observe that , since  and  agree on all factors other than  and . In particular, this means that . Similarly, since , we have that .

We will use this to show that for any  and , either , or . This is because , so , so by the above argument, if  is nonempty, then , which since  is nonempty means  is nonempty, so , so . Symmetrically, we also have that if  is nonempty, then . Thus, if  is nonempty, then either  or  is nonempty, so .

Note that for any , two of the elements among the four  defined above are in , and those two elements are in different parts in , so  has at least two parts, so  is nonempty. However, . Thus, , so , so . Symmetrically, .

In particular, this means that , since 

Since , there exists some . Since , there exist  such that  for all , but it is not the case that . Without loss of generality, assume that  and . Let .

Let  be an arbitrary element of . Since , there exist  such that  for all , but it is not the case that . Without loss of generality, assume that  and .

Consider . Since . Since  is also in ,  . However, since , we have , so .

If  were in , we would similarly have , which would contradict the fact that it is not the case that . Thus .

Next, consider . Since . Since  is also not in ,  . However, since , we have , so 

Thus, it is not the case that . However, we constructed  and  such that  for all . Thus . Since  was arbitrary in , we have that  . Finally, we need to show that this subset relation is strict. 

Since , there is some  such that . Let  be any element of . Since . However, . Therefore . Thus  is a strict subset of , so 

 

In the next post, we'll discuss applications and future research directions.

5 comments

Comments sorted by top scores.

comment by Rohin Shah (rohinmshah) · 2021-09-06T09:24:46.023Z · LW(p) · GW(p)

For Example 2 / Prop 35, would this model also work?

Define  to be the factor corresponding to the question "are the second and third bits equal or not?" Then  is a model of . I believe this is consistent with :

 

For :

We have  and  for the first condition.

We have  and  for the second condition.

We have  and  for the third condition.

 

For .

We have  for the first and second conditions.

We have  for the third condition.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-09-06T10:54:04.712Z · LW(p) · GW(p)

I think that works, I didn't look very hard. Yore histories of X given Y and V given Y are wrong, but it doesn't change the conclusion.

Replies from: rohinmshah
comment by Rohin Shah (rohinmshah) · 2021-09-06T14:21:42.821Z · LW(p) · GW(p)

Yeah, both of those should be , if I'm not mistaken (a second time).

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-09-06T20:13:06.957Z · LW(p) · GW(p)

Yeah, also note that the history of  given  is not actually a well defined concept. There is only the history of  given  for . You could define it to be the union of all of those, but that would not actually be used in the definition of orthogonality. In this case , and  are all independent of choice of , but in general, you should be careful about that.

Replies from: rohinmshah
comment by Rohin Shah (rohinmshah) · 2021-09-07T06:20:55.415Z · LW(p) · GW(p)

Yeah, fair point. (I did get this right in the summary [LW(p) · GW(p)]; turns out if you try to explain things from first principles it becomes blindingly obvious what you should and shouldn't be doing.)