Self-Reference, Complexity, and Learning

计算学习中的许多结果都是由自我引用类见证的。例如，可以证明限制学习机输出总是与数据一致的猜想会降低学习能力|，这是由这样一个类所见证的。各种目击类的算法转换（可以消除自我引用）保留了一些学习能力结果，破坏了其他结果。有人建议对这一现象进行更彻底的调查，以便更好地了解学习。机器学习与实践/经验技术有关，寻求健壮的学习器，并且在某些情况下提供一致的学习器。PI和合作者最近表明，如果一个正式的鲁棒性要求所有可学习类的算法转换也必须是统一可学习的，那么所有这些可能的结果困难的学习都可以由一致的机器来完成。建议表明该结果并不扩展到不一定均匀的情况（或者它确实如此），希望从而获得对机器学习的洞察力。在此基础上，进一步扩展PI等人的工作，提出一种协调目标导向任务的学习理论。u型学习包括学习、遗忘和再学习。u型学习发生在人类认知发展的许多领域（包括语言、对温度的理解、对重量守恒的理解、对物体跟踪和物体持久性的理解之间的相互作用，以及人脸识别）。在算法学习（形式）语言语法的背景下，PI和合作者已经证明，对于一些可学习语言L的类别，任何学习L的机器M必须在L中的某些L上表现出u形学习。建议加强和扩展这一结果，并深刻地描述这些类L，并着眼于告知认知科学家。最后，提出将二类可行泛函与构造序数符号的可行计数结合使用，以获得可行迭代学习的一般概念。总的来说，上面提出的单独项目是高度相互联系和相互加强的，以获得复杂性理论，机器学习和认知科学的重要和统一的见解。

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.