Algorithmic learning theory and typed pattern languages

计算学习理论（英语：Computational Learning Theory，简称CLT）是理论计算机科学、数学和人工智能领域的一个分支。它的研究对象是机器学习的理论基础。我提出的研究计划解决了某些正式的CLT模型和机器学习在现实世界问题中的应用之间的差距。CLT模型是机器学习场景的形式化抽象，其中对真实的世界、学习者、信息源和成功学习的标准做出了假设。在这样一个正式的框架内，人们可以证明特定的机器学习任务可以实现（积极结果）或不能实现（消极结果）。CLT和应用机器学习之间的主要差距在于，CLT中的负面结果往往是由于不必要的悲观假设;积极结果往往是基于不切实际的乐观假设。我提出的研究关注的是机器学习的实际方面如何在正式模型中更好地表示。随着对有效学习的新关注，我将研究（a）建立在递归理论基础上的经典形式学习模型的变体，以及（B）建立在形式语言理论基础上的数据形式模型的变体及其在机器学习场景中向学习者表示的方式。 对于（a），我将设计和分析新的增量学习的正式模型，其中对流数据的有效学习进行建模。对于（B），我将重点关注所谓模式语言的类型化变体。类型化模式语言对于生物信息学和文本挖掘应用中的数据建模特别有用，但尚未得到系统的研究。 我的研究计划的预期收益是计算学习理论，形式语言理论和复杂性理论的新理论见解，以及在机器学习，数据挖掘和生物信息学中开发新的高效算法。

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. For (a), I will design and analyze new formal models of incremental learning, in which efficient learning from streaming data is modeled. For (b), my focus will be on typed variants of so-called pattern languages. Typed pattern languages are particularly useful for modeling data in bioinformatics and text mining applications but have not been studied systematically yet. Expected benefits of my research program are new theoretical insights in computational learning theory, formal language theory, and complexity theory, as well as the development of new efficient algorithms in machine learning, data mining, and bioinformatics.