andrey.fci

andrey.fci(data, *, alpha=0.05, indep_test='fisherz', collider_rule='sepsets', categorical=None, max_categories=10, possible_dsep=None, max_depth=None, knowledge=None)

Learn a PAG from observational data with FCI, sound under latent confounders.

FCI extends PC to handle unmeasured common causes (latent confounders) and selection bias [1] [2]. It uses conditional-independence tests to remove edges, then orients their endpoints. The result is a PAG, whose circles (o) mark endpoints the data cannot determine. Use it when unmeasured confounding is plausible.

Parameters:

• data (ArrayLike) – Observed data, one row per sample. Coerced to float64. A DataFrame’s column names become the structure’s labels.

• alpha (float) – Significance level of the conditional-independence test. Smaller values give sparser graphs.

• indep_test (str) – Conditional-independence test. "fisherz" and "student_t" test partial correlation, for continuous data: "fisherz" applies Fisher’s z-transform and the normal distribution; "student_t" applies the Student-t distribution, which is exact for Gaussian data at any sample size. "chisq" (Pearson’s chi-square) and "gsq" (G-square, the likelihood ratio) test categorical data, coded by whole numbers. "degen_gauss" (degenerate Gaussian) and "cond_gauss" (conditional Gaussian) test mixed data, continuous and categorical columns. Four more tests detect nonlinear dependence in continuous data, at a far higher cost per test: "kci" is the kernel test; "rcot" its random-feature approximation; "cmiknn" a nearest-neighbor conditional mutual information test; and "gpdc" Gaussian-process regression with a distance correlation test. See Notes.

• collider_rule (str) – How FCI decides whether z is a collider on a triple x - z - y where x and y are not adjacent. "sepsets" makes it a collider when z is not in the separating set that removed the edge x - y. "majority" tests x and y given every subset of x’s neighbors and every subset of y’s neighbors, and makes it a collider when fewer than half of the separating subsets (p >= alpha) contain z [4]; at exactly half the triple stays unoriented. Majority runs up to 2**degree extra tests per triple.

• categorical (Sequence[str | int] | None) – The categorical columns of data, for a mixed-data test: column labels (strings) or 0-based positions. None infers them: a DataFrame’s category, bool, and text columns, and every column of at most max_categories distinct whole numbers, named in a DataTypeWarning. [] marks none. The other tests take no column types and reject it. See Data types in the getting-started guide.

• max_categories (int) – The most distinct whole numbers a column may hold to be inferred as categorical, at least 2. With a continuous test, columns within it get a one-time DataTypeWarning that they may be category codes.

• possible_dsep (str | None) – The order of FCI’s possible-d-separation step [2] [3], which removes edges the first step kept, one at a time, so each removal changes what the step tests after it. "order_free" visits the pairs and nodes by a rank computed from each column’s own data, so the result does not depend on the column order unless two columns are identical. "fast" visits them in column order. None follows andrey.config.tie_break: "order_free" under "rank", "fast" under "position". See Notes and Limitations.

• max_depth (int | None) – The maximum conditioning-set size of every conditional-independence test, at least 0: 0 runs only unconditional tests, and None sets no limit. A smaller cap runs fewer tests and can keep edges that a larger conditioning set would remove. It caps the tests of the adjacency search, the possible-d-separation step, the majority rule, and the discriminating-path rule.

• knowledge (Knowledge | None) – Background knowledge, a Knowledge: required and forbidden edges, the pairs allowed to be adjacent, and temporal tiers, all honored. The adjacency search starts from the allowed pairs and never removes a required pair; the tests can remove any other allowed pair. A pair the knowledge makes non-adjacent is tested for a separating set, so colliders over it are oriented as usual; when the search finds none within max_depth, no rule reads its unshielded triples as colliders or non-colliders. In the PAG, a forbidden a -> b on an adjacent pair puts an arrowhead at a and can leave a circle at b, and a required one is a -> b; knowledge that puts an arrowhead at a on an edge a - b while its required edges lead from a to b raises ValueError.

Returns:

Wraps a pag GraphStructure; metadata["algorithm"] is "FCI". Endpoints carry arrowheads, tails, or circle marks (o); a bidirected edge (<->) marks a probable latent common cause. Under a mixed-data setting, metadata["categorical"] lists the categorical columns it read, by name or 0-based position.

Return type:

StructureOutput

Raises:

• NotImplementedError – If indep_test names no available test.

• TypeError – If categorical is not a list of column names and positions, or max_categories is not an int. Also if knowledge is neither None nor a Knowledge, or a given max_depth is not an int.

• ValueError – If data has too few samples for a test or a singular correlation matrix, if alpha is not in (0, 1), if collider_rule or possible_dsep is not a supported choice, or if data or categorical does not suit the test, as for pc(). With "fisherz" or "student_t", also if a column repeats another up to scale and shift, before any test runs; one message names every group of copies and says to keep one column per group. Also if a given max_depth is negative, or if knowledge names a column data lacks or contradicts itself, as Knowledge lists.

Warns:

DataTypeWarning – When a mixed-data test infers the categorical columns, or finds none and so runs as the linear-Gaussian form, or when a continuous setting meets columns that look like category codes; each message warns once per process.

See also

andrey.pc

Orients more of the graph, with fewer tests, when every common cause is measured.

Notes

When to use it. FCI suits data that may be affected by unmeasured common causes or sample selection. Its default Fisher-Z test assumes continuous data with linear effects and roughly Gaussian noise; for categorical data, use "chisq" or "gsq", and for mixed data "degen_gauss" or "cond_gauss", which read the data as pc() describes. Its PAG claims less than PC’s CPDAG: an arrowhead at a node rules out that node causing the node at the edge’s other end, and a circle leaves the mark open.

