Finite Factored Sets: Applications

post by Scott Garrabrant · 2021-08-31T21:19:03.570Z · LW · GW · 1 comments

Contents

  7.1. Inference
    Decidability of Temporal Inference
    Efficient Temporal Inference
    Temporal Inference from Raw Data and Fewer Ontological Assumptions
    Causality, Determinism, and Abstraction
    Conceptual Inference
    Inferring Time without Orthogonality
    Inferring Conditioned Finite Factored Sets
  7.2. Infinity
    The Fundamental Theorem of Finitely Generated Factored Sets
    Orthogonality and Time in Arbitrary Factored Sets
    Continuity and Physics
  7.3. Embedded Agency
    Embedded Observations
    Counterfactability
    Cartesian Frames
    Unraveling Causal Loops
    Conditional Time
    Logical Causality
    Orthogonality as Simplifying Assumptions for Decisions
    Conditional Orthogonality and Abstractions
None
1 comment

We will now discuss several different applications and directions for future work on finite factored sets [? · GW]. We will divide these research directions into three categories: 'Inference,' 'Infinity,' and 'Embedded Agency.'

This post will be much more speculative than the previous posts. It is very likely that some of these avenues for research will turn out to be dead ends, and some of the claims made here may not hold up to further investigation.

 

7.1. Inference

Decidability of Temporal Inference

In Finite Factored Sets: Inferring Time [LW · GW], we described a combinatorial problem of inferring temporal relations from an orthogonality database. However, it is not clear whether the question "Does a given temporal relation follow from a given orthogonality database?" is decidable.

One way we could hope to decide whether a temporal relation follows from some orthogonality database $D$ over $\Omega$ would be to simply check all factored set models of $\Omega$ that model $D$ up to a given size, and see whether the temporal relation always holds. For this to work, we would need an upper bound on the size of factored sets that we need to consider, as a function of the size of $\Omega$. (Note that the existence of such a bound would not mean that there are no models larger than this upper bound. Rather, it would mean that every model larger than this will have all of the same temporal relations as some smaller model.)

 

Efficient Temporal Inference

Assuming temporal inference is computable, we would further like to be able to infer temporal relations from an orthogonality database quickly.

The naive way to get negative results in temporal inference (i.e., to show that certain temporal relations need not hold) would be to search over the space of models. Without the upper bound discussed above, however, this method would only ever yield negative results.

The naive way to get positive results would be to formalize the kind of reasoning used to prove Propositions 34 and 36 [LW · GW], and search over proofs of this form. It is unclear whether this method can be made efficient.

Alternatively, we could hope to develop some new results and refine our understanding of temporal inference to the point where an alternative method can be made efficient.

 

Temporal Inference from Raw Data and Fewer Ontological Assumptions

In the Pearlian causal inference paradigm, we can infer temporal relationships from joint distributions on a collection of variables.

In Pearl's paradigm, however, this data is already factored into a collection of variables at the outset. Further, the Pearlian paradigm does not make explicit the assumptions that go into this factorization.

Our paradigm instead starts from a distribution on some set of observably distinct worlds. This approach allows us to make fewer ontological assumptions; we don't need to take for granted a particular way the world should be factored into variables. Thus, one might hope that the factored sets paradigm could be used to infer time or causality more directly from raw probabilistic data.

 

Causality, Determinism, and Abstraction

Another issue with the Pearlian causal inference paradigm is that it does not work well in cases where some of the variables are (partially) deterministic functions of each other. Our paradigm has determinism and abstraction built in, so it can be used to infer time in situations where the Pearlian paradigm might not apply.

 

Conceptual Inference

In Example 1 [LW · GW], we can infer that $X{<}_{D}Y$. We can think of this fact as being about time. However, we can also think of it as being about which concepts are more natural or fundamental. In that example, $X$ and $V$ were more primitive variables, while $Y$ was a more derived variable that was computed from $X$ and $V$.

Suppose we had a symbol that was either 0 or 1, chosen according to some probability, and was also colored either blue or green, chosen independently according to some other probability. We can reason about this symbol using concepts like color or number. Alternatively, we could define a new concept bleen meaning "the symbol is either blue and 0, or green and 1," and grue, meaning "the symbol is either green and 0, or blue and 1," and use these two concepts instead.

We want to say that color and number are in some sense better or more useful concepts, while bleen and grue are less useful. Finite factored sets help give formal content to the idea that color and number are more primitive, while bleen and grue are more derived; and this primitiveness seems to point at part of what it means to be a good concept for the purpose of thinking about the world.

 

Inferring Time without Orthogonality

In this sequence, we have focused on inferring time from an orthogonality database. Such a database may have been inferred in turn from observed independence and dependence facts drawn from a probability distribution.

We could instead consider inferring time directly from a probability distribution. Cutting out the orthogonality database in this way could even allow us to infer time from a probability distribution that has no nontrivial conditional independencies at all.

To see why it might be possible to infer time without any orthogonality, consider a set $\Omega$, and a model of $\Omega$, $(F,f)$, where $F=(S,B)$ has $n$ binary factors, and $|\Omega |>n+1$.

There are $n$ degrees of freedom in an arbitrary probability distribution on $F$, and thus at most $n$ degrees of freedom in a probability distribution $P$ on $\Omega$ that comes from a probability distribution on $F$. However, there are $|\Omega -1|$ degrees of freedom in an arbitrary distribution on $\Omega$.

As such, the probability distribution on $\Omega$ will lie on some surface without full dimension in the space of probability distributions on $\Omega$, which could be used to infer some of the properties of $F$.

However, if $|\Omega |$ is much smaller than $|S|$, and $f$ is chosen at random, it is unlikely that there will be any conditional orthogonality relations on partitions of $\Omega$ at all (other than the trivial conditional orthogonality relations that come from one partition being finer than another).

 

Inferring Conditioned Finite Factored Sets

If we modify the temporal inference definition to instead allow for $f$ to be a partial function from $S$ to $\Omega$, we get a new, weaker model of temporal inference. This can be thought of as allowing for the possibility that our distribution on $\Omega$ passes through some filter that only shows us some of the observably distinct worlds.

 

7.2. Infinity

The Fundamental Theorem of Finitely Generated Factored Sets

Throughout this sequence, we have assumed finiteness fairly gratuitously. It is likely that many of the results can be extended to arbitrary finite sets. However, this generalization will not be immediate. Indeed, even history [? · GW] is not well-defined on arbitrary factored sets.

One intermediate possibility is to consider finite-dimensional [LW · GW] factored sets. In this case, history would be well-defined, but our proof of the fundamental theorem would not directly generalize. However, we conjecture that the finite-dimensional analogue of the fundamental theorem [LW · GW] would in fact hold.

Conjecture 1. Theorem 3 [LW · GW] can be generalized to finite-dimensional factored sets.

On the other hand, we do not expect the fundamental theorem to generalize to arbitrary factored sets. To see why, consider the following example.

Example 3. Let $F=(S,B)$, where $S=P\left(N\right)$, $b_n=\left\{\right\{s\in S\mid n\in s\},\{s\in S\mid n\notin s\left\}\right\}$, and $B=\{b_n\mid n\in N\}$. Let $X=\left\{\right\{\left\{\right\}\},S\setminus \{\left\{\right\}\left\}\right\}$, and let $Y=\left\{\right\{N\},S\setminus \{N\left\}\right\}$. 

In this example, it seems that in the correct generalization of orthogonality to arbitrary factored sets, we likely want to say that $X$ is not orthogonal to $Y$. However, it also seems like we want to say that in every distribution on $F$, at least one of $\left\{\right\{\left\}\right\}$ and $\left\{N\right\}$ has probability zero, so this should give a counterexample to the fundamental theorem. 

Even without the fundamental theorem, we believe that orthogonality and time in arbitrary-dimensional factored sets will be important and interesting.

 

