Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T17:27:04.215Z Has data issue: false hasContentIssue false
  • English
  • Français

Anomalous Vacillatory Learning

Published online by Cambridge University Press:  12 March 2014

Achilles A. Beros
Achilles A. Beros*
Affiliation:
Department of Mathematics, University of Wisconsin - Madison, Madison, WI 53706, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex** and TxtFext**, could be distinguished [3]. 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** ≠ TxtFext**, thereby answering the question posed by Osherson, et al. We prove this in a strong way by exhibiting a family in TxtFex*2 TxtFext**.

Keywords

Inductive InferenceLearning TheoryVacillatory Learning
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 4 , December 2013 , pp. 1183 - 1188
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Case, J., The power of vacillation, SIAM Journal of Computation, vol. 49 (1999), no. 6, pp. 1941–1969.Google Scholar
[2] Jain, S., Fulk, M. and Osherson, D., Open problems in “systems that learn”, Journal of Computer and System Sciences, vol. 49 (1994), pp. 589–604.Google Scholar
[3] Stob, M., Osherson, D. and Weinstein, S., Systems that learn: An introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, MA, 1986.Google Scholar