How to Throw Away Information in Causal DAGs

post by johnswentworth · 2020-01-08T02:40:05.489Z · LW · GW · 2 comments

Contents

  Modifying Children
None
2 comments

When constructing a high-level abstract causal DAG from a low-level DAG, one operation which comes up quite often is throwing away information from a node. This post is about how to do that.

First, how do we throw away information from random variables in general? Sparknotes:

• Given a random variable $X$, we can throw away information by replacing $X$ with $f\left(X\right)$ for some function $f$.
• Given some other random variable $Y$, $f\left(X\right)$ “contains all information in $X$ relevant to $Y$” if and only if $P\left[Y|f\right(X\left)\right]=P\left[Y|X\right]$. In particular, the full distribution function ($y\to P[Y=y|X]$) is a minimal representation of the information about Y contained in X.

For more explanation of this, see Probability as Minimal Map [LW · GW].

For our purposes, starting from a low-level causal DAG, we want to:

• Pick a node $X_i$
• Pick a set of nodes $X_S$ (with $i\in S$)
• Replace $X_i$ by $f\left(X_i\right)$ for some function $f$, such that
• $P\left[X_{\overline{S}}|f\right(X_i\left)\right]=P\left[X_{\overline{S}}|X_i\right]$

Here $\overline{S}$ denotes all the node indices outside $S$. (Specifying $S$ rather than $\overline{S}$ directly will usually be easier in practice, since $X_S$ is usually a small neighborhood of nodes around $X_i$.) In English: we want to throw away information from $X_i$, while retaining all information relevant to nodes outside the set $S$.

Two prototypical examples:

• In a digital circuit, we pick the voltage in a particular wire at a particular time as $X_i$. Assuming the circuit is well designed, we will find that only the binary value $bin\left(X_i\right)$ is relevant to voltages far away in the circuit or in time. So, with all “nearby” voltages as $X_S$, we can replace $X_i$ by $bin\left(X_i\right)$.
• In a fluid, we pick the (microscopic) positions and momenta of all the particles in a little cell of spacetime as $X_i$. Assuming uniform temperature, identical particles, and some source of external noise - even just a little bit - we expect that only the total number and momentum of particles in the cell will be relevant to the positions and momenta of particles far away in space and time. So, with all “nearby” cells/particles as $X_S$, we can replace the microscopic positions and momenta of all particles in the cell with the total number and momentum of particles in the cell.

In both examples, we’re throwing out “local” information, while maintaining any information which is relevant “globally”. This will mean that local queries - e.g. the voltage in one wire given the voltage in a neighboring wire at the same time - are not supported; short-range correlations violate the abstraction. However, large-scale queries - e.g. the voltage in a wire now given the voltage in a wire a few seconds ago - are supported.

Modifying Children

We still have one conceptual question to address: when we replace $X_i$ by $f\left(X_i\right)$, how do we modify children nodes of $X_i$ to use $f\left(X_i\right)$ instead?

The first and most important answer is: it doesn’t matter, so long as whatever they do is consistent with $f\left(X_i\right)$. For instance, suppose $X_i$ ranges over {-1, 0, 1}, and $f\left(X_i\right)=X_i^2$. When $f\left(X_i\right)=1$, the children can act as though $X_i$ were -1 or 1 - it doesn’t matter which, so long as they don’t act like $X_i=0$. As long as the childrens’ behavior is consistent with the information in $f\left(X_i\right)$, we will be able to support long-range queries.

There is one big catch, however: the children do need to all behave as if $X_i$ had the same value, whatever value they choose. The joint distribution $P[X_{ch\left(i\right)}|X_{sp\left(i\right)},f(X_i\left)\right]$ (where $ch\left(i\right)$ = children of $i$ and $sp\left(i\right)$ = spouses of $i$) must be equal to $P\left[X_{ch}\right(i\left)|X_{sp}\right(i),X_i^{\ast }]$ for some value $X_i^{\ast }$ consistent with $f\left(X_i\right)$. The simplest way to achieve this is to pick a particular “representative” value $X_i^{\ast }\left(f^{\ast }\right)$ for each possible value $f^{\ast }$ of $f\left(X_i\right)$, so that $f\left(X_i^{\ast }\right(f^{\ast }\left)\right)=f^{\ast }$.

Example: in the digital circuit case, we would pick one representative “high” voltage (for instance the supply voltage $V_{DD}$) and one representative “low” voltage (for instance the ground voltage $V_{SS}$). $X_i^{\ast }\left(f\right(X_i\left)\right)$ would then map any high voltages to $V_{DD}$ and any low voltages to $V_{SS}$.

Once we have our representative value function $X_i^{\ast }\left(f\right(X_i\left)\right)$, we just have the children use $X_i^{\ast }\left(f\right(X_i\left)\right)$ in place of $X_i$.

If we want, we could even simplify one step further: we could just choose $f$ to spit out representative values directly. That convention is cleaner for proofs and algorithms, but a bit more confusing for human usage and examples.

2 comments

Comments sorted by top scores.