Explaining User Errors in Knowledge Base Completion

Barış SertkayaBarış Sertkaya

Download

Barış Sertkaya
Explaining User Errors in Knowledge Base Completion
Proceedings of the 2008 International Workshop on Description Logics (DL2008), volume 353 of CEUR-WS, 2008

Details
Bibtex

KurzfassungAbstract
Knowledge base completion is a method for extending both the terminological and assertional part of a Description Logic knowledge base by using information provided by a domain expert. It ensures that the extended knowledge base is complete w.r.t. a fixed interpretation in a certain, well-defined sense. Here we consider the problem of explaining user errors in knowledge base completion. We show that for this setting, the problem of deciding the existence of an explanation within a specified cardinality bound is NP-complete, and the problem of counting explanations that are minimal w.r.t. set inclusion is #P-complete. We also provide an algorithm that computes one minimal explanation by performing at most polynomially many subsumption tests.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Sert08,
  author = {Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Proceedings of the 2008 International Workshop on Description Logics ({DL2008})},
  series = {CEUR-WS},
  title = {Explaining User Errors in Knowledge Base Completion},
  volume = {353},
  year = {2008},
}