When not to. When every common cause is measured, pc() orients more of the graph with fewer tests. FCI’s possible-d-separation step runs tests PC does not.

Choosing alpha. A larger alpha keeps more edges, true and false.

How it works. FCI runs in three steps. First, it removes edges by conditional-independence tests, as PC does, and orients colliders from the separating sets. Next, it tests each remaining pair given subsets of its possible-d-separation set: nodes that can separate the pair when some causes are unmeasured. It removes pairs found independent and orients colliders again. Last, it applies Zhang’s orientation rules R1-R10 [3] until no mark changes. An endpoint no rule resolves stays a circle.

The rules run in rounds: each round collects the marks every rule implies on the graph as it stands and sets them together, except that an endpoint two of them would mark one as an arrowhead and one as a tail stays a circle. The rounds repeat until no mark changes. Rule R4 decides an endpoint by every shortest discriminating path, so paths whose tests disagree leave it a circle. The orientation rules therefore do not depend on the column order, and with possible_dsep="order_free" neither does the result, unless two columns are identical. With "fast" the result can depend on the column order through the possible-d-separation step. A fixed column order gives reproducible results. Under andrey.config(tie_break="position"), the rules instead fire one at a time in column order, and of two firings that conflict the first decides. possible_dsep then defaults to "fast". The column-order guide lists what reordering the columns does to each method.

Rule R5 turns a cycle of circle-circle edges into undirected edges only if the whole cycle, including the closing edge, is uncovered, that is, no two nodes two steps apart are adjacent. It considers every circle path, up to a fixed search bound, so a covered route through a node never hides an uncovered route through the same node. Rule R8 checks each pair of endpoints in both orders, so whether it fires does not depend on the node labels.

Possible-d-separation set. FCI builds each possible-d-separation set [2] [3] with a search that walks out from one endpoint of the pair and keeps a node when a node it was reached from has a possibly directed path, one with no arrowhead pointing back along it, to the endpoint or to the node. FCI checks a node when the search reaches it, against the nodes it was reached from so far, so the set depends on the order the search visits nodes. The set can be smaller than the published definition of the set [2], so FCI can keep an edge that the published set would remove, even with exact tests. FCI keeps this search because the published set grows quickly with the graph, the search’s set is the one FCI has been measured with, and on simulated data the published set did not give more accurate PAGs. FCI tests every subset of the set, except the empty set and the subsets of either endpoint’s neighbors, which the first step already tested. It visits the pairs one at a time, removes a pair as soon as a subset separates it, and records that subset, so each removal changes the sets of the pairs after it. With possible_dsep="order_free", the pairs, the nodes of each search, and the subsets follow a tie rank computed from each column’s own data, as for hc(), which moves with its column when the columns are reordered; with "fast", they follow the column order.

Separating sets. When several conditioning sets of the same size make a pair independent in the first step, FCI records their union as the pair’s separating set. FCI keeps the union because it does not depend on the order of the tests, and on simulated data it gave more accurate PAGs than the first set found.

Limitations. Measured with possible_dsep="fast" on simulated linear-Gaussian data from random graphs with mean degree 2 or 4 and one variable in ten or one in five hidden, from 20 to 800 variables counting the hidden ones, with 10 or 50 rows per variable, on 4 cores. Its median endpoint errors, each mismatched tail, arrowhead, or circle, stayed below the empty graph’s at every size with mean degree 4, and up to 400 variables with mean degree 2, where they passed it at 800 (2,582 against 1,738 with one variable in ten hidden and ten rows per variable). With those settings the median fit took 0.0064 s at 20 variables and 114 s at 800; with one variable in five hidden and 50 rows per variable it took 78 s at 400 and 4,829 s at 800, where two of five fits ran past 7,200 s. The default, "order_free", took 0.99 to 1.05 times as long as "fast" up to 200 variables and 0.78 to 1.42 times at 400 and 800, and its median endpoint errors were within 2% of "fast"’s. On some graphs from 400 variables its order needs more tests than the column order: on one with 400 variables, mean degree 4, one variable in five hidden, and 50 rows per variable, it took 34 s against 23 to 29 s for "fast" over five column orders. possible_dsep="fast" gives the column-order mode. On the 223-variable ANDES network with 1,000 simulated rows, its median endpoint errors passed the empty graph’s (696 against 676). Rule R5 stops searching a pair after a fixed number of partial paths and leaves its circles, so on graphs with many circle-circle edges it can miss an undirected cycle. With the mixed-data tests, it is experimental and not benchmarked yet; its tests run it on 5 variables with 3,000 rows.

References

[1]

Spirtes, P., Meek, C., and Richardson, T. (1995). Causal inference in the presence of latent variables and selection bias. UAI, 499-506.

[2] (1,2,3,4)

Spirtes, P., Glymour, C., and Scheines, R. (2000). Causation, Prediction, and Search, 2nd ed. MIT Press.

[3] (1,2,3)

Zhang, J. (2008). On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence 172(16-17), 1873-1896.

[4]

Colombo, D., and Maathuis, M. H. (2014). Order-independent constraint-based causal structure learning. JMLR 15, 3921-3962.

Examples

>>> import numpy as np
>>> from andrey import fci
>>> rng = np.random.default_rng(0)
>>> x = rng.standard_normal(500)
>>> y = x + 0.1 * rng.standard_normal(500)
>>> fci(np.column_stack([x, y])).structure.kind
'pag'