Result: Revising threshold functions

Title:
Revising threshold functions
Authors:
SLOAN, Robert H, SZÖRENYI, Balazs, TURAN, György
Source:
Algorithmic learning theoryTheoretical computer science. 382(3):198-208
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 27 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Ordre, treillis, structures algébriques ordonnées, Order, lattices, ordered algebraic structures, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Intelligence artificielle, Artificial intelligence, Apprentissage et systèmes adaptatifs, Learning and adaptive systems, Addition, Adicción, Algorithme apprentissage, Learning algorithm, Algoritmo aprendizaje, Apprentissage, Learning, Aprendizaje, Complexité, Complexity, Complejidad, Concept, Concepto, Distance, Distancia, Délétion, Deletion, Deleción, Equivalence, Equivalencia, Fonction booléenne, Boolean function, Función booliana, Fonction seuil, Threshold function, Función umbral, Informatique théorique, Computer theory, Informática teórica, Polynôme, Polynomial, Polinomio, Requête, Query, Pregunta documental, Ressource, Resource, Recurso, Seuil, Threshold, Umbral, Univers, Universe, Universo, 06E30, 68T05, 68Wxx, Interrogation appartenance, Modèle apprentissage, Terme, Boolean threshold function, Query learning, Theory revision
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7053, United States
Research Group on Artificial Intelligence, Hungarian Academy of Sciences and University of Szeged, Szeged, 6720, Hungary
Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7045, United States
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19034085
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.19034085
Database:
PASCAL Archive

Further Information

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.