Automatic learners with feedback queries |
| |
Authors: | John Case Sanjay Jain Yuh Shin Ong Pavel Semukhin Frank Stephan |
| |
Affiliation: | 1. Department of Computer and Information Sciences, University of Delaware, Newark, DE 19716-2586, USA;2. Department of Computer Science, National University of Singapore, Singapore 117417, Republic of Singapore;3. Kurt Gödel Research Center for Mathematical Logic, Vienna, Austria;4. Department of Mathematics, National University of Singapore, Singapore 119076, Republic of Singapore |
| |
Abstract: | Automatic classes are classes of languages for which a finite automaton can decide whether a given element is in a set given by its index. The present work studies the learnability of automatic families by automatic learners which, in each round, output a hypothesis and update a long-term memory, depending on the input datum, via an automatic function. Many variants of automatic learners are investigated: where the long-term memory is restricted to be the current hypothesis whenever this exists, cannot be of length larger than the length of the longest datum seen, or has to consist of a constant number of examples seen so far. Learnability is also studied with respect to queries which reveal information about past data or past computation history; the number of queries per round is bounded by a constant. |
| |
Keywords: | Inductive inference Automatic learners Automatic families Feedback queries Long term memory Bounded example memory Iterative learning |
本文献已被 ScienceDirect 等数据库收录! |
|