This is an edited transcript of Scott Garrabrant's May 23 LessWrong talk on finite factored sets. Video:

 Slides: https://intelligence.org/files/Factored-Set-Slides.pdf

Since there are existing introductions to finite factored sets that are shorter (link) or more formal (link), I decided to do things a bit differently with this transcript:

• I've incorporated Scott's slides into the transcript, and cut out some parts of the transcript that are just reading a slide verbatim.
• There was a text chat and Google Doc attendees used to discuss the talk while it was happening; I've inserted excerpts from this conversation into the transcript, in grey boxes.
• Scott also paused his talk at various times to answer questions; I've included these Q&A sections in white boxes.

Finite Factored Sets

Some Context

Scott: I'm going to start with some context. For people who are not already familiar with my work: My main motivation is to reduce existential risk. This leads me to want to figure out how to align advanced AI. This leads me to want to become less confused about intelligence and about agents embedded in their environment. I think there are a lot of hard open problems in trying to figure out how to do this.

This leads me to do a bunch of weird math and philosophy, and this talk is going to be an example of some of that weird math and philosophy.

Factoring the Talk

Scott: This talk can be split into $2\times 5=10$ parts. For example, this slide is in part 1 (the combinatorics talk) and $\text{Table of Contents}$.

I recognize that this table of contents has a lot more table and a lot less content than tables of contents normally have. But that's okay, because we'll have another table of contents in 6 more slides.

Set Partitions

Scott: All right. Let's do some background math.

A partition of a set $S$ is a way to view $S$ as a disjoint union. You have a bunch of sets that are disjoint from each other, and you can union the sets together to get $S$.

We'll also be using the lattice structure on partitions:

• We'll say that $X$ is finer than $Y$ (and $Y$ is coarser than $X$) if for all elements $s,t\in S$, if $S$ and $T$ are in the same part in $X$, they have to be in the same part in $Y$. So if $X$ is finer than $Y$, then you can think of $Y$ as making some distinctions; and $X$ has to make all of those distinctions, and possibly some more distinctions.
• The common refinement of two partitions $X$ and $Y$ is the coarsest partition that is finer than both $X$ and $Y$. So it has to make all of the distinctions that either $X$ or $Y$ make, and no more.

This picture on the right is all of the partitions of a four-element set, and the graph structure is showing the "finer" relation, with finer things closer to the bottom.

Set Factorizations

Scott: Now for some new stuff.

A factorization is a set $B$ of non-trivial partitions ("factors") of some set $S$, such that for each way of choosing one part from each factor in $B$, there exists a unique element of $S$ in the intersection of those parts.

A factorization is basically a multiplicative version of a partition. A factorization of $S$ is a way to view $S$ as a product, in the same way that a partition of $S$ is a way to view $S$ as a disjoint union.

Scott: If we have a factorization $B=\{b_0,\dots ,b_n\}$ of our set $S$, there will be a bijection between $S$ and the product $b_0\times \cdots \times b_n$. This bijection comes from sending an element $s\in S$ to the tuple consisting only of parts containing that element, $\left(\right[s{]}_{b_0},\dots ,\left[s{]}_{b_n}\right)$.

Because of this, the size of $S$ is always going to be equal to the product of the sizes of $S$'s factors.

This bijection is basically restating the definition above. It's saying that for each way of choosing one part from each factor, we're going to have a unique element in the intersection of those parts.

Another thing we can observe is that any factor in a factorization must always be a partition into parts of equal size, because otherwise you're not going to be able to make this bijection work out.

We will often be working with a finite factored set, which is a pair $(S,B)$, where $S$ is a finite set and $B$ is a factorization of $S$.

This definition is a little bit loopy. There's this thing where I'm first introducing $S$, and I'm saying that $B$ is a collection of partitions of $S$. But there's another way you can view it in which you first define $B$, which is just a collection of sets. Then you take the product of all of the sets in $B$, and this gives you a set $S$, which is tuples of the product of the elements in $B$. Then you can identify, with each element of a $b\in B$, the subset of the space of tuples that you get by projecting onto that part in the tuple.

So there's this temptation to define $S$ first and then define $B$ from $S$, and there's also a temptation to do the opposite. This bijection is saying that we can take either lens. 

Scott: To me, this is an extremely natural notion. I want to really push this naturalness, so I want to describe how factorization is dual to the definition of a partition.

You can see here I have two alternative definitions of partition and factorization. 

For partition: We have a bunch of (non-empty) subsets of $S$; we have functions to $S$, which are the inclusions; we can add all these functions together to give a function from their disjoint union to $S$; and we want this function to be a bijection.

Similarly, a factorization is a set of (non-trivial, meaning not having exactly one element) partitions of $S$ such that the obvious function to the product of the elements of $B$ from $S$ is a bijection. So for each partition in $B$, there's this projection onto that partition; and we can multiply all of these together to get a function from $S$ to the product, and we want this function to be a bijection.

You can see that in these two definitions, I’m pointwise dualizing a bunch of the words to show that there's a duality between partitions and factorizations. You'll notice that there’s also a duality between subsets and partitions. You can view a partition as "that which is dual to a subset," and you can also view it as "that which is built up out of subsets in a certain way." When I say that factorizations are dual to partitions, I'm using the "that which is built up from subsets in a certain way" conception of partitions.

I'm first going to give some examples, and then I'll open up the floor for questions about factorizations.

Enumerating Factorizations

Scott: Exercise: What are the factorizations of a four-element set, $\{0,1,2,3\}$?

.

.

.

.

.

.

.

.

.

.

.

.

The first thing to observe is that given any set with at least one element, we're always going to be able to define at least one factorization, a sort of trivial factorization.

This is a kind of one-dimensional factorization. We have one factor, which is the discrete partition.

Recall that in the definition of factorization, we want it to be the case that for each way of choosing one part from each factor, we want a unique element of $S$ in the intersection of those parts. The trivial factorization satisfies that.

What if we want a nontrivial factorization? Well, recall that the product of the sizes of the factors always has to equal the size of $S$. The only way to express $4$ as a nontrivial product is to express it as a $2\times 2$ product. So we're looking for two partitions/factors that are going to combine to give us $S$.

All of our factors also have to break $S$ into parts of equal size. So we're looking for $2$ partitions that each break our $4$-element set into $2$ parts of size $2$. There are exactly three partitions that break a 4-element set into $2$ parts of size $2$: $\left\{\right\{0,1\},\{2,3\left\}\right\}$, which separates the small numbers from the large numbers; $\left\{\right\{0,2\},\{1,3\left\}\right\}$, which separates the even numbers from the odd numbers; and $\left\{\right\{0,3\},\{1,2\left\}\right\}$, which separates the inner numbers from the outer numbers.

We're going to be able to choose any pair of these. So we're going to have three more factorizations:

The point here is that for each way of choosing, you're going to get a unique element that is the conjunction of those two choices. "Small or large?" and "even or odd?" jointly pick out a specific element of $\{0,1,2,3\}$.

Scott: In general, given an $n$-element set, you can ask how many factorizations there are of that set. We have the sequence here.

You can notice that if $n$ is prime, there’s only one factorization, which is the trivial one.

A very surprising fact to me was that this sequence did not appear on OEIS. OEIS is a database that combinatorialists use to share their sequences of integers, and check whether their sequences have been studied by other people and look for connections. This sequence didn't show up, even when I did minor modifications to deal with the degenerate cases.

I just don't get this. To me this basically feels like the multiplicative version of the Bell numbers. The Bell numbers count how many partitions there are in a set of size $n$. It's sequence #110 out of over 300,000 on the OEIS. And yet this sequence doesn't show up at all. I don't really have an understanding of why that happened.

Okay. Now I'm going to pause for questions.

The Main Talk (It's About Time)

The Pearlian Paradigm

Scott: We can't talk about time without talking about Pearlian causality. This paradigm allows you to, given a collection of variables and a joint probability distribution over those variables, infer causal/temporal relationships between the variables.

(In this talk, I'm going to be using "causal" and "temporal" interchangeably, though I think that there might be more to say there philosophically.)

Pearl can infer temporal data from statistical data. I'm not going to explain exactly how it works, because I'm not going to be technically dependent on it. This is really great. There's this adage, "Correlation does not imply causation,” and I think that it's just wrong and Pearl is correctly inferring causation from correlation all over the place using the combinatorial structure of the correlation.

The way that he does this is by inferring these graphs, like the one on the left. I think this graph is not entirely inferable from a probability distribution on the variables as it is, but some graphs are. You can definitely infer from a probability distribution that came from this graph, using the Pearlian paradigm, whether or not "the ground is wet" is before "the ground is slippery," for example.

Scott: The Pearlian paradigm is great. It's my main starting point. However, I claim that it's cheating: the "given a collection of variables" is actually hiding a lot of the work.

Normally people emphasize the joint distribution in saying that Pearl is inferring temporal data from statistical data, but I think that what's actually going on is that Pearl is inferring temporal data from statistical data together with factorization data.

For example, let's say all the variables in this picture are binary. The choice that we're working with these 5 variables, as opposed to just working with 32 distinct worlds without labels, is actually doing a lot of the work.

I think this issue is also entangled with a failure to adequately handle abstraction and determinism.

Let's say you're given these 5 variables and a joint probability distribution on the variables. One thing you could do is say, "I'm going to forget the variables that were given to me, and I'm just going to consider all Bell number of 32 different ways that the world can be."

And you could try to do Pearlian inference on this set of variables. The set is huge, but I'm working from an ontology where I don't care about things being huge. But you're going to run into a problem, which is that many of these variables that you define are going to be deterministic functions of each other, or partially deterministic functions of each other. Some of your variables/partitions will be coarsenings of other variables/partitions.

It turns out that the Pearlian paradigm, or the part that I'm trying to copy here, doesn't work well with all of this determinism. So you can't just throw away the variables you were given.

That's why I think that this cheating I'm accusing the Pearlian paradigm of doing is entangled with not being able to handle abstraction and determinism. By "abstraction" I mean I want some of my variables to be able to be coarser or finer copies of each other, which is similar to determinism.

We Can Do Better

Scott: So we're going to do something new.

• Where Pearl was given a collection of variables, we're going to take all partitions of a given set.
• Where Pearl inferred a directed acyclic graph, we're going to infer a finite factored set.
• In the Pearlian world, we could read off of our directed acyclic graph something that we'd want to call time. When we have a path from one node to another in a DAG, that means that the first node is before the second node.
  
  In the factored sets paradigm, we're going to have to define our own way of looking at a finite factored set and telling when some partitions are before or after other partitions.
• Pearl draws special attention to when two nodes in your DAG have no common ancestor. This corresponds to orthogonality, or independence. (In this talk, I'm going to use the word "independence" when I'm talking about probability, and I'm going to use the word "orthogonality" when I'm talking about combinatorial properties.)
  
  We're going to be able to read something analogous off of our finite factored sets.
• Pearl has a concept, d-separation, which is kind of complicated. And the reason d-separation is interesting is that it's equivalent to conditional independence in all probability distributions you could put on your DAG.
  
  We're going to define an analogous concept, conditional orthogonality, which we're going to be able to read off of a finite factored set.
• In the Pearlian world, we have that d-separation gives a compositional graphoid. In our world, we're going to have a compositional semigraphoid satisfied by conditional orthogonality. (There's a fifth graphoid axiom that we're not going to satisfy, but I argue we didn't want to satisfy it in the first place.)
• As with d-separation in Pearl, we're going to have a result saying that conditional orthogonality exactly corresponds to conditional independence in all probability distributions that you could put on your structure.
• We're going to be able to do temporal inference.
• And we're going to discuss some applications.

This is a green slide, so it's a table of contents slide; here are some slide numbers.

We've already talked about partitions and factorizations. Now, we're going to talk about time and orthogonality.

Time and Orthogonality

Scott: Before we define time and orthogonality, I'm going to define something called history.

We're starting with a fixed finite factored set, and that’s our context. $X$ is going to be a partition of $S$, and the history of $X$ is the smallest set of factors $H\subseteq B$ such that, if I take an element of $S$ and hide it from you, and you want to know what part in $X$ it's in, it suffices for me to tell you what part it's in within each of the factors in $H$.

So if I want to determine the $X$-value of an element of $S$, it suffices for me to know the value of all of the factors in $H$. So what's written here is saying that if two elements agree on all of the factors in $H$, then they have to agree on $X$.

(Whenever I have a partition, I can kind of think of it as a variable. So when I say "the $X$-value of an element," I mean "what part it's in within $X$.")

This definition is the central starting point. We're going to define everything from this, so it's worth pausing on.

You can kind of think of factors as basic properties from which everything can be computed. And I want to know which factors are going into the computation of $X$, which factors determine the value of $X$.

Scott: Then we're going to define time. We'll say that $X$ is weakly before $Y$ if the history of $X$ is a subset of the history of $Y$. And we'll say that $X$ is strictly before $Y$ if the history of $X$ is a strict subset of the history of $Y$.

One way you might want to think about this is that the history of $X$ is kind of like a past light cone. One spacetime point being before another spacetime point means that the past light cone of the first point is a subset of the past light cone of the second point. That gives some intuition as to why one might want to think of a temporal relationship as a subset relationship.

We're also going to define orthogonality. We’ll say that partitions $X$ and $Y$ are orthogonal if their histories are disjoint.

I think I actually want to pause for questions here, so let's do that.

Game of Life

Scott: Let's let $S$ be the set of all Game of Life computations starting from a board of some size.

I don't want to have to deal with weird stuff about the boundary, and I also want it to be a finite factored set. The way that I'm dealing with this is I'm looking at this pyramid of only the cells that are computable from the initial board state.

So you can imagine starting with your $(2n+1)\times (2n+1)$ board, and we're just pushing the computation forward in time. (In the picture, going up is forward in time.) And as we progress through the time steps in Game of Life, our board is getting smaller, because the boundary is shrinking in to say, "I don't know what this is anymore, because it's dependent on stuff outside the boundary." So we have this set of all pyramids of Game of Life computations.

Because Game of Life is deterministic, we actually have a bijection between the set of all Game of Life computations and the set of all initial board states. And we have an obvious factorization of the set of all initial board states, which is that we have one factor $b\in B$ for each cell that is the partition that separates out "Is that cell alive or dead at time $0$?".

We can also talk about other partitions. There are a whole bunch of partitions on this huge structure.

I'm going to draw attention to partitions that take a cell and take a time step, and ask the question "Is this cell alive or dead at this given time step?", which is going to separate out your space into two sets.

In this picture on the right, I have three (cell, time) pairs—the red cell, the blue cell, and the green cell—which correspond to partitions. And the grid on the bottom is the initial state, time $0$.

The multi-cell squares in the initial board state are the history of the red cell, the blue cell, and the green cell. So the light red squares on the bottom are saying, "Which cells at time $0$ do you need to know the value of in order to be able to compute the value of the red cell at time $1$?".

This, again, pushes the picture that histories are like past light cones. We can see that the history of the red partition is a subset of the history of the blue partition. And so the partition corresponding to “Is that red cell alive or dead?” is before the partition corresponding to “Is that blue cell alive or dead?”.

The red partition is orthogonal to the green partition. And the blue partition is not orthogonal to the green partition, because their histories intersect.

The blue cell and the green cell are almost orthogonal, in that if I conditioned on the values of these two cyan squares at the bottom, then they would become orthogonal. So that's what we're going to talk about next—conditional orthogonality, or "When are things orthogonal conditional on certain assumptions?".

Conditional Orthogonality

Scott: To define conditional orthogonality, we're first going to define conditional history. The conditional history of $X$ given $E$ is the smallest set of factors (again, smallest in the subset ordering) satisfying these two conditions.

The first condition is basically the same as in history, except we make this assumption that we're in $E$. So the first condition is saying that if I want to know the value of $X$, and I'm working under the assumption that my point is in $E$, it suffices for me to know the value of all of the factors in $H$.

The second condition is going to be a little hard to motivate. It's not going to mention $X$; it's just going to be about $E$ and $H$. The second condition says that if I take an element of $S$ and I want to determine whether or not it's in $E$, this process of determining whether or not it's in $E$ can be parallelized:

• I can look at the factors in $H$ and ask, "Is the assignment of values to the factors in $H$ consistent with my point being in $E$?"
• And then I can separately look at the factors in $B\setminus H$ and ask, "Is the value of the factors in $B\setminus H$ consistent with my point being in $E$?"

And then if both of these questions return "true," then my point has to be in $E$.

I'll say that without the second condition, conditional history would not even be well-defined. I do not think it should be obvious that it's well-defined anyway! In order for this history to be well-defined, I need to be able to say that there's a smallest set of factors (in the subset ordering) satisfying these conditions.

One way to see why we need the second condition is: You could imagine that we have a finite factored set that consists of two bits. There's my bit and there's your bit, and they're each either $0$ or $1$. And my factorization is the obvious factorization, with one factor for “What is my bit?” and one factor for “What is your bit?”. So then the history of “What is my bit?”, the history of the partition that separates out the different values that my bit can be, is just going to be the one factor that is “What is my bit?”.

But then imagine conditioning on the assumption that our bits are the same. In that case, knowing my bit is sufficient to know my bit, and knowing your bit is sufficient to know my bit, but the intersection of knowing my bit and knowing your bit is empty.

This is why we need the second condition. The second condition is saying that the act of conditioning on the fact that the two bits were the same, entangled my bit with your bit; so you're not allowed to then take one and not the other. This makes conditional history well-defined.

From conditional history we're going to be able to define conditional orthogonality. We say that $X$ and $Y$ are orthogonal given the subset $E$ if their conditional histories are disjoint. And we'll say that $X$ and $Y$ are orthogonal given a partition, $Z$, if $X$ and $Y$ are orthogonal given each individual part in $Z$.

I think it's pretty hard to motivate this definition. If I go over to categorical language, I think I have a picture that makes it look a little bit nicer than this, or a little bit more motivated. But I'm mostly just going to appeal to this definition's consequences to try to convince you that it's a good definition, as opposed to trying to push that it's really natural.

Compositional Semigraphoid Axioms

Scott: Here's some consequences. This is just a bunch of properties showing that conditional orthogonality is pretty well-behaved.

There are five graphoid axioms, of which the first four are the semigraphoid axioms. And then there's the axiom of composition, which is the fifth item on the above list and is the reason we have a "compositional" semigraphoid.

The field that works with Pearlian inference sometimes talks about these axioms. When they talk about it, they talk about it with sets of variables; we're instead working with partitions. So where they took a union of a set of variables, we're instead going to work with a common refinement. But that's all an easy translation.

All of these properties have a $Z$ in all of the conditions. You can just ignore the $Z$ and think of it without the $Z$ if you want to.

This first property says that $X$ is orthogonal to $Y$ if and only if $Y$ is orthogonal to $X$, which hopefully should make sense.

The second and the fifth are converses that together say that $X$ is orthogonal to the common refinement of $Y$ and $W$, if and only if $X$ is separately orthogonal to $Y$ and to $W$. So they're collectively saying that being orthogonal to a common refinement is equivalent to being orthogonal to each of the pieces.

That's especially nice, because it's saying that if you want to know whether something is orthogonal, it suffices to break it up however you want and check whether it's orthogonal to each individual piece.

d-separation in DAGs also satisfies all these properties.

The Fundamental Theorem

Scott: Those were just some nice properties. The main thing I want to push is that conditional orthogonality is really a combinatorial fragment of conditional independence.

We're going to show that $X$ is orthogonal to $Y$ given $Z$ if and only if $X$ is independent of $Y$ given $Z$ in all probability distributions that you can put on that factored set. (If you divide both sides by the probability of $P(z{)}^2$ in the equation, it's more obvious that this is asserting conditional independence.)

And so I need to explain what it means to put a probability distribution on a factored set.

A probability distribution on a finite factored set $F$ is just a probability distribution on $S$ that factors. What I mean by “factors” is that you can view it as coming from a probability distribution on each of the individual factors in your factorization. I take a probability distribution on $b$ for each $b\in B$, and then I multiply together all those probability distributions and take the product of those measures to get a probability distribution on $S$.

We'll call a probability distribution on $S$ a probability distribution on $F$ if it can be constructed in this way; or equivalently, if the probability of any given element is equal to the product of the probabilities of each of the parts in a factor that contain that element.

And then we get the fundamental theorem of finite factored sets. We can also probably extend this theorem to talk about all probability distributions in general position, or something like that, rather than talking about all probability distributions; but I'm not going to worry about that right now.

This theorem is going to allow us to infer orthogonality data from probabilistic data. If we're given a bunch of probabilistic data—for example, a big probability distribution on our set—we can use the fundamental theorem to tell us when things should be orthogonal.

Next, we're going to show how to infer temporal data from orthogonality data. And we're going to do that working entirely combinatorially; so this slide is actually the only place I'm going to mention probability. Part of the thing that I like about this is that I kind of push all the probability away and think about these questions just using combinatorial properties.

I think I'm going to take another question break.

Temporal Inference

Scott: We're going to start with a set $\Omega$, which is going to be our sample space—although I don't want to carry around any probability intuitions. I want to think about everything combinatorially, and I want the only place probability shows up to be the previous slide. $\Omega$ is a finite set, and it’s something like the space of all possible observations we can make.

One thing you might think that we'd want to do would be to infer a factorization of $\Omega$, but that's not what we're going to do. Instead, we're going to find a factored set model of $\Omega$. We're doing this because I'm thinking of $\Omega$ as the observably distinct situations that we can be in, and I want to allow for inferring latent structure.

There was a question about how to make a factored set out of a three-node Pearlian DAG. There were eight possibilities, but I said, "We don't want a factorization on an 8-element set; we want a factorization on a 32-element set, and then we want to send that over to an 8-element set with a function." In that example, the function $R\to S$ was latent structure.

In the model $(F,f)$:

• Not assuming $f$ is injective is what allows for latent structure.
• Not assuming $f$ is surjective means that it's okay if some of the elements of $\Omega$ don't actually get hit. This is useful if we just want to start with some variables and take their product and have that be my sample space. I don't want to assume that every combination of variables is necessarily possible; and that's what not assuming surjectivity is going to do.

Given a partition of $\Omega$, we can send that partition backwards across the function $f$ to give a partition of $S$. Which is just saying that if you have all of your parts, and then you take the preimage as functions of the parts, this will give you a partition of your original space.

We also have an orthogonality database on $\Omega$, which is a collection of rules about orthogonality in $\Omega$. One place you could think of this database as coming from is a probability distribution. You sample a whole bunch of times, and you get a probability distribution, and whenever you observe that two things are independent you'll put in a rule saying they're orthogonal. And then whenever you observe that things are not independent, you put in a rule that says those things should not be orthogonal. Which makes sense because of the fundamental theorem.

But you could also imagine that orthogonality database coming from anywhere else. This is entirely a combinatorial notion.

A "rule" means putting a triple of partitions either in the set $O$ (for "orthogonal") or the set $N$ (for "not orthogonal").

So we have this collection of rules, and we want to infer a factored set model. We're not actually going to be able to infer a full factored set model, because whenever you have one model, you can always just add in more factors and add in more stuff, and then just delete all that data. Instead, we're going to be able to infer properties of factored set models—properties that all factored set models that satisfy our database are going to have to satisfy.

One of these properties is: we'll say that $X$ is before $Y$ according to the database $D$ if $f^{-1}$ of $X$ is before $f^{-1}$ of $Y$ for all models that satisfy our database.

This is what we're going to mean by temporal inference. Now we have a mathematical specification of (though not a computational procedure for), "Given a bunch of orthogonality rules and non-orthogonality rules, when are those rules sufficient to infer a temporal relationship?"

I've specified this combinatorial notion of temporal inference. But I haven't shown this notion isn't vacuous. So there are these questions: “Are we ever going to be able to infer time with this?" "How is our approach to temporal inference going to be able to compare to Pearlian temporal inference?”

Pearlian temporal inference is actually very strong. If you have a big system with a bunch of variables, you're very likely going to be able to infer a lot of temporal relations from it. Can we keep up with that?

To answer that question, we're going to look at an example.

Two Binary Variables (Pearl)

Scott: If $X$ and $Y$ are independent, then we're not going to have a path from $X$ to $Y$ or vice versa. If $X$ and $Y$ are not independent, then maybe there's a path from $X$ to $Y$, maybe there's a path from $Y$ to $X$, maybe there's some third node that has a path to both of them.

In either case, we're not going to be able to infer any positive temporal relationships.

To me, this feels like it's where "correlation does not imply causation" comes from. If you just have two variables, you can't really infer causation; Pearl needs a lot more variables in order to have a richer combinatorial structure that will allow his approach to infer time.

But the natural next question is: "Is $X$ independent of $X\text{XOR}Y$?"

In the Pearlian ontology, we have $X$ and $Y$, and those are our variables, and we ask whether they're independent.

In the factored sets ontology, we take our $X$ and our $Y$, and the first thing we do is we take a product of $X$ and $Y$, and now we have four different possibilities. And then we forget all our labels, and we consider all possible variables on these four possibilities. And one of those variables is $X\text{XOR}Y$—are $X$ and $Y$ the same?

And if $X$ is independent of $X\text{XOR}Y$, then the finite factored set paradigm is actually going to be able to conclude that $X$ is before $Y$.

So not only is the paradigm non-vacuous, and not only can it keep up with Pearl and infer things that Pearl can't, but also we can use it to infer time even from two binary variables, which is kind of the simplest possible thing that you could hope to be able to do.

Pearl is also going to be able to infer some things that we can't, but as a reminder, Pearl is using extra assumptions. Relative to our ontology, there's extra factorization data that Pearl is using; and I'm not exactly sure where one would get that extra data.

Two Binary Variables (Factored Sets)

Scott: Let $\Omega$ be the set of all binary strings of length two. We're going to define an orthogonality database which is only going to have two rules.

• The first rule is that $X$ ("What is the first bit?") is orthogonal to $Z$ ("Do the bits match?"). The $\left\{\Omega \right\}$ here is just saying we're not making any conditions. (You don't have to worry about the complicated conditional orthogonality definitions for this proof; everything is just going to be normal orthogonality, which will make it easier to think through.)
• Second, $Z$ is not orthogonal to itself. This just means that $Z$ is nondeterministic; both of the parts in $Z$ are supported by our function $f$, both parts are possible.

If we got this orthogonality database from a probability distribution in general position, we would have a lot more rules in our database. We would have a rule for basically every triple of partitions. But inferring time is going to be monotonic with respect to adding partitions: adding more rules just lets you infer more stuff. So we can just work with the smallest database that we're going to need in order to be able to show that $X$ ("What is the first bit?") is before $Y$ ("What is the second bit?").

You should probably just assume that everything is not orthogonal to itself; but "$Z$ is not orthogonal to itself" is the only statement of that form we're going to need.

So, theorem: $X$ is before $Y$. Which, recall, means that $f^{-1}\left(X\right)$ is before $f^{-1}\left(Y\right)$ for all factored set models.

Proof. First, we’re going to prove that $X$ is weakly before $Y$:

• Let $(F,f)$ be a model that satisfies our database, and write $H_X$ for the history of $f^{-1}\left(X\right)$, etc. Since $X$ is orthogonal to $Z$, we're going to have that $H_X$ and $H_Z$ are disjoint.

If the $f^{-1}$ makes it a little bit harder to see what these things are saying, you can kind of ignore that part. If you just think of $X$, $Y$, and $Z$ as partitions of $S$, where $F=(S,B)$, it might be a little bit easier to understand what's going on here.

• Because $(X,Z,\{\Omega \left\}\right)$ is in $O$, $f^{-1}\left(X\right)$ is orthogonal to $f^{-1}\left(Z\right)$, which means the history of $f^{-1}\left(X\right)$ is disjoint from the history of $f^{-1}\left(Z\right)$: $H_X\cap H_Z=\left\{\right\}$.
• Because $Z$ is not orthogonal to itself, the history of $f^{-1}\left(Z\right)$ is not disjoint with itself, i.e., it's not empty.
• $X$ is a coarsening of the common refinement of $Y$ and $Z$: $X{\le }_{\Omega }Y{\vee }_{\Omega }Z$. And since we can compute the value of $X$ from the values of $Y$ and $Z$, we can also compute the value of $f^{-1}\left(X\right)$ from the values of $f^{-1}\left(Y\right)$ and $f^{-1}\left(Z\right)$. Which means that the history of $f^{-1}\left(X\right)$, $H_X$, has to be a subset of $H_Y\cup H_Z$.

To see why this is, recall that a history is the smallest set of factors I need to be able to compute a partition's value. If I have a set of factors that is sufficient to compute the value of $Y$ and sufficient to compute the value of $Z$, that's going to be sufficient to compute the value of $X$, because $X$ is a deterministic function of $Y\times Z$.

• We also get this subset relation for any other combination of $X$, $Y$, and $Z$. So $H_Z\subseteq H_X\cup H_Y$, and $H_Y\subseteq H_X\cup H_Z$.
• Since $H_X\subseteq H_Y\cup H_Z$, and $H_X$ is disjoint from $H_Z$, we get that $H_X\subseteq H_Y$—which is to say, $f^{-1}\left(X\right)$ is (weakly) before $f^{-1}\left(Y\right)$ in all models.

Let's extend this further, and show that $f^{-1}\left(X\right)$ is strictly before $f^{-1}\left(Y\right)$.

• Assume for the purpose of contradiction that $H_X=H_Y$. Since $H_Z\subseteq H_X\cup H_Y$, we'll then just have that $H_Z$ is a subset of $H_X$, because $H_X\cup H_Y$ will be $H_X$.
• But $H_Z$ is disjoint from $H_X$, which means that $H_Z$ is just going to have to be empty. But we assumed that $H_Z$ is nonempty; so this is a contradiction.

