On learnability and predicate logic (Extended Abstract)
Wolfgang Maass · 1995
) W. Maass Gy. Tur'an y 1 Introduction Several applications of learning in artificial intelligence use a predicate logic formalism. The theoretical study of efficient learnability in this area, in the framework of computational learning theory started relatively recently, considering, for example, the PAC ( Probably Approximately Correct ) learnability of logic programs and description logic ( see Cohen and Hirsh [6] , the survey of Kietz and Dzeroski [11] and the further references in these papers ). In this paper we discuss a model theoretic approach to learnability in predicate logic. Results in this direction were obtained by Osherson, Stob and Weinstein [15] . It is assumed that there is a first-order structure given. Instances are tuples of elements of the universe of the model, and concepts are relations that are definable in the model by formulas from some prespecified class. The goal of the learner is to identify an unknown target concept in some specific model of lear...