Background knowledge

Download this notebook

You often know part of the answer before you look at the data: a cause comes before its effect in time, a treatment was given before the outcome was measured, or an earlier study settled one link. andrey.Knowledge passes what you know to a search, which then returns only graphs that agree with it. Here PC finds every pair of a simulated graph but cannot orient a single edge; ordering the variables in time orients nearly all of them.

Start

Choose a CPU runtime and run this cell first. In Colab it installs andrey-core==0.13.0 from PyPI; local kernels use the installed environment.

import os
import sys

IN_COLAB = "google.colab" in sys.modules

if IN_COLAB:
    os.environ["ANDREY_DEVICE"] = "cpu"
    !pip install --quiet "andrey-core[viz]==0.13.0" pandas

import pandas as pd

import andrey
from andrey.data import sample_scm
from andrey.metrics import shd

A linear-Gaussian model with 10 variables, whose true graph we know. sample_scm lists the columns in an order drawn from the seed, so their order says nothing about the causal order.

sim = sample_scm(d=10, n=2000, density=2, seed=5)
names = [f"x{i}" for i in range(10)]
data = pd.DataFrame(sim.data, columns=names)
truth = sim.graph
print("true edges:", ", ".join(f"{names[a]} -> {names[b]}" for a, b, _ in truth.oriented_edges()))

true edges: x1 -> x0, x0 -> x8, x9 -> x0, x9 -> x1, x7 -> x2, x5 -> x3, x4 -> x6, x7 -> x4, x8 -> x4, x8 -> x7

Without knowledge

PC finds all ten pairs, but the data alone cannot say which way any of them points: every edge is undirected, and each counts as an error against the true graph.

out = andrey.pc(data)
print(out)
print("errors:", shd(out.structure, truth))

pc  cpdag  |  10 nodes  |  10 edges (10 undirected)

  x0 -- x1
  x0 -- x8
  x0 -- x9
  x1 -- x9
  x2 -- x7
  x3 -- x5
  x4 -- x6
  x4 -- x7
  x4 -- x8
  x7 -- x8

  indep_test: fisherz
  tie_break: rank
errors: 10

Tiers

Tiers group the variables in time: no edge may point from a later tier into an earlier one. Say the first three variables were measured at the start, the next four in the middle, and the last three at the end. In this simulation the tiers follow the true causal order, as a domain expert’s would.

knowledge = andrey.Knowledge(
    tiers=[["x9", "x5", "x1"], ["x3", "x0", "x8", "x7"], ["x2", "x4", "x6"]]
)
guided = andrey.pc(data, knowledge=knowledge)
print(guided)
print("errors:", shd(guided.structure, truth))

pc  cpdag  |  10 nodes  |  10 edges (9 directed, 1 undirected)

  x1 -> x0
  x0 -> x8
  x9 -> x0
  x1 -- x9
  x7 -> x2
  x5 -> x3
  x4 -> x6
  x7 -> x4
  x8 -> x4
  x8 -> x7

  indep_test: fisherz
  tie_break: rank
errors: 1

import andrey.viz

andrey.viz.draw(guided.structure)

Required and forbidden edges

When you know one edge, require it; when you know an edge cannot exist, forbid it. Forbidding a -> b forbids that direction only, so forbid both to keep two variables apart. PC then orients the edges these imply.

knowledge = andrey.Knowledge(required=[("x8", "x7")], forbidden=[("x6", "x4")])
out = andrey.pc(data, knowledge=knowledge)
print(out)
print("errors:", shd(out.structure, truth))

pc  cpdag  |  10 nodes  |  10 edges (7 undirected, 3 directed)

  x0 -- x1
  x0 -- x8
  x0 -- x9
  x1 -- x9
  x7 -> x2
  x3 -- x5
  x4 -> x6
  x4 -- x7
  x4 -- x8
  x8 -> x7

  indep_test: fisherz
  tie_break: rank
errors: 7

Every family

The same Knowledge works across families: the constraint-based, score-based, and permutation-based searches, the LiNGAM methods, and the time-series methods, where a link can also name its lag. Each method’s reference page says which parts it honors.

knowledge = andrey.Knowledge(
    tiers=[["x9", "x5", "x1"], ["x3", "x0", "x8", "x7"], ["x2", "x4", "x6"]]
)
for method, settings in [("pc", {}), ("ges", {}), ("boss", {"seed": 0}), ("grasp", {"seed": 0})]:
    fit = getattr(andrey, method)
    before = shd(fit(data, **settings).structure, truth)
    after = shd(fit(data, knowledge=knowledge, **settings).structure, truth)
    print(f"{method:>5}: {before} errors without knowledge, {after} with tiers")

   pc: 10 errors without knowledge, 1 with tiers
  ges: 10 errors without knowledge, 1 with tiers
 boss: 10 errors without knowledge, 1 with tiers
grasp: 10 errors without knowledge, 1 with tiers

Wrong knowledge

A search treats knowledge as fact. Require an edge that is not in the true graph, and the result has it:

wrong = andrey.pc(data, knowledge=andrey.Knowledge(required=[("x9", "x3")]))
print("errors:", shd(wrong.structure, truth))

errors: 11

So pass only what you are sure of. Background knowledge in the getting-started guide covers every part of Knowledge.