andrey.tabu#

andrey.tabu(data, *, score_func=None, lambda_value=1.0, tabu_length=10, max_tabu=None, max_iter=None, knowledge=None)[source]#

Learn a CPDAG from observational data with tabu search.

Tabu search is hill climbing that also takes non-improving moves and never returns to a recently visited DAG [1] [2] [3]. Moves are scored as in andrey.hc(). The result is the CPDAG of the best-scoring DAG visited.

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, or "local_score_BDeu" or "local_score_BIC_categorical", the BDeu score or the multinomial BIC for categorical data coded by whole numbers, as for ges(). None picks "local_score_BDeu" when every column is categorical (a DataFrame’s category, bool, or text column, or a column of at most 10 distinct whole numbers) and warns with a DataTypeWarning; otherwise it picks "local_score_BIC_from_cov", on mixed data too, since tabu search has no mixed-data score. 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.
tabu_length (int) – Number of most recently visited DAGs a move may not return to. At least 1.
max_tabu (int | None) – Non-improving moves allowed without a better DAG, from 1 to tabu_length. None uses tabu_length.
max_iter (int | None) – Maximum moves, improving or not, at least 1; None sets no limit. The search still terminates: non-improving runs are bounded by max_tabu, and each new best DAG scores strictly lower.
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 "Tabu" and metadata["score"] the best DAG’s 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 names no score tabu search takes.
TypeError – If tabu_length, max_tabu, or a given max_iter is not an int. Also if knowledge is neither None nor a Knowledge.
ValueError – If lambda_value is negative or non-finite, if tabu_length or a given max_iter is less than 1, if max_tabu is outside 1..tabu_length, or, with a categorical score, if data holds a number that is not whole. 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:

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 every column is categorical, so the search scores with BDeu; once per process.

Notes

The search starts from the empty graph. Each step adds the current DAG to the tabu list, which keeps the last tabu_length DAGs visited, then takes the best improving move outside the list. Without one, it stops if max_tabu non-improving moves have occurred since the best score last improved; otherwise it takes the best non-improving move, leaving the score unchanged or worse. It also stops when every legal move leads into the list, or after max_iter moves when set.

Until it leaves its first local optimum, the search takes the same moves as andrey.hc(), so with the same max_iter its score is never worse than hill climbing’s. Ties between moves break as they do for andrey.hc().

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 2 s at 800 variables and under a minute at 3,200, on 4 cores. It takes hill climbing’s moves plus up to max_tabu non-improving moves between new best scores, with no move limit by default; run time grows with the moves taken. It avoids only the last tabu_length DAGs, so a better DAG beyond that reach may be missed. 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. With a categorical score, its tests run it on small fixed categorical networks.

References

Examples

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