Models and algorithms for interactive machine learning applied to formal languages and geometric concepts

应用机器学习的一个核心问题是，通常需要的数据量大于可用或负担得起的数据量，例如，当必须进行昂贵的实验室实验以生成数据时，例如在生物医学研究中经常出现的情况，或者必须学习涉及基于计算机的系统的单个用户的模式（而不是涉及大量用户的模式）。我在计算学习理论领域的研究建议通过交互式机器学习理论来解决这个问题。这里的交互是指学习算法或环境主动控制关于要学习的目标对象的哪些信息被交换。交互式机器学习与各种应用具有高度相关性，例如，人类与学习系统交互并被学习系统观察的应用。我的目标是设计和分析交互式学习的正式模型，并开发算法技术，以比目前可能的更少的数据有效地解决复杂的学习问题。******我提出的模型与学习者根据一些数据分布随机选择数据的模型形成鲜明对比；特别是，它们旨在利用潜在目标对象的结构属性，以便与随机采样数据的情况相比，减少学习所需的数据点数量。******关于学习的目标对象，我将侧重于学习形式语言或几何概念的情况。******我计划学习的形式语言类是所谓模式语言的变体。模式语言在计算学习理论中的研究已经超过35年了，因为它们具有简单的定义，有趣的结构和语言理论特性，以及它们在生物信息学，自动程序合成，数据库理论和模式匹配等领域的众多应用。它们非常适合于文本数据交互式学习的研究。***几何概念，如n维轴对齐盒的（并），线性半空间等，自该领域的早期以来在计算学习理论中非常受欢迎，部分原因是线性模型在机器学习中的成功，但部分原因是低维情况下的几何概念为我们提供了对成功学习算法的直观解释以及对学习有用的数据集。我的建议是利用这种直观的解释来推进我们对新的（尚未完全理解的）互动学习模型的理解。

A central problem in applied machine learning is that often data is required in larger quantities than are available or affordable, for instance, when costly lab experiments have to be conducted to generate data, as is often the case in biomedical research, or when patterns concerning a single user of a computer-based system (rather than patterns concerning a large pool of users) have to be learned. My proposed research in the field of computational learning theory addresses this problem by means of the theory of interactive machine learning. Interaction here means that the learning algorithm or the environment actively controls which information is exchanged about the target object to be learned. Interactive machine learning is of high relevance for a variety of applications, e.g., those in which a human interacts with and is observed by a learning system. My objective is to design and analyze formal models of interactive learning and to develop algorithmic techniques that can efficiently solve complex learning problems with less data than is currently possible.******The models I propose stand in sharp contrast to models in which the learner receives data chosen at random according to some data distribution; in particular they aim at exploiting structural properties of the potential target objects in order to reduce the number of data points needed for learning in comparison to the case when data is sampled at random.******Concerning the target objects for learning, I will focus on cases in which formal languages or geometric concepts are to be learned.******The classes of formal languages I plan to study are variants of the so-called pattern languages. Pattern languages have been studied in computational learning theory for over 35 years, due to their appealingly simple definition, their interesting structural and language-theoretic properties, as well as their numerous applications in areas such as bioinformatics, automatic program synthesis, database theory, and pattern matching. They are well-suited to a study of interactive learning on text data.***Geometric concepts, such as (unions of) axis-aligned boxes in n dimensions, linear halfspaces, etc., have enjoyed great popularity in computational learning theory since the early days of the field, partly because of the success of linear models in machine learning, but partly also because geometric concepts in the low-dimensional case provide us with an intuitive interpretation of successful learning algorithms as well as of data sets that are useful for learning. My suggestion is to leverage such intuitive interpretation for advancing our understanding of new (and not yet fully understood) models of interactive learning.