This is the edited transcript of a talk introducing finite factored sets. For most readers, it will probably be the best starting point for learning about factored sets.

Video: 

 (Lightly edited) slides: https://intelligence.org/files/Factored-Set-Slides.pdf

1. Short Combinatorics Talk

1m. $\text{Some Context}$

Scott: So I want to start with some context. For people who are not already familiar with my work:

• My main motivation is to reduce existential risk.
• I try to do this by trying to figure out how to align advanced artificial intelligence.
• I try to do this by trying to become less confused about intelligence and optimization and agency and various things in that cluster.
• My main strategy here is to develop a theory of agents that are embedded in the environment that they're optimizing. I think there are a lot of open hard problems around doing this.
• This leads me to do a bunch of weird math and philosophy. This talk is going to be an example of some weird math and philosophy.

For people who are already familiar with my work, I just want to say that according to my personal aesthetics, the subject of this talk is about as exciting as Logical Induction, which is to say I'm really excited about it. And I'm really excited about this audience; I'm excited to give this talk right now.

1t. $\text{Factoring the Talk}$

This talk can be split into 2 parts:

• Part 1: a short pure-math combinatorics talk.

I suspect that if I were better, I would instead be giving a short pure-math category theory talk; but I'm trained as a combinatorialist, so I'm giving a combinatorics talk upfront.

• Part 2: a more applied and philosophical main talk.

This talk can also be split into 4 parts differentiated by color: $\text{Motivation}$, $\text{Table of Contents}$, $\text{Main Body}$, and $\text{Examples}$. Combining these gives us 8 parts (some of which are not contiguous):

1b. $\text{Set Partitions}$

All right. Here's some background math:

• A partition of a set $S$ is a set $X$ of non-empty subsets of $S$, called parts, such that for each $s\in S$ there exists a unique part in $X$ that contains $s$.
• Basically, a partition of $S$ is a way to view $S$ as a disjoint union. We have parts that are disjoint from each other, and they union together to form $S$.
• We'll write $Part\left(S\right)$ for the set of all partitions of S.
• We'll say that a partition $X$ is trivial if it has exactly one part.
• We'll use bracket notation, $[s{]}_X$, to denote the unique part in $X$ containing $s$. So this is like the equivalence class of a given element.
• And we'll use the notation $s{\sim }_{X}t$ to say that two elements $s$ and $t$ are in the same part in $X$.

You can also think of partitions as being like variables on your set $S$. Viewed in that way, the values of a partition $X$ correspond to which part an element is in.

Or you can think of $X$ as a question that you could ask about a generic element of $S$. If I have an element of $S$ and it's hidden from you and you want to ask a question about it, each possible question corresponds to a partition that splits up $S$ according to the different possible answers.

 We're also going to use the lattice structure of partitions:

• We'll say that $X{\ge }_{S}Y$ ($X$ is finer than $Y$, and $Y$ is coarser than $X$) if $X$ makes all of the distinctions that $Y$ makes (and possibly some more distinctions), i.e., if for all $s,t\in S$, $s{\sim }_{X}t$ implies $s{\sim }_{Y}t$. You can break your set $S$ into parts, $Y$, and then break it into smaller parts, $X$.
• $X{\vee }_{S}Y$ (the common refinement of $X$ and $Y$) is the coarsest partition that is finer than both $X$ and $Y$. This is the unique partition that makes all of the distinctions that either $X$ or $Y$ makes, and no other distinctions. This is well-defined, which I'm not going to show here.

Hopefully this is mostly background. Now I want to show something new.

1b. $\text{Set Factorizations}$

A factorization of a set $S$ is a set $B$ of nontrivial partitions of $S$, called factors, 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.

So this is maybe a little bit dense. My short tagline of this is: "A factorization of $S$ is a way to view $S$ as a product, in the exact same way that a partition was a way to view $S$ as a disjoint union."

If you take one definition away from this first talk, it should be the definition of factorization. I'll try to explain it from a bunch of different angles to help communicate the concept.

If $B=\{b_0,\dots ,b_n\}$ is a factorization of $S$, then there exists a bijection between $S$ and $b_0\times \cdots \times b_n$ given by $s\mapsto \left(\right[s{]}_{b_0},\dots ,\left[s{]}_{b_n}\right)$. This bijection comes from sending an element of $S$ to the tuple consisting only of parts containing that element. And as a consequence of this bijection, $|S|={\prod }_{b\in B}|b|$.

So we're really viewing $S$ as a product of these individual factors, with no additional structure.

Although we won't prove this here, something else you can verify about factorizations is that all of the parts in a factor have to be of the same size.

We'll write $Fact\left(S\right)$ for the set of all factorizations of $S$, and we'll say that a finite factored set is a pair $(S,B)$, where $S$ is a finite set and $B\in Fact\left(S\right)$.

Note that the relationship between $S$ and $B$ is somewhat loopy. If I want to define a factored set, there are two strategies I could use. I could first introduce the $S$, and break it into factors. Alternatively, I could first introduce the $B$. Any time I have a finite collection of finite sets $B$, I can take their product and thereby produce an $S$, modulo the degenerate case where some of the sets are empty. So $S$ can just be the product of a finite collection of arbitrary finite sets.

To my eye, this notion of factorization is extremely natural. It's basically the multiplicative analog of a set partition. And I really want to push that point, so here's another attempt to push that point:

I can take a slightly modified version of the partition definition from before and dualize a whole bunch of the words, and get out the set factorization definition.

Hopefully you're now kind of convinced that this is an extremely natural notion.

I'm now going to move on to some examples.

1e. $\text{Enumerating Factorizations}$

Exercise! What are the factorizations of the set $\{0,1,2,3\}$?

Spoiler space:

.

.

.

.

.

.

.

.

.

.

First, we're going to have a kind of trivial factorization:

We only have one factor, and that factor is the discrete partition. You can do this for any set, as long as your set has at least two elements. 

Recall that in the definition of factorization, we wanted that for each way of choosing one part from each factor, we had a unique element in the intersection of those parts. Since we only have one factor here, satisfying the definition just requires that for each way of choosing one part from the discrete partition, there exists a unique element that is in that part.

And then we want some less trivial factorizations. In order to have a factorization, we're going to need some partitions. And the product of the cardinalities of our partitions are going to have to equal the cardinality of our set $S$, which is 4. 

The only way to express 4 as a nontrivial product is to express it as $2\times 2$. Thus we're looking for factorizations that have 2 factors, where each factor has 2 parts.

We noted earlier that all of the parts in a factor have to be of the same size. So we're looking for 2 partitions that each break our 4-element set into 2 sets of size 2.

So if I'm going to have a factorization of $\{0,1,2,3\}$ that isn't this trivial one, I'm going to have to pick 2 partitions of my 4-element set that each break the set into 2 parts of size 2. And there are 3 partitions of a 4-element sets that break it up into 2 parts of size 2. For each way of choosing a pair of these 3 partitions, I'm going to get a factorization.

So there will be 4 factorizations of a 4-element set.

In general you can ask, "How many factorizations are there of a finite set of size $n$?". Here's a little chart showing the answer for $n\le 25$:

You'll notice that if $n$ is prime, there will be a single factorization, which hopefully makes sense. This is the factorization that only has one factor.

A very surprising fact to me is that this sequence did not show up on OEIS, which is this database that combinatorialists use to check whether or not their sequence has been studied before, and to see connections to other sequences.

To me, this just feels like the multiplicative version of the Bell numbers. The Bell numbers count how many partitions there are of a set of size $n$. It's sequence number 110 on OEIS out of over 300,000; and this sequence just doesn't show up at all, even when I tweak it and delete the degenerate cases and so on.

