Can I read Learning Atomic Formulas with Prescribed Properties on EtoBox?

Learning Atomic Formulas with Prescribed Properties by Irene Tsapara; György Turán is a scholarly article available to read on EtoBox.

What is Learning Atomic Formulas with Prescribed Properties about?

We consider the learnability of some concept classes in predicate logic with proper equivalence queries. Concepts are represented by atomic formulas over a restricted language. The concept represented by an atomic formula consists of its ground instances having bounded depth. In addition, it is assumed that there is a first-order sentence given, and the COIIcept class contains only those atomic forrnulas which satisfy this sentence. For instance, one may consider the learnability of atomic formulas that represent symmetric, or transitive concepts. It is shown that every such concept class can be learned with O(m2 +m log n) queries, where m is the quantifier rank of the sentence and n is the depth bound for the ground instances. The proof uses a combination of tools from logic and learning algorithms for geometric concepts. Model theoretic games are used to determine the structure of the concept classes. We formulate a constrained version of the problem of learning two-dimensional axis-parallel rectangles, where one corner is required to belong to a prespecified subset. A sufficient condition is given for the efficient learnability of a rectangle in terms of the geometric properties

Author

Irene Tsapara; György Turán

Publisher

ACM

Published

1998

Language

EN