Learnability of description logics
Learnability of description logics
复制标题
描述逻辑的可学习性
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
H. Hirsh
中科院分区：
文献类型：
--
作者：
William W. Cohen;H. Hirsh
本文考虑一阶逻辑子集的可学习性。 Piror 的工作建立了可学习性的两个边界：Haussler [1989] 表明，一阶逻辑中的合取逻辑无法在 Valiant 模型中学习，即使合取的形式受到高度限制；另一方面，Valiant [1984] 表明命题连词是可以学习的。在本文中，我们研究了称为描述逻辑的受限一阶逻辑的可学习性。描述逻辑也是谓词演算的子集，但使用不同的语法来表达，从而允许探索一组不同的语法限制。在本文中，我们首先定义一个简单的描述逻辑，总结其表达能力的一些结果，然后分析其可学习性。结果表明，完整的逻辑无法轻松习得；然而，存在使学习易于处理的句法限制。即使原始类和角色（在其上构造描述）的字母表是无限的，可学习性结果仍然成立；因此，我们的积极结果不仅概括了 Valiant [1984] 关于学习单项式的结果，以学习我们（合取）一阶语言中的概念，而且概括了 Blum [1990] 关于在无限属性空间上学习单项式的结果。
This paper considers the learnability of subsets of first-order logic. Piror work has established two boundaries of learnability: Haussler [1989] has shown that conjunctions in first-order logic cannot be learned in the Valiant model, even if the form of the conjunction is highly restricted; on the other hand, Valiant [1984] has shown that propositional conjunctions are learnable. In this paper, we study the learnability of the restricted first-order logics known as description logics. 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. In this paper, 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 that enable tractable learning exist. The learnability results hold even if the alphabets of primitive classes and roles (over which descriptions are constructed) are infinite; our positive result thus generalizes not only the result of Valiant [1984] on learning monomials to learning concepts in our (conjunctive) first order language, but also the result of Blum [1990] on learning monomials over infinite attribute spaces.