Grant: Discovery Grants Program - Individual

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.