I am very confused by this fact. To me, factorizations seem like an extremely natural concept, and it seems to me like it hasn't really been studied before.

This is the end of my short combinatorics talk.

All right. I think I'm going to move on to the main talk.

2. The Main Talk (It's About Time)

2m. $\text{The Pearlian Paradigm}$

We can't talk about time without talking about Pearlian causal inference. I want to start by saying that I think the Pearlian paradigm is great. This buys me some crackpot points, but I'll say it's the best thing to happen to our understanding of time since Einstein.

I'm not going to go into all the details of Pearl's paradigm here. My talk will not be technically dependent on it; it's here for motivation.

Given a collection of variables and a joint probability distribution over those variables, Pearl can infer causal/temporal relationships between the variables. (In this talk I'm going to use "causal" and "temporal" interchangeably, though there may be more interesting things to say here philosophically.)

Pearl can infer temporal data from statistical data, which is going against the adage that "correlation does not imply causation." It's like Pearl is taking the combinatorial structure of your correlation and using that to infer causation, which I think is just really great.

I am going to (a little bit) go against this, though. I'm going to claim that Pearl is kind of cheating when making this inference. The thing I want to point out is that in the sentence "Given a collection of variables and a joint probability distribution over those variables, Pearl can infer causal/temporal relationships between the variables.", the words "Given a collection of variables" are actually hiding a lot of the work.

The emphasis is usually put on the joint probability distribution, but Pearl is not inferring temporal data from statistical data alone. He is inferring temporal data from statistical data and factorization data: how the world is broken up into these variables.

I claim that this issue is also entangled with a failure to adequately handle abstraction and determinism. To point at that a little bit, one could do something like say:

"Well, what if I take the variables that I'm given in a Pearlian problem and I just forget that structure? I can just take the product of all of these variables that I'm given, and consider the space of all partitions on that product of variables that I'm given; and each one of those partitions will be its own variable. And then I can try to do Pearlian causal inference on this big set of all the variables that I get by forgetting the structure of variables that were given to me."

And the problem is that when you do that, you have a bunch of things that are deterministic functions of each other, and you can't actually infer stuff using the Pearlian paradigm.

So in my view, this cheating is very entangled with the fact that Pearl's paradigm isn't great for handling abstraction and determinism.

2t. $\text{We Can Do Better}$

The main thing we'll do in this talk is we're going to introduce an alternative to Pearl that does not rely on factorization data, and that therefore works better with abstraction and determinism.

Where Pearl was given a collection of variables, we are going to just consider all partitions of a given set. Where Pearl infers a directed acyclic graph, we're going to infer a finite factored set.

In the Pearlian world, we can look at the graph and read off properties of time and orthogonality/independence. A directed path between nodes corresponds to one node being before the other, and two nodes are independent if they have no common ancestor. Similarly, in our world, we will be able to read time and orthogonality off of a finite factored set.

(Orthogonality and independence are pretty similar. I'll use the word "orthogonality" when I'm talking about a combinatorial notion, and I'll use "independence" when I'm talking about a probabilistic notion.)

In the Pearlian world, d-separation, which you can read off of the graph, corresponds to conditional independence in all probability distributions that you can put on the graph. We're going to have a fundamental theorem that will say basically the same thing: conditional orthogonality corresponds to conditional independence in all probability distributions that we can put on our factored set.

In the Pearlian world, d-separation will satisfy the compositional graphoid axioms. In our world, we're just going to satisfy the compositional semigraphoid axioms. The fifth graphoid axiom is one that I claim you shouldn't have even wanted in the first place.

Pearl does causal inference. We're going to talk about how to do temporal inference using this new paradigm, and infer some very basic temporal facts that Pearl's approach can't. (Note that Pearl can also sometimes infer temporal relations that we can't—but only, from our point of view, because Pearl is making additional factorization assumptions.)

And then we'll talk about a bunch of applications.

Excluding the motivation, table of contents, and example sections, this table also serves as an outline of the two talks. We've already talked about set partitions and finite factored sets, so now we're going to talk about time and orthogonality.

2b. $\text{Time and Orthogonality}$

I think that if you capture one definition from this second part of the talk, it should be this one. Given a finite factored set as context, we're going to define the history of a partition.

Let $F=(S,B)$ be a finite factored set. And let $X,Y\in Part\left(S\right)$ be partitions of $S$.

The history of $X$, written $h^F\left(X\right)$, is the smallest set of factors $H\subseteq B$ such that for all $s,t\in S$, if $s{\sim }_{b}t$ for all $b\in H$, then $s{\sim }_{X}t$.

The history of $X$, then, is the smallest set of factors $H$—so, the smallest subset of $B$—such that if I take an element of $S$ and I hide it from you, and you want to know which part in $X$ it is in, it suffices for me to tell you which part it is in within each of the factors in $H$.

So the history $H$ is a set of factors of $S$, and knowing the values of all the factors in $H$ is sufficient to know the value of $X$, or to know which part in $X$ a given element is going to be in. I'll give an example soon that will maybe make this a little more clear.

We're then going to define time from history. We'll say that $X$ is weakly before $Y$, written $X{\le }^{F}Y$, if $h^F\left(X\right)\subseteq h^F\left(Y\right)$. And we'll say that $X$ is strictly before $Y$, written $X{<}^{F}Y$, if $h^F\left(X\right)\subset h^F\left(Y\right)$.

One analogy one could draw is that these histories are like the past light cones of a point in spacetime. When one point is before another point, then the backwards light cone of the earlier point is going to be a subset of the backwards light cone of the later point. This helps show why "before" can be like a subset relation.

We're also going to define orthogonality from history. We'll say that two partitions $X$ and $Y$ are orthogonal, written $X{\perp }^{F}Y$, if their histories are disjoint: $h^F\left(X\right)\cap h^F\left(Y\right)=\left\{\right\}$.

Now I'm going to go through an example.

2e. $\text{Game of Life}$

Let $S$ be the set of all Game of Life computations starting from an $[-n,n]\times [-n,n]$ board.

Let $R=\left\{\right(r,c,t)\in Z^3\mid 0\le t\le n,|r|\le n-t,|c|\le n-t\}$ (i.e., cells computable from the initial $[-n,n]\times [-n,n]$ board). For $(r,c,t)\in R$, let $\ell (r,c,t)\subseteq S$ be the set of all computations such that the cell at row $r$ and column $c$ is alive at time $t$.

(Minor footnote: I've done some small tricks here in order to deal with the fact that the Game of Life is normally played on an infinite board. We want to deal with the finite case, and we don't want to worry about boundary conditions, so we're only going to look at the cells that are uniquely determined by the initial board. This means that the board will shrink over time, but this won't matter for our example.)

$S$ is the set of all Game of Life computations, but since the Game of Life is deterministic, the set of all computations is in bijective correspondence with the set of all initial conditions. So $|S|=2^{(2n+1{)}^2}$, the number of initial board states.

This also gives us a nice factorization on the set of all Game of Life computations. For each cell, there's a partition that separates out the Game of Life computations in which that cell is alive at time 0 from the ones where it's dead at time 0. Our factorization, then, will be a set of $(2n+1{)}^2$ binary factors, one for each question of "Was this cell alive or dead at time 0?".

Formally: For $(r,c,t)\in R$, let $L_{(r,c,t)}=\left\{\ell \right(r,c,t),S\setminus \ell (r,c,t\left)\right\}$. Let $F=(S,B)$, where $B=\{L_{(r,c,0)}\mid -n\le r,c\le n\}$.

There will also be other partitions on this set of all Game of Life computations that we can talk about. For example, you can take a cell and a time $t$ and say, "Is this cell alive at time $t$?", and there will be a partition that separates out the computations where that cell is alive at time $t$ from the computations where it's dead at time $t$.

Here's an example of that:

The lowest grid shows a section of the initial board state.

The blue, green, and red squares on the upper boards are (cell, time) pairs. Each square corresponds to a partition of the set of all Game of Life computations, "Is that cell alive or dead at the given time $t$?"

The history of that partition is going to be all the cells in the initial board that go into computing whether the cell is alive or dead at time $t$. It's everything involved in figuring out that cell's state. E.g., knowing the state of the nine light-red cells in the initial board always tells you the state of the red cell in the second board.

In this example, the partition corresponding to the red cell's state is strictly before the partition corresponding to the blue cell. The question of whether the red cell is alive or dead is before the question of whether the blue cell is alive or dead.

Meanwhile, the question of whether the red cell is alive or dead is going to be orthogonal to the question of whether the green cell is alive or dead.

And the question of whether the blue cell is alive or dead is not going to be orthogonal to the question of whether the green cell is alive or dead, because they intersect on the cyan cells.

Generalizing the point, fix $X=L_{(r_X,c_X,t_X)},Y=L_{(r_Y,c_Y,t_Y)}$, where $(r_X,c_X,t_X),(r_Y,c_Y,t_Y)\in R$. Then:

• $h^F\left(X\right)=\{L_{(r,c,0)}\in B\mid |r_X-r|\le t_X,|c_X-c|\le t_X\}$.
• $X{<}^{F}Y$ if and only if $t_X<t_Y$ and $|r_Y-r_X|,|c_Y-c_X|\le t_Y-t_X$.
• $X{\perp }^{F}Y$ if and only if $|r_Y-r_X|>t_Y+t_X$ or $|c_Y-c_X|>t_Y+t_X$.

We can also see that the blue and green cells look almost orthogonal. If we condition on the values of the two cyan cells in the intersection of their histories, then the blue and green partitions become orthogonal. That's what we're going to discuss next.

2b. $\text{Conditional Orthogonality}$

So, just to set your expectations: Every time I explain Pearlian causal inference to someone, they say that d-separation is the thing they can't remember. d-separation is a much more complicated concept than "directed paths between nodes" and "nodes without any common ancestors" in Pearl; and similarly, conditional orthogonality will be much more complicated than time and orthogonality in our paradigm. Though I do think that conditional orthogonality has a much simpler and nicer definition than d-separation.

We'll begin with the definition of conditional history. We again have a fixed finite set as our context. Let $F=(S,B)$ be a finite factored set, let $X,Y,Z\in \text{Part}\left(S\right)$, and let $E\subseteq S$.

The conditional history of $X$ given $E$, written $h^F\left(X|E\right)$, is the smallest set of factors $H\subseteq B$ satisfying the following two conditions:

• For all $s,t\in E$, if $s{\sim }_{b}t$ for all $b\in H$, then $s{\sim }_{X}t$.
• For all $s,t\in E$ and $r\in S$, if $r{\sim }_{b_0}s$ for all $b_0\in H$ and $r{\sim }_{b_1}t$ for all $b_1\in B\setminus H$, then $r\in E$.

The first condition is much like the condition we had in our definition of history, except we're going to make the assumption that we're in $E$. So the first condition is: if all you know about an object is that it's in $E$, and you want to know which part it's in within $X$, it suffices for me to tell you which part it's in within each factor in the history $H$.

Our second condition is not actually going to mention $X$. It's going to be a relationship between $E$ and $H$. And it says that if you want to figure out whether an element of $S$ is in $E$, it's sufficient to parallelize and ask two questions:

• "If I only look at the values of the factors in $H$, is 'this point is in $E$' compatible with that information?"
• "If I only look at the values of the factors in $B\setminus H$, is 'this point is in $E$' compatible with that information?"

If both of these questions return "yes", then the point has to be in $E$.

I am not going to give an intuition about why this needs to be a part of the definition. I will say that without this second condition, conditional history would not even be well-defined, because it wouldn't be closed under intersection. And so I wouldn't be able to take the smallest set of factors in the subset ordering.

Instead of justifying this definition by explaining the intuitions behind it, I'm going to justify it by using it and appealing to its consequences.

We're going to use conditional history to define conditional orthogonality, just like we used history to define orthogonality. We say that $X$ and $Y$ are orthogonal given $E\subseteq S$, written $X{\perp }^{F}Y\mid E$, if the history of $X$ given $E$ is disjoint from the history of $Y$ given $E$: $h^F\left(X|E\right)\cap h^F\left(Y|E\right)=\left\{\right\}$.

We say $X$ and $Y$ are orthogonal given $Z\in \text{Part}\left(S\right)$, written $X{\perp }^{F}Y\mid Z$, if $X{\perp }^{F}Y\mid z$ for all $z\in Z$. So what it means to be orthogonal given a partition is just to be orthogonal given each individual way that the partition might be, each individual part in that partition.

I've been working with this for a while and it feels pretty natural to me, but I don't have a good way to push the naturalness of this condition. So again, I instead want to appeal to the consequences.

2b. $\text{Compositional Semigraphoid Axioms}$

Conditional orthogonality satisfies the compositional semigraphoid axioms, which means finite factored sets are pretty well-behaved. Let $F=(S,B)$ be a finite factored set, and let $X,Y,Z,W\in \text{Part}\left(S\right)$ be partitions of $S$. Then:

• If $X{\perp }^{F}Y\mid Z$, then $Y{\perp }^{F}X\mid Z$. (symmetry)
• If $X{\perp }^F\left(Y{\vee }_{S}W\right)\mid Z$, then $X{\perp }^{F}Y\mid Z$ and $X{\perp }^{F}W\mid Z$. (decomposition)
• If $X{\perp }^F\left(Y{\vee }_{S}W\right)\mid Z$, then $X{\perp }^{F}Y\mid \left(Z{\vee }_{S}W\right)$. (weak union)
• If $X{\perp }^{F}Y\mid Z$ and $X{\perp }^{F}W\mid \left(Z{\vee }_{S}Y\right)$, then $X{\perp }^F\left(Y{\vee }_{S}W\right)\mid Z$. (contraction)
• If $X{\perp }^{F}Y\mid Z$ and If $X{\perp }^{F}W\mid Z$, then $X{\perp }^F\left(Y{\vee }_{S}W\right)\mid Z$. (composition)

The first four properties here make up the semigraphoid axioms, slightly modified because I'm working with partitions rather than sets of variables, so union is replaced with common refinement. There's another graphoid axiom which we're not going to satisfy; but I argue that we don't want to satisfy it, because it doesn't play well with determinism.

The fifth property here, composition, is maybe one of the most unintuitive, because it's not exactly satisfied by probabilistic independence.

Decomposition and composition act like converses of each other. Together, conditioning on $Z$ throughout, they say that $X$ is orthogonal to both $Y$ and $W$ if and only if $X$ is orthogonal to the common refinement of $Y$ and $W$.

2b. $\text{The Fundamental Theorem}$

In addition to being well-behaved, I also want to show that conditional orthogonality is pretty powerful. The way I want to do this is by showing that conditional orthogonality exactly corresponds to conditional independence in all probability distributions you can put on your finite factored set. Thus, much like d-separation in the Pearlian picture, conditional orthogonality can be thought of as a combinatorial version of probabilistic independence.

A probability distribution on a finite factored set $F=(S,B)$ is a probability distribution $P$ on $S$ that can be thought of as coming from a bunch of independent probability distributions on each of the factors in $B$. So $P\left(s\right)={\prod }_{b\in B}P\left(\right[s{]}_b)$ for all $s\in S$.