Minimum-cost certificates ensure rule conclusions withstand multiple source failures
Minimum-Cost Robust Evidence Certificates for Horn Reasoning under Correlated Source Failures
Artificial Intelligence
Summary
Sometimes, a conclusion drawn from multiple evidence sources can become invalid if some sources stop providing information. The paper studies how to find the cheapest set of evidence that guarantees a conclusion remains valid even if up to k sources fail. The authors introduce a method using special mathematical structures called transversals to make sure the evidence set is robust and explain why requiring completely separate proofs can wrongly reject valid solutions. Their approach efficiently finds optimal evidence without checking all possible failure scenarios and works well in tests compared to other methods.
What this means in practice
- •For knowledge engineers: Provide reliable evidence sets that keep conclusions valid despite certain sources becoming unavailable during reasoning.
- •For ontology developers: Create robust justifications for ontology inferences even when some related data sources fail simultaneously.
Authors
Yukun Yang
Abstract
A small justification for a rule-based conclusion may disappear when a source is withdrawn, and multiple derivations need not provide independent evidence. We study minimum-cost certificates that preserve a Horn conclusion under every withdrawal of at most k source domains. Evidence records remain distinct from asserted facts, supporting replicated attestations and overlapping failure dependencies. Transversals of minimal-support footprints characterize robustness and explain why disjoint-proof requirements can reject valid certificates. An exact procedure alternates weighted evidence selection with a source-failure oracle. A rule-closed counterinterpretation yields a globally valid selection cut without enumerating supports or failure scenarios. We prove correctness, finite termination, and cost optimality, establish coNP-completeness of unrestricted verification and NP-completeness of synthesis for every fixed budget, and identify a tractable reachability restriction. Experiments on controlled benchmarks, reachability graphs, and ontology-derived instances demonstrate that our counterinterpretation-guided synthesis achieves up to 92% optimum coverage within practical resource bounds, outperforming scenario expansion and general abduction while confirming the necessity of transversal-based reasoning over proof-packing heuristics.