U-SHAPED LEARNING MAY BE NECESSARY

LORENZO CARLUCCI

Abstract. U-shaped learning behaviour in cognitive development involves learning, unlearning and relearning. It occurs, for example, in learning irregular verbs, which is a central topic in the cognitive science debate about learning models. The prior cognitive science literature is occupied with how humans do it, for example, general rules versus tables of exceptions. This paper is mostly concerned with whether U-shaped learning behaviour may be necessary in the abstract mathematical setting of inductive inference from positive data, that is, in the computational learning theory following the framework of Gold. Previous work showed that U-shaped learning behaviour is necessary for behaviourally correct learning but not for syntactically convergent, learning in the limit (= explanatory learning). The present paper establishes the necessity for the whole hierarchy of classes of vacillatory learning where a behaviourally correct learner has to satisfy the additional constraint that it vacillates in the limit between at most k grammars, where k ≥ 1. Non U-shaped vacillatory learning is shown to be restrictive: Every non U-shaped vacillatorily learnable class is already learnable in the limit. Furthermore, if vacillatory learning with the parameter k = 2 is possible then non U-shaped behaviourally correct learning is also possible. But for k = 3, surprisingly, there is a class witnessing that this implication fails.

REFERENCES

[1] G. Baliga, J. Case, W. Merkle and F. Stephan. Unlearning helps. In U. Montanari, J. Rolim, and E. Welzl, editors, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 1853, pages 844–855. Springer-Verlag, 2000.

[2] L. Carlucci, J. Case, S. Jain, F. Stephan. U-shaped learning may be necessary. submitted to Journal of Computer and Systems Sciences, 2004.

DIPARTIMENTO DI MATEMATICA

UNIVERSITÀ DI SIENA

PIAN DEI MANTELLINI 44

53100 SIENA ITALY

and

DEPARTMENT OF COMPUTER AND INFORMATION SCIENCES

UNIVERSITY OF DELAWARE

NEWARK, DE 19716

USA

E-mail: carlucci5@unisi.it

The results are joint work with John Case, Sanjay Jain and Frank Stephan, and have been presented at the meeting of the Society for Mathematical Psychology, SMP 2004.