Orthogonality and Time in Arbitrary Factored Sets

In the infinite-dimensional case, it is not even clear how we should define orthogonality, time, and conditional orthogonality. There are three main contenders.

First, we could say that (sub)partitions $X$ and $Y$ are orthogonal if there exist disjoint $C_X,C_Y\subseteq B$ such that $C_X{⊢}^{F}X$ and $C_Y{⊢}^{F}Y$. We could then define time as a closure property on orthogonality.

Second, we could just define the history of a (sub)partition $X$ to be the intersection of all $C\subseteq B$ such that $C{⊢}^{F}X$, and leave the definitions of orthogonality and time alone. This second option has some unintuitive behavior. Consider the following example.

Example 4. Let $F=(S,B)$, where $S=P\left(N\right)$, $b_n=\left\{\right\{s\in S\mid n\in s\},\{s\in S\mid n\notin s\left\}\right\}$, and $B=\{b_n\mid n\in N\}$. Let $Z=\left\{\right\{s\in S\mid |s|<\infty \},\{s\in S\mid |s|=\infty \left\}\right\}$.

In this example, $Z$ is orthogonal to itself according to the second option, in spite of having more than one part. However, it is possible that this is a feature, rather than a bug, since it seems to interact nicely with Kolmogorov's zero–one law.

Third, we could define a way to flatten factored sets by merging some of the factors into their common refinement, and we could say $X$ and $Y$ are orthogonal given $Z$ in $F$ if $X$ and $Y$ are orthogonal given $Z$ in some finite-dimensional flattening of $F$. 

The main difference between the first and third options comes from the case where $Z$ has infinitely many parts. In the third option, we must fix a single finite-dimensional flattening such that $X|z$ and $Y|z$ have disjoint histories for all $z\in Z$.

We are most optimistic about the third option, because we conjecture that it can satisfy the compositional semigraphoid axioms, while the other two options cannot. It is also possible that other options give the compositional semigraphoid axioms for partitions with finitely many parts, but not general partitions.

 

Continuity and Physics

A major reason why we are interested in exploring arbitrary-dimensional factored sets is because it could allow us to talk about continuous time. 

The Pearlian paradigm takes advantage of the parenthood relationship between nodes to make inferences. E.g., the nodes are thought of as probabilistic functions of their parents, and the existence of edges between nodes is a central part of temporal inference.

In the factored set paradigm, there is no mention of parenthood; instead, ${\le }^F$ is both reflexive and transitive, and so can be thought of as an ancestry relation. Further, by working with arbitrary partitions rather than a fixed collection of variables, we allow for "zooming in" on our variables.

These two properties together suggest that the factored set paradigm is much closer to being able to talk about continuous time, if the theory can be extended naturally to infinite dimensions.

As pointed out by Eliezer Yudkowsky in his blog post "Causal Universes [LW · GW],'' physics looks an awful lot like a continuous analogue of Pearlian causal diagrams. We are thus hopeful that when extended to arbitrary dimensions, factored sets could provide a useful new way of looking at physics.

 

7.3. Embedded Agency

Embedded Observations

We can use finite factored sets to build a new way of thinking about observations.

Definition 46 (observes an event). Let $F=(S,B)$ be a finite factored set. Let $A$ and $W$ be partitions of $S$, and let $E$ be a subset of $S$. Let $X_E$ be the partition of $S$ given by $X_E=\left\{S\right\}$ if $E=\left\{\right\}$ or $E=S$, and $X_E=\{E,S\setminus E\}$ otherwise. We say $A$ observes $E$ with respect to $W$ (in $F$) if the following two conditions hold.

1. $A{\perp }^F{X}_E$.
2. $A{\perp }^{F}W|S\setminus E$.

$A$ can be thought of as an agent, with the different parts in $A$ representing options available to $A$. $E$ represents some fact about the world. $W$ can be thought of as some high-level world model. We will especially think of $W$ as a model that captures all of the information about the world that the agent cares about.

