We consider the problem to learn a concept or a query in the presence of an ontology formulated in the description logic ELr, in Angluin's framework of active learning that allows the learning algorithm to interactively query an oracle (such as a domain expert). We show that the following can be learned in polynomial time: (1) EL-concepts, (2) symmetry-free ELI-concepts, and (3) conjunctive queries (CQs) that are chordal, symmetry-free, and of bounded arity. In all cases, the learner can pose to the oracle membership queries based on ABoxes and equivalence queries that ask whether a given concept/query from the considered class is equivalent to the target. The restriction to bounded arity in (3) can be removed when we admit unrestricted CQs in equivalence queries. We also show that EL-concepts are not polynomial query learnable in the presence of ELI-ontologies.
翻译:我们认为,当描述逻辑ELr、Angluin的积极学习框架内出现一种概念或问题时,学习一个概念或询问的问题,这种概念或询问是在描述逻辑ELr、Angluin的积极学习框架内拟订的,使学习算法能够交互质问一个神器(如域专家),我们表明,在多语种时间可以学习到以下概念或问题:(1)EL-概念,(2)无对称性ELI-概念,(3)合质查询,它们是相交的,无对称性,以及相互交错性。在所有情况下,学习者都可以根据ABoxes和等同性查询向成员提出询问,询问被考虑的阶级的某个特定概念/要求是否与目标相等。当我们在同等质询中接受不受限制的CQ时,可以取消对(3)中约束性限制的(3)的限制。我们还表明,EL-概念在存在ELI-onlogies时不是可学习的多元质询。