Title:
|
Learning intersection-closed classes with signatures
|
Author:
|
Bulatov, Andrei; Chen, Hubie; Dalmau, Víctor
|
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. |
Abstract:
|
The first author was supported by an NSERC Discovery Grant. The second and third authors were supported by grant TIC 2002-04470-C03 and the EU PASCAL Network of Excellence IST-2002-506778. The third author was also supported by the MEC under the program “Ramon y Cajal”, grant TIC 2002-04019-C03, and MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. |
Subject(s):
|
-Computational learning -Closure algorithm -Polymorphism -Quantified formulas |
Rights:
|
© Elsevier http://dx.doi.org/10.1016/j.tcs.2007.03.039 |
Document type:
|
Article Article - Accepted version |
Published by:
|
Elsevier
|
Share:
|
|