When we say that $A$ observes $E$, this does not necessarily mean that $E$ holds. Rather, we are saying that $A$ can safely assume that $E$ holds. $A$ can safely make this assumption if it is the case that $A$'s choice can't affect whether $E$ holds, and if, when $E$ does not hold, $A$'s choice can have no effect on any part of the world that $A$ cares about. This is exactly what is represented by the two conditions in Definition 46.

In Drescher's transparent Newcomb thought experiment, the agent cannot be said to observe the contents of the box, because the first condition in Definition 46 is violated. In Nesov's counterfactual mugging [LW · GW] thought experiment, the agent cannot be said to observe the result of the coin flip, because the second condition is violated.

We can extend this definition to give a notion of an agent observing a partition rather than an event. 

Definition 47 (observes a partition). Let $F=(S,B)$ be a finite factored set. Let $A$, $W$, and $X$ be partitions of $S$. Let $X=\{x_0,\dots ,x_{n-1}\}$. We say $A$ observes $X$ with respect to $W$ (in $F$) if $A{\perp }^{F}X$ and there exist partitions of $S$, $A_i$ for $i\in \{0,\dots ,n-1\}$ such that

1. $A={\bigvee }_S\left(\right\{A_i\mid i\in \{0,\dots ,n-1\}\left\}\right)$.
2. $A_i{\perp }^{F}W|S\setminus x_i$.

Saying that $A$ observes $X$ is roughly saying that $A$ can be divided into subagents, where each subagent observes a different part in $X$.

 

Counterfactability

The factored set paradigm also has some interesting things to say about counterfactuals. The chimera functions [? · GW] can be thought of representing a way of taking counterfactuals.

Given a finite factored set $F=(S,B)$, $C\subseteq B$, and $s,t\in S$, let $X_C={\bigvee }_S\left(C\right)$.

We can think of ${\chi }_C^F(s,t)$ as the result of starting with $t$, then performing a counterfactual surgery that changes the value of $X_C$ to match its value in $s$.

Unfortunately, while we can tell this story for $X_C$, we cannot tell the same story for an arbitrary partition of $S$.

Definition 48 (counterfactability). Given a finite factored set $F=(S,B)$, a partition $X\in \text{Part}\left(S\right)$ is called counterfactable (in $F$) if $X={\bigvee }_S\left(h^F\right(X\left)\right)$.

When a partition $X$ is counterfactable, the chimera function gives a well-defined way to start with an element of $S$, and change it by changing what part in $X$ it is in.

Being counterfactable is rather strong, but we have a weaker notion of relative counterfactability.

Definition 49 (relative counterfactability). Given a finite factored set $F=(S,B)$, a partition $X\in \text{Part}\left(S\right)$ is called counterfactable relative to another partition $W\in \text{Part}\left(S\right)$ (in $F$) if ${\bigvee }_S\left(h^F\right(X\left)\right){\perp }^{F}W|X$.

$X$ is counterfactable relative to $W$ if $X$ screens off the history of $X$ from $W$. This means that if we want to counterfact on the value of $X$, we can safely counterfact on the finer partition ${\bigvee }_S\left(h^F\right(X\left)\right)$. As long as we only care about what part in $W$ the result is in, choices about which subpart in ${\bigvee }_S\left(h^F\right(X\left)\right)$ to counterfact will not matter, so we can think of counterfacting on the value of $X$ as well-defined up to the partition $W$.

This notion of counterfactability explains why counterfactuals sometimes seem clear, and other times they do not seem well-defined. In the factored set ontology, sometimes partitions are not counterfactable because they are not fine enough to fully specify all the effects of the counterfactual.

 

Cartesian Frames

The factored set paradigm can be seen as capturing many of the benefits of the Cartesian frame [? · GW] paradigm. We have already seen this in part in our discussion of embedded observations. We feel that the factored set paradigm successfully captures a meaningful notion of time, while the Cartesian frame paradigm mostly fails at this goal.

