Self-Reference, Complexity, and Learning

University Of Delaware, Newark DE

Investigators

Abstract

Many results in computational learning are witnessed by self-referential classes. For example, one can show that restricting learning machines to output always conjectures consistent with their data lessens learning power | as witnessed by such a class. Various kinds of algorithmic transformations of witnessing classes (which can eliminate the self-reference) preserves some learn ability results and destroys others. It is proposed to investigate this phenomenon more thoroughly for greater insight into learning. Machine learning, which is concerned with practical/empirical techniques, seeks robust learners, and, in some cases, provides consistent learners. The PI and collaborators recently showed that, if one considers a formal robustness requiring that all algorithmic transformations of learnable classes must be uniformly learnable as well, then all such resultantly difficult learning that's possible can be done by consistent machines. It is proposed to show this result does not extend to the not-necessarily-uniformly case (or that it does) with the hope of thereby gaining insight for machine learning. It is proposed to extend prior work of the PI and others to provide a theory of learning to coordinate goal-oriented tasks. U-shaped learning involves learning, unlearning, and re-learning. U-shaped learning occurs in many domains of human cognitive development (including language, understanding of temperature, understanding of weight conservation, the interaction between understanding of object tracking and object permanence, and face recognition). In the context of algorithmically learning grammars for (formal) languages from any stream of complete positive data about those languages, it has been shown by the PI and collaborators that, for some classes of learnable languages L, any machine M which learns L must exhibit, on some L in L, U-shaped learning. It is proposed to strengthen and extend this result and to characterize insightfully such classes L and with an eye to informing the cognitive scientist. Lastly, it is proposed to combine the use of type-2 feasible functional and feasible counting down from notations for constructive ordinals to obtain general concepts of feasible iterative learning. In general, the separate items proposed above are highly interconnected and mutually reinforcing toward obtaining important and unifying insights for complexity theory, machine learning, and cognitive science.