Indexed identification and finite compiler reference

This is the developer reference for causalscience.indexed_identification in the a13 API. Start with the usage guide for public graph-based and graph-free estimation. These lower-level expression/trace interfaces are experimental and are not substitutes for the public default UCA score path. Install the public CausalScience distribution and use the causalscience interface in these examples. The implementation/source references remain under src/causalengine/.

indexed_identification.py provides a pure symbolic path that imports only NetworkX and the Python standard library. Its graph certificates use explicit private/pair latent roots: each hidden U vertex has at most two observed children; a graph outside this scope is rejected. identify_indexed(G, X, Y, complete_mc=False) first applies Assumption 1 preprocessing, then registers every actual intermediate Q[A] in Tian’s algorithm, including ancestral topological-prefix marginals. Each record keeps its original graph and source, true external-parent signature, full evaluation argument map, original derivations, and any independently verified sequential covariate adjustment (SCA) certificate and raw definition. The verifier tests the supplied full topological order, includes the initial outcome block in history, and deletes future fixed actions before each separation test. It does not depend on the legacy minimum-SCA checker. A supplied ID_return_Ctree success is checked operation by operation; a supplied failure is recomputed for the reduced query.

import networkx as nx
from causalscience.indexed_identification import identify_indexed

# Front-door graph; U0 is an independent latent root.
G = nx.DiGraph([("X", "Z"), ("Z", "Y"), ("U0", "X"), ("U0", "Y")])
result = identify_indexed(G, ["X"], ["Y"], complete_mc=True)
assert result.status == "NONRATIO"
program = result.compile_kpp({"X": (0, 1), "Z": (0, 1), "Y": (0, 1)},
                             {"X": 1, "Y": 1})
# program.expectation(conditional) evaluates the effect for an observational
# callback conditional(outcome_values, conditioning_values, source).

The default is literal intermediate indexing with justified conditional-independence, normalization, chain-rule, and matching numerator/denominator reductions. A summed head slot is normalized only when its context and other head coordinates stay fixed; valid diagonal copied-slot expressions are preserved. Duplicate lexical Sum binders are rejected, while distinct scoped copies remain legal. The explicit complete_mc=True option also searches unions of the induced c-components for an arbitrary disjoint SCA partition. It preserves a separate MC derivation, the accepted mc_partition, and all mc_certificates; it does not claim that the literal trace visited those joint blocks. SCA may enumerate factorially many full orders, and MC union/partition search can be exponential. max_orders and max_mc_unions limit these searches; None removes the corresponding limit. Exhaustion returns UNKNOWN for the affected search, never a negative certificate. NONRATIO certifies one constructed raw nonnegative sum-product; a residual ratio yields UNKNOWN, and a valid Tian identification failure yields the distinct NOT_IDENTIFIABLE status. mc_search_status="NO_MC" means the exhaustive canonical-SCA union search found no accepted partition; the overall non-ratio status remains UNKNOWN unless the literal construction succeeds. indexing_status="UNKNOWN" preserves uncertified original raw c-factors when a seed SCA search is budgeted. No completeness claim for all non-ratio estimands is made.

Registered original-model Q[A] references additionally support parent-locality equality: their original graph, source, head A, and actual head/external-parent arguments must agree. Redundant carried contexts may differ; all original arguments remain attached to the raw expansions. reduce_expression(..., registry=registry, domains=domains) enables this check for references issued by that registry. It does not equate arbitrary observational conditionals, different heads, changed parent values, or unregistered/foreign references. Fixed or aliased arguments require supported finite alphabets; positive denominator support remains an assumption. In the five-node example, the final Q[M] and the prefix Q[M] in the derivation of Q[Y]=Q[M,Y]/Q[M] share the same m,r and cancel across final factors.

compile_kpp and result.compile_kpp implement fixed_payoff_expectation only. They check finite alphabets and the raw nonnegative grammar, explicitly expand finite sums, and assign independent copied outputs to every kernel occurrence. A known selector samples a term; its weighted indicator payoff has the desired expectation. Original coordinate alphabets, bound-slot alphabets, and evaluated argument support are checked before normalization can erase a coordinate or context. draw_payoff evaluates only the selected term, equivalently integrating out unused independent draws; it is not a full path sampler or an original-outcome-marginal compiler. Unresolved ratios, unsupported evaluation values, and max_terms exhaustion fail explicitly. Nonfinite reduced/expanded coefficients and selector scaled payoffs are rejected, including floating-point overflow. Conditional support is required from the source. This compiler does not fit a UCA/DML estimator or guarantee a computational advantage at equal statistical accuracy.

