Decomposing Constraint Networks for Calculating c-Representations

Marco Wilhelm, Gabriele Kern-IsbernerAAAI 2024 · DOI

Abstract

Calculating c-representations for nonmonotonic reasoning often involves solving complex global constraint satisfaction problems. This paper presents a novel structural approach to decompose these large rule sets into hierarchical constraint networks. By identifying "safe sub-bases" and their dependencies, the authors demonstrate that belief models can be calculated locally and propagated, significantly reducing computational complexity while maintaining mathematical soundness.

Introduction

In Artificial Intelligence, nonmonotonic reasoning allows systems to handle defeasible statements—rules that are generally true but subject to exceptions. Spohn’s ranking functions provide a powerful framework for this by assigning degrees of implausibility to possible worlds. The "c-representation" is a preferred model within this framework, as it assigns penalty points to rules only when they are violated. However, determining these penalty points requires solving a system of constraints that grows exponentially with the number of rules.

While "syntax splitting" can simplify independent rule sets, it fails when rules overlap. This paper addresses the challenge of decomposing interdependent rule sets into manageable local components.

Methodology: Constraint Networks and Safe Sub-bases

The authors propose a structural decomposition based on Constraint Networks. The process involves several key steps:

  1. Constraint Reductions: Transformation rules (R1–R4) simplify the mathematical requirements, revealing which rules truly influence one another.
  2. Safe Covers: The authors define "safe sub-bases"—groups of rules that are self-contained regarding their constraints. Unlike traditional disjoint sets, these sub-bases can overlap.
  3. Adjacency Graphs: A directed graph maps the dependencies between rules, where an edge from $\delta_i$ to $\delta_j$ indicates that the penalty for $\delta_j$ depends on $\delta_i$.
Adjacency graph showing dependencies between rules in the running example.
  1. Constraint Networks: These are Directed Acyclic Graphs (DAGs) that organize safe sub-bases hierarchically. This structure allows for an iterative approach to solving the global problem.
  2. Iterative Algorithm: The proposed algorithm solves constraints for the simplest sub-bases first. These local solutions are then propagated through the network to solve more complex, overlapping parts.
A constraint network illustrating the hierarchical decomposition and local inequality solving.

Key Insights

  • Flow of Dependency: The core idea is that complete independence is not required for decomposition. By understanding the flow of dependency, one can solve "upstream" rules and use their results as constants for "downstream" rules.
  • Local Inference Validity: A major theoretical result is that "skeptical c-inference"—determining what must be true given the rules—can be performed entirely within a local safe sub-base without losing global validity.
  • The Residuum: The "residuum" represents the new information introduced by a sub-base relative to its predecessors. The computational complexity is bounded by the size of the largest residuum, which is typically much smaller than the total knowledge base.

Results and Conclusion

The authors formally prove that their iterative algorithm is sound and always terminates with a valid global c-representation. By shifting the computational load from one large NP-complete problem to several smaller ones, the framework offers a scalable path for qualitative reasoning in complex domains.

Future work will focus on extending this framework to first-order logic and conducting empirical benchmarks on large-scale knowledge bases to quantify performance gains in real-world applications.

Summary updated

BibTeX
@inproceedings{wilhelm2024decomposing,
  author = {Marco Wilhelm and Gabriele Kern-Isberner},
  title = {{Decomposing Constraint Networks for Calculating c-Representations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28946},
}
Figure