andrey.xges#

andrey.xges(data, *, score_func='local_score_BIC', lambda_value=1.0, extended_search=True, knowledge=None)[source]#

Learn a CPDAG from observational data with extremely greedy equivalence search (XGES).

XGES searches the equivalence classes that GES searches [2], with GES’s moves, the turning move of GIES [3], and the BIC score, but applies them in a different order [1] (see Notes). On linear-Gaussian data it often finds a graph with a better score than GES.

Parameters:

data (ArrayLike) – Observed data, one row per sample. Coerced to float64. A DataFrame’s column names become the structure’s labels.
score_func (str) – Only the Gaussian BIC score is supported.
lambda_value (float) – Multiplier on the BIC penalty of log(n_samples) per parent. Larger values give sparser graphs; 1.0 is the standard BIC. Must be finite and non-negative.
extended_search (bool) – Run the extended search after the base search (see Notes). False returns the base search’s graph, which is faster.
knowledge (Knowledge | None) – Background knowledge, a Knowledge: required and forbidden edges, the pairs allowed to be adjacent, and temporal tiers, all honored. No move adds a forbidden edge or removes a required one, and the search starts from the required edges. The result directs every edge the knowledge decides, then Meek’s rules direct the edges that follow, as Knowledge describes.

Returns:

Wraps a cpdag GraphStructure; metadata["algorithm"] is "XGES" and metadata["score"] the BIC score, computed as for andrey.ges(); lower is better. Directed marks (->) are oriented edges, undirected (--) the ones the equivalence class leaves open.

Return type:

StructureOutput

Raises:

NotImplementedError – If score_func is not "local_score_BIC".
TypeError – If extended_search is not a bool. Also if knowledge is neither None nor a Knowledge.
ValueError – If data is not a 2-D numeric matrix with at least two rows and no NaN or inf, if lambda_value is negative or non-finite, or if a column is constant, repeats another column up to scale and shift given more than two rows, or, with more rows than columns, is a linear function of other columns. One message names every group of copies and says to keep one column per group. Also if knowledge names a column data lacks or contradicts itself, as Knowledge lists.

See also

andrey.ges: Adds edges, then removes them, in two separate phases.

Notes

When to use it. XGES makes the assumptions of ges(): continuous data, no unmeasured common causes, and linear relations with Gaussian noise. It returns the equivalence class.

How it works. Each step takes the best improving deletion, else reversal of a directed edge, else addition; the search stops when no move improves the score [1]. The extended search then deletes each edge of that graph, best score first, forbids adding it back in that direction, and reruns the search. It keeps a result whose score is lower by more than 2e-7 * n_samples, and stops once a fresh pass over the edges keeps nothing. No variable has a parent limit. Moves whose score changes are equal after rounding are taken in the order of each column’s rank, as in hc(); the column-order guide says what the rank keeps.

Limitations. Measured on simulated linear-Gaussian data from sparse random graphs (mean degree 2) and denser ones (mean degree 4), from 25 to 1,000 variables with ten rows per variable. On the denser graphs its median errors (SHD) stayed below the empty graph’s at every size. On the sparse graphs they exceeded it from 500 variables on, where the BIC score still preferred the returned graphs to the true one. At 1,000 variables, the median fit took under a minute on the sparse graphs and under five minutes on the denser ones, on one core; with extended_search=False, a few seconds. The extended search reruns the base search for each edge it tries to delete and retries the edges after keeping a result, so its run time grows with the number of edges and of results kept. Its BIC score assumes linear relations with Gaussian noise. With fewer rows than columns the BIC score is unreliable. A parent set of n_samples - 1 or more variables fits its child exactly, so the search never selects one, nor any parent set that leaves its child a residual variance of at most 1e-12 times its variance.

References

Examples

>>> import numpy as np
>>> import pandas as pd
>>> from andrey import xges
>>> rng = np.random.default_rng(0)
>>> x = rng.standard_normal(500)
>>> y = rng.standard_normal(500)
>>> z = x + y + 0.5 * rng.standard_normal(500)
>>> xges(pd.DataFrame({"x": x, "y": y, "z": z})).structure.oriented_edges()
[('x', 'z', 'directed'), ('y', 'z', 'directed')]