Inferring the algorithmic direction of causal pairs
Cristian Grozea – Fraunhofer FIRST
We suggest an approach for obtaining the "correct" direction of a causal pair of
variables, based on the AIT (ref Chaitin for entropy H), using only absolute
complexity.
This is advantageous for practical approximations, as the absolute complexity of an
object (as opposed to the conditional one) can be easily upper bounded by using a
practical compression algorithm.
We assume that an algorithmic process generates output from input:
output=f(input,extrainfo) – where “extrainfo” is the “noise”, seen as supplementary
information needed to implement a precise mapping (ref Janzig for similar setup).
In this framework the generative mapping is implicitly reversible even if the
function is not bijective! Specifically, even if the generative process was X->Y,
another one always exists that goes Y->X, producing X=g(Y,otherinfo). In fact, the
only thing that X can bring to the construction of Y is exactly the same
information that Y can bring to the construction of X, that is their mutual
information.
We break this perfect reversibility by using the principle of least assumption,
which amounts to choosing the direction that requires the least amount of extra
information to build the target variable.
As H(X)=H(X|Y)+I(X,Y), if H(X)>H(Y) then X is elected as “the cause”.