The learnability of description logics with equality constraints
The learnability of description logics with equality constraints
复制标题
具有等式约束的描述逻辑的可学习性
DOI：
10.1007/bf00993470
复制
发表时间：
1994
期刊：
影响因子：
7.5
通讯作者：
H. Hirsh
中科院分区：
文献类型：
--
作者：
William W. Cohen;H. Hirsh
虽然关于用一阶逻辑表示的学习概念的实验研究越来越多，但关于一阶表示的多项式可学习性的形式化结果仍然相对较少。PAC模型中的大多数分析都集中在PROLOG的子集上，只有少数高度受限的子集被证明是可学习的。在本文中，我们将改为研究被称为“描述逻辑”的受限一阶逻辑的可学性，有时也被称为“术语逻辑”或“KL-One-type语言”。描述逻辑也是谓词演算的子集，但使用不同的语法表示，从而允许探索不同的语法限制集。我们首先定义了一个简单的描述逻辑，总结了关于它的表达能力的一些结果，然后分析了它的可学习性。这表明，完整的逻辑不能很容易地学习。然而，存在句法限制，使得仅从正例学习就可以很容易地进行，而与用于描述例句的词汇量无关。这种可学习的子语言在表达能力上似乎是以前已知的可学习的一阶逻辑的任何子集所无法比拟的。
Although there is an increasing amount of experimental research on learning concepts expressed in first-order logic, there are still relatively few formal results on the polynomial learnability of first-order representations from examples. Most previous analyses in the pac-model have focused on subsets of Prolog, and only a few highly restricted subsets have been shown to be learnable. In this paper, we will study instead the learnability of the restricted first-order logics known as “description logics”, also sometimes called “terminological logics” or “KL-ONE-type languages”. Description logics are also subsets of predicate calculus, but are expressed using a different syntax, allowing a different set of syntactic restrictions to be explored. We first define a simple description logic, summarize some results on its expressive power, and then analyze its learnability. It is shown that the full logic cannot be tractably learned. However, syntactic restrictions exist that enable tractable learning from positive examples alone, independent of the size of the vocabulary used to describe examples. The learnable sublanguage appears to be incomparable in expressive power to any subset of first-order logic previously known to be learnable.