Anomalous vacillatory learning

DOI10.2178/JSL.7804090MaRDI QIDQ5407047zbMATH OpenOpenAlexFDO

Authors Achilles A. Beros

Publication date 4 April 2014

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.2051, https://projecteuclid.org/euclid.jsl/1388954000

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Abstract: In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex^*_* and TxtFext^*_*, could be distinguished. In both, a machine is permitted to vacillate between a finite number of hypotheses and to make a finite number of errors. TxtFext^*_*-learning requires that hypotheses output infinitely often must describe the same finite variant of the correct set, while TxtFex^*_*-learning permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that TxtFex^*_* eq TxtFext^*_*, thereby answering the question posed by Osherson, extit{et al}. We prove this in a strong way by exhibiting a family in TxtFex^*_2 setminus {TxtFext}^*_*.

Recommendations

• Complexity issues for vacillatory function identification
• The Power of Vacillation in Language Learning
• Learning theory in the arithmetic hierarchy. II.
• On learning of functions refutably.
• Learning Theory

Cited in

(1)

• Learning theory in the arithmetic hierarchy. II.

This page was built for publication: Anomalous vacillatory learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5407047)