Sep, 2022
定性推理问题的多元复杂度分析
A Multivariate Complexity Analysis of Qualitative Reasoning Problems
Leif Eriksson, Victor Lagerkvist
TL;DR本文介绍了单指数算法,并通过多元分析研究了时间推理问题,特别是针对 Allen 的时间间隔代数,证明了一个新问题可以在单指数时间内解决,并且这种方法可以更广泛地用于其他问题。
Abstract
qualitative reasoning is an important subfield of artificial intelligence
where one describes relationships with qualitative, rather than numerical,
relations. Many such reasoning tasks, e.g., →
qualitative reasoningartificial intelligencesingle-exponential algorithmstemporal reasoningallen's interval algebra
发现论文,激发创造
基于 Answer Set Programming 的定性理论编码和推理的一般方法
这篇论文提出了使用 ASP 作为一个统一的形式化语言来解决需要定性推理和非定性推理的问题,提出了一族可以处理任何二进制关系资料的 ASP 编码,并且在真实数据集的实验中进行了评估。
Aug, 2020
预测或比较:走向可解释的定性推理
本研究通过将定性关系任务分类成预测和比较两种类型,并采用端到端训练的神经网络模块来模拟这两种推理过程,实验结果在两个问答数据集 QuaRTz 和 QuaRel 上展示了我们方法的有效性和泛化能力,并提供模块的中间输出来使推理过程更容易解释。
Jun, 2021
联结查询反向工程问题的复杂性
本文研究了解决共识查询相关反向工程问题的复杂性,并提出了基于量子比较的松弛方法来降低复杂度。最终得出了基于共识查询树宽度的 QBE 的可行性和闭合性条件,并将其应用于图数据库的查询问题。
Jun, 2016
通过动态规划和次线性分割改进 Allen 的区间代数算法
本文提出了一种新颖的动态规划和亚线性分区技术框架来解决 NP-hard 的定性推理问题,将 Allen 的时间区间代数的复杂度从 O((1.0615n)^ n)降至 O((cn /log n)^ n);提出的算法技术不仅大大提高了 NP-hard 定性推理问题的最新技术水平,而且还可能适用于许多需要 $2^(O(n))$ 分辨率的问题。
May, 2023
SQALER: 通过分离多步问题和逻辑推理实现问答的扩展
通过多跳推理,我们提出了一种与知识图中的关系类型数量成比例的方法,具有出色的可扩展性,可以用于实现多项元 QA 数据集的目的,并实现了更具挑战性的 WebQuestionsSP 的最新技术水平。
Oct, 2021
超关系知识图谱上的查询嵌入
本文介绍了如何利用 Graph Neural Networks 来嵌入和回答超关系连接查询,以处理新型复杂查询,同时提出了一种提高查询效率的方法,并在实验证明 Qualifier 可以在多种查询模式下提高查询效果。
Jun, 2021