Thus $H_X$ is not equal to $H_Y$. So $H_X$ is a strict subset of $H_Y$, and $X$ is before $Y$. $\square$

Proofs in this space largely look like this. We look at a bunch of histories of our variables, we look at various different Boolean combinations of our histories, and we keep track of when they are empty and non-empty; and we use this to eventually infer that some of our histories are subsets of others.

I haven't spent much time on temporal inference, and I haven't really looked into the computational problem of inferring time from orthogonality databases yet. I basically just have two proofs of concept: this one, and another proof of concept that uses something that looks a little bit more like screening off, and uses conditional orthogonality to infer time in a more complicated situation.

Applications / Future Work / Speculation

Scott: I'm going to break some directions I want to go in into three categories. The first category is inference, which has a lot of computational questions. The second category is infinity, which has more mathematical questions. And the third category is embedded agency, which has more philosophical questions.

Inference

Decidability of temporal inference — I haven't been able to even prove whether the temporal inference method I just described is decidable, because there are infinitely many factored set models that you might have to consider.

I suspect it is decidable. Given the size of $\Omega$, there is an upper bound on how complicated of an $S$ you have to consider; and I conjecture that this upper bound is small, and probably computable by some simple function.

There's then the further question of whether we could do efficient temporal inference.

Conceptual inference — In our example, we inferred that $X$ is before $Y$, and we kind of inferred this structure that what's going on is that the universe is computing $X$ and $Z$, and then it's computing $Y$ from $X$ together with $Z$. So $X$ and $Z$ look like primitive properties, and $Y$ looks like a derived property that you might compute from $X$ and $Z$. And I think that this "being a primitive property" is actually also pointing at something about what kind of concepts you want to use.

Imagine that I have a number that's either 0 or 1, and it's also either blue or green. I can define a property called "bleen," which is that the number is a blue 0 $\text{XOR}$ a green 1. Now I have these three different properties I can talk about: number, color, and bleen-ness.

And we're doing something that looks like inferring that color is primitive, while bleen-ness is derived.

This system has the potential to be able to distinguish between blue and bleen. I think finite factored sets have the potential to do to "there's no principled difference between blue and bleen" what Pearl did to the adage "correlation does not imply causation". So that's a thing I'm really excited about maybe being able to do.

Temporal inference from raw data and fewer ontological assumptions — We can do a more end-to-end form of temporal inference, one that doesn't have to see where our variables are coming from. 

We can do temporal inference with deterministic relationships. 

Time without orthogonality — You could actually imagine starting with a huge factored set with a large number of dimensions, and then taking some $\Omega$ and forgetting a lot of the structure and just taking some weird subset of our big factored set.

If you do this, it might be the case that there is no orthogonality besides the vacuous orthogonalities. There might be no orthogonality in $\Omega$, but you can still make inferences from the probability distribution. The probability distribution will still lie on some algebraic curve that's pointing at the structure. And so even when there's no orthogonality at all, you might still be able to infer temporal relationships just from the probabilities.

Conditioned factored sets — Instead of assuming there's a factored set model of $\Omega$, you could imagine a partial factored set model where my $f$ can be a partial function.

This kind of corresponds to pretending that you had a factored set and you got some samples from $\Omega$, but those samples got passed through a filter. And so you can try to do inference on the more general class where maybe your data also went through a filter before you got it.

Infinity

Extending definitions to the infinite case — I talked a little bit about this earlier. I think that the fundamental theorem should be able to be extended to finite-dimensional factored sets, where by "finite-dimensional" I mean that $|B|$ is finite, but $|S|$ is infinite. But my proof assume finiteness, not just finite dimension.

Continuous time — Here's something I'm pretty excited about. Basically, I think that Pearl is not really ready to be continuous. There’s this blog post by Eliezer called Causal Universes that pointed out that physics kind of looks like a continuous Bayes net. But we didn't have a continuous Bayes net, and we still don't have a continuous Bayes net; and I feel like we're a lot closer to having a continuous Bayes net now.

Everything's still finite, and so we're running into problems there. But I think that once we’ve figured out this infinity stuff, we're going to be able to make things continuous, and I think that for two reasons.

1. The Pearlian world is really dependent on parents. We really cared about if this node was a parent of this node. In the finite factored sets paradigm, we only care about the analog of ancestor. So we're not really talking about an edge from this node to this node; we're only talking about “Are there paths?”, which is a lot closer to being able to be continuous.
2. We have this ability to zoom in and out on our variables. Instead of having fixed variables, we're taking them to be partitions, which allows for this zooming in and out.

I think that because of these two properties, we're a lot closer to being able to have not just continuous probabilities, but continuous time—continuity in the part that in Pearl was the DAG.

New lens on physics — Finite factored sets might be able to shine some new light on physics. I don't know; I'm not a physicist.

Embedded agency

I'm mostly viewing finite factored sets as the successor to Cartesian frames. In fact, if you look at the definition of a factored set model, it's almost equivalent; a binary factored set model is basically a Cartesian frame.

