Algorithmic learning theory and typed pattern languages

点击翻译按钮获取中文摘要

Computational Learning Theory (CLT) is a field within the scope of theoretical computer science, mathematics, and artificial intelligence. Its subject of research is the theoretical foundation of machine learning. My proposed research program addresses the gaps between certain formal CLT models and applications of machine learning to real-world problems. CLT models are formal abstractions of machine learning scenarios, in which assumptions are made about the real world, the learner, the source of information, and the criteria for successful learning. Within such a formal framework, one can prove that a specific machine learning task can be achieved (positive results) or cannot be achieved (negative results). The major gap between CLT and applied machine learning is that negative results in CLT are often due to assumptions that are unnecessarily pessimistic; positive results are often based on unrealistically optimistic assumptions. My proposed research is concerned with how practical aspects of machine learning can be better represented in formal models. With a new focus on efficient learning, I will study (a) variants of classical formal learning models, built on recursion theory, and (b) variants of formal models of the data and the way they are represented to the learner in machine learning scenarios, built on formal language theory.