compile_kpp_trace(expression, domains, fixed_values) is a separate, nonexpanded formula-tree evaluator. It supports finite nonnegative Scalar, raw ObsKernel, binary Add, Product, and lexical Sum. A uniform selector chooses one Add child; each Sum samples its coordinates uniformly. Inverse proposal weights restore the sums. Product occurrences draw fresh internal choices while preserving shared outer bindings. Compilation walks formula occurrences and checks the supplied finite alphabet lists; neither compilation nor a trace constructs a Cartesian assignment grid or distributes products into monomials. Domain-list scans, known proposal/vector draws, predictions, arithmetic, and precision costs are still paid.

The returned TraceProgram has leaves, occurrence_count, weight_bound, and mode fitted_cell_trace_expectation. Its draw_value(predict_cell, rng) evaluates a weighted product of fixed fitted conditional-cell predictions; its callback is predict_cell(leaf_index, outcome_values, given_values, source). It never samples raw nature outputs. Every occurrence has its own leaf index even when a subtree is reused. Predictions must lie in [0,1], but need not form normalized distributions, so this compiler preserves the supplied formula without kernel normalization. estimate(predict_cell, n_draws, rng, delta=None) returns an online mean, standard error (None for one draw), and, when requested, a conditional Hoeffding radius. The fitted callback must stay frozen and independent of the trace RNG. These uncertainty measures cover plugin Monte Carlo integration only; they do not cover regression error or lack of observational support. Unsupported arguments, ratios, nonfinite weights/predictions, and unsupported floating-point MC arithmetic fail explicitly. Exact integer/Fraction weights remain available through draw_value.

fit_probability_cell(rows, head, context, domains, fit_regression, rng, source="P") provides the regression adapter. For each genuine iid source row it draws a fresh independent uniform head label, then supplies context-plus-label features and the binary response indicating whether the row’s head matches that label. The caller’s learner returns a prediction function, and FittedProbabilityCell clips its output to [0,1]. For a trace leaf, fit on that leaf’s original head/context and source; assemble the returned cell models into the predict_cell callback. This supplies neither a built-in learner nor an automatic regression-rate/overlap guarantee. Training, pseudo-response construction, and high-dimensional feature access are charged. Direct backward MarginalizeKernel estimation is not implemented by this adapter. Known importance weights, overlap, learning error, or required sample size can grow exponentially: avoiding explicit enumeration alone is not a same-accuracy complexity guarantee.

For an already identified scalar FD or conditional-FD expectation, fit_front_door implements the direct two-regression alternative. Supply separate train_mu, train_r, and evaluation source-row blocks, coordinate names, finite alphabets, a fixed action value, and two learner callbacks. The outcome learner uses (Z, X, C) to predict bounded Y. Each second-block row receives a fresh independent uniform action label U; the second learner uses (X, C, U) to predict the clipped pseudo-outcome hat_mu(Z,U,C). Its target is marginalization of the fitted outcome function. Held-out rows evaluate hat_r(x,C,X), preserving the fixed action and natural observed action in different positions. No mediator density or Cartesian mediator grid is fitted or constructed. This path implements the single-mediator-vector FD formula, not a generic backward compiler for every MC product. The caller supplies the valid identifying formula, independent iid source blocks/auxiliary RNG, population support, and learner guarantees. Obvious block/row object reuse is rejected; independence cannot be established from finite rows. FDRegressionResult retains the clipped mu/r functions and held-out mean, standard error, and optional conditional Hoeffding radius. Learning and overlap errors are not included in those uncertainty measures. Per-row mediator features, all training costs, pseudo-outcome predictions, and held-out predictions are paid.

The focused suite compares the five-node global-cancellation example, front-door, conditional front-door, and a crossed multiple-treatment graph against exact SCM interventions, and checks certificates, genuine-Q equality, binder identity, independent copies, formula traces, source-row regression adapters, direct FD regression mapping, and budget guards:

PYTHONDONTWRITEBYTECODE=1 PYTHONPATH=src python3 -B -m unittest discover -s tests/checkout -p test_indexed_identification.py -v

Related references

• R. Bhattacharya, R. Nabi, I. Shpitser. Semiparametric Inference for Causal Effects in Graphical Models with Hidden Variables. JMLR, 2022.
• J. Tian, J. Pearl. A General Identification Condition for Causal Effects. AAAI, 2002.