Revising threshold functions |
| |
Authors: | Robert H Sloan Balázs Szörényi György Turán |
| |
Affiliation: | 1. Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7053, USA;2. Research Group on Artificial Intelligence, Hungarian Academy of Sciences and University of Szeged, Szeged, 6720, Hungary;3. Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7045, USA |
| |
Abstract: | A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the resource one is interested in) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give an efficient revision algorithm in the model of learning with equivalence and membership queries for threshold functions, and some negative results showing, for instance, that threshold functions cannot be revised efficiently from either type of query alone. The algorithms work in a general revision model where both deletion and addition type revision operators are allowed. |
| |
Keywords: | Theory revision Threshold function Boolean threshold function Query learning |
本文献已被 ScienceDirect 等数据库收录! |
|