andrey.hc

andrey.hc(data, *, score_func=None, lambda_value=1.0, max_iter=None, categorical=None, max_categories=10, knowledge=None)

Learn a CPDAG from observational data with hill-climbing search.

The search repeatedly adds, removes, or reverses the edge that most improves the score, a covariance-based delta-BIC by default, then converts the DAG to its Markov equivalence class [1] [2].

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 | None) – Local score objective: "local_score_BIC_from_cov", a covariance-based Gaussian BIC for continuous data; "local_score_BDeu", the BDeu score, or "local_score_BIC_categorical", the multinomial BIC, for categorical data coded by whole numbers; or "local_score_degen_gauss" and "local_score_cond_gauss", the degenerate and conditional Gaussian BICs for mixed data, as for ges(). 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_from_cov". Pass "local_score_BIC_from_cov" to read whole numbers, such as counts, as numbers.

• lambda_value (float) – Multiplier on the BIC penalty of log(n_samples) per parameter: per parent for the Gaussian BIC. Larger values give sparser graphs; 1.0 is the standard BIC. Must be finite and non-negative. BDeu ignores it.

• max_iter (int | None) – Maximum moves, at least 1; None sets no limit. The search still terminates, since each move lowers the score. A given max_iter also bounds the edge count, as each move adds at most one edge.

• 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. 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 "HC" and metadata["score"] the score of the DAG found, computed as for andrey.ges(); lower is better. Directed marks (->) are oriented edges, undirected (--) the ones the equivalence class leaves open. 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 a given max_iter is not an int, 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 lambda_value is negative or non-finite, if a given max_iter is less than 1, 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, or, under a mixed-data score, requires an edge from a continuous into a categorical column.

Warns:

• SearchLimitWarning – When the search takes a given max_iter moves; a larger max_iter may find a better graph.

• 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

The search starts from the empty graph and stops when no single move improves the score, or after max_iter moves when set. Under a mixed-data score, no move gives a categorical column a continuous parent, so the DAG found is a conditional linear Gaussian network.

Under a score-equivalent score, adding x -> y or y -> x from the empty graph gives the same score. Such ties recur during search, and choosing one move can change later moves and the final CPDAG. Each column gets a rank computed from its own data to choose between tied moves, and the rank moves with the column. The column-order guide says what the rank keeps under a new column order and on another machine, and how andrey.config(tie_break="position") orders the ties by column position instead.

Limitations. Measured on simulated linear-Gaussian data from sparse random graphs, from 10 to 3,200 variables with ten rows per variable. From 50 variables on, its median errors (SHD) exceeded the empty graph’s. The median fit took under a second at 800 variables and about 20 s at 3,200, on 4 cores. It has no move limit by default; run time grows with the moves the search takes. A graph that no single move improves need not be the best-scoring one. 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. On simulated mixed data (conditional linear Gaussian networks on sparse random graphs, the first half of the variables categorical with 2 to 5 categories), from 10 to 40 variables with 2,000 rows, its median errors at 40 variables were 12.5 with "local_score_degen_gauss" and 11 with "local_score_cond_gauss", against 40. On simulated categorical networks with 2 or 3 categories per variable, of the same sizes and rows, they were 18 with "local_score_BDeu" and 20 with "local_score_BIC_categorical". Every median fit took under 0.2 s at 40 variables, on 4 cores.

References

[1]

Chickering, D. M., Geiger, D., and Heckerman, D. (1995). Learning Bayesian networks: search methods and experimental results. AISTATS, PMLR R0, 112-128.

[2]

Scutari, M. (2010). Learning Bayesian networks with the bnlearn R package. Journal of Statistical Software 35(3). https://doi.org/10.18637/jss.v035.i03

Examples

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