Learning intersection-closed classes with signatures
Learning intersection-closed classes with signatures
Citation
- Bulatov A, Chen H, Dalmau V. Learning intersection-closed classes with signatures. Theor Comput Sci. 2007 Sep 6;382(3):209-20. DOI: 10.1016/j.tcs.2007.03.039
Permanent Link
Description
Abstract
Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature.