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.
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.
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.
The fundamental theorem of finite factored sets tells us that (conditional) orthogonality 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 M=(F,f), where F is a finite factored set and f:set(F)→Ω is a function from the set of F to Ω.
Definition 39. Let S and Ω be sets, and let f:S→Ω be a function from S to Ω.
Given a ω∈Ω, we let f−1(ω)={s∈S∣f(s)=ω}.
Given an E⊆Ω, we let f−1(E)={s∈S∣f(s)∈E}.
Given an X∈Part(Ω), we let f−1(X)∈Part(S) be given by f−1(X)={f−1(x) | x∈X,f−1(x)≠{}}.
Definition 40 (orthogonality database). Given a set Ω, an orthogonality database on Ω is a pair D=(O,N), where O and N are both subsets of Part(Ω)×Part(Ω)×Part(Ω).
Definition 41. Given an orthogonality database D=(O,N) on a set Ω, and partitions X,Y,Z∈Part(Ω), we write X⊥DY|Z if (X,Y,Z)∈O, and we write X⇌DY|Z if (X,Y,Z)∈N.
Definition 42. Given a set Ω, a model M=(F,f) of Ω, and an orthogonality database D=(O,N) on Ω, we say M models D if for all X,Y,Z∈Part(Ω),
Definition 43. An orthogonality database D on a set Ω is called consistent if there exists a model M of Ω such that M models D.
Definition 44. An orthogonality database D on a set Ω is called complete if for all X,Y,Z∈Part(Ω), either X⊥DY|Z or X⇌DY|Z.
Definition 45. Given a set Ω, an orthogonality database D on Ω, and X,Y∈Part(Ω), we say X<DY if for all models (F,f) of Ω that model D, we have f−1(X)<Ff−1(Y).
6.2. Examples
Example 1. Let Ω={00,01,10,11} be the set of all bit strings of length 2. For i∈{0,1}, let xi={i0,i1} be the event that the first bit is i, and let yi={0i,1i} be the event that the second bit is i. Let X={x0,x1} and let Y={y0,y1}.
Let v0={00,11} be the event that the two bits are equal, let v1={01,10} be the event that the two bits are unequal, and let V={v0,v1}.
Let D=(O,N), where O={(X,V,{Ω})} and N={(V,V,{Ω})}.
Proposition 33. In Example 1, D is consistent.
Proof. First observe that F=(Ω,{X,V}) is a factored set, and so M=(F,f) is a model of Ω, where f is the identity on Ω. It suffices to show that M models D.
Indeed hF(X)={X}, and hF(V)={V}, so X⊥FV, so f−1(X)⊥Ff−1(V)|f−1({Ω}).
Further, it is not the case that V⊥FV, since V≠IndΩ. Thus it is not the case that f−1(V)⊥Ff−1(V)|f−1({Ω}).
Thus M satisfies all of the conditions to model D, so D is consistent. □
Proposition 34. In Example 1, X<DY.
Proof. Let (F,f) be any model of Ω that models D. Let F=(S,B). For any A∈Part(Ω), let HA=hF(f−1(A)). Our goal is to show that HX is a strict subset of HY.
First observe that X≤ΩY∨ΩV, so for any s,t∈S, if s∼f−1(Y)t and s∼f−1(V)t, then f(s)∼Yf(t) and f(s)∼Vf(t), so f(s)∼Xf(t), so s∼f−1(X)t. Thus f−1(X)≤Sf−1(Y)∨Sf−1(V).
It follows that HX⊆hF(f−1(Y)∨Sf−1(V))=HY∩HV. However, since X⊥DV|{Ω}, we have that HX∩HV={}, so HX⊆HY.
By swapping X and V in the argument above, we also get that HV⊆HY. Since V⇌DV|{Ω}, we have that HV≠{}. Thus HV contains some element b. Observe that b∉HX, but b∈HY. Thus HX is a strict subset of HY, so f−1(X)<Ff−1(Y).
Since (F,f) was an arbitrary model of Ω that models D, this implies that X<DY. □
Example 2. Let Ω={000,001,010,011,100,101,110,111} be the set of all bit strings of length 3. For i∈{0,1}, let xi={i00,i01,i10,i11} be the event that the first bit is i, let yi={0i0,0i1,1i0,1i1} be the event that the second bit is i, and let zi={00i,01i,10i,11i} be the event that the third bit is i. Let X={x0,x1}, let Y={y0,y1}, and let Z={z0,z1}.
Let v0={000,001,110,111} be the event that the first two bits are equal, let v1={010,011,100,101} be the event that the first two bits are unequal, and let V={v0,v1}.
Let D=(O,N), where O={(X,V,{Ω}),(X,Z,Y),(V,Z,Y)} and N={(X,Z,{Ω}),(V,Z,{Ω}),(Z,Z,Y)}.
Proposition 35. In Example 2, D is consistent.
Proof. Let S=Ω∪{00,01,10,11} be the set of all bit strings of length either 2 or 3.
For i∈{0,1}, let x′i={i00,i01,i10,i11,i0,i1} be the event that the first bit is i, and let X′={x′0,x′1}.
For i∈{0,1}, let y′i={0i0,0i1,1i0,1i1,0i,1i} be the event that the second bit is i, and let Y′={y′0,y′1}.
Let v′0={000,001,110,111,00,11} be the event that the first two bits are equal, let v′1={010,011,100,101,01,10} be the event that the first two bits are unequal, and let V′={v′0,v′1}.
For i∈{0,1}, let z′i={00i,01i,10i,11i} be the event that the third bit exists and is i, let z′2={00,01,10,11} be the event that there are only two bits, and let Z′={z′0,z′1,z′2}.
Let B={X′,V′,Z′}. Clearly, (S,B) is a finite factored set.
Let f:S→Ω be given by f(s)=s if s∈Ω, f(00)=000, f(01)=011, f(10)=100, and f(11)=111, so f copies the last bit on inputs of length 2, and otherwise leaves the bit string alone. We will show that (F,f) models D.
First, observe that f−1(X)=X′, f−1(Y)=Y′, f−1(V)=V′, and f−1(Z)={{000,010,100,110,00,10},{001,011,101,111,01,11}}.
It is easy to verify that hF(X′)={X′},hF(V′)={V′},hF(Y′)={X′,V′}, and hF(f−1(Z))=B. From this, we get that X′⊥FV′ holds, but X′⊥Ff−1(Z) and V′⊥Ff−1(Z) do not hold.
Next, observe that for i∈{0,1}, X′|yi=V′|yi={{0i0,0i1,0i},{1i0,1i1,1i}}. It is easy to verify that hF(X′|yi)=hF(V′|yi)={X′,V′}.
Also, observe that f−1(Z)|y0={{000,100,00,10},{001,101}}, and observe that f−1(Z)|y1={{010,110},{011,111,01,11}}. It is easy to verify that hF(f−1(Z)|y0)=hF(f−1(Z)|y1)={Z′}.
From this, we get that X′⊥Ff−1(Z)|Y′ and V′⊥Ff−1(Z)|Y′ hold, and f−1(Z)⊥Ff−1(Z)|Y′ does not hold.
Thus, (F,f) models D, so D is consistent. □
Proposition 36. In Example 2, X<DY<DZ.
Proof. Let (F,f) be any model of Ω that models D. Let F=(S,B). For any A∈Part(Ω), let HA=hF(f−1(A)). Our goal is to show that HX is a strict subset of HY and that HY is a strict subset of HZ.
First observe that X≤ΩY∨ΩV, so f−1(X)≤Sf−1(Y)∨f−1(V), so HX⊆HY∪HV. Since X⊥DY|{Ω}, HX∩HV={}, so HX⊆HY. Symmetrically, HV⊆HY, so HX∪HV⊆HY.
Similarly, Y≤ΩX∨ΩV, so HY⊆HX∪HV. Thus HY=HX∪HV.
We also know that HX and HV are nonempty, because X⇌DZ|{Ω} and Y⇌DZ|{Ω}.
Thus HX is a strict subset of HY, so X<DY.
Let C⊆B be arbitrary such that HX∩C and HV∩(B∖C) are both nonempty. Fix some bX∈HX∩C and bV∈HV∩(B∖C).
Since bX∈HX, there must exist s0,s1∈S such that s0∼bs1 for all b∈B∖{bX}, but not s0∼f−1(X)s1. Thus it is not the case that f(s0)∼Xf(s1). Without loss of generality, assume that f(s0)∈x0 and f(s1)∈x1.
Similarly, since bV∈HV, there must exist t0,t1∈S such that t0∼bt1 for all b∈B∖{bV}, but not t0∼f−1(V)t1. Again, without loss of generality, assume that f(t0)∈v0 and f(t1)∈v1.
For i,j∈{0,1}, let rij=χFHX(si,tj).
Next, observe that rij∼f−1(X)si, so f(rij)∼Xf(si)∈xi, so f(rij)∈xi. Similarly, f(rij)∈vj, so f(rij)∈xi∩vj. Thus, if i=j,f(rij)∈y0, and if i≠j, f(rij)∈y1.
Further, observe that χFC(r00,r11)=r01, since r00 and r11 agree on all factors other than bX and bV. In particular, this means that χFC(f−1(y0),f−1(y0))≠f−1(y0). Similarly, since χFC(r01,r10)=r00, we have that χFC(f−1(y1),f−1(y1))≠f−1(y1).
We will use this to show that for any y∈f−1(Y) and A∈Part(y), either hF(A)∩HY={}, or HY⊆hF(A). This is because hF(A)⊢FA, so χFhF(A)(y,y)=y, so by the above argument, if hF(A)∩HX is nonempty, then HV⊆hF(A), which since HV is nonempty means hF(A)∩HV is nonempty, so HX⊆hF(A), so HY⊆hF(A). Symmetrically, we also have that if hF(A)∩HV is nonempty, then HY⊆hF(A). Thus, if hF(A)∩HY is nonempty, then either hF(A)∩HX or hF(A)∩HV is nonempty, so HY⊆hF(A).
Note that for any y∈f−1(Y), two of the elements among the four rij defined above are in y, and those two elements are in different parts in f−1(X), so f−1(X)|y has at least two parts, so hF(f−1(X)|y) is nonempty. However, hF(f−1(X)|y)⊆hF(f−1(X)∨Sf−1(Y))=HY. Thus, hF(f−1(X)|y)∩HY≠{}, so HY⊆hF(f−1(X)|y), so hF(f−1(X)|y)=HY. Symmetrically, hF(f−1(V)|y)=HY.
In particular, this means that hF(f−1(Z)|y)∩HY={}, since X⊥DZ|Y.
Since X⇌DZ|{Ω}, there exists some bZ∈HX∩HZ. Since bZ∈HZ, there exist u0,u1∈S such that u0∼bu1 for all b∈B∖{bZ}, but it is not the case that u0∼f−1(Z)u1. Without loss of generality, assume that f(u0)∈z0 and f(u1)∈z1. Let y=[u0]f−1(Y).
Let by be an arbitrary element of HY. Since bY∈HY, there exist q0,q1∈S such that q0∼bq1 for all b∈B∖{bY}, but it is not the case that q0∼f−1(Y)q1. Without loss of generality, assume that q0∈y and q1∉y.
Consider p0=χFHY(q0,u0)=χFHY(q0,u1). Since q0∈y, p0∈y. Since u0 is also in y, χFhF(f−1(Z)|y)(p0,u0)∼f−1(Z)p0. However, since hF(f−1(Z)|y)∩HY={}, we have χFhF(f−1(Z)|y)(p0,u0)=u0, so u0∼f−1(Z)p0.
If u1 were in y, we would similarly have u1∼f−1(Z)p0, which would contradict the fact that it is not the case that u0∼f−1(Z)u1. Thus u1∉y.
Next, consider p1=χFHY(q1,u0)=χFHY(q1,u1). Since q1∉y, p1∉y. Since u1 is also not in y, χFhF(f−1(Z)|(S∖y))(p1,u1)∼f−1(Z)p1. However, since hF(f−1(Z)|(S∖y))∩HY={}, we have χFhF(f−1(Z)|(S∖y))(p1,u1)=u1, so u1∼f−1(Z)p1.
Thus, it is not the case that p0∼f−1(Z)p1. However, we constructed p0 and p1 such that p0∼bp1 for all b≠bY. Thus bY∈HZ. Since bY was arbitrary in HY, we have that HY⊆HZ. Finally, we need to show that this subset relation is strict.
Since Z⇌DZ|Y, there is some y such that hF(f−1(Z)|y)≠{}. Let b be any element of hF(f−1(Z)|y). Since hF(f−1(Z)|y)∩HY={}, b∉HY. However, b∈hF(f−1(Z)|y)⊆hF(f−1(Z)∨Sf−1(Y))=hZ∪HY. Therefore b∈HZ. Thus HY is a strict subset of HZ, so Y<DZ. □
In the next post, we'll discuss applications and future research directions.