Source-linked AI summary
Common-Witness Certificates and Sharp Feature Bounds for Counterfactual Image Auditing
Usef Faghihi, Amir Saki
TL;DR
The paper addresses the gap between locally plausible regional edits and a single globally coherent counterfactual explanation. It introduces an externally anchored common-witness audit, separates that audit from causal identification, and derives sharp feature bounds with finite-sample outer coverage. Controlled studies demonstrate the predicted local-to-global separation, while the framework remains limited to declared feature relations rather than unrestricted pixel-level counterfactuals.
Problem
An edited image may satisfy every regional plausibility constraint separately even when no single latent witness explains all regions simultaneously.
Method
The framework combines common-witness feasibility complexes, exact certificates and repair formulas, externally justified feature relations, support-only coupling optimization, and simultaneous marginal confidence regions.
Results
Controlled MNIST, Morpho-MNIST, and smallNORB studies demonstrate the predicted local-to-global separation, while synthetic studies test sharp bounds, certificate recovery, and structured computation.
Takeaways & Limitations
The pipeline makes explicit where external information narrows coupling ambiguity and where multiple compatible couplings remain within the identified interval.
Takeaways & Limitations
The method audits a declared feature relation rather than identifying unrestricted pixel-level counterfactuals, and broader natural-image evaluation remains future work.
Abstract
from arXiv · showhide
An image editor may satisfy every regional plausibility constraint separately even when no single latent explanation fits the complete output. We formalize this local-to-global failure using a common witness grade and witness nerve. The framework separates auditing from causal identification: shared exogeneity alone allows every coupling of the regime marginals, whereas an externally justified witness relation yields sharp partial-identification bounds for prespecified image features. Helly-type arguments provide short incompatibility certificates for quasiconvex losses, heterogeneous action strata, and finite witness atlases; a blocker-hypergraph formula gives exact repair counts. Simultaneous confidence regions for the regime marginals give finite-sample outer coverage of the complete identified interval. Controlled MNIST, Morpho-MNIST, and smallNORB studies demonstrate the predicted local-global separation, while synthetic experiments test sharp bounds, certificate recovery, and structured computation. The method audits a declared feature relation and does not identify unrestricted pixel-level counterfactuals.
1. Introduction.
The paper identifies a local-to-global auditing failure and develops an externally anchored certificate-to-inference pipeline that separates witness auditing from causal identification. It derives sharp certificates, repair formulas, feature bounds, and finite-sample coverage while preserving the boundary that unrestricted pixel-level counterfactuals are not identified.
- Regional plausibility can coexist with global incompatibility when different regions require different latent witnesses.An audit aggregating independent local passes can therefore miss the absence of any single witness explaining all regions.
- Externally justified witness families define regional costs whose common sublevel intersections audit image pairs and project admissibility to prespecified features.The projected relation is an explicit support-only assumption rather than an implication of the causal graph.
- The certificate-to-inference pipeline yields sharp q(s+1) finite-atlas certificates, blocker-hypergraph repair formulas, and heterogeneous action-stratified certificates.These are exact formulas for the labeled witness structures produced by the audit.
- Shared exogeneity alone admits every coupling of the regime marginals, whereas an externally declared relation produces an exact support-only identified interval without selecting a coupling.The framework places partial-identification and transport methods after an auditable, externally sourced relation.
- Controlled and finite paired studies demonstrate local-to-global separation, while the method explicitly does not establish unrestricted pixel-level counterfactual identification.Implementation and reproduction materials are available, but external datasets must be obtained from their original sources.
- Simultaneous marginal confidence regions provide finite-sample outer coverage for the complete identified interval.Clopper–Pearson bands are conservative and nonasymptotic, while other simultaneous multinomial regions may be substituted when joint coverage is established.
3. Setting and the common-witness audit.
The paper models two potential images through a finite declared feature and audits candidate pairs using externally anchored common witnesses. Shared exogeneity does not identify their coupling; the witness audit instead induces a stated feature relation that supports partial identification.
- A measurable feature map Ψ assigns each potential image to one of K finite feature values.The two regimes have potential images I_x and features Y_x = Ψ(I_x).
- Single-world feature laws µ_x are assumed identified from valid causal evidence, while image samples alone generally do not identify them.
- The target joint feature law is represented by π_yy′ = P(Y_0 = y, Y_1 = y′), supporting bounded linear functionals such as transition probabilities and average feature changes.Conditional queries use the corresponding numerator divided by the fixed positive denominator µ_0(B).
- Shared-exogeneity saturation means every coupling of µ_0 and µ_1 can arise from a two-regime structural model with one shared exogenous variable.Thus using the same exogenous realization across worlds does not by itself restrict the joint potential-outcome law.
- The auditing witness w is distinct from the structural response type unless an external scientific argument identifies them.Regional costs c_r(w; i, j) measure each role's violation for a factual–candidate pair, under stated regularity conditions when minimizers are used.
- The common-witness grade and nerve organize jointly explainable role sets, with one global witness exactly when the grade is at most the tolerance.Downward closure makes the nerve a simplicial complex; maximal faces are maximal jointly explainable sets and minimal nonfaces are minimal incompatibility explanations.
- A role budget s permits prespecified regional exceptions, and the induced existential feature projection can be an outer relaxation unless feature-saturation or conditional-fiber conditions hold.Without an external anchor, the default feature relation is unrestricted.
4. Combinatorial certificates and repair.
The paper derives short, sharp incompatibility certificates and exact repair counts for finite witness atlases, convex losses, and heterogeneous action strata. It also quantifies approximate coherence and robustness to uniformly estimated losses.
- Finite atlases: A finite witness atlas yields tolerant incompatibility certificates with at most q(s + 1) roles, and this bound is sharp.The construction shows all q(s + 1) roles can be necessary.
- Finite atlases: Minimal s-tolerant incompatibility explanations are inclusion-minimal (s + 1)-fold transversals of the bad-role hypergraph.The same structure gives an exact repair formula by minimizing the number of bad roles across witnesses.
- Finite atlases: Rowwise order selection computes the tolerant grade, one certificate, and the exact repair number in O(qm) time, while enumerating all minimal transversals can remain exponential.Sorting instead gives O(qm log m) selection time.
- Action-stratified atlases: For action-stratified witness spaces, the certificate bound sums the affine dimensions plus one across strata and is sharp for every dimension list.The proof applies a Helly bound within each compact convex stratum and combines the resulting role sets.
- Approximate coherence: Dense local compatibility yields a large coherent core, but does not imply global compatibility.Fractional-Helly bounds quantify the largest role set explained by one witness from the fraction of feasible h-faces.
- Robustness: A uniform loss-estimation error of at most δ changes every tolerant grade by at most δ, but statistical use requires an independently justified uniform error bound.The robustness statement is deterministic; finite-net outer approximation and exact nerve recovery are treated separately.
5. Sharp feature bounds.
The feature-bound analysis separates externally declared witness relations from causal identification. Under the stated support-only model, the resulting transport program gives a sharp interval, with a violation-budget extension for sensitivity analysis.
- Identification boundary: Shared exogeneity alone permits every coupling of the two regime marginals, so it does not identify a unique counterfactual feature distribution.The support-only model imposes no additional response-function, latent-DAG, or full-image restriction.
- Sharp feature bounds: An externally declared relation restricts the feasible couplings, and Theorem 5.1 identifies the sharp support-only interval whenever the relation-compatible set is nonempty.The analysis treats the projected feature relation as an explicit assumption rather than inferring it from the causal graph.
- Sharp feature bounds: Both endpoints and every intermediate value of the identified interval are attainable.Compact convex feasibility and shared-exogenous realizations establish endpoint attainment and fill the interval by mixtures.
- Scope: Sharpness is relative to the displayed model; additional full-image, latent-DAG, or nonsaturated relation restrictions can make the program only outer.This qualification prevents the audit relation from being treated as identification of unrestricted pixel counterfactuals.
- Budget relaxation: Replacing hard support with a violation-mass budget τ yields a sharp interval nested in τ, with the smallest feasible budget equal to the Hall deficiency.The parameter τ is a sensitivity input rather than a probability learned from unpaired images.
6. Finite-sample outer inference.
Finite-sample inference propagates simultaneous confidence regions for the regime marginals through the coupling program. The resulting random interval covers the complete oracle identified interval, including under relation uncertainty when its outer-coverage property is justified.
- Coverage guarantee: If the marginal confidence region has coverage at least 1 − α, the propagated interval provides outer coverage for the complete oracle identified interval.The containment argument enlarges the feasible coupling set on the confidence event, widening the endpoints conservatively.
- Failure handling: When the random feasible set is empty, reporting the vacuous payoff range preserves the coverage guarantee.Feasibility is not concealed by renormalization.
- Marginal confidence regions: Independent within-regime samples support two-sided Clopper–Pearson intervals for each of M = 2K marginal cells at cellwise noncoverage α/M.Bonferroni provides simultaneous coverage despite dependence among cells within each multinomial sample.
- Coverage guarantee: The target is the complete oracle interval, not one selected coupling.The procedure reports uncertainty over all couplings compatible with the declared relation and marginal constraints.
- Random relations: If the random outer relation contains the true relation with probability at least 1 − β, the combined coverage is at least 1 − α − β.Sample splitting alone does not establish the required outer-relation property.
7. Audit and optimization pipeline.
The operational pipeline separates audit inputs, feature-relation assumptions, and transport-based inference. It returns certificates and repair counts when audits fail while preserving explicit scope boundaries for optimization and interpretation.
- Audit specification: The procedure prespecifies the feature, protected roles, descendants, witness atlas, tolerance, and violation budgets before auditing candidate image pairs.This fixes the declared audit relation and its admissibility criteria in advance.
- Audit outputs: Failed audits return a blocking-role certificate and exact repair count, while passed audits are projected to a feature relation marked exact or outer.The projection is an explicit assumption rather than a causal-graph inference.
- Feature inference: The lower and upper support or budget transport programs are solved from estimated single-world marginals, with simultaneous bands when finite-sample coverage is required.The information sources remain separate throughout the operational procedure.
- Computational scope: Verified global optimization is needed for nonconvex neural witness spaces not represented by a verified finite atlas.The finite-atlas certificates do not validate arbitrary local neural searches.
- Empirical scope: The numerical studies test local-global failure, declared-relation bounds, and structured computational tractability rather than unrestricted pixel-level counterfactual identification.Archived computations are checked against known optima and residual conditions, without claims of comparable scaling for dense arbitrary relations or nonconvex neural optimization.
8. Numerical studies.
The public repository preserves the implementation, tests, configurations, retained outputs, and integrity manifests for the numerical studies, while documenting dataset and replay limitations.
- The repository contains implementation artifacts and integrity manifests supporting the numerical studies.External datasets must be obtained from their original sources.
Status of the numerical evidence.
The numerical evidence supports the framework’s local-to-global audit behavior, sharp relation-based bounds, finite-sample coverage, and structured computation on controlled or finite paired-response families. It also establishes important scope limits: results do not identify arbitrary pixel-level counterfactuals or validate unrestricted relations.
- Empirical audit behavior: The controlled and learned-witness studies show local plausibility can persist while global common-witness acceptance nearly disappears, with Morpho-MNIST free-action acceptance at 0.113750.The protocol contrasts regionwise scores with a single action explaining every region, using disjoint calibration and evaluation splits.
- Sharp bounds: The three-state synthetic check narrows the sharp target interval from [0.35, 0.80] under marginals alone to [0.55, 0.70] under the declared relation.When 0.20 of true coupling mass violates the relation, the constrained interval fails to cover the true target, confirming the negative control’s role.
- Finite-sample inference: The archived inference experiments covered the complete oracle identified interval in all 1,800 repetitions, while mean widths decreased from 0.9237 to 0.2075 under Hoeffding and from 0.7413 to 0.1861 under exact Bonferroni–Clopper–Pearson bands.The exact bands were 10.3%–27.8% narrower, but the comparison was post-confirmatory and descriptive; coverage follows from the theorem.
- Audit-to-bound computation: The controlled audit-to-bound panel reduced the interval from [0.0600, 0.8200] without the image relation to [0.1517, 0.2600] with violation budget τ = 0.08, containing the hidden target 0.2100.The hard-support transport program was infeasible, and no renormalization or silent relaxation was used; the pooled i.i.d. premise was nevertheless violated by digit balancing.
- Structured computation: All 35 archived scaling cases succeeded in 34.85 seconds with peak memory 0.483 GiB, while sparse transport handled 10,000 states using 109,970 edge variables and residuals below 1.4 × 10^-18.Affine cases reached a largest reported primal, stationarity, or duality error of 3.34 × 10^-16, and leave-one-out atlases rejected the full role set.
- Scope and limitations: The evidence validates computations and local-to-global failure on controlled or finite paired families, not arbitrary relations, unrestricted pixel-level counterfactuals, or a joint multi-regime image law.The framework targets sharp bounds for prespecified finite-dimensional image features under a declared support restriction; Morpho-MNIST is synthetic and smallNORB uses ten physical objects in the relation panel.
9. Scope, information boundary, and limitations.
The framework’s conclusions depend on externally justified witness and feature relations, whose misspecification can distort auditing and identification. Its feature-level projection and empirical validation also impose explicit scope boundaries.
- Information boundary: The witness atlas and cross-world relation are scientific inputs, not consequences of observed regime marginals.Misspecification can cause rejection of coherent pairs or identified intervals that exclude the true target.
- Information boundary: Projecting image-level relations onto coarse features can discard image-level restrictions.Feature-level and image-level analyses coincide only under feature-saturation or conditional-fiber conditions.
- Empirical scope: The experiments validate local–global separation, sharp bounds, finite-sample coverage, and computational scaling on MNIST, Morpho-MNIST, smallNORB, and synthetic studies.Broader natural-image evaluation and empirical validation of the multi-regime extension remain future work.
- Scope: The pipeline requires prespecification, external validation of the witness relation, and reproducible evidence at the correct independent unit.These requirements define where the method’s validity rests and where ambiguity remains.
10. Conclusion.
The implementation materials support reproduction while preserving dataset-access constraints and documenting remaining limitations.
- Reproducibility: Code, experiment runners, tests, protocols, aggregate outputs, and reproduction instructions are available.External datasets must be obtained from their original cited sources.
- Reproducibility: The repository documents reproduction limitations.The paper does not redistribute external datasets.