Self-Reference, Complexity, and Learning

计算学习中的许多结果都是通过自我参照类来证明的。例如，可以证明，限制学习机器输出始终与其数据一致的结构会降低学习能力|就像这样一个阶级。见证类的各种算法变换（可以消除自引用）保留了一些学习能力结果，并破坏了其他结果。建议更彻底地调查这一现象，以便更深入地了解学习。 机器学习关注实用/经验技术，寻求强大的学习者，并且在某些情况下，提供一致的学习者。PI和合作者最近表明，如果考虑一种形式鲁棒性，要求可学习类的所有算法转换也必须是一致可学习的，那么所有可能的结果困难的学习都可以由一致的机器完成。我们建议证明这个结果并不延伸到不一定一致的情况（或者它确实如此），希望借此获得对机器学习的洞察力。 建议扩展PI和其他人的先前工作，以提供一种学习理论来协调以目标为导向的任务。U型学习包括学习、忘却和再学习。U形学习发生在人类认知发展的许多领域（包括语言，对温度的理解，对重量守恒的理解，对物体跟踪和物体持久性的理解之间的相互作用，以及面部识别）。在从关于这些语言的任何完整的正数据流中算法学习（形式）语言的语法的背景下，PI和合作者已经表明，对于某些类的可学习语言L，任何学习L的机器M必须在L中的某个L上表现出U形学习。建议加强和扩展这一结果，并有见地地描述这样的类L，并着眼于通知认知科学家。 最后，建议联合收割机使用类型2可行的功能和可行的倒计时从符号的建设性序数，以获得可行的迭代学习的一般概念。 一般来说，上面提出的各个项目是高度相互关联和相互加强的，以获得复杂性理论，机器学习和认知科学的重要和统一的见解。

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.