🤖 AI

A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases

本文介绍了一种利用答案集程序编程（answer set programming）来指定并计算冲突事实之间优先级关系的声明式基于规则的框架，用于查询不一致的知识库，并通过有向无环分析和务实的环消除技术解决了循环偏好带来的挑战。

原作者： Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean

发布于 2026-08-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位管理着一座巨大且混乱图书馆的图书管理员，其中的一些书因为意外被粘连在一起，导致页面内容相互矛盾。一本书说：“天空是蓝色的”，而粘在同一书架上的另一本书却坚持说：“天空是绿色的”。在计算机科学领域，这被称为“不一致知识库”。当计算机试图利用这个混乱的图书馆来回答问题时，它会陷入困境。为了解决这个问题，科学家们开发了一种叫做“修复”（repairing）的方法。你可以把它想象成一位图书管理员，他并没有把整座图书馆扔掉，而是小心翼翼地剪掉那些冲突的页面，从而创造出一个干净、一致的故事版本。但棘手的地方在于：如果你有上百页冲突的内容，那么剪掉它们的方式会有成千上上万种。究竟应该信任哪个版本的故事情节呢？

通常情况下，计算机会表现得极其谨慎，只接受出现在每一个可能的“干净版本”中的答案。但有时，我们明知某些事实比其他事实更可靠。也许那本“蓝天”的书是由一位著名的天文学家编写的，而那本“绿天”的书只是一个孩子的涂鸦。如果我们能告诉计算机，“信任天文学家胜过信任涂鸦”，它就能选出最好的故事版本。这正是这篇新论文所要解决的问题。它探讨了如何告诉计算机哪些事实更好，而无需让人类去手动对图书馆里的每一页进行排序。

作者们是一支来自法国和日本的研究团队，他们构建了一个巧妙的新系统，让用户可以通过编写简单的“偏好规则”（preference rules）来解决这个谜题。你不需要手动对成千上万个事实进行排序，只需编写类似这样的指令：“如果两个事实发生冲突，保留较新添加的那一个”，或者“如果一个事实来自可靠来源，则将其优先级高于来自未知来源的事实”。这篇论文引入了一个框架，通过这些规则自动生成一份优先级列表，告诉计算机在冲突发生时应该保留哪些事实以及丢弃哪些事实。

然而，这里有一个陷阱。如果你编写了太多的规则，它们可能会陷入循环。例如，规则 A 说“事实 1 比事实 2 好”，规则 B 说“事实 2 比事实 3 好”，但规则 C 却说“事实 3 比事实 1 好”。这产生了一个循环论证，导致没有任何一个事实是真正最好的。这篇论文的核心发现是一套用于打破这些循环的策略。作者提出了四种不同的解开这些结的方法，从“向上看”（go up）方法（优先考虑最重要的规则）到“基于基础”（grounded）方法（只信任那些不属于混乱循环的事实）。他们使用了一种名为“答案集编程”（Answer Set Programming）的计算机程序对这些方法进行了测试，这就像是一个超级聪明的逻辑求解器。

研究人员发现，虽然他们的系统功能强大且灵活，但与那些更陈旧、更僵化的方法相比，处理海量数据时速度可能稍慢。在实验中，他们测试了包含多达 200 万个事实的情景，并发现即使在冲突非常混乱且非二元（涉及两个以上事实）的情况下，他们的系统也能成功理顺复杂的冲突并回答问题。他们还从数学上证明了，对于某些类型的简单规则，你可以 100% 确定系统不会陷入循环；但对于更复杂的规则，你可能需要使用他们的“破环”（loop-breaking）策略。最终，这篇论文不仅提供了一种修复混乱数据的新方法，还提供了一种让人们用简单的英语规则表达其逻辑的方式，让计算机承担起决定该相信哪个版本真相的繁重工作。

技术摘要：一种用于指定冲突事实间的偏好并查询不一致知识库的基于规则的方法

问题陈述

不一致容忍语义（特别是基于子集修复的语义）是查询违反约束的知识库（KB）的标准方法。虽然已有框架通过在冲突事实之间定义优先级关系（例如 Staworko 等人提出的优先数据库框架）来定义“最优修复”，但仍存在一个关键空白：如何便捷地指定该优先级关系本身。

现有文献假设优先级关系是预先给定的，但要求用户手动输入所有冲突事实之间的二元关系是不现实的。此外，当用户尝试通过规则来指定偏好时，这些规则可能会诱导出循环（例如：事实 A 优于 B，B 优于 C，且 C 优于 A），从而使该关系失效，因为优先级关系必须是无环的。本文旨在解决如何声明式地指定这些偏好，并解决由此产生的循环问题，以实现对不一致知识库的实际查询。

方法论

1. 基于规则的偏好指定

作者引入了一个声明式框架，其中优先级关系是从对数据集 $D$ 和元数据库 $M$ 进行评估的偏好规则中导出的。

元数据库： 一个包含元数据（如日期、来源可靠性）的数据集 $F$ ，通过唯一标识符与 $D$ 中的事实相关联。
偏好规则： 形式为 $Cond(x_1, x_2) \to pref(x_1, x_2)$ $C o n d (x_{1}, x_{2}) \to p r e f (x_{1}, x_{2})$ 的规则，其主体 $Cond$ 可以引用：
- $D$ 中事实的存在或缺失。
- $F$ 中的元数据（例如，比较日期或可靠性评分）。
- 本体公理（例如，子类关系）。
- 否定和不等式。
诱导关系： 如果条件成立，规则会诱导出一个偏好 $pref(id(\alpha), id(\beta))$ 。实际的优先级关系 $\succ_{\Sigma, K, M}$ 通过过滤这些诱导的偏好来形成，仅保留出现在冲突中的事实对 $(\alpha, \beta)$ 。

2. 处理循环

由于诱导关系可能包含循环，本文提出了两种互补的策略：

静态无环检查： 研究一组规则是否能保证为任何数据集生成无环关系。
- 本文证明，对于通用语言 $PL_{DL}$ ，检查无环性是不可判定的。
- 然而，对于受限语言 $PL_{pos}$ （不含本体原子或否定的正向规则）以及二元否定约束，该问题是可判定的（属于 coNP 类）。
- 引入了**强无环性（strong acyclicity）**的概念：如果一组规则对于任何 KB 和元数据库（无论是否存在冲突）都能产生无环关系，则称该规则集是强无环的。
务实的循环解决： 当规则无法保证无环时，系统允许用户将规则划分为优先级层级 ( $\Sigma_1, \dots, \Sigma_n$ $Σ_{1}, \dots, Σ_{n}$ )，其中索引越低表示优先级越高。定义了四种提取无环子关系的方法：
1. 向上提升 ( $\succ_u$ )： 从最低索引（最高优先级 $\Sigma_1$ ）开始迭代添加层级，如果添加下一层会导致形成循环，则停止。
2. 向下降低 ( $\succ_d$ )： 从所有层级的并集开始，迭代地从最高索引（最低优先级）的层级中移除参与循环的对，直到实现无环。
3. 精炼向上提升 ( $\succ_{ru}$ )： 一种在添加下一层之前先移除当前层级内循环的变体。
4. 基准法 ( $\succ_g$ )： 一种受论证框架中基准扩展（grounded extensions）启发的不动点方法。
- 本文确立了这些策略之间的理论关系（例如 $\succ_u \subseteq \succ_d \subseteq \succ_g$ ），并将它们与已有的修复概念（如可能性修复和非击败修复）联系起来。

3. 实现

作者使用**回答集程序（ASP）**实现了一个端到端的系统：

输入编码： 逻辑程序对数据集、元数据库、约束、查询和偏好规则进行编码。
冲突与原因计算： 系统使用 ASP 计算冲突和原因（最小不一致子集）。值得注意的是，该实现处理了非二元冲突（任意大小的冲突），而许多现有工具仅限于处理二元冲突。
优先级计算： 循环解决策略被编码为 ASP 程序，以导出最终的优先级关系。
查询回答： 系统在各种语义（Brave, AR, IAR）结合不同修复类型（子集、Pareto 最优、完成最优）的情况下评估查询。

核心结果

理论贡献

不可判定性： 证明了检查一组偏好规则是否产生无环关系是不可判定的。
可判定性： 证明了对于正向规则（不含本体原子 $PL_{pos}$ ）和二元否定约束，无环性检查是可判定的，且属于 coNP。
策略等价性： 确立了所提出的循环解决策略在映射到特定 KB 结构时，与文献中已知的修复概念（可能性、非击败、基准）相对应。

实验评估

系统在 CQAPri 基准测试（合成 DL-Lite 知识库）上进行了评估，测试了不同的规模（高达约 200 万个事实）和冲突密度。

循环解决性能：
- 在大多数场景下，向下降低 ( $\succ_d$ ) 策略的计算速度明显快于 $\succ_g$ 和 $\succ_u$ ，同时通常能产生相似的结果（在许多情况下是重合的）。
- 精炼向上提升 ( $\succ_{ru}$ ) 策略由于 ASP 编码的复杂性，即使在小型数据集上也导致了内存溢出。
- 系统成功为具有高冲突比例（高达 46%）和大量偏好事实的数据集计算了优先级关系。
查询回答性能：
- 在计算最优修复语义下的答案时，基于 ASP 的系统通常比现有的基于 SAT 的工具 ORBITS 慢（在大规模数据集上慢了几个数量级）。
- 然而，在 ORBITS 失败（超时或内存溢出）的情况下，该 ASP 系统能够成功回答 C-AR 和 C-brave 语义下的查询。
- 该系统是首个实现针对非二元冲突进行最优修复语义计算的系统。

重要性与主张

本文声称提供了第一个用于为不一致知识库指定优先级关系的声明式、基于规则的框架，解决了阻碍实用化优先修复语义采用的空白。

灵活性： 通过允许规则引用元数据和本体公理，该框架提供了一种灵活的方式来定义不一致管理策略，而无需手动输入二元关系。
循环管理： 本文提供了解决循环问题的务实方案，提供了多种解决策略以及针对特定规则类的理论保证。
实现： 实现过程证明了使用 ASP 处理此类任务的可行性，特别是其处理非二元冲突的能力，这是目前 ORBITS 等先进工具所缺乏的功能。
谦逊态度： 作者承认，虽然在处理二元冲突时其 ASP 实现的效率低于 SAT 方法，但它提供了更高的表达能力（处理任意大小的冲突）和模块化程度（例如，更容易扩展到其他修复计算）。他们并未声称在原始速度上超越了 SAT，而是强调了其方法的独特能力。

研究结论指出未来的研究方向，包括将静态分析扩展到更广泛的理论类、研究最优修复的唯一性，以及构建从标准数据格式自动生成逻辑程序的完整流水线。