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.