andrey.exact_search

andrey.exact_search(data, *, search_method='astar', score_func=None, categorical=None, max_categories=10, knowledge=None)

Learn the globally optimal DAG for a decomposable score by exact search.

The optimum is identified up to its Markov equivalence class, and A* (search_method="astar") [1] and dynamic programming ("dp") [2] return the same DAG of that class. Runtime is exponential in the variable count, so keep the problem small (roughly <= 20 variables).

Parameters:

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

• search_method (str) – Exact search strategy: A* search or dynamic programming.

• score_func (str | None) – Local score: "local_score_BIC", the linear-Gaussian BIC; "local_score_BDeu" or "local_score_BIC_categorical", the BDeu score or the multinomial BIC for categorical data coded by whole numbers; or "local_score_degen_gauss" or "local_score_cond_gauss", the degenerate or conditional Gaussian BIC for mixed data, as for ges(). Each BIC uses the standard penalty, lambda_value=1. None reads the column types from categorical, or infers them, and picks "local_score_BDeu" when every column is categorical or "local_score_cond_gauss" when some are, each with a DataTypeWarning; otherwise it picks "local_score_BIC". Pass "local_score_BIC" to read whole numbers, such as counts, as numbers.

• categorical (Sequence[str | int] | None) – The categorical columns of data, for a mixed-data score: 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 scores 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 score, columns within it get a one-time DataTypeWarning that they may be category codes. With score_func=None, the columns it infers pick the default score.

• knowledge (Knowledge | None) – Background knowledge, a Knowledge: required and forbidden edges, the pairs allowed to be adjacent, and temporal tiers, all honored. Each variable’s parent sets exclude the forbidden parents and include the required ones, so the DAG found is the best one that satisfies the knowledge.

Returns:

Wraps a dag GraphStructure (one DAG of the optimal equivalence class); metadata["algorithm"] is "ExactSearch". 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 score_func names no available score.

• 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.

• ValueError – If search_method is not "astar" or "dp", or if data or categorical does not suit the score, as for ges(). With the BIC score, also if a column repeats another 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.

Warns:

DataTypeWarning – When score_func is None and the columns are all categorical or mixed, so the search scores with BDeu or the conditional Gaussian BIC; when a mixed-data score 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.

Notes

When to use it. With "local_score_BIC", exact search makes the assumptions of ges(): continuous data, no unmeasured common causes, and linear relations with Gaussian noise; the categorical and mixed-data scores below make theirs. It suits a few variables, where it returns a graph with the best score rather than a greedy search’s local optimum.

Tied DAGs. Every DAG of the optimal equivalence class has the same score, so the search’s own pick among them would follow last-bit rounding and the column order. Exact search instead reports one fixed member of the class it found: it keeps the edges every DAG of the class shares, and those the knowledge directs, and orients the others by a rank computed from each column’s own data, as hc() ranks tied moves. The rank moves with the column, so reordering the columns reorders the graph’s nodes and changes nothing else, unless two columns are identical. The rank is arbitrary with respect to causal structure. Rounding differences, such as another CPU’s BLAS kernel makes, leave the reported DAG unchanged whenever they leave the class unchanged; the column-order guide says what the rank keeps.

Categorical data. "local_score_BDeu" [5] and "local_score_BIC_categorical" [6] read each distinct value of a column as one category and score a variable by its counts in each configuration of its parents, as ges() describes. Both give equivalent graphs the same score.

Mixed data. "local_score_degen_gauss" [3] and "local_score_cond_gauss" [4] score data with continuous and categorical columns, as ges() describes, and read the categorical columns as pc() does. Both give equivalent graphs the same score, so the optimum is again identified up to its equivalence class.

Limitations. Measured on simulated linear-Gaussian data from sparse random graphs (mean degree 2), from 5 to 15 variables with ten rows per variable. Its median errors (SHD) stayed below the empty graph’s at every size (7 against 15 at 15 variables). The median fit took 0.11 s at 10 variables and 6.4 s at 15, on 4 cores. With a mixed-data or categorical score it is not benchmarked yet: its tests run it with a mixed-data score on 5 variables with 3,000 rows, and with a categorical score on small fixed categorical networks. It scores every possible parent set of every variable, so its run time at least doubles with each added variable. The "dp" search also keeps one entry per subset of the variables, so its memory doubles as well. 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

[1]

Yuan, C., and Malone, B. (2013). Learning optimal Bayesian networks: a shortest path perspective. https://doi.org/10.1613/jair.4039

[2]

Silander, T., and Myllymaki, P. (2006). A simple approach for finding the globally optimal Bayesian network structure. https://arxiv.org/abs/1206.6875

[3]

Andrews, B., Ramsey, J., and Cooper, G. F. (2019). Learning high-dimensional directed acyclic graphs with mixed data-types. Proceedings of Machine Learning Research 104, 4-21.

[4]

Andrews, B., Ramsey, J., and Cooper, G. F. (2018). Scoring Bayesian networks of mixed variables. International Journal of Data Science and Analytics 6(1), 3-18.

[5]

Heckerman, D., Geiger, D., and Chickering, D. M. (1995). Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning 20(3), 197-243.

[6]

Schwarz, G. (1978). Estimating the dimension of a model. Annals of Statistics 6(2), 461-464.

Examples

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