Grant: Discovery Grants Program - Individual

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.