用形式化验证确保知识图谱推理正确性,解决主流工具不一致问题。
VEL: A Formally Verified Reasoner for OWL2 EL Profile
- 基于Coq证明助手构建可执行的正式化推理算法
- 发现原算法证明缺陷并修正以保证完备性
- 适合对可靠性要求高的医疗等关键领域
过去二十年来,网络本体语言(OWL)在推动本体和知识图谱发展方面发挥了重要作用,提供了增强数据语义集成的结构化框架。然而,这些系统中的演绎推理可靠性仍面临挑战,近期竞赛中主流推理器之间存在不一致现象已表明现有基于测试的方法存在局限性,尤其在医疗等高风险领域更为突出。为此,本文提出了VEL——一个经过形式化验证的EL++推理器,具备机器可检查的正确性证明,确保所有输入下的输出均有效。该形式化基于Baader等人提出的算法,通过Coq证明助手的提取能力转化为可执行的OCaml代码。我们的形式化过程揭示了原始完备性证明中的若干错误,促使对算法进行修正以确保其完备性。这项工作表明,对推理算法进行机械化处理对于保障其理论与实现层面的正确性至关重要。
原文摘要 · Abstract (English)
Over the past two decades, the Web Ontology Language (OWL) has been instrumental in advancing the development of ontologies and knowledge graphs, providing a structured framework that enhances the semantic integration of data. However, the reliability of deductive reasoning within these systems remains challenging, as evidenced by inconsistencies among popular reasoners in recent competitions. This evidence underscores the limitations of current testing-based methodologies, particularly in high-stakes domains such as healthcare. To mitigate these issues, in this paper, we have developed VEL, a formally verified EL++ reasoner equipped with machine-checkable correctness proofs that ensure the validity of outputs across all possible inputs. This formalization, based on the algorithm of Baader et al., has been transformed into executable OCaml code using the Coq proof assistant's extraction capabilities. Our formalization revealed several errors in the original completeness proofs, which led to changes to the algorithm to ensure its completeness. Our work demonstrates the necessity of mechanization of reasoning algorithms to ensure their correctness at theoretical and implementation levels.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。