The connection between factored sets and Cartesian frames is rather strong. For example, a 2-dimensional factored set model of a set $W$ is in effect a Cartesian frame over $W$. The only difference is that the factored set model forgets which factor is the agent, and which factor is the environment. When one Cartesian frame over $W$ is a multiplicative subagent of another, we can construct a 3-dimensional factored set model of $W$, with the subagent represented by one of the factors, and the superagent represented by a pair of the factors.

 

Unraveling Causal Loops

Whenever an agent makes a decision, there is a temptation to think of the effects of the decision as causally "before" the decision being made. This is because the agent uses its model of the effects as an input when making the decision. This causes a problem, because the effects of the decision can of course also be seen as causally after the decision being made.

On our view, part of what is going on is that there is a distinction between the agent's model of the effects, and the effects themselves. The problem is that the agent's model of the effects is highly entangled with the actual effects, which is why we feel tempted to combine them in the first place.

One way to model this situation is by thinking of the agent's model of the effects as being a coarser version of the actual world state after the decision. It is thus possible for the model of the effects to be before the decision, which is before the effects themselves.

By allowing for some variables to be coarsenings or refinements of other variables, the factored set paradigm possibly gives us the tools to be able to straighten out these causal loops.

 

Conditional Time

We can define conditional time similarly to how we define conditional orthogonality.

Definition 50 (conditional time). Given a finite factored set $F=(S,B)$, partitions $X,Y\in \text{Part}\left(S\right)$, and $E\subseteq S$, we say that $X$ is before $Y$ given $E$ (in $F$), written $X{\le }^{F}Y\mid E$, if $h^F\left(X|E\right)\subseteq h^F\left(Y|E\right)$.

It is not clear if this notion has any important philosophical meaning, but it seems plausible that it does. In particular, this notion could be useful for reasoning about situations where time appears to flow in multiple directions at different levels of description, or under different assumptions. Incorporating conditional time could then be used to flatten some causal loops.

 

Logical Causality

Upon discovering logical induction, one of the first things we considered was the possibility of inferring logical causality using our probabilities on logical sentences. We considered doing this using the Pearlian paradigm, but it now seems like that approach was doomed to fail, because we had many deterministic relationships between our variables.

The factored set paradigm seems much closer to allowing us to correctly infer logical causality from logical probabilities, but it is still far from ready. 

One major obstacle is that the factored set paradigm does not have a reasonable way to think about the uniform distribution on a four-element set. The independence structure of the uniform distribution on a four-element set is not a compositional semigraphoid, because if we take $X$, $Y$, and $Z$ to be the three partitions that partition the four-element set into two parts of size two, then $X$ is independent of $Y$ and of $Z$, but not independent of the common refinement of $Y$ and $Z$.

Since the uniform distribution on a four-element set will likely (approximately) show up many times in logical induction, it is not clear how to do the causal inference.

 

Orthogonality as Simplifying Assumptions for Decisions

While we largely have been thinking of orthogonality as a property of the world, one could also think of orthogonality as something that an agent assumes to make decisions.

For example, when an agent is looking at a coin that came up heads, the agent might make the assumption that its decision has no effect on the worlds in which the coin came up tails. This assumption might only be approximately true, but part of being an embedded agent is working with approximations. Orthogonality seems like a useful language for some of the simplifying assumptions agents might make.

 

Conditional Orthogonality and Abstractions

Given some complicated structure $X$, one might want to know when a simpler structure $Y$ is a good abstraction for $X$. One desirable property of an abstraction is that $Y$ screens off $X$ from all of the properties of the world that an agent cares about, $W$. In this way, by thinking in terms of $Y$, the agent does not risk missing any important information.

We could also consider weaker notions than this, by taking $W$ to just be that which the agent cares about within a certain context in which the agent is using the abstraction. 

This is all very vague and rough, but the point is that conditional orthogonality seems related to what makes a good abstraction, so being able to talk about conditional orthogonality and abstractions together seems like it could prove useful.

1 comments

Comments sorted by top scores.