Interactive Debugging of Knowledge Bases

Many AI applications rely on knowledge about a relevant real-world domain that is encoded by means of some logical knowledge base (KB). The most essential benefit of logical KBs is the opportunity to perform automatic reasoning to derive implicit knowledge or to answer complex queries about the modeled domain. The feasibility of meaningful reasoning requires KBs to meet some minimal quality criteria such as logical consistency. Without adequate tool assistance, the task of resolving violated quality criteria in KBs can be extremely tough even for domain experts, especially when the problematic KB includes a large number of logical formulas or comprises complicated logical formalisms. Published non-interactive debugging systems often cannot localize all possible faults (incompleteness), suggest the deletion or modification of unnecessarily large parts of the KB (non-minimality), return incorrect solutions which lead to a repaired KB not satisfying the imposed quality requirements (unsoundness) or suffer from poor scalability due to the inherent complexity of the KB debugging problem. Even if a system is complete and sound and considers only minimal solutions, there are generally exponentially many solution candidates to select one from. However, any two repaired KBs obtained from these candidates differ in their semantics in terms of entailments and non-entailments. Selection of just any of these repaired KBs might result in unexpected entailments, the loss of desired entailments or unwanted changes to the KB. This work proposes complete, sound and optimal methods for the interactive debugging of KBs that suggest the one (minimally invasive) error correction of the faulty KB that yields a repaired KB with exactly the intended semantics. Users, e.g. domain experts, are involved in the debugging process by answering automatically generated queries about the intended domain.