Anomalous vacillatory learning. (English) Zbl 1290.68061

Summary: In 1986, D. N. Osherson, M. Stob and S. Weinstein asked whether two variants of anomalous vacillatory learning, \(\mathrm{TxtFex}^\ast_\ast\) and \(\mathrm{TxtFext}^\ast_\ast\), could be distinguished [Systems that learn: an introduction to learning theory for cognitive and computer scientists. MA: MIT Press University (1986), http://mitpress.mit.edu/books/systems-learn]. In both, a machine is permitted to vacillate between a finite number of hypotheses and to make a finite number of errors. \(\mathrm{TxtFext}^\ast_\ast\)-learning requires that hypotheses output infinitely often must describe the same finite variant of the correct set, while \(\mathrm{TxtFex}^\ast_\ast\)-learning permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that \(\mathrm{TxtFex}^\ast_\ast\neq\mathrm{TxtFext}^\ast_\ast\), thereby answering the question posed by Osherson et al. [loc. cit.]. We prove this in a strong way by exhibiting a family in \(\mathrm{TxtFex}^\ast_2\setminus\mathrm{TxtFext}^\ast_\ast\).


68Q32 Computational learning theory
Full Text: DOI arXiv Euclid