Learnability of Description Logics
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{cohen1992learnability,
author = {William W. Cohen and Haym Hirsh},
title = {{Learnability of Description Logics}},
booktitle = {Conference on Learning Theory},
year = {1992},
url = {https://openreview.net/forum?id=klMTAFgsJEo},
}Loading related content...