So I want to be able to model things like embedded observations. I want to be able to take a partition that corresponds to an action of an agent and take another partition that corresponds to an observation, and be able to say, "Ah, the thing that is deciding, this agent, kind of gets to do whatever functions it wants on this other thing." And I actually have some preliminary thoughts on how to define observations in a factored set world.

A point I want to make here is that in these embedded agency applications, I'm largely doing something different than I was doing in the temporal inference set. I focused in this talk on being able to do temporal inference because I think it's really concrete to be able to say, "Hey, we can do something like Pearlian temporal inference, but better and with fewer assumptions." 

When I'm thinking about embedded agency, I'm not really thinking about doing inference. I'm just thinking about being able to set up these factored set models where I would otherwise set up a DAG.

Or it doesn't even need to be a DAG. Anywhere we would want to set up a graph that has edges between nodes that correspond to causality, or information flow, or something like that, there's some hope of being able to translate that over to the factored set world and thus be able to have it work better with abstraction.

So I'm not really thinking about where these things are coming from. I'm more thinking about "How we can use this as a new way of modeling things that we would otherwise model with graphs?"

So:

Embedded observations — I have a definition of embedded observation. It looks a lot like the Cartesian frames version, except it's cleaner. 

Counterfactability — I have a notion of counterfactability that I can get out of factored sets. It's basically taking the position that you can't always take counterfactuals, but some places you can. I'm using the fact that a factored set takes your world and views it as a bunch of tuples to give me "interventions." My "interventions" correspond to coming in and tweaking some of the values in the tuples. So the factored set is also giving you a theory of how to do interventions.

Cartesian Frame successor — I think this framework is largely capturing a lot of the Cartesian frames content.

Unraveling causal loops — This is largely what I talk about in Saving Time. It feels like often we have these causal loops, and it feels like a bottleneck to being able to not have causal loops in our picture is to be able to have something that has time and also abstraction in the picture. And that's kind of what we're doing.

Conditional time — This is observing that just like we defined conditional orthogonality, we could define conditional time. We just take conditional time to be that the conditional histories are subsets of each other.

I have some hope that this might actually be interesting and useful, especially for the unraveling causal loops thing. I think that conditional time allows you to have multiple different timelines on your structure simultaneously, and have them be concretely playing together. I'm not sure whether it's actually going to end up being useful, but I'm just noticing that there's a very tempting way to define conditional time. 

Logical causality from logical induction — One of the first things that we did after finding logical induction was to ask, "Can we extend this to a theory of logical counterfactuals?" And we said, "How can we do this? Well, we could take our big probability distribution over logical sentences that we have at any given time. Can we do Pearl to that?”

And the answer is, "No, because there's a whole bunch of determinism everywhere."

I think that we still can't just go and do logical causality from something like logical induction. Basically, the finite factored set framework kind of doesn't believe in the uniform distribution on a four-element set. And I have some hopes of being able to fix this, but if you imagine a four-element set and the uniform distribution on it, and you consider the four two-part partitions on your four-element set (like the $X$, $Y$, and $Z$ in our "two binary variables" example). If you have the uniform distribution, we have that $X$ is independent of $Y$, and $X$ is independent of $Z$, but $X$ is not independent of $Y\vee Z$.

So the independence structure of the uniform distribution on a four-element set does not actually satisfy the compositional semigraphoid axioms. It specifically doesn't satisfy the composition axiom.

Similarly to how I'm excited about the infinite case even though the fundamental theorem will fail, I think that we're not going to be able to just directly use the fundamental theorem, but we could still ask, "What are some things consistent with this data?" We might have some extra independence that comes from something other than orthogonality. I could talk more about that, but I think I'll move on now.

Orthogonality as simplifying assumptions for decisions — We talked about orthogonality as coming from independence, but I think part of being an agent interacting with the world is that there are some parts of the world out there that I just believe are not going to be affected by my action. And I make this assumption, and I act based on this assumption. And I think this is another way that we can think of orthogonality as coming in.

And so I just wanted to point out that orthogonality doesn't need to come from probability. We can think of it as coming from somewhere else. 

And finally, conditional orthogonality as an abstraction desideratum — This is largely the kind of stuff that John Wentworth talks about. Like, an abstraction of $X$ should have the property that everything that I care about is orthogonal to $X$, given the abstraction of $X$. So I only throw away irrelevant data, and I can express "I only throw away irrelevant data" as "everything I care about is orthogonal to the underlying structure, given the abstraction."

All right. Those are my long rants about potential research directions for finite factored sets.

I'm going to say one more thing that's not on this slide: You can think of history as similar to entropy. You can think of my notion of history as a non-quantitative version of entropy.

And actually, when proving the semigraphoid axioms, I use some lemmas that look a lot like theorems about entropy, and then I replaced the sums and the expectations with unions.

And when you look at time—well, time is the subset relation on history, which is like saying that time is an inequality relation on entropy, and "later" corresponds to higher entropy. This is speculation, but this is a whole other ontology that you could put on what history means, etc.

Q&A

[Select questions from the Q&A are included below. The full Q&A transcript is here.]