Extending the description logic EL with threshold concepts induced by concept measures
Extending the description logic EL with threshold concepts induced by concept measures
复制标题
使用由概念测量引起的阈值概念来扩展描述逻辑 EL
DOI：
10.1016/j.artint.2023.104034
复制
发表时间：
2024
期刊：
影响因子：
--
通讯作者：
Oliver Fernández Gil
中科院分区：
文献类型：
--
作者：
Franz Baader;Oliver Fernández Gil
在人工智能系统的应用中，很难获得应用领域重要概念的准确定义，使用传统的基于逻辑的知识表示语言（例如描述逻辑）可能会导致非常大且不直观的定义以及推理的高度复杂性。为了克服这个问题，我们定义了新的概念构造器，使我们能够以近似的方式定义概念。更准确地说，我们提出了轻量级描述逻辑 EL 的扩展家族 τ EL (m)，它使用阈值构造函数来实现此目的。为了定义这些构造函数的语义，我们使用分级隶属函数 m，它对于解释和概念中的每个个体产生一个区间 [0, 1] 中的数字，表示个体属于解释中的概念的程度。 ⋈ε{<,≤,>,≥} 的阈值概念 C⋈ t 然后收集属于 C 且度⋈ t 的所有个体。逻辑 τ EL (m) 将 EL 扩展为阈值概念，其语义是相对于函数 m 定义的。为了构建适当的分级隶属函数，我们展示了如何使用概念度量∼（概念之间的包含或等价性的分级概括）来定义分级隶属函数m∼。然后我们引入一大类概念测度，称为 simi-d，其逻辑 τ EL (m∼) 具有良好的算法特性。基本上，我们证明了 τ EL (m∼) 中的推理在没有 TBox 的情况下是 NP/coNP 完全的，对于非循环 TBox 来说是 PSpace 完全的，对于一般 TBox 来说是 ExpTime 完全的。实例问题是个例外，它已经是 PSpace 完整的，没有 TBox 的组合复杂性。虽然上限适用于 simi-d 的所有元素，但我们只能证明 simi-d 子类的一些硬度结果。本文大大改进并概括了我们在之前三篇会议论文中展示的结果，并提供了我们所有结果的详细证明。
In applications of AI systems where exact definitions of the important notions of the application domain are hard to come by, the use of traditional logic-based knowledge representation languages such as Description Logics may lead to very large and unintuitive definitions, and high complexity of reasoning. To overcome this problem, we define new concept constructors that allow us to define concepts in an approximate way. To be more precise, we present a family τ EL (m) of extensions of the lightweight Description Logic EL that use threshold constructors for this purpose. To define the semantics of these constructors we employ graded membership functions m, which for each individual in an interpretation and concept yield a number in the interval [0, 1] expressing the degree to which the individual belongs to the concept in the interpretation. Threshold concepts C⋈ t for⋈∈{<,≤,>,≥} then collect all the individuals that belong to C with degree⋈ t. The logic τ EL (m) extends EL with threshold concepts whose semantics is defined relative to a function m. To construct appropriate graded membership functions, we show how concept measures∼(which are graded generalizations of subsumption or equivalence between concepts) can be used to define graded membership functions m∼. Then we introduce a large class of concept measures, called simi-d, for which the logics τ EL (m∼) have good algorithmic properties. Basically, we show that reasoning in τ EL (m∼) is NP/coNP-complete without TBox, PSpace-complete wrt acyclic TBoxes, and ExpTime-complete wrt general TBoxes. The exception is the instance problem, which is already PSpace-complete without TBox wrt combined complexity. While the upper bounds hold for all elements of simi-d, we could prove some of the hardness results only for a subclass of simi-d. This article considerably improves on and generalizes results we have shown in three previous conference papers and it provides detailed proofs of all our results.
登录
查看更多内容
DOI：
10.1007/s10817-007-9077-y
发表时间：
2007-10
期刊：
Journal of Automated Reasoning
影响因子：
--
作者：
Dmitry Tsarkov;Ian Horrocks;P. Patel-Schneider
通讯作者：
Dmitry Tsarkov;Ian Horrocks;P. Patel-Schneider
DOI：
10.1007/s10817-014-9305-1
发表时间：
2014-10-01
期刊：
JOURNAL OF AUTOMATED REASONING
影响因子：
--
作者：
Glimm, Birte;Horrocks, Ian;Wang, Zhe
通讯作者：
Wang, Zhe
影响因子：
5
作者：
Di Noia, Tommaso;Di Sciascio, Eugenio;Donini, Francesco M.
通讯作者：
Donini, Francesco M.
基于相似性的宽松实例查询
DOI：
10.1016/j.jal.2015.01.002
发表时间：
2015
期刊：
J. Appl. Log.
影响因子：
--
作者：
Andreas Ecke;R. Peñaloza;Anni
通讯作者：
Anni
由概念相似性度量引起的阈值描述逻辑的可判定性和复杂性
DOI：
10.1145/3019612.3019715
发表时间：
2017
期刊：
Proceedings of the Symposium on Applied Computing
影响因子：
--
作者：
Franz Baader;Oliver Fernández Gil.
通讯作者：
Oliver Fernández Gil.