Abstract
This paper solves an important problem left open in the literature by showing that U-shapes are unnecessary in iterative learning from positive data. A U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Iterative learning is a Gold-style learning model in which each of a learner’s output conjectures depends only upon the learner’s most recent conjecture and input element. Previous results had shown, for example, that U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning.
Work on the aforementioned problem led to the consideration of an iterative-like learning model, in which each of a learner’s conjectures may, in addition, depend upon the number of elements so far presented to the learner. Learners in this new model are strictly more powerful than traditional iterative learners, yet not as powerful as full explanatory learners. Can any class of languages learnable in this new model be learned without U-shapes? For now, this problem is left open.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Arikawa, S., Miyano, S., Shinohara, A., Kuhara, S., Mukouchi, Y., & Shinohara, T. (1993). A machine discovery from amino-acid-sequences by decision trees over regular patterns. New Generation Computing, 11, 361–375.
Angluin, D. (1980). Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21, 46–62.
Baliga, G., Case, J., Merkle, W., Stephan, F., & Wiehagen, W. (2007). When unlearning helps. Information and Computation. doi:10.1016/j.ic.2007.10.005. Available online through ScienceDirect. http://www.sciencedirect.com.
Blum, M. (1967). A machine independent theory of the complexity of recursive functions. Journal of the ACM, 14, 322–336.
Case, J. (1999). The power of vacillation in language learning. SIAM Journal on Computing, 28(6), 1941–1969.
Carlucci, L., Jain, S., Kinber, E., & Stephan, F. (2006). Variations on U-shaped learning. Information and Computation, 204, 1264–1294.
Carlucci, L., Case, J., Jain, S., & Stephan, F. (2007a). Non-U-shaped vacillatory and team learning. Journal of Computer and Systems Sciences. doi:10.1016/j.jcss.2007.06.013. Available online through ScienceDirect. http://www.sciencedirect.com.
Carlucci, L., Case, J., Jain, S., & Stephan, F. (2007b). Results on memory-limited U-shaped learning. Information and Computation, 205, 1551–1573.
Case, J., & Lynes, C. (1982). Machine inductive inference and language identification. In M. Nielsen & E. Schmidt (Eds.), Lecture notes in computer science : Vol. 140. Proceedings of the 9th international colloquium on automata, languages and programming (pp. 107–115). Berlin: Springer.
Case, J., & Moelius, S. E. (2007). U-shaped, iterative, and iterative-with-counter learning. In Lecture Notes in artificial intelligence : Vol. 4539. Proceedings of the 20th annual conference on learning theory (COLT’07) (pp. 172–186). Berlin: Springer.
Case, J., Jain, S., Lange, S., & Zeugmann, T. (1999). Incremental concept learning for bounded data mining. Information and Computation, 152, 74–110.
Davis, M., Sigal, R., & Weyuker, E. (1994). Computability, complexity, and languages (2nd ed.). New York: Academic Press.
Fulk, M. (1990). Prudence and other conditions on formal language learning. Information and Computation, 85, 1–11.
Fulk, M., Jain, S., & Osherson, D. (1994). Open problems in systems that learn. Journal of Computer and System Sciences 49(3), 589–604.
Gold, E. (1967). Language identification in the limit. Information and Control, 10, 447–474.
Jain, S. (2006). Private communication.
Jain, S., Osherson, D., Royer, J., & Sharma, A. (1999). Systems that learn: an introduction to learning theory (2nd ed.). Cambridge: Cambridge University Press.
Kinber, E., & Stephan, F. (1995). Language learning from texts: mind changes, limited memory, and monotonicity. Information and Computation, 123, 224–241.
Kuratowski, K., & Mostowski, A. (1967). Set theory. Amsterdam: North-Holland.
Lange, S., & Wiehagen, R. (1991). Polynomial time inference of arbitrary pattern languages. New Generation Computing, 8, 361–370.
Lange, S., & Zeugmann, T. (1996a). Incremental learning from positive data. Journal of Computer and System Sciences, 53, 88–103.
Lange, S., & Zeugmann, T. (1996b). Set-driven and rearrangement-independent learning of recursive languages. Mathematical Systems Theory, 6, 599–634.
Marcus, G., Pinker, S., Ullman, M., Hollander, M., Rosen, T. J., & Xu, F. (1992). Monographs of the society for research in child development : Vol. 54. Overregularization in language acquisition. University of Chicago Press: Chicago. Includes commentary by H. Clahsen.
Osherson, D., Stob, M., & Weinstein, S. (1986). Systems that learn: an introduction to learning theory for cognitive and computer scientists. Cambridge: MIT Press.
Plunkett, K., & Marchman, V. (1991). U-shaped learning and frequency effects in a multilayered perceptron: implications for child language acquisition. Cognition, 38, 43–102.
Rogers, H. (1967). Theory of recursive functions and effective computability. New York: McGraw Hill. Reprinted, MIT Press, 1987.
Schäfer-Richter, G. (1984). Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien. Rheinisch-Westfälische Technische Hochschule Aachen, Germany.
Shimozono, S., Shinohara, A., Shinohara, T., Miyano, S., Kuhara, S., & Arikawa, S. (1994). Knowledge acquisition from amino acid sequences by machine learning system BONSAI. Transactions of Information Processing Society of Japan, 35, 2009–2018.
Shinohara, T. & Arikawa, A. (1995). Pattern inference. In K.P. Jantke, & S. Lange (Eds.), Lecture notes in artificial intelligence : Vol. 961. Algorithmic learning for knowledge-based systems (pp. 259–291). Berlin: Springer.
Sierpinski, W. (1965). Cardinal and ordinal numbers (2nd ed.). Warsaw.
Taatgen, N. A., & Anderson, J. R. (2002). Why do children learn to say broke? A model of learning the past tense without feedback. Cognition, 86, 123–155.
Wexler, K., & Culicover, P. (1980). Formal principles of language acquisition. Cambridge: MIT Press.
Wiehagen, R. (1976). Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. Electronische Informationverarbeitung und Kybernetik, 12, 93–99.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors: Claudio Gentile, Nader H. Bshouty.
This paper is an expanded version of (Case and Moelius 2007).
Rights and permissions
About this article
Cite this article
Case, J., Moelius, S.E. U-shaped, iterative, and iterative-with-counter learning. Mach Learn 72, 63–88 (2008). https://doi.org/10.1007/s10994-008-5047-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10994-008-5047-9