Revising threshold functions
| Autor: | György Turán, Robert H. Sloan, Balázs Szörényi |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Theoretical computer science
General Computer Science 0102 computer and information sciences 02 engineering and technology Threshold function 01 natural sciences Theoretical Computer Science 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Query learning 020201 artificial intelligence & image processing Equivalence (formal languages) Boolean function Theory revision Algorithm Mathematics Boolean threshold function Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 382(3):198-208 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2007.03.034 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect